林軒田機器學習基石筆記 - 第十一講

發表於 更新於 分類於 ， 閱讀次數： Disqus：

機器學習基石第十一講 : 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 的優缺點