名詞：
slack 松弛的
violate 違反
margin 邊界
regularization 正則化
hinge 鉸鏈（連接兩個門） hinge error messure 细办？？丘损？
maxnum likelihood 最大似然
hinge error messure

轉(zhuǎn)自：https://blog.csdn.net/red_stone1/article/details/74506323

Kernel Logistic Regression

上節(jié)課我們主要介紹了Soft-Margin SVM，即如果允許有分類錯誤的點存在工扎，那么在原來的Hard-Margin SVM中添加新的懲罰因子C徘钥，修正原來的公式，得到新的αn值肢娘。最終的到的αn有個上界呈础，上界就是C。Soft-Margin SVM權(quán)衡了large-margin和error point之前的關系橱健，目的是在盡可能犯更少錯誤的前提下而钞，得到最大分類邊界。本節(jié)課將把Soft-Margin SVM和我們之前介紹的Logistic Regression聯(lián)系起來拘荡，研究如何使用kernel技巧來解決更多的問題臼节。

Soft-Margin SVM as Regularized Model

先復習一下我們已經(jīng)介紹過的內(nèi)容，我們最早開始講了Hard-Margin Primal的數(shù)學表達式，然后推導了Hard-Margin Dual形式官疲。后來袱结，為了允許有錯誤點的存在（或者noise），也為了避免模型過于復雜化途凫，造成過擬合垢夹，我們建立了Soft-Margin Primal的數(shù)學表達式，并引入了新的參數(shù)C作為權(quán)衡因子维费，然后也推導了其Soft-Margin Dual形式果元。因為Soft-Margin Dual SVM更加靈活、便于調(diào)整參數(shù)犀盟，所以在實際應用中而晒，使用Soft-Margin Dual SVM來解決分類問題的情況更多一些。

image.png

Soft-Margin Dual SVM有兩個應用非常廣泛的工具包阅畴，分別是Libsvm和Liblinear倡怎。 Libsvm和Liblinear都是國立臺灣大學的Chih-Jen Lin博士開發(fā)的，Chih-Jen Lin的個人網(wǎng)站為：Welcome to Chih-Jen Lin’s Home Page

下面我們再來回顧一下Soft-Margin SVM的主要內(nèi)容贱枣。我們的出發(fā)點是用ξn來表示margin violation监署，即犯錯值的大小，沒有犯錯對應的ξn=0纽哥。然后將有條件問題轉(zhuǎn)化為對偶dual形式钠乏，使用QP來得到最佳化的解。從另外一個角度來看春塌，ξn描述的是點(xn,yn) 距離yn(wTzn+b)=1的邊界有多遠晓避。第一種情況是violating margin，即不滿足yn(wTzn+b)≥1只壳。那么ξn可表示為：ξn=1?yn(wTzn+b)>0俏拱。第二種情況是not violating margin，即點(xn,yn) 在邊界之外吕世，滿足yn(wTzn+b)≥1的條件彰触，此時ξn=0。我們可以將兩種情況整合到一個表達式中命辖，對任意點：

ξn=max(1?yn(wTzn+b),0)

上式表明况毅，如果有voilating margin，則1?yn(wTzn+b)>0尔艇，ξn=1?yn(wTzn+b)尔许；如果not violating margin，則1?yn(wTzn+b)<0终娃，ξn=0味廊。整合之后，我們可以把Soft-Margin SVM的最小化問題寫成如下形式：

12wTw+C∑n=1Nmax(1?yn(wTzn+b),0)

經(jīng)過這種轉(zhuǎn)換之后，表征犯錯誤值大小的變量ξn就被消去了余佛，轉(zhuǎn)而由一個max操作代替柠新。

image.png

為什么要將把Soft-Margin SVM轉(zhuǎn)換為這種unconstrained form呢？我們再來看一下轉(zhuǎn)換后的形式辉巡，其中包含兩項恨憎，第一項是w的內(nèi)積，第二項關于y和w郊楣，b憔恳，z的表達式，似乎有點像一種錯誤估計err^净蚤，則類似這樣的形式：

min 12wTw+C∑err^

看到這樣的形式我們應該很熟悉钥组，因為之前介紹的L2 Regularization中最優(yōu)化問題的表達式跟這個是類似的：

min λNwTw+1N∑err

image.png

這里提一下，既然unconstrained form SVM與L2 Regularization的形式是一致的今瀑，而且L2 Regularization的解法我們之前也介紹過程梦，那么為什么不直接利用這種方法來解決unconstrained form SVM的問題呢？有兩個原因放椰。一個是這種無條件的最優(yōu)化問題無法通過QP解決作烟，即對偶推導和kernel都無法使用；另一個是這種形式中包含的max()項可能造成函數(shù)并不是處處可導砾医，這種情況難以用微分方法解決。

我們在第一節(jié)課中就介紹過Hard-Margin SVM與Regularization Model是有關系的衣厘。Regularization的目標是最小化Ein如蚜，條件是wTw≤C，而Hard-Margin SVM的目標是最小化wTw影暴，條件是Ein=0错邦，即它們的最小化目標和限制條件是相互對調(diào)的。對于L2 Regularization來說型宙，條件和最優(yōu)化問題結(jié)合起來撬呢，整體形式寫成：

λNwTw+Ein

而對于Soft-Margin SVM來說，條件和最優(yōu)化問題結(jié)合起來妆兑，整體形式寫成：

12wTw+CNEin^

image.png

通過對比魂拦，我們發(fā)現(xiàn)L2 Regularization和Soft-Margin SVM的形式是相同的，兩個式子分別包含了參數(shù)λ和C搁嗓。Soft-Margin SVM中的large margin對應著L2 Regularization中的short w芯勘，也就是都讓hyperplanes更簡單一些。我們使用特別的err^來代表可以容忍犯錯誤的程度腺逛，即soft margin荷愕。L2 Regularization中的λ和Soft-Margin SVM中的C也是相互對應的，λ越大，w會越小安疗，Regularization的程度就越大抛杨；C越小，Ein^會越大荐类，相應的margin就越大蝶桶。所以說增大C，或者減小λ掉冶，效果是一致的真竖，Large-Margin等同于Regularization，都起到了防止過擬合的作用厌小。

image.png

建立了Regularization和Soft-Margin SVM的關系恢共，接下來我們將嘗試看看是否能把SVM作為一個regularized的模型進行擴展，來解決其它一些問題璧亚。

SVM versus Logistic Regression

上一小節(jié)讨韭，我們已經(jīng)把Soft-Margin SVM轉(zhuǎn)換成無條件的形式：

image.png

上式中第二項的max(1?yn(wTzn+b),0)倍設置為err^{。下面我們來看看err}與之前再二元分類中介紹過的err0/1有什么關系癣蟋。對于err0/1透硝，它的linear score s=wTzn+b，當ys≥0時疯搅，err0/1=0濒生；當ys<0時，err0/1=1幔欧，呈階梯狀罪治，如下圖所示。而對于err^{礁蔗，當ys≥0時觉义，err0/1=0；當ys<0時浴井，err0/1=1?ys晒骇，呈折線狀，如下圖所示磺浙，通常把err}svm稱為hinge error measure洪囤。比較兩條error曲線，我們發(fā)現(xiàn)err^{svm始終在err0/1的上面屠缭，則err}svm可作為err0/1的上界箍鼓。所以，可以使用err^{svm來代替err0/1呵曹，解決二元線性分類問題款咖，而且err}svm是一個凸函數(shù)何暮，使它在最佳化問題中有更好的性質(zhì)。

image.png

緊接著铐殃，我們再來看一下logistic regression中的error function海洼。邏輯回歸中，errsce=log2(1+exp(?ys))富腊，當ys=0時坏逢，errsce=1。它的err曲線如下所示赘被。

image.png

很明顯是整，errsce也是err0/1的上界，而errsce與err^{svm也是比較相近的民假。因為當ys趨向正無窮大的時候浮入，errsce和err}svm都趨向于零；當ys趨向負無窮大的時候羊异，errsce和err^svm都趨向于正無窮大事秀。正因為二者的這種相似性，我們可以把SVM看成是L2-regularized logistic regression野舶。

總結(jié)一下易迹，我們已經(jīng)介紹過幾種Binary Classification的Linear Models，包括PLA平道，Logistic Regression和Soft-Margin SVM睹欲。PLA是相對簡單的一個模型，對應的是err0/1巢掺，通過不斷修正錯誤的點來獲得最佳分類線句伶。它的優(yōu)點是簡單快速，缺點是只對線性可分的情況有用陆淀，線性不可分的情況需要用到pocket算法。Logistic Regression對應的是errsce先嬉，通常使用GD/SGD算法求解最佳分類線轧苫。它的優(yōu)點是凸函數(shù)errsce便于最優(yōu)化求解，而且有regularization作為避免過擬合的保證疫蔓；缺點是errsce作為err0/1的上界含懊，當ys很小（負值）時衅胀，上界變得更寬松岔乔，不利于最優(yōu)化求解。Soft-Margin SVM對應的是err^svm滚躯，通常使用QP求解最佳分類線雏门。它的優(yōu)點和Logistic Regression一樣嘿歌，凸優(yōu)化問題計算簡單而且分類線比較“粗壯”一些；缺點也和Logistic Regression一樣茁影，當ys很兄娴邸（負值）時，上界變得過于寬松募闲。其實步脓，Logistic Regression和Soft-Margin SVM都是在最佳化err0/1的上界而已。

image.png

至此浩螺，可以看出靴患，求解regularized logistic regression的問題等同于求解soft-margin SVM的問題。反過來要出，如果我們求解了一個soft-margin SVM的問題鸳君，那這個解能否直接為regularized logistic regression所用？來預測結(jié)果是正類的幾率是多少厨幻，就像regularized logistic regression做的一樣相嵌。我們下一小節(jié)將來解答這個問題。

SVM for Soft Binary Classification

接下來况脆，我們探討如何將SVM的結(jié)果應用在Soft Binary Classification中饭宾，得到是正類的概率值。

第一種簡單的方法是先得到SVM的解(bsvm,wsvm)格了，然后直接代入到logistic regression中看铆，得到g(x)=θ(wTsvmx+bsvm)。這種方法直接使用了SVM和logistic regression的相似性盛末，一般情況下表現(xiàn)還不錯弹惦。但是，這種形式過于簡單悄但，與logistic regression的關聯(lián)不大棠隐，沒有使用到logistic regression中好的性質(zhì)和方法。
第二種簡單的方法是同樣先得到SVM的解(bsvm,wsvm)檐嚣，然后把(bsvm,wsvm)作為logistic regression的初始值助泽，再進行迭代訓練修正，速度比較快嚎京，最后嗡贺，將得到的b和w代入到g(x)中。這種做法有點顯得多此一舉鞍帝，因為并沒有比直接使用logistic regression快捷多少诫睬。

image.png

這兩種方法都沒有融合SVM和logistic regression各自的優(yōu)勢，下面構(gòu)造一個模型帕涌，融合了二者的優(yōu)勢摄凡。構(gòu)造的模型g(x)表達式為：

g(x)=θ(A?(wTsvmΦ(x)+bsvm)+B)

與上述第一種簡單方法不同续徽，我們額外增加了放縮因子A和平移因子B。首先利用SVM的解(bsvm,wsvm)來構(gòu)造這個模型架谎，放縮因子A和平移因子B是待定系數(shù)炸宵。然后再用通用的logistic regression優(yōu)化算法，通過迭代優(yōu)化谷扣，得到最終的A和B土全。一般來說，如果(bsvm,wsvm)較為合理的話会涎，滿足A>0且B≈0裹匙。

image.png

那么，新的logistic regression表達式為：

image.png

這個表達式看上去很復雜末秃，其實其中的(bsvm,wsvm)已經(jīng)在SVM中解出來了概页，實際上的未知參數(shù)只有A和B兩個。歸納一下练慕，這種Probabilistic SVM的做法分為三個步驟：

image.png

這種soft binary classifier方法得到的結(jié)果跟直接使用SVM classifier得到的結(jié)果可能不一樣惰匙，這是因為我們引入了系數(shù)A和B。一般來說铃将，soft binary classifier效果更好项鬼。至于logistic regression的解法，可以選擇GD劲阎、SGD等等绘盟。

Kernel Logistic Regression

上一小節(jié)我們介紹的是通過kernel SVM在z空間中求得logistic regression的近似解。如果我們希望直接在z空間中直接求解logistic regression悯仙，通過引入kernel龄毡，來解決最優(yōu)化問題，又該怎么做呢锡垄？SVM中使用kernel沦零，轉(zhuǎn)化為QP問題，進行求解货岭，但是logistic regression卻不是個QP問題蠢终，看似好像沒有辦法利用kernel來解決。

我們先來看看之前介紹的kernel trick為什么會work茴她，kernel trick就是把z空間的內(nèi)積轉(zhuǎn)換到x空間中比較容易計算的函數(shù)。如果w可以表示為z的線性組合程奠，即w?=∑Nn=1βnzn的形式丈牢，那么乘積項wT?z=∑Nn=1βnzTnz=∑Nn=1βnK(xn,x)，即其中包含了z的內(nèi)積瞄沙。也就是w可以表示為z的線性組合是kernel trick可以work的關鍵己沛。

我們之前介紹過SVM慌核、PLA包擴logistic regression都可以表示成z的線性組合，這也提供了一種可能申尼，就是將kernel應用到這些問題中去垮卓，簡化z空間的計算難度。

image.png

有這樣一個理論师幕，對于L2-regularized linear model粟按，如果它的最小化問題形式為如下的話，那么最優(yōu)解w?=∑Nn=1βnzn霹粥。

image.png

下面給出簡單的證明灭将，假如最優(yōu)解w?=w||+w⊥。其中后控，w||和w⊥分別是平行z空間和垂直z空間的部分庙曙。我們需要證明的是w⊥=0。利用反證法浩淘，假如w⊥≠0捌朴，考慮w?與w||的比較。第一步先比較最小化問題的第二項：err(y,wT?zn)=err(yn,(w||+w⊥)Tzn=err(yn,wT||zn)张抄，即第二項是相等的雹洗。然后第二步比較第一項：wT?w?=wT||w||+2wT||w⊥+wT⊥w⊥>wT||w||佳恬，即w?對應的L2-regularized linear model值要比w||大，這就說明w?并不是最優(yōu)解，從而證明w⊥必然等于零优床，即w?=∑Nn=1βnzn一定成立，w?一定可以寫成z的線性組合形式悲龟。

image.png

經(jīng)過證明和分析访娶，我們得到了結(jié)論是任何L2-regularized linear model都可以使用kernel來解決。現(xiàn)在怀酷，我們來看看如何把kernel應用在L2-regularized logistic regression上稻爬。上面我們已經(jīng)證明了w?一定可以寫成z的線性組合形式，即w?=∑Nn=1βnzn蜕依。那么我們就無需一定求出w?桅锄，而只要求出其中的βn就行了。怎么求呢样眠？直接將w?=∑Nn=1βnzn

代入到L2-regularized logistic regression最小化問題中友瘤，得到：

image.png

image.png

上式中，所有的w項都換成βn來表示了檐束，變成了沒有條件限制的最優(yōu)化問題辫秧。我們把這種問題稱為kernel logistic regression，即引入kernel被丧，將求w的問題轉(zhuǎn)換為求βn的問題盟戏。從另外一個角度來看Kernel Logistic Regression（KLR）：

image.png

上式中l(wèi)og項里的∑Nm=1βmK(xm,xn)可以看成是變量β和K(xm,xn)的內(nèi)積绪妹。上式第一項中的∑Nn=1∑Nm=1βnβmK(xn,xm)可以看成是關于β的正則化項βTKβ。所以柿究，KLR是β的線性組合邮旷，其中包含了kernel內(nèi)積項和kernel regularizer。這與SVM是相似的形式蝇摸。但值得一提的是婶肩，KLR中的βn與SVM中的αn是有區(qū)別的。SVM中的αn大部分為零探入，SV的個數(shù)通常是比較少的狡孔；而KLR中的βn通常都是非零值。

總結(jié)

本節(jié)課主要介紹了Kernel Logistic Regression蜂嗽。首先把Soft-Margin SVM解釋成Regularized Model苗膝，建立二者之間的聯(lián)系，其實Soft-Margin SVM就是一個L2-regularization植旧，對應著hinge error messure辱揭。然后利用它們之間的相似性，討論了如何利用SVM的解來得到Soft Binary Classification病附。方法是先得到SVM的解问窃，再在logistic regression中引入?yún)?shù)A和B，迭代訓練完沪，得到最佳解域庇。最后介紹了Kernel Logistic Regression，證明L2-regularized logistic regression中覆积，最佳解w?一定可以寫成z的線性組合形式听皿，從而可以將kernel引入logistic regression中，使用kernel思想在z空間直接求解L2-regularized logistic regression問題宽档。