Skip to content

Home

Jump to bottom
Yue Wu edited this page Jul 23, 2016 · 13 revisions

LIBSOL - A Library for Scalable Online Learning Algorithms

LIBSOL 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. LIBSOL is not only a machine learning toolbox, but also a comprehensive experimental platform for online learning research. Experiments demonstrate that LIBSOL is highly efficient and scalable for large-scale learning with high-dimensional data.

Features

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. LIBSOL 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 LIBSOL.

    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.

Algorithms

Specifically, LIBSOL 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
Clone this wiki locally