Subscribe:

Pages

Working with RubySVM

A classification model is a tool for mapping a sequence of inputs to a predicted output. To construct a classification model, we have to train it on some data where we have the expected output. There are many kinds of classification models; here, I build SVM models using the RubySVM library. For an explanation of SVMs and how to best use the SVM library, please see the LibSVM documentation; this post is an example of using the library from Ruby.

I use the UCI letter recognition example discussed in this earlier post, and assume the SVM library has been installed, as also discussed earlier.

In the letter recognition example, each letter has a "label" (called 'letter') and several attributes, such as 'x-box', 'width', 'height', etc. The classification problem is to compute the label from the attributes. To begin, we assume a dataset of examples which contain attributes and a label.

General Method

The pattern for constructing and using an SVM model is as follows:
  1. The data is partitioned into a training and a test set. The test set is used at the end, to evaluate the model. It is not used at all during model development or parameter selection.
  2. The training set is partitioned into a cross-validation set and an actual training set.
  3. Search through the parameter space of possible SVM models, training each model on the actual training set, and evaluating it on the cross-validation set.
  4. Choose the parameter settings which produce the best performance on the cross-validation set.
  5. Use the chosen parameter settings to evaluate the SVM model on the test set, and report this final figure.
There are many improvements needed for serious work, but that pattern is enough to get an idea of how building a model works, and, most importantly, sort out the main requirements on a Ruby program to handle all the steps.

Creating a Classification Problem

Our dataset used the following structure:
LetterInstance = Struct.new(:letter, :x_box, :y_box, :width, :height,:on_pixels, :x_bar, :y_bar, :x2bar, 
      :y2bar,:xybar, :x2ybar, :xy2bar, :x_ege, :xegvy,:y_ege, :yegvx)

The field 'letter' is the label, and the rest are the attributes. Due to the way we read in and create instances of this structure, the attributes are actually strings. We store all the data into a global array, called @@data.

The data for the SVM needs to be separated into the class 'labels' and the values for the attributes. All the values need to be numeric. For the labels, we can just assign integer values to each class. For the attribute values, we need each number to be in the range [0,1] or [-1,1]. We achieve this by rescaling the actual attribute values to fit into the range. For the letter task, each attribute value is a number from 0 to 15, inclusive; dividing by 15 to form a fractional number gets each attribute value into the right range.

The following code provides two functions to collect the label and an array of attribute values for a given letter-recognition example:

@@classes = @@data.collect {|datum| datum.letter}.uniq.sort

def make_number char
  @@classes.index char
end

def transform datum
  data = []
  1.upto(datum.members.size-1) do |i|
    data << datum[i].to_f / 15.0 # all data in range [0,15]
  end
  data
end

We must now randomise the list (using shuffle), and collect samples for training, cross-validation, and testing. This is easy using subranges:

TrainSet = @@data[0...2000].collect {|datum| transform(datum)}
TrainLabels = @@data[0...2000].collect {|datum| make_number(datum.letter)}
CrossSet = @@data[9000...10000].collect {|datum| transform(datum)}
CrossLabels = @@data[9000...10000].collect {|datum| make_number(datum.letter)}
TestSet = @@data[10000..-1].collect {|datum| transform(datum)}
TestLabels = @@data[10000..-1].collect {|datum| make_number(datum.letter)}


Training an Individual Model

To train a model, we create an instance of SVM::Problem, which is constructed by adding each instance from the training set, in turn, giving its label and attribute values; TrainProblem is constructed here, to hold the training data. The model is trained by creating it using the Problem description and a set of Parameters. The following function constructs an SVM model using a given problem and values for the Cost and Gamma parameters; other parameter values are set to default settings. Here, I use an RBF kernel for the SVM, but others are available.

def make_problem(data, labels)
  problem = SVM::Problem.new
  data.each_index do |i|
    problem.addExample(labels[i], data[i])
  end
  problem
end

def make_rbf_svm_model(problem, cost, gamma)
  params = SVM::Parameter.new
  params.C = cost
  params.gamma = gamma
  params.kernel_type = SVM::RBF
  # some default values
  params.svm_type = SVM::NU_SVC
  params.degree = 1
  params.coef0 = 0
  params.eps = 0.001
  # construct the model
  SVM::Model.new(problem, params)
end

TrainProblem = make_problem(TrainSet, TrainLabels)


Evaluating a Model

Once we have trained a model, we can see what prediction it makes for a given instance and compare that with the true label (the one from the original dataset). The following code runs through an array of examples and counts up the number of errors made by the given model:

def test_model(model, data, labels)
  errors = 0
  labels.each_index do |i|
    prediction, probs = model.predict_probability(data[i])
    errors += 1 if labels[i] != prediction
  end
  errors
end

Searching for the best Cost and Gamma

The critical parameters for the Radial-Basis Function kernel are the Cost function and Gamma. We need to do a search across a range of possible values, to locate the model which performs the best. To evaluate the model, we use a cross-validation set, which is taken from the training data, but different from the test set, which we only use at the very end, once we have selected the SVM parameters.

The following code performs a simple grid search across a range of values for Cost and Gamma, evaluating the model generated by each set of parameters against the cross-validation set. The model with the fewest errors is then selected. 

Costs = [2**-5,2**-3,2**-1,1,2,8,2**5,2**8,2**10,2**13,2**15]
Gammas = [2**-15,2**-12,2**-8,2**-5,2**-3,2**-1,2,2**3,2**5,2**7,2**9]

best_model = nil
lowest_error = CrossLabels.size
Costs.each do |cost|
  Gammas.each do |gamma|
    svm_model = make_rbf_svm_model(TrainProblem, cost, gamma)
    cross_validation_result = test_model(svm_model, CrossSet, CrossLabels)
    if cross_validation_result < lowest_error
      best_model = svm_model
      lowest_error = cross_validation_result
    end
    puts "Testing: C = #{cost}  G = #{gamma} -> #{cross_validation_result}"
  end
end

puts "Error rate is: #{test_model(best_model, TestSet, TestLabels)*100.0/TestLabels.size}%"


Final Result

The performance of the final model is evaluated by finding the number of errors it makes against the test dataset. In this case, I get an error rate of around 16%, which is not too bad, as I only trained on 2000 of the 20000 examples.

Summary

This description has covered the very simplest mechanics of working with RubySVM to build SVM models of data. To get good quality models and properly evaluate the results, you need to be more careful in your selection of parameters and use of cross-validation and test sets. The LibSVM documentation is a good place to start. For optimum performance, the selection of the Cost and Gamma values is critical, and needs finer scale searching than I used above.

You do have to be patient with these techniques. The grid search is not quick; it took around 35 minutes on my 2.8GHz machine to run through all the models, and this was a fairly crude search. This is not the fault of Ruby, as the computation time is required for LibSVM to build the models. Ruby manages the entire data collection, transformation and model selection process in about 80 lines of fairly straightforward code.
Labels: ,