# 5 -- Kernel Logistic Regression 上節課我們主要介紹了Soft-Margin SVM，即如果允許有分類錯誤的點存在，那么在原來的Hard-Margin SVM中添加新的懲罰因子C，修正原來的公式，得到新的值。最終的到的有個上界，上界就是C。Soft-Margin SVM權衡了large-margin和error point之前的關系，目的是在盡可能犯更少錯誤的前提下，得到最大分類邊界。本節課將把Soft-Margin SVM和我們之前介紹的Logistic Regression聯系起來，研究如何使用kernel技巧來解決更多的問題。 ### **Soft-Margin SVM as Regularized Model** 先復習一下我們已經介紹過的內容，我們最早開始講了Hard-Margin Primal的數學表達式，然后推導了Hard-Margin Dual形式。后來，為了允許有錯誤點的存在（或者noise），也為了避免模型過于復雜化，造成過擬合，我們建立了Soft-Margin Primal的數學表達式，并引入了新的參數C作為權衡因子，然后也推導了其Soft-Margin Dual形式。因為Soft-Margin Dual SVM更加靈活、便于調整參數，所以在實際應用中，使用Soft-Margin Dual SVM來解決分類問題的情況更多一些。  Soft-Margin Dual SVM有兩個應用非常廣泛的工具包，分別是Libsvm和Liblinear。 Libsvm和Liblinear都是國立臺灣大學的Chih-Jen Lin博士開發的，Chih-Jen Lin的個人網站為：[Welcome to Chih-Jen Lin’s Home Page](http://www.csie.ntu.edu.tw/~cjlin/index.html) 下面我們再來回顧一下Soft-Margin SVM的主要內容。我們的出發點是用來表示margin violation，即犯錯值的大小，沒有犯錯對應的。然后將有條件問題轉化為對偶dual形式，使用QP來得到最佳化的解。 從另外一個角度來看，描述的是點 距離的邊界有多遠。第一種情況是violating margin，即不滿足。那么可表示為：。第二種情況是not violating margin，即點 在邊界之外，滿足的條件，此時。我們可以將兩種情況整合到一個表達式中，對任意點：  上式表明，如果有voilating margin，則，；如果not violating margin，則，。整合之后，我們可以把Soft-Margin SVM的最小化問題寫成如下形式：  經過這種轉換之后，表征犯錯誤值大小的變量就被消去了，轉而由一個max操作代替。  為什么要將把Soft-Margin SVM轉換為這種unconstrained form呢？我們再來看一下轉換后的形式，其中包含兩項，第一項是w的內積，第二項關于y和w，b，z的表達式，似乎有點像一種錯誤估計，則類似這樣的形式：  看到這樣的形式我們應該很熟悉，因為之前介紹的L2 Regularization中最優化問題的表達式跟這個是類似的：   這里提一下，既然unconstrained form SVM與L2 Regularization的形式是一致的，而且L2 Regularization的解法我們之前也介紹過，那么為什么不直接利用這種方法來解決unconstrained form SVM的問題呢？有兩個原因。一個是這種無條件的最優化問題無法通過QP解決，即對偶推導和kernel都無法使用；另一個是這種形式中包含的max()項可能造成函數并不是處處可導，這種情況難以用微分方法解決。 我們在第一節課中就介紹過Hard-Margin SVM與Regularization Model是有關系的。Regularization的目標是最小化，條件是，而Hard-Margin SVM的目標是最小化，條件是，即它們的最小化目標和限制條件是相互對調的。對于L2 Regularization來說，條件和最優化問題結合起來，整體形式寫成：  而對于Soft-Margin SVM來說，條件和最優化問題結合起來，整體形式寫成：   通過對比，我們發現L2 Regularization和Soft-Margin SVM的形式是相同的，兩個式子分別包含了參數和C。Soft-Margin SVM中的large margin對應著L2 Regularization中的short w，也就是都讓hyperplanes更簡單一些。我們使用特別的來代表可以容忍犯錯誤的程度，即soft margin。L2 Regularization中的和Soft-Margin SVM中的C也是相互對應的，越大，w會越小，Regularization的程度就越大；C越小，會越大，相應的margin就越大。所以說增大C，或者減小，效果是一致的，Large-Margin等同于Regularization，都起到了防止過擬合的作用。  建立了Regularization和Soft-Margin SVM的關系，接下來我們將嘗試看看是否能把SVM作為一個regularized的模型進行擴展，來解決其它一些問題。 ### **SVM versus Logistic Regression** 上一小節，我們已經把Soft-Margin SVM轉換成無條件的形式：  上式中第二項的倍設置為。下面我們來看看與之前再二元分類中介紹過的有什么關系。 對于，它的linear score ，當時，；當時，，呈階梯狀，如下圖所示。而對于，當時，；當時，，呈折線狀，如下圖所示，通常把稱為hinge error measure。比較兩條error曲線，我們發現始終在的上面，則可作為的上界。所以，可以使用來代替，解決二元線性分類問題，而且是一個凸函數，使它在最佳化問題中有更好的性質。  緊接著，我們再來看一下logistic regression中的error function。邏輯回歸中，，當ys=0時，。它的err曲線如下所示。  很明顯，也是的上界，而與也是比較相近的。因為當ys趨向正無窮大的時候，和都趨向于零；當ys趨向負無窮大的時候，和都趨向于正無窮大。正因為二者的這種相似性，我們可以把SVM看成是L2-regularized logistic regression。 總結一下，我們已經介紹過幾種Binary Classification的Linear Models，包括PLA，Logistic Regression和Soft-Margin SVM。PLA是相對簡單的一個模型，對應的是，通過不斷修正錯誤的點來獲得最佳分類線。它的優點是簡單快速，缺點是只對線性可分的情況有用，線性不可分的情況需要用到pocket算法。Logistic Regression對應的是，通常使用GD/SGD算法求解最佳分類線。它的優點是凸函數便于最優化求解，而且有regularization作為避免過擬合的保證；缺點是作為的上界，當ys很小（負值）時，上界變得更寬松，不利于最優化求解。Soft-Margin SVM對應的是，通常使用QP求解最佳分類線。它的優點和Logistic Regression一樣，凸優化問題計算簡單而且分類線比較“粗壯”一些；缺點也和Logistic Regression一樣，當ys很小（負值）時，上界變得過于寬松。其實，Logistic Regression和Soft-Margin SVM都是在最佳化的上界而已。  至此，可以看出，求解regularized logistic regression的問題等同于求解soft-margin SVM的問題。反過來，如果我們求解了一個soft-margin SVM的問題，那這個解能否直接為regularized logistic regression所用？來預測結果是正類的幾率是多少，就像regularized logistic regression做的一樣。我們下一小節將來解答這個問題。 ### **SVM for Soft Binary Classification** 接下來，我們探討如何將SVM的結果應用在Soft Binary Classification中，得到是正類的概率值。 第一種簡單的方法是先得到SVM的解，然后直接代入到logistic regression中，得到。這種方法直接使用了SVM和logistic regression的相似性，一般情況下表現還不錯。但是，這種形式過于簡單，與logistic regression的關聯不大，沒有使用到logistic regression中好的性質和方法。 第二種簡單的方法是同樣先得到SVM的解，然后把作為logistic regression的初始值，再進行迭代訓練修正，速度比較快，最后，將得到的b和w代入到g(x)中。這種做法有點顯得多此一舉，因為并沒有比直接使用logistic regression快捷多少。  這兩種方法都沒有融合SVM和logistic regression各自的優勢，下面構造一個模型，融合了二者的優勢。構造的模型g(x)表達式為：  與上述第一種簡單方法不同，我們額外增加了放縮因子A和平移因子B。首先利用SVM的解來構造這個模型，放縮因子A和平移因子B是待定系數。然后再用通用的logistic regression優化算法，通過迭代優化，得到最終的A和B。一般來說，如果較為合理的話，滿足A>0且。  那么，新的logistic regression表達式為：  這個表達式看上去很復雜，其實其中的已經在SVM中解出來了，實際上的未知參數只有A和B兩個。歸納一下，這種Probabilistic SVM的做法分為三個步驟：  這種soft binary classifier方法得到的結果跟直接使用SVM classifier得到的結果可能不一樣，這是因為我們引入了系數A和B。一般來說，soft binary classifier效果更好。至于logistic regression的解法，可以選擇GD、SGD等等。 ### **Kernel Logistic Regression** 上一小節我們介紹的是通過kernel SVM在z空間中求得logistic regression的近似解。如果我們希望直接在z空間中直接求解logistic regression，通過引入kernel，來解決最優化問題，又該怎么做呢？SVM中使用kernel，轉化為QP問題，進行求解，但是logistic regression卻不是個QP問題，看似好像沒有辦法利用kernel來解決。 我們先來看看之前介紹的kernel trick為什么會work，kernel trick就是把z空間的內積轉換到x空間中比較容易計算的函數。如果w可以表示為z的線性組合，即的形式，那么乘積項，即其中包含了z的內積。也就是w可以表示為z的線性組合是kernel trick可以work的關鍵。 我們之前介紹過SVM、PLA包擴logistic regression都可以表示成z的線性組合，這也提供了一種可能，就是將kernel應用到這些問題中去，簡化z空間的計算難度。  有這樣一個理論，對于L2-regularized linear model，如果它的最小化問題形式為如下的話，那么最優解。  下面給出簡單的證明，假如最優解。其中，和分別是平行z空間和垂直z空間的部分。我們需要證明的是。利用反證法，假如，考慮與的比較。第一步先比較最小化問題的第二項：，即第二項是相等的。然后第二步比較第一項：，即對應的L2-regularized linear model值要比大，這就說明并不是最優解，從而證明必然等于零，即一定成立，一定可以寫成z的線性組合形式。  經過證明和分析，我們得到了結論是任何L2-regularized linear model都可以使用kernel來解決。 現在，我們來看看如何把kernel應用在L2-regularized logistic regression上。上面我們已經證明了一定可以寫成z的線性組合形式，即。那么我們就無需一定求出，而只要求出其中的就行了。怎么求呢？直接將代入到L2-regularized logistic regression最小化問題中，得到：   上式中，所有的w項都換成來表示了，變成了沒有條件限制的最優化問題。我們把這種問題稱為kernel logistic regression，即引入kernel，將求w的問題轉換為求的問題。 從另外一個角度來看Kernel Logistic Regression（KLR）：  上式中log項里的可以看成是變量和的內積。上式第一項中的可以看成是關于的正則化項。所以，KLR是的線性組合，其中包含了kernel內積項和kernel regularizer。這與SVM是相似的形式。 但值得一提的是，KLR中的與SVM中的是有區別的。SVM中的大部分為零，SV的個數通常是比較少的；而KLR中的通常都是非零值。 ### **總結** 本節課主要介紹了Kernel Logistic Regression。首先把Soft-Margin SVM解釋成Regularized Model，建立二者之間的聯系，其實Soft-Margin SVM就是一個L2-regularization，對應著hinge error messure。然后利用它們之間的相似性，討論了如何利用SVM的解來得到Soft Binary Classification。方法是先得到SVM的解，再在logistic regression中引入參數A和B，迭代訓練，得到最佳解。最后介紹了Kernel Logistic Regression，證明L2-regularized logistic regression中，最佳解一定可以寫成z的線性組合形式，從而可以將kernel引入logistic regression中，使用kernel思想在z空間直接求解L2-regularized logistic regression問題。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程