論文の概要: How good is Good-Turing for Markov samples?
- arxiv url: http://arxiv.org/abs/2102.01938v3
- Date: Sat, 27 May 2023 16:05:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 04:57:59.620400
- Title: How good is Good-Turing for Markov samples?
- Title（参考訳）: Markovのサンプルはどの程度良いか?
- Authors: Prafulla Chandra, Andrew Thangaraj and Nived Rajaraman
- Abstract要約: GT の収束は$(Psim x)n$ の収束に依存することを示す。
数値的には$lambdasim x$ と $pi_x$ の関係を$x$ で均一に示す。
- 参考スコア（独自算出の注目度）: 5.046831208137847
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Good-Turing (GT) estimator for the missing mass (i.e., total probability
of missing symbols) in $n$ samples is the number of symbols that appeared
exactly once divided by $n$. For i.i.d. samples, the bias and squared-error
risk of the GT estimator can be shown to fall as $1/n$ by bounding the expected
error uniformly over all symbols. In this work, we study convergence of the GT
estimator for missing stationary mass (i.e., total stationary probability of
missing symbols) of Markov samples on an alphabet $\mathcal{X}$ with stationary
distribution $[\pi_x:x \in \mathcal{X}]$ and transition probability matrix
(t.p.m.) $P$. This is an important and interesting problem because GT is widely
used in applications with temporal dependencies such as language models
assigning probabilities to word sequences, which are modelled as Markov. We
show that convergence of GT depends on convergence of $(P^{\sim x})^n$, where
$P^{\sim x}$ is $P$ with the $x$-th column zeroed out. This, in turn, depends
on the Perron eigenvalue $\lambda^{\sim x}$ of $P^{\sim x}$ and its
relationship with $\pi_x$ uniformly over $x$. For randomly generated t.p.ms and
t.p.ms derived from New York Times and Charles Dickens corpora, we numerically
exhibit such uniform-over-$x$ relationships between $\lambda^{\sim x}$ and
$\pi_x$. This supports the observed success of GT in language models and
practical text data scenarios. For Markov chains with rank-2, diagonalizable
t.p.ms having spectral gap $\beta$, we show minimax rate upper and lower bounds
of $1/(n\beta^5)$ and $1/(n\beta)$, respectively, for the estimation of
stationary missing mass. This theoretical result extends the $1/n$ minimax rate
for i.i.d. or rank-1 t.p.ms to rank-2 Markov, and is a first such minimax rate
result for missing mass of Markov samples.
- Abstract（参考訳）: GT(Good-Turing, Good-Turing, GT)推定器は、不足質量(すなわち、不足シンボルの総確率)を$n$サンプルで推定し、ちょうど$n$で分割されたシンボルの数である。
I.d.サンプルの場合、GT推定器のバイアスと二乗誤差リスクは、すべてのシンボルに対して期待される誤差を均一にバウンドすることで1/n$に低下する。
本研究では,定常分布 $[\pi_x:x \in \mathcal{x}]$ および遷移確率行列 (t.p.m.) $p$ を持つアルファベット $\mathcal{x}$ 上のマルコフサンプルの欠落定常質量 (すなわち欠落記号の完全定常確率) に対する gt 推定器の収束について検討する。
GTはマルコフとしてモデル化された単語列に確率を割り当てる言語モデルのような時間依存性を持つアプリケーションで広く使われているため、これは重要かつ興味深い問題である。
gt の収束は $(p^{\sim x})^n$ の収束に依存しており、ここで $p^{\sim x}$ は $p$ であり、$x$-th の列は 0 である。
これは、ペロン固有値 $\lambda^{\sim x}$ of $P^{\sim x}$ と $\pi_x$ との関係に一様に依存する。
New York Times と Charles Dickens corpora から得られたランダムに生成された t.p.ms と t.p.ms に対して、$\lambda^{\sim x}$ と $\pi_x$ の関係を数値的に表す。
これは言語モデルと実践的なテキストデータシナリオにおけるGTの成功をサポートする。
rank-2 のマルコフ鎖では、スペクトルギャップ $\beta$ を持つ対角化可能な t.p.ms は、静止質量の推定のためにそれぞれ 1/(n\beta^5)$ と 1/(n\beta)$ である。
この理論的結果は、i.d. または rank-1 t.p.ms の1/n$ ミニマックスレートをランク2 マルコフに拡張し、マルコフサンプルの欠落に対する最初のミニマックスレート結果である。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。
一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。
隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
論文 参考訳（メタデータ） (2024-09-02T06:14:05Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models:
Sharp Minimax Rates [1.0309387309011746]
スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。
ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。
以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
論文 参考訳（メタデータ） (2022-11-15T23:53:39Z) - Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture
Models [12.746888269949407]
2進隠れマルコフモデルに対する高次元平均推定問題を考える。
ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
論文 参考訳（メタデータ） (2022-06-06T09:34:04Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - 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) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。