---
# System prepended metadata

title: Classification

---

Classification 
==

input:x
output:他是哪一個class

ex:貸款與否，疾病診斷，手寫辨識，人臉辨識

要先把他的**特性數值化**


# 1. 硬把classification用regression做

Ex:Binary classification
如果結果接近1則是class 1, 如果結果接近-1則是class 2
這樣做會遇到什麼問題

## 問題一
 ![](https://i.imgur.com/FaPFtU0.jpg)
理想上我們會希望出現綠色的那條線 $b+w_1x_1+w_1x_2=0$
但是**一般參數不會只在1~-1**，而**超過1的參數會被判定為是error**，而為了填補這些error則他會偏移他的線來降低他的error

## 問題二
在**multiple class** 下，若是分類為class 1, 2, 3這樣也會有問題，因為這代表1、2, 2、3，比較有關係而1、3比較沒有關係，這樣無法得到好結果

# 2. 機率

理想上的做法：
![](https://i.imgur.com/89UMTSL.png)
- Function
所以Function f(x)，會再有一個function g(x)來判斷x是屬於哪一個class
- Loss Function
$f(x^n)$是指預測的結果
$y^n$指實際結果
$L(f)$找的是哪個結果使loss funtion 最低

這些**無法**用gradient decent求出
可以用Perception, SVM

用**機率**的角度去看：
![](https://i.imgur.com/qoZ8TNS.jpg)
以binary問題來看，要判斷x屬於哪個class會需要$P(C_1), P(x|C_1), P(C_2), P(x|C_2)$，要從training data中預測這四個值出來
就可以算出generative model 然後就可以得到$P(x)$ x出現的機率

## Prior
**$P(C_1), P(C_2)$的部分**(比較好算)
 ![](https://i.imgur.com/dd2RH34.png)
以神奇寶貝來說，令有79隻水系，61隻普通系
$P(C_1)$ -> 是水系的機率是0.56
$P(C_2)$ -> 是普通系的機率是0.44

每隻神奇寶貝都會有一個vector裡面放他的特徵 -> 稱為feature

下面的圖先放Defense, SP defense兩種特徵
![](https://i.imgur.com/gGU1Zzl.jpg)
所以先整理出水系神奇寶貝的Defence跟SP Defence話在這2d圖上

## Gaussian Distribution
![](https://i.imgur.com/owxk0NX.jpg)
input:vextor(數值)
output:可以理解為x在此$\mu,\Sigma$被sample的機率
$\mu$為vector
$\Sigma$為matrix
x越接近$\mu$被sample的機率越大，越遠機率越小

## Maximum Likelihood
**用來找$\mu, \sum$?**
![](https://i.imgur.com/uT1H716.jpg)
不同的$\mu, \sum$都會對應到不一樣的機率
所以取$f_{\mu, \sum}(x)$對每一點的x找找看他的機率
然後取最大的機率$(\mu^*, \sum^*)$
做法就是窮舉出所有的$(\mu, \sum)$再去找最大的$(\mu^*, \sum^*)$

![](https://i.imgur.com/ikpwkmt.jpg)
解$\mu^*$ -> 最大的$\mu^*\equiv$**求平均值**
解$\sum^*$ -> 帶入$\mu^*$ 算他的covariance

![](https://i.imgur.com/4dhkZqq.png)
用上面的辦法去找出水系跟普通系的$(\mu_*, \sum_*)$
現在就可以做classification了

![](https://i.imgur.com/hkfZBAR.jpg)
得到$P(C_1), P(x|C_1), P(C_2), P(x|C_2)$就可以解決問題了

## 實際範例
今天若是用defense, SP defense分出一個2d空間，左上兩圖是training set 可以看到他分出的$P(c_1|x)>0.5\equiv他是水系的機率$，發現其正確率47%，又機器學習可以考慮很多特徵，全部下去算正確率也只有54%，正確率都很低
![](https://i.imgur.com/hi99HoY.jpg)

**要怎麼修正這正確率呢？**

因為feature很多的時候covariance matrix會變很大，會容易導致overfitting，為了有效減少參數
-> **強迫不同class使用相同的covariance matrix**
可以用較少參數來model此模型

![](https://i.imgur.com/RofdRRa.png)

所以$\mu^{1,2}$跟原本是一樣的，$\sum$會是$\sum^1, \sum^2$的平均
先求出$\mu^1, \mu^2$然後把他分別帶進covariance來算出$\Sigma^1, \Sigma^2$，最後再取$\Sigma^1, \Sigma^2$的平均$\Sigma$

![](https://i.imgur.com/gVrvVzB.png)
使用**相同的covariance matrix**可以使boudary變成**直線**(linear)
在考慮七個特徵的狀況下：
正確率有由54 %提升到73 %


# 3. Logistic Regression

![](https://i.imgur.com/8pqav9R.png)

該選擇哪種distribution呢

所以在binary的判斷(output為true/False的時候)不會選擇用gaussian，會說是用Bernouli distribution

如果所有feature是獨立的(比較好算)，我們可以稱他為Naive Bayes Classifier


## Posterior Probabitlity

![](https://i.imgur.com/Wzz6Kym.png)
做完這些操作，會得到sigmoid function $\sigma(z)$
$\sigma(z)無限大趨近於1，無限小趨近於0$

而z 應該長什麼樣子？

![](https://i.imgur.com/4v34axO.png)
這邊有很多推導，我沒有仔細看....我只看最後結論...
可以推得原式=$\sigma(w\cdot x+b)$且b為一scalar
所以他會是一個linear的狀態

我們需要的得$w, b$會需要先求$N_1, N_2, \mu_1,\mu_2,\sum$，
是否可以省去上面的東西直接求的$w, b$呢？


## Step1 Function set

![](https://i.imgur.com/J332kUB.png)

這邊$f_{w,b}$ 是代表該函式由w,b所控制之function

![](https://i.imgur.com/vzGh8f2.png)

所以Logistic Regrssion 因為有igmoid function 所以可以把output控制在0~1
而linear regression 之output會是任何value



## Step2 Goodness of Function

![](https://i.imgur.com/IY8hWqY.png)
在training data上就要把$x^n$屬於哪一個class標好

$L(w,b)$ = ($x^1是C_1的機率$)($x^2是C_1的機率$)($1 - x^3是是C_2的機率$).....
最後再求$w^*, b^*$得出最高機率的解，也就是最大化L(w,b)這個function

接下來的過程是要簡化他的計算
![](https://i.imgur.com/nuckSoe.png)
根據上面的數值更正為$y^1=1, y^2=1, y^3=0$（ 上面的圖數字打錯）
帶入下面的式子：

可以算出兩個distribution之cross entropy為$H(p,q)$


**cross entropy 可以理解為這兩個distribution有多接近
若兩個distribution一樣，cross entropy為0**

![](https://i.imgur.com/u3fm567.jpg)
相較之下Linear Regression用square error來算看起來很直觀，為什麽在Logistic Regreesion要用Cross Entropy來算呢？
 


## Step3 Find the best function

用gradient descent就好，計算它對$w_i$的偏微分，下面是數學的推導，先暫時省略
 會得到結論：
 ![](https://i.imgur.com/HvbZ7LR.png)

**w的update會取決於三件事**
1. learning rate : 自已設定
2. $x_i$：看data有多大
3. $\hat{y}^n-f_{w,b}(x^n)$：$\hat{y}^n$是目標，$f_{w,b}(x^n)$是現在model的output， 代表他離目標的差距有多大。 若離目標越遠，update的大小就越大

## Logistic跟linear之比較

logistic regression之output會控制在0~1之間
linear regression之output會是任何value

![](https://i.imgur.com/jTiDh5M.png)
 為什麼他要用cross entropy來算呢？應該也可以直接用linear regression 的squre rror來算也可以得到一個合理的loss function，怎麼變這麼複雜？
 
## 為何logistic不用square error?

由於logistic的性質是在0~1之間
![](https://i.imgur.com/8E9LE4e.png)
今天對L(F)做gradient descent$\equiv$對他做$e_i$的偏微分

但是接下來會遇到問題
當目標是class 1時：
若現在f(x)=1完美狀態，偏微分就會是0 -> 合理
若現在f(x)=0離目標超遠，偏微分結果是0 -> 不合理

當目標是class 2時：
若現在f(x)=1離目標超遠，偏微分就會是0 -> 不合理
若現在f(x)=0完美狀態，偏微分結果是0 -> 合理

![](https://i.imgur.com/dgnl3Vz.png)
所以用square error的方式，在離目標很遠的情況下他的偏微分值會很小，找答案的速度也很慢，所以你今天隨機選一個起始點他也沒辦法分辨現在離目標的遠近，因為不管是遠是近偏微分值都很小。
用cross entropy，在離目標很遠的時候update大小會比較快，會快很多

用cross entropy可以讓整個training快很多



## Dicrimminative vs generative
Dicrimminative -> logistic的方法
generative -> gausion的方法
實際上他們的function set是一樣的

![](https://i.imgur.com/gd7YbXQ.png)

在共用covariance的情況下，他們會用一樣的function set$P(C_1|x)=\sigma(w\cdot x+b)$

今天是用**logitic**的話可以直接找出w,b

今天是用**generative**的話要算出$\mu^1,\mu^2, \Sigma^{-1}$再求出w,b

而這兩個求出的w,b, 會是**不一樣**的


而這兩個W跟B哪一個會比較好呢?
![](https://i.imgur.com/pQGgkHp.png)
常常會聽到Dicrimminative的表現會比較好。

在generative的角度下，會有一些設定（腦補）：
用naive bayes也就是機率與統計的角度下去看，可能會跑出一些不直覺的答案，就比如說 **下面圖class1的(1,1)** 因為他把不同dimension的data視為idependent，所以可能被歸類於class2，非常不直覺。
他會腦補出一些條件使答案怪怪的。他有時候會遵從自己的腦補而不是data的資訊

![](https://i.imgur.com/xJ5hb4x.png)

今天若是在data很小的情況下，腦補也是有用的，可以提供更多的資訊

所以Discriminative也不一定永遠比generative好，在training data少的時候generative有時候會比較好

正常情況下還是Discriminative比較強，也可以適應更大noise
![](https://i.imgur.com/nm2YHwu.png)

語音辨識現在neural network 是一個discriminative的方法，但是但是語音辨識是generative的system，可以estimate說出下一句話的機率


## Multi-class Classification(3 class以上)

![](https://i.imgur.com/6QlSVny.png)

**其中$z_1,z_2,z_3$可以是任何值**

**SoftMax:**
1. 取exponential（會使值得大小分得更開更明顯）
2. 再除以其$\Sigma$（把它正規化，使他在0~1）
3. 得到$y_i$

$y_i$會有兩個性質：
1. $1>y_i>0$
2. $\Sigma_iy_i=1$（因為他正規化）

![](https://i.imgur.com/n7BAJdd.png)

先對他做softmax就會得到y，然後使$y, \hat{y}$做cross entropy
(上面的式子寫錯了，應該是$-\Sigma\hat{y}_ilny_i$)

然後這邊再重複一次，不能將class設為1,2,3，因為會有遠近問題
要將$\hat{y}$設為一個array，這樣彼此獨立就不會有遠近問題
$\hat{y}=\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}$



## Limitation of Logistic Regression

Logistic Regression畫出來會是一個linear的直線所以在對角的情況下變無法畫出來。
像是上圖，不管Logistic Regression線怎麼畫都沒辦法把紅藍點切開


![](https://i.imgur.com/8QGBort.png)
![](https://i.imgur.com/wpzAXch.png)

若是今天兩個class在對角的時候，不管怎麼切都沒辦法切成兩邊
像是上圖的藍色與紅色點就沒辦法切出來

這時候可以用**Feature Transformation**
可以理解為一個linear transformation，找出最適合的
又他有很多transformation方法，
下面是一種方式：
![](https://i.imgur.com/kd82bl3.png)

將$x_1, x_2$調整他的weight變成$x_1' , x_2'$，調整weight可以有不同的重量都是可以的，接下來再對$x_1', x_2'$做feature transform
又帶入原本的範例：

（這邊右下的圖$x_1', x_2'$的label相反了）
![](https://i.imgur.com/g5sYbdi.png)
可以看出經過這個transformation就可以做logistic regresstion切出紅線做logitic regresion


所以就可以不斷串連logisstic regresstion
![](https://i.imgur.com/LINAbT7.png)
串連很多就可以變成 **Neural Network**!

