机器学习笔记

        在第四节中我们还有一个问题没有解决，即：对求解问题。对求解可以采用SMO算法，此算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。我们先来回顾一下的优化目标函数：

        我们来看一下SMO的主要思想：先选取一对和，选取方法使用启发式方法进行优化，并固定除和之外的其他参数，确定W极值条件下的，而由表示。因为：

        所以有：

        由于a3,a4,...,an都是已固定的值所以上面式子的右侧可以使用一个S来表示它的值：

        当y1和y2异号时（注意，在SVM中y的取值只有两个-1和1），也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图：

        我们规定横轴为a1纵轴为a2，根据约束条件a1和a2既要在直线上也要在矩形内，所以当y1和y2不同时a1和a2的取值范围为：

        同理，当y1和y2不同是a1和a2的取值范围为：

        我们将a1用a2表示并代入W中得：

        展开后通过对W进行求导可以得到a2，然而要保证a2满足，我们使用表示求导求出来的a2,于是有：

        其中为目标与实际的误差：