# Bayesian Online Changepoint Detection > [!abstract] 概要 > 変化点とは、データ列の生成パラメータの急激な変化である。変化点のオンライン検知は、金融、生体計測、ロボティクスなどの応用分野における時系列のモデル化と予測に有用である。頻度論的な手法はオンラインのフィルタリングと予測の技法を生んできたが、ベイズ的な研究の大半は事後的な区間分割の問題に集中してきた。本論文では、変化点の前後でモデルパラメータが独立である場合を扱い、直近の変化点を厳密に推論するオンラインアルゴリズムを導く。単純なメッセージ伝播により、現在の「ラン」の長さ、すなわち最後の変化点からの時間の確率分布を計算する。実装は高度にモジュール化されており、さまざまな種類のデータに適用できる。このモジュール性を、3 つの実世界データセットへの適用で示す。 ## 論文情報 - 題名: Bayesian Online Changepoint Detection - 著者: Ryan Prescott Adams, David J.C. MacKay(Cavendish Laboratory, University of Cambridge) - 公開: arXiv:0710.3742 [stat.ML], 2007-10-19。7 ページ。査読会議名は PDF から確認できない。 - 資金: Gates Cambridge Trust ## 概要 変化点検知をオンラインの因果的な予測フィルタリングとして定式化し、現在のラン長 $r_t$(最後の変化点からの経過時間)の事後分布 $P(r_t \mid x_{1:t})$ を厳密かつ再帰的に更新するアルゴリズム(BOCPD)を示した論文である。ラン長の遷移がハザード関数で決まる 2 択(継続または 0 へのリセット)に限られることで、更新が軽いメッセージ伝播に落ちる。3 つの実データで、検知した変化点が既知の出来事や急変とよく対応することを示した。 ## 問題設定 - 観測列 $x_1,\dots,x_T$ を、重ならない積分割(product partition)に分ける。区間の境目が変化点である。各区間内のデータは分布 $P(x_t \mid \eta_\rho)$ から独立同分布に生じ、区間ごとのパラメータ $\eta_\rho$ も互いに独立同分布とする。 - 区間長の事前分布を $P_{gap}(g)$ と置く。 - 目標は、これまでに観測したデータが与えられたときの現在のラン長 $r_t$ の事後分布である。従来のベイズ的な変化点研究の大半は、事後的な区間分割と変化点位置の事後分布からのサンプリングに集中していた。本論文は、過去のデータだけから次の観測の分布を出す因果的な予測を目的にする点で異なる。 - 動機の例はロボットの環境変化(ドアが閉まる、家具が動く)と、視覚系の明るさの急変(照明のスイッチ、日の出)である。 ## 提案手法 ### 再帰的ラン長推定 - ラン長と観測の同時分布を $P(r_t, x_{1:t}) = \sum_{r_{t-1}} P(r_t \mid r_{t-1})\, P(x_t \mid r_{t-1}, x_t^{(r)})\, P(r_{t-1}, x_{1:t-1})$ と再帰的に書く。必要なのは 2 つだけである。(1) $r_{t-1}$ が与えられたときの $r_t$ の事前分布、(2) 直近ラン内のデータ $x_t^{(r)}$ が与えられたときの新規観測の予測分布。 - 事後は $P(r_t \mid x_{1:t}) = P(r_t, x_{1:t}) / P(x_{1:t})$ で得る。次の観測の周辺予測分布は、ラン長ごとの予測を事後で重み付けして周辺化する。 ![[_attachments/arxiv-0710.3742/fig01-run-length-trellis.png]] (Figure 1. 変化点をラン長で表す図。(a) 平均が変化する 3 区間(長さ g1 = 4, g2 = 6, g3 は未定)。(b) ラン長 $r_t$ は変化点で 0 に落ちる。(c) メッセージ伝播が走るトレリス。実線が質量の上への成長、破線が切断による 0 への遷移を表す。) ### 変化点の事前分布とハザード関数 - 条件付き事前分布 $P(r_t \mid r_{t-1})$ は、質量が 2 点にしかない。ラン長が $r_{t-1}+1$ に伸びるか、変化点が生じて 0 になるかである。変化確率はハザード関数 $H(\tau) = P_{gap}(g=\tau) / \sum_{t=\tau} P_{gap}(g=t)$ で与える。 - $P_{gap}$ が時間尺度 $\lambda$ の離散指数(幾何)分布なら過程は無記憶で、ハザード関数は定数 $H(\tau)=1/\lambda$ になる。実験の 3 例はすべてこの指数事前分布を使う。 ### 境界条件 - 観測前に変化点があった場合(例: 試合の観測)は $P(r_0=0)=1$ とする。データの直近部分だけを観測する場合(例: 気候変動のモデル化)は、$P_{gap}$ の生存関数を正規化した分布を初期ラン長の事前分布にする。 ### 共役指数型モデルと計算量 - 尤度が指数型分布族で事前分布が共役なら、ラン長ごとの事後は超パラメータ $\nu$, $\chi$ だけで表せ、$\nu^{(r)} = \nu_{prior} + r$、$\chi^{(r)} = \chi_{prior} + \sum u(x_{t'})$ と増分更新できる。予測分布は十分統計量の単純な関数になる。正確な予測分布が得られない場合は Snelson と Ghahramani の近似などが使えるとするが、本論文は厳密な場合だけを扱う。 - Algorithm 1 は、初期化、予測確率の評価、成長確率の計算、変化点確率の計算、周辺尤度の計算、ラン長分布の正規化、十分統計量の更新、予測、を毎ステップ繰り返す。 - 1 ステップの時間・空間計算量は、これまでの観測数に線形である。事後質量が閾値(例: $10^{-4}$)未満の裾を捨てれば、平均計算量は期待ラン長 $E[r]$ 程度の定数になる。最悪時は線形のままである。 ## 新規性 - ベイズ的な変化点検知を、事後的な区間分割の問題から、因果的で予測的なオンライン推論の問題として捉え直した点。 - 直近の変化点(ラン長)の事後分布を、単純で厳密なメッセージ伝播で得る点。MCMC のサンプリングを要さない。 - 変化点検知の実装とモデルの実装を分離し、確率モデルを差し替えられる(オブジェクト指向の「プラグイン」型)設計にした点。 ## 実験設定 3 つの実データを使う。いずれも区間長の事前分布は離散指数分布である。 - ウェルログ: 井戸の掘削中に得た核磁気応答 4050 点。ガウス分布の平均が区間ごとに変わるとし、事前パラメータは $\mu=1.15\times10^5$, $\sigma=1\times10^4$、$\lambda_{gap}=250$。地殻の層構造による平均の変化に相当する。先行研究として Ó Ruanaidh と Fitzgerald、Fearnhead と Clifford が同データを使った。 - ダウ平均の日次リターン: 1972-07-03 から 1975-06-30。$R_t = p_t^{close}/p_{t-1}^{close} - 1$ を平均 0 のガウス分布・区間ごとに定数の分散でモデル化した。逆分散にガンマ事前分布($a=1$, $b=10^{-4}$)、$\lambda_{gap}=250$。 - 炭鉱事故: 1851-03-15 から 1962-03-22 の、10 人以上が死亡した爆発事故の間隔(Jarrett のデータ)。週単位のポアソン過程とし、レートにガンマ事前分布($a=b=1$)、$\lambda_{gap}=1000$。 ## 実験結果 - ウェルログ: 予測平均・予測標準偏差(1σ)と、ラン長事後の対数スケールの図を示した。ラン長が 0 へ落ちる時点が平均の急変とよく対応する。変化点直後は、データが急に減るため予測分散が増える。 ![[_attachments/arxiv-0710.3742/fig02-well-log.png]] (Figure 2. ウェルログの 1100 点の部分列。上が生データと予測平均・予測標準偏差、下が各時刻のラン長事後確率(対数色尺度)。) - ダウ平均: 予測ボラティリティと事後を示し、3 つの出来事(ウォーターゲート事件の共謀犯 Liddy と McCord の有罪判決(1973-01-30)、OPEC の対米禁輸開始(1973-10-19)、ニクソンの辞任(1974-08-09))の付近でボラティリティの構造変化が見られる。Hsu が週次リターンの部分集合で頻度論的に行った類似の分析がある。 ![[_attachments/arxiv-0710.3742/fig03-dow-jones.png]] (Figure 3. ダウ平均の日次リターンと予測ボラティリティ(上)、ラン長事後(下)。3 つの出来事を注記。時間軸は営業日。) - 炭鉱事故: 事故の累積数の傾きがレートの局所平均を表す。ラン長の事後は、1887 年の炭鉱規制法(図の週 1868〜1920 に相当)の前後を含めてレートの変化を示す。 ![[_attachments/arxiv-0710.3742/fig04-coal-mine.png]] (Figure 4. 炭鉱事故の週次発生(1851〜1962 年)。上が累積事故数、下がラン長事後。1887 年の炭鉱規制法を注記。) - 3 例とも定量的な精度評価(正解ラベルとの比較、他手法との比較、実行時間)は示されていない。 ## 考察 - 予測的でオンラインなベイズ変化点検知の解釈と、現在のラン長の事後確率を求める簡潔で厳密な方法を提示したと著者らは述べる。 - 検知アルゴリズムとモデルの実装が分かれるため、コード上でも差し替え可能な設計にできる。 - 事前分布の $\lambda_{gap}$ は各例で人手により設定されており、その決め方やハザード関数の選択が結果に及ぼす影響の分析は本論文に無い。 ## 強み / 弱点・課題 - 強み: 単純で厳密なオンライン更新である。共役指数型モデルならモジュール化と実装が容易である。事後分布そのものが得られるため、変化の有無だけでなく不確実性も読める。 - 弱点・課題: 区間間のパラメータ独立を仮定する。変化点前後でパラメータに依存関係がある場合や、多変量・時間依存の問題は扱わない。厳密な予測分布が得られない場合は近似が要る。実験は定性的な提示にとどまり、定量評価が無い。 ## 関連 - ソース: [[@1999__KDD__Event Detection for Time Series Data]] / [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]] / [[@2025__ATC__GREYHOUND - Hunting Fail-Slows in Hybrid-Parallel Training at Scale]] - 概念: [[変化点検知]] / [[ベイズ推定]] - エンティティ: [[Ryan Prescott Adams]] / [[David J.C. MacKay]] / [[University of Cambridge]]