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

• arxiv url: http://arxiv.org/abs/2305.18578v2
• Date: Sat, 04 Oct 2025 08:13:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:58.032606
• Title: Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models
• Title（参考訳）: クイック適応3次セグメンテーション:隠れマルコフモデルのための効率的な復号法
• Authors: Alexandre Mösching, Housen Li, Axel Munk,
• Abstract要約: ノイズ観測から元の信号を復号することは、ほぼすべてのHMMデータ解析における主要な目標の1つである。 QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATSについて述べる。 QATSの実装はGitHubのRパッケージQATSにある。
• 参考スコア（独自算出の注目度）: 41.99844472131922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hidden Markov models (HMMs) are characterized by an unobservable Markov chain and an observable process -- a noisy version of the hidden chain. Decoding the original signal from the noisy observations is one of the main goals in nearly all HMM based data analyses. Existing decoding algorithms such as Viterbi and the pointwise maximum a posteriori (PMAP) 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 hidden chain. We present Quick Adaptive Ternary Segmentation (QATS), a divide-and-conquer procedure with computational complexity polylogarithmic 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. It 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, and is meanwhile admissible. The maximization is performed only approximately using an adaptive search procedure. Our simulations demonstrate the speedups offered by QATS in comparison to Viterbi and PMAP, along with a precision analysis. An implementation of QATS is in the R-package QATS on GitHub.
• Abstract（参考訳）: 隠れマルコフモデル(HMM)は、観測不能マルコフ連鎖と、隠された連鎖のノイズバージョンである観測可能なプロセスによって特徴づけられる。 ノイズ観測から元の信号を復号することは、ほぼすべてのHMMデータ解析における主要な目標の1つである。 ViterbiやPMAPアルゴリズムのような既存の復号アルゴリズムは、観測シーケンスの長さにおいて最も線形に計算複雑性を持ち、隠れ鎖の状態空間の大きさではサブクアドラティックである。 QATS(Quick Adaptive Ternary Segmentation)は,数列長の計算複雑性が多対数的であり,状態空間の大きさが立方体であることから,比較的少ない大規模HMMに特に適している。 また、特定の累積和としてデータストレージの効果的な方法を提案する。 本質的に、推定された状態列は、少なくとも3つのセグメントを持つ全ての局所経路の局所的確率スコアを逐次最大化し、一方で許容できる。 この最大化は、適応探索手順のみを用いて行われる。 シミュレーションでは, ビタビやPMAPと比較してQATSが提供したスピードアップと精度解析を行った。 QATSの実装はGitHubのRパッケージQATSにある。

関連論文リスト

• Gradient-descent methods for fast quantum state tomography [0.24999074238880484]
  量子状態トモグラフィー(QST)の処理後ステップのためのグラデーション・ディフレクション(GD)アルゴリズムを導入する。 我々は、コレスキー分解、スティーフェル多様体、射影正規化など、様々な密度行列パラメタライゼーションを使用する。 我々のミニバッチGD-QSTアルゴリズムのランク制御されたアンサーゼは、ノイズやデータセットを効果的に処理する。
  論文  参考訳（メタデータ） (2025-03-06T15:13:45Z)
• 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)

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

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