---
disqus: ierosodin
---

# Classification

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `machine learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Machine_Learning)==

## Confusion matrix

在解釋 classification 前，先介紹一個評估分類好壞的方法，從下表中可以看到，我們可以將分類的狀況分成四大類：

| | 實際 yes | 實際 no |
| :---: | :---: | :---: |
| 預測 yes | TP (true positive) | FP (false positive) |
| 預測 no | FN (false negative) | TN (true negative) |

而分類的好壞由兩個指標來決定：
sensitivity：在所有真實為 true 的情況中，有多少被判斷出來，也就是 ${\frac{TP}{TP\ +\ FN}}$，也有人稱之為 TPR (true positive rate)。
specificity：在所有真實為 false 的情況中，有多少被判斷出來，也就是 ${\frac{TN}{FP\ +\ TN}}$，另一個相對的指標為 FPR (false positive rate)，其值與 specificity 互補。

如果只有一個指標高，不代表分類就是分得好，可以想像當所有的分類結果都是 positive，則 sensitivity 一定很高，單相對的，specificity 則可能很低，因此我們必須有一個數值或是方法，來評估怎樣的分類是好的。

## ROC space and ROC curve

ROC curve 是可以用肉眼就看出分類的準確性的圖，X 軸是偽陽性率 (false positive rate)，而 Y 軸為真陽性率 (true positive rate)，可以發現，當一個分類的結果越接近左上角時，則這個分類越好，反之，越接近右下角，則代表大部分的分類結果都是錯誤的，又稱為反指標（從另一個角度思考，其實也代表都分出來了，只是 label 相反）。


對比 ACC，也就是 ${\frac{TP\ +\ TN}{TP\ +\ FN\ +\ FP\ +\ TN}}$，當圖中的點越接近左上角時，ACC 趨近於 1，當點越接近右下角時，則 ACC 趨近於 0，實際上最差的分類結果為 ACC = 0.5

## 從 Regression 到 classification

在前面章節介紹的方法中，其實已經介紹過 classification 了，無論是 Naive bayes classifier 或是到後面的 Gaussian distribution， 都是利用對每一個 label 進行機率的計算得到所屬的類別，而機率相等的地方，其實就是 decision boundary。


那有沒有甚麼方法是直接用來求 decision boundary 的呢？其實 classification 的問題也是一種 regression。

### one-coding

回想前面的 LSE，當今天的結果換成是 input 的類別 label時，就變成 classify 的問題了，觀察下圖，我們將體重作為分類的依據，男生的 label 為 1，女生則為 0，利用 LSE 求得直線，則 ${y\ =\ 0.5}$ 的地方，即為 decision boundary。


然而這種方法有一個最大的缺點，當資料群中出現極端值時，為了使 MSE 最小，而會導致分類結果錯誤：


### one-k-coding

其實只是把 one-coding 推廣到多個類別，也就是每一次將一個類別的 label 設為 1，其他則為零，找出該分類的 ${w_i}$，重複對每一個類別做一次，因此需要進行 ${\left(\begin{array}{c}
k \\
2\end{array}\right)}$ 次計算。

當今天有一個點 x 要進行分類時，只要找出 ${arg max(w_ix)}$，即為分類結果。

同樣，我們也可提升到多維的空間，將 ${x}$ 轉換為 ${\phi (x)}$，利用類似的方法，找出每一類別的 decision boundary。

這類的方法都會受到極端值的影響，導致 decision boundary 的偏移。

### Perceptron

為了解決極端值的問題，我們可以思考，今天如果一個點的分類已經正確了，其實我們並不需要在乎這個點離 decision boundary 有多遠，也就是說應該給予相同的權重。

perception 會根據輸入 data 進行判斷，並只會提供 Yes or No 兩種輸出結果，下圖為示意圖，將 input data 經過 Xw 後，若值超過一個 bound（通常都是設為 0），輸出為Yes(1)，否則輸出 No(0)。


然而這種 activation function 是不可微的，所以如果想要用 gradient decent 的方式進行迭代，必須做些修正：

假定我們的參數為 ${w}$，而 Gradient descent 的式子為：
${w_{n+1}\ =\ w_n\ +\ \nabla f(a_n)}$

其中，${f(a_n)\ =\ Xwt \\
\Rightarrow\ \nabla f(a_n)\ =\ Xt}$

我們只有在當預測失敗時，才需要對 ${w}$ 進行更新，而 ${t}$ 則依照實際的結果而不同，若預測失敗，而實際的結果為 yes 時，則 ${t\ =\ 1}$，反之若實際的結果為 no 時，則 ${t\ =\ 0}$。

> 可以想像，當實際結果為 yes 卻預測失敗時，代表預測出來的值小於 boundary，因此 ${w}$ 需要增加，反之實際結果為 no時，代表預測出來的值大於 boundary，需要減少 ${w}$。

下圖為迭代過程的範例：

起始：

第一次迭代：

第二次迭代：

第三次迭代：

第 N 次迭代：

### Logistic regression

因為 perceptron 不可微，我們希望找到近似於 activate
function 的函數，也就是 sigmoid function。

回想前面的 Gaussian distribution，其特性為當值在 mean 附近時，相對於其他地方會相當的高，因此其 CDF 函式就相當類似我們所想要找的 function：${\frac{1}{2}\left(1\ +\ erf(\frac{x-\mu}{\sigma\sqrt{2}}\right)}$

其中，${erf\ =\ \frac{2}{\sqrt{\pi}}\int^x_0 e^{-t^2}dt}$

而在 Logistic regression 中，我們使用的 function 稱之為 sigmoid function：${\frac{1}{1\ +\ e^{-kx}}}$

下圖為不同 ${k}$ 所得到的 logistic function，可以發現，當 ${k}$ 越大時，越接近 perceptron 的 activate function。

#### Probability point of view

我們可以利用上述方法進行分類，也就是藉由找出 MLE，得到分類的參數 ${w}$，假設我們要將 data 分成兩類：
則 ${MLE = argmaxP(D|\theta)\ =\ \prod(\frac{1}{1\ +\ e^{-x_iw}})^{y_i}(1\ -\ \frac{1}{1\ +\ e^{-x_iw}})^{1\ -\ y_i}\ =\ \prod(\frac{1}{1\ +\ e^{-x_iw}})^{y_i}(\frac{e^{-x_iw}}{1\ +\ e^{-x_iw}})^{1\ -\ y_i}}$

同樣我們取 ${log}$：
${J\ =\ \Sigma(y_ilog(\frac{1}{1\ +\ e^{-x_iw}})\ +\ (1\ -\ y_i)log(\frac{e^{-x_iw}}{1\ +\ e^{-x_iw}}))}$

我們先考慮對於 ${w_j}$：
${\begin{split}\frac{\partial J}{\partial w_j}\ &=\ \Sigma\left(\frac{\partial}{\partial w_j}y_ilog(\frac{1}{1\ +\ e^{-x_iw}})\ +\ \frac{\partial}{\partial w_j}(1\ -\ y_i)log(\frac{e^{-x_iw}}{1\ +\ e^{-x_iw}})\right) \\
&=\ \Sigma\left(-y_i\frac{\partial}{\partial w_j}log(1\ +\ e^{-x_iw})\ +\ (1\ -\ y_i)\frac{\partial}{\partial w_j}(log(e^{-x_iw})\ -\ log(1\ +\ e^{-x_iw}))\right) \\
&=\ \Sigma\left(\frac{-y_i}{1\ +\ e^{-x_iw}}(-x_{ij})e^{-x_iw}\ +\ (1\ -\ y_i)(-x_{ij}\ +\ \frac{x_{ij}e^{-x_iw}}{1\ +\ e^{-x_iw}})\right) \\
&=\ \Sigma\left(\frac{-y_i}{1\ +\ e^{-x_iw}}(-x_{ij})e^{-x_iw}\ +\ (1\ -\ y_i)(\frac{-x_{ij}}{1\ +\ e^{-x_iw}})\right) \\
&=\ \Sigma\left(y_ix_{ij}\ -\ \frac{x_{ij}}{1\ +\ e^{-x_iw}}\right)\ =\ \Sigma\left(x_{ij}(y_i\ -\ \frac{1}{1\ +\ e^{-x_iw}})\right)\end{split}}$

寫成矩陣形式：
${\frac{\partial J}{\partial w_j}\ =\ X^T(Y\ -\ \frac{1}{1\ +\ e^{-Xw}})}$

> 在上述的微分中，會出現 ${x_{ij}}$ 是因為：
> ${\frac{\partial}{\partial w_j}x_iw\ =\ \frac{\partial}{\partial w_j}(w_1x_{i1}\ +\ w_2x_{i2}\ +\ ...\ +\ w_dx_{id})\ =\ x_{ij}}$

由於此方程為非線性，因此無法直接求得 close form，只能使用 steepest gradient ascent 來慢慢逼近：
${w_{n+1}\ =\ w_n\ +\ X^T(Y\ -\ \frac{1}{1\ +\ e^{-Xw}})}$

> 這裡也可以加上一個常數 (learning rate)，來加速逼近的速度。

#### Newton's method

利用前面的牛頓法，來增加 gradient ascent 的速度。
首先必須先推導 Hessian matrix：
${\begin{split}\frac{\partial}{\partial w_k}\frac{\partial J}{\partial w_j}\ &=\ \frac{\partial}{\partial w_k}\Sigma\left(x_{ij}(y_i\ -\ \frac{1}{1\ +\ e^{-x_iw}})\right)\ =\ \frac{-\partial}{\partial w_k}\Sigma\left(\frac{x_{ij}}{1\ +\ e^{-x_iw}}\right) \\
&=\ \frac{\partial}{\partial w_k}\Sigma\left(\frac{x_{ij}x_{ik}e^{-(w_1x_{i1}+w_2x_{i2}+...+w_dx_{id})}}{(1\ +\ e^{-(w_1x_{i1}+w_2x_{i2}+...+w_dx_{id})})^2}\right) \\
&=\ \Sigma\left(\frac{x_{ij}x_{ik}e^{-X_iw}}{(1\ +\ e^{-X_iw})^2}\right)\end{split}}$

寫成矩陣形式：
${H\ =\ A^TDA}$
其中，
${A\ =\ \left[\begin{array}{cccc}
x_{11} & x_{12} & ... & x_{1d} \\
x_{21} & x_{22} & ... & x_{2d} \\
... & ... & ... & ... \\
x_{d1} & x_{d2} & ... & x_{dd}\end{array}\right]}$
${D\ =\ \left[\begin{array}{cccc}
\frac{e^{-X_1w}}{(1+e^{-X_1w})^2} & 0 & ... & 0 \\
0 & \frac{e^{-X_2w}}{(1+e^{-X_2w})^2} & ... & 0 \\
... & ... & ... & ... \\
0 & 0 & ... & \frac{e^{-X_dw}}{(1+e^{-X_dw})^2}\end{array}\right]}$

則 ${w_{n+1}\ =\ w_n\ +\ H^{-1}f(x)\nabla f(x)}$

> 若遇到 Hessian matrix 無法做 inverse 時，則退回 logistic regression 假設一個 learning rate。

#### 2+ dimension problem of logistic regression

雖然 logistic regression 可以解決極端值的問題，但在二維空間以上的問題上，有時肉眼可以清楚區分出的問題，logistic regression 卻會得到錯誤得結果，如以下問題：

在 logistic regression 中會得到：

然而若使用 Naive bayes classifier，則可以得到：

### k-nn (k-nearest neighbor)

是一種 memory based 的分類方類，也就是今天要判斷一個點屬於那一類時，就從過去的所有點中，找出最近的 k 個點，則那一類最多就屬於那一類。

由於 k-nn 並沒有 bias，因此容易出現 overfitting 的問題：