Large Scale Machine Learning and Other Animals

An Overview of Graph Processing Frameworks

2013-05-19T10:17:00.001-07:00

A nicely written overview of Graph processing frameworks by Ben Lorica from O'Reilly media. Will help you master the essential buzzwords on big data analytics and graph processing.. And explains quite clearly why you should attend our 2nd GraphLab workshop!

Kaggle Titanic Contest

2013-05-19T10:10:00.001-07:00

I got this from Sagie Davidovich a link to Kaggle's Titanic Contest. The task is to predict who survived the Titanic based on some features like age, cabin class, name, and presence of relatives on the Ship.
What I like about this task, is that you can actually explain to your gradma what you are predicting (unlike many other ML tasks which are hard to explain for the non expert..). The dataset is quite tiny in our standards. But still enables the usage of different ML methods. The best prediction on the leader-board has about 99% accuracy.

Funding for the next generation of GraphLab

2013-05-14T04:40:00.000-07:00

The GraphLab journey began with the desire:

to rethink the way we approach Machine Learning and Graph analytics,
to demonstrate that with the right abstractions and system design we can achieve unprecedented levels of performance, and
to build a community around large-scale graph computation.

We have been blown away by the excitement and growth of the GraphLab community and have been unable to keep up with the incredible interest from our amazing users.

Therefore, we are proud to announce GraphLab Inc, a company devoted to accelerating the development of the open-source GraphLab project.

Why a company?

Put simply, we need a full-time dedicated effort to take GraphLab from where it is today to where we would like to see it go in the future. With a dedicated team, you will see exciting new features, more integration with Cloud infrastructure, easier installation and deployment, along with a revamped support effort, with additional commercial-grade options and tools.

What happens to the open-source project?

The open source project will remain the flagship technology where we push the limits of graph computation and develop new ideas. With a dedicated team focused on the code, documentation, deployment process and most importantly support, you can expect a regular release schedule, faster turnaround on bug fixes and improvements, and a higher quality bar for the code going forward. We will continue to rely on our community to push us to tackle bigger, harder problems, and to contribute back to the open-source effort.

Are you going to charge for GraphLab now?

We believe the only way the best ideas in machine learning are developed is with the help of a vibrant community (it takes a village). That is why GraphLab will remain an open-source project; now with a company behind it, we can double our efforts to keeping the project healthy.

What is the roadmap for the open-source project?

GraphLab 2.2 is just around the corner, see here for more details as to what is in it. Beyond that, we are exploring a new computation engine and further enhancements to the communication layer, as well as simpler integration with existing Cloud technologies, easier installation procedures, and an exciting new graph storage system. And of course, we look forward to working with you to develop the roadmap and build the next generation of the GraphLab system.

The next 12 months will be an exciting time for us, and we hope that everyone will come along for the ride .

Learn more at graphlab.com

Bond Percolation in GraphLab

2013-05-12T06:48:00.001-07:00

I was asked by Prof. Scott Kirkpatrick to help and implement bond percolation in GraphLab. It is an oldie but goldie problem which is closely related to the connected components problem.

Here is an explanation about bond percolation from Wikipedia:
A representative question (and the source of the name) is as follows. Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n vertices, usually called "sites", in which the edgeor "bonds" between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by Broadbent & Hammersley (1957), and has been studied intensively by mathematicians and physicists since.

2-d bond percolation problem. Will the water find their way

along the edges of this maze from top to bottom?

The algorithm for finding the connected edges is very simple:

In parallel

- for each edge, record the minimum id of the connected edges

- if there are no more changes in the network, break

This algorithm is frequently used in social networks to find groups of friends. And it is of course distributed and scales to very large problems. The output is the min component found for each edge. From this output we can find the edge clusters.

I have utilized the newest experimental version of GraphLab (v. 2.2) for quickly implementing the above algorithm. The resulting code is surprisingly simple. The main loop of the program:

//create a GraphLab engine
engine_type engine(dc, graph, clopts);
//register the map and combine operations that will be used in the update function

engine.register_map_reduce(BOND_PERCOLATION_MAP_REDUCE, bond_percolation_map, bond_percolation_combine);

  //in a loop
  for (int i=0; i< max_iter; i++){
     //perform update function on each node

     engine.parfor_all_local_vertices(bond_percolation_function);
     //wait until all nodes are done

     engine.wait();
     //count the number of unsatisfied links

     size_t diff = graph.map_reduce_edges<size_t>(count_component);

     //if no more links to explore we are done

     if (diff == 0)

       break;

}

bond_perculation_function which is executed in parallel across all node. In this function, we traverse all connected edges, and compare their minimum edges id using the bond_perculation_combine. As it is easy to verify, each of those implemented function has a single line of code.

//return the min component id found across this edges and its two connecting nodes

unsigned int bond_percolation_map(const graph_type::vertex_type& center,

                         graph_type::edge_type& edge,

                         const graph_type::vertex_type& other) {

   return edge.data().comp_id =  std::min(std::min(center.data().comp_id, edge.data().id), other.data().comp_id);

}

//find min component of two connected edges

void bond_percolation_combine(unsigned int& v1, const unsigned int& v2) {

    v1 = std::min(v1, v2);

}

//the main update function, go over all nodes and selects their min edge id

void bond_percolation_function(engine_type::context_type& context,

                  graph_type::vertex_type& vertex) {

     vertex.data().comp_id =  context.map_reduce<unsigned int>(BOND_PERCOLATION_MAP_REDUCE, graphlab::ALL_EDGES);

}

//count the number of components that are still not satisfied. When the number of components are zero, we are done

size_t count_components(const graph_type::edge_type & edge) {

  return = (edge.source().data().comp_id != edge.target().data().comp_id);

}

The full code is here. It is now part of the graph_analytics toolkit in v2.2. Needless to say it is working.. :-)

Hadoop Mortar

2013-05-11T23:38:00.001-07:00

Just got from my boss Prof. Carlos Guestrin this link: http://blog.mortardata.com/post/49934459499/recommender-systems-for-free

It looks like a nice publicity stunt - Hadoop Mortar is proposing to build recommender systems for free for selected companies. I wonder if this will actually work?

Fun Readings about Startups

2013-05-09T08:17:00.000-07:00

I got the following from my collaborator Jay Gu:

Here's a fun reading about startup: a well written lecture notes on Peter Thiel's course at Stanford, which covers topics like culture, hiring, strategy, lessons and mindset etc. I've read first 5 chapters and found it interesting and rewarding so I decided to share with all of you.

Html version

http://blakemasters.com/peter-thiels-cs183-startup

Epub version if you like to read on your iPad

http://stanfy.com/blog/epub-version-of-peter-thiel-lectures-at-stanford-university-cs183-startup/

Below are some fun quotes just give you a quick taste.

About hiring good engineers from "Google":

"So the way to compete against the giants is not with money. Google will outbid you. They have oil derrick that spits out $30bn in search revenue every year. To win, you need to tell a story about cogs. At Google, you’re a cog. Whereas with me, you’re an instrumental piece of this great thing that we’ll build together. Articulate the vision. Don’t even try to pay well. Meet people’s cash flow needs. Pay them so they can cover their rent and go out every once in awhile. It’s not about cash. It’s about breaking through the wall of cynicism. It’s about making 1% of this new thing way more exciting than a couple hundred grand and a cubicle at Google."

"We tend to massively underestimate the compounding returns of intelligence. As humans, we need to solve big problems. If you graduate Stanford at 22 and Google recruits you, you’ll work a 9-to-5. It’s probably more like an 11-to-3 in terms of hard work. They’ll pay well. It’s relaxing. But what they are actually doing is paying you to accept a much lower intellectual growth rate. When you recognize that intelligence is compounding, the cost of that missing long-term compounding is enormous. They’re not giving you the best opportunity of your life. Then a scary thing can happen: You might realize one day that you’ve lost your competitive edge. You won’t be the best anymore. You won’t be able to fall in love with new stuff. Things are cushy where you are. You get complacent and stall. So, run your prospective engineering hires through that narrative. Then show them the alternative: working at your startup."

The fundamental question

"The path from 0 to 1 might start with asking and answering three questions: First, what is valuable? Second, what can I do? And third, what is nobody else doing?

The intellectual rephrasing of these questions is: What important truth do very few people agree with you on?

The business version is: What valuable company is nobody building?"

About escaping competition:

"Intense competition makes things hard because you just beat heads with other people. The intensity of competition becomes a proxy for value. But value is a different question entirely."

About how to own a market:

"For a company to own its market, it must have some combination of brand, scale cost advantages, network effects, or proprietary technology."

About hiring nerds vs athletes:

"In thinking about building good company culture, it may be helpful to dichotomize two extreme personality types: nerds and athletes. Engineers and STEM people tend to be highly intelligent, good at problem solving, and naturally non zero-sum. Athletes tend to be highly motivated fighters; you only win if the other guy loses."

"The optimal spot on the matrix is monopoly capitalism with some tailored combination of zero-sum and non zero-sum oriented people. You want to pick an environment where you don’t have to fight. But you should bring along some good fighters to protect your non zero-sum people and mission, just in case."

New collaborative filtering functionality in GraphLab and GraphChi

2013-05-09T06:37:00.005-07:00

A few days ago I wrote in this blog about parallel coordinate descent for speeding up ALS.
I have just implemented parallel ALS using coordinate descent a.k.a.

CCD++ algorithm. The algorithm is described in the following two papers:

H.-F. Yu, C.-J. Hsieh, S. Si, I. S. Dhillon, Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems. IEEE International Conference on Data Mining(ICDM), December 2012.

Steffen Rendle, Zeno Gantner, Christoph Freudenthaler, and Lars Schmidt-Thieme. Fast context-aware recommendations with factorization machines. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval (SIGIR '11). ACM, New York, NY, USA, 635-644.

In a nutshell, it speeds up ALS by avoiding the need for costly least square computation, each dimension (coordinate) is handled separately in parallel.

Documentation of the method for GraphChi is here:

http://bickson.blogspot.co.il/2012/12/collaborative-filtering-with-graphchi.html

Documentation of the method for GraphLab is here:

http://docs.graphlab.org/collaborative_filtering.html

Note: For GraphLab the algorithm is implemented in version 2.2 which will be release this summer. It is still possible to checkout this version and try it out using the mercurial command "hg up v2.2".

Let me know if you try it out!

Speeding up parallel ALS

2013-05-06T00:06:00.002-07:00

My collaborator Joey Gonzalez sent me the following paper:
H.-F. Yu, C.-J. Hsieh, S. Si, I. S. Dhillon, Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems. IEEE International Conference on Data Mining(ICDM), December 2012.

Which got the best paper award in ICDM 2012. It is a well written a paper proposing a technique for speeding up ALS (alternating least squares) when executed in parallel, by using coordinate descent. It also has a good review of the two highly repeating building blocks in matrix factorization algorithms: alternating least squares and stochastic gradient descent and a discussion on how to parallelize them.

When I read the paper, it reminded me of previous work of Steffen Rendle, which I shared with my blog readers here:
Steffen Rendle, Zeno Gantner, Christoph Freudenthaler, and Lars Schmidt-Thieme. 2011. Fast context-aware recommendations with factorization machines. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval (SIGIR '11). ACM, New York, NY, USA, 635-644.

Basically, it is the same construction. (Unfortunately it seems that ICDM guys where not aware to the previous SIGIR paper).

Here is the algorithm update rule from Steffen's paper:

And here is the update rule from ICDM paper:

Anyway aside from slightly different notations it is basically the same algorithm. And the conclusions of both papers are identical: this constructions improves performance of parallel ALS, and have favorable performance relative to SGD.

I asked Prof. Inderjit Dillon from The University of Texas at Austin about the relation between the papers and I got the following reply:

Solving the one-variable problem is simple, and was not intended to count as a "contribution" (we had similar 1-variable solutions in an earlier paper on coordinate descent for NMF, which appeared in KDD 2011). The main contribution of our ICDM paper is to present a parallel coordinate descent algorithm (on multi-core and distributed memory machines) for matrix factorization for missing value estimation. The results show it outperforms ALS and SGD, which is what most people seem to use in industry (and which is what prompted me to investigate co-ordinate descent for the problem).

To anyone who is interested in reading more, my recommendation is to read first the ICDM paper for getting a general overview, and then read the SIGIR paper for getting more specific.

To those of you who are interested in additional parallel coordinate descent method for L1 loss function, you are welcome to take a look at our ICML paper described here.

GraphLab Challenge @ SC13

2013-05-02T12:24:00.000-07:00

Just learned from my boss Prof. Carlos Guestrin about student cluster competition which is part of SC13 conference. The interesting part is the GraphLab programming is one of the challenges:

• GraphLab(rador)http://graphlab.orgThe GraphLab project started in 2009 to develop a new parallel computation abstraction tailored to machine learning. GraphLab scales to graphs with billions of vertices and edges easily, performing orders of magnitude faster than competing systems. GraphLab combines advances in machine learning algorithms, asynchronous distributed graph computation, prioritized scheduling, and graph placement with optimized low-level system design and efficient data-structures to achieve unmatched performance and scalability in challenging machine learning tasks.
The GraphLab project consists of a core C++ GraphLab API and a collection of high-performance machine learning and data mining toolkits built on top of the GraphLab API. The API is built on top of standard cluster and cloud technologies: interprocess communication is accomplished over TCP-IP and MPI is used to launch and manage GraphLab programs. Each GraphLab process is multithreaded to fully utilize the multicore resources available on modern cluster nodes. GraphLab supports reading and writing to both Posix and HDFS filesystems.

We will keep an eye to hear about the outcome of this contest...

Recsys 2013: Yelp! Business Prediction Contest

2013-04-30T03:02:00.001-07:00

I got an interesting email from Prof. Nicholas Ampazis from University of Aegean, Greece. Nicholas is trying out GraphChi gensgd for Kaggle's Yelp! business prediction contest which is part of Recsys 2013.

First he sent me some interesting observations about the dataset:

- There are 2108 training users in the ratings (review) matrix that do appear in the training users file. The reverse is not true (i.e. all users in the training user file have ratings).
- All business_ids in review appear in the business file
- There are 5315 users for which we wish to make predictions that do not appear in the ratings matrix.
- There are 1205 businness_ids for which we wish to make predictions that do not appear in the ratings matrix (those always come in pairs with the unknown users above).
- The union of (distinct) users in the ratings matrix, training user file and test user file is 51082
- The union of (distinct) business_ids in the ratings matrix, training business file and test business file is 12742

Nicholas has kindly agreed to share with us some of the scripts he is using, to convert the Yelp! data to GraphChi: (written by his colleague Vaggelis Tripolitakis - thanks!!).

Disclaimer: we did not fine tune performance of gensgd yet so prediction quality is still poor. We plan to refine execution in the next couple of days and report results here.

0) Register to the competition here and download the datasets into your root GraphChi folder.

1) Download the conversion scripts from GitHub:
https://github.com/vtripolitakis/yelpscripts
2) Give running permission to the script:
# chmod a+rx script

3) Verify that json ruby library is present using:
# sudo gem install json

Note: if you do not have root permission on your machine, install the package using
# gem install json
and add the locally created gem folder into your path, for example:
# export PATH=$PATH:/home/bickson/.gem/ruby/1.8/bin

4) Use the following instructions for converting the data to GraphChi format
(hint: use copy & paste!)

###################### TRAINING SET ##########################

#---REVIEW---
./script yelp_training_set/yelp_training_set_review.json user_id business_id date votes stars > yelp_training_set_review.csv

#----USER---
./script yelp_training_set/yelp_training_set_user.json user_id review_count average_stars name votes > yelp_training_set_user.csv

#----BUSINESS----
./script yelp_training_set/yelp_training_set_business.json business_id open city state review_count longitude latitude categories name neighborhoods full_address stars > yelp_training_set_business.csv

##############################################################

###################### TEST SET ##########################

#---REVIEW---
./script yelp_test_set/yelp_test_set_review.json user_id business_id > yelp_test_set_review.csv

#----USER---

./script yelp_test_set/yelp_test_set_user.json user_id review_count > yelp_test_set_user.csv

#----BUSINESS----

./script yelp_test_set/yelp_test_set_business.json business_id open city state review_count longitude latitude categories name neighborhoods full_address > yelp_test_set_business.csv

##############################################################

######### CONCATENATE USER/BUSINESS FILES FROM TRAIN AND TEST ##########################

cat yelp_training_set_user.csv yelp_test_set_user.csv > user_file.csv
cat yelp_training_set_business.csv yelp_test_set_business.csv > business_file.csv

5) Run GraphChi GENSGD
a) First trial: run using reviews only (without user and business information)

bickson@thrust:~/graphchi$ ./toolkits/collaborative_filtering/gensgd --training=yelp_training_set_review.csv --test=yelp_test_set_review.csv --from_pos=0 --to_pos=1 --val_pos=2 --rehash=1 --gensgd_mult_dec=0.999999 --quiet=1 --file_columns=3 --minval=1 --maxval=5 --clean_cache=1
WARNING: common.hpp(print_copyright:180): GraphChi Collaborative filtering library is written by Danny Bickson (c). Send any comments or bug reports to danny.bickson@gmail.com
[training] => [yelp_training_set_review.csv]
[test] => [yelp_test_set_review.csv]
[from_pos] => [0]
[to_pos] => [1]
[val_pos] => [2]
[rehash] => [1]
[gensgd_mult_dec] => [0.999999]
[quiet] => [1]
[file_columns] => [3]
[minval] => [1]
[maxval] => [5]
[clean_cache] => [1]

...
2.60862) Iteration: 0 Training RMSE: 1.22329
3.39838) Iteration: 1 Training RMSE: 1.18201
4.2365) Iteration: 2 Training RMSE: 1.16143
5.04867) Iteration: 3 Training RMSE: 1.14613
5.89126) Iteration: 4 Training RMSE: 1.13354
6.70683) Iteration: 5 Training RMSE: 1.1225
Found 2466 new test users with no information about them in training dataset!

b) second run: throw in user information

WARNING: common.hpp(print_copyright:180): GraphChi Collaborative filtering library is written by Danny Bickson (c). Send any comments or bug reports to danny.bickson@gmail.com

[training] => [yelp_training_set_review.csv]

[test] => [yelp_test_set_review.csv]

[from_pos] => [0]

[to_pos] => [1]

[val_pos] => [2]

[rehash] => [1]

[gensgd_mult_dec] => [0.999999]

[quiet] => [1]

[file_columns] => [3]

[minval] => [1]

[maxval] => [5]

[user_file] => [user_file.csv]

[clean_cache] => [1]

...

3.14781) Iteration: 0 Training RMSE: 1.21868

4.17876) Iteration: 1 Training RMSE: 1.10707

5.20784) Iteration: 2 Training RMSE: 1.05591

6.28441) Iteration: 3 Training RMSE: 1.01406

7.31922) Iteration: 4 Training RMSE: 0.975489

8.33992) Iteration: 5 Training RMSE: 0.939978

Found 2466 new test users with no information about them in training dataset!

c) third run: throw in also business information:

bickson@thrust:~/graphchi$ ./toolkits/collaborative_filtering/gensgd --training=yelp_training_set_review.csv --test=yelp_test_set_review.csv --from_pos=0 --to_pos=1 --val_pos=2 --rehash=1 --gensgd_mult_dec=0.999999 --quiet=1 --file_columns=3 --minval=1 --maxval=5 --user_file=user_file.csv --item_file=business_file.csv --clean_cache=1
WARNING: common.hpp(print_copyright:180): GraphChi Collaborative filtering library is written by Danny Bickson (c). Send any comments or bug reports to danny.bickson@gmail.com
[training] => [yelp_training_set_review.csv]
[test] => [yelp_test_set_review.csv]
[from_pos] => [0]
[to_pos] => [1]
[val_pos] => [2]
[rehash] => [1]
[gensgd_mult_dec] => [0.999999]
[quiet] => [1]
[file_columns] => [3]
[minval] => [1]
[maxval] => [5]
[user_file] => [user_file.csv]
[item_file] => [business_file.csv]
[clean_cache] => [1]
...
3.62809) Iteration: 0 Training RMSE: 1.29575
5.10944) Iteration: 1 Training RMSE: 1.06187
6.50959) Iteration: 2 Training RMSE: 0.995394
7.92686) Iteration: 3 Training RMSE: 0.947596
9.35034) Iteration: 4 Training RMSE: 0.906372
10.7604) Iteration: 5 Training RMSE: 0.86826
Found 2466 new test users with no information about them in training dataset!

Conclusion: including user and business properties significantly improves prediction performance.

The output of gensgd is the file yelp_test_set_review.csv.predict

%%MatrixMarket (null)
22956 1
1.4793704
N/A
3.3002301
2.8208445
4.0713396
N/A
3.1468302
3.6243955

Next: soon I will post some update about performance of GraphChi & how to create the submission format out of GraphChi.

Incremental SVD

2013-04-27T11:56:00.001-07:00

Here is an email I got from Prof. Magnasco from Rockefeller University, NY:

Hi Danny, I've seen some of your posts regarding lanczos and thought I'd ask you.

I have a problem where I need to compute the first few hundred eigenvectors/values in the PCA of a large, dense dataset, about ten thousand times five million. (It's an avi of a fluorescence microscopy experiment). For the larger datasets I might not even be able to hold the entire set in memory. The normal approach would be to compute the 10000^2 A*A' matrix and then diagonalize it, the problem being that this matrix entails 12 million dot products of 5M element vectors. So I was hoping to find a method that iteratively computes the eigenvectors without such explicit evaluations. Is Lanczos numerically stable enough for such sizes?

Thanks,

Marcelo

__________________________________________________________

Marcelo Magnasco Box 212, 1230 York Avenue, NY NY10065

Professor and Head, v +1 212 3278542 f +1 212 3277422

Mathematical Physics Lab http://sur.rockefeller.edu/Plone

The Rockefeller University magnasco@rockefeller.edu

As a great coincidence, I just heard about the same problem solution from Byron Boots, a postdoc in UW:

The incremental SVD papers that I am thinking of have been written by Matthew Brand. He has several papers on this topic, but the one that I have been using the most is this one: http://www.merl.com/papers/docs/TR2006-059.pdf

Unfortunately I am not aware of software package which implements the Brand method. You will probably have to implement it yourself.

Additional resource I found is another paper by Brand:

Brand, M.E., “Incremental Singular Value Decomposition of Uncertain Data with Missing Values”, European Conference on Computer Vision (ECCV), Vol 2350, pps 707-720, May 2002 (Lecture Notes in Computer Science)

Which has a better explanation of the setup.

ACM KDD CUP 2013

2013-04-24T12:14:00.001-07:00

ACM KDD (Knowledge Discovery and Data mining) 2013 conference will be held Aug 11-14 in Chicago. The annual KDD CUP competition is organized this year by Microsoft Research.
There are two tracks:
1) Identification of authorship of academic papers - track 1.
2) Author disambiguation - track 2.

Following the last couple of years, we hope to see some activity of users who are utilizing GraphLab for computing part of the solution. I will update more once we get interesting results to report.

Presto: distributed R framework from HP Labs

2013-04-23T04:47:00.000-07:00

I got from my collaborator Aapo Kyrola the following pointer to Presto.
Presto is an interesting system which allowed large scale computation in R by distributing the computational workload in a cluster. Presto implements distributed arrays and thus allows efficient implementation of linear algebra primitives like matrix-vector product.

The following two papers where recently published about Presto:

Presto: Distributed Machine Learning and Graph Processing with Sparse Matrices. Shivaram Venkataraman, Erik Bodzsar, Indrajit Roy, Alvin AuYoung, Rob Schreiber. Eurosys 2013, Prague, Czech Republic.
Using R for Iterative and Incremental Processing. Shivaram Venkataraman, Indrajit Roy, Alvin AuYoung, Rob Schreiber. HotCloud 2012, Boston, USA.

It those papers, a large number of applications where implemented in Presto like K-means, ALS< pagerank, vertex centrality, shortest path and others. A large performance gain of x15 - x40 is demonstrated over Hadoop and Spark.

Unfortunately, it is not clear if Presto will be released as an open source project.

Distributed Dual Decomposition (DDD) in GraphLab

2013-04-18T07:23:00.002-07:00

Our collaborator Dhruv Batra, from Virginia Tech has kindly contributed DDD code for GraphLab. Here are some explanation about the method and how to deploy it.
The full documentation is found here.

Distributed Dual Decomposition

Dual Decomposition (DD), also called Lagrangian Relaxation, is a powerful technique with a rich history in Operations Research. DD solves a relaxation of difficult optimization problems by decomposing them into simpler subproblems, solving these simpler subproblems independently and then combining these solutions into an approximate global solution.

More details about DD for solving Maximum A Posteriori (MAP) inference problems in Markov Random Fields (MRFs) can be found in the following:

D. Sontag, A. Globerson, T. Jaakkola. 
Introduction to Dual Decomposition for Inference. 
Optimization for Machine Learning, editors S. Sra, S. Nowozin, and S. J. Wright: MIT Press, 2011.

Running DDD

The input MRF graph is assumed to be in the standard UAI file format. For example a 3x3 grid MRF can be found here: grid3x3.uai.

The program can be run like this:

> ./dd --graph grid3x3.uai

Other arguments are:

–help Display the help message describing the list of options.

–output The output directory in which to save the final predictions.

–dualimprovthres (Optional, default 0.00001) The amount of change in dual objective (in log-space) that will be tolerated at convergence.

–pdgapthres (Optional, default 0.1) The tolerance level for zero primal-dual gap.

–maxiter (Optional, default 10000) The maximum no. of dual update iterations.

–engine (Optional, Default: asynchronous) The engine type to use when executing the vertex-programs
- synchronous: All LoopyBP updates are run at the same time (Synchronous BP). This engine exposes greater parallelism but is less computationally efficient.
- asynchronous: LoopyBP updates are run asynchronous with priorities (Residual BP). This engine is has greater overhead and exposes less parallelism but can substantially improve the rate over convergence.

–ncpus (Optional, Default 2) The number of local computation threads to use on each machine. This should typically match the number of physical cores.

–scheduler (Optional, Default sweep) The scheduler to use when running with the asynchronous engine. The default is typically sufficient.

–engine_opts (Optional, Default empty) Any additional engine options. See –engine_help for a list of options.

–graph_opts (Optional, Default empty) Any additional graph options. See –graph_help for a list of options.

–scheduler_opts (Optional, Default empty) Any additional scheduler options. See –scheduler_help for a list of options.

Anyone who tries to run it - please let us know!

CLiMF Algorithm in GraphChi

2013-04-17T12:35:00.003-07:00

I got some good news to report: last week we got a great contribution from Mark Levy (last.fm) for GraphChi collaborative filtering toolkit. Mark have implemented the CLiMF algorithm, described in the paper: CLiMF: learning to maximize reciprocal rank with collaborative less-is-more filtering. Yue Shi, Martha Larson, Alexandros Karatzoglou, Nuria Oliver, Linas Baltrunas, Alan Hanjalic, Sixth ACM Conference on Recommender Systems, RecSys '12.

CLiMF is a ranking method which optimizes MRR (mean reciprocal rank) which is an information retrieval measure for top-K recommenders. CLiMF is a variant of latent factor CF which optimises a significantly different objective function to most methods: instead of trying to predict ratings CLiMF aims to maximise MRR of relevant items. The MRR is the reciprocal rank of the first relevant item found when unseen items are sorted by score i.e. the MRR is 1.0 if the item with the highest score is a relevant prediction, 0.5 if the first item is not relevant but the second is, and so on. By optimising MRR rather than RMSE or similar measures CLiMF naturally promotes diversity as well as accuracy in the recommendations generated. CLiMF uses stochastic gradient ascent to maximise a smoothed lower bound for the actual MRR. It assumes binary relevance, as in friendship or follow relationships, but the graphchi implementation lets you specify a relevance threshold for ratings so you can run the algorithm on standard CF datasets and have the ratings automatically interpreted as binary preferences.

CLiMF-related command-line options:
--binary_relevance_thresh=xx Consider the item liked/relevant if rating is at least this value [default: 0]
--halt_on_mrr_decrease Halt if the training set objective (smoothed MRR) decreases [default: false]
--num_ratings Consider this many top predicted items when computing actual MRR on validation set [default:10000]

Here is an example on running CLiMF on Netflix data:

./toolkits/collaborative_filtering/climf --training=smallnetflix_mm --validation=smallnetflix_mme --binary_relevance_thresh=4 --sgd_gamma=1e-6 --max_iter=6 --quiet=1 --sgd_step_dec=0.9999 --sgd_lambda=1e-6

Training objective:-9.00068e+07
Validation MRR: 0.169322
Training objective:-9.00065e+07
Validation MRR: 0.171909
Training objective:-9.00062e+07
Validation MRR: 0.172372
Training objective:-9.0006e+07
Validation MRR: 0.172503
Training objective:-9.00057e+07
Validation MRR: 0.172544
Training objective:-9.00054e+07
Validation MRR: 0.172549

I am very excited about this development - and I hope many more users will follow with additional contributions to our growing code base! Thanks Mark!!!

DARPA PPAML

2013-04-17T12:27:00.002-07:00

I got this following DARPA call from Mike Draugelis, our man in Lockheed Martin:

Machine learning – the ability of computers to understand data, manage results, and infer insights from uncertain information – is the force behind many recent revolutions in computing. Email spam filters, smartphone personal assistants and self-driving vehicles are all based on research advances in machine learning. Unfortunately, even as the demand for these capabilities is accelerating, every new application requires a Herculean effort. Even a team of specially-trained machine learning experts makes only painfully slow progress due to the lack of tools to build these systems.

The Probabilistic Programming for Advanced Machine Learning (PPAML) program was launched to address this challenge. Probabilistic programming is a new programming paradigm for managing uncertain information. By incorporating it into machine learning, PPAML seeks to greatly increase the number of people who can successfully build machine learning applications and make machine learning experts radically more effective. Moreover, the program seeks to create more economical, robust and powerful applications that need less data to produce more accurate results – features inconceivable with today’s technology.

And here is the call abstract:
The goal of the PPAML program is to advance machine learning by using probabilistic programming to 1) dramatically increase the number of people who can successfully build machine learning applications, 2) make machine learning experts radically more effective, and 3) enable new applications that are impossible to conceive of using today’s technology. In support of this overarching goal, PPAML has a number of sub-goals. Specifically, the sub-goals are 1) to make machine learning model code shorter, 2) to reduce development time, 3) to facilitate the construction of richer models, 4) to require lower levels of expertise in building machine learning applications, and 5) to support the construction of integrated models.

The GraphLab Workshop - Why Should You Care?

2013-04-10T10:25:00.000-07:00

Everyone knows that one of the hottest topics today is big data analytics. The GraphLab workshop is a "trade show" for all the significant graph analytics and graph database solutions. In one day you could learn more about the following systems (a preliminary list!):

Featured Projects

	Google’s Pregel is their Bulk Synchronous graph framework. Prof. Vahab Mirrokni is going to give an oral talk about graph processing @ Google.
	Apache Giraph is the open source equivalent system to Google’s Pregel. Dr. Avery Ching, one of Giraph contributors, will give a talk about large scale graph processing @ Facebook.
	Dr. Pankaj Gupta, the creator of Cassovary Graph Processing system @ Twitter will give a talk about Who To Follow (WTF) service in Twitter.
	Naiad is a parallel data flow framework from Microsoft with the focus of incremental computation. Dr. Derek Murray from Microsoft Research will present Naiad.
	Intel GraphBuilder is a software for creating graphs out of raw data, utilizing Hadoop for parallel graph creation. Dr. Theodore Willke from Intel Labs will present Intel Labs work in this domain.
	GraphLab is CMU+UW open source graph processing system, which supports both bulk synchronous parallel as well as asynchronous computation. Prof. Carlos Guestrin will present the latest GraphLab project.
	Allegro Graph is a high performance graph database with RDF support. Jans Aasman, the CEO of Franz, will give a demo of their newest graph database.
	Combinatorial BLAS is a distributed memory parallel graph library from LBNL/UCSB. Dr. Aydin Buluc will present comb-BLAS.
	Grappa is a distributed graph processing framework using commodity processors, from The University of Washington. Prof. Mark Oskin will present Grappa.
	Presto is a distributed framework for speeding up R computations by HP Labs. Shivaram Venkataraman from Bekreley and Kyungyong Lee will present Persto.
	Titan is a distributed graph database. Dr. Matthias Broecheler will present Titan.
	Neo4j is an open source distributed graph database in Java. Alex Averbuch from neo4j will present neo4j.
	Infinite Graph from Objectivity is a distributed graph database.
	DEX is a high performance and scalable graph database system. Norbert Martinez will present DEX.
	YarcData, a Cray spinoff is creating customized hardware solutions for ultra fast graph processing.
	Systap LLC is a startup working on speeding up graph algorithms using GPUs. Bryan Thompson from Systap will present preliminary results of applying the gather apply scatter model on GPU.
	Linked Data Benchmark Council (LDBC), a new EU FP7 project that aims to establish industry cooperation on graph database benchmarks, benchmark practices and benchmark results. Dr. Alex Averbuch (Neo Technologies), Norbert Martinez (Polytechnic University of Catalonia) and Dr. Andrey Gubichev (Technical University of Munich) will present LDBC.

Other notable talks at the GraphLab workshop:

	Trifacta is the hottest bay area startup out there, started by Prof. Joe Hellerstein from Berkeley and Prof. Jefferey Heer from Stanford. Prof. Joe Hellerstein will talk about Productivity for Data Analysts: Visualization, Intelligence and Scale.
	Dr. Lei Tang from Walmart Labs will talk about adaptive user segmentation for collaborative filtering.
	Alpine Data Labs is a Greenplum spinoff focusing on big data analytics. Seven Hillion will describe a case study of big data analytics on top of Hadoop.

Stay tuned - additional talks and demos are going to be added soon!

Facebook graph benchmark system

2013-04-07T13:30:00.000-07:00

I just heard from Carlos Guestrin about a new graph benchmark system from Facebook called LinkBench. I will be happy to hear when anyone tries it out...

Additionally, I got from Nilesh Jain from Intel Labs a link to LDBC an EU project for promoting graph benchmarks in industry. I was not aware of this project, but they are organizing the GRADES workshop I previously wrote about. And guess who is giving the keynote talk at the GRADES workshop? You may have guessed right - Carlos Guestrin is going to talk about GraphLab. The GRADES workshop will take place June 23rd in NY.

Insider ML Jobs

2013-04-07T07:49:00.000-07:00

In this blog post I will publish some open ML positions relating to big data analytics I got from my contacts. Those positions are not public yet and are published first in this blog.

PhD in CS, Bio-informatics, EE, physics, Statistics post doctoral fellow in biomedical informatics for 1 year. Emphasis of applications of Big Data to medicine. The fellow will be involved in projects which mine the electronic health record in of the Veterans Affairs system.

For details contact Alon Ben-Ari, MD, department of anesthesiology VA Puget Sound Seattle, Washington.

alon.benari@gmail.com

Stay tuned - more jobs to be posted soon..

Spotlight: Blaze C++ math library

2013-04-04T09:31:00.000-07:00

My collaborator Yucheng Low, asked me to take a look at Blaze math library. I did a quick review and here are my findings.

Blaze is an interesting effort with relatively easy programming interface (see for example CG code: http://code.google.com/p/blaze-lib/wiki/Getting_Started under "A complex example").

The main guy behind the software is Klaus Iglberger, a PhD from germany. Two papers were published about Blaze:

K. Iglberger, G. Hager, J. Treibig, and U. Rüde: Expression Templates Revisited: A Performance Analysis of Current Methodologies(Download). SIAM Journal on Scientific Computing, 34(2): C42--C69, 2012
K. Iglberger, G. Hager, J. Treibig, and U. Rüde: High Performance Smart Expression Template Math Libraries (Download). Proceedings of the 2nd International Workshop on New Algorithms and Programming Models for the Manycore Era (APMM 2012) at HPCS 2012

Regarding performance, at least for the tested primitives they have very good performance. It seems they work very well for small matrices (less than 100 width) even relative to MKL. For larger matrices have performance similar to MKL. The performance tests do not cover sparse matrices (only dense).

What is missing IMHO, is an algorithmic suite like linear solvers, svd etc. that exists Eigen. So currently Blaze focuses mainly on matrix vector operation.

It seems Blaze is using a single core implementation (they do not exploit parallelism).

Overall, it seems like a very interesting project to keep track of. Once it supports some additional functionality I would consider using it.

To dig a little dipper, I sent some questions to Klaus Iglberger, who was very kind to promptly replay:

> We were looking for a good math library to replace Eigen and we liked Blaze API. But we still have some missing functionality I wanted to ask you about.

We released the Blaze library only recently, in August 2012. Therefore Blaze is obviously much younger than Eigen and cannot compete in terms of features. Currently it can only compete in terms of performance (it seems to be the most efficient C++ math library for many operations) and in terms of software architecture and design. The software design and architecture is one of our personal interests will therefore always play a major role in the development of Blaze. However, due to that effort, I feel that Blaze can be used more naturally than the other C++ math libraries (including Eigen).

Since you are asking about features, let me give you an idea of our current roadmap. We are currently working on views (which you can for instance use to work on submatrices, extract parts of the result from vectors and matrices, etc.), special purpose matrices (banded matrices, upper and lower triangle matrices, etc.) and shared memory parallelization. These will be the next big features, starting with views in Blaze 1.2.

Whereas in direct comparison Blaze cannot compete in the total number of features, Blaze still offers a small number of unique features. The probably most important is the support of the Intel MIC architecture (Xeon Phi). Second is the support of the AVX instruction set, that is still not available in most other C++ math libraries. Third, Blaze is probably the only library that allows a completely hierarchic nesting of matrix and vector data types without performance penalties. For instance, you can define block structured matrices very conveniently:

typedef CompressedMatrix< DynamicMatrix<double,rowMajor>, rowMajor> BlockStructuredMatrix;

BlockStructuredMatrix A, B, C;
// … Initializing the matrices
C = A * B;

In this matrix multiplication you can still count on every single matrix multiplication to be executed at maximum performance (see also the answer to your third question). And last but not least, with the introduction of views, Blaze will offer an extremely versatile feature to restrict the computation to the "parts" you are interested in:

DynamicMatrix<double,rowMajor> A, B;
DynamicVector<double,columnVector> x;

// Restricts the computation of the matrix multiplication to the fourth column and still considers the most efficient way
// to compute the result although both matrices are stored in a row-wise fashion.
x = column( A * B, 4 );

> 1) Is there a plan to support sparse matrix algorithms like solving a linear system, eigen decomposition etc.

We currently don't plan to extend our linear system solvers, but hope that they can be added easily based on the data structures that we provide.

> 2) What is the level of support for parallelism? Namely, is the library fully serial or do you have some support for parallelism when there are multiple cores.

Until now, Blaze is completely serial, except for the vectorization (which is of course also a level of parallelization). So unfortunately, currently a single operation can only use a single core. But, as already stated, we are currently working on shared memory parallelization, but it will take some time until we release this feature.

> 3) According to the performance plots, on large matrices blaze performance aligns with MKL. Is there some mechanism which sends the computation to MKL once the problem is big enough and otherwise uses blaze code?

Blaze tries to detect several characteristics about the involved matrices. One of these characteristics is the size, which is used to determine which algorithm is most beneficial for performance. Whereas the MKL offers by far the best performance for large matrices, for small matrices the performance is less favorable due to optimizations that only work well for large matrices and therefore cause a performance penalty for small matrices. Therefore Blaze provides a couple of special algorithms tailored for small matrices (for instance, these algorithms don't use blocking strategies and use the data a little differently). The threshold for this algorithm switching can be configured in one of the configuration files: blaze/config/Threshold.h. With these you can tune Blaze to a specific target platform.

> 4) Is there support for serialization for writing and loading matrices from file?

We unfortunately neglected the support for writing to file and loading from file a little. Currently, only the DynamicVector class supports this feature. The member function you can use are called 'read' and 'write', respectively. However, I have added this to our list of features for the next release, since this will not take too much time to implement.

> Thanks a lot for your time!

You're very welcome. Please don't hesitate to contact me again if you have further questions (or possible feature requests) or if you have suggestions of how to improve Blaze. Hopefully you consider Blaze for your work, even if some features are currently missing. Please keep me posted on your decision.

The 2nd GraphLab workshop is coming up!

2013-03-27T03:04:00.000-07:00

An update: Just got a limited number of discount codes for this blog readers. The first few to email me will get 30% discount, in addition to the early bird rate!!

Following the great success of the first GraphLab workshop, we have started to organize this year event, in July at the bay area. To remind you, last year we wanted to organize a 15-20 people event, which eventually got a participation of 300+ researchers from 100+ companies.

The main aim of this year workshop is to bring together top researchers from academia, as well as top data scientists from industry with the special focus of large scale machine learning on sparse graphs.

The event will take place Monday July 1st, 2013 in San Francisco. Early bird registration is now open!

Preliminary agenda

A (preliminary) list of our program committee:

Deepak Agarwal, LinkedIn
John Mark Agosta, Toyota InfoTechnology Center USA
Alex Averbuch, Neo4j
Eric Bieschke, Pandora Internet Radio
Jim Blomo, Yelp!
Mauricio Breterniz, AMD
Matthias Broecheler, Auerelius
Igor Carron, Nuit Blanche & Space Engineering Research Center
Avery Ching, Facebook
Jike Chong, CMU SV Campus
Brad Cox, Technica Corporation
Yogesh Dalal, Ebay
Ranjit Desai, Adobe
Ted Dunning, MapR
Michael Draugelis, Lockheed Martin Corporation
Frank Elliot, Opera Solutions
Baldo Faieta, Adobe
Hulya Emir-Farinas, Greenplum
Carlos Guestrin, University of Washington
Andy Harbick, Rosetta Stone
Tamir Hazan, Toyota Technical Institute Chicago
Steven Hillion, Alpine Data Labs
Nilesh Jain, Intel Labs
Lee Jones, Cisco
Nick Kolegraff, Rackspace
Edo Libery, Yahoo! Labs
Ben Lorica, O'Reilly
Michael Mahoney, Stanford
Norbert Martinez, Sparsity Technologies
Charles Martin, Gerson Lehman Group
Vahab Mirrokni, Google Research
Ash Munshi, Knobout Inc.
Jan Neumann, Comcast
Andrew Nystrom, Thomson Reuters
Josep Lluís Larriba Pey, Univirsitat Politecnica De Catalunya
Nikolaos Vasiloglou II, Ismion
Udi Weinsberg, Technicolor Labs
Joel Welling, Pittsburgh Supercomputing Center
Ted Willke, Intel Labs
Josh Wills, Cloudera
Joshua Vogelstein, Duke
Lei Tang, Walmart Labs
Bryan Tompson, Systap
Tao Ye, Pandora Internet Radio
Nezih Yigitbasi, Intel Labs

A preliminary list of our sponsors:

The GraphLab workshop is co-sponsored by the Linked Data Benchmark Council (LDBC), a new EU FP7 project that aims to establish industry cooperation on graph database benchmarks, benchmark practices and benchmark results. A recommended event is the SIGMOD GRADES workshop, June 23rd in NY.

Twitter WTF (Who to Follow) Paper

2013-03-20T12:02:00.000-07:00

I got the following interesting paper from my collaborator Aapo Kyrola:
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. WTF: The Who to Follow Service at Twitter. Proceedings of the 22th International World Wide Web Conference (WWW 2013), May 2013, Rio de Janeiro, Brazil.

It details Twitter "Who to Follow" recommendation service. In a nutshell Twitter uses two algorithms: an egocentric random walk (personalized pagerank) and SALSA which is a bipartite random walk (similar to HITS algorithm).

In terms of infrastructure they use Twitter Cassovary graph processing system, on top of a single multicore machine, which is rather surprising considering Twitter graph size. Anyway this shows that proper efficient implementation on a single multicore machine can scale to very large models.

Spotlight: Large Scale Distributed Deep Networks

2013-03-17T21:52:00.002-07:00

I got from Liu from Tencent, the following paper from Google:
Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, and Andrew Y. Ng Large Scale Distributed Deep Networks, NIPS 2012: Neural Information Processing Systems, Lake Tahoe, Nevada, United States, December, 2012.

It uses a distributed implementation of SGD/LBGFS for training deep networks. It is one of the largest ML deployments I have seen so far: up to 10K cores, 5K machines. In a nutshell they factorize the problem into regions, run SGD in each region separately and then use a central server to merge the model from the different regions. They also support asynchronous computation of the different nodes.

And they did not fail to mention GraphLab :-)

We considered a number of existing large-scale computational tools for application to our problem, MapReduce [24] and GraphLab [25] being notable examples. We concluded that MapReduce, designed for parallel data processing, was ill-suited for the iterative computations inherent in deep network training; whereas GraphLab, designed for general (unstructured) graph computations, would not exploit computing efﬁciencies available in the structured graphs typically found in deep networks.

I am sure I got their meaning - if anyone knows let me know.

A nice collaborative filtering tutorial "for dummies"

2013-03-05T03:42:00.001-08:00

I got from M. Burhan, one of our GraphChi users from Germany, the following link to an online book called: A Programmer's Guide to Data Mining.

There are two relevant chapters that may help beginners understand the basic concepts.
The first one of them is Chapter 2: Collaborative Filtering and Chapter 3: Implicit Ratings and Item Based Filtering.

Intel Labs report on GraphLab vs. Mahout

2013-03-05T00:21:00.000-08:00

I have some very interesting news to report. I got from Nezih Yigitbasi, Intel Labs, the following graph:

It compares Mahout vs. Distributed GraphLab on the popular task of matrix factorization using ALS algorithm (alternating least squares) on Netflix data. The bottom line is that GraphLab is about x20 faster than Mahout.

And here is the exact experiment setup, I got from Nezih:

N is the number of ALS iterations, D is the number of latent factors. The experiments have been conducted on a 16 node cluster.
We start GL as mpirun -hostfile ~/hostfile -x CLASSPATH ./als –ncpus=16 --matrix hdfs://host001:19000/user/netflix --D=$LATENT_FACTOR_COUNT --max_iter=$ITER_COUNT --lambda=0.065 --minval=0 --maxval=5
To run mahout ALS, we use the factorize-netflix.sh script under the examples directory. It should be run as ./factorize-netflix.sh /path/to/training_set/ /path/to/qualifying.txt /path/to/judging.txt
In our test cluster we have 16 machines each with 64GB of memory, 2 CPUs (Intel(R) Xeon(R) CPU E5-2670 @ 2.60GHz [8 cores each]) and 4 x 1 TB HDDs. The machines communicate over a 10Gb Ethernet interconnect.
The Netflix dataset has been splitted into 32 equally sized chunks and then put into HDFS.