論文の概要: On the Computational Complexity of Hidden Markov Model Identification

• arxiv url: http://arxiv.org/abs/2610.09104v1
• Date: Tue, 06 Oct 2026 20:54:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.602364
• Title: On the Computational Complexity of Hidden Markov Model Identification
• Title（参考訳）: 隠れマルコフモデル同定の計算複雑性について
• Abstract要約: 同定は、サンプルデータから未知の地下構造モデルのパラメータを復元するタスクである。 文献における識別可能性の様々な概念から生じる決定問題について考察する。 これらの問題はすべてPSPACEで決定可能であることを示す。
• 参考スコア（独自算出の注目度）: 14.348940121215497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data. When parameters other than the ground truth induce the same output distribution, data alone does not provide enough information to recover the ground truth, and the model is thus called unidentifiable. We study the identifiability problem for hidden Markov models (HMMs): given an HMM, is it identifiable? Existing work on HMM identification establishes conditions under which the ground-truth HMM can be identified. However, most of these conditions are sufficient but not necessary, meaning that, when a model does not satisfy them, its identifiability remains inconclusive. We instead take a computational perspective: is there a sound and complete algorithm that decides whether a given HMM is identifiable, and if so, what is the complexity of this decision problem? We consider the decision problems arising from the various notions of identifiability in the literature, including deterministic, generic, global, local, state-permutation- invariant, and finite-alphabet identifiability. We show that all of these problems are decidable in PSPACE, via reductions to the theory of the reals at various levels of its quantifier-alternation hierarchy. We further show that the deterministic variants are already coETR-hard (and hence coNP-hard) for simply parameterized families.
• Abstract（参考訳）: 同定は、サンプルデータから未知の地下構造モデルのパラメータを復元するタスクである。 基底真理以外のパラメータが同じ出力分布を誘導する場合、データだけでは基底真理を回復するのに十分な情報が得られず、したがってモデルは不特定性と呼ばれる。 隠れマルコフモデル(HMM)の識別可能性問題について検討する。 HMM識別に関する既存の研究は、基底構造HMMを識別できる条件を確立する。 しかし、これらの条件の多くは十分であるが必要ではないため、モデルがそれらを満たすことができなければ、その識別性は決定的ではない。 与えられたHMMが特定可能であるかどうかを判断する健全で完全なアルゴリズムが存在し、もしそうであれば、この決定問題の複雑さは何か? 本稿では, 決定論的, ジェネリック, グローバル, 局所, 状態置換不変, 有限アルファベット識別可能性など, 文学における識別可能性の様々な概念から生じる決定問題を考察する。 これらの問題はすべて、PSPACEにおいて、その量化子置換階層の様々なレベルにおける実数理論への還元を通じて決定可能であることを示す。 さらに、決定論的変種は、単純にパラメータ化された族に対して既に coETR-hard であり、したがって coNP-hard であることを示す。

関連論文リスト

• Computational Identifiability [58.12019389497595]
  「自己同一性」は性質、無限のデータ、その他の数学的に理想化された条件を仮定する。 「計算的識別可能性」とは、経験的推定器に対する有限計算探索手順を定義することである。 このフレームワークは、どのようにしてきめ細かな、実用的な識別問題に答えられるかを示します。
  論文  参考訳（メタデータ） (2026-06-08T19:39:59Z)
• On the Complexity of Identification in Linear Structural Causal Models [3.44747819522562]
  空間内で動作するジェネリック識別のための,新しい音響および完全アルゴリズムを提案する。 また,同定が一般に困難であることを示す。
  論文  参考訳（メタデータ） (2024-07-17T13:11:26Z)
• Score-based Causal Representation Learning: Linear and General Transformations [31.786444957887472]
  本稿は、識別可能性と達成可能性の両方に対処する。 スコアに基づくアルゴリズムのクラスを設計し、識別性と達成性の両方を保証する。 結果は、構造化された合成データと画像データに関する実験によって検証される。
  論文  参考訳（メタデータ） (2024-02-01T18:40:03Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Learning Hidden Markov Models When the Locations of Missing Observations are Unknown [54.40592050737724]
  本研究では、未知の観測位置を持つデータからHMMを学習する際の一般的な問題について考察する。 我々は、下層の鎖の構造に関する仮定を一切必要としない再構成アルゴリズムを提供する。 適切な仕様の下では、プロセスのダイナミクスを再構築でき、また、見当たらない観測位置が分かっていたとしても、その有効性を示す。
  論文  参考訳（メタデータ） (2022-03-12T22:40:43Z)
• Fundamental limits for learning hidden Markov model parameters [2.66418345185993]
  学習可能なマルコフモデル(HMM)と学習不可能な隠れマルコフモデル(HMM)のフロンティアについて検討する。 HMMは、未知の集団から来る依存データをクラスタリングするための柔軟なツールである。
  論文  参考訳（メタデータ） (2021-06-24T12:02:33Z)

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

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