# ML Lecture 4: Classification
###### tags: `機器學習` `李弘毅教授`

## Classfication
輸入是一個物件，輸出是它屬於哪一類。例如輸入一個神奇寶貝的各項特徵，輸出他是哪個屬性。

## 可以把Classfication當作Regression解嗎？
### 以二元分類為例：
二元分類的輸出種類只有兩種。
Regression的輸出會是一個數值，因此如果要用Regression解Classification問題的話，就要定義數字接近哪個數字時是哪一類。例如，如果數字接近1的話就是第一類；接近-1的話就是第二類。

#### 用這樣的分法有甚麼問題呢？
如下圖，如果要分類的樣本如左圖一樣，分類時不會有甚麼問題；但如果樣本分布如右圖，就會出問題了。

因為就分類來看，右下角的那些點應該是非常好的第二類，但用Regression來分的話，他反而會產生很大的error。為了縮小error，模型可能就會從綠線更新成紫線，結果反而變差。

### N元分類的問題：
如果把接近1當成第一類，接近2當成第二類，接近3當成第三類...，也不太好。因為這樣設定的話，第二類、第三類的輸出會被當作比較接近，他們之間應該有某種關係。不過事實上，他們之間並沒有這種關係，應該是彼此獨立的。

## 解Classification問題的正確方式
Classification問題的輸出會是離散的，前面用Regression的輸出是連續的。
- 選擇模型
如下圖，其中一種「二元分類」可能的做法是，在定義模型時，模型內部包含另一個模型g(x)。之後再定義，g(x)在哪個範圍是哪一類。
- 決定損失函數
損失函數可以定義成：分類錯誤的次數，假如在Training data上的錯誤次數越多，就代表Loos越大。
- 找出最佳模型
由於用這個方是定義出來的損失函數沒辦法微分，因此不能使用Gradient Descent。取而代之可以用的是，Percoption、SVM，不過下面要介紹的不是這兩種方式。

## 如何找出最佳模型
### 從以前學過的機率開始帶入
如下圖，假設有一個大箱子，裡面有Box1、Box2兩個箱子，隨便抽一顆球，抽到箱子1的球的機率P(B~1~)是2/3、箱子2的機率P(B~2~)是1/3。並且從箱子1抽出藍色球的機率是4/5、從箱子2抽出藍色球的機率是2/5。則如果今天抽到了一顆藍球，他從箱子1出來的機率如下圖最下面式子所示。
### 這跟分類問題有甚麼關係呢？
把類別1當成盒子1、類別2當成盒子2，問題就會變成給定一個寶可夢(輸入資料)，則他從各個類別抽出來的機率是多少呢？

要計算這個值就要知道以下四個數值：
1. 類別1本身的機率
2. 類別2本身的機率
3. 從類別1中抽出x的機率
4. 從類別2中抽出x的機率

計算x從第一類出現的機率的算法如下：

### 如何取得那四個機率值呢？
要從訓練資料把這四個值算出來，==這樣的方式稱為Generative Model==。

#### Prior Probability(先驗機率)
其實就是P(C~1~)、P(C~2~)，代表的是兩個種類在所有訓練樣本中佔的比例。例如第一類有79隻、第二類有61隻，則：
- P(C~1~)=79/(79+61)=0.56
- P(C~2~)=61/(79+61)=0.44

#### Propability from class

==計算P(x|C)，也就是要計算x從C類中出現的機率。==
從這裏的例子來看就是「在訓練樣本中的水系神奇寶貝中，找到海龜的機率為何(海龜不在訓練資料中)」。

使用訓練資料來計算海龜出現在水系神奇寶貝的機率很奇怪，因為海龜明明就不在訓練資料中，==這樣他出現的機率不就一定是0嗎？？==

事實上不是的，因為水系神奇寶貝都是從同一個Gaussian Distribution中取樣出來的，既然是水系神奇寶貝就會有差不多的特徵向量分布(高斯分布)。透過這個分布就可以估測出，從水系神奇寶貝中，抓出海龜的機率是多少了。

##### Gaussian Distribution
這裡的高斯分布是甚麼意思呢？
前面提到相同的神奇寶貝會有差不多的分布，把特徵向量畫出來會發現他們是很接近的。而高斯分布的式子如圖上半部所示，跟平均值μ、共變異矩陣Σ有關，相同性質(例如同屬神奇寶貝)會由同一組高斯分布的式子表示(相同的μ、Σ)。

這個式子的輸入會是x，代表的是輸入物件的特徵向量。

回到神奇寶貝的例子，這裡要看海龜是甚麼屬性，因此可以把海龜代入水屬性的高斯分布式子看他的結果高不高，這個得到的結果是一個機率。假如得到的數值越高的話，就代表從水系神奇寶貝中找到他的機率越高。
### Maximum Likehood
==用來計算最佳μ、Σ的方法。==
每一個類別的資料分布都會有個趨勢，某一組μ、Σ會讓高斯分布最接近那個趨勢，要找出那組最佳的μ、Σ就要使用Maximum Likehood。

機率密度函數：可以看某個輸入是哪一類的機率是多少，將特徵值代入。機率密度函數本身跟平均值μ、共變異矩陣Σ有關。每一種類別都會有不同的μ、Σ。

如下圖，兩個紅色框框是不同μ、Σ對應的機率密度函數。即使這兩個框框出現的位置不同，但他們仍然都有機會取樣出那79個點(即使沒有框到也只能說機率非常低)，只是左邊框框取樣出來的機率比較高。

#### 求解Maximum Likelihood：
L是Likelihood的意思，他的公式是把每一個訓練樣本點代入高斯分布的式子，再全部相成。讓L算出來最大的那個μ、Σ就是Maximum Likelihood的μ、Σ。

不過如何求出讓L最大的那組μ、Σ也是個問題，要求這組解有兩種做法：
1. 直覺的想法是：將L微分，看微分為0的點在哪裡，那裡就是μ、Σ的最佳解。
2. 使用公式解：平均值很直覺就是把每個點相加取平均，而共變異矩陣則是要使用下圖綠色框框的式子解。

### 實測使用Generative Model的結果
如下圖，分別計算出了兩種屬性神奇寶貝分別的μ、Σ。
接下來計算x從第一類取樣出來的機率P(C~1~|x)，其中為了計算P(x|C)，因此會使用到已經取得的μ、Σ。
假如計算出來的P(C~1~|x)>0.5就代表：目前輸入的資料x是屬於第一類。
由於已經計算出P(C~1~|x)了，因此就可以知道各個不同特徵值的x，屬於個個類別的機率了。如下圖，紅色代表該點越接近第一類，藍色代表越接近第一類。

不過稍微觀察一下結果會發現結果不是太好，在只考慮兩個特徵時，正確率只有47%，就算考慮了所有的特徵，也只有提升到54%。

## Modifying Model
前面介紹到的Generative Model是不同類型用不同的共變異矩陣，但這邊介紹的方法是所有類別使用相同共變異矩陣。概念是不同屬性的神奇寶貝的特徵平均值會不同，但他們分布的趨勢卻差不多(使用相同共變異矩陣)。

### 不同類別使用相同共變異矩陣的好處
由於共變異矩陣跟輸入的feature size成平方正比，因此如果feature size很大的話，共變異矩陣的變化就會很大。也就是會讓Variance變很大，就會容易產生Over fitting。

因此為了減少Over fitting的情形，就會選擇讓多個類別共用共變異矩陣。

### 如何計算共用的共變異矩陣呢？
==先計算出各自的共變異矩陣，之後再加權取平均。==

### 使用Modelfying Model的結果
由圖中可以發現，分開不同類別資料的界線變成線性的了，而辨識的準確度也提高了許多。==因此Modelfying Model又可以稱為Linear Model==。

## 統整二元分類完整步驟
二元分類的過程也遵守那三大步驟
### 1. 選擇模型
這裡的Model是採用如圖前面提到的式子，要訓練的參數就是P，像這個例子就是4個參數。不過由於要計算出P(x|C)的過程是很繁瑣的，過程中包含了輸入的很多特徵值，因此事實上還是一個超多特徵值的模型(前面提到共變異矩陣跟特徵值的數量呈平方比)。

### 2. 衡量模型的好壞
這邊衡量模型的好壞不是透過Loss Function的方式，而是透過Maximum Likelihood。找出產生最大Likelihood的μ、Σ，找到之後就可以進而計算出Probability Distribution ( P(x|C) )，再搭配Prior Propability就可以得到最佳模型。

### 3. 找出最佳模型
使用公式即可快速找出Maximum Likelihood的μ、Σ。

## Probability Distribution
### 機率模型的選擇
其實也不一定要用高斯模型當作Probability Distribution，不過一樣的道理，==比較簡單的機率模型就會造成較大的Bias、較小的Variance；比較複雜的機率模型就會產生比較大的Variance、比較小的Bias==(因為複雜的機率模型會有比較多參數)。

不過==假如已知特徵值是Binary的，則使用Bernoulli distribution會比較好==，因為他的資料就不是高斯分布了，用高斯模型一定比較差。

一筆資料會有很多個特徵值，<font color = "red">假設各個特徵值是獨立的。這樣就可以把一個本來是n維的高斯分布變成很多個1維，最後再全部乘起來</font>。因為共變異矩陣變成Diagonal，只有對角線的地方有值，其他地方都是0，因此可以減少參數量，讓模型變簡單。如果是透過這樣的方式來做分類，就是在使用==Naive Bayes Classifier==。


## Posterior Propability
其實P(C|x)又稱為後驗機率，由圖中的式子表示。
若將後驗機率的式子上下同除P(x|C~1~)P(C~1~)，則會產生紅色框框的式子。
之後為了希望可以把後驗機率的式子用==Sigmoid==式子表示，因此將橘色框框的部分設為z。

### 接著嘗試化簡z
1. log相乘的可以變兩個log相加
2. P(C~1~)、P(C~2~)是先驗機率，代表的就是訓練資料集中這兩類出現的比例。N~1~就是第一類的數量、N~2~就是第二類出現的數量。
3. P(x|C)是Gaussian Probability Distribution，把他的式子列出來。
4. 把P(x|C)相除的那項也化簡
5. 綠色框框那項就是把他展開，展開後會發現藍色底線那兩項一樣，可以合在一起變兩倍。而橘色框框的不分因為跟綠色框框的一樣，差別只差在1變成2，所以直接套綠色的結果就好。
6. 紫色部分則是綜合上面所有化簡的結果
7. 由於前面有提到，在很多情形下，我們會讓多個類別使用相同共變異矩陣，因此可以假設Σ~1~=Σ~2~=Σ。做了這個假設之後就可以發現，有三項會消失，因此可以將Z化簡為綠色框框部分。
8. 再經過觀察可以發現，左半部可以當作是一個矩陣，右半部可以當成一個純量(因為轉置向量a * 某矩陣 * 向量a = 純量)。
9. 因此可以得到結論：後驗機率的式子其實沒那麼複雜，就是橘色框框部份而已。
> σ(X)代表sigmoid函數。

結論：目前要得到P(c|x)需要先有μ~1~、μ~2~、Σ(如果是Generative model還要分Σ~1~、Σ~2~)，得到這些東西後再代入sigmoid function才可以得到後驗機率。但後驗機率其實就是我們要進行最佳化的模型，那==有沒有辦法不要先計算那些麻煩的東西，直接找到w、b呢？== 這就需要使用到<font color="red">Logistic Regression</font>。