Twitterが公開したRパッケージBreakoutDetectionについて調べたことメモ(その2)

前回までのあらすじ
Twitterが公開したRパッケージBreakoutDetectionについて調べてみたけど統計の知識が足りなくてよく分からない(超ざっくり

なんかいろいろ調べた感じ、変化点検出というのはわりとアツい分野のようで、いろいろ資料が見つかりました。changepointというRパッケージもBreakoutDetectionが出る前からすでにあったりします。

changepointパッケージについて書いたペーパーがわりと分かりやすそうだったんですが、ここはとりあえず、Wikipedia先生のありがたいお言葉を聞いてみましょう。

Change Detectionとは

Change detection - Wikipedia, the free encyclopedia

曰く、change detectionにはいろいろあって、

  • online change detection
  • minimax change detection
  • offline change detection

とかがあるらしいです。大別にするとこの3つになる、というわけではなくて単に羅列してあるだけみたいですけど。minimaxはちょっとよく分かりませんが、onlineとofflineは対になっているっぽいです。なんでしょうこれは。

onlineとoffline

Sequential analysis - Wikipedia, the free encyclopediaによると、

In statistics, sequential analysis or sequential hypothesis testing is statistical analysis where the sample size is not fixed in advance.

とあります。サンプルのサイズが事前に決まらないもの、つまりリアルタイムにデータを流し込んで解析するようなときの分析の仕方だと思われます。

逆に、offlineの方はサンプルサイズが事前に決まっているものだと思われます。

offline change detection

そっけなく一行だけ説明があります。

Offline algorithms may employ clustering based on maximum likelihood estimation.

もうofflineの変化点検知といえば最尤法、と相場が決まっているようです。なんと。

なぜOffline algorithmsか

IT系で変化点検出というと、onlineっぽいイメージがあります。リアルタイム異常検知とかやってそう、みたいな。なんでofflineなんでしょう。

それはたぶん、BreakoutDetectionをつくったチームがPerformance Engineerの方だからだと思います。このTwitterのひとの発表のスライド8をいまいちど振り返ると、

  • Detect cold and hot services
  • Detect Performance Regressions
  • Characterize user engagement

(Mitigating User Experience from 'Breaking Bad': The Twitter Approach …)

と書いてあります。こういう観点で変化点を検出したいシナリオとしては、

「あれ、なんか遅くなってない?」
→ 「この日から変わってるっぽいぞ」
→ 「そういえばこの日あのアップデートがあったけどそれのせい?」

みたいな感じの流れが多そうな気がします。つまり、変化をリアルタイムに知りたいのではなくて、事後的に変化がいつあったか知りたい、というモチベーションです。

完全に推測ですけど。まあ、だいたい雰囲気がつかめてきました。ということで、実際何やってるのかみてみたいと思います。

changepointパッケージ

CRAN - Package changepoint
changepoint: An R Package for Changepoint Analysis - paper

これを読んで、変化点がひとつの時の検出法はだいたいイメージつきました。(複数のときはちょっと難しそうだったのでもうちょっと調べます)

ざっくりいうと、「ある時刻\tauが変化点であるかどうか」という問いは、「区間[0,n]がすべて同じ母集団に属すると考える方がもっともらしいか、区間[0,\tau]と区間[\tau+1,n]とが別々の母集団に属すると考える方がもっともらしいか」を考えればいいみたいです。

最大尤度 MLを用いて数式にすると(添字とか適当です。すみません…)


ML_1 = \log{p}(y_{1:\tau}|\hat{\theta_1})


ML_2 = \log{p}(y_{\tau+1:n}|\hat{\theta_2})


ML=\log{p}(y_{1:n}|\hat{\theta}))

で、 ML_1 + ML_2 MLより十分大きければ、 \tauが変化点だと考えられます。

変化点が複数の時

変化点がひとつだけだと前提を置くことができれば、区間内の点をひとつひとつ調べるだけでも済みますが、変化点がいくつあるか分からない場合は組み合わせが無数にあるため工夫が必要らしいです。この部分は読んだけどぱっとは分かりませんでした。

まとめ

  • offlineのchangepoint analysisといえば最尤法
  • 変化点が複数ある時は工夫が必要

to be continued...