# 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問題。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale