論文の概要: Exact marginal inference in Latent Dirichlet Allocation

• arxiv url: http://arxiv.org/abs/2004.00115v1
• Date: Tue, 31 Mar 2020 21:14:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-18 00:22:25.568024
• Title: Exact marginal inference in Latent Dirichlet Allocation
• Title（参考訳）: 潜在ディリクレ割当における厳密な辺縁推論
• Authors: Hartmut Maennel
• Abstract要約: より正確なベイズ推定は、驚くほど単純な式で与えられた上界の$n$に対して$|Z|$で線形時間で計算できることが示される。 このアルゴリズムをスパース確率$beta(w|z)$の場合に一般化し、観測上の「相互作用グラフ」のツリー幅が制限されていると仮定する。
• 参考スコア（独自算出の注目度）: 1.441340412842035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Assume we have potential "causes" $z\in Z$, which produce "events" $w$ with known probabilities $\beta(w|z)$. We observe $w_1,w_2,...,w_n$, what can we say about the distribution of the causes? A Bayesian estimate will assume a prior on distributions on $Z$ (we assume a Dirichlet prior) and calculate a posterior. An average over that posterior then gives a distribution on $Z$, which estimates how much each cause $z$ contributed to our observations. This is the setting of Latent Dirichlet Allocation, which can be applied e.g. to topics "producing" words in a document. In this setting usually the number of observed words is large, but the number of potential topics is small. We are here interested in applications with many potential "causes" (e.g. locations on the globe), but only a few observations. We show that the exact Bayesian estimate can be computed in linear time (and constant space) in $|Z|$ for a given upper bound on $n$ with a surprisingly simple formula. We generalize this algorithm to the case of sparse probabilities $\beta(w|z)$, in which we only need to assume that the tree width of an "interaction graph" on the observations is limited. On the other hand we also show that without such limitation the problem is NP-hard.
• Abstract（参考訳）: 潜在的な " becauses" $z\in Z$ が存在し、既知の確率を持つ "events" $w$ が生成されると仮定する。 我々は、w_1,w_2,...,w_n$を観察し、原因の分布について何が言えるか? ベイズ推定は、$z$ の分布の事前を仮定し(dirichlet pre を仮定する)、後続を計算する。 その後部の平均値から、Z$の分布が得られ、Z$が観測にどれだけ貢献したかが推定される。 これはLatent Dirichlet Allocationの設定で、例えばドキュメント内の「生成」単語のトピックに適用することができる。 この設定では、通常、観察される単語の数は大きいが、潜在的な話題の数は少ない。 ここでは、多くの潜在的な「原因」(地球上の場所など)を持つアプリケーションに興味を持っているが、観測はわずかである。 より正確なベイズ推定は、驚くほど単純な式で与えられた上界の$n$に対して$|Z|$で線形時間(および定数空間)で計算できることを示す。 このアルゴリズムをスパース確率 $\beta(w|z)$ の場合に一般化し、観測上の「相互作用グラフ」の木の幅が限られていると仮定するだけでよい。 一方、そのような制限がなければ、問題はNPハードであることが示される。

関連論文リスト

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
  この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。 特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
  論文  参考訳（メタデータ） (2023-09-17T01:45:13Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• On the Multidimensional Random Subset Sum Problem [0.9007371440329465]
  確率変数 $X_1, ..., X_n$ が与えられたランダム部分集合 Sum 問題では、任意の点 $z in [-1,1]$ を部分集合 $X_i_1(z), ..., X_i_s(z)$ の和として近似したい。 我々は、$d$次元において、$n = O(d3log frac 1varepsilon cdot
  論文  参考訳（メタデータ） (2022-07-28T08:10:43Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• List-Decodable Sparse Mean Estimation [7.594050968868919]
  最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。 本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
  論文  参考訳（メタデータ） (2022-05-28T05:13:45Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Consistent regression when oblivious outliers overwhelm [8.873449722727026]
  我々の研究に先立ち、ガウスの$X$でさえ、$beta*$ の見積子は、このモデルでは一貫性がないことが知られていた。 ほぼ線形なサンプルサイズと逆ポリノミアル不整分率で一貫した推定が可能であることを示す。 ここで研究したモデルは、最初の瞬間さえも持たない重い尾の雑音の分布も捉えている。
  論文  参考訳（メタデータ） (2020-09-30T16:21:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。