論文の概要: Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models

• arxiv url: http://arxiv.org/abs/2305.18578v1
• Date: Mon, 29 May 2023 19:37:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 19:36:55.378938
• Title: Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models
• Title（参考訳）: クイック適応三分法:隠れマルコフモデルの効率的な復号法
• Authors: Alexandre M\"osching, Housen Li, Axel Munk
• Abstract要約: ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。 本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
• 参考スコア（独自算出の注目度）: 70.26374282390401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hidden Markov models (HMMs) are characterized by an unobservable (hidden) Markov chain and an observable process, which is a noisy version of the hidden chain. Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses. Existing decoding algorithms such as the Viterbi algorithm have computational complexity at best linear in the length of the observed sequence, and sub-quadratic in the size of the state space of the Markov chain. We present Quick Adaptive Ternary Segmentation (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity in the length of the sequence, and cubic in the size of the state space, hence particularly suited for large scale HMMs with relatively few states. The procedure also suggests an effective way of data storage as specific cumulative sums. In essence, the estimated sequence of states sequentially maximizes local likelihood scores among all local paths with at most three segments. The maximization is performed only approximately using an adaptive search procedure. The resulting sequence is admissible in the sense that all transitions occur with positive probability. To complement formal results justifying our approach, we present Monte-Carlo simulations which demonstrate the speedups provided by QATS in comparison to Viterbi, along with a precision analysis of the returned sequences. An implementation of QATS in C++ is provided in the R-package QATS and is available from GitHub.
• Abstract（参考訳）: 隠れマルコフモデル(HMM)は、隠れマルコフ鎖の観測不能な(隠された)マルコフ連鎖と、隠された鎖のノイズのあるバージョンである観測可能過程によって特徴づけられる。 ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。 既存の復号アルゴリズムであるビタビアルゴリズムは、観測シーケンスの長さにおいて最も線形に計算複雑性を持ち、マルコフ連鎖の状態空間の大きさではサブクアドラティックである。 本稿では,多対数計算の複雑度で隠れた列を列の長さでデコードし,状態空間の大きさを立方体で表し,比較的少ない状態の大規模hmmに対して特に適合する3次分割法であるquick adaptive ternary segmentation (qats)を提案する。 この手順はまた、特定の累積和としてデータストレージの効果的な方法を提案する。 本質的に、推定された状態列は、少なくとも3つのセグメントを持つ全ての局所経路の局所的確率スコアを逐次最大化する。 最大化は適応探索手順を用いてのみ行われる。 結果列は、全ての遷移が正の確率で起こるという意味で許容される。 我々のアプローチを正当化する公式な結果を補完するため、我々は、返却シーケンスの精度解析とともに、QATSによるビタビと比較しての高速化を示すモンテカルロシミュレーションを提案する。 C++でのQATSの実装は、RパッケージのQATSで提供されており、GitHubから入手できる。

関連論文リスト

• Bisimulation Learning [55.859538562698496]
  我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。 提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
  論文  参考訳（メタデータ） (2024-05-24T17:11:27Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Efficiency Ordering of Stochastic Gradient Descent [9.634481296779057]
  我々は、任意のグラフ上のノイズやランダムウォークを含む一般的なサンプリングシーケンスによって駆動される勾配降下(SGD)アルゴリズムについて検討する。 我々は、マルコフ・チェイン・モンテカルロサンプリング器の性能を比較するためのよく分析されたツールである「効率順序付け」の概念を採用している。
  論文  参考訳（メタデータ） (2022-09-15T16:50:55Z)
• MrSQM: Fast Time Series Classification with Symbolic Representations [11.853438514668207]
  MrSQMは複数のシンボル表現と効率的なシーケンスマイニングを使用して重要な時系列特徴を抽出する。 本研究は, 完全教師付きから非教師付き, ハイブリッドまで, 記号列の4つの特徴選択手法について検討する。 UEA/UCRベンチマークの112のデータセットに対する実験では、MrSQMがすぐに有用な特徴を抽出できることが示されている。
  論文  参考訳（メタデータ） (2021-09-02T15:54:46Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  連続可変量子鍵分布(QKD)は、ボソニックモードの二次構造を用いて、2つのリモートパーティ間の秘密鍵を確立する。 構成可能な有限サイズセキュリティの一般的な設定におけるホモダイン検出プロトコルについて検討する。 特に、ハイレート(非バイナリ)の低密度パリティチェックコードを使用する必要のあるハイシグネチャ・ツー・ノイズ・システマを解析する。
  論文  参考訳（メタデータ） (2021-03-30T18:02:55Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• MAP segmentation in Bayesian hidden Markov models: a case study [0.0]
  有限状態および有限発光アルファベット隠蔽マルコフモデル(HMM)の最大後続確率(MAP)状態列を推定する問題を考える。 本論文の主な目的は,HMMのパラメータをトレーニングデータを用いて推定し,ベイズ的な設定を頻繁な設定と比較することである。
  論文  参考訳（メタデータ） (2020-04-17T16:42:18Z)
• Scalable Hybrid HMM with Gaussian Process Emission for Sequential Time-series Data Clustering [13.845932997326571]
  隠れマルコフモデル(HMM)とガウス過程(GP)のエミッションを組み合わせることで、隠れた状態を効率的に推定することができる。 本稿では,HMM-GPSMのためのスケーラブルな学習法を提案する。
  論文  参考訳（メタデータ） (2020-01-07T07:28:21Z)

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

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