上一章我們介紹了SVM算法的意義，SVM是large-margin算法畦幢，旨在找到一條能夠完全區(qū)分訓(xùn)練集而且擁有最大margin值的直線坎吻。在這一章節(jié)里，我們將推導(dǎo)margin的計(jì)算方式和SVM最終要解決的問題的方程表達(dá)式宇葱。
任意點(diǎn)到?jīng)Q策邊界距離（1） － 初步表達(dá)式
上章節(jié)我們提到瘦真，margin值就是所有數(shù)據(jù)點(diǎn)到?jīng)Q策邊界的距離里面的最小值刊头，所以首先我們要計(jì)算平面內(nèi)任意一點(diǎn)到?jīng)Q策邊界的距離。為了使得表述和理解更簡(jiǎn)單诸尽，在下面的所有推導(dǎo)中原杂，我們都采用二維平面內(nèi)的數(shù)據(jù)作為例子去做解釋。二維平面得到的結(jié)論可以推廣到任意維度的空間當(dāng)中您机。
上圖是一個(gè)在上一章節(jié)用過的二維數(shù)據(jù)集例子穿肄。在圖中，紅色的數(shù)據(jù)點(diǎn)是需要計(jì)算到?jīng)Q策邊界距離的點(diǎn)际看，我們標(biāo)注其為X咸产。X1為決策邊界上的點(diǎn)。注意仲闽，這里的X1跟坐標(biāo)軸上的x1不一樣脑溢，這里的X1是一個(gè)點(diǎn)，也是一個(gè)擁有兩個(gè)維度的向量焚志。坐標(biāo)軸上的x1是兩個(gè)維度對(duì)應(yīng)的值的大小，是標(biāo)量。圖中的distance是我們需要計(jì)算的距離，該線段與決策邊界垂直且與點(diǎn)X相交巡揍。
現(xiàn)在腮敌，假定圖中的決策邊界是由特征權(quán)重向量W和偏差值b決定的糜工，既對(duì)于任意數(shù)據(jù)點(diǎn)，h(X) = sign(WTX + b)，該分類器是一個(gè)線性分類器(linear classifier)凤覆。對(duì)于任意數(shù)據(jù)X，當(dāng)WTX + b > 0的時(shí)候預(yù)測(cè)該點(diǎn)為正類渤刃，當(dāng)WTX + b < 0的時(shí)候預(yù)測(cè)該點(diǎn)為負(fù)類。當(dāng)WTX + b = 0的時(shí)候诫舅，該點(diǎn)正好落在決策邊緣上虚汛，此時(shí)分類器將其預(yù)測(cè)為正類來打破平衡(tie-break)属拾。因此礼预，我們很容易得到?jīng)Q策邊界的方程為WTX + b = 0。
為了計(jì)算點(diǎn)X到?jīng)Q策邊界的距離刨疼，我們做了一條輔助線泉唁，這條輔助線穿過點(diǎn)X和決策邊界上的一點(diǎn)X1。根據(jù)高中幾何知識(shí)我們知道X到?jīng)Q策邊緣的距離D揩慕，是向量X X1長(zhǎng)度在垂直于決策邊界方向上的投影亭畜，既Distance = ||X - X1||cos(a)，a為向量XX1與垂直于決策邊界方向的夾角迎卤。
此時(shí)拴鸵，要計(jì)算Distance大小我們有兩個(gè)方法，第一個(gè)方法是計(jì)算角度a以及||X - X1||的大小蜗搔，第二個(gè)方法是找到一個(gè)垂直于決策邊界的向量劲藐，假設(shè)是P。則距離
對(duì)于以上的公式推導(dǎo)樟凄，我們將會(huì)在下面演示聘芜。
根據(jù)經(jīng)驗(yàn)而言，求法向量P往往比求角度a要簡(jiǎn)單一些不同，所以我們?cè)谶@里采用第二種方法厉膀。由于我們最終需要用權(quán)重向量W和偏差b來表示距離大小，所以上面公式的是距離的初步表達(dá)式二拐，我們還需要進(jìn)行進(jìn)一步推算服鹅。
任意點(diǎn)到?jīng)Q策邊界距離（2） － 初步表達(dá)式的證明
剛剛我們提到了第二種計(jì)算距離的方法，并給出了計(jì)算公式百新，現(xiàn)在我們要證明計(jì)算公式的正確性企软。
首先根據(jù)向量相乘公式我們知道，兩個(gè)向量相乘等于向量長(zhǎng)度的乘積再與向量夾角余弦值的乘積饭望。既
上面的式子說的是向量P和向量||X - X1||的乘積仗哨，因?yàn)?em>P是垂直于決策邊界，所以P與X - X1向量的夾角就是第一個(gè)坐標(biāo)圖中的角a铅辞。之前我們提到過，所求距離Distance = ||X - X1|| cos(a)斟珊。因此根據(jù)上面的得到的公式我們可以推出：
任意點(diǎn)到?jīng)Q策邊界距離（3） － 找到跟決策邊界垂直的向量P
在前面我們介紹并推導(dǎo)了任意點(diǎn)到?jīng)Q策邊界距離的初步表達(dá)式。現(xiàn)在，我們要找到公式當(dāng)中的向量P，一個(gè)垂直于決策邊界的向量示惊。
現(xiàn)在我們?cè)俣x另一個(gè)落在決策邊界上的點(diǎn)X2。
X1和X2都落在決策邊界上，因此對(duì)于點(diǎn)X1和X2阔拳，滿足決策邊界方程
我們把方程組中的上下兩式相減得到 WT (X1 - X2) = 0。向量相乘等于零說明向量方向互相垂直类嗤。因此我們可以得到WT ⊥ (X1 - X2)糊肠。由于X1和X2都落在決策邊界上，所以遗锣，(X1 - X2)的方向就是決策邊界的方向货裹。因此WT就是我們要找的垂直于決策邊界的向量P。
任意點(diǎn)到?jīng)Q策邊界距離（4）－ 最終表達(dá)式
上面我們得到了垂直于決策邊界的向量 WT精偿，現(xiàn)在我們把WT代入到前面的得到的距離初步表達(dá)式當(dāng)中弧圆，
我們把WT放到后面的括號(hào)里面：
因?yàn)?em>X1是決策邊界上的一點(diǎn)，所以有
把上式代入Distance公式當(dāng)中得到
為了讓式子看著更簡(jiǎn)單笔咽，我們把||WT||換成||W||搔预，因?yàn)?br> W的長(zhǎng)度與其轉(zhuǎn)置的長(zhǎng)度一樣。
這個(gè)距離公式還存在一個(gè)問題叶组，就是WTX + b的值有可能為負(fù)拯田，這樣算出來的距離就會(huì)為負(fù)值，這不符合我們常規(guī)當(dāng)中對(duì)距離大小的認(rèn)識(shí)甩十，我們常識(shí)當(dāng)中總認(rèn)為距離是非負(fù)的船庇。因此我們?cè)?em>WTX + b外面加上一個(gè)絕對(duì)值符號(hào)，確保其非負(fù)侣监。下面就是任意點(diǎn)X到?jīng)Q策邊界的距離最終表達(dá)式：
Margin表達(dá)式的推導(dǎo)
前面我們推導(dǎo)了任意點(diǎn)到?jīng)Q策平面的距離表達(dá)式鸭轮，下面我們要把問題回歸到SVM，推導(dǎo)Margin值的表達(dá)式橄霉。
在上一章節(jié)我們提到窃爷，SVM的前提是要把訓(xùn)練集無錯(cuò)誤地分開，也就是說，對(duì)于所有訓(xùn)練數(shù)據(jù)X, WTX + b 于這個(gè)點(diǎn)的分類值yn必須是同號(hào)吞鸭，即yn (WTX + b) > 0寺董。
因?yàn)閥n只有兩個(gè)值，+1和-1, 我們可以把距離公式當(dāng)中的絕對(duì)值符號(hào)去掉刻剥，但是要添加一個(gè)條件：
s.t. 后面的是等式成立的條件遮咖，這也是SVM的前提。
我們已經(jīng)知道造虏，Margin值就是所有點(diǎn)Distance的最小值御吞，因此我們得到Margin的表達(dá)式：
Margin表達(dá)式的簡(jiǎn)化
上面我們得到了Margin的表達(dá)式，然而要得到上面表達(dá)式的最大值仍然有點(diǎn)復(fù)雜漓藕，不便于計(jì)算陶珠，因此我們還需要對(duì)表達(dá)式進(jìn)行進(jìn)一步的簡(jiǎn)化，以方便計(jì)算享钞。
通過觀察上面的表達(dá)式揍诽，我們可以把1 / ||W||提到min函數(shù)的前面去，因?yàn)? / ||W||跟n并無關(guān)系栗竖，margin公式轉(zhuǎn)換成了：
現(xiàn)在再次觀察新的margin表達(dá)式暑脆，容易看出我們或許可以嘗試對(duì)公式當(dāng)中min后面的式子進(jìn)行簡(jiǎn)化。假若我們能夠把后面的min值簡(jiǎn)化成一個(gè)常數(shù)狐肢，甚至讓后面的min值簡(jiǎn)化成1添吗，那么margin表達(dá)式就會(huì)剩下一個(gè) 1 / ||W||，計(jì)算量將會(huì)大大減少份名。
事實(shí)上碟联，我們確實(shí)可以把表達(dá)式當(dāng)中的min值簡(jiǎn)化成1。在說明白這個(gè)道理之前僵腺，先看一個(gè)例子鲤孵。
對(duì)于平面內(nèi)任意決策邊界，WTX + b ＝ 0〕饺纾現(xiàn)在讓其W和b同時(shí)放大三倍裤纹，既 3WTX + 3b ＝ 0∩ッ唬可以很容易知道鹰椒，放大三倍之后的決策邊界跟放大之前的決策邊界是同一條邊界，因此我們可以知道呕童，對(duì)W和b同時(shí)進(jìn)行縮放漆际，不會(huì)影響決策邊界的位置。
現(xiàn)在我們回到剛剛的margin表達(dá)式夺饲，我們可以對(duì)決策邊界參數(shù)做一個(gè)特殊的縮放奸汇，假設(shè)縮放倍數(shù)為n施符，使得其永遠(yuǎn)滿足以下條件：
剛剛提到，對(duì)決策邊界參數(shù)同時(shí)做相同倍數(shù)的縮放不影響決策邊界的位置擂找，因此戳吝，WTX + b ＝ 0 與 nWTX + nb ＝ 0是同一條直線。所以可以得到相同的結(jié)論：
因此我們可以對(duì)margin表達(dá)式再次簡(jiǎn)化為：
注意贯涎，s.t.條件當(dāng)中原來有的 yn (WTX + b) > 0 這個(gè)條件在這里我們省略不寫听哭，原因是只要滿足了yn (WTX + b)的最小值為1的話，必然滿足原來大于0的條件塘雳，所以為了簡(jiǎn)化陆盘，我們省略原來的條件不寫。
把最小化條件放松
上面我們得到了簡(jiǎn)化的margin表達(dá)式及其成立條件败明，表達(dá)式只是剩下一個(gè)1 / ||W||隘马，已經(jīng)足夠簡(jiǎn)單。然而妻顶，在讓表達(dá)式簡(jiǎn)單的同時(shí)酸员，我們卻把s.t.后面的條件變得更復(fù)雜了：
原來的條件是一個(gè)不等式，現(xiàn)在變成了一個(gè)最小化問題讳嘱，問題變得更加復(fù)雜了沸呐，所以現(xiàn)在我們要做的就是把最小化條件放松，使條件再次變成一個(gè)不等式呢燥。關(guān)于為什么不等式條件會(huì)比最小化條件容易解決，我們會(huì)在以后的章節(jié)有所解釋≡⒚洌現(xiàn)在我們暫且認(rèn)同這一點(diǎn)叛氨。
現(xiàn)在我們嘗試把原來的最小化條件放松成以下條件：
這個(gè)條件是原來最小化條件的必要條件，即滿足原來?xiàng)l件棘伴，必定滿足新的條件寞埠，即若滿足yn (WTX + b)的最小值為1必定滿足對(duì)于所有的n，yn (WTX + b) >= 1焊夸。
但是對(duì)于新條件是否是原來?xiàng)l件的充分條件仁连，我們還需證明。
現(xiàn)在用反證法證明新條件是舊條件的充分條件
假設(shè)一個(gè)最大的margin值對(duì)應(yīng)的最優(yōu)解為(W, b)阱穗，假設(shè)這個(gè)最優(yōu)解滿足 ：
此時(shí)這個(gè)最優(yōu)解滿足新的不等式條件饭冬，但是不滿足舊的最小化條件。
此時(shí)可以把不等式兩邊同時(shí)除以1.1揪阶，使其與原來的不等式條件一致：
這時(shí)的最優(yōu)解就變成了(W / 1.1, b / 1.1)昌抠。
把新的參數(shù)代入margin：
我們發(fā)現(xiàn)，當(dāng)W變成W / 1.1的時(shí)候鲁僚，||W||的值會(huì)變小炊苫，margin的值就會(huì)更大裁厅，解比原來的W更優(yōu)。因此這與原來假設(shè)的(W, b)是最優(yōu)解相互矛盾侨艾。
所以执虹，我們可以下結(jié)論，當(dāng)(W, b)為最優(yōu)解時(shí)唠梨，最小化條件和不等式條件是互為充要條件袋励，可以作出最小化條件放松的操作。
現(xiàn)在姻成，我們得到了更簡(jiǎn)單的margin計(jì)算方程插龄，這里把最小化條件去掉了：
margin最大化問題
上面我們得到了margin的計(jì)算表達(dá)式，現(xiàn)在可以得到我們需要優(yōu)化的模型：
總結(jié)
在這一章節(jié)里科展，主要講解了如何計(jì)算平面內(nèi)任意一點(diǎn)到?jīng)Q策邊界的距離均牢，之后還推導(dǎo)了margin最大化問題的模型。在后面的章節(jié)里才睹，將會(huì)繼續(xù)介紹如何解決這一章得到的最大化問題徘跪，從而得到最優(yōu)解。
引用
本章節(jié)某些內(nèi)容引用了臺(tái)灣大學(xué)林軒田老師Standard_Large-Margin_Problem一章節(jié)課件內(nèi)容
