論文の概要: Optimal estimation of sparse topic models
- arxiv url: http://arxiv.org/abs/2001.07861v1
- Date: Wed, 22 Jan 2020 03:19:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 18:12:53.709759
- Title: Optimal estimation of sparse topic models
- Title（参考訳）: スパーストピックモデルの最適推定
- Authors: Xin Bing and Florentina Bunea and Marten Wegkamp
- Abstract要約: 本稿では、要素的にスパースである可能性のある$A$の推定について検討し、$K$のトピックの数は不明である。
我々は、そのような$A$を推定するための新しいミニマックスローバウンドを導出し、そのリカバリのための新しい計算効率の良いアルゴリズムを提案する。
我々の推定値は、未知の$A$に適応し、我々の分析は、任意の有限$n$、$p$、$K$および文書長に対して有効である。
- 参考スコア（独自算出の注目度）: 3.308743964406688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Topic models have become popular tools for dimension reduction and
exploratory analysis of text data which consists in observed frequencies of a
vocabulary of $p$ words in $n$ documents, stored in a $p\times n$ matrix. The
main premise is that the mean of this data matrix can be factorized into a
product of two non-negative matrices: a $p\times K$ word-topic matrix $A$ and a
$K\times n$ topic-document matrix $W$. This paper studies the estimation of $A$
that is possibly element-wise sparse, and the number of topics $K$ is unknown.
In this under-explored context, we derive a new minimax lower bound for the
estimation of such $A$ and propose a new computationally efficient algorithm
for its recovery. We derive a finite sample upper bound for our estimator, and
show that it matches the minimax lower bound in many scenarios. Our estimate
adapts to the unknown sparsity of $A$ and our analysis is valid for any finite
$n$, $p$, $K$ and document lengths. Empirical results on both synthetic data
and semi-synthetic data show that our proposed estimator is a strong competitor
of the existing state-of-the-art algorithms for both non-sparse $A$ and sparse
$A$, and has superior performance is many scenarios of interest.
- Abstract（参考訳）: トピックモデルは、$p\times n$Matrixに格納された$n$ドキュメント中の$p$ワードの語彙の観測周波数で構成されるテキストデータの次元減少と探索的分析のための一般的なツールとなっている。
主な前提は、このデータ行列の平均は2つの非負行列の積に分解できる: a $p\times K$ワードトピック行列$A$と a $K\times n$トピックドキュメント行列$W$である。
本稿では、要素的にスパースである可能性のある$A$を推定し、$K$のトピックの数は不明である。
この未探索の文脈では、そのような$A$を推定するための新しいミニマックス下限を導出し、その回復のための新しい計算効率の良いアルゴリズムを提案する。
我々は、推定器の有限標本上界を導出し、多くのシナリオにおいてミニマックス下界と一致することを示す。
我々の推定値は、未知の$A$に適応し、我々の分析は任意の有限$n$、$p$、$K$および文書長に対して有効である。
合成データと半合成データの両方を用いた実験結果から,提案手法は,非スパース$a$とスパース$a$の両方において,既存の最先端アルゴリズムと強力な競合関係にあり,優れた性能が注目されている。
関連論文リスト
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。
サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。
本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
論文 参考訳（メタデータ） (2023-11-08T13:29:08Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - Likelihood estimation of sparse topic distributions in topic models and
its applications to Wasserstein document distance calculations [3.679981089267181]
トピックモデルでは、$ptimes n$予測ワード頻度行列は$ptimes K$ワードトピック行列$A$として分解される。
A$の列は、すべてのドキュメントに共通する$p$の混合コンポーネントと見なされる。
A$が未知の場合、プラグインに対応する可能性関数を最適化して$T$を見積もる。
論文 参考訳（メタデータ） (2021-07-12T22:22:32Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。