Structured Bundle Method for Risk Minimization
==============================================

Overview
--------

  sbmrm determines the optimal weights that minimize a structured loss for the
  following class of models:

    E(x,y) = <w,φ(x)y>

    x         observations
    y         binary labels
    φ(x)      features, one column per component of y
    w         feature weights

  Given a set of weights w, the best solution is:

    y* = argmin_y E(x,y)

  The learning consists of finding:

    w* = argmin_w λ½|w|² + L(w)

  where L(w) is the soft margin loss with a cost function Δ(y',y)

    L(w) = max_{y:Ay≤b} <w,φ(x')y' - φ(x')y> + Δ(y',y)

    y'        ground truth
    Δ(y',y)   cost function for mislabeling
    λ         regularizer weight
    A,b Ay≤b  linear constraints on y

  Currently, only the Hamming cost function is implemented for Δ(y',y).

Dependencies
------------

  * Gurobi

    Get the gurobi solver from http://www.gurobi.com. Academic licenses are free.

  * CMake, Git, GCC, boost

    On Ubuntu 14.04, get the build tools via:

      sudo apt-get install cmake git build-essential libboost-dev

Get Source:
-----------

  $ git clone https://github.com/funkey/sbmrm
  $ cd sbmrm
  $ git submodule update --init

Compile
-------

  Configure:

    $ mkdir build
    $ cd build
    $ cmake ..

    Set Gurobi_ROOT_DIR to the Gurobi subdirectory containing the /lib and
    /bin directories.

  Compile:

    $ make


  MacOS
  -----

  Use MacPorts to install cmake and gcc-4.9 (other versions might work as well):

  $ sudo port install cmake gcc49

  The current versions of Gurobi are compiled with GCC using libstdc++, which
  is not compatible with the default boost libraries obtained via MacPorst.
  Therefore, you have to compile boost youself, which can be done with the
  following command:

  $ sudo port -ns upgrade --force boost configure.compiler=macports-gcc-4.9

  Using CMake, you also have to change the default compiler for sbmrm by setting

    CMAKE_CXX_COMPILER=/opt/local/bin/g++-mp-4.9

  The default gurobi root dir is
  Gurobi_ROOT_DIR=/Library/gurobi<version>/mac64/. In some versions of Gurobi for
  MacOS, the lib directory only contains a libgurobi<version>.so. Move it to
  libgurobi<version>.dylib (or create a symlink) before you run cmake, such that
  it finds the library.

Usage
-----

  By default, sbmrm expects three files:

    labels.txt        the ground truth labeling y'
    features.txt      φ(x)', one column per line
    constraints.txt   linear constraints on y

  Example:

    labels.txt:

      0 # one digit per component of y'
      1 # comments are allowed
      0
      1

    features.txt:

      # one feature vectors per line

      0.2 1 # for y_0
      0.1 2 # for y_1
      0.3 0 # ...
      0.1 2

    constraints.txt:

      # format: [ceofficient*component]* [rel] [value]
      # components of y starting counting at 0
      # [rel] = <= | == | >=

      1*0 1*1 1*2 1*3 >= 1 # at least one compnent of y has to be 1

  Running ./sbmrm will find w*. See ./sbmrm --help for options like setting
  the regularizer weight.