SVM——（七）SMO（序列最小最优算法）

本文主要是介绍SVM——（七）SMO（序列最小最优算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在说SMO (Sequential minimal optimization)之前，先介绍一种与之类似的算法，坐标上升（下降）算法.

1.Coordinate ascent

所谓坐标上升（下降）指的是同一个算法，只是若实际问题是求极大值则是上升，反之为下降。我们知道梯度下降算法在每次迭代过程中都是沿着梯度的（反）方向进行的；而坐标下降算法则是在每次迭代中分步沿着你n个(n为特征维度)方向进行的。下图是2维情况下，两者求解的示意图。

具体的就是每次只把第i个变量看做是未知数，其他看做常数进行求导，令为0解出第i个变量。求出所有参数的表达式后，利用旧的参数一次更新得到每一个新的参数。也就是：梯度下降强调所有参数同时（simultaneously)更新,而坐标下降则是每个参数分别更新

下面是一个两者的一个代码片段：

% gradient descentfor i = 1:200grad(1)=4*x1-2*x2-4;grad(2)=-2*x1+10*x2-24;% 都是用旧的参数得到梯度x = x-alpha*grad;% 同时更新得到新的参数f1 = f(x(1),x(2));
end% coordinate descent 
for i = 200x1=1+0.5*x2;x2=2.4+0.2*x1;% 用上一步更新的参数，来更新另外一个参数，未同时f2 = f(x1,x2);
end

源码地址

2.SMO算法

如下我们要之前推导出来要优化的目标函数：
$$\begin{array}{rl}\underset{\alpha }{\max }& W(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j⟨x^{(i)},x^{(j)}⟩\\ s.t.& 0\le {\alpha }_i\le C,i=1,...,m\\ & \sum _{i=1}^m{\alpha }_i{y}^{(i)}=0\end{array}\text{\hspace{1em}(2.1)}$$

照着上面的想法，我们是否也能将同样的思路用在此处呢？答案是否定的，因为此处多了一个约束条件。

例如，我们将${\alpha }_1$看做是未知量，其它视为常量，那么由约束条件我们可以得到：
$$\begin{array}{r}{\alpha }_1{y}^{(1)}=-\sum _{i=1}^m{\alpha }_i{y}^{(i)}(\text{两边同乘以}{y}^{(1)})\end{array}$$

这篇关于SVM——（七）SMO（序列最小最优算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---