論文の概要: Fast Generating A Large Number of Gumbel-Max Variables
- arxiv url: http://arxiv.org/abs/2002.00413v1
- Date: Sun, 2 Feb 2020 15:15:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 19:56:50.097114
- Title: Fast Generating A Large Number of Gumbel-Max Variables
- Title(参考訳): 多数のgumbel-max変数を高速に生成する
- Authors: Yiyan Qi, Pinghui Wang, Yuanming Zhang, Junzhou Zhao, Guangjian Tian,
and Xiaohong Guan
- Abstract要約: 分類分布から要素をサンプリングするGumbel-Max Trickは、機械学習や情報検索などの分野で広く使われている。
我々は,f(nln k + n+)$から$O(kln k + n+)$へ時間複雑性を減少させる新しいアルゴリズム,emphFastGMを提案する。
我々のメソッドFastGMは、順に全ての正の要素に対して$g_i+ln v_i$を計算します。
- 参考スコア(独自算出の注目度): 35.751963721335045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The well-known Gumbel-Max Trick for sampling elements from a categorical
distribution (or more generally a nonnegative vector) and its variants have
been widely used in areas such as machine learning and information retrieval.
To sample a random element $i$ (or a Gumbel-Max variable $i$) in proportion to
its positive weight $v_i$, the Gumbel-Max Trick first computes a Gumbel random
variable $g_i$ for each positive weight element $i$, and then samples the
element $i$ with the largest value of $g_i+\ln v_i$. Recently, applications
including similarity estimation and graph embedding require to generate $k$
independent Gumbel-Max variables from high dimensional vectors. However, it is
computationally expensive for a large $k$ (e.g., hundreds or even thousands)
when using the traditional Gumbel-Max Trick. To solve this problem, we propose
a novel algorithm, \emph{FastGM}, that reduces the time complexity from
$O(kn^+)$ to $O(k \ln k + n^+)$, where $n^+$ is the number of positive elements
in the vector of interest. Instead of computing $k$ independent Gumbel random
variables directly, we find that there exists a technique to generate these
variables in descending order. Using this technique, our method FastGM computes
variables $g_i+\ln v_i$ for all positive elements $i$ in descending order. As a
result, FastGM significantly reduces the computation time because we can stop
the procedure of Gumbel random variables computing for many elements especially
for those with small weights. Experiments on a variety of real-world datasets
show that FastGM is orders of magnitude faster than state-of-the-art methods
without sacrificing accuracy and incurring additional expenses.
- Abstract(参考訳): カテゴリー分布(あるいは一般には非負ベクトル)から要素をサンプリングするための有名なガンベル・マックス・トリックとその変種は、機械学習や情報検索などの分野で広く使われている。
ランダム要素 $i$ を正の重み $v_i$ に比例してサンプリングするために、gumbel-max トリックはまず各正の重み要素 $i$ に対してガムベル確率変数 $g_i$ を計算し、次に$i$ を最大値 $g_i+\ln v_i$ でサンプリングする。
近年、類似度推定やグラフ埋め込みを含むアプリケーションは、高次元ベクトルから$k$独立のgumbel-max変数を生成する必要がある。
しかし、従来のgumbel-maxトリックを使用する場合、大きなk$(例えば数百ドルや数千ドル)の計算コストがかかる。
この問題を解決するために、新しいアルゴリズムである \emph{fastgm} を提案する。これは、時間の複雑さを$o(kn^+)$ から $o(k \ln k + n^+)$ に減らすもので、ここで $n^+$ は関心ベクトル内の正の要素の数である。
k$独立のgumbel確率変数を直接計算する代わりに、これらの変数を次々に生成するテクニックがあることが分かりました。
この手法を用いて、FastGMは下降順に全ての正の要素に対して$g_i+\ln v_i$を演算する。
その結果,多くの要素に対するガムベル確率変数の計算,特に小さい重みを持つ場合の計算を中止できるため,fastgmは計算時間を著しく短縮する。
さまざまな実世界のデータセットの実験によると、FastGMは精度を犠牲にせず、追加のコストを発生させることなく、最先端の手法よりも桁違いに高速である。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - Fast Gumbel-Max Sketch and its Applications [35.751963721335045]
我々はFastGMを提案し、これは時間複雑性を$O(kn+)$から$O(kln k + n+)$に還元する。
FastGMは、精度を犠牲にしたり追加費用を発生させることなく、最先端の手法よりも桁違いに高速である。
論文 参考訳(メタデータ) (2023-02-10T11:09:47Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳(メタデータ) (2022-03-18T18:50:52Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳(メタデータ) (2021-11-30T14:16:48Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳(メタデータ) (2020-08-01T19:23:34Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-06-11T00:55:35Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。