Keeping wxRuby GUI Working with Threads

A big problem with GUI applications is the unresponsive interface, which happens when the program is busy working on a complex task, leaving no time for updating the graphical interface. All graphical programs performing significant work will require at least two working threads: one thread to look after the graphical interface, redrawing the windows and buttons; and one thread to look after the task.

The following program illustrates the problem. The display is a simple menu with a 'start' item on it. Selecting 'start' will begin a thread displaying ten messages into the text control; the task is just to add up a lot of numbers. Although this works, none of the messages appears until the entire 'busy_task' method is complete.

require 'wx'

class MyFrame < Wx::Frame
  def initialize
    super(nil, :title => "Thread example")

    set_menu_bar menubar

    @text = Wx::TextCtrl.new(self, :style => Wx::TE_MULTILINE)
    @tasks = 0
  end

  def menubar
    menubar = Wx::MenuBar.new
    file_menu = Wx::Menu.new
    about_item = Wx::MenuItem.new(file_menu, Wx::ID_ANY, "About")
    evt_menu(about_item) { @text.append_text "About\n" }
    file_menu.append_item about_item
    start_item = Wx::MenuItem.new(file_menu, Wx::ID_ANY, "Start")
    evt_menu(start_item) { busy_task} 

    file_menu.append_item start_item

    menubar.append(file_menu, "File")
    menubar
  end

  def busy_task
    @tasks += 1
    tasks = @tasks
    10.times do 
      @text.append_text "running #{tasks} ... #{Time.new}\n"
      (1...1000_000).inject :+
    end
    @text.append_text "Thread #{tasks} done\n"
  end
end

Wx::App.run do 
  MyFrame.new.show
end

Threads and Timers

We can improve on the above code by placing the work within the 'busy_task' method into a thread:

  def busy_task
    # start task in a separate thread
    Thread.new do 
      @tasks += 1
      tasks = @tasks
      10.times do 
        @text.append_text "running #{tasks} ... #{Time.new}\n"
        (1...1_00_000).inject :+
      end
      @text.append_text "Thread #{tasks} done\n"
    end
  end
end

This will indeed work. The GUI stays responsive, and more than one thread can be active, by selecting the 'start' menu item again. However, you may find the working thread seems to stop doing anything at times; this happens if I switch focus to another window, so the ruby application is running in the background.

The second improvement is to add a Timer. This is created in the initialize method for the frame. The Timer's role is to wake up after a short period of time, and pass processing control to the next thread. In this case, I make the Timer wake up after 10 milliseconds.

  def initialize
    super(nil, :title => "Thread example")

    set_menu_bar menubar

    # -- this timer interrupts every 100ms and gets next thread active
    # -- if you don't have the timer, the GUI does not update if window 
    #    in background
    timer = Wx::Timer.new(self, Wx::ID_ANY)
    evt_timer(timer.id) {Thread.pass}
    timer.start(10)

    @text = Wx::TextCtrl.new(self, :style => Wx::TE_MULTILINE)
    @tasks = 0
  end

Summary

Worker Threads and a Timer to make sure the Threads are kept active is probably the key to keeping wxRuby's GUI active under large-running tasks, although I expect to have to do some experimenting in future. For better information, Mario Steele has described the principles here and in a tutorial.

Using LibSVM from Ruby with data in files

In previous posts, I looked at RubySVM and how to set up models with data held within the memory of a running Ruby process. I have found this does not scale up to larger datasets of images, taking up to a gigabyte in storage on disk, and so I have adopted a different approach, constructing training/test files on disk and then calling the command line svm-train and svm-predict functions. Ruby then drives the whole process, automating the construction of the datasets, selection of the best models, and final evaluation. I use the UCI Letter Recognition dataset discussed earlier as an example, but the approach is fully general.

Calling System Commands

The first step in controlling external programs is calling them, and for this Ruby's backtick syntax is ideal. `ls` will call the ls command, returning the result as a string, which we can store with result = `ls`: result.split("\n") then produces an array of filenames in the current directory.

This backtick notation supports the interpolation of arbitrary Ruby code, just like in
strings. Thus, writing `ls *.#{extension}` will use the value of extension to list file of the given extension only.

Try it from irb:

peter@peter-desktop:~/Code$ irb
irb(main):001:0> `ls`
=> "instances.html\njruby.jar\ntest-instances.rb\ntrial-kmeans.rb\nweather.arff\nweka.jar\n"
irb(main):002:0> result = `ls`
=> "instances.html\njruby.jar\ntest-instances.rb\ntrial-kmeans.rb\nweather.arff\nweka.jar\n"
irb(main):003:0> result.split("\n")
=> ["instances.html", "jruby.jar", "test-instances.rb", "trial-kmeans.rb", "weather.arff", "weka.jar"]
irb(main):004:0> extension = "rb"
=> "rb"
irb(main):005:0> `ls *.#{extension}`.split("\n")
=> ["test-instances.rb", "trial-kmeans.rb"]

Constructing the Datasets

The data is read in, just like I did before, creating an array @@data containing instances of the LetterInstance datatype. I then use input parameters to partition the dataset into training, cross-validation and test datasets:

# Read in letter-recognition UCI data

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)

@@data = []

File.open("letter-recognition.data", "r") do |f|
  f.each_line do |line|
    @@data << LetterInstance.new(*line.strip.split(","))
  end
end

# -- using given proportion for training/cross-validation sets, create three files

if ARGV.length != 2
  puts "To use: ruby train-models.rb TRAINING_PROPORTION CROSS_PROPORTION"
  exit
end

@@training_proportion = ARGV[0].to_f
@@cross_validation_proportion = ARGV[1].to_f

@@num_training = (@@data.length * @@training_proportion).floor
@@num_cross = (@@num_training * @@cross_validation_proportion).floor

# Select Train/Cross/Test sets
# -- note, cross-validation size is taken out of the training-set

@@data.shuffle!

TrainSet = @@data[@@num_cross...@@num_training]
CrossSet = @@data[0...@@num_cross]
TestSet = @@data[@@num_training..-1]

The three datasets must now be saved onto disk, to form the datasets to pass to the SVM. The file format for an SVM places each instance onto a single line in the file. Each instance has its class first, and then its attribute values. Every item is separated by a space. The class must be a number, and the attribute values should be in the range [0,1] or [-1,1]. The attribute-values are written by writing the index of the attribute, followed by a colon, and then the value. An example from the training file is:

17 0:0.466666666666667 1:0.6 2:0.666666666666667 3:0.533333333333333 ....

The advantage of this notation is that it supports sparse data - any attribute that has value 0 can simply be ignored.

The following code constructs the required data:

# Create SVM format of features in instance, rescaling to [0,1]
def make_data item
  str = ""
  (item.length-1).times do |i|
    str << "#{i}:#{item[i+1].to_f/15.0} "
  end
  str
end

def save_file(dataset, filename)
  File.open(filename, "w") do |f|
    dataset.each_with_index do |item, index|
      f.puts "#{item.letter.ord - 65} #{make_data(item)}"
    end
  end
end

save_file(TrainSet, "training-data.dat")
save_file(CrossSet, "cross-data.dat")
save_file(TestSet, "test-data.dat")

Training the Models

I create each model using svm-train, supplying it a training data set and set of parameters. As I am creating SVMs with an RBF kernel, there are two parameters that particularly interest me: cost and gamma. I will save a model file for each pair of parameters, embedding the parameter value in the name. This is all done by string interpolation in the backtick call to svm-train.

# -- train models using Cost/Gamma values and external system
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]

Costs.each do |cost|
  Gammas.each do |gamma|
    `svm-train -s 1 -t 2 -d 3 -r 0 -e 0.001 -c #{cost} -g #{gamma} training-data.dat l-#{cost.to_f}-#{gamma.to_f}.model`
  end
end

Evaluating a Model

svm-predict is the command-line tool for evaluating a model on a given dataset. It produces two sets of outputs. A file containing the actual predictions of the model for each instance in the dataset, and a printed output of the model's accuracy. This accuracy is a percentage correct. We can retrieve it using a regular expression match on the result of running svm-predict.

Our models are defined by their cost and gamma values, using the format above. Given the filename of a dataset to test on, the following function will run svm-predict and parse its output to produce the model's accuracy. The actual predictions are sent to the same file - I don't want to keep them.

# Test the model on given dataset, and parse output to get accuracy
def get_accuracy(cost, gamma, dataset)
  result = `svm-predict #{dataset} l-#{cost.to_f}-#{gamma.to_f}.model test.out`
  result.match(/\d+.\d+/)[0].to_f
end

Selecting a Model and Final Evaluation

Having trained models for every combination of cost and gamma, we need to find the one that does best on the cross-validation dataset, and then evaluate it on the test set. This is straightforward:

# Search for best cost/gamma pairing, based on result on cross-validation dataset
@@best_cost = Costs[0]
@@best_gamma = Gammas[0]
@@best_accuracy = 0.0
Costs.each do |cost|
  Gammas.each do |gamma|
    accuracy = get_accuracy(cost, gamma, "cross-data.dat")
    if accuracy > @@best_accuracy
      @@best_accuracy, @@best_cost, @@best_gamma = accuracy, cost, gamma
    end
  end
end

puts "Best cost #{@@best_cost}, Best gamma #{@@best_gamma}"
puts "Test score is: #{get_accuracy(@@best_cost, @@best_gamma, "test-data.dat")}"

Summary

Running the letter-recognition task with 2000 training examples using files, instead of in memory, took 11 minutes in total, instead of the 35 minutes my in-memory solution required. So the saving in time is considerable.

Accuracy with 2000 training examples was 82%.

I also ran the system using 72% of the data (14,400 instances) for training, 8% (1600 instances) as cross-validation, and the remaining 20% (4000 instances) as test data. I searched across 121 combinations of Cost/Gamma pairs using an RBF kernel. The best fit had a cost of 1/32, gamma of 32, and produced an accuracy of 97.5%. This took 6 hours to run.

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.

LibSVM and Ruby

LibSVM is the standard library for using Support Vector Machines, a powerful machine-learning tool. Installing LibSVM can be done through your usual package manager system, or through the LibSVM download page. There is Ruby-LibSVM library, available from http://rubysvm.cilibrar.com/download/. If you download the library, you will find the installation instructions do not work for Ruby 1.9. However, the fix is relatively simple. After downloading and unpacking Ruby-LibSVM, run ./configure. Before compiling, modify the main.cpp file to allow for the change between Ruby 1.8 and Ruby 1.9. I had to make three changes:

1. remove the line #include "node.h"
2. change RARRAY(xs)->len on line 50 to RARRAY_LEN(xs)
   
3. change RARRAY(xs)->len on line 579 to RARRAY_LEN(xs)

(Thanks to Lee Hinman for the clue as to what to do.) After those changes, I could finally run 'make' and then 'sudo make install' to install the LibSVM library for Ruby. Ilya Grigorik has a nice example of using Ruby-LibSVM, which I used to check everything was working.