Nonparametric Detection of Multiple Location-Scale Change Points via Wild Binary Segmentation

ゴードン・J・ロスによる論文「非パラメトリックな位置・スケール変化点の検出：ワイルド・バイナリ・セグメンテーションによる手法」の詳細な技術的概要を以下に示す。

1. 問題定義

本論文は、一変量観測系列 $y = (y_1, \dots, y_n)$ における多重変化点検出問題を取り扱っている。目的は、統計的挙動が異なるセグメントに系列を分割する変化点の数 ($K$) と位置 ($\tau = \{\tau_1, \dots, \tau_K\}$) を同時に推定することである。

主要な制約と課題:

• 非パラメトリック設定: 各セグメント内のデータの分布形式は未知である。手法は正規性などの特定のパラメトリック仮定に依存してはならない。
• 対象とする変化: 任意の分布変化ではなく、位置（平均）および/またはスケール（分散）のシフトを検出することに焦点を当てる。
• マスキング効果: バイナリ・セグメンテーションのような従来の逐次的手法は、複数の変化点が互いに近接している場合に失敗することが多い。2 つの変化が近接して発生する場合、単一の分割点がセグメント全体の検定統計量を最大化しないため、アルゴリズムが変化を見逃す（マスキングされる）ことがある。
• 偽陽性の制御: 既存の非パラメトリック手法は、特にペナルティ選択が敏感なペナルティ付き尤度アプローチを用いる場合、有限サンプルにおいて偽検出の確率（第 1 種の過誤）を直接制御することが困難である。

2. 手法：WBS-Lepage

著者は、ワイルド・バイナリ・セグメンテーション (WBS) とランクベースのレページュ統計量を組み合わせた新しい手順であるWBS-Lepageを提案する。

A. 検定統計量（レページュ型）

特定の代替仮説に対する検出力が不足する可能性のある一般的な包括的検定（コルモゴロフ・スミルノフ検定など）の代わりに、位置とスケールに敏感な統計量を使用する。

• 構成要素: 位置シフトに敏感なマン・ホイットニー統計量と、スケールシフトに敏感なムード統計量を組み合わせる。
• 定式化: セグメント $[p, q]$ 内の候補分割点 $k$ に対して、統計量 $L^k_{p,q}$ は標準化された成分の二乗和として定義される。
  $$L^k_{p,q} = \left( \frac{U^k_{p,q} - E[U]}{\sqrt{Var(U)}} \right)^2 + \left( \frac{M^k_{p,q} - E[M]}{\sqrt{Var(M)}} \right)^2$$
• 分布フリー性: 統計量が観測値のランクのみに依存するため、その帰無分布は基礎となる連続分布に依存しない。これにより、パラメトリック仮定なしに正確な有限サンプル較正が可能となる。

B. セグメンテーション戦略（ワイルド・バイナリ・セグメンテーション）

標準的なバイナリ・セグメンテーションのマスキング効果を克服するために:

• ランダム区間: 現在のセグメント全体のみを検証するのではなく、アルゴリズムは現在のセグメント内で $M$ 個のランダムな部分区間 $[s_m, e_m]$ を生成する。
• 最大化: レページュ統計量をこれらすべてのランダム部分区間に対して最大化する。局所的に変化が存在する場合、それはこれらの部分区間のいずれかに孤立している可能性が高く、セグメント全体ではマスキングされていても検出可能となる。
• 再帰的剪定: アルゴリズムは検出された変化点でデータを再帰的に分割する。事後に剪定ステップを適用して冗長な変化点を除去する。検出された点 $\hat{\tau}_j$ が隣接する $\hat{\tau}_{j-1}$ と $\hat{\tau}_{j+1}$ に囲まれている場合、アルゴリズムは結合された区間 $[\hat{\tau}_{j-1}, \hat{\tau}_{j+1}]$ を再検証する。有意な変化が見つからない場合、$\hat{\tau}_j$ は除去される。

C. 閾値較正

• モンテカルロシミュレーション: 帰無分布が分布フリーであるため、臨界閾値 $\gamma(n)$ は、さまざまな系列長 $n$ と有意水準 $\alpha$ に対してモンテカルロシミュレーションにより事前に計算される。
• 有限サンプル制御: これらの閾値により、データの分布に関係なく、均質なセグメント内で少なくとも 1 つの偽変化点を検出する確率がレベル $\alpha$（例：0.05）に制御されることを保証する。

3. 主要な貢献

1. WBS-Lepage アルゴリズム: 位置・スケール変化に特化して設計されたランクベースのレページュ統計量と、ランダム区間探索である WBS の統合。
2. 分布フリー較正: シミュレーションによる有限サンプル閾値の設定のための厳密な手法により、パラメトリック仮定なしに偽陽性率を直接制御する。
3. 理論的整合性: 位置またはスケールの対比が非ゼロである場合、単一分割推定量（レページュ統計量を最大化するもの）が真の変化点位置に対して整合的であることを証明。
4. ソフトウェア実装: 本手法は R パッケージ**npwbs**に実装されており、実用的な応用が可能である。

4. 実験結果

本手法は、ECP（Matteson & James）、PELT（MBIC および較正済みペナルティを用いた非パラメトリック尤度）、PYWR（Padilla ら）といった競合手法と比較評価された。

• 偽陽性制御:
  • WBS-Lepage と ECP は、正規分布、学生 t 分布、対数正規分布 across で、偽陽性率を名义水準（0.05）に近いレベルに維持した。
  • 標準的な PELT（デフォルトの MBIC ペナルティ使用）は高い偽陽性率（約 40%）を示し、非パラメトリック設定におけるペナルティの調整の難しさを浮き彫りにした。較正済み PELT バージョン（PELT-FP）は良好に機能したが、特定の調整を必要とした。
• 位置変化の検出:
  • WBS-Lepage は、位置変化データセット（例：fms, mix）において、ECP や PELT-FP と競争力のある性能を示した。
  • 標準的なバイナリ・セグメンテーションがしばしば失敗する短期間の変化（interval データセット）を正常に検出した。
• スケール変化の検出（主要な利点）:
  • WBS-Lepage は、スケール変化データセット（dhk, kfe）において、すべての競合手法を大幅に上回った。
  • ECP や PYWR などの競合手法は、分散変化の数を過小評価する傾向があった。
  • WBS-Lepage は、重尾分布（学生 t 分布）や歪んだ分布（対数正規分布）の下でも、高い検出力と正確な局所化を維持した。
• 剪定の影響: 剪定ステップは、fms や dhk データセットのような複雑なシナリオにおいて、推定された変化点数の誤りを一般的に減少させた。

5. 実世界への応用：スタイルメトリ

本手法は、サー・テリー・プラチェットによる41 冊の『ディスクワールド』小説のコーパスに適用され、執筆スタイルの変化を検出した。

• データ処理: テキストを単語数のベクトルに変換した。主成分分析（PCA）によりデータを 2 番目の主成分（漸進的なドリフトではなく急激な変化を捉える）という一変量の要約に縮約した。
• 発見: WBS-Lepage は 2 つの変化点を検出した。
  1. シリーズの初期（7 巻後）：確立されたシリーズスタイルへの移行を示す。
  2. シリーズの後期（31 巻後）：プラチェットのアルツハイマー病診断の時期に発生。
• 意義: この結果は、以前の多変量パラメトリック分析と整合するが、非パラメトリックかつ教師なしのアプローチで達成されたものであり、探索的データ分析における本手法の有用性を示している。

6. 意義と結論

本論文は、WBS-Lepageを、堅牢な非パラメトリックな変化点検出ツールとして確立する。その主な意義は以下の点にある。

• スケール検出における優位性: 非ガウスデータにおいて、多くの手法が分散変化を検出できないという分野の既知の弱点を解決する。
• 堅牢性: ユーザーがペナルティパラメータを推測したり、特定のデータ分布を仮定したりすることなく、信頼性の高い偽陽性制御を提供する。
• 実用性: マスキング耐性を持つワイルド・バイナリ・セグメンテーションと、分布フリーなランク統計量を組み合わせることで、多様な実世界のデータセットにおける位置およびスケールシフトの検出に対する「プラグ・アンド・プレイ」型の解決策を提供する。

著者は、本手法がセグメント内では独立した観測値を仮定しているが、依存構造をモデル化した後の残差に適用することで、連続的に依存するデータにも適応可能であると指摘している。