The library was originally written in C before being ported to Java. It can be downloaded from http://www.csie.ntu.edu.tw/~cjlin/libsvm as a ZIP or tar.gzip file. The library includes the following classifier modes:

LIBSVM has the distinct advantage of using Sequential Minimal Optimization (SMO), which reduces the time complexity of a training of n observations to O(n² ). LIBSVM documentation covers both the theory and implementation of hard and soft margins and is available at http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf.

The implementation of the different support vector classifiers and the support vector regression in LIBSVM is broken down into the following five Java classes:

The library also includes template programs for training, prediction, and normalization of datasets.

Let's create a Scala wrapper to the LIBSVM library to improve its flexibility and ease of use.

The implementation of the support vector machine algorithm uses the design template for classifiers (refer to the Design template for classifier section of the Appendix).

The key components of the implementation of an SVM are as follows:

The key software components of the support vector machine are described in the following UML class diagram:

UML class diagram for the support vector machine

The UML diagram omits the helper traits and classes such as Monitor or Apache commons math components.

LIBSVM exposes several parameters for the configuration and execution of any of the SVM algorithms. Any SVM algorithm is configured with three categories of parameters, which are as follows:

trait SVMConfigItem { def update(param: svm_parameter): Unit }

sealed trait SVMFormulation extends SVMConfigItem {   
  def update(param: svm_parameter): Unit 
}

class CSVCFormulation (c: Double) extends SVMFormulation {   
   override def update(param: svm_parameter): Unit = {      
     param.svm_type = svm_parameter.C_SVC
     param.C = c
  }
}

sealed trait SVMKernel extends SVMConfigItem {    
  override def update(param: svm_parameter): Unit 
}

class RbfKernel(gamma: Double) extends SVMKernel {   
  override def update(param: svm_parameter): Unit = {     
    param.kernel_type = svm_parameter.RBF     
    param.gamma = gamma
}

class SVMExecution(cacheSize: Int, eps: Double, nFolds: Int) 
extends SVMConfigItem {
  override def update(param: svm_parameter): Unit = {     
    param.cache_size = cacheSize //1
    param.eps = eps //2
  }
}

class SVMConfig(formula: SVMFormulation, kernel: SVMKernel,
     exec: SVMExecution) {
  val param = new svm_parameter    
  formula.update(param) //3
  kernel.update(param)  //4
  exec.update(param)  //5
}

We need to create an adapter object to encapsulate the invocation to LIBSVM. The object SVMAdapter hides the LIBSVM internal data structures, svm_model and svm_node:

object SVMAdapter {
  type SVMNodes = Array[Array[svm_node]]
  class SVMProblem(numObs: Int, expected: Array[Double]) //6
   
  def createSVMNode(dim: Int, 
                 x: Array[Double]): Array[svm_node] //7
  def predictSVM(model: SVMModel, x: Array[Double]): Double//8
  def crossValidateSVM(
     problem: SVMProblem, //9
     param: svm_parameter, 
     nFolds: Int, 
     expected: Array[Double]) 
  def trainSVM(
     problem: SVMProblem,  //10
     param: svm_parameter): svm_model 
}

The object SVMAdapter is a single-entry point to LIBSVM for training, validating an SVM model, and executing predictions:

public class svm_node implements java.io.Serializable {   
  public int index;    
  public double value;
}

The SVMAdapter methods are described in the next section.

The model for SVM is defined with the following two components:

The residuals r = y – f(x) are computed in the LIBSVM library.

Next, let's create the first support vector classifier for the two-class problems. The SVM class implements the monadic data transformation ITransform that generates implicitly a model from a training set as described in the Monadic data transformation section in Chapter 2, Data Pipelines (line 11).

The constructor for SVM follows the template described in the Design template for classifiers section of Appendix. It takes a configuration of type SVMConfig, a set of observations xt of type Array[T], and a set of labels (expected values) of type, DblVec as arguments (line 12):

class SVM[T: ToDouble](
  config: SVMConfig, 
  xt: Vector[Array[T]], 
  expected: DblVec)  //12
extends ITransform[Array[T],Double]{ //11

  val normEPS = config.eps*1e-7 //13
  val model: Option[SVMModel] = train //14

  def accuracy: Option[Double] = model.map( _.accuracy) //15
  def mse: Option[Double] //16
  def margin: Option[Double] //17
}

The normEPS is used for rounding errors in the computation of the margin (line 13). The model of type SVMModel is generated through training by the SVM constructor (line 14). The last four methods are used to compute the parameters of the model accuracy (line 15), the mean square of errors, mse (line 16), and the margin (line 17).

Let's look at the training method, train:

def train: Option[SVMModel] = Try {
  val problem = new SVMProblem(xt.size, expected.toArray) //18
  val dim = dimension(xt)
  xt.indices.foreach( 
    n => problem.update(n, createNode(dim,x(n)).map((c(_)))))//12
  )
  new SVMModel(
     trainSVM(problem, config.param),accuracy(problem) //20
  )
}.toOption

The train method creates a SVMProblem that provides LIBSVM with training components (line 18). The purpose of the SVMProblem class is to manage the definition of training parameters implemented in LIBSVM, as follows:

class SVMProblem(numObs: Int, expected: Array[Double]) {
  val problem = new svm_problem //21
  problem.l = numObs
  problem.y = expected 
  problem.x = new SVMNodes(numObs)

  def update(n: Int, node: Array[svm_node]): Unit = 
     problem.x(n) = node //22
}

The arguments of the SVMProblem constructor, the number of observations and the labels or expected values are used to initialize the corresponding data structure, svm_problem in LIBSVM (line 21). The method update maps each observation, defined as an array of svm_node to the problem (line 22).

The method createNode creates an array of svm_node from an observation. A svm_node in LIBSVM is the pair of the index j of a feature in an observation (line 23) and its value y (line 24):

def createNode(dim: Int,x: Array[Double]): Array[svm_node] = 
   x.indices./:(new Array[svm_node](dim)){(newNode, j) =>
     val node = new svm_node
     node.index= j	//23
     node.value = x(j)	//24
     newNode(j) = node 
     newNode
   }

The mapping between an observation and a LIBSVM node is illustrated in the following diagram:

Indexing of observations using LIBSVM

The method trainSVM pushes the training request with a well-defined problem and configuration parameters to LIBSVM by invoking the svm_train method (line 26):

def trainSVM(problem: SVMProblem, 
            param: svm_parameter): svm_model =
 svm.svm_train(problem.problem, param) //26

The accuracy is the ratio of true positive plus the true negative over the size of the test sample (refer to the Key metrics section of Chapter 2, Data Pipelines). It is computed through cross-validation only if the number of folds is initialized in the SVMExecution configuration class as greater than 1. Practically, the accuracy is computed by invoking the cross-validation method, svm_cross_validation, in the LIBSVM package, and then computing the ratio of the number of predicted values that match the labels over the total number of observations:

def accuracy(problem: SVMProblem): Double =
  if( config.isCrossValidation ) {
     val target = crossValidateSVM(problem, config.param,  //27
                             config.nFolds, expected.size)

     target.view.zip(expected.view)
             .count{ case(x, y) => abs(x-y) < config.eps }//28
             .toDouble/expected.size
  }
  else 0.0

The call to the crossValidateSVM method of SVMAdapter forwards the configuration and execution of the cross validation with config.nFolds (line 27):

def crossValidateSVM(
  problem: SVMProblem, 
  param: svm_parameter, 
  nFolds: Int, 
  size: Int) = {
    val target = Array.fill(size)(0.0)
    svm.svm_cross_validation(
       problem.problem, param, nFolds, target)
    )
    target
}

The Scala filter weeds out the observations that were poorly predicted (line 28). This minimalist implementation is good enough to start exploring the support vector classifier.

The implementation of the classification method |> for the SVM class follows the same pattern as the other classifiers. It invokes the predictSVM method in SVMAdapter that forwards the request to LIBSVM (line 29):

override def |> : PartialFunction[Array[T], Try[Double]] =  {
   case x: Array[T] if(x.size == dimension(xt) && isModel) =>
     Try(predictSVM(model.get, x.map(c(_))) )  //29
}

The first evaluation consists of understanding the impact of the penalty factor C to the margin in the generation of the classes. Let's implement the computation of the margin. The margin is defined as 2/|w| and implemented as a method of the SVM class, as follows:

def margin: Option[Double] = model.map{ m => 
   1.0/sqrt(m.residuals.reduce(_ * _))
}

The first instruction computes the sum of the squares, wNorm, of the residuals r = y – f(x|w). The margin is ultimately computed if the sum of squares is significant enough to avoid rounding errors.

The margin is evaluated using an artificially generated time series and labeled data. First, we define the method to evaluate the margin for a specific value of the penalty (inversed regularization coefficient) factor C:

val GAMMA = 0.8; val CACHE_SIZE = 1<<8
val NFOLDS = 2; val EPS = 1e-5

def evalMargin(features: Vector[Array[Double]], 
               expected: DblVec, 
               c: Double): Int = {
  val execEnv = SVMExecution(CACHE_SIZE, EPS, NFOLDS)
  val config = SVMConfig(new CSVCFormulation(c), 
                        new RbfKernel(GAMMA), 
                        execEnv
               )
  val svc = SVM[Double](config, features, expected)
  svc.margin.map(_.toString) //30
}

The method evalMargin uses the execution parameters, CACHE_SIZE, EPS, and NFOLDS. The execution displays the value of the margin for different values of C (line 30). The method is invoked iteratively to evaluate the impact of the penalty factor on the margin extracted from the training of the model. The test uses a synthetic time series to highlight the relation between C and the margin. The synthetic time series created by the method generate consists of two training sets of an equal size, N:

Consider the following code:

def generate: Option[(Vector[Array[Double]],Array[Double])] = {
  val z = Vector.tabulate(N)(i => {
     val ri = i*(1.0 + 0.2*nextDouble)	
     Array[Double](i, ri)  //31
  }) ++
  Vector.tabulate(N)(i =>Array[Double](i,i*nextDouble))

  normalizeArray(z).map(
     (_, Array.fill(N)(1) ++ Array.fill(N)(-1))
  ).toOption  //32
}

The evalMargin method is executed for values C ranging from 0.1 to 5:

generate.map(y => 
  (0.1 until 5.0 by 0.1)
    .flatMap(evalMargin(y._1, y._2, _)).mkString("
")
)

class A { val x = 5;  final val y = 8 } 
class B extends A { 
  override val x = 9 // OK    
  override val y = 10 // Error 
}

The following chart illustrates the relation between the penalty, or cost factor, C, and the margin:

The margin value versus C-penalty factor for a support vector classifier

As expected, the value of the margin decreases as the penalty term C increases. The C penalty factor is related to the L₂ regularization factor ? as C ~ 1/?. A model with a large value of C has a high variance and a low bias, while a small value of C will produce lower variance and a higher bias.

The next test consists of comparing the impact of the kernel function on the accuracy of the prediction. Once again, a synthetic time series is generated to highlight the contribution of each kernel. The test code uses the runtime prediction or classification method |> to evaluate the different kernel functions. Let's create a method to evaluate and compare these kernel functions. All we need is the following (line 33):

Consider the following code:

val C = 1.0
def accuracy(
  xt: Vector[Array[Double]], 
  test: Vector[Array[Double]], 
  labels: DblVec, 
  kF: SVMKernel): Double = { //33

  val config = SVMConfig(new CSVCFormulation(C), kF) //34
  val svc = SVM[Double](config, xt, labels)
  val pfnSvc = svc |> //35
  
  test.zip(labels).count{ case(x, y) => 
    if(pfnSvc.isDefinedAt(x)) pfnSvc(x).get == y else false
  }.toDouble/test.size //36
}

The configuration, config, of the SVM uses C penalty factor 1, the C-formulation, and the default execution environment (line 34). The predictive partial function pfnSvc (line 35) is used to compute the predictive values for the test set. Finally, the method accuracy counts the number of successes for which the predictive values match the labeled or expected values. The accuracy is computed as the ratio of the successful prediction over the size of the test sample (line 36).

In order to compare the different kernels, let's generate three datasets of the size 2N for a binomial classification using the pseudo-random data generation method genData:

def genData(
  variance: Double, 
  mean: Double): Vector[Array[Double]] = {

  val rGen = new Random(System.currentTimeMillis)
  Vector.tabulate(N){ _ =>
    rGen.setSeed(rGen.nextLong)
    Array[Double](rGen.nextDouble, rGen.nextDouble)
        .map(variance*_ - mean)  //37
  }
}

The random value is computed through a transformation f(x) = variance*x = mean (line 37). The training and test sets consist of the aggregation of two classes of data points:

Consider the following code for the training set:

val trainSet = genData(a, b) ++ genData(a, 1-b)
val testSet = genData(a, b) ++ genData(a, 1-b)

The parameters a, b are selected from two groups of training data points with various degree of separation to illustrate the separating hyperplane.

The following chart describes the high margin; the first training set generated with the parameters a = 0.6 and b = 0.3 illustrates the highly separable classes with a clean and distinct hyperplane:

Scatter plot for training and testing sets with a = 0.6 and b = 0.3

The following chart describes the medium margin; the parameters a = 0.8 and b = 0.3 generate two groups of observations with some overlap:

Scatter plot for training and testing sets with a = 0.8 and b = 0.3

The following chart describes the low margin; the two groups of observations in this last training are generated with a = 1.4 and b = 0.3 and show a significant overlap:

Scatter plot for training and testing sets with a = 1.4 and b = 0.3

The test set is generated in a similar fashion as the training set, as they are extracted from the same data source:

val GAMMA = 0.8; val COEF0 = 0.5; val DEGREE = 2 //38
val N = 100

def compareKernel(a: Double, b: Double) {
  val labels = Vector.fill(N)(0.0) ++ Vector.fill(N)(1.0)

  evalKernel(trainSet, testSet,labels,new RbfKernel(GAMMA)) 
  evalKernel(trainSet, testSet, labels, 
      new SigmoidKernel(GAMMA)) 
  evalKernel(trainSet, testSet, labels, LinearKernel) 
  evalKernel(trainSet, testSet, labels, 
      new PolynomialKernel(GAMMA, COEF0, DEGREE))
}

The parameters for each of the four kernel functions are arbitrary selected from textbooks (line 38). The evalKernel method defined earlier is applied to the three training sets: high margin (a = 1.4), medium margin (a = 0.8), and low margin (a = 0.6), with each of the four kernels (RBF, sigmoid, linear, and polynomial). The accuracy is assessed by counting the number of observations correctly classified for all the classes for each invocation of the predictor, |>:

Comparative chart of kernel functions using synthetic data

Although the different kernel functions do not differ in terms of their impact on the accuracy of the classifier, you can observe that the RBF and polynomial kernels produce results that are slightly more accurate. As expected, the accuracy decreases as the margin decreases. A decreasing margin is a sign that the cases are not easily separable, affecting the accuracy of the classifier:

Impact of the margin value on the accuracy of RBF and Sigmoid kernel functions

In summary, there are four steps in creating an SVC-based model:

As mentioned earlier, this test case relies on synthetic data to illustrate the concept of margin and compare kernel methods. Let's use the support vector classifier for a real-world financial application.

The purpose of the test case is to evaluate the risk for a company to curtail or eliminate its quarterly or yearly dividend. The features selected are financial metrics relevant to a company's ability to generate cash flow and pay out its dividends over the long term.

We need to select any subset of the following financial technical analysis metrics (refer to the Metrics section of the Appendix):

The earnings trend has the following values:

The labels or expected output, dividend changes, is categorized as follows:

Let's combine two of these three labels, {-1, 0, 1}, to generate two classes for the binary SVC:

The different tests are performed with a fixed set of configuration parameters C and GAMMA and a two-fold validation configuration:

val path = "supervised/svm/dividends2.csv"	
val C = 1.0
val GAMMA = 0.5
val EPS = 1e-2
val NFOLDS = 2

val extractor = relPriceChange :: debtToEquity :: 
    dividendCoverage :: cashPerShareToPrice :: epsTrend :: 
    shortInterest :: dividendTrend :: 
    List[Array[String] =>Double]()  //39
						
val pfnSrc = DataSource(path, true, false,1) |> //40
val config = SVMConfig(new CSVCFormulation(C), 
     new RbfKernel(GAMMA), SVMExecution(EPS, NFOLDS))

for {
  path <- getPath(dataPath)
  pfnSrc <- DataSource(path, true, false, 1) //40
  input <- pfnSrc.|>(extractor) //41
  obs <- getObservations(input) //42
} yield {
  svc = SVM[Double](config, obs, input.last.toVector)
  show(s"${svc.toString}
accuracy=${svc.accuracy.getOrElse(-1)}")	
}

The first step is to define the extractor, that, is the list of fields to retrieve from the file, dividends2.csv (line 39). The partial function pfnSrc generated by the DataSource transformation class (line 40) converts the input file into a set of typed fields (line 41). An observation is an array of fields. The sequence of observations, obs, are generated from the input fields by transposing the matrix observations x features (line 42):

def getObservations(input: Vector[Array[Double]]):   
     Try[Vector[Array[Double]]] = Try {
  transpose( input.dropRight(1).map(_.toArray) ).toVector
}

The test computes the model parameters and the accuracy from the cross-validation during the instantiation of SVM.

The test is repeated with a different set of features and consists of comparing the accuracy of the support vector classifier for different features sets. The features sets are selected from the content of the .csv file by assembling the extractor with different configurations, as follows:

val extractor = … :: dividendTrend :: ....

The following bar chart displays the various values of the accuracy of the different SVM models, using the training set A.

Comparative study of trading strategies using binary SVC

The test demonstrates that the selection of the proper features set is the most critical step in applying the SVM, or any other model for that matter, to classification problems. In this case, the accuracy is also affected by the small size of the training set. The increase in the number of features also reduces the contribution of each specific feature to the loss function.

The same process is repeated for the test B whose purpose is to classify companies with decreasing dividends and companies with stable or increasing dividends, as shown in the following graph:

Comparative study of trading strategies using binary SVC

The difference, in terms of accuracy of prediction, between the first three features set and the last two features set in the preceding graph is more pronounced in test A than in test B. In both tests, the feature eps (earning per share) trend improves the accuracy of the classification. It is a particularly good predictor for companies with increasing dividends.

The problem of predicting the distribution (or not) dividends can be restated as evaluating the risk of a company to dramatically reduce its dividends.

What is the risk a company eliminates its dividend altogether? Such a scenario is rare, and those cases are outliers. A one-class support vector classifier can be used to detect outliers or anomalies [12:13].