Implements an SVM with soft-margin using the communication-efficient distributed dual coordinate ascent algorithm with hinge-loss function. The algorithm solves the following minimization problem:
$$\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)$$
with $\mathbf{w}$ being the weight vector, $\lambda$ being the regularization constant, $$\mathbf{x}i \in \mathbb{R}^d$$ being the data points and $$l{i}$$ being the convex loss functions, which can also depend on the labels $$y_{i} \in \mathbb{R}$$. In the current implementation the regularizer is the $\ell_2$-norm and the loss functions are the hinge-loss functions:
$$l_{i} = \max\left(0, 1 - y_{i} \mathbf{w}^T\mathbf{x}_i \right)$$
With these choices, the problem definition is equivalent to a SVM with soft-margin. Thus, the algorithm allows us to train a SVM with soft-margin.
The minimization problem is solved by applying stochastic dual coordinate ascent (SDCA). In order to make the algorithm efficient in a distributed setting, the CoCoA algorithm calculates several iterations of SDCA locally on a data block before merging the local updates into a valid global state. This state is redistributed to the different data partitions where the next round of local SDCA iterations is then executed. The number of outer iterations and local SDCA iterations control the overall network costs, because there is only network communication required for each outer iteration. The local SDCA iterations are embarrassingly parallel once the individual data partitions have been distributed across the cluster.
The implementation of this algorithm is based on the work of Jaggi et al.
SVM is a Predictor. As such, it supports the fit and predict operation.
SVM is trained given a set of LabeledVector:
fit: DataSet[LabeledVector] => UnitSVM predicts for all subtypes of FlinkML's Vector the corresponding class label:
predict[T <: Vector]: DataSet[T] => DataSet[(T, Double)], where the (T, Double) tuple corresponds to (original_features, label)If we call evaluate with a DataSet[(Vector, Double)], we make a prediction on the class label for each example, and return a DataSet[(Double, Double)]. In each tuple the first element is the true value, as was provided from the input DataSet[(Vector, Double)] and the second element is the predicted value. You can then use these (truth, prediction) tuples to evaluate the algorithm's performance.
predict: DataSet[(Vector, Double)] => DataSet[(Double, Double)]The SVM implementation can be controlled by the following parameters:
{% highlight scala %} 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
// Read the training data set, from a LibSVM formatted file val trainingDS: DataSet[LabeledVector] = env.readLibSVM(pathToTrainingFile)
// Create the SVM learner val svm = SVM() .setBlocks(10)
// Learn the SVM model svm.fit(trainingDS)
// Read the testing data set val testingDS: DataSet[Vector] = env.readLibSVM(pathToTestingFile).map(_.vector)
// Calculate the predictions for the testing data set val predictionDS: DataSet[(Vector, Double)] = svm.predict(testingDS)
{% endhighlight %}
{% top %}