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:
- 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.
- The training set is partitioned into a cross-validation set and an actual training set.
- 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.
- Choose the parameter settings which produce the best performance on the cross-validation set.
- Use the chosen parameter settings to evaluate the SVM model on the test set, and report this final figure.
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.
