『異常検知と変化検知』の1-3章（基礎）要点まとめ

* 読んだ本：[異常検知と変化検知](https://www.amazon.co.jp/dp/B018K6C99U)
* 本には、コレに加えて↓が書いてある
    * 定理の証明や、使う式の導出


# 目的

後から要点を参照できるようにしておく


# 内容

## 第1章：異常検知・変化検知の基本的な考え方

* 異常検知・変化検知の種類
    * 外れ値検知(outlier detection)、変化検知(change detection)（=変化点検知(change-point detection)）、異常部位検知(discord discovery)


### 異常度

#### ラベル付きデータ

* データ数：$N$
* データ：$D = \bigl( (\boldsymbol{x}^{(1)}, y^{(1)}), (\boldsymbol{x}^{(2)}, y^{(2)}), \cdots , (\boldsymbol{x}^{(N)}, y^{(N)}) \bigr) $
* データの特徴量：$\boldsymbol{x}^{(n)}$
* データのラベル：$y^{(n)}$（正常な場合は0、異常な場合は1になる）
* 条件付き分布：$p(\boldsymbol{x} | y)$（$y$が決まったとき、$\boldsymbol{x}$に対する確率密度。データ$D$から作る。作り方は後述）

とすると、**異常値（anomaly score）**は以下のようになる。

```math
a(\boldsymbol{x}') = \ln \frac{p(\boldsymbol{x}' | y=1)}{p(\boldsymbol{x}' | y=0)}
```

* ここでは、確率分布の比＝密度比（density ratio）＝尤度比（likelihood ratio）で異常度を定義している
    * 「$y=1$（異常）の場合の$\boldsymbol{x}'$になりやすさ」と「$y=0$（正常）の場合の$\boldsymbol{x}'$になりやすさ」を比較してる
* コレがある値を超えたら$y=1$（異常）と判定する（ネイマン・ピアソン決定則(Neyman-Pearson decision rule)）


#### ラベルなしデータ

* データ数：$N$
* データ：$D = \bigl( \boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}, \cdots , \boldsymbol{x}^{(N)} \bigr) $
* データの特徴量：$\boldsymbol{x}^{(n)}$
* 条件付き分布：$p(\boldsymbol{x} | D)$（データ$D$から作る、$\boldsymbol{x}$に対する確率密度。）

とすると、**異常値（anomaly score）**は以下のようになる。

```math
a(\boldsymbol{x}') = - \ln p(\boldsymbol{x}' | D)
```

* 情報理論におけるシャノン情報量（Shannon information）
    * $\boldsymbol{x}'$が珍しい
    * = $\boldsymbol{x}'$になりやすさが小さい
    * = $p(\boldsymbol{x}' | D)$が小さい
    * = 異常度$a(\boldsymbol{x}')$が高い
    * = 情報量が高い


### 検知器の性能評価

* 確認法
    * 交差確認法（cross validation）
        * 全体の1/N個を検証データ、残りを訓練データに分ける
        * 訓練データで学習し、検証データで性能を評価する
        * 検証データを変えて、N回繰り返す
    * 1つ抜き交差確認法（leave-one-out cross validation）
        * ↑を、検証データを1個、残りを訓練データとして行う
* 異常検知での注意点
    * **ほとんどの場合で（正常標本の数）＞＞（異常標本の数）になる**
    * 何がマズイのか？
        * 全体に対しての正解率だけ見ると、欲しい性能を評価しきれない
        * 例：データが1,000個あって異常が1個だけのとき、「全部正常と判定する」検知器が正解率99.9%になる。しかし、この検知器では異常は検出できない
* 精度
    * 精度 (Accuracy)、適合率 (Precision)$r_0$、再現率 (Recall)$r_1$、F値 (F-Measure)あたりの話
* ROC曲線、AUC
    * ROC曲線 (receiver operating characteristic curve)
        * $(x, y) = (1-r_0, r_1)$を、異常判定の閾値を変化させてプロットした曲線
    * AUC (area under curve, 曲線下部面積)
        * ROC曲線の下側面積
        * 大きいほど良い検知器


## 第2章：ホテリングのT2法による異常検知

### 多変量正規分布の最尤推定

* $M$次元の$N$個のデータ$D$を考える
    * $D = \bigl( \boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}, \cdots , \boldsymbol{x}^{(N)} \bigr) $
* ホテリングの$T^2$法の前提
    * データ$D$が異常標本を含まないか、含んでいたとしても圧倒的に少数である
* 各標本が、独立に以下の確率密度関数（正規分布、ガウス分布）に従うと仮定する
    * $\boldsymbol{\mu}$：平均
    * $\Sigma$：共分散行列
    * $\Sigma^{-1}$：共分散行列の逆行列 = 精度行列。しばしば$\Lambda$で表される

```math
N( \boldsymbol{x} | \boldsymbol{\mu} , \Sigma) \equiv \frac{ |\Sigma|^{-1/2} }{ (2\pi)^{M/2} } exp \bigl( - \frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu})^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}) \bigr)
```

$\mu$, $\Sigma$をデータ$D$から求めるには、最尤推定を使う。$N$個のデータの対数尤度$L(\mu, \Sigma | D)$は以下のようになる

```math
\begin{align}
L(\mu, \Sigma | D) &= \ln \prod_{n=1}^{N} N( \boldsymbol{x}^{(n)} | \boldsymbol{\mu} , \Sigma) \\
&= \sum_{n=1}^{N} \ln N( \boldsymbol{x}^{(n)} | \boldsymbol{\mu} , \Sigma) \\
&= - \frac{MN}{2} \ln (2\pi) - \frac{N}{2} \ln |\Sigma| - \frac{1}{2} \sum_{n=1}^{N} \bigl( (\boldsymbol{x}^{(n)} - \boldsymbol{\mu})^T \Sigma^{-1} (\boldsymbol{x}^{(n)} - \boldsymbol{\mu}) \bigr) \\
\end{align}
```

これを最大にするような$\boldsymbol{\mu}$, $\Sigma$を$\hat{\boldsymbol{\mu}}$, $\hat{\Sigma}$とすると、以下のようになる

```math
\begin{align}
\hat{\boldsymbol{\mu}} &= \frac{1}{N} \sum_{n=1}^{N} \boldsymbol{x}^{(n)} \\
\hat{\Sigma} &= \frac{1}{N} \sum_{n=1}^{N} (\boldsymbol{x}^{(n)} - \hat{\boldsymbol{\mu}}) (\boldsymbol{x}^{(n)} - \hat{\boldsymbol{\mu}})^T \\
\end{align}
```

### マハラノビス距離とホテリングのT2法

* マハラノビス距離
    * 変数ごとの分散、相関を加味した距離
    * 「バラつきが大きい方向には、多少変動があっても小さく」「バラつきが小さい方向には、変動があると大きく」出てくる

```math
a(\boldsymbol{x'}) = (\boldsymbol{x'} - \hat{\boldsymbol{\mu}})^T \hat{\Sigma}^{-1} (\boldsymbol{x'} - \hat{\boldsymbol{\mu}})
```

各変数の相関が弱いとき、↓のようになる

```math
a(\boldsymbol{x'}) = \sum_{n=1}^{N} ( \frac{x_i - \hat{\mu}_i }{ \sigma_i } )^2
```

* ホテリングの$T^2$法
    1. $\boldsymbol{x'} - \hat{\boldsymbol{\mu}}$は、平均$\boldsymbol{0}$、共分散$\frac{N+1}{N} \Sigma$の$M$次元正規分布に従う.
    2. $\hat{\Sigma}$は、$\boldsymbol{x'} - \hat{\boldsymbol{\mu}}$と統計的に独立である.
    3. 統計量$T^2 \equiv \frac{N-M}{(N+1) M} a(\boldsymbol{x'})$は、自由度$(M, N-M)$の$F$分布に従う.
    4. $N >> M$の場合は、$a(\boldsymbol{x'})$は、近似的に自由度$M$、スケール因子1のカイ二乗分布に従う. **(実用上は、コレが成り立つことが多い)**
* 精度よい異常検知のためには、なるべく変数を絞った変数の部分集合ごとに$T^2$を計算するのがよい
    * =事前の**特徴量の吟味**(feature engineering)が必要

## 第3章：単純ベイズ法による異常検知

* $M$次元の変数を持つ$N$個のデータの異常検知を考える
* 単純ベイズでは、変数ごとに問題を切り分ける
    * 多次元の問題を１次元に帰着する
    * 変数1つずつで独立の確率分布を考え、全部掛けたものを使う
    * 変数同士の相関関係などは考えない
    * [コッチ](https://qiita.com/kazuya_minakuchi/items/c3a0066e90cfdfc8a859)でも一応まとめてる

```math
p(\boldsymbol{x} | y) = p(x_1 | y) p(x_2 | y) \cdots p(x_M | y) = \prod_{i=1}^{M} p(x_i | y)
```

* 「BOW(bag-of-words)での迷惑メール振り分け例」「事前分布とベイズの定理使っての、事後分布算出」あたりは割愛

### 二値分類と異常検知

二値分類に一般的に使われるベイズ決定則は↓

```math
\begin{align}
& \quad \ln \frac{p(y=1 |\boldsymbol{x})}{p(y=0 |\boldsymbol{x})} > 0 \\
\Rightarrow & \quad p(y=1 |\boldsymbol{x}) > p(y=0 |\boldsymbol{x}) \\
\Rightarrow & \quad y = 1と判定
\end{align}
```

* これは、ネイマン・ピアソン決定則の閾値を0に設定したものと同じ
* 異常検知では検知器の異常標本精度（再現率）も考えて閾値をカスタマイズする