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になるようにしている
  • 平均方向ベクトルからのばらつき度合い(分散)を表わすようなパラメータΚは実は目的関数にはあまり大きな影響を与えないので、今回は定数として取り扱う
    • いい感じにΚを推定する方法もあるようだ

複数のパターンに対応できるようにする

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

異常度としてのKLダイバージェンス

  • 学習とテストの期間の長さは当然異なるので、代表的なパターンをいくつ取るかもそれぞれ異なる
    • 学習用のパターン数を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})の結果を使う
    • 線形結合のベクトル\mathbf{f}\mathbf{g}も正規化されているという条件を使うと、SVDの問題に落ちる
    • 異常度は最大特異値が手に入れば、簡単に計算できる
  • SDVで必要な計算オーダーはO(min(m, r)^3)なので無視できるようなオーダー
    • パターン数は現実はかなり少なくて問題ない(多くても10とかそんなもん?)

実験: Failure detection of ore belt conveyors

  • センサーによって得られた10次元の指標から変化点検出をする
  • 約40%に対応するデータの重みが0になっており、ノイズに対応するデータはモデルから自動的に除去された
  • PCAやホテリングのT2法、部分空間法(?)を使った方法よりもよいパフォーマンスを得た

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)