# 李宏毅_Anomaly Detection
###### tags: `Hung-yi Lee` `NTU` `Anomaly Detection`

## Anomaly Detection (1/7)
[課程連結](https://www.youtube.com/watch?v=gDp2LXGnVLQ)

異常偵測
### Problem Formulation

給定一系列的訓練資料${x^1...x^N}$，要找一個function，在輸入input-$x$的時候，判斷這個input與我們的訓練資料是否有類似。

也就是，當輸入$x$被判定為與訓練資料相似，那它就是正常的資料，反之則為異常資料。雖然課程以anomaly來命名，但實際上模型所找的是與訓練資料不相符的東西，但它不見得是異常。

符號約定：上標表示完整的資料，下標表示完整的資料內的某一個部份

註：其它地方也可能不是以anomaly稱呼，而是outlier，novelty，exceptions
### What is Anomaly?

至於到底什麼是Anomaly(異常)，這取決於你所給予機器的資料。

上圖給出三個直觀的案例：
1. 如果你的訓練資料都是雷丘，那皮卡丘就是異常
2. 如果你的訓練資料都是皮卡丘，那雷丘就是異常
3. 如果你的訓練資料都是神經寶貝，那數碼寶貝就是異常
### Applications

異常偵測的應用範圍很廣，舉例來說：
* 詐欺偵測(Fraud Detection)
* 訓練資料就是收集很多正常的交易行為，以此檢測交易是否為詐欺交易
* Ref: https://www.kaggle.com/ntnu-testimon/paysim1/home
* Ref: https://www.kaggle.com/mlg-ulb/creditcardfraud/home
* 網路系統入侵偵測(Network Intrusion Detection)
* 訓練資料就是正常的連線，以此檢測新的連線是否為攻擊行為
* Ref: https://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
* 癌細胞偵測(Cancer Detection)
* 訓練資料就是正常的細胞，以此檢測是否為癌細胞
* Ref: https://www.kaggle.com/uciml/breast-cancer-wisconsin-data/home
### Binary Classification?

直觀來看，似乎可以利用binary classifier來達成，只要你擁有正常資料做為一個類別，異常的資料做為另一個類別，就可以直接硬train一發達成。

但實務上卻沒有那麼容易，舉例來說，如果寶可夢是正常的資料，那非寶可夢的就通通是異常的資料，這難以窮舉，也導致你無法決定異常資料的分佈。再來就是，多數情況下，我們難以收集到很多的異常資料，而收集正常的資料反而是簡單的，這也造成異常偵測無法以二元分類問題來看待的原因。
### Categories

現在對異常偵測的問題做簡單的分類：
* 訓練資料擁有label，這可以訓練出classifier，讓機器知道什麼樣的資料對應什麼樣的$\hat{y}$
* 這邊的lable並不存在unknown，如果我們希望機器在看到沒見過的資料可以回應unknown的話，那這就是另一個屬於Open-set Recognition的問題
* 訓練資料皆無label，並且全部為正常資料
* 訓練資料皆無label，但資料混雜了一些異常資料
* 多數情況如此，無法保證手上的資料狀況

## Anomaly Detection (2/7)
[課程連結](https://www.youtube.com/watch?v=cYrNjLxkoXs)

### Example Application

這個案例主要判斷input的人物是否為辛普森家庭，而且每一個辛普森家庭的人物都有標記。

資料來源為kaggle上一個非常喜歡辛普森家庭的人，見[連結](https://www.kaggle.com/alexattia/the-simpsons-characters-dataset)，直接取用他的分類器來應用。
### How to use the Classifier

直接取用訓練好的分類器，input-x，而output除了類別-y之後還有它的置信度-c。

接著，我們定義一個threshold-$\lambda$，當置信度高於閥值，那就代表是辛普森家庭，如果低於閥值，那就代表不是辛普森家庭。
### How to use the Classifier

輸入影像經過分類器會得到一個機率分佈的輸出，以最高的那一個做為置信度來與閥值比較。
### How to use the Classifier

上面是李弘毅老師的實作結果，也可以確認，如果是辛普森家庭的人物所得的分數會比較高，但也發現到，如果非辛普森家庭的人物多伴會被分類到柯阿三，這有可能是因為柯阿三與普遍辛普森家庭的不同在於他不是黃臉，因此非黃臉的就通通被歸類於此。

### How to use the Classifier

上圖的上半部是多數的辛普森家庭經過分類器之後所得的置信度(測試資料集)，以分佈來看幾乎可以成功辨識。

上圖的下半部是課程上老師自己拿15,000張動漫照片~(那來那麼多張...)~下去測試，雖然有1,400張也被歸類為辛普森家庭，但也大約只有10%，多數照片都是得到較低的置信度~(信心分數)~。
### Outlook: Network for Confidence Estimation

[論文連結_Learning Confidence for Out-of-Distribution Detection in Neural Networks](https://arxiv.org/abs/1802.04865)

上面說的方法是用一個分類器直接給照片信心分數的回饋，另一種方法是直接讓`nn`輸出信心分數。

## Anomaly Detection (3/7)
[課程連結](https://www.youtube.com/watch?v=ueDlm2FkCnw)

### Example Framework

總結一下剛才說的部份：
* 有一個Simpsons家庭的訓練資料集-$x$
* 每一張照片都有標記-$\hat{y}$
* 訓練一個分類器，得到一個信心分數的輸出

另外，現在要談的是：
* 有一個訓練集以外的驗證集，這是拿來調整超參數使用
* 驗證集裡面應該有要"是辛普森家族的人物"與"不是辛普森家族的人物"
* 以此資料集計算效能，定義閥值，調整參數

確認超參數，訓練完畢之後就可以讓分類器上線，判斷是否來自辛普森家族。
### Evaluation

課程上用100張辛普森家族的照片(藍色)與5張非辛普森家族的照片(紅色)來評估模型效能。

異常偵測本身是一個二元分類的問題，這種情況下多數用正確率來衡量系統好壞，但這不一定是一個最好的衡量標準，會有這種問題是因為在異常偵測的問題中，其正常的資料與異常的資料量比例差異往往非常大~(範例上有100張正常，5張異常)~。

舉例來說，如果$\lambda$設置為0.3，那這個模型的正確率是高遠95.2%，因此在異常偵測的任務中我們並不會拿正確率來做衡量標準。
### Evaluation

如果各別以0.5、0.8來設置$\lambda$就可以得到上面表格的結果(左、右)，我們可以觀察FP、FN的樣本數變化。
### Evaluation

但兩個參數那一個比較好這必須取決於究竟是FP嚴重，還是FN嚴重。這可以用一個Cost Table來做衡量，兩者取其輕，而Cost Table的設置就取決於任務來決定。

## Anomaly Detection (4/7)
[課程連結](https://www.youtube.com/watch?v=XwkHOUPbc0Q)

### Possible Issues

雖然直接用分類器來做異常偵測是一個不錯的方法，但還是會遇到一些問題，以貓狗分類器為例。

假設一個分類器可以用來分類狗與貓，那如果輸入的是草泥馬還是馬來貘，那可能得到的置信度就很低，但如果是虎跟狼，就有可能會被分別分類到貓、狗那邊，這是因為虎、狼身上可能會有某一種的特徵讓機器誤以為牠們就是那個所屬類別。
### Possible Issues

回頭看之前所談的辛普森家族模型，將非辛普森家族的照片變黃之後，整個置信度就大大提升，很明顯的黃色是模型判斷是否為辛普森的一個重要關鍵。
### To Learn More ...

解決這個問題可以參考上面的文獻說明。

[Novelty Detection with GAN](https://arxiv.org/abs/1802.10560)
## Anomaly Detection (5/7)
[課程連結](https://www.youtube.com/watch?v=Fh1xFBktRLQ)

稍早的案例是有lable的情況，現在說明的是沒有lable的情況。
### Twitch Plays Pokemon

這是一個網路大家一起操作的遊戲，因此很容易讓人崩潰。

我們可以假設，多數的玩家都是想過關的，這是我們的正常的訓練資料，由多數玩家的行為來瞭解正常玩家的行為應該是怎麼樣的，以此偵測出異常玩家的行為。
### Problem Formulation

為此我們需要收集訓練資料，每一個玩家都是一筆資料-$x$，都以向量來表示，這在[git](https://github.com/ahaque/twitch-troll-detection)上是有相關資料可以下載。
### Problem Formulation

現在我們的手上有大量的$x$，但沒有$y$，因此沒有辦法用分類器來處理。但是我們可以先建立一個模型，這個模型是告訴我們$P(x)$的機率有多少，根據我們的訓練資料找出一個機率模型來回答我們某一個使用者的行為發生的機率有多少。如果大於閥值，那就是正常，低於閥值則為異常。
### Problem Formulation

假設每一個玩家都可以用二維向量來表示，那就可以將資料以圖示來表示。可以看的到，多數的玩家都喜歡在無政府狀態下發言。
## Anomaly Detection (6/7)
[課程連結](https://www.youtube.com/watch?v=LmFWzmn2rFY)

### Maximum Likelihood

我們還是希望可以將資料以數值化來表示，以決定玩家究竟是正常還是異常，這可以用likelihood的概念來處理。

我們有$N$筆資料，並且有一個probablity density function-$f_\theta(x)$，其中$\theta$是該function的參數，且$\theta$會決定這個probablity density function會長什麼樣子。

我們要計算likelihood，也就是根據目前我們手上的probablity density function，產出這樣子的資料分佈的機率有多大，即：
$L(\theta) = f_\theta(x^1) f_\theta(x^2) ... f_\theta(x^N)$

很明顯的，這個function是由$\theta$所控制，因此不同的$\theta$就會不同的probablity density function，也就會算出不同的likelihood。

但我們並不知道$\theta$，而我們想找的$\theta$是要能最大化likelihood，即：
$\theta^* = \arg \max_\theta L(\theta)$
### Gaussian Distribution

常用的probablity density function就是gaussian distribution。上面的數學式是一個multi variable gaussian distribution，簡單來看，這個function就是輸入向量-$x$，接著輸出這個輸入$x$被sample到的機率。

可以發現到，這個function是被$\mu$與$\Sigma$所控制，而這也是我們剛才所看到的$\theta$，也就是我們要找出來的參數。

因此我們可以將原本的數學式內的$\theta$以$\mu, \sigma$替換掉：
$L(\mu, \Sigma) = f_{\mu, \Sigma}(x^1)f_{\mu, \Sigma}(x^2) ... f_{\mu, \Sigma}(x^N)$

假設這個gaussian distribution的$\mu$在圖左上的藍框處，這意味著在附近的資料被sample到的機率是很高的，因為這是一個high density的區域，其所得的likelihood就會很大。但如果$\mu$是在圖中的藍框處，很明顯的計算所得的likelihood就會很小。

因此我們要做的就是，窮舉所有可能的$\mu, \sigma$來找出likelihood最大值的組合：
$\mu^*, \Sigma^* = \arg \max_{\mu, \Sigma} L(\mu, \Sigma)$

只要能夠找出$\mu^*, \Sigma^*$就可以找出產生這筆資料背後的distribution是長什麼樣子。雖然資料分佈來看可能不像是gaussian，但這個假設真的太常用了。

這部份在Machine Learning課程中已經有提過：
* $\mu^* = \dfrac{1}{N} \sum^N_{n=1} x^n$
* $\Sigma^* = \dfrac{1}{N} \sum^N_{n=1} (x-\mu^*)(x-\mu^*)^T$
### Gaussian Distribution

找出$\mu^*, \Sigma^*$就可以拿來做異常偵測，只要將輸入$x$帶入probablity density function，得到的output與閥值做比較，就可以判斷該輸入是正常還是異常，即是是沒有看過的輸入資料，只要帶入這個function就可以得到一個output與閥值比較。

可視化這個分佈的話可以看的到，愈往左上集中的機率是愈高的，也愈紅，也愈可能是正常，愈往外就可能愈是異常，而$\lambda$就是其中一條等高線。
## Anomaly Detection (7/7)
[課程連結](https://www.youtube.com/watch?v=6W8FqUGYyDo)

### More Features

使用機器學習的好處就是，你可以選擇加入更多的特徵來做判斷。然後再計算你的likelihood，取log是因為算出來的值比較小，因此取log。
### Outlook: Auto-encoder

也可以利用Auto-encoder來處理這個問題。這其它的課程有提過，可以參考。

因為訓練資料都只有看過辛普森家族的照片，因此能夠成功的還原影像資料，但如果今天給的是一個沒有看過的資料，那還原出來就會失敗，這是一個利用還原度判斷是否為異常的方法。
### More

上面給出其它異常偵測的方法。

[One-class SVM_Support Vector Method for Novelty Detection ](https://papers.nips.cc/paper/1723-support-vector-method-for-novelty-detection.pdf)