# 李宏毅_ML_Lecture_4
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## ML Lecture 4: Classification
[課程連結](https://www.youtube.com/watch?v=fZAZUYEeIMg&index=9&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49)
### Classification

* 是否借款
* 醫療診斷
* 手寫辨視
* 人臉辨視
### Example Application

範例：輸入一隻寶可夢來預測它的屬性類別

註：寶可夢有18種屬性
### Example Application

首先要確定特徵，將寶可夢的相關資訊數值化做為特徵。(如上圖條列)
### How to do Classification

需求第一步，我們要收集訓練資料集，這邊也提到為什麼不能將分類問題以迴歸方式來處理。

以二分類問題為例，輸出就是$\{1, -1\}$，但regression的輸出並不會剛好是1或-1，是一個數值，或許我們可以說，接近1那就視為class 1，接近-1那就視為class 2。這代表是以0為分界，大於0就是接近1，那就是class 1，小於0就是接近-1，那就是class 2。
### Why not Regesssion

但這麼做會遇到什麼問題?

假設我們的模型是：$y=b+w_1x_1+w_2x_2$，藍色為類別1，紅色為類別2，雖然左圖來看分佈有順利的區隔，但如果出現離群值(如右圖)會造成整條迴歸線受離群值影響而造成迴歸線性切割無法順利區隔。模型會為了讓離群值的輸出接近1而傾向那邊，近而造成整個決策邊界由綠色轉紫線。
### Ideal Alternatives

作法上我們可以這麼處理：
* 在function內再加入一個function(g)來轉換
* 當g(x)>0的時候就當做是類別1，否則即為類別2
* 損失函數單純統計錯誤次數?
* 但是這樣做是無法微分的(無法梯度下降)
* 用其它的方法
* svm、perceptron

本日的課程先以機率的觀點來解，後續課程會提其它的。
### Two Boxes

從機率問題來談怎麼處理。

兩個盒子，裡面各有藍綠兩個色球，如果抽到一個藍色的球，那這球從box1抽的機率有多少?
### Two Classes

將Box變為class，給一個x(要分類的對象)，它屬於某個class的機率為何，我們需要知道：
* $P(C_1)$:從class1抽出來的機率
* $P(C_2)$:從class2抽出來的機率
* $P(x|C_1)$:從class1抽出x的機率
* $P(x|C_2)$:從class2抽出x的機率

有了上面四種機率，就可以計算出$P(C_1|x)$的機率($x$是class1的機率)，而這四種機率就是從我們的訓練資料去估測出來的，這種想法即為Generative Model，這可以計算某一個$x$出現的機率，也就是，
* $P(x)=P(x|C_1)P(C_1)+P(x|C_2)P(C_2)$

上面的式子說明著，某一個$x$出現的機率就是它是$C_1$的機率乘上$C_1$挑出$x$的機率加上$C_2$的機率乘上$C_2$挑出$x$的機率。
### Prior

以寶可夢分類為例：
* Class1是水系寶可夢
* 數量：79
* Class2是一般系寶可夢
* 數量：61

從兩類別中取得一隻寶可夢的機率如下：
$P(C_1)=\dfrac{79}{79+61}=0.56$
$P(C_2)=\dfrac{61}{79+61}=0.44$
### Probability from Class

我們從水系神奇寶貝中撈到海龜的機率如何計算?$P(x|C_1)=?$

註：水系數量79
### Probability from Class - Feature

每一隻寶可夢(神奇寶貝)都帶有它的所屬特徵(feature)，這特徵述敘是個向量(vectory)，將其中兩個特徵取出可視化觀察。

圖上每一個點都代表一隻寶可夢，現在有一個不存在這79隻寶可夢資料的新資料，它是屬於海龜的機率有多少?(不會是0)

我們可以把這79隻寶可夢的資料視為是從一個高斯分佈中挑出來的，這並不是完整的神奇寶貝的資料，只是我們剛好取到這79個點，因此我們從這個高斯分佈中取到海龜的機率並不會是0。所以我們要做的是，用這79個點來得到那一個高斯分佈。
### Gaussian Distribution

高斯分佈，可以將它視為一個function($f_{\mu, \Sigma}$)，它的輸入是一個向量$x$，也就是某一個寶可夢的特徵值，輸出是$x$被從這個分佈中被抽取到的機率(不全然是機率)，這個機率的分佈是由$\mu$(mean)與$\Sigma$(covariance)決定：
* $\mu$:vectory
* $\Sigma$:matrix

因此，將不同的$\mu,\Sigma$帶入，這個分佈就會有不同的形狀：
1. 不同的$\mu$相同的$\Sigma$，機率分佈最高點不一樣
2. 相同的$\mu$不同的$\Sigma$，機率分佈最高點一樣，但是分散的程度不一樣

註：Gaussian Distribution:高斯分佈
註：covariance:共變異數
### Probability from Class

假設我們從Gaussian中取出79個點(就是資料集中的79個水系神奇寶貝)，現在給我們一個新的點(不存在79個資料集中的新資料)，就可以利用Gaussian Distribution function來計算出抽到該點的機率。

以分佈來看，該點愈接近中心點被抽到的機率會愈高，離中心愈遠被抽到的機率則愈低，因此黑點，New $x$離中心有點遠，被抽到的機率就會有點小。

所以，如何找出$\mu$與$\Sigma$就是一個問題，而找出它們的概念就是Maximum Likelihood。
### Maximum Likelihood

任何一個Gaussian都有可能找出這79個點，只是它的可能性(Likelihood)是不相同的，並且每一個點的機率都不會是0，以右上的分佈為例，離它最遠的點機率很低，但卻不會是0。

上圖兩個分佈為例，左邊Gaussian找出這79個點的機率會較右邊Gaussian來的高，只要有$\mu$與$\Sigma$我們就可以計算出這個Gaussian的Likelihood。

也就是這個Gaussian抽到這79個點的機率連乘積，將這79個點帶入likelihood的function：
* $L(\mu,\Sigma)=f_{\mu,\Sigma}(x^1),f_{\mu,\Sigma}(x^2)...f_{\mu,\Sigma}(x^{79})$

註：L非指成本函數
### Maximum Likelihood

現在我們知道怎麼計算likelihood，所以我們就可以來找出一個Gaussian($\mu^*, \Sigma^*$)，而這個Gaussian是找出這79點的Lieklihood是最大的。

窮舉所有可能的$\mu, \Sigma$，我們要得到最大的那一個，$\mu^*,\Sigma^*=\arg\max_{\mu,\Sigma}L(\mu, \Sigma)$：
* $\mu^*=\dfrac{1}{79}\sum_{n=1}^{79}x^n$
* 將79個x vectory加總之後取平均
* $\Sigma^*=\dfrac{1}{79}\sum_{n=1}^{79}(x^n-\mu^*)(x^n-\mu^*)^T$

當然你也可以直接用微分硬解一發就可以。
### Maximum Likelihood
改圖：改37:16秒

有了上面的公式就可以求出兩個calss的各別$\mu$與$\Sigma$，也就可以計算出$P(C_1|X)$。

### Now we can do classification
改圖：38.36

$P(C_1\vert x)=\dfrac{P(x\vert C_1)P(C_1)}{P(x\vert C_1)P(C_1)+P(x\vert C_2)P(C_2)}$，只要得到的結果是大於0.5，那我們就可以說這個$x$是屬於$C_1$。

### How's the results?

上圖左是水系(藍點)與一般系(紅點)在兩個特徵上的分佈，每一個點都可以計算它是$C_1$的機率。

上圖很清楚的看的出來，它們之間並沒有一個很明顯的決策邊界，紅色的區域是屬水系的機率較高，藍色區則是屬一般系的機率較高。

上圖右上說明著訓練集的結果。上圖右下說明著測試集的結果，測試資料集也僅47%的正確率，即使用了七個特徵，最後得到的結果還是只有54%的正確率。
### Modifying Model

實務上比較少每一個高斯模型都有自己的$\mu, \Sigma$，以我們的案子來看，兩個類別擁有著各自的$\mu, \Sigma$，這會造成參數過多的問題。常見作法是不同類別有著相同的$\Sigma$.。
### Modifying Model

讓我們調整式子，讓水系與一般系神奇寶貝擁有相同的covariance，計算它們的likelihood：
* $L(\mu^1, \mu^2, \Sigma)=f_{u^1,\Sigma}(x^1)f_{u^1,\Sigma}(x^2)...f_{u^1,\Sigma}(x^79)f_{u^2,\Sigma}(x^80)f_{u^2,\Sigma}(x^81)...f_{u^2,\Sigma}(x^140)$

上面的式子很直覺，$C_1$就用$\mu_1$來跟$\Sigma$計算，而$C_2$就用$\mu_2$來跟$\Sigma$計算。

$\mu^1,\mu^2$不變，一樣是取各自類別的均值，而$\Sigma$則依各自類別總數做加權平均，即$\Sigma=\dfrac{79}{140}\Sigma^1+\dfrac{61}{140}\Sigma^2$
### Modifying Model

調整共用covariance之後，決策邊界變為線性，這也稱為線性模型，並且考慮所有特徵之後正確率提升為73%。
### Three Steps

從剛剛的計算推論，我們得到機率模型三步驟：
* Model
* 有$P(C_1),P(C_2),P(x|C_1),P(x|C_2)$四種機率分佈，這就是模型的參數，只要你選不同的$\mu$(mean)與$\Sigma$(covariance)，就會得到不同的機率分佈，也就會得到不同的模型
* $P(C_1)$>0.5, class=1
* Goodness of a function
* 評估這個模型的好壞就是找出一個機率分佈來最大化產生資料集的likelihood
* Find the best function
### Probability Distribution

不一定要使用高斯分佈，也可以使用其它的，簡單的機率模型，參數少就high bias，low variance。

有一種作法是這樣的，$x$是一個$K$維向量，並且$x$是輸入特徵，假設每一個維度的機率分佈是獨立的，則$P(x|C_1)=P(x_1|C_1)P(x_2|C_1)....P(x_K|C_1)$(**Naive Bayes Classifier**)，但以這種方式去建這次的案例得到的結果是不好的，可能是過於簡單，或許特徵間還是有相關性存在。

註：binary feature，像是『是、不是』、『0,、1』，可能會以bernoulli distribution來假設(柏努力)
### Posterior Probability

這邊將剛才計算機率所用的數學式做一些改變：
* $P(C_1|x)=\dfrac{P(x|C_1)P(C_1)}{P(x|C_1)P(C_1)+P(x|C_2)P(C_2)}$
* 上下同除分子
* $\dfrac{1}{1+\frac{P(x|C_2)P(C_2)}{P(x|C_1)P(C_1)}}$
* 分母$\frac{P(x|C_2)P(C_2)}{P(x|C_1)P(C_1)}$取對數
* $z=ln\frac{P(x|C_1)P(C_1)}{P(x|C_2)P(C_2)}$
* $P(C_1|x)=\dfrac{1}{1+exp(-z)}=\sigma(z)$
* 這又稱sigmoid function
### Posterior Probability

後面開始是數學的推論，剛才我們已經知道：
* $P(C_1\vert x)=\sigma (z)$，其中$z=\ln\dfrac{P(x\vert C_1)P(C_1)}{P(x\vert C_2)P(C_2)}$
* 因為是取$\ln$，因此相乘就等於相加，可以寫為$z=\ln\dfrac{P(x\vert C_1)}{P(x\vert C_2)} + \ln\dfrac{P(C_1)}{P(C_2)}$
* 其中$\ln\dfrac{P(C_1)}{P(C_2)}$是類別的機率，$P(C_1)=\dfrac{N_1}{N_1+N_2}$，$P(C_2)=\dfrac{N_2}{N_1+N_2}$，消掉之後就可以得到$\dfrac{N_1}{N_2}$
* $P(x\vert C_1)$我們也知道，這是一個機率分佈，也就是$f_{\mu,\Sigma}$，即$P(x\vert C_1)=\dfrac{1}{(2\pi)^{D/2}}\dfrac{1}{\vert \Sigma^1 \vert^{1/2}}\exp \{-\dfrac{1}{2}(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1)\}$，而$P(x\vert C_2)$則是另一個機率分佈


把兩個機率分佈相乘再取$\ln$會得到：
* $\ln \dfrac{\dfrac{1}{(2\pi)^{D/2}}\dfrac{1}{\vert \Sigma^1 \vert^{1/2}}\exp \{-\dfrac{1}{2}(x-\mu^1)^T(\Sigma^2)^{-1}(x-\mu^1)\}}{\dfrac{1}{(2\pi)^{D/2}}\dfrac{1}{\vert \Sigma^1 \vert^{1/2}}\exp \{-\dfrac{1}{2}(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)\}}$
* $\dfrac{1}{(2\pi)^{D/2}}$與distribution無關，直接消掉
* $=\ln\dfrac{\vert \Sigma^2 \vert^{1/2}}{\vert \Sigma^1\vert^{1/2}} \exp\{-\dfrac{1}{2}[(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1) - (x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)]\}$
* 提出$\ln$的部份，然後$\exp$的部份相除即相減，因此調整
* $=\ln\dfrac{\vert \Sigma^2 \vert^{1/2}}{\vert \Sigma^1\vert^{1/2}} -\dfrac{1}{2}[(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1) - (x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)]$
* 相乘變相加，消掉$\exp$


細部展開$(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1)$：
* $=x^T(\Sigma^1)^{-1}x-x^T(\Sigma^1)^{-1}-(\mu^1)^T(\Sigma^1)^{-1}x+(\mu^1)^T(\Sigma^1)-1\mu^1$
* $=x^T(\Sigma^1)^{-1}x-2(\mu^1)^T(\Sigma^1)^{-1}x+(\mu^1)^T(\Sigma^1)^{-1}\mu^1$

另一個$(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)$展開只是1調整為2，因此為$=x^T(\Sigma^2)^{-1}x-2(\mu^2)^T(\Sigma^2)^{-1}x+(\mu^2)^T(\Sigma^2)^{-1}\mu^1$

而$\ln\dfrac{\vert \Sigma^2 \vert^{1/2}}{\vert \Sigma^1\vert^{1/2}}$是將$\Sigma^1$與$\Sigma^2$的determinant相除。

最後只要將$-\dfrac{1}{2}$乘進去，最後的機率$\ln\dfrac{N_1}{N_2}$再加回來就可以成功的得到$z$


剛才我們說過，一般來說，covariance是共用的，因此$\Sigma^1 = \Sigma^2 = \Sigma$，這種情況下，剛才得到的式子就可以得到很大的簡化，最終得到的就只會是，
* $z=(\mu^1-\mu^2)^T\Sigma^{-1}x-\dfrac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1 + \dfrac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2 + \ln\dfrac{N_1}{N_2}$
* 上面是把跟$x$相關的集合起來之後的結果

其中，我們可以將第一個項目，$(\mu^1-\mu^2)^T\Sigma^{-1}$，視為一個$W^T$，它會是一個向量，後面剩下的剩為$b$。其實$b$裡面的$\mu,\Sigma$連乘之後得到的就只會是一個scalar，想一下剛才的寶可夢案例，是一個2x1的向量，轉置之後就是1x2，乘上一個2x2的矩陣就是1x2，再乘上一個2x1的向量那就是1x1，自然就是一個scalar。而最後面的$\ln\dfrac{N_1}{N_2}$也是一個scalar，因此整個$b$其實計算之後也就只是一個數字。

推導到最後我們知道，$P(C_1\vert x)=\sigma(z)$，所以我們可以把這整個式子很簡單的寫成$\sigma(w\cdot x +b)$，從這邊也可以瞭解到為什麼假設兩個類別是同一個分佈的時候，它的決策邊界會線性的。

在generative model中，我們試著去找出$N_1,N_2,\mu^1,\mu^2,\Sigma$，找出這五個值，我們就可以得到$w,b$，也就可以得到機率。

但是，如果最終的目標就是為了找出$w,b$，那幹嘛這麼累?搞了一堆東西就是為了算出$w,b$，如果我們可以直接找出$w,b$，那就可以不用這麼麻煩，這也就是下一堂課會說的。