# 林軒田機器學習基石筆記 - 第十一講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第十一講 : Linear Model for Classification**
>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>
---

## Linear Classification , Linear Regression and Logistic Regression

我們所學的這些線性模型，是否均能夠用來作分類問題 ? 一樣的，只要我們能夠確認 VC bound 存在就沒有問題。

我將我們學的這幾種線性模型做了一番整理 :


我們來看看他們的 error 圖形會長成什麼樣子


### 從 Logistic Regression 角度來看 :

$\forall ys$ , $err_{0/1}(s,y)\leq err_{SCE}(s,y)=\frac{err_{CE}(s,y)}{\ln 2}$

$\Longrightarrow E_{in}^{0/1}(\mathbb{W})\leq E_{in}^{SCE}(s,y)=\frac{E_{in}^{CE}(s,y)}{\ln 2}$

$\Longrightarrow E_{out}^{0/1}(\mathbb{W})\leq E_{out}^{SCE}(s,y)=\frac{E_{out}^{CE}(s,y)}{\ln 2}$

$\therefore E_{out}^{0/1}\leq E_{in}^{0/1}+\Omega^{0/1}\leq E_{in}^{SCE}(\mathbb{W})+\Omega^{0/1}=\frac{1}{\ln 2}E_{in}^{CE}(\mathbb{W})+\Omega^{0/1}$

$\Longrightarrow$ 當 $E_{in}^{CE}$ 夠小，我們便能確定 $E_{out}^{0/1}$ 夠小

$\Longrightarrow$ 利用 Logistic Regression 來做 Classification 是可行的。
( Linear Regression 亦有此保證 )

我們也可以從上圖整理出各項 Linear Model 在處理分類問題時的優缺點 :

> [Remark]
> * 在實務上，我們會用 Linear Regression 的最佳解來當作 PLA/Pocket/Logistic Regression 的起始權重 $\mathbb{W}_0$
> * 抑或直接使用 Logistic Regression 取代 PLA ( 較容易求出最佳解 )

## Stochastic Gradient Descent

Logistic Regression 跟 Pocket 一樣，每一次的迭代都必須計算所有的資料一輪，成本相對於PLA來說高出很多。


想要降低計算成本的方法是
將 $\nabla E(\mathbb{W}_{t})$ 視為隨機 $(\mathbb{X}_n,y_n)$ 的 $\nabla err(\mathbb{W}_t,\mathbb{X}_n,y_n)$ 之期望值


換句話說，**Stochastic Gradient = True Gradient + Noise**
* 經過多次迭代後 ，平均的 Stochastic Gradient 會近似於 True Gradient
* 用SGD取代GD的好處是，計算成本相對簡單很多，且計算簡單，但是比較不穩定


從上面兩式來看 :
* 可以將SGD Logistic Regression 視為是一種 Soft PLA
* 只要 $\mathbb{W}_t^T\mathbb{X}_t$ 夠大 ( $\theta\rightarrow 1$ )， PLA 就會近似於 SGD Logistic Regression

> [Remark]
> 1. 停止條件 ? $\Rightarrow$ 當 t 夠大的時候
> 2. $\eta$ 要取多少 ? ? $\Rightarrow$ 0.1附近通常有不錯的表現

## Multuclass Classification : One-Versus-All (OVA) Decomposition


利用基本二元分類，個別找出 classifier，但這樣的方式會有幾個問題 :
* 落在上圖 A 區的資料應該如何分類 ?
* 落在上圖 B 區的資料又該如何分類 ?

$\Longrightarrow$ 利用 Soft binary Classification 來解決這樣的問題


### OVA Decomposition Algorithm


Step 1 : 對每一個分類 k ，我們都能藉由 Logistic Regression 找到一組 $\mathbb{W}_k$ 可以將 $\mathbb{D}\rightarrow\mathbb{D}_k$

Step 2 : 將每一個資料點與各分類器所對應到的機率值進行比較，最高者就分給那一類。

### OVA Decomposition 的優缺點


## Multuclass Classification : One-Versus-One (OVO) Decomposition

為了解決 OVA 中遇到 k 值過大的 unbalance 情況，將 One-Versus-All 改為 One-Versus-One，意即，將所有類別倆倆抓出來 learning pairwise classifier


從上面例子來看，4個類別可以學習出 ${4}\choose{2}=6$種 classifier，一旦新的資料需要預測，就將其丟入這六種 classifier ，端看最後這六種 classifier 最多的預測結果即為 OVO 之預測結果

### OVO Decomposition Algorithm


Step 1 : 任取 k , l 兩種類別，找出一組 $\mathbb{W}_{k,l}$，可以將 $\mathbb{D}\rightarrow\mathbb{D}_{k,l}$

Step 2 : 對於 $\mathbb{X}$ 的分類 $g(\mathbb{X})$ 則由 $\left\{\mathbb{W}_{k,l}^T\mathbb{X}\right\}_{\forall k,l}$來投票決定

### OVO Decomposition 的優缺點