台灣國立大學機器學習基石.聽課筆記（第十一講）
：Linear Models of Classification 在上一講中，我們了解到線性回歸和邏輯斯蒂回歸一定程度上都可以用于線性二值分類，因為它們對應的錯誤衡量(square error, cross-entropy) 都是“0/1 error” 的上界。
1，Linear Models for Bineary Classification(三個模型的比較)
1.1Error Function分析
本質上講，線性分類（感覺機）、線性回歸、邏輯斯蒂回歸都屬于線性模型，因為它們的核心都是一個線性score 函數：
隻是三個model 對其做了不同處理：
線性分類對s 取符号；線性回歸直接使用s 的值；邏輯斯蒂回歸将s 映射到(0,1) 區間。 為了更友善地比較三個model，對其error function 做一定處理：
這樣，三個error function 都變成隻有y*s 這一項“變量”。
通過曲線來比較三個error function （注意：cross-entropy 變為以2為底的scaled cross-entropy）
很容易通過比較三個error function 來得到分類的0/1 error 的上界：
這樣，我們就了解了通過邏輯斯蒂回歸或線性回歸進行分類的意義。
1.2優缺點比較
線性分類(PLA)、線性回歸、邏輯斯蒂回歸的優缺點比較：
（1）PLA
優點：在資料線性可分時高效且準确。
缺點：隻有在資料線性可分時才可行，否則需要借助POCKET 算法（沒有理論保證）。
（2）線性回歸
優點：最簡單的優化（直接利用矩陣運算工具）
缺點：y*s 的值較大時，與0/1 error 相差較大(loose bound)。
（3）邏輯斯蒂回歸
優點：比較容易優化（梯度下降）
缺點：y*s 是非常小的負數時，與0/1 error 相差較大。
實際中，邏輯斯蒂回歸用于分類的效果優于線性回歸的方法和POCKET 算法。線性回歸得到的結果w 有時作為其他幾種算法的初值。
2，随機梯度下降 (Stochastic Gradient Descent)
傳統的随機梯度下降更新方法：
每次更新都需要周遊所有data，當資料量太大或者一次無法擷取全部資料時，這種方法并不可行。
我們希望用更高效的方法解決這個問題，基本思路是：隻通過一個随機選取的資料(xn,yn) 來擷取“梯度”，以此對w 進行更新。這種優化方法叫做随機梯度下降。
這種方法在統計上的意義是：進行足夠多的更新後，平均的随機梯度與平均的真實梯度近似相等。
注意：在這種優化方法中，一般設定一個足夠大的疊代次數，算法執行這麼多的次數時我們就認為已經收斂。（防止不收斂的情況）
3，多類别分類(multiclass classification)
與二值分類不同的是，我們的target有多個類别(>2)。
一種直覺的解決方法是将其轉化為多輪的二值分類問題：任意選擇一個類作為+1，其他類都看做-1，在此條件下對原資料進行訓練，得到w；經過多輪訓練之後，得到多個w。對于某個x，将其分到可能性最大的那個類。（例如邏輯斯蒂回歸對于x 屬于某個類會有一個機率估計）如果target 是k個類标簽，我們需要k 輪訓練，得到k 個w。
這種方法叫做One-Versus-All (OVA)：
它的最大缺點是，目标類很多時，每輪訓練面對的資料往往非常不平衡(unbalanced)，會嚴重影響訓練準确性。multinomial(‘coupled’)logistic regression 考慮了這個問題，感興趣的話自學下吧。
4，另一種多值分類方法
這種方法叫做One-Versus-One(OVO)，對比上面的OVA 方法。
基本方法：每輪訓練時，任取兩個類别，一個作為+1，另一個作為-1，其他類别的資料不考慮，這樣，同樣用二值分類的方法進行訓練；目标類有k個時，需要k*(k-1)/2 輪訓練，得到 k*(k-1)/2 個分類器。
預測：對于某個x，用訓練得到的k*(k-1)/2 個分類器分别對其進行預測，哪個類别被預測的次數最多，就把它作為最終結果。即通過“循環賽”的方式來決定哪個“類”是冠軍。
顯然，這種方法的優點是每輪訓練面對更少、更平衡的資料，而且可以用任意二值分類方法進行訓練；缺點是需要的輪數太多(k*(k-1)/2)，占用更多的存儲空間，而且預測也更慢。
OVA和OVO方法的思想都很簡單，可以作為以後面對多值分類問題時的備選方案，并且可以為我們提供解決問題的思路。