修士論文 要旨

Change Sign Detection with Two-Stage MDL Change Statistics(2 段階 MDL 変化統計量による変化予兆検知の研究)
数理情報学専攻 48-196233
指導教員

結城 凌
山西 健司 教授

1 はじめに
本研究では，変化予兆検知という問題に 2 段階 MDL変化統計量でアプローチする．変化予兆検知の前身となる問題として，変化検知という問題がある [1]．これは，時系列データを考えた際に，データ発生の確率分布が変化する時刻を検知する問題を指す．ここで，変化は，1) 確率分布のパラメータ，2) 確率分布自体が持つ自由パラメータの数や潜在構造 (構造的変化と呼ぶ) の

図 1. パラメータ変化における，突発的変化と漸進的変化の例二種類に分けることができる．いずれの変化も，その背後に人間にとって重要なイベントに結びつくことが多く，実用的に重要であることから機械学習・データマイ

xn1 = x1 , . . . , xn が与えられており，時刻 t が変化点のただ一つの候補点であるとする．MDL 原理 [7] に基づニングの文脈で古くから研究されてきた．例えば，web

き，与えられたデータを 1) 変化がないと仮定した時のアクセスログが SQL インジェクションに対応すること

データの記述長，2) 時刻 t が変化点であると仮定した[2] や，顧客の購買トランザクション [3] における類似ときのデータの記述長，を比べ変化点かどうかを検定す

購買パターンが市場トレンドに対応することが報告さる．具体的には，与えられた正のパラメータ ϵ を用いてれている．従来変化検知に関する研究では，統計的に扱defいやすいことから，突発的な変化の発生が頻繁に仮定さ

Φ(xn1 )t = L(xn1 ) − {L(xt1 ) + L(xnt+1 )} − nϵ,れていた．しかし，現実の状況下においては，変化の漸を時刻 t における MDL 変化統計量とし，これが 0 を進的発生を仮定する方が自然であり，この場合従来手法超過した場合にのみ変化点であると判断する．ここで，では漸進的変化の検知遅延・見逃しが起こりうる．そのL(·) はデータの記述長を出力する関数であり，NML 符ため，漸進的変化開始点検知や，より一般に変化予兆の号長 [8] が良好な性質をもつのでよく用いられる．ま検知を試みる研究が増えてきている [3, 4, 5]．[5] で指た，パラメータ・構造的変化の両方における MDL 変化

摘されているとおり，変化予兆検知の目的は二つある．

統計量の計算方法はすでに確立されている [2, 6]．

一つ目は，変化予兆を捉えることで，その直後に起こる変化を予測することであり，二つ目はデータが一括で与えられた下で既に発生した変化の原因を解析するためである．

3 提案手法提案手法である 2 段階 MDL 変化統計量について説明する．1 段階目では，change probability ptchange と本研究では，パラメータ変化および構造的変化においいう各時刻が変化点である確率をモデリングした統計て漸進的変化を仮定し，その開始点を変化予兆と考える量を計算する．これが 1 段階目の変化検知に対応する．

(図 1)．そして，2 段階の変化検知で漸進的変化の開始

2 段階目では，change probability の負の対数の増加率点を検知する，2 段階 MDL 変化統計量を提案する．

rt = (− log ptchange )/(− log pt−1change ) − 1 を計算し，こ2 従来研究の統計量に対し MDL 変化統計量を用いて再度変化検知を行う．パラメータ・構造的変化両方において，漸進2 段階 MDL 変化統計量は MDL 変化統計量 [2, 6] を的変化の過渡期に入ると rt の分散が時間に沿って増加基にしており，まずこちらを説明する．F = {p(X; θ) :することを確認し，その分散の変化を検知することでθ ∈ Θ} を確率変数 X の従う確率分布のクラスとする．

漸進的変化の開始点を検知を実現する．まず時刻 t でθ ∈ Θ は確率分布のパラメータである．時系列データの change probability を，与えられた正のパラメータChange Sign Detection with Two-Stage MDL Change Statistics (2 段階 MDL 変化統計量による変化予兆検知の研究) (結城 凌)類生成した．こちらにおいても同様に，提案手法が最も良い性能を出すことを確認できた．
実データにおいては，Dow Jones 平均株価，工場における生産ラインの多次元データ，感染流行データという多様な性質を持つデータセットにおいて提案手法を適用した．それらのデータセットにおいて，現実でのイ
図 2. 誤検知率と遅延の曲線下面積．赤線が提案手法

ベント (平均株価では政治的イベント，感染流行データであり，他色は対抗手法．変化過渡期の長さがでは感染流行対策など) と提案手法があげたアラームを長い時，提案手法が最も良い性能を出すことが比較した結果，イベントの予兆と考えられるアラームを確認できた．縦軸: 曲線下面積．横軸: 変化過複数上げていることが確認できた．

渡期の長さ．

5 まとめ
β を用いて次の形で定義する．
ptchange =本研究ではパラメータ・構造的変化を対象にした変化予兆検知手法，2 段階 MDL 変化統計量を提案した．まexp(−β(L(xt1 ) + L(xnt+1 ))), た，実用的なアルゴリズムを 2 種類提案した．人工デー
exp(−βL(xn1 )) + exp(−β(L(xt1 ) + L(xnt+1 )))タによる実験では，提案手法が定量的に良い性能を示せ

ここで，change probability はパラメータ・構造的変化のどちらにおいても定義できることに注意したい．

ることを確認し，実データでは，様々な性質を持つデータにおいて提案手法が良い変化予兆検知を行えること

次に，change probability の負の対数の増加率 rt =を確認した．今後の展望としては，提案手法の予兆検知(− log ptchange )/(− log pt−1change ) − 1 という新たな統計の意味での性能保証解析などが考えられる．

量を考える．変化過渡期になると，この統計量の分散が増加することが，実験的，さらに簡単な数理的考察から参考文献確認した．rt が 1 変数ガウス分布に従うことを仮定し[1] 山西健司編著. データサイエンスの数理 数理で読み解く
データの価値 数理科学 2019 年 06 月号. サイエンス社,
2019 年 6 月.
[2] Kenji Yamanishi and Kohei Miyaguchi. Detecting
gradual changes from data stream using mdl-changestatistics. In 2016 IEEE International Conference onBig Data (Big Data), pages 156–163. IEEE, 2016.
[3] So Hirai and Kenji Yamanishi. Detecting modelchanges and their early warning signals using mdl
change statistics. In 2019 IEEE International Conference on Big Data (Big Data), pages 84–93. IEEE,
2019.
[4] Kohei Miyaguchi and Kenji Yamanishi. Online detection of continuous changes in stochastic processes.
International Journal of Data Science and Analytics,
3(3):213–229, 2017.
[5] Kenji Yamanishi and So Hirai. Detecting signs ofmodel changes with continuous model selection. submitted to IEEE Transactions on Knowledge and DataEngineering, 2020.
[6] Kenji Yamanishi and Shintaro Fukushima. Modelchange detection with the mdl principle. IEEE
Transactions on Information Theory, 64(9):6115–6126, 2018.
[7] Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465–471, 1978.
[8] Yurii Mikhailovich Shtar’kov. Universal sequential
coding of single messages. Problemy Peredachi Informatsii, 23(3):3–17, 1987.

た上で，MDL 変化統計量を用いて
defn
Φt2−stage = L(r1n ) − {L(r1t ) + L(rt+1)} − nϵ,をシステムの最終的な出力とする．

4 実験結果
提案手法および対抗手法を人工データおよび実データを用いて評価した．人工データでは，パラメータ変化および構造的変化の両方において，漸進的変化を複数持つデータセットを生成した．パラメータ変化においては，独立ガウス分布のパラメータが変化するデータセッ
トを生成し，さらに漸進的変化の変化過渡期の長さを変化させた．ここで，変化過渡期前後のパラメータは固定したため，変化過渡期が長くなるほど変化予兆の検知は難しくなることが予想される．図 2 は提案手法および対抗手法の結果の一部である．変化が突発的変化に近い場合，対抗手法が高い性能を出すことが出来ているものの，変化過渡期が長くなるにつれて，提案手法がより高い性能を出せていることが確認できる．構造的変化においては，混合ガウス分布に従い，混合数が漸進的に変化するデータを，漸進的変化の特徴を変えつつ複数種