FastML

Machine learning made easy

Vowpal Wabbit, Liblinear/SBM and StreamSVM compared

Our Indiegogo campaign turned out to be a (partial) success, so we deliver as promised: a comparison of Vowpal Wabbit, Liblinear/SBM and StreamSVM on the webspam dataset. Refer to the Comparing large-scale linear learners for motivation and references.

Just to recap: the Liblinear/SBM and StreamSVM papers deal with linear learners able to handle data which doesn’t fit into memory. Among other things, the authors experiment with various tools and find VW not quite competitive. We set out to clarify the situation using current versions of the software involved.

Data

The authors of the Liblinear/SBM paper run Vowpal Wabbit on two datasets, so it narrows down the selection as far as reproducing the results goes. These two sets are webspam and kdd10. We have chosen the first because it’s bigger: 24GB vs 5GB. The downside of webspam is that it’s easy to get 99% accuracy, while kdd10 is more demanding, with accuracy in 85-90% range.

Webspam has 350k rows and 16.6M features. It is available from the LibSVM dataset repository and was originally used in Pascal Large Scale Learning Challenge. The underlying data consists of web pages HTML source, classified as spam or not. We’re dealing with the trigram version, there’s also a unigram version with much smaller number of features. We split the data randomly into training and test: 270k / 80k examples, as was done in the papers.

python split.py train.txt train_v.txt test_v.txt 0.8 dat_seed

split.py is a phraug script, it will randomly split the given file into two, 80% of lines will go to the first, the rest to the second. We use a random seed so that you can get exactly the same files.

Vowpal Wabbit

Since data is in libsvm format, we need to convert it for VW. The format in this case would differ from libsvm only by something like “|x” between the label and the rest of the line. To speed things up, let’s skip the text file and save data as VW’s binary/cache file. Instead of saving the output to a file, we send it to standard output (Unix territory) and pipe it directly to VW, which will train and create a cache file as a side effect we seek.

python libsvm2vw.py train_v.txt /dev/stdout | vw --cache_file train_v.cache python libsvm2vw.py test_v.txt /dev/stdout | vw --cache_file test_v.cache

UPDATE: contents of the cache depend on the number of bits used for hash table (-b). One can use existing cache for training with fewer bits, but not vice-versa. Therefore it makes sense to create the cache with higher bits:

python libsvm2vw.py train_v.txt /dev/stdout | vw -b 29 --cache_file train_v.cache python libsvm2vw.py test_v.txt /dev/stdout | vw -b 29 --cache_file test_v.cache

And now we find the optimal number of passes using VW’s built-in validation/early-stopping mode:

vw --cache_file train_v.cache --loss_function logistic -b 29 -P 10000 --passes 10 

(...)
finished run
number of examples per pass = 252163
passes used = 5
weighted example sum = 1.26082e+06
weighted label sum = 267743
average loss = 0.0341765 h
best constant = 0.212357
total feature number = 4703937821

Then disable it (--holdout_off) to train on the full file:

$ time vw --cache_file train_v.cache --loss_function logistic -b 29 -P 10000 --passes 5 --holdout_off -f model_v_logistic

(...)   
finished run
number of examples per pass = 280130
passes used = 5
weighted example sum = 1.40065e+06
weighted label sum = 298340
average loss = 0.0178536
best constant = 0.213001
total feature number = 5225004535

real    4m10.574s
user    2m55.532s
sys 0m14.009s   

See Holdout test for validation and early stopping for explanation of this procedure.

Once we have predictions, we can score them using the code available at GitHub:

accuracy: 0.994675826535
AUC: 0.998418419401

We’ll be comparing classifiers’ accuracy, so another option is to use hinge loss instead of logistic. The procedure is the same, scores are slightly worse.

accuracy: 0.993502218406
AUC: 0.99632599445

Regular Liblinear

For starters let’s just try a tool that’s not designed to handle data bigger than memory. When you run regular Liblinear’s train on webspam, nothing happens for a long time. If you look at system monitoring tools, iotop shows intensive disk read (60-90 M/s, probably max for this system), while CPU is at 20-40% of one core. Then after a while CPU goes to roughly full utilization for one core, while memory usage starts to climb. That’s probably a second pass over data and loading it. Then CPU utilization starts to show a lot of irregularity, and swap usage starts to climb and the system becomes intermittently unresponsive. All this time train didn’t output a word. It’s time to kill the process and try Liblinear/SBM.

Liblinear/SBM

We downloaded and built the software according to the instructions in the README, no rocket science here. The software is called liblinear-cdblock and is a fork of Liblinear, so if you need other non-standard extensions you’re out of luck. Instead of the train program in the original you get blocktrain, and additionally blocksplit.

First thing to do is to blocksplit a training file into a number of blocks. Each block should fit into memory. The default number of blocks is eight. With 12GB memory and webspam you can get away with just two blocks.

The process takes one core to roughly 100%, utilizes practically no memory and creates a folder with blocks in the current directory. The folder is named after the input file with a dot and a number of blocks at the end, for example train_v.txt.2.

$ time ./blocksplit -m 2 data/train_v.txt
............................
time : 822

real    13m42.357s
user    12m8.597s
sys 0m10.435s

The software outputs a series of dots so at least you know something is going on.

Now it’s time to run blocktrain. We use the default settings. CPU gets maxed out, memory usage grows. After a while the software spits out a line, the first iteration stats, including cumulative run time, value of the objective function and of the gap (whatever it is). The default setting for max iterations is five, and the first takes roughly two minuts on our hardware. The next iterations are progressively quicker. The objective stays the same after the second iteration, only the gap gets smaller.

In the middle of each iteration CPU util falls to 0 for a couple of seconds. This is synchronized with memory usage pattern.

$ time ./blocktrain data/train_v.txt.2/ data/cdblock_model
iter 1 time 118 runtime 118 loadtime 0 obj -9213.28 PGmax 0.015024 PGmin -0.01629 gap 0.031314
iter 2 time 228 runtime 228 loadtime 0 obj -9234.21 PGmax 0.013591 PGmin -0.011198 gap 0.02479
iter 3 time 315 runtime 315 loadtime 0 obj -9234.22 PGmax 0.009242 PGmin -0.027316 gap 0.036558
iter 4 time 402 runtime 402 loadtime 0 obj -9234.22 PGmax 0.0038895 PGmin -0.010379 gap 0.014268
iter 5 time 488 runtime 488 loadtime 0 obj -9234.23 PGmax 0.0017845 PGmin -0.0024688 gap 0.0042533

real    8m14.249s
user    5m17.476s
sys 0m18.643s

Predict seems to support probability estimates, but only with logistic regression. Otherwise you get a bunch of ones and negative ones.

$ time ./predict data/test_v.txt data/cdblock_model data/cdblock_p.txt
Accuracy = 99.3245% (69398/69870)

real    1m5.930s
user    1m1.962s
sys 0m1.584s

Generally everything works as advertised in regard to handling large files. Metrics are slightly, but strictly worse than VW (either logistic or hinge). We fall just a bit short of the accuracy reported in the paper, 0.995, probably because of using default hyperparams.

accuracy: 0.993244597109
AUC: 0.993511427279

Probability estimates?

Now let’s try logistic regression solver so that we can get probability estimates. It shows less stats and iterations take longer - the first 140 seconds, the last about 110 seconds.

$ time ./blocktrain -s 7 data/train_v.txt.2/ /path/to/model/file
iter 1 time 141 runtime 141 loadtime 0 obj -19147.418065
iter 2 time 282 runtime 282 loadtime 0 obj -19588.075924
iter 3 time 393 runtime 393 loadtime 0 obj -19605.536968
iter 4 time 507 runtime 507 loadtime 0 obj -19612.382242
iter 5 time 621 runtime 621 loadtime 0 obj -19613.193329

real    10m22.001s
user    7m11.244s
sys 0m18.864s

Be careful to specify a valid path for a model file. Otherwise the program will run and won’t complain, but there will be no model.

$ time ./blocktrain -s 7 data/train_v.txt.2/ data/cdblock_model_s7
iter 1 time 140 runtime 140 loadtime 0 obj -19147.418065
iter 2 time 275 runtime 275 loadtime 0 obj -19588.075924
iter 3 time 383 runtime 383 loadtime 0 obj -19605.536968
iter 4 time 495 runtime 495 loadtime 0 obj -19612.382242
iter 5 time 609 runtime 609 loadtime 0 obj -19613.193329

real    10m15.373s
user    7m14.188s
sys 0m21.043s

Time to predict.

$ time ./predict data/test_v.txt data/cdblock_model_s7 data/cdblock_p_s7.txt
Accuracy = 98.5201% (68836/69870)

real    1m7.231s
user    1m2.190s
sys 0m1.569s

The results are significantly worse:

accuracy: 0.985201087734
AUC: 0.985763288671

Let’s tell Liblinear we want probabilities, using -b 1:

$ time ./predict -b 1 data/test_v.txt data/cdblock_model_s7 data/cdblock_p_s7_probs.txt
probability output is only supported for logistic regression

Apparently no probability estimates from Liblinear today.

Generally for us Liblinear is no match for Vowpal Wabbit, at least with this dataset. It runs longer, offers worse feedback and slightly worse scores. Maybe by tuning the hyperparams one could improve the results: the authors report setting the most important parameter, C, to 64, while the default is 1. However, they also report 99.5% accuracy while we get 99.3%, so it seems there’s not that much to be gained here.

StreamSVM

Building StreamSVM is a bit more involved than building Liblinear: one needs a few dependencies. Luckily, apt-get install ... does the trick.

With this tool, you don’t need to convert data, which is a plus. However, it seems to have a price - it takes much longer to train than either VW or Liblinear.

When calling the program, a small inconvenience greets us; you need to specify the number of training examples and data dimensionality at the outset. Let’s count those lines then.

wc -l train_v.txt

When you run StreamSVM, there’s some info at the start and then it goes silent. Then comes iteration info. The first iteration took 270 seconds, that is more than twice as long as with Liblinear. The value of objective function stays the same after the third iteration.

$ time ./StreamSVM -d 280130 -f 16609143 data/train_v.txt data/streamsvm_model
Warning! Setting max_nnz to 16609143
model parameter C is not specified. C=1 would be applied this time.
model_name is specified but the way to save is not specified.
the model will be saved at the end
model_name is data/streamsvm_model
Trainer id 0 Iteration 1 time 279.346566 obj 9848.694509 gap 6.150838
Cache access 13237417 epsilon 1.274152 active size 9675 access ratio 47.254550 access speed(M/sec) 0.047387
Trainer id 0 Iteration 2 time 297.081339 obj 10376.918432 gap 4.585239
Cache access 13909444 epsilon 0.100929 active size 8720 access ratio 49.653532 access speed(M/sec) 0.046820
Trainer id 0 Iteration 3 time 318.703953 obj 10380.234806 gap 0.400062
Cache access 13655784 epsilon 0.000269 active size 1606 access ratio 48.748024 access speed(M/sec) 0.042848
Trainer id 0 Iteration 4 time 302.305856 obj 10380.244612 gap 0.095953
Cache access 12151680 epsilon 0.000071 active size 1560 access ratio 43.378717 access speed(M/sec) 0.040197
Trainer id 0 Iteration 5 time 272.086716 obj 10380.244735 gap 0.000240
Cache access 11496425 epsilon 0.000064 active size 1553 access ratio 41.039607 access speed(M/sec) 0.042253
 Total cache access 64450750
 obj 10380.244735 Total time 1469.524430

real    25m9.155s
user    46m34.383s
sys 1m27.857s

One interesting thing about StreamSVM is that it uses two cores. It has the --num_learners command line parameter, but according to the author it doesn’t work at the moment. As far as hyperparams go, in the paper the best value for C for this dataset is 1, which is also the default.

$ time ./StreamSVMPredict -f 16609143 --output_file data/streamsvm_p.txt --model_file data/streamsvm_model --train_file data/test_v.txt 
Warning! Setting max_nnz to 16609143
Accuracy = 99.0597% (69213/69870)
Fscore = 99.2199%
Precision = 99.6447% (41782/41931)
Recall = 98.7988% (41782/42290)

real    1m0.091s
user    0m57.772s
sys 0m0.947s

The scores didn’t impress us:

accuracy: 0.990596822671
AUC: 0.991292619197

StreamSVM outputs both binary predictions and probabilities, like this:

-1  0.810701
-1  0.920251
-1  0.89225

Note that these are probabilities for negative class, which may be misleading. It can be corrected in classifier.hpp, we sent the author a bug report. When you take these estimates into account, AUC matches VW!

AUC: 0.998972438313

Conclusion

Current version of Vowpal Wabbit outperforms both Liblinear and StreamSVM on webspam. That’s just one dataset, so it would be good to compare using a broader selection. On the other hand, the results show that one better take claims made in papers with a grain of salt, but you already knew that.

VW is also faster and allows using non-linear features like n-grams, which should score even better without any additional hassle. Its advantage is no surprise if you take into consideration that VW comes from a strong industrial lab, while the two other projects are of more academic quality.


We would like to thank Rajarshi Das and Peter Ritz, the main supporters of the Indiegogo campaign, and Gurjeet Singh, who was the first to contribute. You made this article possible.

Comments