Liblinear is amazingly fast!

I decided to give up using LibSVM for the linear case because it was not optimized for that. Then, I had a look at liblinear, developed on the same team than LivSVM. Liblinear is recommended for document classification because it removes lots of unuseful operations for the linear case. It has also a (very recent) port to Java, which is located here.

Now, working with 50 categories and 0.5GB of data takes only less than 10 seconds on a Core 2 Duo 2GHz laptop. Those timings are impressive! The interface for this library is very similar to the LibSVM one, so it is very easy to migrate from one library to other. Of course, if you made a good design, all you have to do is to update/change your corresponding facade class.

BTW: Happy new year!

LibSVM integrated

I finally finished integration of LibSVM in my software. Trying to reproduce Joachims' results on reuters and ohsumed-23 I got the following on the micro-averaged breakeven point:

• On reuters: 84.2 (Joachims), 85.9 (me).
• On ohsumed: 60.7 (Joachims), 64.8 (me).

(the reference paper is this).

The differences can be due to the difference on the stopword list (I used the famous 571 words of the SMART system which is almost a standard) and my own processing procedure (I remove all punctuation marks). Indeed the results are really good, but the great difference in ohsumed is mysterious...

By the way, training time in my Core 2 Duo 2Ghz, for LibSVM is 4m28s, and classification 1m42s. It is the Java version, but it is still affordable. Who said SVMs were slow?

On the following days, I will try to improve my k-NN implementation (at this time, it has no inverted index, and so is terrifyingly slow), and to include another Bayesian network classifier (Sahami's "limited dependence bayesian classifier"), which I think could be improved in some way to make it competitive with SVMs.

Novice problems with LibSVM

If you are dealing with LibSVM, you mus remember the following:

• When building sparse vectors using datatype svm_node, be careful with allocating keys in ascending order. This is clearly specified in the documentation, but sometimes we are too lazy to read it before.
• By default, the outputs of LibSVM, when doing classification are one of {-1,1}. So, do not wait to get real outputs (for instance, distance to the hyperplane), unless you hack the code yourself. If you are doing text categorization, this is good to measure (macro/micro) F1, but not to get a good accuracy.
• You must first preprocess your feature vectors! Joachims proposes using a tf * idf, followed by a L2 normalization (classical Euclidean norm). This is valid for text classification, translating every coordinate value to the interval [0,1]. Other normalization schemes are valid for "classic" classification problems like iris and so (in those cases, the different atributes are scaled independently to [0,1]).
• There is a nasty bug (lack of feature?) in the Java version, at the method "svm_save_model", that makes very slow that procedure, because the output is not buffered. To solve it, find this line:
  DataOutputStream fp = new DataOutputStream(new FileOutputStream(model_file_name));
  And change it by the following:
  DataOutputStream fp = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(model_file_name)));

Using a SVM library for text categorization

In text categorization, one of my research fields, is impossible to ignore the great power of Support Vector Machines (SVM). Almost everyone agrees that, even in its more primitive form (Linear SVM), they are the killer algorithm to do this task (the one that gets more accuracy). And of course, that implies that any new presented approach to solve this problem should be tested against SVMs.

But, ¿what (open source/free) software packages are available for Support Vector Machines? In fact, the list is very reduced, being the two most popular ones the following:

• SVM^light, a C implementation written by Thorsten Joachims.
• LibSVM, a C (and Java) implementation written by Chih-Jen Lin.

Both of them are suitable for tasks of text categorization, as they are lightweight implementations, and relatively fasts. Besides, they both include Platt's SMO algorithm in order to make training procedure faster. So, ¿which one can be chosen?

I have tested both of them. In my most recent paper, we have used SVM^light to make a comparison against a Bayesian Network model to classify in a thesaurus environment (and of course, we beat linear SVMs!). That package is amazingly fast, not only due to the language it is written in (C), but due to the great job of Joachims in doing heuristics and other tricks.

In this moment, I am using LibSVM in my Java environment for text categorization (which I expect to release soon as free software), using directly the Java implementation. Althought it is written in a very "C-style" (arrays instead of containers, static methods, no exceptions,...), it is not so bad at speed (obviously it is several times slower than SVM^light, but it is Java, avoiding linking with a non portable library, and keeping the entire system in one language).

From the point of view of software licenses, LibSVM is released under the modified BSD license (a GPL compatible license). This is good, because it allows yo to use this package, even in a non free software environment (I must admit the last point is not really so good). SVM^light , on the other hand, is not free software. The license note claims that:

The program is free for scientific use. Please contact me, if you are planning to use the software for commercial purposes. The software must not be further distributed without prior permission of the author.

This is an important fact for me, and that is why I prefer LibSVM. I must admit that Joachims' work is impressive, and SVM^light is probably a faster and more complete environment, but I can cope with the lack of functionality and speed of LibSVM, because it is free software.

What do you think about this?