論文の概要: Just Wing It: Optimal Estimation of Missing Mass in a Markovian Sequence
- arxiv url: http://arxiv.org/abs/2404.05819v1
- Date: Mon, 8 Apr 2024 18:55:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 18:38:40.074537
- Title: Just Wing It: Optimal Estimation of Missing Mass in a Markovian Sequence
- Title（参考訳）: 正解:マルコフ系列における欠落質量の最適推定
- Authors: Ashwin Pananjady, Vidya Muthukumar, Andrew Thangaraj,
- Abstract要約: emphWindowed Good-Turing (textscWingIt) と呼ばれる線形実行時推定器を開発した。
リスクは$widetildemathcalO(mathsfT_mix/n)$で、$mathsfT_mix$は全変動距離におけるチェーンの混合時間を表す。
我々は推定器を拡張して、Xn$の小さな周波数で発生する要素上の定常質量を近似する。
- 参考スコア（独自算出の注目度）: 13.552044856329648
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of estimating the stationary mass -- also called the unigram mass -- that is missing from a single trajectory of a discrete-time, ergodic Markov chain. This problem has several applications -- for example, estimating the stationary missing mass is critical for accurately smoothing probability estimates in sequence models. While the classical Good--Turing estimator from the 1950s has appealing properties for i.i.d. data, it is known to be biased in the Markov setting, and other heuristic estimators do not come equipped with guarantees. Operating in the general setting in which the size of the state space may be much larger than the length $n$ of the trajectory, we develop a linear-runtime estimator called \emph{Windowed Good--Turing} (\textsc{WingIt}) and show that its risk decays as $\widetilde{\mathcal{O}}(\mathsf{T_{mix}}/n)$, where $\mathsf{T_{mix}}$ denotes the mixing time of the chain in total variation distance. Notably, this rate is independent of the size of the state space and minimax-optimal up to a logarithmic factor in $n / \mathsf{T_{mix}}$. We also present a bound on the variance of the missing mass random variable, which may be of independent interest. We extend our estimator to approximate the stationary mass placed on elements occurring with small frequency in $X^n$. Finally, we demonstrate the efficacy of our estimators both in simulations on canonical chains and on sequences constructed from a popular natural language corpus.
- Abstract（参考訳）: 我々は、離散時間エルゴード型マルコフ連鎖の1つの軌道から欠落している静止質量(ユニグラム質量とも呼ばれる)を推定する問題を研究する。
この問題にはいくつかの応用があり、例えば、定常欠落質量の推定は、シーケンスモデルにおける確率推定を正確に滑らかにするために重要である。1950年代の古典的グッドチューリング推定器は、i.d.データに対して魅力的な性質を持っているが、マルコフ設定では偏りがあることが知られており、他のヒューリスティック推定器には保証が備わっていない。
状態空間のサイズが軌跡の長さ$n$よりもはるかに大きいような一般的な設定で、我々は 'emph{Windowed Good-Turing} (\textsc{WingIt}) と呼ばれる線形実行時推定器を開発し、そのリスクが$\widetilde{\mathcal{O}}(\mathsf{T_{mix}}/n)$として崩壊することを示す。
特に、この速度は状態空間のサイズとは独立であり、対数係数が$n / \mathsf{T_{mix}}$までミニマックス最適化される。
また、欠落したマスランダム変数のばらつきについて、独立な興味を持つかもしれない境界を示す。
我々は、X^n$の小さな周波数で発生する要素上の定常質量を近似するために、推定器を拡張した。
最後に、正規鎖上のシミュレーションと、人気のある自然言語コーパスから構築されたシーケンスにおける推定器の有効性を実証する。
関連論文リスト
- Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
我々は、パラメトリックな$sqrt n $-rateで収束する、最も近い隣人の新しい修正とマッチング推定器を開発する。
我々は,非パラメトリック関数推定器は含まないこと,特に標本サイズ依存パラメータの平滑化には依存していないことを強調する。
論文 参考訳（メタデータ） (2024-07-11T13:28:34Z) - Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
量子レグレッション(Quantile regression)は、出力の分布における量子の実験的推定を通じてそのような間隔を得るための主要なアプローチである。
本稿では、この任意の制約を除去する量子回帰に基づく区間構成の直接的な代替として、Relaxed Quantile Regression (RQR)を提案する。
これにより、柔軟性が向上し、望ましい品質が向上することが実証された。
論文 参考訳（メタデータ） (2024-06-05T13:36:38Z) - Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
本稿では, 推定パラメータが滑らかな多様体内にある推定問題に対して, 新たな性能境界を提案する。
これはパラメータ多様体の幾何学と推定誤差測度の本質的な概念を誘導する。
論文 参考訳（メタデータ） (2023-11-08T15:17:13Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Tangent Space and Dimension Estimation with the Wasserstein Distance [10.118241139691952]
ユークリッド空間の滑らかなコンパクト部分多様体の近くで独立にサンプリングされた点の集合を考える。
我々は、その多様体の次元と接空間の両方を推定するために必要なサンプル点の数について数学的に厳密な境界を与える。
論文 参考訳（メタデータ） (2021-10-12T21:02:06Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Large Non-Stationary Noisy Covariance Matrices: A Cross-Validation
Approach [1.90365714903665]
金融時系列のヘテロシデスティックな性質を利用する新しい共分散推定器を提案する。
断面次元と時系列次元の両方のノイズを減衰させることにより、我々は、競合する推定器に対する推定器の優位性を実証的に実証する。
論文 参考訳（メタデータ） (2020-12-10T15:41:17Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Spectral statistics in constrained many-body quantum chaotic systems [0.0]
本研究では,空間的に拡張された多体量子系のスペクトル統計を,現地のアベリア対称性や局所的制約を用いて研究する。
特に、$mth$ multipole モーメントを保存する長さ $L$ のシステムでは、$t_mathrmTh$ は $L2(m+1)$ として半微分的にスケールする。
論文 参考訳（メタデータ） (2020-09-24T17:59:57Z) - A metric on directed graphs and Markov chains based on hitting
probabilities [0.0]
エルゴード的、有限状態、時間均質なマルコフ連鎖の状態空間に関する計量を導入する。
提案手法は,あるノードから別のノードへのランダムウォーカーの移動に伴う距離空間の近さを仮定して構築した。
特に、私たちのメトリクスは、最も短くて平均的な歩行距離に敏感であり、既存のメトリクスと比較して新しい情報を与えます。
論文 参考訳（メタデータ） (2020-06-25T15:25:05Z) - Empirical and Instance-Dependent Estimation of Markov Chain and Mixing
Time [5.167069404528051]
本稿では,マルコフ連鎖の混合時間を1つの観測軌道から推定する問題に対処する。
ヒルベルト空間法を用いてスペクトルギャップを推定する以前の多くの研究とは異なり、全変動に対する収縮に基づくアプローチを選択する。
この量はスペクトルギャップとは異なり、強い普遍定数まで混合時間を制御し、可逆鎖にも適用できる。
論文 参考訳（メタデータ） (2019-12-14T13:38:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。