論文の概要: Fast Gumbel-Max Sketch and its Applications
- arxiv url: http://arxiv.org/abs/2302.05176v1
- Date: Fri, 10 Feb 2023 11:09:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 16:03:49.712389
- Title: Fast Gumbel-Max Sketch and its Applications
- Title（参考訳）: 高速ガンベルマックススケッチとその応用
- Authors: Yuanming Zhang and Pinghui Wang and Yiyan Qi and Kuankuan Cheng and
Junzhou Zhao and Guangjian Tian and Xiaohong Guan
- Abstract要約: 我々はFastGMを提案し、これは時間複雑性を$O(kn+)$から$O(kln k + n+)$に還元する。
FastGMは、精度を犠牲にしたり追加費用を発生させることなく、最先端の手法よりも桁違いに高速である。
- 参考スコア（独自算出の注目度）: 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 non-negative vector) and its variants have
been widely used in areas such as machine learning and information retrieval.
To sample a random element $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 weighted cardinality estimation 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, FastGM, which 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. FastGM stops the procedure of Gumbel random variables
computing for many elements, especially for those with small weights. We
perform experiments on a variety of real-world datasets and the experimental
results demonstrate that FastGM is orders of magnitude faster than
state-of-the-art methods without sacrificing accuracy or incurring additional
expenses.
- Abstract（参考訳）: カテゴリー分布(あるいは一般には非負ベクトル)から要素をサンプリングするための有名なガンベル・マックス・トリックとその変種は、機械学習や情報検索などの分野で広く使われている。
Gumbel-Max Trickは、その正の重みに比例してランダム要素$i$をサンプリングするために、まず、各正の重み要素$i$に対してGumbelランダム変数$g_i$を計算し、次に最大値$g_i+\ln v_i$で要素$i$をサンプリングする。
近年、類似度推定や重み付けされた濃度推定を含む応用では、高次元ベクトルから$k$独立なGumbel-Max変数を生成する必要がある。
しかし、従来のgumbel-maxトリックを使用する場合、大きなk$(例えば数百ドルや数千ドル)の計算コストがかかる。
この問題を解決するために、FastGMという新しいアルゴリズムを提案する。これは、時間複雑性を$O(kn^+)$から$O(k \ln k + n^+)$に減らし、$n^+$は興味のあるベクトルの正の要素の数である。
FastGMは、Gumbelランダム変数の多くの要素、特に小さな重みを持つ要素の計算を停止する。
実世界の様々なデータセットの実験を行い、実験結果から、FastGMは精度を犠牲にしたり、追加費用を発生させることなく、最先端の手法よりも桁違いに高速であることが示された。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
論文 参考訳（メタデータ） (2021-06-05T01:58:40Z) - 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) - Fast Generating A Large Number of Gumbel-Max Variables [35.751963721335045]
分類分布から要素をサンプリングするGumbel-Max Trickは、機械学習や情報検索などの分野で広く使われている。
我々は,f(nln k + n+)$から$O(kln k + n+)$へ時間複雑性を減少させる新しいアルゴリズム,emphFastGMを提案する。
我々のメソッドFastGMは、順に全ての正の要素に対して$g_i+ln v_i$を計算します。
論文 参考訳（メタデータ） (2020-02-02T15:15:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。