【机器学习】支持向量机(三)----拉格朗日对偶性与对偶问题

上一篇，讲的是硬间隔最大化和软间隔最大化的原始学习问题，回顾一下。
1.硬间隔最大化(线性可分支持向量机)学习算法
原始问题：
　　　minωT,b12||ω||2$\underset{{\omega }^T,b}{min}\frac{1}{2}||\omega |{|}^2$
s.t.　　yi(ωTxi+b)−1≥0$y_i({\omega }^T{x}_i+b)-1\ge 0$

2.软间隔最大化(线性支持向量机)学习算法
原始问题：
　　　minωT,b,ξ12||ω||2+C∑n=1Nξi$\underset{{\omega }^T,b,\xi }{min}\frac{1}{2}||\omega |{|}^2+C\sum _{n=1}^N{\xi }_i$
s.t.　　yi(ωTxi+b)≥1−ξi$y_i({\omega }^T{x}_i+b)\ge 1-{\xi }_i$　　(i=1,2,..,N)
s.t.　　ξi≥0${\xi }_i\ge 0$　　　　　　　　　(i=1,2,..,N)

由于约束项的存在，对于这些原始问题的求解变得复杂起来，回忆起高中那时有一类不等式题，求解的思路就是用的拉格朗日乘数法，将那些约束项和待求项合在一起组成一个式子来求解，这个就有点像我们要用的方法。
因此，在这里，我们可以利用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是支持向量机的对偶算法。其优点有二：一、对偶问题往往更容易求解；二、自然地引入核函数，进而推广到非线性分类问题。

【原始问题】

首先我们来看看原始问题的形式(来自统计学习方法附录C)
假设f(x)$f(x)$,ci(x)$c_i(x)$,hj(x)$h_j(x)$是定义在Rn$R^n$上的连续可微函数.考虑约束最优化问题：
　　　minx∈Rnf(x)$\underset{x\in R^n}{min}f(x)$
s.t.　　ci(x)≤0$c_i(x)\le 0$　　　(i=1,2,…,k)
s.t.　　hj(x)=0$h_j(x)=0$　　　(j=1,2,…,s)
这个问题就被称为原始最优化问题或原始问题

【拉格朗日乘数】

引入拉格朗日乘数L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1sβjhj(x)$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^k{\alpha }_i{c}_i(x)+\sum _{j=1}^s{\beta }_j{h}_j(x)$
这里αi${\alpha }_i$,βj${\beta }_j$是拉格朗日乘子，αi≥0${\alpha }_i\ge 0$
又到了重头戏时间，上图：

为什么要这要设计呢，原始问题的约束项在这个式子中如何体现呢？那么我们就来看看θp(x)=maxα,β:αi≥0L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1sβjhj(x)${\theta }_p(x)=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^k{\alpha }_i{c}_i(x)+\sum _{j=1}^s{\beta }_j{h}_j(x)$这个式子是否能满足原始问题的那两个约束条件吧。
接着上图：

诶嘿，真是一个美妙的变化。不过为什么

θp(x)={f(x),+∞,x满足原始条件约束其他${\theta }_p(x)=\{\begin{array}{ll}f(x),& \text{x满足原始条件约束}\\ +\mathrm{\infty },& \text{其他}\end{array}$
其实当x满足原始条件约束时(即ci(x)≤0$c_i(x)\le 0$，hj(x)=0$h_j(x)=0$)
θp(x)${\theta }_p(x)$就会变成maxα,β:αi≥0L(x,α,β)=f(x)+负数乘上αi$\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )=f(x)+负数乘上{\alpha }_i$，为了使L(x,α,β)$L(x,\alpha ,\beta )$最大，由于αi≥0${\alpha }_i\ge 0$，只有αi${\alpha }_i$取0的时候才能使其最大，这样就得出θp(x)=maxα,β:αi≥0L(x,α,β)=f(x)${\theta }_p(x)=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )=f(x)$了
这样，原本三行式子的原始问题就被转化成了minxθp(x)=minxmaxα,β:αi≥0L(x,α,β)$\underset{x}{min}{\theta }_p(x)=\underset{x}{min}\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )$
被称为广义拉格朗日函数的极小极大问题

【对偶问题】

定义θD(α,β)=minxL(x,α,β)${\theta }_D(\alpha ,\beta )=\underset{x}{min}L(x,\alpha ,\beta )$，再考虑极大化θD(α,β)${\theta }_D(\alpha ,\beta )$
即maxα,β:αi≥0θD(α,β)=maxα,β:αi≥0minxL(x,α,β)$\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}\underset{x}{min}L(x,\alpha ,\beta )$
这个被称为广义拉格朗日函数的极大极小问题，我们给它换个形式，把αi≥0${\alpha }_i\ge 0$给提出来做约束项，就可以写成这样：
　　　　maxα,βθD(α,β)=maxα,βminxL(x,α,β)$\underset{\alpha ,\beta }{max}{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta }{max}\underset{x}{min}L(x,\alpha ,\beta )$
s.t.　　　αi≥0${\alpha }_i\ge 0$
这个就被称为原始问题的对偶问题

定理1

定义原始问题最优解为：p∗=minxθp(x)$p^{\ast }=\underset{x}{min}{\theta }_p(x)$
定义对偶问题最优解为：d∗=maxα,β:α≥0θD(α,β)$d^{\ast }=\underset{\alpha ,\beta :\alpha \ge 0}{max}{\theta }_D(\alpha ,\beta )$
若原始问题和对偶问题都有最优解，则有：
d∗=maxα,β:αi≥0minxL(x,α,β)≤minxmaxα,β:αi≥0L(x,α,β)=p∗$d^{\ast }=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}\underset{x}{min}L(x,\alpha ,\beta )\le \underset{x}{min}\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )=p^{\ast }$

推论

设x∗$x^{\ast }$是原始问题可行解，α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$是对偶问题可行解，并且d∗=p∗$d^{\ast }=p^{\ast }$，则x∗$x^{\ast }$是原始问题最优解，α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$是对偶问题最优解

定理2

1、假设函数f(x)$f(x)$和ci(x)$c_i(x)$是凸函数，hj(x)$h_j(x)$是仿射函数(即最高次数为1的多项式函数，若常数项等于0，就是线性函数)
2、假设不等式约束ci(x)$c_i(x)$是严格可行的(即存在x$x$,对所有i$i$有ci(x)<0$c_i(x)<0$)
以上两个假设同时满足的情况下，则存在x∗$x^{\ast }$,α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$，使x∗$x^{\ast }$是原始问题的解，α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$是对偶问题的解，且d∗=p∗=L(x∗,α∗,β∗)$d^{\ast }=p^{\ast }=L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })$

定理3

对于定理2来说，存在x∗$x^{\ast }$,α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$，使x∗$x^{\ast }$是原始问题的解，α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$是对偶问题的解的充分必要条件是x∗$x^{\ast }$,α∗${\alpha }^{\ast }$,β∗${\beta }^{\ast }$满足下面的KKT条件：

【KKT条件】

　　　　∇xL(x∗,α∗,β∗)=0${\mathrm{\nabla }}_{x}L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0$
　　　　α∗ici(x∗)=0${\alpha }_i^{\ast }{c}_i(x^{\ast })=0$　　　i=1,2,…k
　　　　ci(x∗)≤0$c_i(x^{\ast })\le 0$　　　　i=1,2,…k
　　　　α∗i≥0${\alpha }_i^{\ast }\ge 0$　　　　　　i=1,2,…k
　　　　hj(x∗)=0$h_j(x^{\ast })=0$　　　　j=1,2,…s
特别指出，α∗i≥0${\alpha }_i^{\ast }\ge 0$被称为KKT对偶互补条件，由此条件可知：若α∗i>0${\alpha }_i^{\ast }>0$，则ci(x)=0$c_i(x)=0$

【线性可分支持向量机的对偶问题】

有了上面的基础，我们就可以对线性可分支持向量机的原始问题进行转化啦~
再次写一下原始问题：
　　　minωT,b12||ω||2$\underset{{\omega }^T,b}{min}\frac{1}{2}||\omega |{|}^2$
s.t.　　yi(ωTxi+b)−1≥0$y_i({\omega }^T{x}_i+b)-1\ge 0$
引入拉格朗日乘子αi≥0${\alpha }_i\ge 0$，得L(ωT,b,α)=12||ω||2−∑i=1nαiyi(ωTxi+b)+∑i=1nαi$L({\omega }^T,b,\alpha )=\frac{1}{2}||\omega |{|}^2-\sum _{i=1}^n{\alpha }_i{y}_i({\omega }^T{x}_i+b)+\sum _{i=1}^n{\alpha }_i$

对偶问题为：
maxαminωT,bL(ωT,b,α)$\underset{\alpha }{max}\underset{{\omega }^T,b}{min}L({\omega }^T,b,\alpha )$
为了求得对偶问题的解，需先求L(ωT,b,α)$L({\omega }^T,b,\alpha )$对ωT${\omega }^T$，b$b$的极小，再求对α$\alpha$的极大。

(1)求L(ωT,b,α)$L({\omega }^T,b,\alpha )$对ωT${\omega }^T$，b$b$的极小：

　　　　∇ωL(ωT,b,α)=ω−∑i=1nαiyixi=0${\mathrm{\nabla }}_{\omega }L({\omega }^T,b,\alpha )=\omega -\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0$
　　　　∇bL(ωT,b,α)=−∑i=1nαiyi=0${\mathrm{\nabla }}_{b}L({\omega }^T,b,\alpha )=-\sum _{i=1}^n{\alpha }_i{y}_i=0$

　　　　求得：ω=∑i=1nαiyixi$\omega =\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$
　　　　　　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　
　　　　带入minωT,bL(ωT,b,α)$\underset{{\omega }^T,b}{min}L({\omega }^T,b,\alpha )$
得：minωT,bL(ωT,b,α)=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixj$\underset{{\omega }^T,b}{min}L({\omega }^T,b,\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$
　　

(2)求maxαminωT,bL(ωT,b,α)$\underset{\alpha }{max}\underset{{\omega }^T,b}{min}L({\omega }^T,b,\alpha )$

即求：
　　　maxα∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixj$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$
s.t.　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　　(αi≥0,i=1,2..,n${\alpha }_i\ge 0,i=1,\mathrm{2..},n$)

(3)转换为等价问题

　　　minα12∑i=1n∑j=1nαiαjyiyjxTixj−∑i=1nαi$\underset{\alpha }{min}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j-\sum _{i=1}^n{\alpha }_i$
s.t.　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　　(αi≥0,i=1,2..,n${\alpha }_i\ge 0,i=1,\mathrm{2..},n$)

(4)解得最优解α∗=(α∗1,α∗2,...,α∗n)T${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_n^{\ast }{)}^T$

(5)计算ω∗${\omega }^{\ast }$,b∗$b^{\ast }$

　　　　ω∗=∑i=1nα∗iyixi=0${\omega }^{\ast }=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i=0$
　　　　b∗=yj−∑i=1nα∗iyixTixj=0$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i^T{x}_j=0$

(6)求得超平面：ω∗x+b∗=0${\omega }^{\ast }x+b^{\ast }=0$

求得分类决策函数：f(x)=sign(ω∗x+b∗)$f(x)=sign({\omega }^{\ast }x+b^{\ast })$

【线性支持向量机的对偶问题】

对线性支持向量机的原始问题同样进行转化
原始问题：
　　　minωT,b,ξ12||ω||2+C∑n=1Nξi$\underset{{\omega }^T,b,\xi }{min}\frac{1}{2}||\omega |{|}^2+C\sum _{n=1}^N{\xi }_i$
s.t.　　yi(ωTxi+b)≥1−ξi$y_i({\omega }^T{x}_i+b)\ge 1-{\xi }_i$　　(i=1,2,..,N)
s.t.　　ξi≥0${\xi }_i\ge 0$　　　　　　　　　(i=1,2,..,N)

入两个拉格朗日乘子αi≥0${\alpha }_i\ge 0$和μi≥0${\mu }_i\ge 0$，得L(ωT,b,ξ,α)=12||ω||2+C∑n=1Nξi−∑i=1n(αiyi(ωTxi+b)−1+ξi)−∑i=1nμiξi$L({\omega }^T,b,\xi ,\alpha )=\frac{1}{2}||\omega |{|}^2+C\sum _{n=1}^N{\xi }_i-\sum _{i=1}^n({\alpha }_i{y}_i({\omega }^T{x}_i+b)-1+{\xi }_i)-\sum _{i=1}^n{\mu }_i{\xi }_i$

对偶问题为：
maxαminωT,b,ξL(ωT,b,ξ,α)$\underset{\alpha }{max}\underset{{\omega }^T,b,\xi }{min}L({\omega }^T,b,\xi ,\alpha )$
为了求得对偶问题的解，需先求L(ωT,b,ξ,α)$L({\omega }^T,b,\xi ,\alpha )$对ωT${\omega }^T$，b$b$，ξ$\xi$的极小，再求对α$\alpha$的极大。

(1)求L(ωT,b,ξ,α)$L({\omega }^T,b,\xi ,\alpha )$对ωT${\omega }^T$，b$b$，ξ$\xi$的极小：

　　　　∇ωL(ωT,b,ξ,α)=ω−∑i=1nαiyixi=0${\mathrm{\nabla }}_{\omega }L({\omega }^T,b,\xi ,\alpha )=\omega -\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0$
　　　　∇bL(ωT,b,ξ,α)=−∑i=1nαiyi=0${\mathrm{\nabla }}_{b}L({\omega }^T,b,\xi ,\alpha )=-\sum _{i=1}^n{\alpha }_i{y}_i=0$
　　　　∇ξL(ωT,b,ξ,α)=C−αi−μi=0${\mathrm{\nabla }}_{\xi }L({\omega }^T,b,\xi ,\alpha )=C-{\alpha }_i-{\mu }_i=0$
　　　　求得：ω=∑i=1nαiyixi$\omega =\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$
　　　　　　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$
　　　　　　　C−αi−μi=0$C-{\alpha }_i-{\mu }_i=0$　
　　　　带入minωT,b,ξL(ωT,b,ξ,α)$\underset{{\omega }^T,b,\xi }{min}L({\omega }^T,b,\xi ,\alpha )$
得：minωT,b,ξL(ωT,b,ξ,α)=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixj$\underset{{\omega }^T,b,\xi }{min}L({\omega }^T,b,\xi ,\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$
　　

(2)求maxαminωT,b,ξL(ωT,b,ξ,α)$\underset{\alpha }{max}\underset{{\omega }^T,b,\xi }{min}L({\omega }^T,b,\xi ,\alpha )$

即求：
　　　maxα∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixj$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$
s.t.　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　　(αi≥0,i=1,2..,n${\alpha }_i\ge 0,i=1,\mathrm{2..},n$)
s.t.　　C−αi−μi=0$C-{\alpha }_i-{\mu }_i=0$　　(i=1,2..,n$i=1,\mathrm{2..},n$)
s.t.　　αi≥0${\alpha }_i\ge 0$　　(i=1,2..,n$i=1,\mathrm{2..},n$)
s.t.　　μi≥0${\mu }_i\ge 0$　　(i=1,2..,n$i=1,\mathrm{2..},n$)
等价于：
　　　maxα∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixj$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$
s.t.　　∑ni=1αiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　　(αi≥0,i=1,2..,n${\alpha }_i\ge 0,i=1,\mathrm{2..},n$)
s.t.　　0≤αi≤C$0\le {\alpha }_i\le C$　　(i=1,2..,n$i=1,\mathrm{2..},n$)

(3)转换为等价问题

　　　minα12∑i=1n∑j=1nαiαjyiyjxTixj−∑i=1nαi$\underset{\alpha }{min}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j-\sum _{i=1}^n{\alpha }_i$
s.t.　　∑i=1nαiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$　　(αi≥0,i=1,2..,n${\alpha }_i\ge 0,i=1,\mathrm{2..},n$)
s.t.　　0≤αi≤C$0\le {\alpha }_i\le C$　　(i=1,2..,n$i=1,\mathrm{2..},n$)

(4)解得最优解α∗=(α∗1,α∗2,...,α∗n)T${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_n^{\ast }{)}^T$

(5)计算ω∗${\omega }^{\ast }$,b∗$b^{\ast }$

　　　　ω∗=∑i=1nα∗iyixi=0${\omega }^{\ast }=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i=0$
　　　　b∗=yj−∑i=1nα∗iyixTixj=0$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i^T{x}_j=0$

(6)求得超平面：ω∗x+b∗=0${\omega }^{\ast }x+b^{\ast }=0$

求得分类决策函数：f(x)=sign(ω∗x+b∗)$f(x)=sign({\omega }^{\ast }x+b^{\ast })$

参考文献：《统计学习方法》、《机器学习》