Change Detection using Directional Statisticsを読んだ

方向データに対する変化点検出の論文を読んだところ、面白かったのでメモを残しておきます(論文、スライド)。IJCAI2016の論文です。

異常検知は重要な領域であるにも関わらず、まだまだ枯れていなくて論文読んでて面白いものが多いですね。

問題設定

多次元かつノイズの多い時系列データに対して変化点検出を行いたい
実データでは、ある変数にのみノイズが乗るというより、相乗的にノイズが乗ることが多いが、そのノイズを誤検知したくない
- 例: 同じモーターで複数のベルトコンベアが操作されているので、一緒にセンサーのノイズが乗る

複数の変数に同時にノイズが乗る場合、ベクトルのノルムは大きくなるが、方向は同じ
- こういうのは変化点ではないので無視したい
- 1次元の時系列だけではノイズかどうか判断できる材料が少ないので、多次元を見る意味は大きい
こういう場合に有効なのがvon Mises-Fisher分布
- イメージとしては超球上のガウス分布
- ノルムの大きさは1に正規化されているので、ベクトルの方向のみを取り扱うことができる
参考: 異常検知本の読書メモ Part 2(方向データの異常検知と部分空間法による変化検出) - yasuhisa’s blog

以下が基本的な考え方。

学習期間とテスト期間をそれぞれvon Mises-Fisher分布でモデル化
代表的な方向は一つではないので、いくつかのパターン分のモデルを作る
- それぞれが同じものでは意味がないので、平均方向パラメータがそれぞれ直交するように制約を入れる
それぞれの確率分布の距離をKLダイバージェンスで取り、それを異常度とする

データ毎の重み付き対数尤度 + スパースになるような正則化項
学習データxは正規化されていないので、正規化済みのベクトルをz、xの元々のノルムをbとする
ノイズが入ったようなデータであれば重みを0にすることで、学習への影響が取り除かれるようにしたい
- 正規化項でL1ノルムも入っているので、sparseになるようにしている
平均方向ベクトルからのばらつき度合い(分散)を表わすようなパラメータΚは実は目的関数にはあまり大きな影響を与えないので、今回は定数として取り扱う
- いい感じにΚを推定する方法もあるようだ

システムの内部状態が一つであれば、単純な重み付き尤度の最大化でよい
- しかし、現実はそうではない
代表的な方向というm個のパターンでデータの動きがカバーできるようにしよう
- それぞれで同じ解を出されても困るので、 $u_i$ と $u_j$ がそれぞれ直交するような制約を持たせる
iterative sequentialなアルゴリズムでuとwは求めることができる
- Lassoのような形に落ち着く
- 結構綺麗で、実装もしやすそう

学習とテストの期間の長さは当然異なるので、代表的なパターンをいくつ取るかもそれぞれ異なる
- 学習用のパターン数をm、テスト用のパターン数をrとする
パターン数が異なるので、線形結合で代表的なパターンを作り、KLダイバージェンスで距離を考える
- 学習データで得られた平均方向ベクトル $u_1, u_2, \cdots, u_m$ を束ねた行列UはM * m次元。m次元の正規化されたベクトル $\mathbf{f}$ と線形結合
- テストデータで得られた平均方向ベクトル $v_1, v_2, \cdots, v_r$ を束ねた行列UはM * r次元。r次元の正規化されたベクトル $\mathbf{g}$ と線形結合
KLダイバージェンスが最小になるような線形結合(と)の結果を使う
- 線形結合のベクトル $\mathbf{f}$ と $\mathbf{g}$ も正規化されているという条件を使うと、SVDの問題に落ちる
- 異常度は最大特異値が手に入れば、簡単に計算できる
SDVで必要な計算オーダーはなので無視できるようなオーダー
- パターン数は現実はかなり少なくて問題ない(多くても10とかそんなもん?)