> [!abstract] 概要 > 本論文は、多変量時系列における複数の変化点をオフラインで検出するアルゴリズムの選択的サーベイである。この膨大な研究群を整理するために、一般的かつ構造化された方法論的戦略を採用する。具体的には、本レビューで検討する検出アルゴリズムを 3 つの要素——コスト関数、探索手法、変化点数への制約——で特徴づける。これらの要素をそれぞれ個別に記述・検討・議論する。本論文で述べた主要アルゴリズムの実装は、[[ruptures]] という Python パッケージで提供される。 ## 論文情報 - **タイトル**: Selective review of offline change point detection methods - **著者**: [[Charles Truong]]（CMLA, CNRS, [[ENS Paris-Saclay]]）、[[Laurent Oudre]]（L2TI, University Paris 13）、[[Nicolas Vayatis]]（CMLA, CNRS, [[ENS Paris-Saclay]]） - **媒体**: Signal Processing, Volume 167, Article 107299, 2020 - **arXiv**: 1801.00718（投稿 2018-01-02、最終改訂 2020-03-26、v3） - **DOI**: 10.1016/j.sigpro.2019.107299 - **コード**: [[ruptures]]（BSD ライセンス） ## 概要 多変量時系列のオフライン変化点検知を、コスト関数・探索手法・変化点数の制約という 3 要素の組み合わせとして統一的に体系化するサーベイ論文である。パラメトリック/ノンパラメトリックの計 13 種のコスト関数、最適/近似の 5 種の探索アルゴリズム、線形/l1/複雑ペナルティの制約手法を網羅し、各手法の漸近一致性を含む理論的性質と応用例を整理する。主要手法はモジュール式の Python ライブラリ [[ruptures]] として実装・公開されている。 ## 問題設定 入力は多変量（$d \geq 1$）非定常確率過程 $y = \{y_1, \dots, y_T\}$ で、$y$ は区分定常であり、未知の時点 $t^*_1 < t^*_2 < \cdots < t^*_{K^*}$ で統計的性質が急変する。出力は変化点インデックスの集合 $\hat{T}$。問題は 2 種に分かれる。 - **Problem 1（既知 K）**: 変化点数 $K$ が既知のもとで、分割のコスト和 $V(T, y) = \sum_k c(y_{t_k..t_{k+1}})$ を最小化する離散最適化問題。 - **Problem 2（未知 K）**: 変化点数が未知の場合、ペナルティ項 $\text{pen}(T)$ を加えた $V(T) + \text{pen}(T)$ を最小化する。 コスト関数 $c(\cdot)$ はサブ信号の「均質性」を測る。コスト和が加法的であることが全手法の前提である。 **Figure 2: 変化点検知手法の類型** ![[_attachments/arxiv-1801.00718/fig02-typology-overview.png]] （Figure 2. 本サーベイで扱う変化点検知手法の構成要素。全手法はコスト関数・探索手法・制約の 3 要素で定義される。） ## 提案手法（体系的分類） ### コスト関数（13 種） コスト関数はパラメトリックとノンパラメトリックに大別される。 **Figure 6: コスト関数の類型** ![[_attachments/arxiv-1801.00718/fig06-cost-function-typology.png]] （Figure 6. パラメトリック 3 系統（最尤推定・区分線形回帰・Mahalanobis 型距離）とノンパラメトリック 3 系統（ノンパラメトリック最尤・順位統計・カーネル）の分類。） **パラメトリックモデル**: 1. **最尤推定系**: $c_\text{i.i.d.}$（一般の分布族）から $c_{L_2}$（平均シフト = 二乗誤差損失）、$c_\Sigma$（平均+分散シフト）、$c_\text{Poisson}$（計数データ）が導出される。ガウス分布の平均シフト検出（$c_{L_2}$）は最も古く最も研究されたモデルであり、DNA アレイデータや地質信号に応用される。 2. **区分線形回帰系**: $c_\text{linear}$（最小二乗）と $c_{\text{linear},L_1}$（最小絶対偏差、重い裾分布に適合）。自己回帰モデル $c_{AR}$ は特殊ケースとして EEG・fMRI・音声認識に応用される。計量経済学で「構造変化(structural change)」の検出に広く用いられる。 3. **Mahalanobis 型距離**: $c_M$ は線形変換後の平均シフトを検出する。$M$ を逆共分散行列に設定すると Mahalanobis 距離になる。教師あり計量学習で $M$ を最適化する手法も存在する。 **ノンパラメトリックモデル**: 4. **ノンパラメトリック最尤**: $c_{\hat{F}}$ は経験累積分布関数に基づく。分布非依存だが計算量が $O(T^3)$ と大きく、スクリーニングステップや近似で対処する。 5. **順位統計**: $c_\text{rank}$ はデータの順位に基づき、単調変換に不変。Wilcoxon-Mann-Whitney 検定や Kruskal-Wallis 検定と関連する。 6. **カーネル法**: $c_\text{kernel}$ は再生核ヒルベルト空間(RKHS)への写像後の平均シフトを検出する。特性カーネル（例: ガウスカーネル）を用いれば分布変化の検出が可能。$c_\text{rbf}$（ガウスカーネル特化）と $c_{\mathcal{H},M}$（RKHS 上の Mahalanobis 型距離）も導出される。カーネル変化点検知の漸近一致性は近年証明された。 ### 探索手法（5 種） **Figure 7: 探索手法の類型** ![[_attachments/arxiv-1801.00718/fig07-search-method-typology.png]] （Figure 7. 最適解法（Opt, Pelt）と近似解法（Win, BinSeg, BotUp）の分類。） **最適解法**: 1. **Opt（動的計画法）**: Problem 1 の厳密解を $O(KT^2)$ で求める。コスト和の加法性を利用して再帰的に部分問題を解く。拡張として top-L 分割を求める「前進動的計画法」($O(LKT^2)$) と、枝刈り付き動的計画法（$10^6$ サンプルまで対応）がある。 2. **Pelt（Pruned Exact Linear Time）**: Problem 2 の線形ペナルティ下での厳密解を、明示的枝刈り規則により期待計算量 $O(T)$ で求める。レジーム長が一様分布に従う仮定下で線形時間。 **近似解法**: 3. **Win（窓スライド）**: 隣接する 2 窓間の乖離度を走査して変化点をピーク検出する。計算量は $O(T)$（線形）。Student t 検定・GLR 検定・カーネル MMD 検定と等価な場合がある。 4. **BinSeg（二分分割）**: 貪欲法で逐次的に変化点を追加。$O(T \log T)$。近接する変化点の検出精度が低い欠点がある。拡張として circular BinSeg（DNA コピー数解析）、wild BinSeg（ランダム区間上の検出）がある。 **Figure 9: BinSeg の模式図** ![[_attachments/arxiv-1801.00718/fig09-binseg-schematic.png]] （Figure 9. BinSeg の再帰的分割過程。Step 0 の信号全体に対し、コスト和を最も下げる分割点を選び、結果のサブ信号に再帰的に同じ操作を適用する。） 5. **BotUp（ボトムアップ統合）**: BinSeg の逆で、多数の微小区間から出発して乖離度が最小のペアを統合する。計算量は $O(T)$ だが、初期グリッドに含まれない変化点を検出できない。BinSeg より 10 データセットで優れるとの報告あり。 ### 変化点数の推定（制約） **Figure 11: 制約の類型** ![[_attachments/arxiv-1801.00718/fig11-constraint-typology.png]] （Figure 11. 変化点数が既知（Known K*）の場合は直接解き、未知（Unknown K*）の場合は l0 ペナルティ・l1 ペナルティ・その他の手法で推定する。） 1. **線形ペナルティ（l0）**: $\text{pen}_{l_0}(T) = \beta|T|$。BIC・AIC が特殊ケース。平滑化パラメータ $\beta$ の較正が鍵で、交差検証・スロープヒューリスティクス・教師あり学習による方法がある。 2. **fused lasso（l1 ペナルティ）**: $c_{L_2}$ との組み合わせで凸最適化に帰着し、Lars で $O(T \log T)$ で解ける。平均シフトモデル下で漸近一致性が証明されている。 3. **複雑ペナルティ**: modified BIC（$\text{pen}_\text{mBIC}$、均等間隔の変化点を選好）と Lebarbier のオラクル不等式を満たすペナルティ（$\text{pen}_\text{Leb}$）。いずれもトラクタブルでないため、$K = 1, \dots, K_\text{max}$ で Opt を回して最良を選ぶ。 ## 新規性 本サーベイの独自性は以下の点にある。 - 変化点検知手法を**コスト関数・探索手法・制約の 3 軸で直交的に分解**し、任意の組み合わせを許容するモジュール的視点を提示したこと。従来のサーベイ（ベイズ系を含む包括的なもの、窓ベース手法に特化したもの、理論的性質に焦点を絞ったもの）と異なり、**実務者がタスクに応じて要素を選択してアルゴリズムを組み立てる**ための実用的枠組みを提供する。 - ベイズ的手法（HMM、Dirichlet 過程等）はスコープ外とし、加法的コスト和 $V(T) = \sum c(\cdot)$ に帰着する手法に限定。この制約が 3 軸分解を可能にしている。 - サーベイと対応する Python ライブラリ [[ruptures]] を公開し、モジュール式 API（探索手法とコスト関数を自由に組み合わせ可能）、キャッシュ付き複数回実行、サブサンプリングによるスケーラビリティを実装。 ## 評価指標 論文は 4 種の評価メトリクスを整理する。 - **AnnotationError**: 推定変化点数と真の変化点数の差 $|\hat{K} - K^*|$。 - **Hausdorff 距離**: 真の変化点集合と推定集合の間の最大距離（最悪誤差）。 - **RandIndex**: 2 つのセグメンテーション間の合致度（0〜1）。クラスタリングの Rand Index と同じ定義。 - **F1-Score**: マージン $M$ 以内の一致を真陽性とした適合率・再現率の調和平均。 ## 考察 - 3 軸分解は「どのコスト関数がどの変化型に適するか」「計算量とのトレードオフで探索手法をどう選ぶか」を明示化し、実務的なプロトタイピングを容易にする。 - ベイズ手法の除外は本サーベイの限界であり、HMM や Bayesian Online Changepoint Detection（BOCD）など実用上重要な手法群が対象外となる。 - カーネル法（$c_\text{kernel}$）は分布変化を非パラメトリックに検出でき、キャリブレーションパラメータが少ないため汎用性が高いが、カーネルグラム行列の計算（$O(T^2)$）がスケーラビリティのボトルネックとなる。 - Pelt の線形時間性はレジーム長が一様分布に従う仮定に基づくため、極端に短いまたは長いレジームが多い場合は最悪 $O(T^2)$ に退化しうる。 ## 強み - 3 軸分類は既存の変化点検知文献を横断的に整理する上で極めて有効であり、各要素の独立な選択を可能にする。 - 評価メトリクスの統一的記述により、異なる手法間の比較基盤を提供する。 - 漸近一致性の理論的結果を各コスト関数・探索手法に紐づけて整理しており、理論的保証の有無が一覧できる。 - [[ruptures]] の公開により、サーベイの内容が再現可能な形で利用できる。 ## 弱点・課題 - ベイズ手法（HMM・BOCD・Dirichlet 過程等）を除外しているため、オンライン変化点検知やオンライン→オフライン変換を行う実用シナリオをカバーしない。 - 実データでの大規模ベンチマーク実験は含まれておらず、各手法の比較は理論的性質と応用事例の列挙にとどまる。 - 高次元時系列（$d \gg 1$）や非定常ノイズ下でのスケーラビリティについて、実験的な検証がない。 - 2020 年時点のサーベイであり、深層学習ベースの変化点検知手法（例: 時系列基盤モデルによる変化点検知）は対象外。 **Figure 12: ruptures パッケージの構成** ![[_attachments/arxiv-1801.00718/fig12-ruptures-package.png]] （Figure 12. ruptures の全体構成。入力信号（シミュレーション/ユーザーデータ）→ 変化点検知（探索手法 + コスト関数 + 制約）→ 評価（表示 + メトリクス）のパイプライン。）