機器學習基石系列(8) — 利用線性模型解決分類問題
在本篇中，我們要來利用前面幾篇介紹過的線性模型解決分類問題。這些模型分別是：
- PLA(proceptron learning algorithm)：最基本的二元分類模型，要求資料線性可分。
- Linear regression：有公式解，強力且迅速的解決問題，儘管不一定是最佳解。
- Logistic regression：利用梯度下降的方式處理問題，有比較好的機會找到最佳解。
這三種演算法，核心就是找到一個w，使s=w^Tx。在PLA中，關心的是s和y是否同一類(同號)，即h(x)=sign(s)。E_in屬於離散型(0,1)。很直觀，但需要花時間。線性回歸中，直接使用s，關心的是距離，E_in使用平方差。羅吉斯回歸使用θ，h(x)=θ(s)。E_in使用cross entropy。
現在，我們要用這些概念來處理線性分類問題。因為個別使用的E_in，也就是評估方法不同，所以在核心的s=w^Tx之外，再加上y={1,-1}這個條件。PLA本來就是最早設計來針對線性分類的工具，所以這邊只考慮linear regression和logistic regression就好：
- Linear regression：y={1,-1}是實數空間裡的兩個值，而原本的輸出結果是實數空間，自然包括這兩個值。
- Logistic regression：拿到的資料性質比較像線性分類會拿到的資料，所以也可以適用。(見羅吉斯回歸)
錯誤評估函數的調整
不過錯誤評估函數可能要做一些調整。例如在線性分類，原本的定義是
現在為了要讓其他兩個方法也能通用，透過核心s=w^Tx，把s引進到函數裡
然後符號是否一致這件事可以用「相乘是否為正」取代
線性回歸
現在來看看線性回歸要怎麼改。原本的損失評估函數是
把h(x)用s代換，變成
這邊為了要把s也換成ys，做了一點小技巧。老師在這邊講得比較快，我稍微推演一下：(s-y)²=s²-2sy+y²。如果把括弧內s換成ys，則y要換成1，這樣得到(ys-1)²=y²s²-2ys+1。然後利用關鍵的y²=1，兩式相等。老師只直接說「乘以y平方」，也可以看成在括弧內乘以y。展開後無論是y²s²，或是y⁴，結果都和s²、1是一樣的。結論：可以把式子改寫成
羅吉斯回歸
根據前一單元推導cross entropy error的最後結論，我們可以直接寫出
把三種機器學習方法的錯誤評估函數都改成了ys為基底的表示方式。究竟ys有什麼意義呢?
y用來檢視是否和正確答案同符號(+/-1)。也就是相乘之後，如果是正確的(同符號)則應該為正。因此，他是正確度(correctness)。s是量(score)，越大表示越正確。所以ys的意義就是一個評估預測有多正確的指標(correctness score)。
畫圖
把三種錯誤評估函數的圖畫出來，如下：
線性分類函數很直觀，就不多說了。線性回歸函數本身是一個二次多項式，最小值為ys=1時，表示完全命中，錯誤為0。在ys很小的時候(負值)，函數值會越來越大，雖然會和線性分類的損失落差很大，但還可以接受；有問題的是如果ys很大(正值)，函數值也會越來越大，這點就和線性分類的結果不符合了。因為我們如果要拿線性回歸來做線性分類，只要同符號就是正確，值並不那麼重要。所以，線性回歸大概只有ys靠近1附近的一小段，函數表現比較像線性分類。
那羅吉斯回歸呢?他是單調曲線，ys越大時錯誤就越接近0，反之ys越小，尤其是負值時，函數值很大。為了作圖方便對照，把原本錯誤評估函數的自然對數換底，改成以2為底，改寫成
這個好處是若ys=0時，函數值會剛好是1，可以和線性分類的折點相交。改寫後的函數給他一個名字叫scaled cross entropy。
我們再來看看圖1。scaled cross entropy的曲線始終壓在線性分類的錯誤評估函數上面，用數學式表示就是
等號右邊是原本的cross entropy經過換底的意思。現在，要把E_in(w)帶進來。因為E_in(w)的本質就是err的平均，所以在N一樣的情況下，可以直接改寫
而E_out就是
根據VC bound，
不等式最右邊就是一個複雜項，詳細內容請見第三單元。把式1代進來：
或者，可以用式2.先處理：
然後再用VC bound
做這些要幹嘛呢?要證明如果把cross entropy的E_in做好，線性分類的E_out就會跟著好。這句話翻成白話文就是羅吉斯回歸可以處理線性分類問題。
同理，因為線性回歸的錯誤評估函數曲線也始終都在線性分類的上面，所以上面這段推導也適用於線性回歸，只是其程度寬鬆許多(在值偏差較大時)。結論：線性回歸和羅吉斯回歸都可以用來處理線性分類問題。
處理線性分類問題的小總結
用回歸模型時：
- 利用模型找到w
- g(x)=sign(w^Tx)
三種模型的優缺點：
- 對於線性回歸：
好處：最佳化(optimization)最容易(直接找pseudo-inverse)。
壞處：對於大的|ys|，err值太離散。 - 對於羅吉斯回歸：
好處：最佳化還算容易，err值也比線性回歸較貼近。
壞處：在負的ys區，err值還是離散。 - 對於PLA(即線性分類法)：
好處：對於線性可分的資料有效率，且最精確。
壞處：不是線性可分資料時就不能用了，除非加上口袋演算法(pocket heuristic)。
實務上會用線性回歸快速鎖定w的可能範圍，再用羅吉斯回歸遍訪資料做梯度下降以逼近最佳解。PLA受限於資料必須線性可分，並不是很好使用。
提高羅吉斯回歸的效率?
目前我們在羅吉斯回歸處理梯度時，都是要遍覽全部資料計算才能得到。但每次做梯度下降就要遍覽一次全部資料是相當耗時的，尤其資料量大時更是如此。那有沒有提高效率的做法?
如果不要遍覽全部的資料，那只抽一小部分資料來看呢?這時得到的梯度不是真實的梯度，但也不能說它完全不正確，因為仍然代表了一部分的資料。可以說，如果這個抽取資料的方式是隨機的話，那真實梯度就是隨機梯度和期望值的組合了：
或者也可以說，隨機梯度就是真實梯度加上雜訊，這個雜訊的平均值為0。
隨機梯度下降(stochastic gradient descend)
我們抽資料的時候極端一點，只取一筆。然後假設抽的過程夠多次，這個隨機的次數多，就會貼近真實的梯度。羅吉斯回歸的隨機梯度下降法表示如下：
對照原本的羅吉斯回歸，真實梯度下降版本：
用一筆資料代替全部，所以加總後平均項就移除了。根據在羅吉斯回歸單元討論到的，η是步長，所以它右邊的項是更新的方向。仔細看這個項，最右邊乘上yx，這種更新方法好像在哪裡看過?
沒錯，就是一開始的線性分類(PLA)。
把隨機梯度下降的羅吉斯回歸視為軟性的PLA，但不是絕對的更新/不更新，而是錯得多就更新多一點，錯的少就更新少一點。這樣一來，還不用擔心步長過大帶來的問題。
另一方面，也可以把PLA視為羅吉斯回歸的極端狀況，也就是w^Tx很大時，θ函數的結果接近1。但這樣想的前提是η為1。
那如果改採隨機梯度下降，什麼時候要停止呢?
施主，這個問題要問你自己。
其實沒有絕對的答案，按照剛剛討論的，隨機梯度要能近似真實梯度，有一個必要條件就是採樣夠多。所以只要下降的次數夠多，而梯度似乎不再有變化，就可以合理假設已經逼近最近值了。至於多少才叫夠多，這沒有固定答案，只能靠自己摸索。(其實有一個方法叫early stop，雖然主要是為了避免過度配適，但相對的梯度應該也已經降到某個程度了。過度配適的問題會在後面介紹)
推展到多元分類問題
現在來試看看把二元分類問題的解決方法推廣到多元分類問題上。如果用線性分類的方法，把多元分類拆成重複的二元分類，就會強行把資料分成兩邊，最後形成如下的圖：
這個圖顯示出兩個問題：一個是有些資料被重複劃分到不同區域，另一個則是有資料不被分進任何一類。
換一個方法：利用軟性的分類方式，就是羅吉斯回歸了。除了可以分類之外，還利用機率解決上面兩個問題：如果被重複劃分，就選機率最大的。同時，即使機率再小，也必定有一個分類的機率相對大，就把這筆資料分進去。得到的圖如下：
同時，整合四種分類的式子為
argmax就是取最大者。這個分類器(classifier)也很常出現在深度學習裡面。
One Versus All(OVA) decomposition
現在來介紹兩個常用的手法：第一種是OVA。這是把多分類問題拆成多個「一對多」問題的方法。只要屬於這個分類的都是圈，不屬於這個分類的，全部是叉。
D表示利用上述的原理進行羅吉斯回歸，可以得到一個
然後再利用式6，選出最大的，就是它的歸屬。這樣做的好處是有效率，只要有羅吉斯回歸適用的資料都可以這樣處理。但缺點是萬一資料的分類出現不平均的狀況，例如某一類資料偏少，在判斷時就可能出現問題。因為即使機器全部判錯，但其正確率仍有(N-n)/N，而錯誤率僅n/N，假設極端狀況只有一筆資料屬於該分類的時候…基本上就一定會判錯了。
為了解決這個問題，我們換一個方法。
One Versus One(OVO) decomposition: tournament champion
顧名思義，把多分類問題拆成許多一對一的問題。像擂台賽一樣，選兩個出來單挑。注意在選取分類的同時，也把其他不屬於這兩個分類的資料拿掉。如此一來，分類器就會有C N取2個。
從圖4的下方一排可以知道有6種分類器。現在，假設有一個資料點出現在右上角，根據這六個分類器的判斷，它會分別屬於：方形、方形、方形、菱形、星形、星形。統整這六個分類器，其中前三種是直接和分類方形有關的。最後，這筆資料被分到方形的次數最多，因此將它歸為方形類。
這種作法，有點像分類器投票，又有點像所有的分類進行一個錦標循環賽。在這個例子中，有四種分類代表四個人。單循環賽就是所有人都要跟對手打過一次，所以總共六場比賽。比賽的結果一定分出誰贏誰輸，所以最後可以統整出它贏或輸，根據贏輸的場次也可以判斷它是誰。所以又稱作tornament champion。
它的D式如下：
而最後的投票，或錦標賽選拔，就是
這樣做法的好處，就是在每個分類器運算時資料量反而減少，可以和各種二元分類器結合，比較穩定。但缺點就是分類器數量會變多，儲存空間要比較大，預測時所有分類器要跑一遍。總之，面對大量分類時候，或者擔心資料標籤可能不平衡時，可以考慮使用。
OVA和OVO都會用到多個羅吉斯回歸運算。如果有平行運算的硬體，對於應付這樣的運算方法將會輕鬆且更有效率。
結論
本單元內容較多，前面講到把三種線性分類的模型整合在一起比較，並證明羅吉斯回歸和線性回歸是可以處理線性分類的問題。中間講到利用隨機梯度下降改良羅吉斯回歸的效率。最後，則提到將二元分類推廣至多元分類的運用。
下個單元，將會講到非線性轉換。如何將非線性的資料分布轉成線性，以讓線性分類的演算法可以運用呢?請看下回分曉。
