論文の概要: The Sparse Hausdorff Moment Problem, with Application to Topic Models
- arxiv url: http://arxiv.org/abs/2007.08101v3
- Date: Mon, 7 Sep 2020 17:24:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 22:51:28.561245
- Title: The Sparse Hausdorff Moment Problem, with Application to Topic Models
- Title（参考訳）: スパースハウスドルフモーメント問題とトピックモデルへの応用
- Authors: Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman, Yuval Rabani
- Abstract要約: 我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
- 参考スコア（独自算出の注目度）: 5.151973524974052
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of identifying, from its first $m$ noisy moments, a
probability distribution on $[0,1]$ of support $k<\infty$. This is equivalent
to the problem of learning a distribution on $m$ observable binary random
variables $X_1,X_2,\dots,X_m$ that are iid conditional on a hidden random
variable $U$ taking values in $\{1,2,\dots,k\}$. Our focus is on accomplishing
this with $m=2k$, which is the minimum $m$ for which verifying that the source
is a $k$-mixture is possible (even with exact statistics). This problem, so
simply stated, is quite useful: e.g., by a known reduction, any algorithm for
it lifts to an algorithm for learning pure topic models.
We give an algorithm for identifying a $k$-mixture using samples of $m=2k$
iid binary random variables using a sample of size $\left(1/w_{\min}\right)^2
\cdot\left(1/\zeta\right)^{O(k)}$ and post-sampling runtime of only
$O(k^{2+o(1)})$ arithmetic operations. Here $w_{\min}$ is the minimum
probability of an outcome of $U$, and $\zeta$ is the minimum separation between
the distinct success probabilities of the $X_i$s. Stated in terms of the moment
problem, it suffices to know the moments to additive accuracy
$w_{\min}\cdot\zeta^{O(k)}$. It is known that the sample complexity of any
solution to the identification problem must be at least exponential in $k$.
Previous results demonstrated either worse sample complexity and worse $O(k^c)$
runtime for some $c$ substantially larger than $2$, or similar sample
complexity and much worse $k^{O(k^2)}$ runtime.
- Abstract（参考訳）: 我々は、最初の$m$ノイズモーメントから、$[0,1]$のサポート$k<\infty$の確率分布を識別する問題を考える。
これは$m$オブザーバブルバイナリ確率変数 $x_1,x_2,\dots,x_m$ の分布を学習する問題と同値であり、これは$\{1,2,\dots,k\}$ で値を取る隠れた確率変数 $u$ 上で iid 条件付きである。
私たちはこれを$m=2k$で達成することに注力しています。これは、ソースが$k$-mixtureであることを確認するための最小の$m$です。
この問題は、単に述べられているように、非常に有用である:例えば、既知の還元によって、その問題のアルゴリズムは純粋なトピックモデルを学ぶアルゴリズムに持ち上げられる。
1/w_{\min}\right)^2 \cdot\left(1/\zeta\right)^{O(k)}$と、$O(k^{2+o(1)})$算術演算のみのポストサンプリングランタイムを用いて、$m=2k$のバイナリ変数のサンプルを用いて$k$-mixtureを識別するアルゴリズムを提供する。
ここで$w_{\min}$は$U$の結果の最小確率であり、$\zeta$は$X_i$sの異なる成功確率の間の最小分離である。
モーメント問題の観点から言えば、加算精度$w_{\min}\cdot\zeta^{O(k)}$のモーメントを知るのに十分である。
識別問題に対する任意の解のサンプル複雑性は少なくとも$k$で指数関数的になければならないことが知られている。
以前の結果は、サンプルの複雑さが悪く、さらに悪い$O(k^c)$ランタイムが2ドルよりかなり大きいか、類似のサンプルの複雑さとずっと悪い$k^{O(k^2)}$ランタイムが示されていた。
関連論文リスト
- One-Shot Learning for k-SAT [2.6293381978389787]
我々は、$k$-SATのワンショット学習が、満足度しきい値を大きく下回っていることを示す。
学習アルゴリズムの解析を単純化し、$d$のより強いバウンダリを$beta$で取得する。
論文 参考訳（メタデータ） (2025-02-10T23:56:08Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。
目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文 参考訳（メタデータ） (2024-03-14T15:04:45Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か?
この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
論文 参考訳（メタデータ） (2019-04-26T21:42:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。