SVM的推导(1)

SVM是机器学习中的一种经典方法，除了硬间隔SVM之外，还包括软间隔SVM，核技巧等SVM的变种，本文主要介绍硬间隔SVM 的推导。

函数距离与几何距离

假设两类样本点是可以被准确分开的，那么则可以使用硬间隔SVM来进行分类，假设分隔的超平面方程为w⋅x+b=0w\cdot x+b=0，则每个样本点xix_{i}到该超平面的距离为∣w⋅xi+b∣|w\cdot x_{i}+b|，如果设定与超平面之间的距离为正的点为正分类，即yi=+1y_{i}=+1，相反负距离的点为负分类，即yi=−1y_{i}=-1，那么可以将样本点到分离超平面的距离表示为γ^i=yi(w⋅xi+b)\hat{\gamma}_{i}=y_{i}(w\cdot x_{i}+b)，这称为样本点到分离超平面之间的函数距离。

令γ^=min(γ^i)\hat{\gamma}=min(\hat{\gamma}_{i})，即为最小函数距离。需要注意到，函数距离γ^i=yi(w⋅xi+b)\hat{\gamma}_{i}=y_{i}(w\cdot x_{i}+b)在ww和bb同时增大某个比例倍数时，函数间隔会增大但是超平面不会发生改变，此时便需要将超平面的ww进行约束，比如令∣∣w∣∣=1||w||=1，我们可以重新定义距离为γi=yi(w∣∣w∣∣⋅xi+b∣∣w∣∣)\gamma_{i}=y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})，称之为几何距离，令γ=min(γi)\gamma=min(\gamma_{i})，即可以得到γ=γ^∣∣w∣∣\gamma=\frac{\hat\gamma}{||w||}。

最大间隔的最优化形式

那么最大化分隔距离的优化问题即可表示如下：

maxw,bγs.t.yi(w∣∣w∣∣⋅xi+b∣∣w∣∣)≥γ，i=1,2...n\begin{align*} &max_{w,b}\quad \gamma \\ &s.t.\quad y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})\ge\gamma，i=1,2...n \end{align*}

即

maxw,bγ^∣∣w∣∣s.t.yi(w⋅xi+b)≥γ^，i=1,2...n\begin{align*} &max_{w,b}\quad \frac{\hat\gamma}{||w||} \\ &s.t.\quad y_{i}(w\cdot x_{i}+b)\ge\hat \gamma，i=1,2...n \end{align*}

注意上式中，函数间隔γ^\hat\gamma的取值并不会影响最优化问题的解，不妨假设γ^=1\hat\gamma=1，并且注意到最大化1∣∣w∣∣\frac{1}{||w||}与最小化12∣∣w∣∣2\frac{1}{2}||w||^{2}等价，那么上述问题即可以等价为：

minw,b12∣∣w∣∣2s.t.yi(w⋅xi+b)−1≥0\begin{align*} &min_{w,b}\quad \frac{1}{2}||w||^{2}\\ &s.t.\quad y_{i}(w\cdot x_{i}+b)-1\ge0 \end{align*}

拉格朗日乘子与 KKT 条件

上述问题即为一个不等式约束的最优化问题，可以利用拉格朗日乘子法与KKT条件来求解，令α=[α1,α2,α3,...,αn]T\alpha=[\alpha_{1},\alpha_{2},\alpha_{3},...,\alpha_{n}]^{T}，首先构造拉格朗日函数为：L(w,b,α)=12∣∣w∣∣2−∑iαiyi(w⋅xi+b)+∑iαiL(w,b,\alpha)=\frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i}

假设W∗,b∗,α∗W^{*},b^{*},\alpha^{*}是优化问题的最优解，那么根据KKT条件，W∗,b∗,α∗W^{*},b^{*},\alpha^{*}一定满足以下方程：

∇wL(w∗,b∗,α∗)=w∗−∑i=1Nαi∗yixi=0∇bL(w∗,b∗,α∗)=−∑i=1Nαi∗yi=0αi∗(yi(w∗⋅xi+b∗)−1)=0yi(w∗⋅xi+b∗)−1≥0αi∗≥0\begin{align} &\nabla_{w}L(w^{*},b^{*},\alpha^{*})=w^{*}-\sum_{i=1}^{N}\alpha^{*}_{i}y_{i}x_{i}=0\tag{1}\\ &\nabla_{b}L(w^{*},b^{*},\alpha^{*})=-\sum_{i=1}^{N}\alpha_{i}^{*}y_{i}=0\tag{2}\\ &\alpha_{i}^{*}(y_{i}(w^{*}\cdot x_{i}+b^{*})-1)=0\tag{3}\\ &y_{i}(w^{*}\cdot x_{i}+b^{*})-1\ge 0\tag{4}\\ &\alpha_{i}^{*}\ge0\tag{5} \end{align}

KKT条件主要包括几个方面的内容：1.拉格朗日函数对于原始优化变量的梯度为0，如（1）和（2）2.拉格朗日乘子和不等式约束的左式（化为标准形式）的乘积全为0，如（3）3.原问题的约束条件，如（4）4.拉格朗日乘子非负，如（5）

由（1）和（2）可以得到：

w∗=∑iNαi∗yixi∑iNαi∗yi=0w^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}\\ \sum_{i}^{N}\alpha_{i}^{*}y_{i}=0

对偶问题

根据拉格朗日对偶性，原问题可以化为：

minw,b maxα 12∣∣w∣∣2−∑iαiyi(w⋅xi+b)+∑iαi,αi≥0min_{w,b}\ max_{\alpha}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i},\alpha_{i}\ge 0

即

maxα minw,b 12∣∣w∣∣2−∑iαiyi(w⋅xi+b)+∑iαi,αi≥0max_{\alpha}\ min_{w,b}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i},\alpha_{i}\ge 0

其中minw,b 12∣∣w∣∣2−∑iαiyi(w⋅xi+b)+∑iαimin_{w,b}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i}问题的最优解由KKT条件可以得到为w∗=∑iNαi∗yixiw^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}，并且有∑iNαi∗yi=0\sum_{i}^{N}\alpha_{i}^{*}y_{i}=0，代入上式即可将原问题化为：

maxα−12∑i∑jαiαjyiyj(xi⋅xj)+∑iαis.t.αi≥0\begin{align*} max_{\alpha}\quad&-\frac{1}{2}\sum_{i}\sum_{j}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j})+\sum_{i}\alpha_{i}\\ s.t.\quad&\alpha_{i}\ge 0 \end{align*}

在求解了α∗\alpha^{*}之后，即可根据w∗=∑iNαi∗yixiw^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}求得w∗w^{*}，由于分离超平面的参数是w∗,b∗w^{*},b^{*}决定的，而分离超平面由αi≠0\alpha_{i}\neq0的αi,xi,yi\alpha_{i},x_{i},y_{i}决定的，因此再选取任意jj使得αj≠0\alpha_{j}\neq0，得到b∗=yj−w∗⋅xjb^{*}=y_{j}-w^{*}\cdot x_{j}，这样便可以得到分离超平面w∗⋅x+b∗=0w^{*}\cdot x+b^{*}=0。

对于上面的求解α∗\alpha^{*}的优化问题，我们在下文将会介绍SMO算法来求解 To be continuue…

  • 技术