---
# System prepended metadata

title: 林軒田機器學習基石筆記 - 第十一講
tags: [機器學習基石, Maching Learning, 林軒田]

---

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

---

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

## Linear Classification , Linear Regression and Logistic Regression

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

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

![](https://i.imgur.com/INx9k8g.jpg)

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

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

### 從 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 在處理分類問題時的優缺點 : 
![](https://i.imgur.com/TeQxRwA.png)


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

## Stochastic Gradient Descent

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

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

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

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

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

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

從上面兩式來看 : 
* 可以將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

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

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

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

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

### OVA Decomposition Algorithm

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

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

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

### OVA Decomposition 的優缺點

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


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

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

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

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

### OVO Decomposition Algorithm

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

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 的優缺點

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