## Memo ## Memo with LLM ### 論文情報 - **タイトル**: Bayesian Online Changepoint Detection - **著者と所属**: Ryan Prescott Adams（Cavendish Laboratory, Cambridge CB3 0HE, United Kingdom）、David J.C. MacKay（Cavendish Laboratory, Cambridge CB3 0HE, United Kingdom） - **カンファレンス/ジャーナル名**: arXiv プレプリント（arXiv:0710.3742） - **発表年**: 2007年 ### 論文概要 時系列データの生成パラメータに生じる突発的な変化（チェンジポイント）をオンラインで検出するベイズ的手法を提案する。現在の「ラン長」（直近チェンジポイントからの経過時間）の事後分布を逐次的なメッセージパッシングアルゴリズムで正確に計算する。指数族分布に対して高いモジュール性を持ち、異なるデータ型への適用が容易である。 ### 詳細解説 #### 問題設定 - **入力**: 逐次観測される時系列データ $x_1, x_2, \ldots, x_T$ - **出力**: 各時刻 $t$ における現在のラン長 $r_t$（直近チェンジポイントからの経過ステップ数）の事後分布 $P(r_t \mid x_{1:t})$、および次の観測値の予測分布 $P(x_{t+1} \mid x_{1:t})$ - **前提条件**: 観測列は非重複な積分割（product partition）に分割可能であり、各区間内のデータは同一のパラメータ $\eta^\rho$ からi.i.d.に生成される。また区間ごとのパラメータも互いに独立とする。 - **必要なデータ**: 逐次到着する1次元または多次元の観測データ列 #### 提案手法 ##### アーキテクチャ チェンジポイント検出を「ラン長推定問題」として定式化する。ラン長 $r_t$ の同時分布 $P(r_t, x_{1:t})$ をトレリス上のメッセージパッシングで逐次更新する。アルゴリズムは2つの独立したコンポーネントで構成される： 1. **チェンジポイント事前分布**（ハザード関数 $H(\tau)$）: ラン長がそのまま延びるか（$r_t = r_{t-1}+1$）、リセットされるか（$r_t = 0$）の確率を決定する。 2. **観測モデル**（予測分布）: 指数族分布の充足統計量を更新し、ランごとの予測確率 $\pi_t^{(r)}$ を計算する。 ##### アルゴリズム/手法の詳細 ラン長とデータの同時分布を次の漸化式で計算する： $P(r_t, x_{1:t}) = \sum_{r_{t-1}} P(r_t \mid r_{t-1}) \cdot P(x_t \mid r_{t-1}, x_t^{(r)}) \cdot P(r_{t-1}, x_{1:t-1})$ チェンジポイント事前分布は2つの遷移のみに非ゼロ質量を持つ： $P(r_t \mid r_{t-1}) = \begin{cases} H(r_{t-1}+1) & \text{if } r_t = 0 \\ 1 - H(r_{t-1}+1) & \text{if } r_t = r_{t-1}+1 \end{cases}$ ハザード関数は $H(\tau) = P_{\text{gap}}(g=\tau) / \sum_{t=\tau}^{\infty} P_{\text{gap}}(g=t)$。チェンジポイント間隔が幾何分布に従う場合、$H(\tau) = 1/\lambda$（定数）となりメモリレス性が成立する。 充足統計量の更新（共役指数族の場合）： $\nu_t^{(r+1)} = \nu_t^{(r)} + 1, \quad \chi_t^{(r+1)} = \chi_t^{(r)} + u(x_t)$ 事後分布の裾が閾値（例：$10^{-4}$）以下になったベクトルを打ち切ることで、平均的に $O(\mathbb{E}[r])$ の定数時間・空間計算量を達成する。 ##### 実装上の工夫 - **充足統計量の増分更新**: 各ランの充足統計量を過去から累積して保持するため、予測分布の計算を $O(1)$ で行える。 - **打ち切りによる効率化**: 裾の質量が閾値以下のラン長仮説を廃棄し、メモリと計算量を現実的なサイズに抑える。 - **プラガブルアーキテクチャ**: チェンジポイント検出ロジックと観測モデルを完全に分離し、多変量ガウス・ポアソン・ベルヌーイ・ガンマ等のモデルを差し替え可能にした。 #### 新規性 既存のベイズ的チェンジポイント検出手法（Barry & Hartigan 1993, Chib 1998等）のほとんどは**後退的セグメンテーション**を対象としており、将来の観測なしにオンラインで推論する枠組みを持たなかった。頻度論的手法（CUSUMなど）はオンライン検出を提供するが、確率的な事後分布を与えない。本手法は**オンラインかつ正確な事後推論**を行う初めてのベイズ的枠組みであり、メッセージパッシングによる効率的な実装を実現した。また既存手法が区間数を事前に設定する必要がある（例：隠れマルコフモデル）のに対して、本手法は区間数を自動的に推定する。 #### 実験設定 ##### 実験環境 論文には具体的なハードウェア・ソフトウェアスタックの記述はないが、Pythonによる実装コードを公開している（`http://www.inference.phy.cam.ac.uk/rpa23/cp/`）。 ##### データセット 3つの実世界データセットを使用： 1. **ウェルログデータ**: 掘削中の核磁気応答の4050点の測定値。地殻の地質構造解析に使用される。変化点は地層の層序を反映する。 2. **ダウジョーンズ工業平均 (1972-75)**: 1972年7月3日から1975年6月30日の日次リターン。ウォーターゲート事件やOPEC石油禁輸などの大規模経済イベントを含む。 3. **炭鉱災害データ** (Jarrett 1979): 1851年3月15日から1962年3月22日にかけて10人以上を死傷させた炭鉱爆発事故の発生日。 ##### 比較対象 (Baseline) 比較対象の手法は明示されていない。各データセットの先行研究（Ó Ruanaidh & Fitzgerald 1996, Fearnhead & Clifford 2003, Hsu 1977等）との定性的比較にとどまる。 ##### 評価指標 定量的評価指標は設定されていない。予測平均・予測分散の可視化と、ラン長事後分布のヒートマップによる定性的評価を行う。 #### 実験結果 ##### 定量的評価 定量的な数値比較は論文中に提示されていない。 ##### 定性的評価 - **ウェルログ**: ラン長がゼロにリセットされるタイミングが地層の境界（平均の急変）と良好に一致した。チェンジポイント直後に予測分散が増大する（データ不足による不確実性の増大）という期待通りの挙動を確認。 - **ダウジョーンズ**: ニクソン再選スタッフ有罪判決（1973年1月30日）、OPEC禁輸開始（1973年10月19日）、ニクソン辞任（1974年8月9日）の3イベント付近でラン長の有意なリセットが観測された。 - **炭鉱災害データ**: 1887年の炭鉱規制法（Coal Mines Regulations Act）の施行前後でポアソン率の変化が検出された。 ##### アブレーションスタディ 実施されていない。 #### 考察 (Discussion) ##### 結果の解釈 ラン長事後分布を予測分布の混合重みとして用いることで、直近のチェンジポイント以降のデータのみを予測に利用する仕組みが自然に実現する。チェンジポイント直後に予測不確実性が増大するのは、適切な統計的振る舞いである。 ##### 優位性の根拠 指数族分布に対して充足統計量が有限次元で表現可能なため、モデルの増分更新が理論的に保証される。また離散的なチェンジポイント事前分布（ハザード関数）により、ラン長の遷移が2状態のみに集中し計算が簡潔になる。 ##### 限界と例外 - 時間・空間計算量が最悪の場合 $O(T)$（観測データ数に線形）となり、長期間のストリームでは打ち切り近似が必須。 - チェンジポイント前後でパラメータが独立であるという仮定は、パラメータに持続的なトレンドがある場合には不適切。 - 連続的な変化（急変でなく漸変）には対応していない。 - 観測モデルが指数族である必要があり、より複雑な分布（例：混合分布）には直接適用できない。 #### 強み (Strengths) - オンライン・因果的推論のため、リアルタイムアプリケーションに直接適用可能。 - チェンジポイント数を事前に指定する必要がない。 - アルゴリズムとモデルの完全な分離により、多様なデータ型への適用が容易。 - 指数族に対して正確な（近似なし）事後推論を実現。 - シンプルなメッセージパッシングで実装でき、コードの再利用性が高い。 #### 弱点・課題 (Weaknesses / Limitations) - 最悪計算量 $O(T)$（打ち切りで緩和可能だが保証なし）。 - チェンジポイント前後のパラメータ独立性仮定が強い。 - 多次元データへの拡張は可能だが、高次元での計算効率の問題は論文では扱われていない。 - 評価が定性的な可視化のみであり、定量的ベンチマークが欠如している。 ## Abstract チェンジポイントとは、データ列の生成パラメータに生じる突発的な変動である。チェンジポイントのオンライン検出は、金融・生体計測・ロボティクスなどの応用領域における時系列のモデリングおよび予測に有用である。頻度論的手法がオンラインフィルタリングおよび予測技術を提供してきた一方で、ベイズ的な先行研究の多くは後退的なセグメンテーション問題に焦点を当ててきた。本稿では、チェンジポイントの前後でモデルパラメータが独立である場合を検討し、直近のチェンジポイントに対する正確な推論を行うオンラインアルゴリズムを導出する。現在の「ラン」の長さ、すなわち直近のチェンジポイントからの経過時間の確率分布を、単純なメッセージパッシングアルゴリズムを用いて計算する。実装は高いモジュール性を持つよう設計されており、様々な種類のデータに対してアルゴリズムを適用可能である。このモジュール性を、3つの異なる実世界データセットにアルゴリズムを適用することで示す。