本文來自同步博客审磁。

P.S. 不知道簡書怎么顯示數(shù)學(xué)公式以及更好的排版內(nèi)容谈飒。所以如果覺得文章下面格式亂的話請自行跳轉(zhuǎn)到上述鏈接。后續(xù)我將不再對(duì)數(shù)學(xué)公式進(jìn)行截圖态蒂，畢竟行內(nèi)公式截圖的話排版會(huì)很亂杭措。看原博客地址會(huì)有更好的體驗(yàn)钾恢。

前面介紹的SVM手素，無論是線性可分還是非線性可分，稱為Hard Margin SVM瘩蚪，都要求對(duì)輸入數(shù)據(jù)進(jìn)行精確劃分泉懦。我們不難想到這類SVM存在過擬合這個(gè)問題。如果輸入數(shù)據(jù)本身就存在誤差疹瘦，精確劃分反而是沒意義的崩哩。本篇文章就如何處理過擬合問題，介紹即所謂的Soft Margin SVM言沐。

數(shù)學(xué)推導(dǎo)

引入衡量誤差的變量 -\xi\_i-邓嘹。-\xi\_i-表示不能被正確分類的樣本點(diǎn)距離正確一側(cè)邊界的距離，距離越大表示錯(cuò)誤越大呢灶，即-\xi\_i-越大吴超。如果樣本點(diǎn)能被正確分類，則-\xi\_i = 0-鸯乃。故有-\xi\_i \ge 0-鲸阻。

那么，原來能通過求解函數(shù)-\frac{1}{2}\vec{w}^{2}-在最小化下的參數(shù)-\vec{\alpha}-缨睡，如今需要增加能夠體現(xiàn)誤差的約束條件再求解鸟悴。

可以如下構(gòu)造函數(shù)來描述誤差：
\frac{1}{2}\vec{w}^{2} + C\sum_{i}^{n}{\xi\_i}

這個(gè)函數(shù)把所有輸入數(shù)據(jù)的誤差疊加在一起，即-\sum_{i}^{n}{\xi\_i}-奖年。然后用參數(shù)C來控制所有誤差的權(quán)重细诸。如果C很大，表示即使有很小的誤差出現(xiàn)都會(huì)嚴(yán)重影響目標(biāo)函數(shù)陋守。

結(jié)合之前文章提到的知識(shí)震贵，可以構(gòu)造拉格朗日方程：

L(\vec{w}, b, \vec{\xi}, \vec{\alpha}, \vec{\beta}) = \frac{1}{2}\vec{w}^{T}\vec{w} + C\sum_{i}^{n}{\xi\_i} - \sum\_{i}^{n}{\alpha\_i[y\_i(\vec{w}^{T}\vec{x\_i}+b)-1+\xi\_i]} - \sum\_{i}^{n}\beta\_i\xi\_i
其中利赋，
\alpha\_i \ge 0, \beta\_i \ge 0, i = 1,2...n

然后利用對(duì)偶思想求解-\vec{w}, b, \xi-的導(dǎo)數(shù)，并讓他們等于0猩系。如下：

\begin{array}{lcl} \frac{\partial L}{\partial \vec{w}} = \vec{w} - \sum\_{i}^{n}\alpha\_{i} y\_{i} \vec{x}\_i = 0 \\\\ \frac{\partial L}{\partial b} = - \sum\_{i}^{n}\alpha\_{i} y\_{i} = 0 \\\\ \frac{\partial L}{\partial \xi\_{i}} = C - \alpha\_{i} - \beta\_{i} = 0 \end{array}

代入上面的拉格朗日方程媚送，可以得到二項(xiàng)規(guī)劃方程。最后求解-\vec{\alpha}-寇甸，可得-\vec{w}-和-b-塘偎。二項(xiàng)規(guī)劃方程如下：
F(\alpha) = \frac{1}{2}\sum\_{i}^{n}\sum\_{j}^{m}y\_{i}y\_{j}\alpha\_{i}\alpha\_{j}\vec{x}\_{i}^{T}\vec{x}\_{j} - \sum\_{i}^{n} \alpha\_i， C \ge \alpha\_i \ge 0, i = 1,...,n

其中-\vec{w}-如下：
\vec{w} = \sum\_{i}^{n}\alpha\_{i}y\_{i}\vec{x}\_{i}

-b-可利用落于邊界上的支持向量求解拿霉。

比較

看到二項(xiàng)規(guī)劃那一步吟秩，我們可以發(fā)現(xiàn)Hard Margin SVM和Soft Margin SVM的差別僅僅是-\alpha\_i-的取值范圍上有差異。Hard Margin SVM的約束條件是-\alpha\_i \ge 0-绽淘；Soft Margin SVM的約束條件是-C \ge \alpha\_i \ge 0-涵防。

我們知道-\alpha\_{i}-僅在-\vec{x}-為支持向量時(shí)值大于零。而在這里沪铭，-\alpha\_{i}-多了一個(gè)上限C武学。因?yàn)?span id="mqmiqto" class="math-inline">-C = \alpha\_{i} + \beta\_{i}-，所以有下面結(jié)論：

如果-\alpha\_{i} = 0-伦意，表示該點(diǎn)為非支持向量。

如果- 0 \lt \alpha\_{i} \lt C-硼补，則-\beta\_{i} \gt 0-驮肉，對(duì)應(yīng)的-\xi\_{i} = 0-，表示該點(diǎn)為邊界支持向量已骇。如下圖：

image.png

如果-\alpha\_{i} = C-离钝，則-\beta\_{i} = 0-，對(duì)應(yīng)的-\xi\_{i} \gt 0-褪储，表示該點(diǎn)違反了最大邊界的原則卵渴，屬于噪聲點(diǎn)。

image.png