第八课 顺序最小优化算法

笔记：http://blog.csdn.net/Andrewseu/article/details/48443633
参考：https://zhuanlan.zhihu.com/p/21932911

要点：

1. 对于线性不可分或个别异常点SVM提出的优化方案

• 软边界
• 核函数。基本思想是：将原本的低维特征空间映射到一个更高维的特征空间，从而使得数据集线性可分。
  </br>
  映射到高维
  上图所用的核函数
  常用核函数：
  
  核函数怎么应用？

原始优化模型通过拉格朗日对偶

注意到公式红色部分，表示两个xi和xj做内积，要应用核函数，我们只需要将这个部分替换为对应的核函数即可：

</br></br>

2. 顺序最小优化算法SMO sequential minimal optimization

SMO算法就是为了高效计算上述优化模型而提出的。其是由坐标上升算法衍生而来。
所谓坐标上升算法，就是指：对于含有多个变量的优化问题：每次只调整一个变量，而保证其他变量不变，来对模型进行优化，直到收敛。
SMO的思想类似，由于约束条件

\sum_{i=1}^{m}{\alpha _iy^{(i)}} 的存在，如果按照坐标上升算法，每次只修改一个a的值，是不可行的（因为a的值完全取决于剩下a的m-1个值）。所以每次至少改变一对a的值。

3. SVM应用实例

参考https://zhuanlan.zhihu.com/p/21932911