標籤：

拉格朗日乘子法

05-04

上周我們對線性svm的最大間隔進行了推導，得到以下結論

$maxfrac{1}{2}W^{T} W$ subject to $y^{(i)}(W^{T}X^{(i)} +b)geq 1$ $i=1,2,3,4,.......n$ (subject 的意思是約束於, n 是樣本數量)

先不討論這個問題怎麼求解，我們介紹一個拉格朗日乘子法。

在高中的時候，我們經常碰到這樣的最優化問題，求 xy 的最大值，當 $frac{x^{2} }{4}+frac{y^{2} }{2} =1$ 時。

在高中的時候，我們用帶入法就可以求解，過程如下

求 xy 的最大值，我們不妨求 $x^{2} y^{2}$ ，那 $x^{2} y^{2}$ ＝ $(4-2y^{2} )y^{2}$ ,

設 $y^{2} =t$ , 則 $(4-2t)t$ ,其中 $tgeq 0$ , 這個二次函數的最大值很容易求，最終 xy 的最大值是 $sqrt{2}$

我們從另一個角度來看待這個問題

xy的等高線是一系列反比例函數，而 $frac{x^{2} }{4} +frac{y^{2} }{2} =1$ 是個橢圓，圖像如下

什麼時候 $xy$ 取最大值？當然是等高線與橢圓相切的時候，即圖中的綠色的那根反比例函數曲線取最大值

那用什麼方法去確定這個與橢圓相切的反比例函數呢？用導數（多維空間用梯度),

導數相等（多維空間時，梯度成比例，因為多維空間的導數是個多維向量，所以只要成比例就可以），於是

$xy+lambda (frac{x^{2} }{4} +frac{y^{2} }{2}-1 )$ 的 x，y的偏導數全部為0

x的偏導數 $y+frac{2lambda x}{4} =0$ ,y 的偏導數 $x+frac{2ylambda }{2} =0$ ,同時 $frac{x^{2} }{4} +frac{y^{2} }{2} =1$

於是 x ＝ $sqrt{2}$ ，y ＝ 1 或則 x＝ $-sqrt{2}$ , y = -1

總結，在 $g(x)=0$ 的條件下，求 $f(x)$ 的極值的這類最優化的問題，可以轉化為

$f(x)+lambda g(x)$ 的梯度為0

對於多個約束條件同樣適用，即

在 $g(x)=0,h(x)=0$ 的條件下，求 $f(x)$ 的極值的問題，可以轉化為

$f(x)+lambda _{1} g(x)+lambda _{2} h(x)$ 的梯度等於0

你可以自行擴展到n個約束的情況

下期介紹不等式約束下的最優化問題

推薦閱讀：

※想研究下SVM，有什麼好的文章或者經驗之談可以分享下不？
※機器學習演算法實踐-Platt SMO和遺傳演算法優化SVM
※【學界】非凸轉成凸、約束轉無約－運籌學和支持向量機中的拉格朗日鬆弛法
※淺談最優化問題的KKT條件

TAG:SVM |