論文の概要: Learning Hidden Markov Models Using Conditional Samples
- arxiv url: http://arxiv.org/abs/2302.14753v2
- Date: Sat, 24 Feb 2024 17:17:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 19:50:14.451602
- Title: Learning Hidden Markov Models Using Conditional Samples
- Title(参考訳): 条件付きサンプルを用いた隠れマルコフモデル学習
- Authors: Sham M. Kakade, Akshay Krishnamurthy, Gaurav Mahajan, Cyril Zhang
- Abstract要約: 本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
- 参考スコア(独自算出の注目度): 72.20944611510198
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper is concerned with the computational complexity of learning the
Hidden Markov Model (HMM). Although HMMs are some of the most widely used tools
in sequential and time series modeling, they are cryptographically hard to
learn in the standard setting where one has access to i.i.d. samples of
observation sequences. In this paper, we depart from this setup and consider an
interactive access model, in which the algorithm can query for samples from the
conditional distributions of the HMMs. We show that interactive access to the
HMM enables computationally efficient learning algorithms, thereby bypassing
cryptographic hardness. Specifically, we obtain efficient algorithms for
learning HMMs in two settings:
(a) An easier setting where we have query access to the exact conditional
probabilities. Here our algorithm runs in polynomial time and makes
polynomially many queries to approximate any HMM in total variation distance.
(b) A harder setting where we can only obtain samples from the conditional
distributions. Here the performance of the algorithm depends on a new
parameter, called the fidelity of the HMM. We show that this captures
cryptographically hard instances and previously known positive results.
We also show that these results extend to a broader class of distributions
with latent low rank structure. Our algorithms can be viewed as generalizations
and robustifications of Angluin's $L^*$ algorithm for learning deterministic
finite automata from membership queries.
- Abstract(参考訳): 本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
HMMは、シーケンシャルおよび時系列モデリングにおいて最も広く使われているツールであるが、観察シーケンスのサンプルであるi.d.にアクセス可能な標準設定では、暗号的に学習が難しい。
本稿では,この設定から脱却し,HMMの条件分布からサンプルを検索できる対話型アクセスモデルを提案する。
HMMの対話的アクセスにより、計算効率のよい学習アルゴリズムが実現され、暗号化の難しさを回避できることを示す。
具体的には、HMMを2つの設定で学習するための効率的なアルゴリズムを得る。
(a)厳密な条件付き確率へのクエリアクセスが容易な設定。
このアルゴリズムは多項式時間で動作し、任意のHMMを全変動距離で近似するために多項式的に多くのクエリを生成する。
(b)条件分布からのみサンプルを得ることのできる、より難しい設定。
ここで、アルゴリズムの性能は、HMMの忠実度と呼ばれる新しいパラメータに依存する。
これは暗号処理の難しいインスタンスと、以前知られていたポジティブな結果をキャプチャする。
また,これらの結果は潜在低位構造を持つ分布のより広いクラスに拡張できることを示した。
我々のアルゴリズムは、会員クエリから決定論的有限オートマトンを学習するためのAngluinの$L^*$アルゴリズムの一般化とロバスト化と見なすことができる。
関連論文リスト
- LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
大規模言語モデル(LLM)におけるインテリジェンス(インテリジェンス)の出現は、オートマチックラーニングへの統合に関する調査にインスピレーションを与えている。
本稿では,pMAT (probabilistic Minimally Adequate Teacher) の定式化について紹介する。
我々は,解答精度を向上し,学習したオートマタの正確性を確保する技術を開発した。
論文 参考訳(メタデータ) (2024-08-06T07:12:09Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Cramer Type Distances for Learning Gaussian Mixture Models by Gradient
Descent [0.0]
今日まで、ガウス混合モデルに適合または学習できる既知のアルゴリズムはほとんどない。
一般多変量GMM学習のためのスライスクラマー2距離関数を提案する。
これらの機能は、分散強化学習とディープQネットワークに特に有用である。
論文 参考訳(メタデータ) (2023-07-13T13:43:02Z) - Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For
Hidden Markov Models [70.26374282390401]
ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。
本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
論文 参考訳(メタデータ) (2023-05-29T19:37:48Z) - Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。
私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。
ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
論文 参考訳(メタデータ) (2023-02-10T18:50:37Z) - The Automatic Quasi-clique Merger algorithm (AQCM) [0.0]
Automatic Quasi-Clique Mergerアルゴリズムは、QCMという名前で発表された初期の研究から適応された新しいアルゴリズムです。
本稿では,準斜晶凝集アプローチの一般的な考え方を示し,aqcmアルゴリズムの数学的ステップの詳細を述べるとともに,新しい手法の背景にある動機について述べる。
論文 参考訳(メタデータ) (2021-03-06T20:01:59Z) - A New Algorithm for Hidden Markov Models Learning Problem [0.0]
本研究は隠れマルコフモデル(HMM)の学習アルゴリズムとアプローチに焦点を当てる。
HMMは、モデル化されているシステムがマルコフ過程であると仮定される統計マルコフモデルである。
HMMの本質的な特徴の1つは、学習能力です。
論文 参考訳(メタデータ) (2021-02-14T09:33:00Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳(メタデータ) (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。