上一節課，我們介紹了Logistic Regression問題，建立cross-entropy error，并提出使用梯度下降算法gradient descnt來獲得最好的logistic hypothesis。本節課繼續介紹使用線性模型來解決分類問題。
之前介紹幾種線性模型都有一個共同點，就是都有樣本特征x的權重運算，我們引入一個線性得分函數s：
s=wTx
三種線性模型，第一種是linear classification。線性分類模型的hypothesis為h(x)=sign(s),取值範圍為{-1,+1}兩個值，它的err是0/1的，是以對應的E_{in}(w)是離散的，并不好解，這是個NP-hard問題。第二種是linear regression。線性回歸模型的hypothesis為h(x)=s，取值範圍為整個實數空間，它的err是squared的，是以對應的E_{in}(w)是開口向上的二次曲線，其解是closed-form的，直接用線性最小二乘法求解即可。第三種是logistic regression。邏輯回歸模型的hypothesis為h(x)=\theta(s)，取值範圍為(-1,1)之間，它的err是cross-entropy的，所有對應的E_{in}(w)是平滑的凸函數，可以使用梯度下降算法求最小值。
從上圖中，我們發現，linear regression和logistic regression的error function都有最小解。那麼可不可以用這兩種方法來求解linear classification問題呢？下面，我們來對這三種模型的error function進行分析，看看它們之間有什麼聯系。
對于linear classification，它的error function可以寫成： err_{0/1}(s,y)=|sign(s)\neq y|=|sign(ys)\neq 1| 對于linear regression，它的error function可以寫成： err_{SQR}(s,y)=(s-y)^2=(ys-1)^2 對于logistic regression，它的error function可以寫成： err_{CE}(s,y)=ln(1+exp(-ys)) 上述三種模型的error function都引入了ys變量，那麼ys的實體意義是什麼？ys就是指分類的正确率得分，其值越大越好，得分越高。
下面，我們用圖形化的方式來解釋三種模型的error function到底有什麼關系：
從上圖中可以看出，ys是橫坐标軸，err_{0/1}是呈階梯狀的，在ys>0時，err_{0/1}恒取最小值0。err_{SQR}呈抛物線形式，在ys=1時，取得最小值，且在ys=1左右很小區域内，err_{0/1}和err_{SQR}近似。err_{CE}是呈指數下降的單調函數，ys越大，其值越小。同樣在ys=1左右很小區域内，err_{0/1}和err_{CE}近似。但是我們發現err_{CE}并不是始終在err_{0/1}之上，是以為了計算讨論友善，我們把err_{CE}做幅值上的調整，引入err_{SCE}=log_2(1+exp(-ys))=\frac1{ln2}err_{CE}，這樣能保證err_{SCE}始終在err_{0/1}上面，如下圖所示：
由上圖可以看出： err_{0/1}(s,y)\leq err_{SCE}(s,y)=\frac1{ln2}err_{CE}(s,y)
E_{in}^{0/1}(w)\leq E_{in}^{SCE}(w)=\frac1{ln2}E_{in}^{CE}(w) E_{out}^{0/1}(w)\leq E_{out}^{SCE}(w)=\frac1{ln2}E_{out}^{CE}(w) 那麼由VC理論可以知道： 從0/1出發：
E_{out}^{0/1}(w)\leq E_{in}^{0/1}(w)+\Omega^{0/1}\leq \frac1{ln2}E_{in}^{CE}(w)+\Omega^{0/1}
從CE出發： E_{out}^{0/1}(w)\leq \frac1{ln2}E_{out}^{CE}(w)\leq \frac1{ln2}E_{in}^{CE}(w)+\frac1{ln2}\Omega^{CE}
通過上面的分析，我們看到err 0/1是被限定在一個上界中。這個上界是由logistic regression模型的error function決定的。而linear regression其實也是linear classification的一個upper bound，隻是随着sy偏離1的位置越來越遠，linear regression的error function偏差越來越大。綜上所述，linear regression和logistic regression都可以用來解決linear classification的問題。
下圖列舉了PLA、linear regression、logistic regression模型用來解linear classification問題的優點和缺點。通常，我們使用linear regression來獲得初始化的w0w_0，再用logistic regression模型進行最優化解。
之前介紹的PLA算法和logistic regression算法，都是用到了疊代操作。PLA每次疊代隻會更新一個點，它每次疊代的時間複雜度是O(1)；而logistic regression每次疊代要對所有N個點都進行計算，它的每時間複雜度是O(N)。為了提高logistic regression中gradient descent算法的速度，可以使用另一種算法：随機梯度下降算法(Stochastic Gradient Descent)。
随機梯度下降算法每次疊代隻找到一個點，計算該點的梯度，作為我們下一步更新w的依據。這樣就保證了每次疊代的計算量大大減小，我們可以把整體的梯度看成這個随機過程的一個期望值。
随機梯度下降可以看成是真實的梯度加上均值為零的随機噪聲方向。單次疊代看，好像會對每一步找到正确梯度方向有影響，但是整體期望值上看，與真實梯度的方向沒有差太多，同樣能找到最小值位置。随機梯度下降的優點是減少計算量，提高運算速度，而且便于online學習；缺點是不夠穩定，每次疊代并不能保證按照正确的方向前進，而且達到最小值需要疊代的次數比梯度下降算法一般要多。
對于logistic regression的SGD，它的表達式為： w_{t+1}\leftarrow w_t+\eta\theta(-y_nw_t^Tx_n)(y_nx_n)
我們發現，SGD與PLA的疊代公式有類似的地方，如下圖所示：
我們把SGD logistic regression稱之為’soft’ PLA，因為PLA隻對分類錯誤的點進行修正，而SGD logistic regression每次疊代都會進行或多或少的修正。另外，當η=1，且w_t^Tx_n足夠大的時候，PLA近似等于SGD。
除此之外，還有兩點需要說明：1、SGD的終止疊代條件。沒有統一的終止條件，一般讓疊代次數足夠多；2、學習速率η。η的取值是根據實際情況來定的，一般取值0.1就可以了。
之前我們一直講的都是二分類問題，本節主要介紹多分類問題，通過linear classification來解決。假設平面上有四個類，分别是正方形、菱形、三角形和星形，如何進行分類模型的訓練呢？
首先我們可以想到這樣一個辦法，就是先把正方形作為正類，其他三種形狀都是負類，即把它當成一個二分類問題，通過linear classification模型進行訓練，得出平面上某個圖形是不是正方形，且隻有{-1,+1}兩種情況。然後再分别以菱形、三角形、星形為正類，進行二進制分類。這樣進行四次二分類之後，就完成了這個多分類問題。
但是，這樣的二分類會帶來一些問題，因為我們隻用{-1，+1}兩個值來标記，那麼平面上某些可能某些區域都被上述四次二分類模型判斷為負類，即不屬于四類中的任何一類；也可能會出現某些區域同時被兩個類甚至多個類同時判斷為正類，比如某個區域又判定為正方形又判定為菱形。那麼對于這種情況，我們就無法進行多類别的準确判斷，是以對于多類别，簡單的binary classification不能解決問題。
針對這種問題，我們可以使用另外一種方法來解決：soft軟性分類，即不用{-1，+1}這種binary classification，而是使用logistic regression，計算某點屬于某類的機率、可能性，去機率最大的值為那一類就好。
soft classification的處理過程和之前類似，同樣是分别令某類為正，其他三類為負，不同的是得到的是機率值，而不是{-1，+1}。最後得到某點分别屬于四類的機率，取最大機率對應的哪一個類别就好。效果如下圖所示：
這種多分類的處理方式，我們稱之為One-Versus-All(OVA) Decomposition。這種方法的優點是簡單高效，可以使用logistic regression模型來解決；缺點是如果資料類别很多時，那麼每次二分類問題中，正類和負類的數量差别就很大，資料不平衡unbalanced，這樣會影響分類效果。但是，OVA還是非常常用的一種多分類算法。
上一節，我們介紹了多分類算法OVA，但是這種方法存在一個問題，就是當類别k很多的時候，造成正負類資料unbalanced，會影響分類效果，表現不好。現在，我們介紹另一種方法來解決當k很大時，OVA帶來的問題。
這種方法呢，每次隻取兩類進行binary classification，取值為{-1，+1}。假如k=4，那麼總共需要進行C_4^2=6次binary classification。那麼，六次分類之後，如果平面有個點，有三個分類器判斷它是正方形，一個分類器判斷是菱形，另外兩個判斷是三角形，那麼取最多的那個，即判斷它屬于正方形，我們的分類就完成了。這種形式就如同k個足球對進行單循環的比賽，每場比賽都有一個隊赢，一個隊輸，赢了得1分，輸了得0分。那麼總共進行了C_k^2次的比賽，最終取得分最高的那個隊就可以了。
這種差別于OVA的多分類方法叫做One-Versus-One(OVO)。這種方法的優點是更加高效，因為雖然需要進行的分類次數增加了，但是每次隻需要進行兩個類别的比較，也就是說單次分類的數量減少了。而且一般不會出現資料unbalanced的情況。缺點是需要分類的次數多，時間複雜度和空間複雜度可能都比較高。
本節課主要介紹了分類問題的三種線性模型：linear classification、linear regression和logistic regression。首先介紹了這三種linear models都可以來做binary classification。然後介紹了比梯度下降算法更加高效的SGD算法來進行logistic regression分析。最後講解了兩種多分類方法，一種是OVA，另一種是OVO。這兩種方法各有優缺點，當類别數量k不多的時候，建議選擇OVA，以減少分類次數。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習基石》課程