Giraph Machine Learning Project

I heard from Joey Gonzalez, about this project: http://incubator.apache.org/giraph/project-info.html :


"It is an open-source framework for large-scale graph computation that is community maintained (Apache incubator status), with contributors from LinkedIn and Yahoo!.
It runs on very large (4000 node) cloud systems, and does so efficiently (in memory using low-latency communication and fault-tolerant snapshots)."


"Giraph was recently featured at the HotCloud conference and has been going on a lecture circuit around the valley (...).  Unlike Pegasus Giraph is relatively well designed with in memory storage, HadoopRPC messaging, infrequent snapshots, and map-only execution.   Basically with the exception of startup and occasional snapshots, Giraph runs entirely in memory and communicates
over sockets."

It definitely sounds like an interesting project. Although no Giraph will beat our labardor! (GraphLab.. :-)

Big learning NIPS workshop

My friends Joey Gonzalez and Yucheng Low, are among the organizers of this year
NIPS workshop on big learning. Mark down your calendars for December 16-17 in Sierra Nevada, Spain.

Some of the interesting topics of this workshop:
Hardware Accelerated Learning: Practicality and performance of specialized high-performance hardware (e.g. GPUs, FPGAs, ASIC) for machine learning applications.

Applications of Big Learning: Practical application case studies; insights on end-users, typical data workflow patterns, common data characteristics (stream or batch); trade-offs between labeling strategies (e.g., curated or crowd-sourced); challenges of real-world system building.

Tools, Software, & Systems: Languages and libraries for large-scale parallel or distributed learning. Preference will be given to approaches and systems that leverage cloud computing (e.g. Hadoop, DryadLINQ, EC2, Azure), scalable storage (e.g. RDBMs, NoSQL, graph databases), and/or specialized hardware (e.g. GPU, Multicore, FPGA, ASIC).

Hopefully, if I manage to scrap enough travel money, I may even attend!

Installing GNU Octave

GNU Octave is a Matlab like open source math environment. Recently, while talking to many companies, many of them have expressed their dissatisfaction with Maltlab license. In this post I will explain how to install Octave instead, for all the open source lovers.

After breaking my head most of today, I found out that the easiest way
to install Octave on Linux is found here.

Specifically for Fedora, you just need to do

sudo yum install octave-forge

On Ubuntu, you need to

sudo apt-get install octave3.2

For MAC OS it is also easy: you can download dmg file here

If you want to work really hard, you can try to compile the
sourcess.
However, this is really not recommended!!!

After you download the tgz file, you need to run ./configure
you may get this error:

configure: error: You are required to have BLAS and LAPACK libraries

point to the right blas/lapack libs:

./configure --with-lapack="-llapack -L/usr/lib64/atlas/" --with-blas="-lblas -L/usr/lib64/atlas/" --prefix=/mnt/bigbrofs/usr6/bickson/octave/ --without-qhull

when compiling I got this error:

Range.cc:440: error: 'floor' is not a member of 'gnulib'

by reading on the web, it seems it is some gcc bug:
http://lists.gnu.org/archive/html/octave-bug-tracker/2011-02/msg00262.html

The way to resolve it, is either update gnulib version, or add
the appropriate header file
#include
and change gnulib::floor to floor

Next you will get about 20 such erros in different files that needs to be
setup manually.
dir-ops.cc: In member function 'bool dir_entry::open(const std::string&)':
dir-ops.cc:61: error: 'strerror' is not a member of 'gnulib'
make[3]: *** [liboctave_la-dir-ops.lo] Error 1

#include<stdlib.h>

file-ops.cc: In function 'int octave_mkdir(const std::string&, mode_t, std::string&)':
file-ops.cc:378: error: 'strerror' is not a member of 'gnulib'

file-ops.cc: In function 'int octave_rename(const std::string&, const std::string&, std::string&)':
file-ops.cc:502: error: 'rename' is not a member of 'gnulib'
make[3]: *** [liboctave_la-file-ops.lo] Error 1

lo-mappers.cc: In function 'double xtrunc(double)':
lo-mappers.cc:48: error: 'trunc' is not a member of 'gnulib'
lo-mappers.cc: In function 'double xfloor(double)':
lo-mappers.cc:53: error: 'floor' is not a member of 'gnulib'
lo-mappers.cc: In function 'double xround(double)':
lo-mappers.cc:59: error: 'round' is not a member of 'gnulib'
lo-mappers.cc: In function 'float xtrunc(float)':
lo-mappers.cc:267: error: 'truncf' is not a member of 'gnulib'
lo-mappers.cc: In function 'float xround(float)':
lo-mappers.cc:273: error: 'round' is not a member of 'gnulib'
make[3]: *** [liboctave_la-lo-mappers.lo] Error 1

lo-utils.cc: In function 'void octave_putenv(const std::string&, const std::string&)':
lo-utils.cc:93: error: 'malloc' is not a member of 'gnulib'
lo-utils.cc: In function 'std::string octave_fgets(FILE*, bool&)':
lo-utils.cc:121: error: 'malloc' is not a member of 'gnulib'
lo-utils.cc:136: error: 'realloc' is not a member of 'gnulib'

oct-env.cc: In member function 'void octave_env::error(int) const':
oct-env.cc:534: error: 'strerror' is not a member of 'gnulib'
make[3]: *** [liboctave_la-oct-env.lo] Error 1
make[3]: Leaving directory `/mnt/bigbrofs/usr7/bickson/octave-3.4.2/liboctave'
make[2]: *** [all] Error 2
make[2]: Leaving directory `/mnt/bigbrofs/usr7/bickson/octave-3.4.2/liboctave'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/mnt/bigbrofs/usr7/bickson/octave-3.4.2'

ct-md5.cc: In function 'std::string oct_md5_file(std::string)':
oct-md5.cc:73: error: 'fclose' is not a member of 'gnulib'
make[3]: *** [liboctave_la-oct-md5.lo] Error 1

oct-time.cc: In constructor 'octave_time::octave_time(const octave_base_tm&)':
oct-time.cc:62: error: 'mktime' is not a member of 'gnulib'
oct-time.cc: In member function 'void octave_strptime::init(const std::string&, const std::string&)':
oct-time.cc:269: error: 'strptime' is not a member of 'gnulib'
oct-time.cc:276: error: 'mktime' is not a member of 'gnulib'

ANOTHER ERROR I GOT:
build-aux/bootstrap: libtoolize -c -f ...
libtoolize: $pkgltdldir not a directory: `/usr0/software/libtool/share/libtool'
SOLUTION: make clean, and this error disappeared

ANOTHER ERROR:
./liboctave/.libs/liboctave.so: undefined reference to `METIS_NodeComputeSeparator'
SOLUTION:
setenv LIBS "-lmetis -L/usr/cs/lib/"
and then ./configure again and compile again

GraphLab and Mahout Compatability - Mahout SVD input format

In the last couple of months, we are working on increasing compatibility of GraphLab large scale machine learning project, with Apache Mahout large scale machine learning project. About 3 months ago, as a first step, we decided to change GraphLab license to Apache license to allow for better interaction between the projects.

This week I wrote some Java code, to allow translation of Mahout Hadoop sequence files using in Mahout's SVD solver into GraphLab's format and back. This will allow users of Mahout that rely on Hadoop infrastructure, to pre-process the matrix factorization problem as before, but change the actual solver used from Mahout SVD to GraphLab. The advantage, is that for problems which fit into memory, GraphLab run about x50 faster.

Here is the Java code:

import java.io.*;
import java.util.Iterator;

import org.apache.mahout.math.SequentialAccessSparseVector;
import org.apache.mahout.math.Vector;
import org.apache.mahout.math.VectorWritable;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.SequenceFile;

/**
 * Code for converting Mahout SequenceFile containing SequentialAccessSparseVector to GraphLab format
 * @author bickson
 *
 */

public class SeqFile2GraphLab {


   public static int Cardinality;

        /**
         * 
         * @param args[0] - input svd file
         * @param args[2] - output csv file
         */

  static void writeFloat(DataOutputStream dos, float a) throws java.io.IOException{
    int floatBits = Float.floatToIntBits(a);
    byte floatBytes[] = new byte[4];
    floatBytes[3] = (byte)(floatBits >> 24);
    floatBytes[2] = (byte)(floatBits >> 16);
    floatBytes[1] = (byte)(floatBits >> 8);
    floatBytes[0] = (byte)(floatBits);
    dos.write(floatBytes);
  }
  static void writeInt(DataOutputStream dos, int a) throws java.io.IOException{
    byte floatBytes[] = new byte[4];
    floatBytes[3] = (byte)(a >> 24);
    floatBytes[2] = (byte)(a >> 16);
    floatBytes[1] = (byte)(a >> 8);
    floatBytes[0] = (byte)(a);
    dos.write(floatBytes);
  }



  public static void main(String[] args){

    if (args.length < 6){
      System.err.println("Usage: java SeqFile2GraphLab [input seq file name] [output graphlab file name] [M - number of users] [N - number of movies] [K - number of time bins ] [ e - number of edges] [ OPTIONAL: transpose = false]");
      System.exit(1);
    }

    String inputfile = args[0];
    String outputfile = args[1];
   int M = Integer.parseInt(args[2]);
    int N = Integer.parseInt(args[3]);
    int K = Integer.parseInt(args[4]);
    int e = Integer.parseInt(args[5]);
    if (M < 1 || N < 1 || K< 1 || e<1){
       System.err.println("wrong input. M,N,K,e should be >=1");
       System.exit(1);
    }
    boolean transpose = false;
    if (args.length >= 7)
       transpose = new Boolean(args[6]).booleanValue();

    try {
        final Configuration conf = new Configuration();
        final FileSystem fs = FileSystem.get(conf);
        final SequenceFile.Reader reader = new SequenceFile.Reader(fs, new Path(inputfile), conf);
        DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outputfile)));
        writeInt(dos,M);
        writeInt(dos,N);
        writeInt(dos,K);
        writeInt(dos,e);
        System.out.println("Writing a matrix of size: " + M + " users, " + N + " movies, " + K + " time bins " + e + " edges.");
        IntWritable key = new IntWritable();
        VectorWritable vec = new VectorWritable();
        int edges = 0;

        while (reader.next(key, vec)) {
           SequentialAccessSparseVector vect = (SequentialAccessSparseVector)vec.get();
           //System.out.println("key " + key + " value: " + vect);
           Iterator<Vector.Element> iter = vect.iterateNonZero();

           while(iter.hasNext()){

              Vector.Element element = iter.next();
              if (!transpose){
                assert(element.index() < M);
                assert(key.get() < N);
                writeFloat(dos,element.index()+1);
                writeFloat(dos,key.get()+1+M);
              }
              else {
                assert(element.index() < N);
                assert(key.get() < M);
                writeFloat(dos,key.get()+1);
                writeFloat(dos,element.index()+1+M);
              }
              writeFloat(dos,1);
              writeFloat(dos,(float)vect.getQuick(element.index()));
              //System.out.println("col: " + key.get() + " row: " + element.index() + " val: " + vect.getQuick(element.index()));
              edges++;

              if (edges % 1000000 == 0)
                 System.out.println("edges: " + edges);
           }
        }
        if (edges != e){
           System.err.println("Wrong number of edges in file. Should be " + e + " in practice we have : " + edges);
        }
        reader.close();
        dos.close();
        System.out.println("Done writing !" + e + " edges");
    } catch(Exception ex){
       ex.printStackTrace();
    }

  }
}

Compilation:

javac -cp /mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/core-3.1.1.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/mahout-core-0.5-SNAPSHOT.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/mahout-math-0.5-SNAPSHOT.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/commons-cli-1.2.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/hadoop-0.20.2-core.jar *.java

Example run, for converting netflix data, from Mahout's format into GraphLab's:

run2:
        java -cp .:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/core-3.1.1.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/mahout-core-0.5-SNAPSHOT.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/mahout-math-0.5-SNAPSHOT.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/commons-cli-1.2.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/hadoop-0.20.2-core.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/commons-logging-1.0.4.jar:/mnt/bigbrofs/usr7/bickson/hadoop-0.20.2/lib/commons-logging-api-1.0.4.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/commons-collections-3.2.1.jar:/mnt/bigbrofs/usr7/bickson/mahout-0.4/taste-web/target/mahout-taste-webapp-0.5-SNAPSHOT/WEB-INF/lib/google-collections-1.0-rc2.jar  SeqFile2GraphLab netflix.seq netflix 480189 17770 27 1408395
        

More on shutgun

I got inquiries from several companies who wanted to use shotgun, our large scale sparse logistic regression / lasso solver. I thought about writing a quick tutorial that could be useful.

PAPER: shotgun paper appears in this year ICML 2011. The paper explains the approach we took to allow running our algorithm on multicore machines. It analyzes the theory, and justifies the cases where parallel execution does not hurt accuracy.

CODE: the shotgun code is found here: http://select.cs.cmu.edu/code/

TARGET: the goal of this code, is to handle large scale problems, that from the one hand fit into a multicore machine, but from the other hand, other solvers such as GLMNET, Boy'd l1 interior point methods and liblinear fail to scale.

LICENSE: The code is licensed under Apache license.

INTERFACES: We have both a C code version, as well as Matlab interface for running the code from within Matlab. Due to Patrick Harrington (OneRiot.com) request, we added support for Matrix Market input format.
Additional R interface is found here, thanks to Steve Lianoglou, Cornell graduate student.

COST FUNCTION:
We use the following cost function formulation.
For Lasso:
argmin_x sum_i [(A_i*x - y_i)^2 + lambda * |x|_1]
For sparse logistic regression:
argmin_x sum_i [-log(1 + exp(-y_i * x* A_i) ) + lambda * |x|_1]

where |x|_1 is the first norm (sum of absolute value of the vector x).

Matlab Usage:

x = shotgun_logreg(A,y,lambda)
x = shotgun_lasso(A,y,lambda)

C Usage:

./mm_lasso [ A input matrix_file] [y input vector file] [x vector output file] [algorithm] [ threshold] [ K] [max_iter] [num_threads] [lammbda]
  Program inputs are:
Matrix and vector files are mandaroty inputs
Usage: ./mm_lasso
 -m matrix A in sparse matrix market format
  -v vector y in sparse matrix market format
  -o output file name (will contain solution vector x, default is x.mtx)
  -a algorithm (1=lasso, 2=logitic regresion, 3 = find min lambda for all zero solution)
  -t convergence threshold (default 1e-5)
  -k solution path length (for lasso)
  -i  max_iter (default 100)
  -n num_threads (default 2)
  -l lammbda - positive weight constant (default 1)
  -V verbose: 1=verbose, 0=quiet (default 0) 

More interesting ML contests

I just saw an interesting post by Zeno Gantner. A website representing multiple ML contests is found on: http://www.kaggle.com/

The highest rewarding competition is: http://www.heritagehealthprize.com/
for a total prize of 3M $!!

Efficient multicore collaborative filtering

Recently we got the 5th place in ACM Yahoo! KDD CUP (track1). We report out solution method on arxiv. This is a joint work with Yucheng Low from CMU, and Yao Wu, Qiang Yan and Qing Yang from the Chinese National Academy of Science.

In our opinion, there were two main challenges in this contest:
1) The magnitude of the data: the dataset has about 260M music ratings
in the range 0-> 100. Each rating is composed of user, music item, time of rating and the numeric rating. Time of ratings is between 2249 - 6649 (this is from the top of my head - minor inaccuracies possible).
2) Special characteristics of the data: data includes some taxonomy information which relates music tracks to albums, artists and genere.

Here is some more information about the data from the contest website:
The dataset is split into three subsets:

* - Train data: in the file trainIdx1.txt
* - Validation data: in the file validationIdx1.txt
* - Test data: in the file testIdx1.txt


For each subset, user rating data is grouped by user. First line for a user is formatted as:

* <usedid>|<#UserRatings>\n

Each of the next <#UserRatings> lines describes a single rating by , sorted in chronological order. Rating line format is:

* <itemid>\t<score>\t<date\t><time>\n

The scores are integers lying between 0 and 100. All user id's and item id's are consecutive integers, both starting at zero. Dates are integers describing number of days elapsed since an undisclosed date.

An item has at least 20 ratings in the total dataset (including train, validation, and test sets).

Each user has at least 10 ratings in the training data, which were given by the user earlier than his validation ratings. Then, each user has exactly four ratings in the validation data, which come earlier in time than the ratings by the same user in the test data. Finally, the test data holds the last 6 ratings of each user.

For the test subset, we withheld the scores. The contestants are asked to provide predictions for these test scores. The predictions should be arranged by the given test set order. Each prediction is quantized to one of the 256 evenly spaced numbers between 0 and 100 (100*0/255, 100*1/255,...,100*254/255, 100*255/255). Thus, a single unsigned byte would be dedicated for a predicted value, and predicting the 6,005,940 ratings of the test set would require 6,005,940 bytes. (We provide C and Python programs for converting into well-formatted prediction files.)

The evaluation criterion is the root mean squared error (RMSE) between predicted ratings and true ones.

The test subset is further split into two equally sized subsets, called Test1 and Test2. Test1 is used to rank contestants on the public Leaderboard and Test2 is used for deciding the winners of the contest. The split between Test1 and Test2 is not disclosed.

The dataset statistics are as follows:
#Users #Items #Ratings #TrainRatings #ValidationRatings #TestRatings
1,000,990 624,961 262,810,175 252,800,275 4,003,960 6,005,940

Besides of the rating itself, there is taxonomy information as well. In other words:
* Each music item has an album.
* Each album has an artist.
* Each album has a genre.
Here is an excerpt from the contest website:
A distinctive feature of this dataset is that user ratings are given to entities of four different types: tracks, albums, artists, and genres. In addition, the items are tied together within a hierarchy. That is, for a track we know the identity of its album, performing artist and associated genres. Similarly we have artist and genre annotation for the albums. Both users and items (tracks, albums, artists and genres) are represented as meaningless anonymous numbers so that no identifying information is revealed.

Our solution method:
* We used GraphLab for rapid prototyping of multiple collaborative filtering algorithms and
for fine tuning their parameters. Multiple algorithms where blended together using the ensemble method (you are welcome to read more in our paper!).
* Most linear models take into account only the information about user, music item and rating. So the user-> item matrix is decomposed to build a linear model. However, if we know that a user likes Madona, he may like different Madona albums/or songs than the one he rated. So it is good to have this relation in the model. The same with user who likes Jazz, he may well like other albums of Jazz. Since the rating is for a single song, if we do not relate the artist to the song, we miss this information. We propose a novel method called MFITR (matrix factorization item taxonomy regularization)
1) Add feature vector for artist, that mean that if a user like a certain artist it will add to the ratings of other songs of this artist.
2) Add a linear connection between the artist and the items, or else if they will be independent, thus making section 1) not useful. So we added weights that links between user, artist and album. The weights force that if user rated one album or artist higher, it will result in other items from the same artist or album to be higher as well.
3) We did not use genere in our model, although in principal genre can be added using the same technique.

We believe that Yahoo KDD CUP contest data is a great academic resource for both academic researchers as well as high-tech companies who perform collaborative filtering tasks. This is why we release a large portion of our source code as part of GraphLab's collaborative filtering library. Python/Matlab scripts are available for converting the data between KDD format into GraphLab's format.

Recently, we learned from Noam Koenigstein, a Tel-Aviv PhD candidate, about a related paper that was submitted for publication: Yahoo! Music Recommendations: Modeling Music Ratings with Temporal Dynamics and Item Taxonomy. By Gideon Dror, Noam Koenigstein and Yehuda Koren: In ACM Conference on Recommender Systems (RecSys), 2011. While obtained independently, our solution has some similarities to their proposed solution by adding a feature vectors for artist and albums. Their paper have also nice overview of KDD data characteristics in section 3.

I got another interesting resource from Yao Wu: InnerSpace group website: http://apex.sjtu.edu.cn/apex_wiki/svdfeature - they won the 3rd place this year.

And here is the workshop website including all presentations.