深入机器学习系列2-支持向量机

写在前面的:

SVM算法是在深度学习大火之前最受欢迎的机器学习算法,也是广大机器学习爱好者的入门算法。请大家系好安全带,当心老司机一言不合就甩你一脸代码!

1 SVM

1.1 介绍

Support Vector Machine 支持向量机是一种机器学习算法。

所以优化问题可以写成:

这等价于最小化

subject to 


Figure1: SVM

事实上,它可以被看作一个带有惩罚项的最小化损失问题。最终,我们希望找到以下问题的最小解

对于这一最优化问题,我们可以使用梯度下降算法来达到最小值。

目标函数为:

所以,迭代 t 时的梯度为:

1.2 SGD

从上一节我们可以看到每次迭代我们都需要所有的数据点来计算梯度。而当数据集变大后,无疑会耗费大量的计算时间。 这就是为什么在大规模梯度下降算法中,我们总会使用 SGD(随机梯度下降)。SDG 在每次迭代时只使用一部分数据而不是全部, 从而降低了计算量。

所以,现在目标函数变成了:

1.3 Pegasos and MLlib implementation

Pegasos 是 SVM 使用梯度下降算法的一种实现。Spark MLlib 也提供了 SVM 的梯度下降实现,于 Pegasos 稍有不同。 主要是梯度的更新速度不同。