NO.Idea

SVM

SVM 的思想是找到一个超平面 wTx+b=0w^T\cdot x+b=0 能够使间隔 γ\gamma 最大。

间隔最大化#

函数间隔#

对于一个训练样本 (xi,yi)(x^i,y^i),我们定义它到超平面 (w,b)(w,b) 的函数间隔为:

γi^=yi(wTxi+b)\hat{\gamma^i}=y^{i}(w^Tx^i+b)

±1\pm1 表示正负类别,则 γ^>0\hat{\gamma} > 0 表示分类正确,且越大表示分类越确信。但函数间隔的问题是,当 wwbb 等比例改变后,超平面不变,γ^\hat{\gamma} 却发生了改变。

几何间隔#

设在超平面上的点为 x0x_0,则其它点可以表示为 x=x0+γwwx=x_0+\gamma\frac{w}{||w||},带入 f(x0)=0f(x_0)=0,可以得到 γi=f(xi)w\gamma^i=\frac{f(x^i)}{||w||}。这里 f(xi)f(x^i) 是有符号的,间隔不应该有符号,所以 γ~=yiγi=γi^w\tilde{\gamma}=y^i\gamma^i=\frac{\hat{\gamma^i}}{||w||} 是我们的几何间隔。

所以 SVM 的思想可以用下面这个式子来表达:

arg maxw,bγ^ws.t.yi(wTxi+b)γ^\argmax_{w,\,b} \frac{\hat{\gamma}}{||w||}\quad \text{s.t.}\quad y^i(w^T\cdot x^i+b)\ge \hat{\gamma}

因为我们可以等比例改变 wwbb,而不影响最优化求解。所以设函数间隔 γ^=1\hat{\gamma}=1,不影响最终得到的超平面。上式可以写成:

arg minw,bwTw2s.t.yi(wTxi+b)10\argmin_{w,\,b} \frac{w^T\cdot w}{2}\quad \text{s.t.}\quad y^i(w^T\cdot x^i+b)-1\ge 0

拉格朗日对偶#

原始问题#

对于一个最优化求解问题

arg minwf(w).s.t.gi(w)=0,i=1,,l\argmin_{w} f(w).\quad \text{s.t.}\quad g_i(w)=0,\quad i=1,\dots,l

使用拉格朗日乘子法,讲问题转化为:

L(w,α)=f(w)+i=1lαigi(w)\mathcal{L}(w,\alpha)=f(w)+\sum_{i=1}^{l}\alpha_i g_i(w)

其中,αi\alpha_i 是拉格朗日乘子(Lagrange Multipliers)。然后求解:

\frac{\partial\mathcal{L}}{\partial w} & = 0 \\ \frac{\partial\mathcal{L}}{\partial \alpha_i} & = 0

最优间隔分类器#

构造拉格朗日函数:

L(w,b,α)=12w2i=1mαi[y(i)(wTx(i)+b)1].\mathcal{L}(w, b, \alpha)=\frac12||w||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1].

首先求 arg minw,bL(w,b,α)\argmin_{w,b} \mathcal{L}(w, b, \alpha)

w=i=1mαiy(i)x(i)i=1mαiy(i)=0\begin{aligned} w&=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\\ \sum_{i=1}^m\alpha_iy^{(i)}&=0 \end{aligned}

ww 带回 L(w,b,α)\mathcal{L}(w, b, \alpha)可得到

L(w,b,α)=i=1mαi12i,j=1my(i)y(j)αiαjx(i),x(j)bi=1mαiy(i)0\mathcal{L}(w, b, \alpha)=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle-\underbrace{b\sum_{i=1}^{m}\alpha_iy^{(i)}}_\text{0}

Then we obtain the following dual optimization problem:

arg maxαW(α)=i=1mαi12i,j=1my(i)y(j)αiαjx(i),x(j).s.t.αi0,i=1,,mi=1mαiy(i)=0\begin{aligned} & \argmax_{\alpha} W(\alpha)=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle.\\ \text{s.t.} \quad & \alpha_i\ge0,\quad i=1,\dots,m \\ & \sum_{i=1}^{m}\alpha_i y^{(i)}=0 \end{aligned}

有了这两个参数后,

wTx+b=(i=1mαiy(i)x(i))Tx+b=i=1mαiy(i)x(i),x+b\begin{aligned} w^Tx+b & = {\left(\sum_{i=1}^{m}\alpha_iy^{(i)}x^{(i)}\right)}^Tx+b \\ & = \sum_{i=1}^{m}\alpha_iy^{(i)}\langle x^{(i)},x \rangle +b \end{aligned}