How to prepare your problem to be used in GraphLab / GraphLab parsers

In many cases your data is a collection of strings and you like to convert it to numerical form so it can be used in any machine learning software.

In GraphLab v2, I have added parsers library that can help you accomplish this task hopefully easier.
Let's start with an example. Suppose I have a collection of documents and in each document I have
a bag of words that appear. The input to GraphLab parser is:

1::the boy with big hat was here
2::no one would have believe in the last years of the nineteenth century

where 1 and 2 are the file numeric ids, we use '::' as a separator, and the rest of the line contains keywords that appear in that document.

Assuming you have this format, it is very easy to convert it to be used in GraphLab. You simply use
the texttokenparser application.
Preliminaries: you will need to install GraphLab v2 (explanation under installation section here).

And here is an example run of the parser:

./texttokenparser --dir=./ --outdir=./ --data=document_corpus.txt --gzip=false --debug=true

WARNING:  texttokenparser.cpp(main:209): Eigen detected. (This is actually good news!)

INFO:     texttokenparser.cpp(main:211): GraphLab parsers library code by Danny Bickson, CMU

Send comments and bug reports to danny.bickson@gmail.com

Currently implemented parsers are: Call data records, document tokens 

Schedule all vertices

INFO:     sweep_scheduler.hpp(sweep_scheduler:124): Using a random ordering of the vertices.

INFO:     io.hpp(gzip_in_file:698): Opening input file: ./document_corpus.txt

INFO:     io.hpp(gzip_out_file:729): Opening output file ./document_corpus.txt.out

Read line: 1 From: 1 To: 1 string: the

Read line: 1 From: 1 To: 2 string: boy

Read line: 4 From: 1 To: 3 string: with

INFO:     texttokenparser.cpp(operator():159): Parsed line: 50000 map size is: 30219

INFO:     texttokenparser.cpp(operator():159): Parsed line: 100000 map size is: 39510

INFO:     texttokenparser.cpp(operator():159): Parsed line: 150000 map size is: 45200

INFO:     texttokenparser.cpp(operator():159): Parsed line: 200000 map size is: 50310

INFO:     texttokenparser.cpp(operator():164): Finished parsing total of 230114 lines in file document_corpus.txt

total map size: 52655

Finished in 17.0022

Total number of edges: 0

INFO:     io.hpp(save_map_to_file:813): Save map to file: ./.map map size: 52655

INFO:     io.hpp(save_map_to_file:813): Save map to file: ./.reverse.map map size: 52655

The output of the parser :
1) Text file containing consecutive integers in sparse matrix market format. In other words, each string is assigned an id, and a sparse matrix is formed where the rows are the document numbers and the non-zero columns are the strings.
NOTE: currently you will need to manually create the two header lines as explained here. The header lines specify the number of rows, columns and non-zero entires in the matrix. In the future I will automate this process.
2) A mapping from each text keyword to its matching integer
3) A mapping from each integer to its matching string.

Advanced options:
1) It is possible to parse in parallel (on a multicore machine) multiple files and still have the ids assigned correctly. Use the --filter= command line argument to select all files starting with a certain prefix. Do not use the --data= command line argument in that case.
2) Support for gzip input format. Using --gzip=true command line option.
3) Save the mapping into readable text file using the --save_in_text=true command line argument.
4) Incrementally add more documents to an existing map by using the --load=true command line flag.
5) Limit the number of parsed lines using --lines=XX command line flag (useful for debugging!)
6) Enable verbose mode using --debug=true command line flag.

Principal components wanted

Here is quite a funny joke. A startup company called principal components wanted

links to my blog. Now what is funny about it? The title.. It says: today's tools are just too complicated and painful to be used by non experts. And then they link to my explanations on how to debug hadoop (using the painful keyword).. :-) My first reaction is that they are completely right:
1) I am an expert
2) Hadoop is too complicated..
If those tools where too simple to use no one would have read my blog. The second funny thing, is that if they would have linked to any of my GraphLab instructions, I would have been more upset.. But I algo agree that GraphLab is still too complicated and advanced relative to the way we want it to be. Anyway I wish those guy a lot of luck, with the explosion of ML related startups it is not going to be an easy breakthrough.

GraphLab svd v. 2 tutorial

This blog post is outdated. The new SVD instructions have moved here:
http://docs.graphlab.org/collaborative_filtering.html

GraphLab v2 @ Big Learning Workshop

It took some time, but finally Carlos' Guestrin GraphLab version 2 talk, given at the Big Learning Workshop is online. Enjoy!

Open Connectome Project

A couple of days ago I sent out an initial announcement about our planned GraphLab workshop and immediately I started getting a lot of interesting feedback from my blog readers.

Joshua Vogelstein, a researcher at the Dept. of Applied Mathematics & Statistics, Johns Hopkins University just sent me a note a would like very much to participate in our workshop. Joshua is a part of the Open Connectome project, a very interesting project in the area of neuroscience. The project mission is to allow open access for neuro data for researchers worldwide. Here is some examples for the data they are hosting:

I have no clue what the above picture means (although I must admit they look pretty cool)!!.. so I asked Joshua to describe in a little more detail the problems he is working on. This is what I got from him:

We have two very different kinds of data:

1) EM Connectomes - each dataset is a volumetric image of part of some animal brain, ranging in size from 1GB and 10TB. you can look at the data in 2D here
the first project is 10TB. we also designed a RESTful interface to facilitate anybody downloading and processing the data. the instructions for using it are here.
another thing that we have, but haven't yet provided the documentation for, is an annotation database. the idea is that anybody should be able to download some volume, annotate it, and upload it back to the server. we collect and store all the annotations, and can combine them to obtain meta-annotations. i expect that we'll release details for the annotation database in a week or so.

2) MR Connectomes - these are essentially multimodal images of human brains, including both time-varying and non-time-varying. the "multi" part of multimodal means that for each subject we have a number of different kinds of images. our plan for what to do with this stuff is here. Currently, we are organizing the data and pre-processing it. the output of the preprocessed data with be for each subject (there are a few thousand of them), we will have an O(10,000) vertex and O(100,000) edge graph. our vertices are attributed. in particular, each vertex has a 3d position as well as a whole time-series associated with it. we will implement a kind of spectral clustering on each graph (see this manuscript for the theoretical results of our algorithm).

Another interesting aspect in Joshua's work, is that he is part of the Institute for Data Intensive Engineering and Science which has a 5PB "Data-Scope".

Joshua is interested in exploring GraphLab at the first step for spectral clustering of brain image graphs. I promised to help him utilize our SVD and K-mean solvers and try them out on some of his data. I am looking forward to meeting Joshua at our workshop. I also think it is going to be very interesting if he could give a quick talk describing some of the challenges he is facing and what is needed out of GraphLab to help him solve them.

Some interesting projects

That where recently brought to my attention.

I got this from Oren Dobzinski:
Cassovary - new graph processing library from Twitter. Pankaj Gupta from Twitter is involved in this project. Since he is also a program committee member of our GraphLab workshop it will be very interesting to learn about this new system.

Ted Willke from Intel Labs brought to my attention the following project:
Galois - executes serial c++ code in parallel on multicore machines.

Mika Illouz from Eigendog recommended on the following projects:
ciel: yet-another-distributed-computing-abstraction
julia a new programming language, aims to be R/Matlab for clusters.

Definitely a lot of activity in this domain.

Large scale SVM (support vector machine)

Not long ago I had the pleasure of visiting Toyota Technical Institute in Chicago.
I had some interesting meeting with Joseph Keshet. We discussed what is the best way to
deploy large scale kernel SVM.

According to Joseph, linear SVM is a pretty much solved problem. State of the art solutions
consists Pegasos and SVMLight see Joachim 2006.

Recently, Joseph have worked on large scale SVMs in two fronts: GPU and MPI.
The GPU kernelized (not linear) can be found here. This paper appeared in KDD 2011.
Here is an image depicting nice speedup they got:

The second SVM activity by Joseph is how to quickly approximate the kernel matrix using Taylor serias expansion. This work is presented in their arxiv paper. Evaluating the kernel matrix has a major overhead in SVM implementation especially because it is dense.  Previously, I have implemented a large scale SVM solver on up to 1024 cores on IBM BlueGene supercomputer.  About 90% of the time was spent on evaluating the kernel matrix. I wish I had some fancy techniques as Joseph proposes for quickly approximating the kernel matrix...