変化点検知 - yuuk1's Digital Garden

# 変化点検知 ## 定義変化点検知(change point detection)は、時系列の**統計的性質の変化(シフト)**が起こる時点を特定するタスクである。1950 年代の品質管理に端を発し、信号処理・統計学・機械学習にまたがる研究分野として発展した。異常な「データ点」を特定する[[異常検知]]とは区別され、変化点検知は分布の変化そのものを捉える。オンライン手法(変化をリアルタイムで検知)とオフライン手法(全サンプル収集後に遡及的に検知)に大別される。オフライン手法は**コスト関数**(変化の型に対応)・**探索手法**(最適化の解法)・**制約**(変化点数の制約)の 3 要素の組み合わせで統一的に表現される。(Source: [[@2020__Signal Processing__Selective review of offline change point detection methods]], [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]]) ## 横断的知見 - **Truong+ のサーベイが整理した 3 軸分類（コスト関数・探索手法・制約）は AIOps 応用の手法選択の基盤を提供する**: [[@2020__Signal Processing__Selective review of offline change point detection methods]] はパラメトリック 7 種・ノンパラメトリック 6 種、計 13 種のコスト関数と 5 種の探索手法を直交的に分類する。一方、AIOps 実システムでの変化点検知は mean shift model（$c_{L_2}$）+ Pelt の一択に収束している実態がある——[[MetricSifter]] は $c_{L_2}$ + 線形ペナルティを用い、[[Minder]] もメトリクスの統計的変化を検出する段で同種の検定を使う。サーベイが示す「カーネル法（$c_\text{kernel}$）は分布変化を非パラメトリックに検出でき汎用性が高いがカーネルグラム行列の計算が $O(T^2)$ でボトルネック」「順位統計（$c_\text{rank}$）は単調変換に不変で分布仮定が不要」といった他コストの利点・欠点は、AIOps のメトリクス時系列（分布が事前に未知・外れ値が多い）でどこまで有利に働くかがまだ検証されていない。(Source: [[@2020__Signal Processing__Selective review of offline change point detection methods]], [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]]) - **「持続する変化」を「短命なノイズ」から弁別する発想が、変化点検知と Minder の continuity で独立に現れる**: [[MetricSifter]] の変化点検知は障害起因の統計的性質シフトの時点を捉え、バースト的なジッタとは区別する。[[@2025__NSDI__Minder - Faulty Machine Detection for Large-scale Distributed Model Training]] の **machine-level continuity**(§3.2)は、障害由来の異常は数分持続するがジッタは短命という性質を使い、連続するタイムウィンドウで同一マシンが異常を示し続けたときのみ真に障害があると判定する(continuity threshold = 4 分、障害持続時間の実測図4 に基づく)。両者とも「一過性の揺らぎ」と「持続する逸脱」を時間軸で切り分ける点で同じ発想だが、MetricSifter は変化"点"(いつ変わったか)を、Minder は変化の"持続"(何分続いたか)を主に見る——変化点の検出と変化の継続性チェックという裏表の関係。(Source: [[@2025__NSDI__Minder - Faulty Machine Detection for Large-scale Distributed Model Training]], [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]]) - **変化点検知の応用先が「障害窓の局所化」から「訓練ステップ境界の検出」へ広がる**: [[@2025__DSN__LLMPrism - Black-box Performance Diagnosis for Production LLM Training Platforms]] はフロー間隔の時系列に BOCD(Bayesian Online Changepoint Detection, 閾値 0.95)を適用してステップ境界を検出する(教師なし・線形時間・オンライン常駐に適合)。[[MetricSifter]] が変化点検知を障害窓の局所化に使うのに対し、LLMPrism は周期的なステップ構造の境界抽出に使う——同じ変化点検知でも「異常の時点」を捉えるか「正常な周期構造」を捉えるかで応用が分かれる。(Source: [[@2025__DSN__LLMPrism - Black-box Performance Diagnosis for Production LLM Training Platforms]], [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]]) - **多変量 BOCPD はサービス間の障害伝播チェーンをメトリクス相関変化として捉えることで単変量手法より高い異常検知 F1 を達成する**: [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]] は Adams & MacKay 2007 の BOCPD に Xuan & Murphy 2007 の MultivariateCPD(逆ウィシャート事前分布付き多変量正規モデル)を組み合わせた Multivariate BOCPD を提案する。Online Boutique/Sock Shop/Train Ticket 3 ベンチマークで F1 0.75〜0.82 と単変量 BOCPD(UniBCP: 0.66〜0.67)・N-Sigma(0.67〜0.72)・SPOT(0.67〜0.69)を上回った。マイクロサービスの障害はサービス間を伝播して複数系列に相関変化を起こすため、多変量モデリングが適合する。また推定された最初の変化点 $\hat{t}_A$ が障害注入時刻 $t_{\text{inject}}$ に近似する性質を活用して RCA モジュールの入力として渡す。(Source: [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]], §3.3, Table 2) ## 未解決の問い - AIOps 実システムが $c_{L_2}$ + Pelt に収束している現状に対して、カーネル法（$c_\text{kernel}$）や順位統計（$c_\text{rank}$）は実運用の変化点検知で精度・ロバスト性・計算量のトレードオフを改善できるか。Truong+ のサーベイ（[[@2020__Signal Processing__Selective review of offline change point detection methods]]）はこれらのコスト関数の理論的性質を示すが、AIOps メトリクスでの実験的比較は未踏。 - 変化点検知は正常タイムウィンドウの事前指定を不要にする点で異常検知ベースの normality reduction より優れる([[MetricSifter]] §III-A)が、変化度合いの小さい root fault metrics(満杯近いリソース等)を取りこぼす。微小変化に頑健な変化点検知は可能か。 - [[時系列基盤モデル]](TSFM)はゼロショットで予測・異常検知を行うが、変化点検知タスクに TSFM を使うと、Pelt のような古典手法より障害起因の変化点を正確に捉えられるか。 - ペナルティ重み $\omega$ は異常の型に敏感([[MetricSifter]] Fig. 9)。障害の型に依らず安定して変化点を検知するペナルティ設計はあるか。 - [[Minder]] の continuity threshold(4 分)は障害持続時間の経験分布から固定値で決め打つ。障害種別ごとに持続時間が異なる(高速伝播の障害は短い)ため、適応的な持続性判定や変化点検知との併用で取りこぼし(GPU exec error・PCIe downgrading の低い再現率)を減らせるか。 - BOCD の変化点尤度閾値は窓長やジョブ規模に依存して調整が要るか。([[@2025__DSN__LLMPrism - Black-box Performance Diagnosis for Production LLM Training Platforms]]) - 多変量 BOCPD の計算量は次元数(サービス数 × メトリクス数)の二乗程度になる。高次元マイクロサービスシステムへのスケーラビリティをどう確保するか。BARO の最大実行時間が Train Ticket(64 サービス・212 メトリクス)で 7 分かかる事実は、本番リアルタイム適用での計算コストを示唆する。(Source: [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]], §4.9) ## 関連 - ソース: [[@2020__Signal Processing__Selective review of offline change point detection methods]] / [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]] / [[@2025__NSDI__Minder - Faulty Machine Detection for Large-scale Distributed Model Training]] / [[@2025__DSN__LLMPrism - Black-box Performance Diagnosis for Production LLM Training Platforms]] / [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]] - 概念: [[特徴量削減]] / [[Fault Localization]] / [[時系列基盤モデル]] / [[多変量時系列予測]] / [[異常検知]] - エンティティ: [[MetricSifter]] / [[Minder]] / [[ruptures]] - 関連 MOC: [[異常検知 - MOC]] / [[時系列基盤モデル - MOC]] ## 出典 - [[@2020__Signal Processing__Selective review of offline change point detection methods]]（§2 問題定式化、§4 コスト関数の分類、§5 探索手法、§6 変化点数推定、Table 1-2） - [[@2024__IEEE Access__MetricSifter - Feature Reduction of Multivariate Time Series Data for Efficient Fault Localization in Cloud Applications]](§III-A, §III-C, Algorithm 1) - [[@2025__NSDI__Minder - Faulty Machine Detection for Large-scale Distributed Model Training]](§3.2 Machine-level Continuity, §6.4 Analysis of Continuity) - [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]](§3.3 Multivariate BOCPD、Table 2 異常検知結果比較、§4.9 実行時間)