Insider ML Jobs

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

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!

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

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

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 efficiencies 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"

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

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.