変化点検知 - 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) - **SST(Singular Spectrum Transform)ベースの変化点検知は、統計的検定(DiD)との組み合わせによって因果帰属まで踏み込んだ最初期(2015年)の AIOps 応用例である**: [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]](FUNNEL)は Hankel 行列の SVD に基づく SST を「変化スコアを検知する」だけでなく「その変化がソフトウェア変更に起因するか」まで判定する2段構成に拡張した。SST 単体(改良版・DiD なし)は季節性の強い KPI で precision 1.10% まで崩壊する一方、DiD(treated/control 群比較)を組み合わせた FUNNEL は同じ KPI で precision 98.28% を維持する(Table 1)。これは、本 concept が繰り返し確認してきた「変化点検知アルゴリズムそのものより前処理・後段処理が精度を支配する」という設計原則([[MetricSifter]]・[[Minder]] 等の continuity/持続性フィルタと同型)が、統計的因果推論(DiD)という形でも成立することを示す——SST は「いつ変わったか」を高速に検知し、DiD は「なぜ変わったか」を切り分ける、という役割分担。(Source: [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]], Table 1, §3.2.4-3.2.5) - **FUNNEL の IKA(Implicit Krylov Approximation)による行列圧縮は、AIOps 実システムが $c_{L_2}$+Pelt に収束する以前(2015年)に「SVD ベース変化点検知の計算コストをどう削減するか」に対して出された最初期の解答である**: Truong+ サーベイ([[@2020__Signal Processing__Selective review of offline change point detection methods]])が整理するコスト関数群のうち SST は独自の SVD ベース手法だが、FUNNEL は Lanczos 法 + QL 反復による Krylov 部分空間近似で SVD の計算量を削減し、100万 KPI 級を毎分処理してもサーバ1台で足りる水準まで高速化した(MRLS 比 7000 倍以上)。これは、後年の AIOps 実システムが計算コストの軽い $c_{L_2}$+Pelt(コスト関数の単純化)に収束していった動きとは異なる経路——**アルゴリズム自体は複雑な SVD ベースを維持したまま、近似計算で高速化する**——であり、精度と計算コストのトレードオフに対する設計思想の多様性を示す一事例。(Source: [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]], §3.2.3, Table 2) - **セグメントの「大きさ」を変化点の個数でなくメトリクス当たりの逆数和で測る設計は、変化点検知の後段処理が持つ「小規模な偽の集積を過大評価しない」という一般原則の具体形である**: [[@2025__PhD__Scaling Telemetry Workloads in Cloud Applications - Chapter 5 Feature Reduction of Multivariate Time Series Data for Automated Fault Localization]](博士論文第 5 章)の Algorithm 2 は、KDE で得たセグメント集合からサイズ最大のセグメントを選ぶ際、単純な変化点数ではなく $S_{max}=\arg\max_{S_j}\sum_{m\in M(S_j)} 1/N(m)$(メトリクス当たり変化点数の逆数和)でサイズを測る。これは「1 つのメトリクスが障害窓外で大量の変化点を出しても、そのセグメントを過大評価しない」ための重み付けであり、ablation study(Fig. 5.9)は STEP 2/3(セグメンテーション+選択)を除くとペナルティ重み $\omega$ への感度が急増することを示す。本ページが既に指摘した「変化点検知アルゴリズムそのものより前処理・後段処理が精度を支配する」という設計原則(FUNNEL の DiD、Minder の continuity と同型)に、「セグメントサイズの測り方」という新しい後段処理の実例を加える。(Source: [[@2025__PhD__Scaling Telemetry Workloads in Cloud Applications - Chapter 5 Feature Reduction of Multivariate Time Series Data for Automated Fault Localization]], Algorithm 2, Fig. 5.9) - **Chandola 2009 の「構造利用」による文脈異常検知(回帰モデルからの逸脱検知)と本 concept の変化点検知は、隣接するが異なるタスクとして区別できる**: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]](§10.2)が整理する構造利用アプローチは、AR(Fox 1972)・ARMA・ARIMA 等の回帰モデルで文脈から期待挙動を予測し、観測値がモデルの誤差範囲外に落ちたときにその**時点の観測**を異常と判定する。本 concept が扱う「分布パラメータの変化(シフト)そのものを捉える」変化点検知とは異なるタスクであり、Fox 1972 のモデルでは分布パラメータ自体は定常なまま個々の観測を判定する。両者は「モデルから外れた箇所を検知する」という発想を共有するが、変化点検知が捉えるのは分布のシフト(変化点)、Fox 1972 型の回帰残差検知が捉えるのは個々の観測の逸脱(点異常)であり、粒度が異なる。Adams & MacKay 2007 の BOCPD(本 concept が [[BARO]] で扱う)は 2007 年の提案だが、Fox 1972 はその 35 年前から「モデルの共分散行列に対する逸脱」という類似の発想を時系列の文脈異常検知の枠組みで先取りしていた。(Source: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]] §10.2, [[@2024__FSE__BARO - Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection]]) - **Chandola 2009 第7章は、回帰モデルベース統計的異常検知が抱える「訓練データ中の異常が回帰パラメータ自体を歪める」という問題を明示するが、これは第10章の回帰残差検知(Fox 1972 型)の記述には現れない論点である**: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 7 Statistical Anomaly Detection Techniques]](§7.1.2)は、回帰モデルベース異常検知の基本技法(モデル当てはめ→残差を異常スコアとする)を述べたうえで、訓練データ中に異常が存在すると回帰パラメータの推定自体が歪みモデルの精度が損なわれる問題を指摘し、ロバスト回帰[Rousseeuw and Leroy 1987](異常を許容しつつパラメータを推定し、ロバスト当てはめでは異常の残差がむしろ大きくなる性質を検知に利用する)による対処を挙げる。本ページが既に記録する第10章の構造利用アプローチ(AR/ARMA/ARIMAで期待挙動を予測し観測の逸脱を判定する、Fox 1972)は「モデルが正しく学習済みである」ことを暗黙に仮定しており、訓練データ自体が異常で汚染されている場合にモデル当てはめがどう歪むかには触れない。この論点は、本ページが繰り返し確認する「変化点検知アルゴリズムそのものより前処理・後段処理が精度を支配する」という設計原則(FUNNEL の DiD、Minder の continuity、MetricSifter のセグメントサイズ計測)とは異なる層——**モデル当てはめ自体の頑健性**——に位置する。(Source: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 7 Statistical Anomaly Detection Techniques]] §7.1.2, [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]] §10.2) - [Zスコアによる時間帯別平均・分散標準化]**1998年のDECプロキシサーバ計測は、後年のBOCPD・SSTのような専用アルゴリズムに先立ち、時間帯ごとの平均・分散推定だけで正規化するという最小限の統計モデルで実運用障害を検知していた**: [[@1998__PER__Internet Service Performance Failure Detection]]は、i.i.d.性のような強い分布仮定を置かず、定常性と大数の強法則のみを仮定して観測値をZスコア Z_t=(X_t-mean_t)/sigma_t に標準化し、非対称な閾値(Z_i<-2.30 または Z_i>3.00)で逸脱を判定した。本ページが記録するAIOps実システムのc_L2+Peltへの収束や[[MetricSifter]]・[[Minder]]のcontinuityフィルタは前処理・後段処理の洗練を積み重ねてきたが、その原型にあたる「時間帯別の正規分布仮定+Zスコア閾値」という枠組みは1998年時点で既に実データ(12週間のDEC社内プロキシ計測、既知障害との突き合わせ)で検証されていた。(Source: [[@1998__PER__Internet Service Performance Failure Detection]]) - [検知の早さと誤警報のトレードオフ]**単一観測での即時判定と直近N観測窓での判定を比較した実験は、後年のcontinuity threshold(Minder)やペナルティ重み調整(MetricSifter)が扱う「検知感度と誤警報率のトレードオフ」を、変化点検知以前の最も単純な形で定量化していた**: [[@1998__PER__Internet Service Performance Failure Detection]]は、単一観測アルゴリズム(検証データで検知率90%・誤警報2件)と窓サイズ5・閾値2の窓ベースアルゴリズム(検知率90%だが誤警報3件、より早期の検知が可能)を比較し、早期警告と誤警報数が背反することを示した。この背反は、本ページが[[Minder]]のcontinuity threshold(4分の固定値)や[[MetricSifter]]のペナルティ重みの感度として記録してきたトレードオフの、時系列版・より単純な先行例といえる。(Source: [[@1998__PER__Internet Service Performance Failure Detection]]) ## 未解決の問い - Chandola 2009 が整理する構造利用アプローチ(回帰モデルからの逸脱=点異常の判定)と、変化点検知(分布パラメータのシフト)を同一の時系列データに独立に適用した場合、どこまで同じ時刻を検知するか。障害伝播シナリオでは両者が同一の根本原因に起因する現象を別の粒度(点対区間)で捉えている可能性があるが、直接比較した研究は本ページ・Chandola 2009 のいずれにも見当たらない。(Source: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]]) - 訓練窓に既存インシデントや外れ値が混入した場合、本ページの主要手法(Pelt+$c_{L_2}$、BOCPD、SST)はどこまで頑健か。Chandola 2009 第7章のロバスト回帰(訓練データ中の異常が回帰パラメータを歪める問題への対処)に相当する「訓練データ汚染への頑健性」を明示的に評価した変化点検知の研究は本ページに見当たらない。(Source: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 7 Statistical Anomaly Detection Techniques]] §7.1.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) - FUNNEL の DiD 法は「treated group と control group が(変更以外は)同一の統計的挙動を持つ」というロードバランシング前提に強く依存する(§3.2.4 の observations 1-4)。この前提が成立しにくい小規模システム(サービスあたりサーバ1台等)や、control group を構築できない Full Launching 環境で、DiD に代わる因果帰属の設計はどうあるべきか。(Source: [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]], §3.2.4-3.2.5) - FUNNEL は変動性(variable)KPI で precision 68.47% と季節性・定常性(いずれも 98%超)より明確に劣る(Table 1)。高変動 KPI での変化点検知の精度改善は、後年の BOCPD 系(BARO 等)のロバストスコアリング(中央値/IQR)でどこまで解決されているか、両者の直接比較は本 concept 内でまだ行われていない。 - 1998年のZスコア閾値法(窓サイズ・非対称閾値)は、後年のBOCPD/SST系と比べて、同じDEC社内プロキシ計測データに適用した場合どの程度の精度差があるか。直接比較した研究は本ページに見当たらない。(Source: [[@1998__PER__Internet Service Performance Failure Detection]]) ## 関連 - ソース: [[@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__PhD__Scaling Telemetry Workloads in Cloud Applications - Chapter 5 Feature Reduction of Multivariate Time Series Data for Automated Fault Localization]] / [[@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]] / [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]] / [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]] / [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 7 Statistical Anomaly Detection Techniques]] / [[@1998__PER__Internet Service Performance Failure Detection]] - 概念: [[特徴量削減]] / [[Fault Localization]] / [[時系列基盤モデル]] / [[多変量時系列予測]] / [[異常検知]] / [[カーネル密度推定]] - エンティティ: [[MetricSifter]] / [[Minder]] / [[ruptures]] - 関連 MOC: [[異常検知 - MOC]] / [[時系列基盤モデル - MOC]] ## 出典 - [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 10 Handling Contextual Anomalies]](§10.2 構造利用アプローチ、AR/ARMA/ARIMA による文脈異常検知) - [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 7 Statistical Anomaly Detection Techniques]](§7.1.2 回帰モデルベース、ロバスト回帰による訓練データ汚染への対処) - [[@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__PhD__Scaling Telemetry Workloads in Cloud Applications - Chapter 5 Feature Reduction of Multivariate Time Series Data for Automated Fault Localization]](§5.3.4-5.3.5 Algorithm 2、§5.5.6 ablation study Fig. 5.9) - [[@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 実行時間) - [[@2015__CoNEXT__Rapid and Robust Impact Assessment of Software Changes in Large Internet-based Services]](§3.2.1-3.2.3 改良 SST、§3.2.4-3.2.5 DiD 法、Table 1-2 精度・計算コスト比較)