Social features on this blog

The readers of this blog can now:

1. Easily subscribe to the RSS feed with their reader of choice [left panel].
2. Decide to become a visible "follower" of this blog [left panel].
3. Rate each blog entry from 1 to 5 stars [end of each post].

I would be particularly happy to see people rating the posts. It's less informative than writing comments but still it's very good feedback for me.

Thanks!

Vapnik's picture explained

This is an extremely geek picture! :) Let's try to explain it:

First of all, as many of you know, the gentleman in the picture is Prof. Vladimir Vapnik. He is famous for his fundamental contributions to the field of Statistical Learning Theory, such as the Empirical Risk Minimization (ERM) principle, VC-dimension and Support Vector Machines.

Then we notice the sentence in the board: it resembles the famous "All your base are belong to us"! This is a piece of geek culture that emerged after a "broken English" translation of a Japanese video game for Sega Mega Drive .



Wait, but they replaced the word "Base" by "Bayes"!?
Yes, that Bayes, the British mathematician known for the Bayes' theorem.
Okay, seems fair enough, we are dealing with people from statistics...

By the moment we think things can not get more geeky, we realize there is scary inequality written on the top of the white board:

My goodness, what's this?! Okay, that's when things get really technical:
This is a probabilistic bound for the expected risk of a classifier under the ERM framework. In simple terms, it relates the classifier's expected test error with the training error on a dataset of size l and in which the cardinality of the set of loss functions is N.
If I'm not mistaken, the bound holds with probability (1 - eta) and applies only to loss functions bounded above by 1.

Sweet! Now that we got the parts, what's the big message?

Well, it's basically a statement about the superiority of Vapnik's learning theory over the Bayesian alternative. In a nutshell, the Bayesian perspective is that we start with some prior distribution over a set of hypothesis (our beliefs) and we update these according to the data that we see. We then look for an optimal decision rule based on the posterior distribution.
On the other hand, in Vapnik's framework there are no explicit priors neither we try to estimate the probability distribution of the data. This is motivated by the fact that density estimation is a ill-posed problem, and therefore we want to avoid this intermediate step. The goal is to directly minimize the probability of making bad decision in the future. If implemented through Support Vector Machines, this boils down to finding the decision boundary with maximal margin to separate the classes.

And that's it, folks! I hope you had fun decoding this image! :)

Computer Vision vs Computer Graphics

If I had to explain what computer vision is all about, in just one snapshot, I would show you this:




Computer Graphics algorithms go from the parameter space to the image space (rendering), computer vision algorithms do the opposite (inverse-rendering). Because of this, computer vision is basically a (very hard) problem of statistical inference.
The common approach nowadays is to build a classifier for each kind of object and then search over (part of) the parameter space explicitly, normally by scanning the image for all possible locations and scales. The remaining challenge is still huge: how can a classifier learn and generalize, from a finite set of examples, what are the fundamental characteristics of an object (shape, color) and what is irrelevant (changes in illumination, rotations, translations, occlusions, etc.).
This is what is keeping us busy! ;)

PS - Note that changes in illumination induce apparent changes in the color of the object and rotations induce apparent changes in shape!

Stationary Features - Google Tech Talk

François Fleuret, my PhD advisor, recently gave a talk about object detection at Google (Zurich offices).
You can now see it online:




If you wonder where my research will try to extend the work done so far, just go to minute 45:30!

Machine Learning Summer School

Held in Ile de Ré (France), 1-15th September, this school counted with some famous names within the Machine Learning and Artificial Intelligence communities: Rich Sutton (co-author of the widely adopted book on Reinforcement Learning), Isabelle Guyon (co-author of the first paper on Support Vector Machines) and Yann LeCun (known for the convolutional neural network, energy based models and the DjVu image compression technique).

You can check the (almost) complete list of lecturers here. I found the course given by Shai Ben-David, on the Theoretical Foundations of Clustering" quite interesting and intriguing. Clustering seems to be *really* lacking solid theoretical support, which is surprising, given the importance of the problem. Some atempts are being done to axiomatize it, but there are a lot of open questions: what exactly is the class of clustering algorithms? how can you compare different clustering algorithms? why is a partition better than other?
Hope to see more developments in this area in the coming years.

ICVSS 2008

Last week I attended the International Computer Vision Summer School in Sicily, Italy. The main topics were Reconstruction and Recognition. I think the quality of the lectures, organization and location were all quite good, therefore I would recommend it to other PhD students.

Here is a short summary of some of the things we heard about:

Andrew Zisserman (Oxford, UK) - gave an overview of object recognition and image classification, with focus on methods that use "bag of visual words" models. Quite nice for newcomers like me!

Silvio Savarese (UIUC, USA) - talked about 3D representations for object recognition. There is actually a Special Issue of the "Computer Vision and Image Understanding" on the topic at
http://vangogh.ai.uiuc.edu/cviu/home.html

Luc Van Gool (ETH Zurich, Switzerland) - Lots of cool and fancy demos about 3D reconstruction. They are starting to use some recognition to help reconstruction (opposite direction of S. Savarese).

Stefano Soatto (UCLA, USA) - gave an "opinion talk" on the foundations of Computer Vision and how it can be distinguished from Machine Learning. I would have to read his papers to understand better, but he seems to claim that the existence of non-invertible operations such as
occlusions would support the need for image analysis instead of just "brute-force machine learning".

We also had Bill Triggs (CNRS) talking about human detection, Jan Koendrick (Utrecht, Netherlands) on "shape-from-shade" and a few tutorials touching stuff as diverse as: SIFT, object tracking, multi-view stereo and photometric methods for 3D reconstruction or
randomized decision forests.


To summarize, I think the message was:

- Traditionally, recognition uses lots of Machine Learning but models keep few 3D information about objects;
- Traditionally, reconstruction uses ideas from geometry, optics and optimization but not learning;
- The future trend is to merge them: use 3D reconstruction to help in recognition tasks and use recognition to help in 3D reconstruction.

Moved to Switzerland

Since the 1st of July, I am a PhD student at Idiap Research Institute and the Ecole Polytechnique Fédérale de Lausanne.
I am working in Machine Learning and Computer Vision under the supervision of Dr. François Fleuret.

Generating all possible pictures

Think of an image of 800 x 600 pixel and 24 bit of color (8 bit per each RGB component). Its trivial binary representation is a sequence of 11520000 bits (800 x 600 x 24) and we can think of each picture as being a natural number.

Imagine now that we write an computer program that generates all these pictures one by one, incrementing the natural number by one in each round.

Running this algorithm for enough time you would eventually get:

- a picture of your face
- a picture of you in the Moon
- a picture of you with Marlin Monroe and James Dean
- pictures of ancient Earth, with dinosaurs
- pictures of all the paintings of Leonardo da Vinci, Van Gogh or Picasso
- pictures of all the pages of Shakespeare's writings
- pictures of proofs of all relevant mathematical theorems (already proved or not)
- pictures of all great music compositions (already written or not)
- pictures of Microsoft Office and Windows source code
- pictures/printscreens of all pages in the World Wide Web, including all the versions of Wikipedia


Warning: don't do this at home unless you can wait for some billion years between each pair of interesting pictures you would get!

Still, it's interesting to realize that you can compress all the world's information to a short and trivial program, all you have to do is add enough useless data to it!

Monkey with robotic arm

I'm not sure it's recent news, because there is a public release from as back as 2005, but I just came across this video of a monkey eating using a robotic arm directly controlled by his brain. Researchers are from the Pittsburgh University.

Really impressive, although probably a bit tough for the monkey.

The amazing intelligence of crows

In this 10min TED talk, Joshua Klein talks about crows and how they are incredibly good learners.



They seem to have a powerful memory, use vision effectively, have problem solving skills, use tools and even learn from examples of other crows. I guess AGI is more than achieved at "crow-level Artificial Intelligence"!!