opal - C++ header library of online learning with kernel slicing

What is this?

Opal is a C++ header library of online learning [1,2] with kernel slicing [3], which enables large-scale training with binary conjunctive features (polynomial kernel). The kernel slicing generalizes kernel splitting [4] in a feature-wise manner to combine the merits of linear and kernel-based training. To improve the scalability of the training with redundant data (in NLP), the kernel slicing reuses the partial margins computed in past rounds and truncates margin computations that do not contribute to parameter updates. The resulting learner is faster than a vanilla kernel-based online learner (w/ inverted indexing technique) by a factor of 30-250, while retaining its space-efficiency. Opal supports both linear and kernel-based training (polynomial kernel) with binary features; the models trained with the polynomial kernel are saved in the SVM^light-like format.

Main features of opal are summarized as follows:

• Include a fast kernel-based learner [-t 1] based on kernel slicing [-k]: currently, perceptron [P] [1] [-t 0], passive-aggressive algorithms [PA, PA-I, PA-II] [2] [-t 1,2,3] (opal), and their multi-class extensions [8,9] (opal-multi) are implemented. You can easily add your own additive online learning algorithms (need to modify 4 lines at the shortest).
• Include an adaptive classifier that becomes faster as testing continues ([-k]): in testing, opal builds fstrie online; it requires memory space (sub-)linear to the test data size, though ;-) If you want to have the memory footprint fixed, do not enable kenrel slicing ([-k]). Opal also avoids computation irrelevant to determine the label ([-p]). If you want to obtain an exact margin value, do not set [-p]. Generally, we recommend pecco [6] for testing; faster and more space-efficient than opal (in terms of testing) thanks to the static double array library.
• Include a fast linear learner/classifier [-t 0]: significantly faster than oll, LIBLINEAR, Vowpal Wabbit or other major open-source linear learners/classifiers.
• Support retraining [-m]: you can use the model that has been trained w/ opal as an initial model.
• Support instant training/testing [set model to '-']: training/testing w/o saving a model as libarow does.
• Support averaging [-a] and shuffling [-s]: both stabilize the model accuracy; averaged PA trains a stable model with a larger c value (aggressive update), which requires a smaller number of iterations than PA to obtain the same accuracy.
• Support various event buffering [-b]: buffer event on memory (time-efficient) [-b 0], buffer event on disk (space-efficient) [-b 1], or no buffering (slowest but no resource needed) [-b 2].
• Provide a C++ header library of an online double-array builder: implemented as a darts-compatible header library; optimized to minimize the construction time with random keys (dynamic insertion) [5]; insertion/retrieval is faster than std::tr1::unordered_map by a factor of 2-3, when the data access is skewed.

The following table summarizes the features of opal variants and pecco in training/testing.

The libraries are distributed under the GNU General Public License (Version 2) and the GNU Lesser General Public License (Version 2.1) (e-mail me when you prefer some license other than GNU GPL/LGPL). Note that this license doesn't apply to the training/dev/test data in test/ directory, which are generated from the annotated data by the way described in [3,6].

Please keep in mind that opal is not a versatile learner; the efficiency is based on the assumption of binary feature space with skewed (or sparse) and redundant examples (typically, NLP).

Download & Setup

> wget http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/opal/opal-latest.tar.bz2
> tar jxvf opal-latest.tar.bz2
> cd opal-YYYY-MM-DD
> configure
> make install

Alternatively, Mac OS X users can exploit macports to install opal (renamed as opal-ml to avoid package name confliction; again special thanks to @hjym_u); when you train a binary classifier, you may want to use opal instead of opal-multiclass (opal-multiclass is slow compared to opal).

See below for usage; In [3], PA-I SL, PA-I SL*, PA-I SP and PA-I KERNEL refer to opal [-k -p], opal [-p], opal, and opalk, respectively.

Requirements

• OS: 32/64-bit UNIX-compatible OS (tested on Linux / Mac OS X)
• Compiler: GNU make & gcc (tested with gcc 4.0 or higher)

ToDo

• Support parallel/distributed training [7].
• Support other additive-style online learning algorithms (e.g., averaged stochastic gradient descent).
• Support lossy counting [10] to select common features.
• Support reading/writing a compiled model to minimize start-up time in testing.

History

• May 15th, 2012 (development; minor bug/typo fixes and doc only):
  • Support GNU autoconf/automake.
  • Change License to GNU GPL to GNU GPL/LGPL.
  • Add option to enable kernel slicing [-k] and terminating marging computations [-]
  • Speed up the training/testing with multi-class classifier.
  • Resolve memory leak in cedar.h.
• December 21st, 2011:
  • Rewrite interface with GNU Getopt.
  • Speed up training by a factor of 2-3 using an array-based pseudo trie.
  • Support multi-class classification using multi-class perceptron [7] and support-class passive aggressive algorithms [8].
  • Support automatic shrinking of parameter N [# features expanded].
  • Support automatic model identification.
  • Suppress rounding errors by reducing the number of multiplications.
• August 29th, 2011:
  • Add SWIG-based Perl/Python/Ruby/Lua bindings (experimental).
  • Rename dda.h to cedar.h.
  • Remove intricacy in Makefile (you can make install).
  • Cache std::strtol () in a double array to speed up reading examples.
• March 27th, 2011:
  • Cache test examples as well to speed up per-iteration testing.
  • Support per-iteration testing w/ averaging (no side effect).
  • Add event=Null not to cache training examples (poor man's training).
  • Adopt double-precision floating point for conjunctive feature weight to suppress rounding errors (slightly more training time and memory footprint).
• January 21st, 2011:
  • Fix a (tiny) bug in PA-II and USE_HASH_TRIE.
  • Add USE_MAP_TRIE option.
• October 28th, 2010:
  • Fix a (tiny) bug in averaging (update on the last example at the last iteration had been wrongly ignored).
• September 16th, 2010:
  • Improve the performance with Disk mode; 1) caching examples into disk and 2) on-disk shuffling (≠ std::random_shuffle (), though).
  • Optimize the option order.
  • Resolve memory leak in dda.h.
  • Fix a bug in retraining with polynomial kernel.
• August 14th, 2010:
  • Fix a bug in linear retraining with averaging.
  • Revisit debug option (=1: output margins of examples in testing; =2: report model accuracy on test data at each iteration; debug=2 with development data will greatly help you to optimize # iterations (iter), but do not tune it on the test-set).
• August 12th, 2010:
  • Replace random () with XorShift RNG (also set as default RNG instead of TR1 mt19937) for shuffling examples (results updated).
  • Fix a bug in feature mapping.
• August 1st, 2010:
  • Make dda.h compatible to darts.
  • Improve the header portability by adding hash-based trie implementation to pa.h.
  • Clean up codes & bug fix in counting # features and retraining with kernel.
• July 27th, 2010:
  • Optimize the option order and support instant mode (w/o saving a model; like libarow).
• July 23rd, 2010:
  • Revisit debug option.
• July 21st, 2010:
  • initial release.

Usage

command-line options

Copyright (c) 2009-2012 Naoki Yoshinaga, All rights reserved.

Usage: src/opal-multi [options] train model test

train   training file       set '-' to skip training
model   model file          set '-' to training/test w/o saving a mode
test    test file           set '-' to skip testing

Optional parameters in training and testing:
  -t, --kernel=TYPE         select type of kernel function
                            * 0 - linear     (w^T * x)
                              1 - polynomial (s^T * x + 1)^d
  -d, --kernel-degree=INT   parameter d in polynomial kernel (0)
  -N, --kernel-splitN=INT   parameter N in kernel splitting (0)
                            (a learner [-N 0] will automatically calibrates N
                             to keep the weight trie within [-T] MiB bytes)
  -T, --max-trie-size=INT   max. RAM size (MiB) for feature weight trie (32)
                            (ignored if kernel-splitN [-N] is specified)

Optional parameters in training:
  -m, --model0=FILE         re-train a model trained w/ opal ('-')
  -l, --learner=TYPE        select learning algorithm
                              0 - Perceptron
                              1 - Passive Aggressive    (PA)
                            * 2 - Passive Aggressive I  (PA-I)
                              3 - Passive Aggressive II (PA-II)
  -c, --reg-cost=FLOAT      PA-I/-II aggressiveness parameter C (1.0)
  -i, --iteration=INT       # iterations (10)
  -a, --averaging           average parameters
  -s, --shuffling           shuffle training examples on RAM
  -b, --buffer=TYPE         select type of buffer to read examples
                            * 0 - Use RAM to load examples
                              1 - Use DISK to cache examples
                              2 - Do not cache examples
  -M, --max-examples=INT    max. # examples used in training (0: all)
  -k, --kernel-slicing      perform kernel slicing
  -p, --pruning-margin      terminate margin computation if unnecessarily
  -C, --max-classes=INT     max. # classes (needed for [-b 2])

Optional parameters in testing:
  -O, --output=TYPE        select output type of testing
                            * 0 - report accuracy
                              1 - report accuracy per iteration
                              2 - output margins

Misc.:
  -h, --help               show this help and exit

file format for train / test

(BNF-like notation)
<class>   := +1 | -1 (or any string in multi-class classification)
<feature> := integer // >=1
<value>   := 1       // value is ignored
<line>    := <class> <feature>:<value> <feature>:<value> ... <feature>:<value>

See opal/test/*.{train,dev,test}. As in SVM^light, feature/value pairs must be ordered by increasing feature number (values will be ignored and assumed to be 1, though).

example

# linear training w/ Averaged Perceptron [-l 0, -a] with shuffling examples
> opal -t 0 -l 0 -c 1.0 -i 5 -as train model -

# linear training and testing w/ Passive Aggressive-I w/o saving model
> opal -t 0 -c 0.005 -i 20 train - test

# kernel-based training and testing (polynomial kernel of d=2) with Passive Aggressive-I
#  (event on Disk; shuffling ignored)
> opal -t 1 -d 2 -i 20 -c 0.0005 -a -b 1 train model test

# kernel-based testing
#  (only combinations among 500 common features are explicitly considered)
> opal -N 500 - model test

NOTE:

• When you run opal as instant mode (model='-') with PA-I [-l 2] or PA-II [-l 3] and polynomial kernel [-t 1], the reported accuracy can be slightly different from the one obtained with non-instant mode; this is due to rounding errors.
• The retraining ([-m model0]) with averaging ignores #examples processed in a prior training (e.g., with [-a], a model trained with [-i 20] will be different from a model retrained with [-i 10] from a model trained with [-i 10]).

Performance comparison

The following tables show a comparison among linear learners (opal; ver. in 2011, oll 0.2, AROW++ 0.05, libarow 0.2.0, Vowpal Wabbit 4.1, SVMlin 1.0 and LIBLINEAR 1.7) and a comparison among kernel-based learners (opal, LIBLINEAR-POLY2 1.7 ([-d 2] only) and TinySVM 0.09), and LIBSVM 3.0: for LIBLINEAR, results with the fastest algorithm and the algorithm that obtained the most accurate model are shown. pecco (FST [-t 1]) is also used to test the models obtained with opal ([-d 2,3]; fstrie is build from the training data). The experiments were conducted on Mac OS X 10.5 over Intel Xeon E5462 3.2Ghz CPU with 32GB main memory. Only oll uses 4-byte float as floating-point numbers (others use 8-byte double). AROW++ and libarow cannot output margins of examples (others (can) do). opal, LIBLINEAR-POLY2 (modified to handle a large number of conjunctive features; int->int64_t) and TinySVM (modified for the experiments in [3]) and LIBSVM (add -m64, to make speed and memory comparable to 64-bit TinySVM) adopt 64-bit addressing, while others adopt 32bit addressing. These differences may cause 10-20% difference in time, and at most 100% difference in space (32bit v.s. 64bit). opal with [-b 1] and Vowpal Wabbit do not load events on memory; this leads to slower but memory-efficient training (demand additional Disk space for caching data, though); in the experiments, examples for these learners were offline shuffled to make the accuracy of the obtained models comparable to the others.

We have tried parameters # iters = 1, 5, 10, 20 (online learners only), and c/r = 100.0, 50.0, ..., 0.000005, 0.000001; the table lists the model that achieved the best accuracy on the development set. Due to intricate parameters related to learning rate in SGD, we have only tried l= 1.0, 0.5, 0.2, .., 0.02, 0.01 for Vowpal Wabbit. The gettimeofday command is used to measure the run-time (namely, the whole training or testing time).

Dependency Parsing (DEP in [3], opal/test/tl.*, # training / test examples = 296,776 / 113,716)

NOTE: the above accuracy is computed against the test examples, and is not directly comparable to those in [3], which shows dependency accuracy.

Hyponymy Relation Identification (REL in [3], opal/test/wiki.*, # training / test examples = 201,664 / 10,000)

NOTE: LIBLINEAR-POLY2 did not work in this dataset (it should require ~400G memory space).

Disclaimer

We do not guarantee that the implemented algorithms other than those proposed by us are patent-free; we regarded them to be patent-free simply because their implementations are available as (existing) open-source softwares (otherwise a simple patent look-up). Please be careful when you use this software for commercial use.

How to pronounce `opal'?

Opal was originally meant for online passive-agressive algorithms; the efficiency attributes to obsolete partial-margins in the active lifespan.

References

1. Y. Freund and R. E. Schapire. Large Margin Classification using the Perceptron Algorithm. Machine Learning 37(3):277--296, 1999.
2. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online Passive-Aggressive Algorithms. JMLR 7(Mar):551--585. 2006.
3. N. Yoshinaga and M. Kitsuregawa. Kernel Slicing: Scalable Online Training with Conjunctive Features. Proc. COLING (oral), pp. 1245--1253. 2010.
4. Y. Goldberg and M. Elhadad. splitSVM: Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications. Proc. ACL, short papers, pp. 237--240. 2008.
5. S. Yata and M. Tamura and K. Morita and M. Fuketa and J. Aoe. Sequential Insertions and Performance Evaluations for Double-arrays. Proc. the 71st National Convention of IPSJ, pp. 1263--1264. 2009.
6. N. Yoshinaga and M. Kitsuregawa. Polynomial to Linear: Efficient Classification with Conjunctive Features. Proc. EMNLP, pp. 1542--1551. 2009.
7. R. McDonald, K. Hall, and G. Mann. Distributed Training Strategies for the Structured Perceptron. Proc. NAACL, pp. 456--464. 2010.
8. K. Crammer and Y. Singer. Ultraconservative Online Algorithms for Multiclass Problems. JMLR 3(Jan):951--991, 2003.
9. S. Matsushima, N. Shimizu, K. Yoshida, T. Ninomiya, H. Nakagawa. Exact Passive-Aggressive Algorithm for Multiclass Classification using Support Class. Proc. SDM, pp. 301--314. 2010.
10. G. S. Manku and R. Motwani, Approximate Frequency Counts over Data Streams, Proc. VLDB, pp. 346--357. 2002.