- Anomaly Detection in Streams with Extreme Value Theory
- Amossys-team/SPOT: SPOT algorithm implementation (with variants)
KDD2017の異常検知の論文です。異常検知を行なうとき、何らかの閾値を設定しますがこの閾値の決定は難しいことが多いです(そして精度にはよく効いてくる...)。正規分布のように理論的によく知られていて、解析的にも扱いやすいような分布では、累積分布関数を逆に辿ると「99.9%に対応する閾値はこれ!」と設定することができます。しかし、確率分布を陽に仮定するとそれ以外の分布ではきちんと動かなかったり、データ毎にモデル化をする必要があります。陽に確率分布を仮定しない方法もありますが、そちらはデータが少ないor厳しめのパーセンタイルを指定したいときに難しさがあります。例えば、データが1000個しか取れないような場合に99.9%に対応する閾値を知ろうと思って、異常値のスコアの999番目に大きい値を取ろうとすると、その値がぐらつくだけで閾値が大きく変わってしまう場合などです。こういう場合は理論値が知りたい。
この論文ではデータ自体の分布を陽に仮定はせず、データの最大値や分位点に関する分布を異常検知に用いることを考えます。最大値のような極端な値(Extream Value)は順序統計量と呼ばれたり、極値統計学と呼ばれる理論があり、自然災害への対応やファイナンス(Value at riskなど)などに特に応用されています(津波や地震などは平均的な挙動が知りたいわけではなく、例えば一年間で最も災害をもたらしそうな値がどれくらいのものなのかを知りたい)。Extream Valueを異常検知に適応する考え方自体は前からあったようですが、この論文ではサイバーセキュリティのように大量のデータが流れてくる、かつデータの傾向も動的に変動するといったケースに対応できるようにしようというのがこの論文の主な貢献です。
極値統計学
- 極値分布はi.i.dなサンプルの最大値や最小値をモデル化した分布
- i.i.dの元になってる分布によって極値分布も変わるが、一様分布、ガンマ分布など、様々な分布を包含した一般的な形で書くことができる
- P(X > zq) < qとなるような閾値zqを極値分布を使って知りたい
- 極値分布のパラメータ推定をすればよいが、特定のケースしかあまりうまく行かないようだ
- そこで、分布のtailの部分をfitingする他のアプローチとして、Peaks-Over-Threshold(POT) approachというものを使う
- このアプローチは緩い仮定の条件下で、条件付きの累積分布がSection3.3にあるような形で分布収束するというもの
- Xが閾値tよりもx以上大きくなる確率(P(X - t > x | X > t))
- 収束先の分布に対して推定を行う(この場合、パーセンタイルにそれがなる)
- 収束先の分布は一般化パレート分布になってる
- パレート分布 - Wikipedia
- パレート分布はある閾値を超える確率をモデリングした分布
- 極値統計学
- 最尤推定でパラメータを計算できたら、欲しい確率qに対応した閾値zqを(1)式によって計算することができる
- この式はどこから出てきたんだ...?
- この辺((2.9)式)あたりを見ると分かりそうだった
- 静的でバッチでいいときはAlgorithm 1で決める
- 最初の閾値tをどうやって決めるかが謎だが、section 4.3.2によると学習データの98%タイルのようなある程度大きい(かつ1-qより小さい)empirical quantileを使うようだった
Streamへの対応
- やりたいこととしてはデータの傾向が動的に変わる場合だが、その前にパラメータがをstreamで更新できるように拡張する
- Algorithm 2
- ストリームと書いてあるけど、閾値を超えてる集合(Y)をmaintainして、パラメータはバッチでどかっと再計算してた...。オンラインっぽいノリではないのか
- ただ、多分、異常検知の文脈で閾値を超えたようなやつのサンプル数って多くないからバッチでやり直しても実質問題ないってことなんだと理解した
- 元データが10000あっても99%タイルだと100個しか学習に実質使われない、みたいなノリ
- これのおかげで、秒間1000くらいデータが流れ込んできても平気だそうな
- 集合に追加はされるが、削除はされない
- パラメータ推定はGrimshaw's trick(section 3.4.2)というのを使うそうだけど、一般化パレート分布のパラメータ推定ではよく使うテクニックらしい
Drift caseへの対応
- Streamへの対応だけでは保持してる集合に追加してくだけで、分布が変化していく場合に対応できない(drift case)。それに対応できるようにする
- (streamってそもそもメモリにデータ全部乗っけとけないって設定だった気がするけど、この論文はそういうこと考えてない気がする)
- 移動平均使って若干ずらしていく感じ?アドホック過ぎて正当性はあまりなさそう
- この方法でなんでいいのかは述べずに実験の章に突入
- こっそりとwindow-sizeという新しくて重要なパラメータが追加されている
実験
- 人口データで理論値と閾値の食い違いを評価(section 5.1)
- 静的なデータの例(サイバーセキュリティ)はうまくいってそう(section 5.2)
- 動的なケースもまあまあ(section 5.3)
- window-sizeの調整は難しそうではある
論文を読んだ感想
- 異常検知では分布全体よりも極端な値の傾向を知りたいことが多いので、極値分布や一般化パレート分布を用いてtail部分を重点的にfittingしにいくというアプローチは面白い
- 極値理論という硬派な(?)理論をベースにしているわりにはstreamやdrift caseへの対応はアドホックな感じで、理論的な正当性があまりない
- empiricalにはよいでしょう、という感じで実験で保証
- しかし、実験はもっと他の手法とも比較実験をして欲しかった
- おそらく事前に分布の形状が分かっているならば提案手法が負けてしまうから、というのが大きい気はする...
- とはいえ、分布の形状が事前に分からなくてもこれくらいcomparativeな結果が出ます、というので十分だとは思う