深入机器学习系列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 稍有不同。 主要是梯度的更新速度不同。

2 SGD in Spark

2.1 treeAggregate

Spark 来计算 SGD 的主要优势使可以分布式地计算梯度，然后将它们累加起来。 在 Spark 中，这一任务是通过 RDD 的 treeAggregate 方法来完成的。 Aggregate 可被视为泛化的 Map 和 Reduce 的组合。 treeAggregate 的定义为

在此方法中有三个参数，其中前两个对我们更重要：

seqOp: 计算每隔 partition 中的子梯度

combOp: 将 seqOp 或上层 combOp 的值合并

depth: 控制 tree 的深度

Figure 2: tree aggregate

2.2 实现（提示：代码块部分可以左右滑动来完整查看哦~）

SGD 是一个求最优化的算法，许多机器学习算法都可以用 SGD 来求解。所以 Spark 对其做了抽象。

可以看到SVMWithSGD继承了GeneralizedLinearAlgorithm，并定义 optimizer 来确定如何获得优化解。 而 optimizer 即是 SGD 算法的实现。正如上节所述，线性 SVM 实际上是使用 hinge 损失函数和一个 L2 惩罚项的线性模型，因此这里使用了HingeGradient和SquaredL2Updater作为GradientDescent的参数。

此节中,Code 1展示了GradientDescent的主要执行逻辑。 重复执行numIterations次以获得最终的 Ｗ。

首先,通过取一部分样本. 然后使用。 在中,会通过更新，如果

y⟨w,x⟩

，即分类错误。 在中,通过被集合起来。 当获得后, 我们就可以计算和了。 最后, 我们使用更新。

Code 1: GradientDescent 代码片断

3实验和性能

3.1 正确性验证

我们模拟了一些简单的 2D 和 3D 数据来验证正确性。

Figure 3: 2D linear

Figure 4: 3D linear

3.2 收敛速度

我们比较两种实现的收敛速度差异。这里，我们使用 5GB 带有 1000 个特征的模拟数据。使用 4 个 executors 并迭代 100 次。

Figure 5: before aligning Y axis

Figure 6: after aligning Y axis

4 参考文献

Zaharia, Matei, et al. "Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing." Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012

Zaharia, Matei, et al. "Spark: cluster computing with working sets." Proceedings of the 2nd USENIX conference on Hot topics in cloud computing. Vol. 10. 2010

Shalev-Shwartz, Shai, et al. "Pegasos: Primal estimated sub-gradient solver for svm." Mathematical programming 127.1 (2011): 3-30