Benchmarking Java Linear Algebra Libraries for BIGS

I think we all agree in that we need a standard, efficient and easy way of performing linear algebra operations in BIGS. Not necessarily parallelized operations but operations performed in each worker (even in one core of each worker) like multiplying a pair of matrices or computing the norm of a matrix.

It is truth that we previously used JAMA, in the BIGS' K-Means for example. But recent benchmarks made over K-Means by Raúl show that the linear algebra operations being made are a bottleneck: 

en las pruebas, con unos 1000 data items de mnist, comparo los métodos norm2  y minus de Jama con implementaciones "straight-forward"
norm2 (straight-forward) 55.00ms
norm2 (jama)                48.99sec
minus (straight-forward) 9.00ms
minus (java)                 87.00ms

Having this in mind we did an evaluation of some JAVA linear algebra libraries, taking into account the following factors:

• Active development
• Ease of usage
• Speed
• Portability
• License

Looking for something "Bueno, bonito y barato" by instruction of El Comandante Raúl.

As far as I know they're all equally "portable" and they all have JavaDocs. The speed here is measured with respect to the straight-forward implementation (the straight-forward implementation has a speed of 1.0 and corresponds to using fors and native operations in JAVA), i.e. the speed tells how much times slower (or faster if less than 1) it ran (on average over 10 runs) with respect to the straight forward implementation (here the smaller the better). The speed measure shown is an a
verage over runs with different matrix sizes (ranging from 1000x1000 to 10000x10000), so you would expect a linear increase in this measure as you go up by one order of magnitude in the size of the matrices used.

JAMA

• Last release date : 09/11/2012
• Ease of usage : Method's names are pretty much what you would expeect (plus, minus, times, etc...). The JavaDoc is rather short and kind of uninformative. (No muy bonito)
• Licence : "Released to the public domain" (Barato)
• Speed in substraction : (Approx.) 11.0
• Speed in frobenius norm : (Approx.) 17.0

EJML

• Last release date : 04/12/2012
• Ease of usage : Method's names are pretty much what you would expeect (plus, minus, times, etc...). There's a mapping between some MATLAB commands and the EJML methods. And has many useful linear algebra operations already implemented. (Bonito)
• Licence : LGPL (Barato)
• Speed in substraction : Around 3.5 (Más o menos bueno)
• Speed in frobenius norm : Around 7.0

Colt

• Last release date : 10/09/2004
• Ease of usage : There's a bit of work involved in implementing simple things as the developer must adapt to a special "operations framework" proposed by the library, i.e. it is not SO straightforward to do things like sum, substract or norms.
• Licence : Copyrighted.
• Speed in substraction : Around 0.6, i.e. faster than s.f.
• Speed in frobenius norm : Around 1.3

There's already a benchmark of all this (and more) libraries here, however it was made by the author of EJML so it was not that thrusthwortly.

News: Big Data R&D Initiative

Les comparto nuevamente esta noticia, que ya habia compartido por correo, para reactivar el blog. Esta noticia  me llamo mucho la atención debido a la importancia que el gobierno de E.E.U.U. le esta dando a abordar la investigación desde la perspectiva de Big Data involucrando las principales instituciones de investigación y proporcionando recursos para ello. Igualmente en esta nota esta la noticia, la convocatoria para los tipos de proyectos y la presentación oficial de la iniciativa.

Obama Administration Unveils $200M Big Data R&D Initiative

http://www.cccblog.org/2012/03/29/obama-administration-unveils-200m-big-data-rd-initiative/

FG:

Muy interesante! Esto significa que vamos por donde es y que nuestra intuición ha sido correcta. En una charla 'motivacional' que tuvimos hace algo más de un año hablamos de muchos de estos temas:

"Today, U.S. government agencies recognize that the scientific, biomedical and engineering research communities are undergoing a profound transformation with the use of large-scale, diverse, and high-resolution data sets that allow for data-intensive decision-making, including clinical decision making, at a level never before imagined. New statistical and mathematical algorithms, prediction techniques, and modeling methods, as well as multidisciplinary approaches to data collection, data analysis and new technologies for sharing data and information are enabling a paradigm shift in scientific and biomedical investigation. Advances in machine learning, data mining, and visualization are enabling new ways of extracting useful information in a timely fashion from massivedata sets, which complement and extend existing methods of hypothesis testing and statistical inference."

Esto nos pone en una posición privilegiada, pues ya llevamos un tiempo reflexionando sobre la problemática del BIg Data y hemos dado pasos importantes para consolidar una propuesta de investigación coherente que le apunta a varios frentes consistentes con este llamado del gobierno gringo. Por ejemplo en el área de biomédica  a muchos de los puntos:

"Big Data” is a new joint solicitation supported by the National Science Foundation (NSF) and the National Institutes of Health (NIH) that will advance the core scientific and technological means of managing, analyzing, visualizing, and extracting useful information from large and diverse data sets.  This will accelerate scientific discovery and lead to new fields of inquiry that would otherwise not be possible. NIH is particularly interested in imaging, molecular, cellular, electrophysiological, chemical, behavioral, epidemiological, clinical, and other data sets related to health and disease."

Esto es mucho más grande de lo que parece y seguramente va a generar un cambio dramático en muchas áreas y va a producir una oleada de investigación y desarrollo en ML, IR, cloud computing, visualization, etc.:

"In the same way that past Federal investments in information-technology R&D led to dramatic advances in supercomputing and the creation of the Internet, the initiative we are launching today promises to transform our ability to use Big Data for scientific discovery, environmental and biomedical research, education, and national security"

FG

Embarrassingly Parallel

I remember we found this expression in one of the papers we were studying during the Large Scale Machine Learning seminar. Here we have a definition, take from Wikipedia:

In parallel computing, an embarrassingly parallel workload (or embarrassingly parallel problem) is one for which little or no effort is required to separate the problem into a number of parallel tasks. This is often the case where there exists no dependency (or communication) between those parallel tasks.

Full article: http://en.wikipedia.org/wiki/Embarrassingly_parallel

Synthetic Training Data

One of the recent breakthroughs in computer vision was the use of synthetic data to train effective recognition systems. The most remarkable example is the work of Shotton et al. from Microsoft Research Cambridge, who trained the kinect human pose recognition system using more than a million of synthetic images, generated by rendering fake humans using 3D software.

That's perfectly possible mainly because the computer graphics industry has been working on generating 3D humans with realistic appearance for cinematographic productions and games. Clothing materials, hair, shapes and so on, are easily simulated in 3D. So, generating 3D human poses is a well establish and well understood procedure, and it make sense to generate synthetic data for this kind of problem.

What about medical images? Can we generate synthetic images simulating various medical conditions? It sounds a bit weird, right? Well, during the SIPAIM 2011 in Bucaramanga, Juan Antonio, one of the invited speakers from Spain, was giving a tutorial on how medical images are captured and generated, specially using Magnetic Resonance Imaging (MRI). This is also a very well known physical phenomenon that could be "simulated" using 3D software. Perhaps it's not a conventional 3D rendering procedure, because the intensities observed in an MRI scan are not responses to light, such as in conventional photography, but to magnetic resonance, as its name suggests.

Anyway, we could simulate various tissues and their responses to different machine configurations (intensity of the magnetic field, for instance) and render quite good MRI scans playing with tissue parameters. Then, we could produce a really large dataset of images with quite precise labelling at the pixel level, useful to train a recognition system for medical images. It could eventually work for xrays and other imaging modalities.

On the other hand, I wonder, if we can simulate that data, why can not we use the simulation function directly inside a learning algorithm? In other words, instead of generating the data to train a learning algorithm, the recognition system might also be ready to get that sort of simulation function as prior knowledge to make more effective predictions... does it make sense?

Big problems on Computer Science and Machine Learning

One of the most intriguing questions that Richard Hamming raised in his talk : "You and your research" (which I'm sure most of you've red) is : What are the most important problems in your area?
In one hand it is obvious that one can only focus on single well defined thing to do "great" stuff but in the other, and as Feynman states:

"... You have to keep a dozen of your favorite problems constantly present in your mind, although by and large they will lay in a dormant state. Every time you hear or read a new trick or a new result, test it against each of your twelve problems to see whether it helps. ..."

 So I decided to do a quick search about this and found a Wikipedia entry, a StackOverflow entry and a very interesting blog from Andreas Zwinkau, who describes an experiment : "Fantasy Research Lab" proposed by Philip Greenspun.
The Fantasy Research Lab consists of

 " ... [you] pretending that you are the lab director for computer science at a brand-new research university and to come up with a plan for how you'd populate your lab with projects."

 I thought it was an interesting experiment so I asked prof. Fabio to try it out, he rapidly came up with the interesting problem of Automatic Programming.
Now I'm interested in knowing the point of view of some very bright people like you,  but not only regarding the entire Computer Science field (which by itself could extend to Operating Systems, Software Engineering, Security, Databases, Hardware and so on as Microsoft Academic Search unveils) but also the more specific Machine Learning, Information Retrieval and HPC view which is central to this blog.

Thanks for reading ;)

Bag of Features and Image Matching

I think bag of features is a good enough representation for image matching. Of course, it is not perfect, it still requires a lot of improvements. But it still captures many ideas that the computer vision community was working on a few years before it started to be popular.

For instance, consider the problem of image matching using SIFT features. The procedure goes like this:

1. Extract SIFT features from image A and B.
2. Build a list of descriptors for each image.
3. For each descriptor in image A, compute the distance to all other descriptors in image B.
4. Identify the minimum distance. If it is less than a threshold, count one match.
5. Repeat.

At the end of the procedure, we have the total number of matches between both images. As you can imagine, this is sort of expensive if we are supposed to compute the number of matches for a large set of images (not just between two images). There is when the bag-of-features (BoF) appears and introduces an intermediate layer to save some computations: the dictionary of visual patterns. Actually, instead of saving those computations, the BoF moves the effort to an off-line stage, when we can wait (the dictionary construction).

Later, when we are indexing images with the BoF, we pre-compute the number of matches between the descriptors of one image and a reference dictionary. That's the histogram of occurrences between two images. Afterwards, for a query image, we can estimate the total number of matches with respect to a previously indexed image, just by computing the histogram intersection between both histograms.

In other words, if image A shows the pattern "x" 5 times and image B shows the same pattern 3 times, guess what would be the number of common matches if we look directly from image to image without using a dictionary: 3 (because at least 3 of the patterns in A would match with those patterns in B, approximately, i.e., the minimum between 5 and 3). Sounds familiar? Of course, this is an approximation to the matching process described above using the histogram intersection metric. However, it sort of mimics what was previously done.

Notice that one important parameter in the direct matching process is the threshold to accept or reject a match. This is sort of relaxed in the BoF approach by using k-means to group similar patterns. I think it's relaxed because there is no rejection when using BoF (unless it would be sparse enough). So, here is the trick: the larger the number of patterns in the dictionary, the smaller the number of matches, and possibly the better the approximation.

I would argue that when the number of patterns goes to infinite, it is equivalent to have a matching process where the threshold is set to zero (a match requires exact descriptors). This sort of justifies the use of large dictionaries when using BoF. And it becomes even more important when we would like to use it in large scale setups, just because when we introduce more images, it is likely that more unseen visual patterns appear in the collection.

Thoughts on Multimodal Fusion

There are some arguments that can help us build a discussion about multimodal learning (or retrieval):

• Assume we have a common unit of information from which we can observe two states (or modalities).
• Each modality is an incomplete view of the actual information there.
• Also, each observed modality is corrupted or noisy.
• Modalities are not independent, they have relationships, dependences, joint probabilities.
• Use multimodal fusion to complement the representation of the true information unit. To make it more accurate with respect to the original content. To reconstruct the missed information.

These are some ideas that we were discussing with prof. Fabio this morning. I think they make perfect sense from a global perspective, even though they require some formalization yet.