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

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

  • 本文為一系列課程之筆記，建議從" 機器學習基石筆記-1 "開始閱讀

  • 本文討論內容請參考: 機器學習基石第十一講 : 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 的優缺點