はじめに

この記事は，異常検知と変化検知を学ぶアドベントカレンダー2018 – Takala’s Memory の3日目の記事です．MLPシリーズの 「異常検知と変化検知」 の3章まとめとなります．

素人がoutput駆動の勉強用に書いています．不備や勘違いもあるかもしれません．差し支えなければ間違え等については，ご指摘・ご教授頂けると助かります．よろしくお願いします．

また，本記事において使用している図表はすべて，上記参考書を基にして作成したものです．

コンテンツ

• 独立変数モデル
• 迷惑メール判定

独立変数モデル

今回は，多次元データに対して各変数が独立であるという仮定のもとで構築される異常検知手法について示していく．多次元データを直接扱おうとすると直感的にも理解がしにくく，数式も複雑になる．しかしながら，各変数が独立と考えてしまえば，変数ごとに問題を切り分けることが可能となる．少し強引かもしれないが，仮定が必ずしも正しくなくとも異常度の大きさをおおよそ見積もることができるという点で非常に強力である．

独立変数モデルの構築と最尤推定

まず，これまでの議論と同様に，正常・異常ラベル$y$付きのデータ$M$次元の$N$個のデータ$\mathcal{D} = \left\{ (\boldsymbol{x}^{(n)},y^{(n)}) | n=1,2,…,N \right\}$を考えよう．ここで，正常データならば$y=0$，異常データならば$y=1$となる．

各変数(次元・軸)が独立であれば(独立と仮定するならば)，$\boldsymbol{x}$の条件付き確率分布$p(\boldsymbol{x}|y)$は以下のように表される．

$$
p(\boldsymbol{x}|y) = p(x_1|y)p(x_2|y)\cdots p(x_M|y) = \prod^{M}_{i=1}p(x_i|y)
$$

次に，$x_i$の条件付き確率分布はパラメータベクトル$\boldsymbol{\theta}^{y}_i$で表されるなんらかの確率分布$p(x_i|\boldsymbol{\theta}^{y}_i,y)$であると考えよう．ここで，確率分布は一般的に複数のパラメータで表される(*1)のでパラメータベクトルとして定義している．また，正常データ・異常データごとに従う確率分布が異なると考えているため両者を区別するために添え字$y$が付いている．

このとき，訓練データ$\mathcal{D}$を利用してパラメータの最尤推定量を考える．

対数尤度関数は：

$$
\begin{align}
L(\boldsymbol{\Theta}|\mathcal{D}) &= \sum_{n=1}^{N} \sum_{i=1}^{M} \ln p(x_i^{(n)} | \boldsymbol{\theta}_i^{y},y^{(n)} )
\\
&= \sum_{i=1}^{M}
\left\{
\sum_{n \in \mathcal{D}^1} \ln p(x_i^{(n)} | \boldsymbol{\theta}_i^{1}, y=1)
+
\sum_{n \in \mathcal{D}^0} \ln p(x_i^{(n)} | \boldsymbol{\theta}_i^{0}, y=0)
\right\}
\end{align}
$$

となる．ここで，$\mathcal{D}^0$は正常標本集合，$\mathcal{D}^1$は異常標本集合である．左辺の$\boldsymbol{\Theta}$は，すべてのパラメータ$\boldsymbol{\theta}^y_i$を便宜的にまとめて表記したベクトルである．

各変数が独立であるということは，各変数(各軸)の確率分布間に相関がないことを示している．つまり，$\boldsymbol{\theta}^y_i$は互いに(異なる$i$同士で)関数関係にない．まあ，なにが言いたいかというと，対数尤度関数を$\boldsymbol{\theta}^y_i$で偏微分したときに残るのは$p(x^{(n)}_i|\boldsymbol{\theta}^{y}_i,y^{(n)})$に関係する項だけということである．

例えば，$\boldsymbol{\theta}^1_i$の最尤解を与える条件は，

$$
\boldsymbol{0}
= \frac{\partial L}{\partial \boldsymbol{\theta}_i^1}
= \frac{\partial}{\partial \boldsymbol{\theta}_i^1}
\sum_{n \in \mathcal{D}^1} \ln p(x_i^{(n)}|\boldsymbol{\theta}_i^{1},y=1)
$$
となる．独立と仮定しているのだから，まあ当たり前ですよね．

このように変数同士を独立みなして議論する方法を単純ベイズ法と呼ぶ．

独立変数モデルにおけるホテリングの$T^2$法

変数の独立性を仮定するモデルはラベルなしの場合にも考えることができる．

$M$次元の$N$個の観測値からなるラベルなしの訓練データ$\mathcal{D} = \left\{ \boldsymbol{x}^{(n)} | n=1,2,…,N \right\}$を考える．

これに対して，各変数が独立であるという仮定のもと，2章で学んだホテリングの$T^2$法を適用する．このとき，各変数が独立であるという仮定は，分散共分散行列の非対角項がすべて$0$であるということを意味している．

詳細な式展開は割愛するが，最終的に異常度$a(\boldsymbol{x}’)$は

$$
a(\boldsymbol{x}’) = \sum^{M}_{i=1} (\frac{x_i’-\hat{\mu_i}}{\hat{\sigma_i}})^2
$$

となる．ここで，$\hat{\mu_i},\hat{\sigma_i}$はそれぞれ各変数(各軸)ごとの標本平均と標準偏差である．この式は，多次元データの異常度は各次元の異常度の線形和の形で表されると主張している．行列計算などが不要なので，使い勝手がよさそうである．

多項分布による単純ベイズ分類

ホテリングの$T^2$法では，対象とする観測量が正規分布に従うことを仮定していた．本章では，観測量が多項分布に従うと仮定した場合について考えていく．一般的になにかの頻度は多項分布に従うとされることが多い(*2)．今回は迷惑メールの振り分け問題を例に，多項分布による単純ベイズ分類を考える．このとき観測量はメール内の各単語の数(出現頻度)ということになる．

メールを多項分布で表現する

具体的に手順を見ていこう．

まず，あるメールを単語の出現頻度ベクトルで表すことを考える．この世に存在する単語を$M$個列挙し，各メール内に現れるその単語の出現数が，そのメールの特徴量を示すことになる．数学的にはメール$\boldsymbol{x}$は$M次元$ベクトルで

$$
\boldsymbol{x} = [0,0,0,0,1,0,2,5,0,0,…]^{\mathsf{T}} \qquad \in \mathbb{R}^{M}
$$

といった形で表現される，各要素の値が，メール中の単語数を表している．

こうして，数学的に表現されたメール$\boldsymbol{x}$を以下に示す多項分布でモデリングする．これは，各単語の出現確率$\theta_{i}$を用いると
$$
\mathrm{Mult}(\boldsymbol{x}|\boldsymbol{\theta})=
\frac{(x_1 + \cdots + x_M)!}{x_1!x_2! \cdots x_M!} \theta_{1}^{x_1} \cdots \theta_{M}^{x_M}
$$
と表現される．二項分布の拡張ということが一目でわかる．

多項分布の最尤推定

モデル(確率分布)のパラメータを例のごとく，最尤推定により求める．ここですべてのメール(訓練データ)には迷惑メールかどうかのラベル$y$が付与されているとする(*3)．

具体的には，$\mathrm{Mult}(\boldsymbol{x}|\boldsymbol{\theta}^0)$，$\mathrm{Mult}(\boldsymbol{x}|\boldsymbol{\theta}^1)$という2つのモデルを仮定し，そのパラメータ$\boldsymbol{\theta}^0$，$\boldsymbol{\theta}^1$を最尤推定する．

これは，以下の最適化問題を解くことに等しい．

$$
\begin{align}
\max_{\boldsymbol{\theta}^0,\boldsymbol{\theta}^1} \qquad
&L(\boldsymbol{\theta}^0,\boldsymbol{\theta}^1 | \mathcal{D}) =
\sum_{n \in \mathcal{D}^1} \sum_{i=1}^{M} x_i^{(n)} \ln \theta_i^1
+
\sum_{n \in \mathcal{D}^0} \sum_{i=1}^{M} x_i^{(n)} \ln \theta_i^0
+
C
\\
\mbox{s.t.} \qquad
&\sum_{i=1}^{M} \theta_i^1 = 1
\\
&\sum_{i=1}^{M} \theta_i^0 = 1
\end{align}
$$

ここで目的関数は，対数尤度関数であり，$C$は決定変数に依存しない定数を表している．これは最適化問題の超有名解法ツール，ラグランジュ法により簡単に解くこと可能である．

結局，最適値(最尤推定量)は以下となる．

$$
\hat{\theta^1_i} = \frac{\sum_{n \in \mathcal{D}^1}^{N} x_i^{(n)}}{\sum_{j=1}^{M} \sum_{n \in \mathcal{D}^1}^{N} x_j^{(n)}}
$$
$$
\hat{\theta^0_i} = \frac{\sum_{n \in \mathcal{D}^0}^{N} x_i^{(n)}}{\sum_{j=1}^{M} \sum_{n \in \mathcal{D}^0}^{N} x_j^{(n)}}
$$

つまり，結局のところ
$$
\hat{\theta^1_i} = \frac{\mathcal{D}^1\mbox{における単語$i$の出現総数}}{\mathcal{D}^1\mbox{における全単語の出現総数}}
$$
$$
\hat{\theta^0_i} = \frac{\mathcal{D}^0\mbox{における単語$i$の出現総数}}{\mathcal{D}^0\mbox{における全単語の出現総数}}
$$
ということになる．これは「まあ，うん，だろうね」という結果ですよね．標本平均がそのまま最尤推定量になっているというイメージですね．

ただこのような手法を採用すると，訓練データに1回もあらわれない単語のパラメータが0になってしまうという，少しめんどくさいことが起こる．そのため，実用的には単語の出現頻度に少し「ゲタ」をはかせるらしい．本記事では詳しく説明しない(*4)が，頭の片隅にいれておいた方がよさそう．

迷惑メール判定

ここまでで，モデル(確率分布)を作成しそのパラメータを求めることができたので，最後の異常判定のステップを示す．

新規のメール$\boldsymbol{x}’$の異常度は

$$
a(\boldsymbol{x}) = \sum^{M}_{i=1} x’_i \ln \frac{\hat{\theta}^1_i}{\hat{\theta}^0_i}
$$

となる．各$i$について，$\alpha_i = \hat{\theta}^1_i / \hat{\theta}^0_i$とパラメータを作っておくと，結局$a(\boldsymbol{x}) = \boldsymbol{\alpha}^{\mathsf{T}} \boldsymbol{x}’$と簡潔に書くことが可能である．最終的に，この異常度$\boldsymbol{x}’$と閾値の大小で異常判定(迷惑メール)判定を行う．

この一連の流れは参考書p35に，単純ベイズ分類による迷惑メール判定アルゴリズムとして整理されている．

また，参考書3.5節には，二値分類と異常検知の関係性として，ネイマン・ピアソン決定則とベイズ決定則について触れられている．

コメント

• 多次元データの各変数が独立と仮定すると，数学的にかなり見通しがよくなると思った
• 実務的には，独立になるように変数を選べばよいのかもしれない
• そもそも相間が強い変数を多くいれても，情報量はそんなに増えないはず
• 迷惑メール判定アルゴリズムについては自分で作れそう！というぐらい理解できたの嬉しい

注釈

(*1) : 正規分布の場合であれば，平均と分散のふたつのパラメータが必要．ポアソン分布は$\lambda$ひとつだね．

(*2) : 多項分布はもちろん二項分布の拡張と考えて差し支えない．二項分布の代表としてはコイントスがよく例にあげられる．多項分布の場合は，確率変数のとりうる値が2値(コインだと表裏)に限らない，有限個の値を考えている．

(*3) : 結局ラベル付きの話なる．まあ，迷惑メール判別を教師なしでやるのは難しいでしょうね．迷惑メールの方がむしろ多いから，外れ値検出ができなさそう．

(*4) : 参考書には丁寧な解説があるよ．

2