SVM学习笔记3-问题转化

1中,我们的求解问题是:$min_{w,b}$ $frac{1}{2}||w||^{2}$,使得$y^{(i)}(w^{T}x^{(i)}+b)geq 1 ,1 leq i leq n$

设$g_{i}(w)=-y^{(i)}(w^{T}x^{(i)}+b)+1 leq 0$,

那么按照2中的定义,对应的拉格朗日函数为$L(w,b,alpha)=frac{1}{2}||w||^{2}-sum_{i=1}^{n}alpha_{i}[y^{(i)}(w^{T}x^{(i)}+b)-1]$

这里我们这里面没有$eta$,因为没有$h$。

那么按照2中的定义有:
(1)$ frac{partial}{partial w}L(w,b,alpha)=w-sum_{i=1}^{n}alpha_{i}y^{(i)}x^{(i)}=0$
(2)$ frac{partial}{partial b}L(w,b,alpha)=sum_{i=1}^{n}alpha_{i}y^{(i)}=0$

由(1)得$w=sum_{i=1}^{n}alpha_{i}y^{(i)}x^{(i)}$,将其带入$L(w,b,alpha)$的表达式,化简得到:$L(w,b,alpha)=sum_{i=1}^{n}alpha_{i}-frac{1}{2} sum_{i,j=1}^{n}y^{(i)}y^{(j)}alpha_{i}alpha_{j}(x^{(i)})^{T}x^{(j)}-bsum_{i=1}^{n}alpha_{i}y^{(i)}$
由(2)得$sum_{i=1}^{n}alpha_{i}y^{(i)}=0$,所以最后式子为$L(w,b,alpha)=sum_{i=1}^{n}alpha_{i}-frac{1}{2} sum_{i,j=1}^{n}y^{(i)}y^{(j)}alpha_{i}alpha_{j}(x^{(i)})^{T}x^{(j)}$

现在这个式子里只有$alpha$是未知数。这里我们要说明一点,这里我们其实将问题转成了它的对偶问题,也就是说我们的目标是求解2中所说的$d^{*}$。所以我们的目标是:
$underset{alpha}{max}W(alpha)=sum_{i=1}^{n}alpha_{i}-frac{1}{2} sum_{i,j=1}^{n}y^{(i)}y^{(j)}alpha_{i}alpha_{j}(x^{(i)})^{T}x^{(j)}$,使得满足(1)$alpha_{i}geq 0,1 leq i leq n$,(2)$sum_{i=1}^{n}alpha_{i}y^{(i)}=0$

我们将最大化变为最小化,
$underset{alpha}{min}W(alpha)=frac{1}{2} sum_{i,j=1}^{n}y^{(i)}y^{(j)}alpha_{i}alpha_{j}(x^{(i)})^{T}x^{(j)}-sum_{i=1}^{n}alpha_{i}$,使得满足(1)$alpha_{i}geq 0,1 leq i leq n$,(2)$sum_{i=1}^{n}alpha_{i}y^{(i)}=0$

此时,假设我们求出了$alpha^{*}$(我们将在后面说如何求$alpha$),那么可以通过$w^{*}=sum_{i=1}^{n}alpha_{i}y^{(i)}x^{(i)}$求出$w$。现在看如何求b。由于b只是一个截距,所以$w^{*}$一旦确定,那么就确定了一个平面簇,b只是一个偏移,所以当平面偏移到两类点的中间时最好,所以b的求解公式为:$b^{*}=- frac{ underset{i:y^{(i)}=-1}{max}(w^{*})^{T}x_{(i)}+ underset{i:y^{(i)}=1}{min}(w^{*})^{T}x_{(i)}}{2}$

原文地址:https://www.cnblogs.com/jianglangcaijin/p/6369071.html