SOL is an open-source library for scalable online learning with high-dimensional data. The library provides a family of regular and sparse online learning algorithms for large-scale binary and multi-class classification tasks with high efficiency, scalability, portability, and extensibility. We provide easy-to-use command-line tools, python wrappers and library calls for users and developers, and comprehensive documents for both beginners and advanced users. SOL is not only a machine learning toolbox, but also a comprehensive experimental platform for online learning research. Experiments demonstrate that SOL is highly efficient and scalable for large-scale learning with high-dimensional data.

• Installation
• Command Line Tools
• Library Call
• Design & Extension
• Examples
• Extension Examples

The whole package is designed for high efficiency, scalability, portability, and extensibility.

• Efficiency: it is implemented in C++ and optimized to reduce time and memory cost.

• Scalability: Data samples are stored in a sparse structure. All operations are optimized around the sparse data structure.

• Portability: All the codes follow the C++11 standard, and there is no dependency on external libraries. We use cmake to organize the project so that users on different platforms can build the library easily. SOL thus can run on almost every platform.

• Extensibility:

  • The library is written in a modular way, including PARIO(for PARallel IO), Loss, and Model. User can extend it by inheriting the base classes of these modules and implementing the corresponding interfaces;

  • We try to relieve the pain of coding in C++ so that users can implement algorithms in a "Matlab" style. The following code snippet shows an example to implement the core function of the "ALMA" algorithm.

    Vector<float> w; //weight vector
    void Iterate(SVector<float> x, int y) {
    	float predict = dotmul(w, x);  //predict label with dot product
    	float loss = max(0, 1 - y * predict); //hinge loss
    	if (loss > 0) { //non-zero loss, update the model
    		w = w + eta * y * x; //eta is the learning rate
    		float w_norm = Norm2(w); //calculate the L2 norm of w
    		if (w_norm > 1) w /= w_norm;
    	}
    }

  Compact implementation of the core function of "ALMA" algorithm in SOL.

  Vector<float> w; //weight vector
  void Iterate(SVector<float> x, int y) {
      //predict label with dot product
      float predict = 0;
      for (int i = 0; i < x.size(); ++i){
    	  predict += w[x.index(i)] * x.value(i);
      }
      float loss = max(0, 1 - y * predict); //hinge loss
      if (loss > 0) { //non-zero loss, update the model
    	  //eta is the learning rate
    	  for (int i = 0; i < x.size(); ++i) {
    		  w[x.index(i)] += eta * y * x.value(i);
    	  }
    	  //calculate the L2 norm of w
    	  float w_norm = 0;
    	  for (int i = 0; i < x.size(); ++i) {
    		  w_norm += x.value(i) * x.value(i);
    	  }
    	  w_norm = sqrtf(w_norm);
    	  if (w_norm > 1) {
    		  for (int i = 0; i < w.dim(); ++i){
    			  w[i] /= w_norm;
    		  }
    	  }
      }
  }

  Traditional "C++" style counterpart implementation of the above algorithm

It's obvious that the traditional implementation is tedious. It's also much harder for readers to understand the code. What's more, users have to pay much more effort with much larger risk to make mistakes when coding in the traditional implementation.

Specifically, SOL consists of a family of:

• First Order Online feature selection algorithms:

  • Perceptron: The Perceptron Algorithm(Rosenblatt, 1958)
  • OGD: Online Gradient Descent(Zinkevich, 2003)
  • PA: Online Passive Aggressive Algorithms(Crammer et al., 2006)
  • ALMA: Approximate Large Margin Algorithm(Gentile, 2002)
  • RDA: Regularized Dual Averaging(Xiao, 2010)

• Second order online learning algorithms:

  • SOP: Second-Order Perceptron(Cesa-Bianchi et al., 2005)
  • CW: Confidence Weighted Learning(Dredze et al., 2008)
  • ECCW: Exactly Convex Confidence Weighted Learning(Crammer et al., 2008)
  • AROW: Adaptive Regularized Online Learning(Crammer et al., 2009)
  • Ada-FOBOS: Adaptive Regularized Online Learning(Crammer et al., 2009)
  • Ada-RDA: Adaptive Regularized Dual Averaging(Crammer et al., 2009)

• First order Sparse online learning algorithms:

  • STG: sparse online learning via truncated graidient (Langford et al., 2009);
  • FOBOS-L1: l1 Regularized Forward backward splitting (Duchi et al., 2009);
  • RDA-L1: Mixed l1/l2^2 Regularized Dual averaging(Xiao, 2010);
  • ERDA-L1: Enhanced l1/l2^2 Regularized Dual averaging(Xiao, 2010);

• Second order sparse online learning algorithms as follows

  • Ada-FOBOS-L1: Ada-FOBOS with l1 regularization
  • Ada-RDA-L1: Ada-RDA with l1 regularization

SOL is released under the Apache 2.0 open source license.

Please cite SOL in your publications if it helps your research:

@article{sol2016,
Author = {Yue Wu, Steven C.H. Hoi, Chenghao Liu, Jing Lu, Doyen Sahoo, Nenghai Yu},
Journal = {SMU Technical Report (SMU-TR-2016-10-27)},
Title = {SOL: A Library for Scalable Online Learning Algorithms},
Year = {2016},
url= {http://libsol.stevenhoi.org}
}

For any questions and comments, please send your email to chhoi@smu.edu.sg