BioinformaticsOnline

Support Vector Machines (SVMs) are old, they have been around for some time but have only recently been adopted in Bioinformatics. They are linear machines that can be used for classification and regression problems. For a general overview of SVMs I suggest you take a trip to a relevant Wikipedia page.

In this howto I will tell you how you can use one implementation of an svm. In this case we will use svmLight by Thorsten Joachims. I only consider the use of svmLight on the Linux x86 and x86_64 architecture.

SvmLight can be obtained from here for the Linux distro, for other versions see here. If you want the source click here.

The first step is to download svmLight.

1. Make a directory where you want to install the programs. (i.e. /home/danny/svmlight)
2. Copy or move the downloaded package from your download point to your directory of choice or type commands along this line at the shell:
   cd /home/danny/svmlight/
   wget http://download.joachims.org/svm_light/current/svm_light.tar.gz
   tar zxvf svm_light.tar.gz
3. Finally, type "make" and you should get an output like this:
   make
   gcc     -c -O3     svm_learn_main.c -o svm_learn_main.o
   gcc     -c -O3     svm_learn.c -o svm_learn.o
   gcc     -c -O3     svm_common.c -o svm_common.o
   gcc     -c -O3     svm_hideo.c -o svm_hideo.o
   gcc     -O3        svm_learn_main.o svm_learn.o svm_common.o svm_hideo.o -o svm_learn -L. -lm
   gcc     -c -O3     svm_classify.c -o svm_classify.o
   gcc     -O3        svm_classify.o svm_common.o -o       svm_classify -L. -lm

Provided you have gcc or another C compiler installed all should go well. If not install gcc. Type "make clean" and try step 3 again.

There are two files you should be interested in:

1. svm_learn
2. svm_classify

svm_learn is used to build the model and svm_classify is used to test/use it... but lets not get ahead of ourselves there is lots to do yet.

The Dataset

Like all programs there is an input style that you have to use for svmLight. It is worth noting at this point that the input for one svm does not apply to others! For classification and regression, the only thing that changes is the label. What this means is that your vector will always have the following layout:

To make things clear I have made one part of the vector red. In this case our input vector is 5 elements long. Each element has a label, in this case the bold section. The label is separated from the value using a simple colon (:). Simple hey?

Now the label. Is your problem a regression problem or a classification?

If you imagine that I am a scientist and I want to predict height. I will take several features that are correlated with their height - say weight and hand span. Because I want to predict a value, the problem is a regression problem. So in this case I have something that looks like this:

The first element (180) is the label - it is the height of one person. The first feature (1:80) is the weight in Kg and the second (2:25) is the hand span. Now imagine I have this data for 1000 people…

Now imagine I work on fruit - more specifically I work with apples and bananas. I get a delivery and I don't want to sort the stuff as I am lazy. I want to get my robot to do it (because I am also rich!), this is a classification task. So the problem is 'simple' — Robby the robot has an item x. Item x can only be an apple (+1) or a banana (-1), all I have to do is teach Robby how the apple differs to the banana.

As mentioned above I have 2 classes (apple or banana). Lets say we encode the colour of the fruit by its RGB values and its length from pole to pole. +1 is an apple and -1 is a banana.

The first element in the list is the label. 1: is the Red 2: is Green and 3: is the Blue component of RGB. 4: is the pole-pole distance. Again assume we have a large sample of apples and bananas and that there is some variation in the samples.

Now for some terminology. Each apple, banana or person is called an instance. Each instance has a number of features (e.g. the R component of RGB). The collection of features and the label is called the feature vector.

I hope that you now understand the basics of a regression and a classification problem as well as how to create the feature vectors.

Training and Testing

When it comes to building an svm we need two things.

1. A training set
2. A test set

Take your data and split it along the lines of 60:40 or 70:30. The larger portion set will be your training set, the small your test set. Now before you get excited, we have not finished with the test set. When you use svms you have to optimise some variables (C, gamma and epsilon) - we will get to this later. To do this we need to do something called n-fold cross-validation.

n-Fold Cross-Validation (CV)

Typically five fold validation is used. This means that we take our test data and split it n(5) times into n(5) equal parts. We take four of those parts and combine them leaving one out. Now we train the svm on the combined four sections and test it on the fifth part we left out. We repeat this for all five parts of the training data. Naturally you can change n to any value you want but I would consider 4/5 a minimum.

Once we have optimal values for our variables we can test our models on unseen data… otherwise known as the test set. Because this data is held out from training it is often called the hold out test set or HOT for short.

Quick Note: SvmLight does not come with a facility to do CV. You should write your own, or hack someone else's code. If you want to do some hacking have a look at the libsvm code which is available here.

Kernels and Optimization of C, Gamma and Epsilon

The majority of SVM implementations come with a number of strandard kernels. This list often includes:

1. Linear
2. Polynomial - (s a*b+c) ^d
3. RBF - radial basis function (exp (-gamma || a-b|| ^2)
4. Sigmoid - (s a*b + c)

So I feel must be honest at this point. I have only used an RBF. The reason for this is that the RBF is happy to solve linear and non-linear problems, this means that you really don't have to consider using a linear kernel as a starting point.

I feel that I should also say at this point - I AM NOT GOING TO GO OVER THE MATH. SVMs are trivial to run with existing architectures but the math behind them is far from simple. If you wish to go over some of the details feel free to contact me or better yet post here - as I know some of the authors hang-out on the forum.

If you are dealing with either classification or regression you must optimise C and gamma. C controls the margin of the model - this can be considered as a margin of tolerance to error. In the case of svmLight, as C grows the margin becomes softer and softer. Gamma controls the width of the gaussian used to sample the data. As the gaussian decreases the search becomes more 'intense'. Think about going from a standard hair comb to a head louse comb!

When you attempt regression there is another value to consider - Epsilon! When the margin is defined, what we are essentially doing is defining how data contributes to the finished model. Each point is weighted according to the distance from the ideal solution - this is a penalty. When it comes to regression the epsilon tube basically says:

"Hey Mr Data Point, you are within Epsilon distance of the margins so you won't be penalised. In fact, you won't even contribute to the model!"

I have, on the whole, not made any attempt to change the value of Epsilon (0.001) because I have had no need. This is an exercise for the reader.

Summary:

1. Choose your problem
2. Set your dataset
3. Choose your kernel function (start with an RBF)
4. Split your data 60:40 || 70:30 => TRAIN & HOT.
5. Using your TRAIN data, optimise C & gamma (Epsilon)
6. Using your HOT data evaluate the model on something the machine has never seen before
7. Prepare scripts to calculate accuracy and RMSE (Root Mean Square Error) — if you are running a classification then the precision and accuracy are calculated for you

Other Features

When we said that the introductions to various topics were going to be basic - we meant exactly that. SVMs are not a toy, they are powerful and by nature very complex. Like genetic algorithms you have to put some sort of thought into how to encode your initial data. Should you scale things? - if so how? (standard logistic transform?). These are the kind of questions that I can't answer here in an introduction and overview.

I will also not show you how to run svmlight. To get all the options you need type "./svm_learn" at the command prompt and you will be greated with:

My typical training run is something like (yes, this is from a perl script):

A typical test run is:

To hack at the optimal C and G try this as a starting point:

I hope you find this a useful resource to get you started!