近傍法による異常検知
Keywords：
- $k$近傍法 (k-neighbor method)
- マージン最大化近傍法 (Large-margin nearest neighbors)
4.1 k近傍法：経験分布に基づく異常判定
- 経験分布(empirical distribution)を使った異常検知
- ラベルありデータ
- ラベルなしデータ
の2パターンを考える
4.1.1 ラベルなしデータに対するk近傍法
経験分布
p_{emp}(\boldsymbol{x}\ |\ D) = \frac{1}{N}\sum_{n=1}^{N}\delta(\boldsymbol{x} - \boldsymbol{x}^{(n)})
- データ点$\ \boldsymbol{x}^{(n)}\ $と一致する$\ \boldsymbol{x}\ $でのみ値をもち，その他の$\ \boldsymbol{x}\ $では0になる．
十分小さい半径$\epsilon$の球（イプシロンボール）の中で，確率密度一定だと考えると，
p(\boldsymbol{x'}) \times |V_M(\epsilon, \boldsymbol{x'})| \approx \int_{\boldsymbol{x} \in V_M(\epsilon,\boldsymbol{x'})} d\boldsymbol{x}\:p_{emp}(\boldsymbol{x}\ |\ D) = \frac{k}{N}
\Longrightarrow \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p(\boldsymbol{x'}) \approx \frac{k}{N\ |V_M(\epsilon, \boldsymbol{x'})|} \propto \frac{k}{N\epsilon^M}
異常度の定義 式(1.4)
a(\boldsymbol{x'}) = -\ln p(\boldsymbol{x'}\ |\ D)
より
a(\boldsymbol{x'}) = -\ln p(\boldsymbol{x'}) = - \ln k + M\ln\epsilon + (定数)
- $\epsilon$を固定すれば，$k$が小さいほど高い異常度 ($\epsilon$近傍法)
- $k$を固定すれば，$\epsilon$が大きいほど高い異常度 ($k$近傍法)
思ったこと：$\epsilon$近傍法だと異常値が$k$によって決まるため，異常度が離散値になる．似たような手法だが$k$近傍法の方が扱いやすいのではないかと思った．
-
メリット:
- 分布が多峰性を持っていても使える（ホテリング$T^2$では正規分布を仮定）
-
デメリット:
- 多峰性があった場合，データの粗密や広がりの違いにより，
- 次元が高くなると，個々の変数の寄与がかき消される傾向
-
対策:
- 特徴量を吟味する
- 距離尺度の最適化を行う(4.2章)
- 明示的に混合モデルを学習する(５章)
4.1.2 ラベルつきデータに対するk近傍法
ここでは，異常標本と正常標本のラベルがあるデータに対してのk近傍法を述べる
近傍数$k$を与えて，近傍標本を選びラベルを確認する．異常ラベルの近傍標本の数を$N^1(\boldsymbol{x'})$, 正常ラベルの近傍標本の数を$N^0(\boldsymbol{x'})$とすると，
p(y = 1 |\ \boldsymbol{x'}, D) = \frac{N^1(\boldsymbol{x'})}{k}
p(y = 0 |\ \boldsymbol{x'}, D) = \frac{N^0(\boldsymbol{x'})}{k}
ベイズの定理より
p(\boldsymbol{x'}\ |\ y=0, D) = \frac{p(y=0\ |\ \boldsymbol{x'},D)p(\boldsymbol{x'})}{p(y=0)} = \frac{p(\boldsymbol{x'})}{k}\frac{N^0(\boldsymbol{x'})}{\pi^0}
p(\boldsymbol{x'}\ |\ y=1, D) = \frac{p(y=1\ |\ \boldsymbol{x'},D)p(\boldsymbol{x'})}{p(y=1)} = \frac{p(\boldsymbol{x'})}{k}\frac{N^1(\boldsymbol{x'})}{\pi^1}
異常度
a(\boldsymbol{x'}) = \ln\frac{p(\boldsymbol{x'}\ |\ y = 1, D)}{p(\boldsymbol{x'}\ |\ y = 0,D)} = \ln\frac{\pi^0N^1(\boldsymbol{x'})}{\pi^1N^0(\boldsymbol{x'})}
- $\pi_1$は全標本に対する異常標本の割合
- $\pi_0$は全標本に対する正常標本の割合
訓練
決めるパラメータは近傍数kと異常判定の閾値$a_{th}$．一つ抜き交差確認法(1.4節)によって，kと$a_{th}$の組からベストなものを選んでいく．まずはユークリッド距離で精度を評価し，不十分な場合は距離の計算方法を変更するのがよい．手法としては，
- 局所外れ値度 (local outlier factor, (LOF)) (姉妹書参照)
- 計量学習（次節）
があげられる．
4.2 マージン最大化近傍法
計量について
実際の空間の距離を計算するときは，あまり意識しないが，次元の異なる変数同士の距離をユークリッド距離で計算するには注意が必要．
例えば，身長と体重
身長170cm, 体重50kgのデータと身長171cm,体重50kgのデータ間のユークリッド距離は1
身長170cm，体重51kgのデータとのユークリッド距離も1
身長をmmに変えると？
前者の距離は10
後者の距離は1
変数の測り方によって，距離は変わり得るので，目的に即した距離(計量)を使うことが必要．今回は多くの分類問題において安定した性能を発揮するマージン最大化近傍法を紹介する．
4.2.1 計量学習とは
ユークリッド距離に代わり，$M \times M$の半正定値行列$\boldsymbol{A}$を使って，２つの標本間の距離の2乗を以下のように定義する．
d_A^2(\boldsymbol{x'},\boldsymbol{x''}) = (\boldsymbol{x'} - \boldsymbol{x''})^{T}\boldsymbol{A}(\boldsymbol{x'} - \boldsymbol{x''})
- Aをデータから学習する手法を計量学習(metric learning)と呼ぶ．
- リーマン幾何学では行列Aに対応するものを計量テンソルやリーマン計量と呼ぶ．
- Aを単位行列におきかえれば，普通のユークリッド距離になる．
マージン最大化近傍法では，空間の伸縮・回転を組み合わせて，異常・正常の標本が上手く分かれるように空間の計量を学習していく．
考える条件は
- 同一ラベルの標本を密集させる
- 異なるラベルの標本をできるだけ引き離す．
4.2.2 マージン最大化近傍法の目的関数
上の二つの条件を目的関数に落としこむ．
- 同一ラベルの標本を密集させる
\psi_1^{(n)}(\boldsymbol{A}) \equiv \sum_{i \in N^{(n)}} d_A^2(\boldsymbol{x}^{(n)}, \boldsymbol{x}^{(i)})
をなるべく小さくすること
- 標本$\boldsymbol{x'}$に対するk個の近傍標本との距離の2乗の和をとったもの
- 異なるラベルの標本をできるだけ引き離す
\psi_2^{(n)} \equiv \sum_{j \in N^{(n)}}\sum_{l=1}^N I[y^{(l)} \neq y^{(n)}]\left[ 1 + d_A^2(\boldsymbol{x}^{(n)}, \boldsymbol{x}^{(j)}) - d_A^2(\boldsymbol{x}^{(n)}, \boldsymbol{x}^{(l)})\right]_+
を小さくすること
- I[]はラベルが異なる標本の時だけ1をとる
- マージンを踏み込んできたものだけ，計算すればよい．
- $[]_+$は中身が正のときだけ，そのまま値を返し，負の時は0を返す関数
まとめると，リーマン計量$\boldsymbol{A}$を求めるための最適化問題は，
\Psi(\boldsymbol{A}) \equiv \frac{1}{N} \sum_{n=1}^{N} \left[(1-\mu)\psi_1^{(n)}(\boldsymbol{A}) + \mu\psi_2^{(n)}(\boldsymbol{A}) \right] \Longrightarrow 最小化 subject\ to\ \boldsymbol{A} \succeq 0
に帰着する．
- $\mu$は条件１と条件２の相対的な重みのパラメータだが，多くの問題において$\mu = 0.5$と決めても問題ない．
4.2.3 勾配法による最適化
勾配法により最適化する．
- 目的関数の勾配を計算し，目的関数が小さくなる方向にパラメータを更新する．
- $\eta$が大きいほど，大胆に更新．
\boldsymbol{A} \leftarrow \boldsymbol{A} - \eta\frac{\partial\Psi(\boldsymbol{A}}{\partial\boldsymbol{A}}
勾配の計算は，「容易に得られる」，とあるが．．．
\frac{\partial \Psi(\boldsymbol{A})}{\partial \boldsymbol{A}} = \frac{1}{N}\boldsymbol{X}\boldsymbol{C}\boldsymbol{X}^T
ここで
\boldsymbol{C} \equiv \sum_{n=1}^{N}\sum_{j \in N^{(n)}} \left\{ \{(1-\mu)\boldsymbol{C}^{(n,j)} + \mu\sum_{l\in N_{n,j}}(\boldsymbol{C}^{(n,j)} - \boldsymbol{C}^{(n,l)}) \right\}
4.2.4 確率モデルとの関係
マージン最大化近傍法
「異なるラベルを持つ標本間の平均的なマージンを最大化する」と解釈できる．
マージン最大化近傍法は，確率モデルの観点から解釈することが可能
任意の標本$\boldsymbol{x}^{(n)}$の近傍に，正規分布に似た確率分布を考える
p(\boldsymbol{x}\ |\ \boldsymbol{x}^{(n)}, y^{(n)}) = \frac{1}{Z_n(\boldsymbol{A}, \sigma)} \exp\left\{-\frac{1}{2\sigma^2}d_A^2(\boldsymbol{x},\boldsymbol{x}^{(n)})\right\}
データDに基づく↑の分布はの尤度は，$\boldsymbol{x}^{(n)}$に対する同一ラベルの近傍標本を使って，
\prod_{i \in N^{(n)}}\frac{1}{Z_n(\boldsymbol{A},\sigma)}\exp\left\{-\frac{1}{2\sigma^2}d_A^2(\boldsymbol{x}^{(i)}, \boldsymbol{x}^{(n)})\right\}
全体の対数尤度は，
L(\boldsymbol{A}\ |\ D) = -\frac{1}{2\sigma^2} \sum_{n=1}^{N}\sum_{i \in N^{(n)}} d_A^2(\boldsymbol{x^{(i)}}, \boldsymbol{x}^{(n)}) - kN\ln Z_n(\boldsymbol{A},\sigma)