異常検知本の読書メモ Part 4(密度比推定による異常検知)

前回扱った内容を密度比推定により直接的にかっこよく解く。

やりたいこと

正常であると分かっているデータを元に異常が含まれるかもしれないデータの中から異常な標本を見つけ出す
- 個々に外れ値検出するのではなく、テストデータ全体の確率分布も考える
- 全体を考えることでノイズを減らせるのではないか、という期待がある

やる方法としては、密度比を基底関数の線形モデルで表わし、KLダイバージェンスなり、最小二乗の考え方で目的関数に落とし込んで線形モデルのパラメータを求める、というもの。割とシンプル。

密度比による外れ値検出問題の定式化

正常なデータ集合Dと異常標本が混入しているかもしれないデータ集合 $D^\prime$ が与えられているとする。ネイマンピアソン決定則によると $\mathbf{x} \in D^\prime$ に対する異常さの度合いと表わす尺度として、 $a(\mathbf{x}) = - \log r(\mathbf{x})$ を自然に考えることができる(ただし、 $r(\mathbf{x}) = \frac{p(\mathbf{x})}{p^\prime(\mathbf{x})}$ で、 $p^\prime(\mathbf{x})$ はテストデータが従う確率密度)。

密度比のふるまいについてまとめる。 $D^\prime$ において、異常標本の割合を $\alpha$ とすると、連続性など適切な条件を満たせば $p^\prime(\mathbf{x}) = (1 - \alpha)p(\mathbf{x}) + \alpha \tilde{p}(\mathbf{x})$ のような形を仮定できる( $\tilde{p}(\mathbf{x})$ はpと $p^\prime$ の差に対応する規格化条件を満たす関数)。これを使うと密度比は

$r(\mathbf{x}) = \frac{p(\mathbf{x})}{(1 - \alpha)p(\mathbf{x}) + \alpha \tilde{p}(\mathbf{x})} = \frac{1}{(1 - \alpha) + \alpha \frac{\tilde{p}(\mathbf{x})}{p(\mathbf{x})}}$

と表現できる。

正常なxに対しては $\frac{\tilde{p}(\mathbf{x})}{p(\mathbf{x})}$ が1より小さい値を取る
異常なxに対しては $\frac{\tilde{p}(\mathbf{x})}{p(\mathbf{x})}$ は1より大きな値を取る

↑より、以下のことが分かる。

正常なxに対しては密度比 $r(\mathbf{x})$ が大きな値を取る
異常なxに対しては密度比 $r(\mathbf{x})$ が小さな値を取る

また、密度比は $0 \leq r(\mathbf{x}) \leq \frac{1}{1 - \alpha}$ なので、 $\mathbf{x}^\prime$ に対する異常度は $\log (1 - \alpha) \leq a(\mathbf{x}^\prime) \lt \infty$ を満たす。実用上、異常標本の割合は1より圧倒的に小さいので、左辺は $- \alpha$ で近似でき(0周辺でテイラー展開)、これが異常度の近似的な下限となる。これより、異常度が $\alpha$ のオーダーより非常に小さい場合は異常が疑われる、ということになる。

ここで問題になることが1つあって、 $p(\mathbf{x})$ と $p^\prime(\mathbf{x})$ の推定には誤差が必ず含まれ、割り算によってその誤差が増幅されてしまうということ。今回欲しいのは異常度 $a(\mathbf{x}) = - \log r(\mathbf{x})$ であるから、個々の分布が分からなくても密度比が分かればそれでよい。バプニックの原理から密度比を直接的に求めていくことを考えよう。

カルバックライブラー密度比推定法

密度比を表わすモデルとして線形モデル

$r_{\boldsymbol\theta}(\mathbf{x}) = \sum_{j=1}^b \theta_j \phi_j(\mathbf{x}) = {\boldsymbol\theta}^T \boldsymbol\phi(\mathbf{x})$

を仮定する。ただし、 $\boldsymbol\phi(\mathbf{x})$ はb次元の非負値を取る基底関数、 $\boldsymbol\theta$ はb次元のパラメータである。このような仮定を入れると、密度比推定はパラメータ $\boldsymbol\theta$ の推定問題に落ちる。あとは、その目的関数を決めてやればよいが、以下のような基準を考えることができる。

パラメータ $\boldsymbol\theta$ は $r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x})$ が $p(\mathbf{x})$ にできるだけ近くなるように
$r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x})$ は非負値で規格化条件を満たす

これらを満たす基準として、非負関数fとgの情報理論的な距離を測る一般化カルバックライブラーダイバージェンス

$\mbox{gKL}(f||g) = \int f(\mathbf{x}) \log \frac{f(\mathbf{x})}{g(\mathbf{x})} d \mathbf{x} - (\int f(\mathbf{x}) - g(\mathbf{x}) d \mathbf{x})$

を考える(これの気持ちはよく分からない...)。fとgに $p(\mathbf{x})$ と $r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x})$ を代入すると

$\mbox{gKL}(p||r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x})) = \int p(\mathbf{x}) \log \frac{p(\mathbf{x})}{r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x})} d \mathbf{x} - 1 + \int r_{\boldsymbol\theta}(\mathbf{x}) p^\prime(\mathbf{x}) d \mathbf{x}$

となる。上の式の期待値を経験分布で近似して、定数項を無視すると、以下の目的関数の最小化を考えればよいことになる。

$J(\boldsymbol\theta) = - \frac{1}{|D|} \sum_{x \in D} \log r_{\boldsymbol\theta}(\mathbf{x}) + \frac{1}{|D^\prime|} \sum_{x \in D^\prime} r_{\boldsymbol\theta}(\mathbf{x})$

第一項は異常度の期待値なので、異常度の期待値を最小化したいということを表わしていて、第二項は規格化条件を表わしている。

なお、本では一般化カルバックライブラーダイバージェンスの最小化で定式化されているが、元の論文ではカルバックライブラーダイバージェンスに正規化項等を陽に制約に加えた最適化問題を解いているので、理解する分には制約付きのカルバックライブラーダイバージェンスの最小化と思って普通に問題ない。

パラメータの最適化

$J(\boldsymbol\theta)$ の最小化は凸最適化問題なので、勾配法などで求めることができる。基底関数は例えばRBFカーネルを使うことができる。RBFカーネルのバンド幅は交差検定によって求めることができる。

最小二乗密度比推定法

カルバックライブラー密度比推定法では目的関数を一般化カルバックライブラーダイバージェンスに置いたが、他の目的関数を置くことももちろんできる。ここでは最小二乗の考え方でやっていて、正則化項を付け加えても閉じた形でパラメータを求めることができる。閉じた形で表わせる分計算としては楽だが、KLダイバージェンスを最小化した場合で得られた解との性質の違いは後で抑えておきたい。