libhmm: A Modern C++20 Library for Hidden Markov Models with Correct MLE Emission M-Steps

技術概要：libhmm – 隠れマルコフモデルのためのモダンな C++20 ライブラリ

問題定義
本論文は、既存の隠れマルコフモデル（HMM）ソフトウェアの状況において、以下の 2 つの主要なギャップを特定しています：

1. 埋め込み可能な C++ インフラの欠如：主要な HMM ツール（例：moveHMM、fHMM、hmmlearn）は R または Python ランタイムに依存しており、大幅なオーバーヘッドなしに本番環境の C++ システムに埋め込むには不適切です。既存の C/C++ ライブラリ（例：GHMM、HMMLib）は、いずれも放棄されているか、モダンな C++ の慣習を欠いているか、離散放出に限定されています。
2. 誤った放出 M ステップ：多くの既存パッケージは、閉形式の最尤推定量（MLE）が利用できない場合、バウム・ウェルチアルゴリズムにおける放出分布の M ステップにモーメント法（MOM）近似を利用しています。著者らは、これが統計的な正確性を犠牲にする計算上の便宜であると主張しており、特に MOM が正確な MLE とは異なる固定点に収束する可能性があるガンマ分布、ベータ分布、ワイブル分布、負の二項分布、および学生 t 分布において、その問題が顕著であると指摘しています。

手法
本論文では、パラメータ推定、系列復号、モデル選択を目的とした、ゼロ依存性の C++20 ライブラリである libhmm について記述しています。

• 推論アルゴリズム：本ライブラリは、完全なログ空間のフォワード・バックワードアルゴリズムとビタビアルゴリズムを実装しています。明示的な正規化定数（アンダーフローを引き起こし得る）を必要とするスケーリングアルゴリズムとは異なり、libhmm は数値的に安定した log-sum-exp 操作を全体を通じて使用し、任意の長さの系列に対して無条件の安定性を保証します。
• 放出分布：本ライブラリは、16 種類の連続および離散放出分布をサポートしています。
  • 閉形式の MLE：ガウス分布、対数正規分布、指数分布、ポアソン分布、レイリー分布、一様分布、離散分布、およびフォン・ミーゼス分布（平均方向）に対して実装されています。
  • ニュートン・ラプソン法による MLE：ガンマ分布、ベータ分布、ワイブル分布、負の二項分布、およびフォン・ミーゼス分布（集中度パラメータ）に対して実装されています。これらは MOM 推定値を初期値として使用し、通常 2〜4 回の反復で収束します。
  • ECME アルゴリズム：位置・スケール型学生 t 分布については、本ライブラリは期待値/条件付き最大化のいずれか（ECME）アルゴリズム（Liu and Rubin, 1994）を実装しています。これは、ほぼガウス型の尾部において MOM による尖度推定が真の MLE に収束しないという既知の問題に対処するものです。
• アーキテクチャ：
  • ゼロ依存性：本ライブラリは C++20 標準ライブラリのみでコンパイルされ、Eigen や GSL などの外部依存関係を回避します。
  • 多態性 vs テンプレート：設計では、単一のモデル内で分布タイプを混合可能にし、シリアライズや Python バインディングを簡素化するため、放出分布に対してランタイム多態性（仮想メソッド）を使用しています。これにより、わずかな仮想呼び出しオーバーヘッドを受け入れています。
  • SIMD アクセラレーション：コンパイル時ディスパッチにより、フォワード・バックワードの内部ループに対して AVX-512、AVX2、SSE2、および ARM NEON をサポートし、スカラーフォールバックを備えています。
  • 階層化設計：コードは 8 つのレイヤーに整理され、保守性と監査可能な依存関係グラフを確保するために、厳密に一方向の依存フローが維持されています。

主な貢献

1. 正確な MLE M ステップ：16 種類の分布に対する正確な最尤推定量の導出と実装。特に、ニュートン・ラプソン法および ECME 法を用いて MOM 近似を置き換えること。
2. ログ空間の安定性：再スケーリングの管理の複雑さなしに数値的アンダーフローを防ぐための、ログ空間における完全なフォワード・バックワードおよびビタビ復号の実装。
3. モダンな C++20 実装：モダンなビルドシステム（CMake）および慣習をサポートし、放棄されたレガシーな C/C++ ライブラリが残した空白を埋める、ゼロ依存性で埋め込み可能なライブラリ。
4. Python バインディング：C++ API を nanobind を介してラップし、Python ユーザーに正確な M ステップ機能を提供するコンパニオンパッケージ pylibhmm。

結果とベンチマーク
本論文は、libhmm を 5 つの実データベンチマークおよび合成データにおいて、確立された R 参照パッケージおよび他の C/C++ ライブラリと比較しています：

• スループット（合成データ）：離散モデルにおいて、libhmm は生のフォワード・バックワードスループットにおいて HMMLib（約 2.8 倍遅い）および GHMM（約 4.9 倍遅い）よりも低速です。著者らは、これを libhmm がスケーリング方式ではなくログ空間を使用し、ランタイム多態性を用いていることに起因すると説明しています。ただし、著者らは、放出評価が計算を支配する連続分布においては、この差が著しく縮小すると指摘しています。
• 統計的精度（実データ）：
  • DAX 金融レジーム：DAX 収益に対する 3 状態学生 t HMM において、ECME 実装は対数尤度 17,487.2 を達成し、fHMM 参照（17,485.7）および以前の MOM ベースの実装（17,334.9）をそれぞれ 152 ナット上回りました。これは、ECME が MOM と比較して優れた解を見つけることを確認するものです。
  • エルクの移動：GPS 軌跡に適合させたパラメータは、moveHMM 参照値と 2% 未満の差で一致しました。
  • 風向：フォン・ミーゼス HMM は、円形データ境界（0°/360°）を正しく処理しましたが、HiddenMarkov によって使用された正規近似は、境界付近の観測値に対して 100% の誤分類を引き起こしました。
• パフォーマンス（実データ）：コンパイル済み C++ 実行およびインタプリタオーバーヘッドの欠如により、libhmm は R パッケージに対して大幅な高速化を示しました（例：エルク移動データで 23 倍高速、DAX レジームで 5〜12 倍高速）。

意義と主張
本論文は、libhmm を HMM エコシステムにおける独自のツールとして位置づけています。これは、広範な分布サポート（16 種類）、統計的に正確な M ステップ実装（ECME/ニュートン・ラプソン）、およびモダンでゼロ依存性のビルド慣習を組み合わせる唯一の C++ ライブラリです。

著者らは、アーキテクチャ上のトレードオフを明確に認めています。すなわち、GHMM/HMMLib が得意とする離散モデルにおける生スループットを犠牲にして、API の使いやすさ、分布の幅、および数値的正確性を獲得しているという点です。主な意義は、特に標準的な MOM 近似が統計的に最適ではない連続放出分布において、研究者やエンジニアが HMM を本番環境の C++ パイプラインに統合するための「正確な」かつ「埋め込み可能な」代替案を提供することにあります。本ライブラリは MIT ライセンスでリリースされ、pylibhmm を通じて Python バインディングが利用可能です。