Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering

あなたは、センサーを流れる長い連続的なデータのストリーム、例えば川の流れを見ていると想像してください。時として、水の性質が変わることがあります。水温が上がったり、川底の岩が動いたり、あるいは流速が変わったりするかもしれません。データサイエンスの世界では、これらの瞬間は**変化点（change points）**と呼ばれます。変化点を見つけることは、穏やかな小川が激流へと変わるまさにその瞬間を特定しようとするようなものです。

長い間、科学者たちにはこれらの変化を見つけるための優れた道具箱がありましたが、それはデータの変化が互いに独立している場合、つまり雨粒がランダムに降る時のように、互いに影響を与えない場合にのみ完璧に機能しました。しかし現実の世界では、データはしばしば**依存関係（dependent）**を持っています。例えばマルコフ連鎖（Markov chain）のようにです。マルコフ連鎖とは、「次に聞いたメッセージは、直前に聞いたメッセージに完全に依存する」という、電話の「伝言ゲーム」のようなものだと考えてください。もし川が荒れていれば、次のしぶきは前のしぶきに依存します。従来のツールは、このような状況では苦戦し、予測を誤ったり、探し始める前にあらかじめ変化がいくつ起こるのかを知っておかなければならなかったりしました。

この論文は、事前に答えを知ることなく、こうした依存関係のあるデータの中から変化を見つけ出す、巧妙で新しい方法を紹介しています。その手法を、簡単な物語に分解して説明します。

旧来のツールの問題点

著者らは、既存の多くの手法が、まるで「容疑者が何人いるか教えられない限り、事件を解決することを拒む探偵」のようであると指摘しています。また、それらの多くはデータが独立していることを前提としていますが、これは気候パターンやネットワークトラフィックのように、今日のデータが昨日のデータに強く影響を受けるような現象に対しては、無理な仮定です。

PELT（Pruned Exact Linear Time）と呼ばれる有名な手法は非常に高速ですが、著者らはこれに欠陥があることを見出しました。それは「幽霊を見る（存在しないものを見る）」傾向があるということです。彼らのテストでは、真の川には3回の変化があったにもかかわらず、PELTはデータの長さに応じて7回、8回、9回、あるいは26回もの変化を見つけてしまいました。つまり、過剰にセグメント化してしまい、川を不必要に細かく切り刻んでしまうのです。

新しい解決策：適応型クラスタリング

著者らは、スマートで適応型のソーター（分類器）のように機能する手法を提案しています。想像してみてください。あなたは、一列に流れてくる大量の色とりどりのビー玉（データポイント）を持っています。そこには何色のビー玉があるのか、あるいは色の変化がどこで起きるのかは分かりません。

彼らの手法は、ビー玉を「クラスター（セグメント）」にグループ化しようと試みます。その際、各グループ内のビー玉が可能な限り似通っているようにします。彼らは「類似性」を**クラスタリング分散（clustering variance）**を用いて測定します。分散とは「混沌（カオス）」の尺度だと考えてください。赤と青のビー玉を一つのバケツに混ぜると混沌としていますが、赤だけのバケツは穏やかです。目標は、この混沌を最小限に抑えるように川をバケツへと切り分けることです。

これを依存関係のあるデータ（「伝言ゲーム」のようなデータ）に対して機能させるために、彼らは新しい数学的な安全網を考案する必要がありました。彼らは、これらのマルコフ連鎖に特化したドブレツキー・キーファー・ウルフヴィッツ（DKW）不等式を証明しました。平易な言葉で言えば、これは次のような保証です。「たとえデータポイント同士が互いに影響し合っていたとしても、十分に長い時間を待てば、我々の推定する川の形状は真実に非常に近いものになる」ということです。

証明：彼らが実際に発見したもの

この論文は単に推測しているのではなく、数学的に証明し、シミュレーションによって検証を行っています。

1. 数学的側面： 彼らは、作成するバケツの数に対して小さなペナルティを課しながら「混沌（分散）」を最小化すれば、最終的に正確な変化の数と、その正確な位置を見つけられることを示しました。これは、データの長さに伴って変化の数が増加する場合でも成立することを証明しています。
2. シミュレーション： 彼らは、250のタイムポイントを持つテストを行い、4つの明確なセグメント（長さはそれぞれ25、75、150、25）を持つ架空の川を作成しました。
   • 結果： 彼らの新手法は、変化をまさに25、75、150で見つけました。完璧でした。
   • 競合相手： PELT法は、変化を25、37、46、72、151、161、176、および204で見つけました。本来の3回ではなく、8回の変化を見つけてしまったのです。
3. 速度と精度のトレードオフ： 著者らはまた、計算を高速化するためのコンピュータプログラム（混合整数バイナリ定式化）を構築しました。彼らは、最初のバージョンよりも計算を大幅に速くする「双線形再定式化（bilinear reformulation）」という数学的トリックを見出しました。
   • 250のデータポイントに対し、彼らの高速な手法は9.43秒かかりました。
   • PELT法はわずか0.35秒であり、最も高速ですが、間違っていました。
   • 彼らの低速なオリジナル手法は30.42秒かかりましたが、これも完璧でした。

提唱していないこと

この論文が「言っていないこと」を知っておくことも重要です。

• 彼らは、これがあらゆるタイプのデータに対して機能すると主張しているわけではありません。彼らは特に、データが「再生マルコフ連鎖（regenerating Markov chain）」（時折自身をリセットする特定の種類の依存関係のあるデータ）のように振る舞うことに焦点を当てています。
• 彼らは、この手法が多変量データ（多くの異なる変数が同時に存在するデータ）の問題を解決したとも主張していません。多次元への拡張は、依然として「未解決の課題」であると明記しています。
• 彼らは、自分たちの手法が世界で最も速いとも主張していません。PELTの方が速いことは認めていますが、偽の変化を見つけてしまうのであれば、速度は価値がないと彼らは主張しています。

結論

著者らは、事前に答えを知ることなく、依存関係のあるデータのストリームから複数の変化を見つけ出すことができる、厳密なノンパラメトリックなツールを構築しました。彼らは数学的にそれが機能することを証明し、シミュレーションを通じて、他の一般的な手法が偽の変化を見つけて過剰に分割してしまう場面でも、正しく変化を見つけられることを示しました。

背後にある数学には「ラデマッハー複雑度（Rademacher complexities）」や「オルリッツノルム（Orlicz norms）」といった複雑な概念が含まれていますが、結果はシンプルです。もし、過去が未来に影響を与えるようなデータのストリームがあるならば、この新しい手法はそれを正しく切り分けることができます。一方で、従来の高速な手法は、データを紙吹雪のように細かく切り刻んでしまうかもしれません。彼らは、将来的に「ポアソン集中（Poissonian concentration）」に関する特定の数学的パズルを解くことができれば、データの「裾（tails）」の部分における変化を捉える能力をさらに向上させられる可能性があると示唆していますが、現時点では、これは確実で証明された一歩を踏み出したものです。