支持向量机（SVM using CoCoA）

支持向量机（SVM using CoCoA）

描述

使用具有合页损失函数的 CoCoA 算法实现了软间隔 SVM。 此算法解决了如下损失函数最小化问题：

$\min{\mathbf{w} \in \mathbb{R}^d} \frac{\lambda}{2} \left\lVert \mathbf{w} \right\rVert^2 + \frac{1}{n} \sum{i=1}^n l_{i}\left(\mathbf{w}^T\mathbf{x}_i\right)$

其中 $\mathbf{w}$ 为权值向量，$\lambda$ 为正则化常数， $\mathbf{x}i \in \mathbb{R}^d$ being the data points and $l${i} 为凸损失函数，并依赖于输出分类 $y_{i} \in \mathbb{R}$。在当前的实现中正则化项为 $\ell_2$ 范数，损失函数为合页损失函数：

$l{i} = \max\left(0, 1 - y{i} \mathbf{w}^T\mathbf{x}_i \right)$

基于前面的选择，问题的定义就等价于软间隔支持向量机(SVM)。最小值通过 SDCA 算法求得，为了让算法在分布式环境下更加高效，COCOA 算法首先在本地的一个数据块上计算若干次 SDCA 迭代，然后再将本地更新合并到有效全局状态中。

全局状态被重新分配到下一轮本地 SDCA 迭代的数据分区，然后执行。 因为只有外层迭代需要网络通信，外层迭代的次数和本地 SDCA 迭代决定了全部的网络消耗。一旦独立的数据分区分布在集群中时，本地 SDCA 是不容易并行的。

算法基于 Jaggi 等人的相关论文实现。

操作

SVM 是一个预测模型（Predictor）。 因此，它支持拟合（fit）与预测（predict）两种操作。

拟合

SVM 通过 LabeledVector 集合进行训练：

• fit: DataSet[LabeledVector] => Unit

预测

SVM 会对 FlinkML Vector 的所有子类预测其对应的分类标签：

• predict[T <: Vector]: DataSet[T] => DataSet[(T, Double)]，其中 (T, Double) 对应（原始特征值，预测的分类）

如果想要对模型的预测结果进行评估，可以对已正确分类的样本集做预测。传入 DataSet[(Vector, Double)] 返回 DataSet[(Double, Double)]。返回结构的首元素为传入参数提供的真值，第二个元素为预测值，可以使用这个(真值, 预测值)集合来评估算法的准确率和执行情况：

• predict: DataSet[(Vector, Double)] => DataSet[(Double, Double)]

参数

SVM 的执行可以通过下面的参数进行控制：

例子

import org.apache.flink.api.scala._
import org.apache.flink.ml.math.Vector
import org.apache.flink.ml.common.LabeledVector
import org.apache.flink.ml.classification.SVM
import org.apache.flink.ml.RichExecutionEnvironment
val pathToTrainingFile: String = ???
val pathToTestingFile: String = ???
val env = ExecutionEnvironment.getExecutionEnvironment
// 从 LibSVM 格式的文件中读取训练数据集
val trainingDS: DataSet[LabeledVector] = env.readLibSVM(pathToTrainingFile)
// 创建 SVM 学习器
val svm = SVM()
  .setBlocks(10)
// 使用 SVM 模型开始训练学习
svm.fit(trainingDS)
// 读取测试数据集
val testingDS: DataSet[Vector] = env.readLibSVM(pathToTestingFile).map(_.vector)
// 对测试数据集进行预测
val predictionDS: DataSet[(Vector, Double)] = svm.predict(testingDS)