Computer Blindness

When and why it is safe to cast floor/ceil result to integer

2012-01-05T20:05:00.000+04:00

Happy new year, ladies and gents! I am back, and the following couple of posts are going to be programming-related.

The C/C++ standard library declares floor function such that it returns a floating-point number:

     double floor (      double x );
      float floor (       float x );  // C++ only

I used to be tortured by two questions:

Why would the floor function return anything other than integer?
What is the most correct way to cast the output to integer?

At last I figured out the answer to both questions. Note that the rest of the post applies to the ceil function as well.

For the second point, I knew the common idiom was just type-casting the output:

double a;

int intRes = int(floor(a));  // use static_cast if you don't like brevity

If you’ve heard anything about peculiarities of floating-point arithmetic, you might start worrying that floor might return not exact integer value but $\lfloor a \rfloor - \epsilon$, so that type-casting is incorrect (assume $a$ is positive). However, this is not the case. Consider the following statement.

If $a$ is not integer and is representable as IEEE-754 floating-point number, than both $\lfloor a \rfloor$ and $\lceil a \rceil$ are representable within that domain. This means that for any float/double value floor can return a number that is integer and fits in float/double format.

The proof is easy but requires understanding of representation of floating-point numbers. Suppose $a = c \times b^q, c \in [0.1, 1)$ has $k$ significant digits, i.e. $k$-th digit after the point in $c$ is not null, but all the further ones are. Since it is representable, $k$ is less then the maximum width of significand. Since $a$ is not integer, both $\lfloor a \rfloor$ and $\lceil a \rceil$ have significands with the number of significant digits less then $k$. Rounding however might increase the order of magnitude but only by one. So, the rounded number’s significand fits in $k$ digits, Q.E.D.

However, this does not mean one can always type-cast the output safely, since, for example, not every integer stored in double can be represented as 4-byte int (and this is the answer to the question #1). Double precision numbers have 52 digit significands, so any integer number up to $2^{52}$ can be stored exactly. For the int type, it is only $2^{31}$. So if there is possibility of overflow, check before the cast or use the int64 type.

On the other hand, a lot of int’s cannot be represented as floats (also true for int64 and double). Consider the following code:

std::cout << std::showbase << std::hex

      << int(float(1 << 23)) << " " << int(float(1 << 24)) << std::endl

      << int(float(1 << 23) + 1) << " " << int(float(1 << 24) + 1) << std::endl;

The output is:

0x800000 0x1000000
0x800001 0x1000000

$2^{24}+1$ cannot be represented as float exactly (it is represented as $2^{24}$), so one should not use the float version of floor for numbers greater than few millions.

There are classes of numbers that are guaranteed to be represented exactly in floating point format. See also the comprehensive tutorial on floating-point arithmetic by David Goldberg.

Kinect Apps Challenge

2011-11-25T20:54:00.001+04:00

Graphics & Media Lab and Microsoft Research Cambridge have announced a contest for applications that use Kinect sensor. The authors of the five brightest apps will be funded to attend the 2012 Microsoft Research PhD summer school. I blogged about the last year's event in my previous post. Details of the contest are here.

I guess there's no need to explain what Kinect is. It is extremely successful combined colour and depth sensor by Microsoft. It is being distributed for killer price (≈$150) as an add-on for Xbox, although it is hard to imagine the range of possible applications. Controlling a computer only by gestures is considered as a primer of natural user interface. To name some applications beyond gaming, this kind of NUI is useful to help surgeons to keep their hands clean:

Kinect helps blind people to navigate through buildings:

For more ideas look at the winners of OpenNI challenge.

OpenNI is an open-source alternative to Kinect SDK. Its strong point is it is integrated with PCL, but beware that you cannot use it for the contest. Only Kinect for Windows SDK is allowed.

Kinect is probably the most successful commercial outcome from the Microsoft Research lab. MSR is unique because they do a lot of theoretical research there, and it is unclear if it is profitable for Microsoft to fund it. But the projects like Kinect reveal the doubts. I will post about MSR organization in comparison to other industrial labs in one of the later posts.

All the summer schools

2011-08-16T03:35:00.005+04:00

This summer I attended two conferences (3DIMPVT, EMMCVPR) and two summer schools. I know my latency is somewhat annoying, but it's better to review them now then never. :) This post is about the summer schools, and the following is going to be about the conferences.

PhD Summer School in Cambridge

Both schools were organized by Microsoft Research. The first one, PhD Summer School was in Cambridge, UK. The lectures covered some general issues for computer science PhD students (like using cloud computing for research and career perspectives) as well as some recent technical results by Microsoft Research. From the computer vision side, there were several talks:

Antonio Criminisi described their InnerEye system for retrieval of similar body part scans, which is useful for diagnosis based on similar cases' medical history. He also featured the basics of Random Forests as an advertisement to his ICCV 2011 tutorial. The new thing was using peculiar weak classifiers (like 2nd order separation surfaces). Antonio argued they perform much better then trees in some cases.
Andrew Fitzgibbon gave a brilliant lecture about pose estimation for Kinect (MSR Cambridge is really proud of that algorithm [Shotton, 2011], this is the topic for another post).
Olga Barinova talked about the modern methods of image analysis and her work for the past 2 years (graphical models for non-maxima suppression for object detection and urban scene parsing).

The other great talks were about .NET Gadgeteer, the system for modelling and even deployment of electronic gadgets (yes, hardware!), and F#, Microsoft's alternative to Scala, the language that combines object-oriented paradigm with functional. Sir Tony Hoare also gave a lecture, so I had a chance to ask him how he ended up in Moscow State University in the 60s. It turns out he studied statistics, and Andrey Kolmogorov was one of the leaders of the field that time, so that internship was a great opportunity for him. He said he had liked the time in Moscow. :) There were also magnificent lectures by Simon Peyton-Jones about giving talks and writing papers. Those advices are the must for everyone who does research, you can find the slides here. Slides for some of the lectures are available from the school page.

The school talks did not take all the time. Every night was occupied by some social event (go-karting, punting etc.) as well as unofficial after-parties in Cambridge pubs. Definitely it is the most fun school/conference I've attended so far. Karting was especially great, with the quality track, pit-stops, stats and prizes, so special thanks to Microsoft for including it to the program!

Microsoft Computer Vision School in Moscow

This year, Microsoft Research summer school in Russia was devoted to computer vision and organized in cooperation with our lab. The school started before its official opening with a homework assignment we authored (I was one of four student volunteers). The task was to develop an image classification method capable to distinguish two indoor and two outdoor classes. The results were rated according to the performance on the hidden test set. Artem Konev won the challenge with 95.5% accuracy and was awarded a prize consisted of an xBox and Kinect. Two years ago we used those data for the projects on Introduction to Computer Vision course, where nobody reached even 90%. It reflects not just the lore of participants, but also the progress of computer vision: all the top methods used PHOW descriptors and linear SVM with approximate decomposed χ² kernel [Vedaldi and Zisserman, 2010], which were unavailable that time!

In fact, Andrew Zisserman was one of the speakers. Andrew is the most cited computer vision researcher and the only person whose Zisserman number is zero. :) His course was on Visual Search and Recognition, including instance-level and category-level recognition. The ideas that were relatively new:

when computing visual words, sometimes it is fruitful to use soft assignments to clusters, or more advanced methods like Locality-constrained linear coding [Wang et al., 2010];
for instance-level recognition it is possible to use query expansion to overcome occlusions [Chum et al., 2007]: the idea is to use the best matched images from the base as new queries;
object detection is traditionally done with sliding window, the problems here are: various aspect ratio, partial occlusions, multiple responses and background clutter for substantially non-convex objects;
for object detection use bootstrapped sequential classification: on the next stage take the false negative detections from the previous stage as negative examples and retrain the classifier;
multiple kernel learning [Gehler and Nowozin, 2009] is a hot tool that is used to find the ideal linear combination of SVM kernels: combining different features is fruitful, but learning the combination is not much better than just averaging (Lampert: “Never use MKL without comparison to simple baselines!”);
movies are common datasets, since there are a lot of repeated objects/people/environments, and the privacy issues are easy to overcome. The movies like Groundhog Day and Run Lola Run are especially good since they contain repeated episodes. You can try to find the clocks on Video Google Demo.

Zisserman talked about PASCAL challenge a lot. During a break he mentioned that he annotated some images himself since “it is fun”. One problem with the challenge is we don't know if the progress over years really reflects the increased quality of methods, or is just because of growth of the training set (though, it is easy to check).

Andrew Fitzgibbon gave two more great lectures, one about Kinect (with slightly different motivation than in Cambridge) and another about continuous optimization. He talked a lot about reconciling theory and practice:

the life-cycle of a research project is: 1) chase the high-hanging fruit (theoretically-sound model), 2) try to make stuff really work, 3) look for the things that confuse/annoy you and fix them;
for Kinect pose estimation, the good top-down method based on tracking did not work, so they ended up classifying body parts discriminatively, temporal smoothing is used on the late stage;
“don't be obsessed with theoretical guarantees: they are either weak or trivial”;
on the simplest optimization method: “How many people have invented [coordinate] alternation at some point of their life?”. Indeed, the method is guaranteed to converge, but the problems arise when the valleys are not axis-aligned;
gradient descent is not a panacea: in some cases it does small steps too, conjugate gradient method is better (it uses 1st order derivatives only);
when possible, use second derivatives to determine step size, but estimating them is hard in general;
one almost never needs to take the matrix inverse; in MATLAB, to solve the system Hd = −g, use backslash: d = −H\g;
the Friday evening method is to try MATLAB fminsearch (implementing the derivative-free Nelder-Mead method).

Dr. Fitzgibbon asked the audience what the first rule of machine learning is. I hardly helped over replying “Never talk about machine learning”, but he expected the different answer: “Always try the nearest neighbour first!”

Christoph Lampert gave lectures on kernel methods, and structured learning, and kernel methods for structured learning. Some notes on the kernel methods talk:

(obvious) don't rely on the error on a train set, and (less obvious) don't even report about it in your papers;
for SVM kernels, in order to be legitimate, a kernel should be an inner product; it is often hard to prove it directly, but there are workarounds: a kernel can be drawn from a conditionally positive-definite matrix; sum, product and exponent of a kernel(s) is a kernel too etc. (thus, important for multiple-kernel learning, linear combination of kernels is a kernel);
since training (and running) non-linear SVMs is computationally hard, explicit feature maps are popular now: try to decompose the kernel back to conventional dot product of modified features; typically the features should be transformed to infinite sums, so take first few terms [Vedaldi and Zisserman, 2010];
if the kernel can be expressed as a sum over vector components (e.g. χ² kernel $\sum_d x_d x'_d / (x_d + x'_d)$), it is easy to decompose; radial basis function (RBF) kernel ($\exp (\|x-x'\|^2 / 2\sigma^2)$) is the exponent of a sum, so it is hardly decomposable (more strict conditions are in the paper);
when using RBF kernel, you have another parameter σ to tune; the rule of thumb is to take σ² equal to the median distance between training vectors (thus, cross-validation becomes one-dimensional).

Christoph also told a motivating story why one should always use cross-validation (so just forget the previous point :). Sebastian Nowozin was working on his [ICCV 2007] paper on action classification. He used the method by Dollár et al. [2005] as a baseline. The paper reported 80.6% accuracy on the KTH dataset. He outperformed the method by a couple of per cents and then decided to reproduce Dollár's results. Imagine his wonder when simple cross-validation (with same features and kernels) yielded 85.2%! So, Sebastian had to improve his method to beat the baseline.

I feel I should stop writing about the talks now since the post grows enormously long. Another Lampert's lecture and Carsten Rother's course on CRFs were close to my topic, so they deserve separate posts (I already reviewed basics of structured learning and max-product optimization in this blog). Andreas Müller blogged about the recent Ivan Laptev's action recognition talk on CVML, which was pretty similar to ours. The slides are available for all MSCVS talks, and videos will be shared in September.

There were also several practical sessions, but I personally consider them not that useful, because one hardly ever can feel the essence of a method in 1.5 hours changing the code according to some verbose instruction. It is more of an art to design such tutorials, and no one can really master it. :) Even if the task is well-designed, one may not succeed performing it due to technical reasons: during Carsten Rother's tutorial, Tanya and me spent half an hour to spot the bug caused by confusing input and index variable names (MATLAB is still dynamically typed). Ondrej Chum once mentioned how his tutorial was doomed since half of the students did not know how to work with sparse matrices. So, practical sessions are hard.

There was also a poster session, but I cannot remember a lot of bright works, unfortunately. Nataliya Shapovalova who won the best poster award, presented quite interesting work on action recognition, which I liked as well (and it is not the last name bias! :) My congratulations to Natasha!

The planned social events were not so exhaustive as in Cambridge, but self-organization worked out. The most prominent example was our overnight walk around Moscow, in which a substantial part of school participants took part. It included catching last subway train, drinking whiskey and gin, a game of ~~guessing~~ hallucinating names of each other, and moving a car from the tram rail to let the tram go in the morning. :) I also met some of OpenCV developers from Nizhny Novgorod there.

MSCVS is a one-time event, unfortunately. There are at least three annual computer vision summer schools in Europe: ICVSS (the most mature one, I attended it last year), CVML (held in France by INRIA) and VSSS (includes sport sessions besides the lectures, held in Zürich). If you are a PhD student in vision (especially in the beginning of your program), it is worth attending one of them each year to keep up with current trends in the vision community, especially if you don't go to the major conferences. The sets of topics (and even speakers!) have usually large intersection, so pick one of them. ICVSS has arguably the most competitive participant selection, but the application deadline and acceptance notification are in March, so one can apply to the other schools if rejected.

Google search by image

2011-06-25T11:27:00.004+04:00

Last week Google introduced Search by Image feature. There were a handful of web-sites that suggested content-based image retrieval in the Internet, but the quality was low, as I blogged earlier. I repeated the queries TinEye failed at, and Google image search found them both! It found few instances of Marion Lenbach (one of them from this blog, which means the coverage is large!), and I finally remembered the movie from the HOG paper: The Talanted Mr. Ripley.

So, from the quick glance Google finally accomplished what the others could not do for ages. Why did they succeed? There are two possible reasons: large facilities that allow building and storing large index efficiently, and a unique technology. The former is surely the case: it seems the engine indexed a large portion of the photos in the web. I cannot say anything about the technology: there is nothing about that among the Google's CVPR papers, so one need to do black-box testing to see which transformations and modifications are allowed.

Google seems to expand to the areas of multimedia web, even where the niche is already occupied. Recently they announced their alternative to grooveshark, the recommendation system for Music beta (the service is unfortunately available on invitation basis in the US only). The system is not based on collaborative filtering (only), they (also) analyse the content. I planned to investigate this area too, but given that it is becoming mature and thus not so alluring. I am eager to see if the service will succeed. After all, Buzz did not replace Twitter, and Orkut did not replace Facebook.

On structured learning

2011-04-26T02:20:00.003+04:00

This post is devoted to structured learning, a novel machine learning paradigm which may be used for solving different computer vision problems. For example, finding optimal parameters of graphical models is essentially a structured learning problem. I am going to give an introductory talk on structured learning for Dmitry Vetrov's graphical models class this Friday at 4:20 pm, so please feel free to drop by if you are in Moscow (the talk is to be in Russian).

Structured learning is basically a very general supervised learning setting. Consider the classification setting as a basic problem. One needs to find parameters of a function that maps a feature vector to one of the pre-defined class labels $\mathbb{R}^m \to \{c_1, c_2, \dots, c_K\}$. The fundamental property is the classes are unordered and orthogonal. The latest means the probabilities of objects classified as different labels are uncorrelated (some negative correlation is normal since strong classifying of an object as $c_i$ decreases the probability for rest of the labels).

Now consider regression, which is another supervised learning problem where feature vectors map to real values: $\mathbb{R}^m \to \mathbb{R}$. It might be considered a classification problem with infinite number of classes. There are two obvious flaws in this reduction. First, a training set is unlikely to have at least one example for each class. To overcome this one can quantize the codomain and train a classifier over a finite set of class labels. However, it leaves us with the second flaw: the method does not take into account correlation between the possible outcomes. The bins are ordered: the training features that correspond to neighbouring bins should be handled differently from those that correspond to distant bins. That's why some global methods (like linear regression) are used.

The similar situation is in the case of a structured outcome. In this case, one usually has a plenty of possible outcomes, but they are not independent. The techniques of structured learning are applicable when the outcomes have some underlying structure, and the elements of the structure have similar sets of features. Also, it should be possible to estimate how bad the prediction is (often in terms of incorrectly predicted elements), which is called structured loss. The methods allow small deviations from the ideal training outcome, which are possible e.g. because of noise, but penalize the substantial ones (just like regression!). The prediction function (parameters of which are tuned) can thus be formalized as a mapping $\mathbb{R}^{m \times l} \to \{c_1, c_2, \dots, c_K\}^l$.

The possible example is hidden Markov model learning, where the elements are emission potentials and transition potentials, and the loss can be defined as the number of wrong HMM outputs. According to the upper formalization, there are $l$ elements, each represented by $m$ features (in practice, $m$ can vary for different types of elements). Since the labels of transition elements are strictly defined by emission outputs, not every outcome is possible.

Another example of a structured prediction problem is natural language parsing. Given a sentence of a natural language, the corresponding parsing tree is to be constructed. Surprisingly, parsing trees could also be represented as high-dimensional vectors, with constraints applied. To summarize, structure prediction has outcome that is multivariate, correlated and constrained.

Ideally, the parameters of structured prediction should be tuned via likelihood maximization, but this turns out to be intractable due to the need of computing the partition function on each gradient optimization step. That's why the L²-regularized hinge loss is usually minimized. The prediction algorithm is represented as a scoring function over possible outcomes. The task of the learning algorithm is to find the parameters of the scoring function to make it return maximum values for the true outcomes on the training set, and low ones for the instances that are far from optimal. Given that, the margin between good and bad possible outcomes should be maximized (in terms of scoring function value).

You can learn more about structure learning from Ben Taskar's NIPS 2007 tutorial. See also our recent 3DIMPVT paper for an up-to-date survey of MRF/CRF training methods and their applications.

PS. I've installed MathJax equation engine into the blog. Seems to work, huh?

[CFP] GraphiCon-2011 and MSCVSS

2011-03-31T00:36:00.005+04:00

Our lab traditionally organizes GraphiCon, the major (and may be the only) conference in Russia specialized in computer graphics and computer vision. The conference is not very selective, still it has a decent community of professionals behind it. So, if you want to get a quality feedback on your preliminary work, or always wanted to visit Russia, consider submitting a paper by May, 16.

Special offer for young readers of my blog: If it is the place where you learned about the conference and decided to submit a paper, I'll buy you a beer during the conference. :) Consider it another social micro-event.

Another piece of news is primarily for undergrads and PhD students from Russia. Our lab and Microsoft Research organize another event this summer: Computer vision summer school. There are such lecturers as Cristoph Lampert and Andrew Zisserman, among others. Participation is free of charge, and accommodation is provided. Deadline is on April, 30. You should not miss it!

IEEE goes evil?

2011-03-07T23:01:00.007+03:00

In November, the IEEE released a new copyright agreement, that is to be signed by the authors of all papers published by the organization since January 2011. The main novelty is that the authors are not allowed to publish final versions of their papers on-line. Fortunately, we still may post the versions accepted for print (with post-review corrections), which is still great, indeed. You can find the FAQ concerning the new policy here.

It seems the IEEE realizes that nowadays there is almost no need in their printed materials and the digital library as search engines manage to find papers posted by their authors. No doubt that they do not want to restrict dissemination of scientific results, but that is a question of their survival as a major publishing organization. The worst is they use the drug-dealer strategy: first they organize great conferences and journals (the majority of top venues in my field are run by IEEE), and allow authors to re-publish anything on-line ("the first hit for free"), then cut it off. Yes, one still may post an accepted version, but who knows what is their next step?

The IEEE motivate their decision by preserving the value of their database: "the IEEE is better able to track usage of articles for the benefit of authors and journals". One can object that there are big and growing open-access databases like Mendeley, where all the statistics is open and refined (the personal info of users is known). Also, not all institutions have an access to the library. For example, my university (the largest one in Russia) does not. And I cannot afford to pay $25 per paper.

What can we do about that? Sure, it is impossible to stop publish in IEEE venues, although the community can find the way around, as was demonstrated by the founders of JMLR, now the major journal in machine learning, which was created to cancel the overhead of the commercial publishing model. Matt Blaze encourages the researchers not to serve as reviewers for IEEE. As for me, I'm too young (as a researcher) to be a reviewer. But it also has effect on me: I am now preparing a final version for the proceedings published by the IEEE, and I doubt if there is any use in improving my paper (even given a quality review), assuming that majority of researchers will use the accepted version and will never see the revised one.

UPD (Mart 14, 2011). I should have misunderstood the new policy at first, Blaze's post and IEEE terminology somehow misled me. The accepted paper means accepted for print by the IEEE, not the submitted for review. So, you still can use review results to correct the paper and post it on-line, then submit for publishing, where the formatting will probably be adjusted. So, any meaningful part could be reflected in the on-line version. I have corrected the post now, so it may seem weird.

The one about CERN

2011-02-28T23:02:00.000+03:00

About a month ago I visited CERN, arguably the most famous research organization in Europe. It is the place where the World Wide Web has been invented, and the home of the Large Hadron Collider. I was very excited about the trip, much like Sheldon Cooper. Here are some facts which were new to me:

... about CERN:

CERN was founded after the WWII by a bunch of European countries. They were exhausted by the war, and the only way to catch up with the USA and USSR in fundamental science was to join forces.
The original name was Conseil Européen pour la Recherche Nucléaire (European Council for Nuclear Research), which abbreviated to CERN. Later the name has been officially changed to European laboratory for particle physics, which is both more relevant and less fearful for the locals, however the brand CERN is used now even in official documents.
There are almost 3,000 full-time employees, but most of them are engineers and not scientists. There are a lot of visiting researchers though.
There are 20 member states now (primarily EU states), and 6 observer states (such as Russia and the USA).
CERN's annual budget is about € 1 billion, it is funded by the member states in proportion to their economical power, e.g. Germany gives 20% of the money.
The budget money are spent to infrastructure and support, all the individual experiments are funded by research groups and their universities.
In spite of the USA is not a member state, it leads on the number of researchers who work on CERN projects (more than thousand), second is Germany, third is Russia (yes, we still have a good shape in particle physics). It turned out that everybody at CERN spoke Russian, even the janitor. :)

... about the LHC:

It is in fact a circular tunnel of 27 km in circumference lying 175 m beneath the ground.
The tunnel was used before the LHC, it was build in 1983 for the Large Electron-Positron Collider. In 2008 it was upgraded to be able to accelerate heavy particles like protons to become the Large Hadron Collider (remind that proton and neutron are thousand times heavier than electron).
The tunnel is about 4 meters in diameter, one can walk there or ride a bike.
The tunnel encapsulates two small pipes for the particles that intersect at four points (to make the tracks' lengths equal, like in speed scating arenas). There are more then a thousand of electric magnet dipoles along the pipe. They are not that big as I imagined before.
It is nearly vacuum and zero temperature inside the tubes.
Proton beams are not generated inside the LHC. First, they are accelerated in the linear accelerator and almost reach the speed of light c. While the speed is rising, it becomes harder and harder to increase it since it cannot overcome the speed of light. Then they are accelerated in the small circular accelerator, and only after that they are injected into the LHC where during 40 minutes the beams are accelerated to speed as much close to c as possible.
When accelerated, the beams are being observed during 10 hours. They suffer about 10,000 collisions per second, about 20 pairs of protons collide each time. Since the speed is large, the energy of that collisions is enormous.
The collisions take place within special locations called detectors. We visited a control centre of one of them, ATLAS. A detector has multiple layers, each able to register certain kind of particles, like photons.
Ten thousand collision per second would yield really big amount of data, so only few of them are selected to be logged. I don't know how they select those collisions, machine learning might be used. :)
All the collected data are spread into servers all over the world. An authorized researcher may log in to the grid network and execute her script to analyse the data.

... about Higgs boson:

Higgs boson is a hypothetical particle, existence of which would prove the standard model of particle physics.
Higgs boson appears as a result of collision of two protons and large amount of energy. The protons in the LHC are accelerated enough to produce theoretically sufficient energy.
Higgs boson is very heavy and thus unstable. In theory, it decays into either four muons or two photons. So, if there will be two counter-directed light beams registered by the detector, this will be an evidence of the boson. See the picture below for example of likely detector output in case of the boson shows up.
Scientist say that if Higgs boson would not be detected, all the modern knowledge on particle physics will crush. They will be obliged to develop a new theory from scratch.
There are no published results that report on Higgs boson detection so far...

Don't you want to be a theoretical physicist now? =)

Art + Multimedia

2011-01-25T09:04:00.000+03:00

In December we visited a lecture about interaction between arts and sciences, namely between (primarily) visual arts and (again, primarily) multimedia studies (Russian page). The lecture was given by Asya Ablogina, who turned out to be a nice girl. Although she lacked any technical background, she was doing well. Surprisingly, there is a lot of artwork that exploits technical support in a witty manner, which I was unaware of, so the lousy stuff exhibited in the Moscow Museum of Modern Art is not everything one can do in this field!

The most interesting part was Asya's exposition of some masterpieces. Most of them were presented during 2009 Science as Suspense exhibit in Moscow (Russian). Nicolas Reeves is a famous Canadian architect, also known for his work on modelling biological systems. He used the output of biologically-inspired computer algorithms (such as genetic algorithms) to draw pictures. In Moscow he presented a project called ~~Marching~~ Floating Cubes: massive but light cubes float in the air. Their movements are controlled by tiny fans, although any little gust of wind can affect the movement. Each cube is equipped with an on-board computer, which helps to avoid collisions. The implemented algorithms are simple but stochastic, hence the behaviour is unpredictable. They are said to move like animal creatures. Here is the video:

A similar project was developed by Paul Granjon. He also tries to gift robots with animal behaviour. In the video below, robots are sexed, i.e. they are able to locate robots of the opposite sex and eventually end up in coitus. Another Paul's robot (the Smartbot, photo) creeps over the restricted space and always grumbles (just like Marvin!). I also enjoy the way Paul speaks:

The real idol in the sci-art community is Stelarc (see also his homepage, although it takes balls to get through the welcome page :). His talent is recognized by both scientists and artists (it is enough to mention he's an Honorary Professor of Arts and Robotics at Carnegie Mellon). He's best known for his experiments on his own body. For example, during a performance he allowed to control his body remotely over the Internet by muscle stimulation. Probably his favourite project is Prosthetic Head, which is in fact a 3D model of his own head. The head is learned from Stelarc's behaviour and speech, so it is able to communicate with people using colloquial information as well as non-verbal cues. It is interesting to try it in practice, but here is just a non-interactive demo video:

Stelarc is probably the only person on Earth who has three ears. In 2007 surgeons implanted an ear into his arm! It is not functioning now (just a piece of skin), but he plans to install an audio receiver into the ear and broadcast everything he hears over the Internet. I definitely recommend to look through his projects, there are decent ones.

Asya also presented her own works. She focus on different photographic techniques such as overexposure. Here are photos from her project Canvas of the Road compiled in a video. There is a play of words in Russian: the single word for canvas and road surface. On these photos car traces look like painter's strokes:

Another Asya's project is a short film series called Habitat. She showed only one episode with the title Habitat: MSU Main Building. The film was about a girl who is a PhD student in Moscow State University and described her place: a standard 8 sq.m. dorm room. The narrative was full of expressive epithets and metaphors about that awful room: the girl felt like in a cage, she also didn't like shared bathroom, etc. It's funny, because I live in a similar PhD student single room, and I'm quite happy with it, since I've been living 5 years in a shared room before. :)

The second lecturer, Vladimir Vishnyakov, presented his project called The Museum of Revived Photography. He used the photos of the XIX century to create image-based animation. The idea is technically simple: first segment people from the background, then use inpainting techniques to restore the background behind them, and animate the movements, but Vladimir referred to a programmer he works with as a real genius. In fact, all the stuff I post here varies from easy to moderately complex (except of Stelarc's projects), so you can do something similar too. The main problem is to come up with the concept. Come on then! ;)

Comic strip: Nerd's confession

2010-12-22T22:21:00.003+03:00

I continue sharing my Prague comic strips, since I have not been posting for a while. In fact, I was busy writing a paper, so this one may seem somehow connected. Disclaimer: There's nothing personal in the strip. Kids under 18 are not allowed. :)

The next post is going to be about multimedia technologies for art. Stay tuned!

Happy Thaknsgiving!

2010-11-26T10:30:00.004+03:00

Here is a comic strip by Ryan Lake that illustrates the concept of Russell's turkey. The idea is simply the induction does not always work the way you expect. There could be some factors, which did not have influence on the training data, yet changing the learned concept dramatically. We should thus keep in mind that machine learning (which is based on induction) is not the panacea.

Bertrand Russell is well-known for his metaphors. Probably the most famous one is Russell's teapot that aims to show how pointless is to believe in god.

Happy Thanksgiving!

PS. I am reading Animal Farm by George Orwell now, it is a great animal metaphor too.

Nice paper acknowledgement

2010-11-10T21:13:00.002+03:00

It turns out that not only in Russia PhD students could be underpaid so that they cannot afford food:

This is from Olga Veksler's paper "Graph cut based optimization for MRFs with truncated convex priors" from CVPR 2007.

Andrew seems to be a nice person. I should definitely ask Anton Osokin to introduce us on ocasion. =)

Papers, citations, co-authorship, and genealogy

2010-10-10T10:10:00.009+04:00

This summer I accidentally found out that there are two papers citing our CMRT 2009 paper. I was excited a bit about that since they were the first actual citations of me, so I even read those papers.

The first of them [Димашова, 2010] was published in Russian by OpenCV developers from Nizhny Novgorod. They implemented cascade-based face detection algorithm that used either Local Binary Patterns (LBP) or Haar features. The algorithm was released within OpenCV 2.0. They cite our paper as an example of using Random Forest on the stages of the cascade. However, they implemented the classical variation with the cascade over AdaBoost.

Another citation [Sikiric et al., 2010] is more relevant since it came from the road mapping community. They address the problem of recovering a road appearance mosaic from the orthogonal views to the surface. They contrast their approach with ours in the way that theirs do not employ human interaction. In fact, we need human input for recognizing road defects and lane marking, rectification is done in the previous stage, which is fully automatic.

The rest of the post is devoted to some interesting metrics and structures concerning citations, co-authorship and supervising students.

Citations

The number of citations is a weak measure of paper quality. We can also go further and estimate the impact of a journal or a particular researcher based on the number of citations. A generally accepted measure is the journal impact factor, which is simply the mean number of citations by paper published in the journal for some period in time. Individual researchers could be evaluated by the impact factor of the journals they published in, though it is considered as a bad practice. Another not-so-bad practise is h-index. By definition, one's h-index equals H if there are at least H citations of his top H papers¹. It has also been criticised widely.

So, citation-based scoring has a lot of flaws. But what can we use instead? Another interesting approach is introduced by ReaderMeter. They collect the information about the number of people who have added some paper to their Mendeley collections and compute something like h-index. Unfortunately, they recently excluded some papers from their database, so the statistics became less representative but more accurate.

Co-authorship and Erdős number

Paul Erdős was a Hungarian mathematician who published about 14 hundred research papers with 511 different co-authors. That's why he has a special role in bibliometrics. Erdős number is defined as a collaborative distance from a researcher to Erdős. More strictly, Wikipedia defines:

Paul Erdős is the one person having an Erdős number of zero. For any author other than Erdős, if the lowest Erdős number of all of his coauthors is k, then the author's Erdős number is k + 1.

My Erdős number is at most 7 (via Olga Barinova, Pushmeet Kohli, Philip H.S. Torr, Bernhard Schölkopf, John Shawe Taylor, David Godsil). To be honest, Erdős number system is primarily used for math papers. Even if we use the wider definition, it is not that beautiful, because there are not too many gates, e.g. all the vision community will probably connect to Erdős via the machine learning gate. Thus, the researchers who work on the edge will be closer. To illustrate this fact, David Marr probably had not any finite Erdős number during his lifetime (now he definitely has). So, we can introduce, say, Zisserman number for computer vision.² According to DBLP, Andrew Zisserman has 165 direct co-authors so far. Now, my Zisserman number is 3, David Marr's is 4 (via Tomaso Poggio, Lior Wolf, Yonatan Wexler).

The movie industry have their own metrics, which is the Bacon number (after Kevin Bacon). The distance is established 1 if two actors have appeared in a single movie. Someone tried to combine those two to the Erdős-Bacon number. For some person, it is just a sum of her Erdős and Bacon numbers. Of course, very few people have a finite Erdős-Bacon number, since one should both appear in a movie and publish a research paper (and it is still not sufficient). Often they are possessed by researchers who consulted the filming crew and accidentally were filmed. =) Erdős himself has this number 3 or 4 (depending on the details of definition), since he starred in N is a Number (1993) and his Bacon number is thus 3 0r 4.

The person with the probably lowest Erdős-Bacon number is Daniel Kleitman, an MIT mathematician, who has appeared in one of my favourite movies Good Will Hunting (1997) along with Minnie Driver, who collaborated with Bacon in Sleepers (1996). Since Kleitman has 6 joint papers with Erdős, his Erdős-Bacon number is 3.

Surprisingly, Marvin Minsky has his Erdős number (4) greater than his Bacon number (2), which he obtained via The Revenge of the Dead Indians (1993) and Yoko Ono. Another strange example is ~~the paedophile's dream~~ Natalie Portman. She has graduated from Harvard, saying she would rather "be smart than a movie star". That's my kind of a girl! A neuroscience paper [Baird et al., 2002] brought Natalie Hershlag (her real name) Erdős number of 5, and then she appeared in New York, I Love You (2009) along with Kevin Bacon, so she reached the same Erdős-Bacon number as Minsky, i.e. 6.

UPD (Mart 13, 2011). There is a totally relevant xkcd strip.

Scientific genealogy

Finally, I tell about what is known as scientific genealogy. Every grown-up researcher has a PhD advisor, usually one, while an advisor can have a lot of students. Let's just use the analogy with parents and children. We get a tree (or a forest) representing the historical structure of science. The mathematics genealogy project aims to recover this structure.

I tried to track my genealogy back. Unfortunately, I failed to find who was Yury M. Bayakovsky's PhD advisor. But if consider Olga Barinova my advisor, I am the 11th generation descendant of Carl Friedrich Gauß. Nice ancestry, huh?

The similar project exists for computer vision. There are 290 people in the base, though there are duplicates (I've found five Vitorio Ferrari's :). It seems strange that some trees have depth as big as 5 (e.g. Kristen Graumann and Adriana Quattoni are the 5th generation after David Marr), though vision is a relatively young field.

¹ Okay, take the supremum of the set if you want to stay formal
² It seems that Philip Torr has already used that number.

LidarK 2.0 released

2010-09-16T16:39:00.002+04:00

The second major release of GML LidarK is now available. It reflects our 3-year experience on 3D data processing. The description from the project page:

The LidarK library provides an open-source framework for processing multidimensional point data such as 3D LIDAR scans. It allows building a spatial index for performing fast search queries of different kinds. Although it is intended to be used for LIDAR scans, it can be helpful for a wide range of problems that require spatial data processing.

The API has been enriched with various features in this release. Indeed, it became more consistent and logical. New ways to access data (i.e. various iterators) are implemented. One can now find k nearest neighbours for any point, not just for one that belongs to the index. Since the data structure is a container, we've decided to parametrize it with template parameter. This decision is controversive: one does not need to cast tuples any more, but the code became clumsier and less portable, unfortunately.

The C++/MATLAB code is licensed free of charge for academic use. You can download it here.

ECCV 2010 highlights

2010-09-11T22:51:00.002+04:00

Today is the last day of ECCV 2010, so the best papers are already announced. Although I was not there, a lot of papers are available via cvpapers, so I eventually run into some of them.

Best papers

The full list of the conference awards is available here. The best paper is therefore "Graph Cut based Inference with Co-occurrence Statistics" by Lubor Ladicky, Chris Russell, Pushmeet Kohli, and Philip Torr. The second best is "Blocks World Revisited: Image Understanding Using Qualitative Geometry and Mechanics" by Abhinav Gupta, Alyosha Efros, and Martial Hebert. Two thoughts before starting reviewing them. First, the papers come from the two institutions which are (arguably) considered now the leading ones in the vision community: Microsoft Research and Carnegie-Mellon Robotics Institute. Second, both papers are about semantic segmentation (although the latter couples it with implicit geometry reconstruction); Vidit Jain already noted the acceptance bias in favour of the recognition papers.

Okay, the papers now. Ladicky et al. addressed the problem of global terms in the energy minimization for semantic segmentation. Specifically, their global term deals only with occurrences of object classes and invariant to how many connected components (i.e. objects) or individual pixels represent the class. Therefore, one cow on an image gives the same contribution to the global term as two cows, as well as one accidental pixel of a cow. The global term penalizes big quantity of different categories in the single image (the MDL prior), which is helpful when we are given a large set of possible class labels, and also penalizes the co-occurrence of the classes that are unlikely to come along with each other, like cows and sheep. Statistics is collected from the train set and defines if the co-occurrence of the certain pair of classes should be encouraged or penalized. Although the idea of incorporating co-occurrence to the energy function is not new [Torralba et al, 2003; Rabinovich et al., 2007], the authors claim that their method is the first one which simultaneously satisfy the four conditions: global energy minimization (implicit global term rather than a multi-stage heuristic process), invariance to the structure of classes (see above), efficiency (not to make the model order of magnitude larger) and parsimony (MDL prior, see above).

How do the authors minimize the energy? They restrict the global term to the function of the set of classes represented in the image, which is monotonic w.r.t. argument set enclosing (more classes, more penalty). Then the authors introduce some fake nodes for αβ-swap or α-expansion procedure, so that the optimized energy remains submodular. It is really similar to how they applied graph-cut based techniques for minimizing energy with higher-order cliques [Kohli, Ladicky and Torr, 2009]. So when you face some non-local terms in the energy, you can try something similar.

What are the shortcomings of the method? It would be great to penalize objects in addition to classes. First, local interactions are taken into account, as well as global ones. But what about the medium level? Shape of an object, size, colour consistency etc. are the great cues. Second, on the global level only inter-class co-occurrences play a role, but what about the intra-class ones? It is impossible to have two suns in a photo, but it is likely to meet several pedestrians walking along the street. It is actually done by Desai et al. [2009] for object detection.

The second paper is by Gupta et al., who have remembered the romantic period of computer vision, when the scenes composed of perfect geometrical shapes were reconstructed successfully. They address the problem of 3D reconstruction by a single image, like in auto pop-up [Hoiem, Efros and Hebert, 2005]. They compare the result of auto pop-up with Potemkin villages: "there is nothing behind the pretty façade." (I believe this comparison is the contribution of the second author). Instead of surfaces, they fit boxes into the image, which allows them to put a wider range of constraints to the 3D structure, including:

static equilibrium: it seems that the only property they check here is that centroid is projected into the figure bearing;
enough support force: they estimate density (light -- vegetation, medium -- human, heavy -- buildings) and say that it is unlikely that building is build on the tree;
volume constraint: boxes cannot intersect;
depth ordering: backprojecting the result to the image plane should correspond to what we see on the image.

This is a great paper that exploits Newtonian mechanics as well as human intuition, however, there are still some heuristics (like the density of a human) which could probably be generalized out. It seems that this approach has a big potential, so it might became the seminal paper for the new direction. Composing recognition with geometry reconstruction is quite trendy now, and this method is ideologically simple but effective. There are a lot of examples how the algorithm works on the project page.

Funny papers

There are a couple of ECCV papers which have fancy titles. The first one is "Being John Malkovich" by Ira Kemelmacher-Shlizerman, Aditya Sankar, Eli Shechtman, and Steve Seitz from the University of Washington GRAIL. If you've seen the movie, you can guess what is the article about. Given the video of someone pulling faces, the algorithm transforms it to the video of John Malkovich making similar faces. "Ever wanted to be someone else? Now you can." In contrast to the movie, in the paper not necessarily John Malkovich plays himself: it could be George Bush, Cameron Diaz, John Clooney and even any person for whom you can find a sufficient video or photo database! You can see the video of the real-time puppetry on the project page, although obvious lags take place and the result is still far from being perfect.

Another fancy title is "Building Rome on a Cloudless Day". There are 11 (eleven) authors contributing to the paper, including Marc Pollefeys. This summer I spent one cloudless day in Rome, and, to be honest, it was not that pleasant. So, why is the paper called this way then? The paper refers to another one: "Building Rome in a Day" from ICCV 2009 by the guys from Washington again, which itself refers to the proverb "Rome was not built in a day." In this paper authors build a dense 3D model of some Rome sights using a set of Flickr photos tagged "Rome" or "Roma". Returning back to the monument of collective intelligence from ECCV2010, they did the same, but without cloud computing, that's why the day is cloudless now. S.P.Q.R.

I cannot avoid to mention here the following papers, although they are not from ECCV. Probably the most popular CVPR 2010 paper is "Food Recognition Using Statistics of Pairwise Local Features" by Shulin Yang, Mei Chen, Dean Pomerleau, Rahul Sukthankar. The first page of the paper contains the motivation picture with a hamburger, and it looks pretty funny. They insist that the stuff from McDonald's is very different from that from Burger King, and it is really important to recognize them to keep track of the calories. Well, the authors don't look overweight, so the method should work.

The last paper in this section is "Paper Gestalt" by the imaginary Carven von Bearnensquash, published in Secret Proceedings of Computer Vision and Pattern Recognition (CVPR), 2010. The authors (presumably from UCSD) make fun of the way we usually write computer vision papers assuming that some features might convince a reviewer to accept or reject the paper, like mathematical formulas that create an illusion of author qualification (although if they are irrelevant), ROC curves etc. It also derides the attempts to apply black-box machine-learning techniques without the appropriate analysis of the possible features. Now I am trying to subscribe to the Journal of Machine Learning Gossip.

Colleagues

There was only one paper from our lab at the conference: "Geometric Image Parsing in Man-Made Environments" by Olga Barinova and Elena Tretiak (in co-authorship with Victor Lempitsky and Pushmeet Kohli). The scheme similar to the image parsing framework [Tu et al., 2005] is utilized, i.e. top-down analysis is performed. They detect parallel lines (like edges of buildings and windows), their vanishing points and the zenith jointly, using a witty graphical model. The approach is claimed to be robust to the clutter in the edge map.

Indeed, this paper could not have been possible without me. =) It was me who convinced Lena to join the lab two years ago (actually, it was more like convincing her not to apply for the other lab). So, the lab will remember me at least as a decent selectioner/scout...

Comic strip: 10%

2010-08-27T22:49:00.006+04:00

Last summer, during my internship at CMP in Prague I drew some xkcd-style comic strips, and I want to share some of them here. I considered starting a different blog for that, but there are too few of them, and they do suck (at least in comparison to Randall's work). However, most of them are programming/research related, so they are appropriate here.

I planned to use them when I would have nothing to post about. This is not the case now (I am planning a couple more posts in a week or so), but this one is topical. It was originally drawn in September 1, 2009 when GMail was not operating for a few hours. From the recent news: Google shuts Google Wave down, admitting their failure predicted by some sceptics (see the image title text).

Theorem 8.10. P ≠ NP.

2010-08-19T01:49:00.008+04:00

Nearly two weeks ago Indian-American mathematician Vinay Deolalikar, the employee of HP Labs, sent a letter to a group of mathematicians asking them to proof-read his attempt to prove P ≠ NP. The pre-print was eventually distributed over the Internet, so a lot of people became aware. Later two major flaws were found in the proof, so it is now considered wrong. Nevertheless, Vinay has removed the paper from his page and commented that he fixed all the issues and is going to submit a paper to the journal review. You can download the original paper from my web-site [Deolalikar, 2010].

We'll see if he is bluffing or not. In any case, it is very pleasant to me that the main role in the proof is played by... the graphical probabilistic model framework. Yeah, those graphical models we use in computer vision! It was surprising indeed, since the problems in computational complexity are usually discrete and well-posed. So, this post is devoted to understanding why a graphical model emerges in the proof.

First, I am going to review some key points of the proof. It is far from being exhaustive, just some rough sketches that are critical for understanding. Then I report on the flaws found in the proof, and then I end up with a methodological note on the whole P vs. NP problem.

k-SAT and d1RSB Phase

In order to prove P ≠ NP, it is enough to show the absence of a polynomial algorithm for some problem from the class NP, e.g. for some NP-complete problem (which are the "hardest" problems in NP). The boolean satisfiability problem (SAT) addresses the issue of checking if there is at least one assignment of the boolean variables in the formula, represented in conjunctive normal form (CNF), which makes it TRUE. The k-satisfiability problem (k-SAT) is a particular case of SAT, where all the clauses in the CNF have order k. For example, (x˅y)&(¬x˅y)&(x˅¬y)&(¬x˅¬y) is an instance of 2-SAT which has the answer 'NO', since any boolean values of (x, y) makes the formula false. (x˅y˅z)&(¬x˅u˅v)&(¬x˅u˅¬z) is a 3-SAT over 5 variables (x, y, z, u, v), which is satisfiable, e.g. on the input (1,0,0,1,0). 2-SAT is in P, but k-SAT is NP-complete whenever k > 2. The Deolalikar's idea is to show that k-SAT (with k > 8) is outside of P, which (if true) proves that there is a separation between P and NP.

The space of possible k-SAT solutions is analysed. Let m be the number of clauses in the CNF, n be the number of variables. Consider the ratio α = m/n. In the border case m = 1 (α is small), k-SAT is always true, there are usually a lot of inputs that satisfy the CNF. Consider an ensemble of random k-SATs (the following is statistical reasoning). With the growth of α, the probability of the CNF to be satisfiable decreases. When a certain threshold α_d is reached, the "true" solutions set breaks into clusters. This stage is known in statistical mechanics as dynamical one step replica symmetry breaking (d1RSB) phase. Moving further, we make the problem completely unsatisfiable. It turns out that d1RSB stage subproblems are the most challenging of the all k-SAT problems. The effect could be observed only if k > 8, that's why such problems are used in the proof. [Deolalikar, 2010, Chapter 6]

FO(PFP) and FO(LFP)

In the finite model theory there are recurrent extensions of the first-order logic. The predicate P_i(x) is evaluated as some second-order function φ(P_i-1, x), where x is a k-element vector, P₀(x) ≡ false. In the general case, either there is a fixed point, or is P_ilooping. For example, if φ(P, x) ≡ ¬P(x), then P₀(x) ≡ false, P₁(x) ≡ true, P₂(x) ≡ false, etc. Here x is meaningless, but it is not always the case. Consider the following definition: φ(P, x) ≡ max(x) ˅ P(x) // recall x is a vector, in the boolean case 'max' is the same as 'or'. If x contains at least one non-zero element, P₀(x) = false, P₁(x) = true, P₂(x) = true, etc. Otherwise, P_i(0) = false for all i. In the case of looping, let's redefine the fixed point to be constantly false. FO(PFP) is a class of problems of checking if there will be a loop for some x, or a fixed point. They are actually very difficult problems. FO(PFP) is equal to the whole PSPACE. Suppose now that φ is monotonic on P. It means that P(x) only appears in the formula with even number of negations before it (or zero, as in the second example). This means that once P_i(x) is true, P_j(x) will be true for any j > i. This reduces the class to FO(LFP), which is proven to be equal to the class P. So, the global problem now is to show that k-SAT is outside of the class FO(LFP).

ENSP: the graphical model for proving P ≠ NP

So how a graphical model emerges here? Graphical model is a way to describe a multivariate probability distribution, i.e. dependencies of covariates in the distribution. Recall now the definition of NP. If we somehow guess the certificate, we are done (i.e. have a polynomial algorithm). If the space of certificates (possible solutions, in terms of Deolalikar) is simple, we can probably get a polynomial algorithm. What is simple? This means that the distribution is parametrizable with a small amount of parameters (c.f. intrinsic dimensionality), which allows us to traverse the solution space efficiently. This is twofold. First, the distribution is simple if it has a limited support, i.e. all the probability measure is distributed among a limited number of points of the probabilistic space. Second, it is simple if the covariates are as much conditionally independent as possible. In the ideal case, if all the groups of covariates are independent (recall that pairwise and mutual independence do not subsume each other!), we need only n parameters to describe the distribution (n is the number of covariates), while in general case this number is exponential. See [Deolalikar, 2010, p. 6] for examples.

How to measure the degree of conditional independence? Yes, to build a graphical model. It is factorized to cliques according to Hammersley-Clifford theorem. Larger cliques you get, stronger dependency is. When the largest cliques are k-interactions, the distribution can be parametrized with n2^k independent parameters. Finally, Vinay shows that FO(LFP) can deal only with the distributions parametrizable with 2^{poly(log n)} parameters, which is not the case for d1RSB k-SAT (its solution space is too complicated).

In order to show it strictly, Deolalikar introduces a tailored graphical model describing LO(LPF) iterative process, the Element-Neighborhood-Stage Product model (ENSP):

There are two types of sites: corresponding to the variables on the stages of LFP (small circles) and corresponding to the elements of witty neighbourhood system (some closure over Gaifman graph; big blue circles). When a variable is assigned 0 or 1, it is painted with red or green respectively. The last column corresponds to the fixed point, all the variables are assigned. Thus, this model is easily factorizable to the small cliques, and it cannot describe the imaginable LFP process for some k-SAT. See [Deolalikar, 2010, Chapter 8] for the details.

So what's the problem?

Neil Immerman, an expert in the finite model theory, noticed two major flaws. The first one is that Vinay actually model only monadic LFP, which is not equal to P, as assumed. He thus proved that there is a gap between NP and some subclass of P, which is not obligatory equals P. The second major flow deals with modelling k-SAT as a logical structure. I do not fully understand this step, but some order-invariance assumptions are wrong. Here is a discussion in Lipton's blog. According to it, the flaws are really fatal.

The third way

It seems that it is really difficult to prove P ≠ NP. The most of scientists think that P = NP is improbable, and that's why the hypothesis P ≠ NP is generally adopted now. But there is one more option: neither P = NP nor P ≠ NP is provable. As every mathematical theory, computational complexity is a set of axioms and statements, which are usually could be proved to be correct or not. But there are sometimes some statements formulated in terms of the theory, which could not. Moreover, according to the first Gödel's incompleteness theorem, in any mathematical theory based on our natural understanding of natural numbers, there is either a statement that could be proved both true or false, or an unprovable one. I know no actual reasons why this could not be the case for P ≠ NP (although I have feelings there are some since it is not usually taken into account).

Suppose it is really so. This would mean that the whole theory should be reconsidered. Some axioms or definitions will change to make this fact provable. But may be anything else will become unprovable. Who knows...

Image Parsing: Unifying Segmentation, Detection, and Recognition

2010-08-15T22:38:00.002+04:00

Recently I have posted about the connection between object category detection and semantic image segmentation. While delving into this problem more deeply, I have found the paper denoted in the title of this post.

The ICCV 2003 paper by Tu et al. was among the three Marr prize winners. And it is really a prominent piece of work! In the introduction to the special Marr prize IJCV issue, Bill Triggs featured the paper as one that "would have been particularly pleasing to David Marr", because of "its bold attack on the central problem of perceptual organization and whole scene understanding". Here is the journal version of the paper.

The authors combined discriminative and generative models, which resulted to the unified framework for image parsing. For each image the corresponding parsing tree could be found. The root of the tree represents the whole scene. On the next level, nodes represent semantic fragments, such as human faces, text, or textured regions. The leaves of the tree correspond to the pixels of the image.

The approach differs drastically from the vanilla CRF framework in the way that the structure of the parsing tree is dynamic while the CRF structure remains constant and just interaction models between the pairs of sites may change. The goal is to obtain the tree that maximizes the posterior probability given the image. The directed search in the space of valid trees is performed by means of Markov chain Monte-Carlo (MCMC). The possible tree changes like split and merge of regions, varying the border between regions, are defined. Such changes are described in terms of learnable Markov chain transition kernels.

What they actually did is they effectively combined top-down and bottom-up approaches. In a nutshell, the bottom-up (discriminative) method generates the hypotheses of pixel labels and object positions using the local neighbourhood, and the top-down generative model is then built making use of those hypotheses. The latest guarantees the consistency of the output and the optimum of its posterior probability.

Okay, what does it mean for the issue of detection and segmentation convergence? Because the shapes of objects are determined implicitly during the recognition, and stuff regions are detected by their colour and texture, the problem of semantic image segmentation is actually solved. Moreover, multi-scale semantic segmentation is performed during the parsing. Therefore, image parsing seems to be the most general formulation of image recognition problem.

The nodes of a parsing tree, which belong to the same depth level, are not connected (right, because it is a tree). This means that spatial interactions could not be modelled directly. A totally different approach was introduced in another Marr prize winning paper by Desai et al [2009]. They also use bottom-up tests to generate hypotheses on the object locations and then use CRF over those location to take spatial context into account. They model different kinds of inter-class and intra-class interactions. Thus, they ensure that the objects in the image (described by their bounding boxes) are arranged correctly, e.g. a cup is likely to be on a table (spatial arrangement), while a train could not be close to a ship (mutual exclusion).

It seems that the two papers exploit the two different forms of information (aggregation vs. spatial interactions), which are mutually redundant to a certain extent, but do not completely exhaust each other. It seems that the group of researchers who will successfully combine those approaches will receive some 201x Marr prize.

ICVSS 2010: some trivia

2010-07-28T00:41:00.010+04:00

If you think that summer schools are only about lectures and posters, you are certainly wrong. Well, I also did not expect that I would get drunk every night (it was not in Russia after all!). On the first night I convinced people to go to the beach for night swimming, but on the next day I realized that it was not a really good idea, because lectures started at 9. Eventually, we did not go to bed early for the rest of the week.

I would like to thank "Marsa Sicla" people (Fig. 1), you were the great company!

Fig. 1. The Marsa Sicla company. Left to right: Richard, Ramin,
Nicolas, Xi, Vijay, Clément, Aish, me. Sandra is behind the camera.

Actually, there was a reason why we had such a close-knit company. On the Fig. 2 you can see the map of the region where the school took place. The school was hosted by Baia Samuele hotel village (inside the blue frame on the map). The cheapest accommodation at Baia Samuele costed €100 per night, so some pragmatic people scared a different accommodation up. It was in a neighbouring hotel village, Marsa Sicla.

Fig. 2. ICVSS location map. View ICVSS_2010_MSvsBS in a larger map

In a map it looked pretty close, but in practice it turned out that there were a lot of fences (blue line)! Officially, we had to walk along the red route (~2.5 km, partly along a highway) through the official entrance. Moreover, we had to leave the village for lunch (since there were buffet), otherwise we would have been charged €30 per meal. To control it they wanted us to leave our documents at the control post (bottom blue tick on Fig. 2). Thus, we were supposed to walk 2.5 km four times a day. But we found a better solution.

Although the fence was equipped with a barbwire, we managed to find two shortcuts (green ticks). One of them led through ever-closed gate (Fig. 3), which were suitable for hopping over. So, we used the green path usually. It made the way two times shorter. Moreover, we did not have to leave Baia Samuele for lunch, since we weren't officially there. Sometimes we even had free lunch, that finally proved that the no free lunch theorem is wrong (joke by Ramin).

Fig. 3. Hopping over the fence.

Well, the lunch was really great. But this was not really a question of food, the main reason not to leave Baia Samuele was of course socialization, which used to be active during lunch (and also Internet access at the conference centre :). If we knew about such situation before booking the apartments, we would probably followed the official accommodation recommendations. However, we had a great company at Marsa Sicla too. But because of "unofficial night programme" I had to (almost) sleep during lectures. Most of guys was on their last year of PhD, so they considered the school as a vacation. But I really wanted to learn a lot of stuff. It was really difficult to perceive any information when you had not slept enough time. Surprisingly, I somehow managed to pass the final exam, but I feel I need to look through the lecture slides again, reading up some papers they refer to, otherwise the scientific part of the school will be useless for me.

Thus, I finish posting about ICVSS. To conclude, I want to recommend everyone to visit such summer schools, because they are the best way to enter into the community.

ICVSS 2010: Have you cited Lagrange?

2010-07-26T20:33:00.006+04:00

Yeah, I have. :) Before the beginning of the summer school we received a homework assignment from Prof. Stefano Soatto. We had to read the three papers and discover the roots of ideas exploited by the authors. Such connections are not obligatory expressed by references. As a result, one had to get a tree (or, may be, lattice) with a root in the given paper. Since the task was not accurately formulated, most of us chose just one paper and made a tree for it. Later it turned out that all three problems (optical flow estimation, multi-view stereo and volume registration) have the same roots because they lead to the similar optimization problems and we were supposed to establish that connection.

I (like most of the students) had a limited time to prepare the work. All the modern research in optical flow is based on two seminal papers by MIT's Horn & Shunk and CMU's Lukas & Kanade, both from 1981. During the last 30 years a lot of work has been done. It was summarized by Sun et al. (2010), who discovered that only small fraction of the ideas give significant improvement and combined them into quite simple method that found its place on the top of Middlebury table. Since I had no time to read a lot of optical flow papers, I discovered a lot of math stuff (like PDEs and variation calculus) used in Horn-Shunk paper. Just as a joke I added references to the works of Newton, Lagrange and d'Alambert to my report. Surprisingly, joke was not really understood.

There were only 21 submissions, one of them was 120 pages long (the author did not show up at the seminar =), the tree depth varied from 1 to 20. I was not the only one who cited "pre-historic" papers, someone traced ideas back to Aristotle through Occam. The questions about the horizon arose: it is really ridiculous to find the roots of computer vision at Aristotle works. Since the prizes were promised for rare references (the prize policy was left unclear too), some argument took place. Soatto did not give any additional explanations on the formulation of the task but let the audience decide which references are legitimate in controversial cases. Eventually, I was among the 5 people whose references were considered controversial, so I needed to defend them. Well, I suppose I looked pretty pathetic talking about Newton's finite differences which were used for approximation of derivatives in the Horn-Shunk's paper. Surprisingly, almost a half of the audience voted for me. =) Also, my reference to the Thomas Reid's essay was tentatively approved.

Finally, there were no bonuses for the papers that could not be found with Google, and the whole $1000 prize went to the Cambridge group. To conclude, Soatto (among other) said that nobody had read any German or Russian papers. After the seminar I told him how I tried to dig into the library (it is described here in Russian), he answered something like "funny, it is hard to find them even for you!"

One evening during the dinner we talked about Russia, and Vijay told a lot of interesting stuff (like the guy who developed ChatRoulette is now working in Silicon Valley). He remembered Stephen Boyd who is known for his jokes about Russia. I said that I watched the records of his amazing course on Convex Optimization. It turned out that Vijay (who is now a PhD student in Stanford) took that course, and he promised to tell Boyd that he has a fan in Russia. (Or, maybe in Soviet Russia fans have Boyd =).

continued here

ICVSS 2010: lectures and posters

2010-07-25T03:17:00.008+04:00

I returned from my eurotrip yesterday and now I am ready to start a series of posts about International Computer Vision Summer School (ICVSS 2010). Generally, I enjoyed the school. That week gave me (I hope) a lot of new knowledge and new friends.

The scientific programme of the school included lectures, tutorials, a student poster session and a reading group. Lectures occupied most of official programme time and were given by a great team of professors including Richard Szeliski, renowned Tomasso Poggio and enchanting Kristen Grauman. I am not going to describe all the talks, but feature the ones that are close to my interests. You can find the complete programme here. Unfortunately, no video was recorded, but I have an access to all the slides and posters, so if you are interested in anything, I can send it to you (I believe it does not violate any copyrights).

Wednesday was the day of Recognition. Kristen Grauman gave a talk about visual search. She covered the topics concerning specific object search using local descriptors and bags of words, object category search with pyramid matching, and also discussed state-of-the-art in the challenging problem of web-scale image retrieval. Mark Everingham continued with a talk about category recognition and localization using machine learning techniques. Localization is reached using bounding boxes, segments, or object parts search (like finding eyes and a mouth to find a face). Sure he could not avoid to mention importance of context. He also explained the PASCAL VOC evaluation protocol.

The tutorials covered some applications and did not really impress me. Poster session was a great opportunity to meet people. Some posters were really decent, for example Michael Bleyer's poster on dense stereo estimation using soft segmentation, which won a half of the school's best presentation prize. The work was done with Microsoft Research Cambridge, they formulated a really complicated energy function based on surface plane estimations and minimized it with Lempitsky's graph-cut based fusion-move algorithm (2009). More details could be found in their recent CVPR paper.

The problem with the poster session was that lecturers did not attend it, although they could really give a great feedback. My presentation was in the last day of the session after the not-really-popular reading group and in the room upstairs (its existence was not a well-known fact :), so many people preferred to spend that evening on the beach. The school audience was quite heterogeneous, there were a lot of people from medical imaging, video compression etc., so I had to explain some basics (like MRFs) to some students interested in my poster. There were also really smart guys (like those from Cambridge group). There was a bit of useful feedback: someone recommended me to use QPBO for inference, and I should probably consider it.

Since the speakers did not attend the poster session, students had to communicate with them informally. A roommate of mine, Ramin, who does a crowd analysis, caught Richard Szeliski and asked him about local descriptors in video that operate in 3D image-time space. Szeliski told that it is a promising field and even remembered Ivan Laptev's name. During our tour to Ragusa Ibla I asked Mark Everingham (who is probably the closest of all speakers to my topic) about 3D point cloud classification. He said it was not really his field, but it should be fruitful to analyse clouds not only in local levels, and stuff like multi-layer CRFs could be useful. During the last 2 years there appeared a few papers that exploit that simple intuitive idea and incorporate shape detectors with CRFs, but it usually looks awkward. Well, may be smartly designed multi-layer CRFs might be really useful. It is funny, when I told Everingham that I'm from Moscow he replied that it was great, Moscow has a great math school and remembered Vladimir Kolmogorov. So, our education seems to be not so terrible. :D

continued here

Mendeley news

2010-06-27T11:53:00.003+04:00

Few months ago I posted about Mendeley, the reference management system. I've been using it all the time and I am really satisfied. It is much more convenient to have your papers on a server than on a flash drive. Also keeping meta-information about the papers makes dealing with them (exploring, reading, citing etc.) more pleasant.

In this month a major update was released and a monetizing scheme was introduced. There are now 3 tariff plans in addition to the free one that allows one to use up to 1Gb of server disk space. There are also restrictions on the max number of shared collections and the number of users per collection. It does not look critical after all: there are no features you cannot use in the free version, so the company seems not evil. However, on the sister project last.fm the radio feature became paid after years of free service, which caused many users drift to grooveshark.

The update has affected the design of the paper info right-hand bar, and the references bar was eliminated. They promise to rebirth the bar in the future releases. It was really unusable before. When you read a paper, it is handy to have the list of indexed references on the bar, especially if the reference-style citing is used (it is the major problem with reading papers from the screen: where the hell [42] is referencing to?) I hope the people in Mendeley realize it.

It would be great to have a possibility to find papers without leaving the application. In theory, you could drag a citation from the references bar to a collection, find its (more) precise details via Internet search, and you are likely to have the link, and if it is direct, you can add the pdf with the Add File dialog using the found URL. In practice, the found URLs usually are not direct, they refer to IEEE/ACM/Springer pages, where the paper could be downloaded (usually not freely). In the same time, the paper is likely to be available for free through the direct link on the author's homepage. Moreover, Google Scholar often finds them too, but Mendeley chooses indirect links.

Mendeley needs to be more "semantic" while working with authors and conferences. It stores the author name as it appears in the paper. When you want to filter your papers by author, you can see "Shapovalov, R", "Shapovalov, R.", "Shapovalov, Roman", "Shapovalov, Roman V." etc. in the list. There are bases like DBLP, Mendeley can build their own index, so the author should be identified. If we know the author (but not only her name appearance in the paper), we are able to filter Google Scholar results and retrieve the direct link to the paper hosted on the author/university site. Finally, it is feasible to create the system, where human don't need to find papers. If I see the reference, I can automatically retrieve the pdf in a few seconds. I want Mendeley to develop in this direction.

Object detection vs. Semantic segmentation

2010-06-21T02:21:00.008+04:00

Recently I realized that object class detection and semantic segmentation are the two different ways to solve the recognition task. Although the approaches look very similar, methods vary significantly on the higher level (and sometimes on the lower level too). Let me first state the problem formulations.

Semantic segmentation (or pixel classification) associates one of the pre-defined class labels to each pixel. The input image is divided into the regions, which correspond to the objects of the scene or "stuff" (in terms of Heitz and Koller (2008)). In the simplest case pixels are classified w.r.t. their local features, such as colour and/or texture features (Shotton et al., 2006). Markov Random Fields could be used to incorporate inter-pixel relations.

Object detection addresses the problem of localization of objects of the certain classes. Minimum bounding rectangles (MBRs) of the objects are the ideal output. The simplest approach here is to use a sliding window of varying size and classify sub-images defined by the window. Usually, neighbouring windows have similar features, so each object is likely to be alarmed by several windows. Since multiple/wrong detections are not desirable, non-maximum suppression (NMS) is used. In PASCAL VOC contest an object is considered detected, if the true and found rectangles are intersected on at least half of their union area. In the Marr prize winning paper by Desai et al. (2009) more intelligent scheme for NMS and incorporation of context is proposed. In the recent paper by Alexe the objectness measure for a sliding window is presented.

In theory, the two problems are almost equivalent. Object detection reduces easily to semantic segmentation. If we have a segmentation output, we just need to retain object classes (or discard the "stuff" classes) and take MBRs of regions. The contrary is more difficult. Actually, all the stuff turns into the background class. All the found objects within the rectangles should be segmented, but it is a solvable issue since foreground extraction techniques like GrabCut could be applied. So, there are technical difficulties which could be overcome and the two problems could be considered equivalent, however, in practice the approaches are different.

There arise two questions:

1. Which task has more applications? I think we do not generally need to classify background into e.g. ground and sky (unless we are programming an autonomous robot), we are interested in finding objects more. Do we often need to obtain the exact object boundary?

2. Which task is sufficient for the "retrieval" stage of the intelligent vision system in the philosophical sense? I.e. which task is more suitable for solving the global problem of exhaustive scene analysis?

Thoughts?

Max-product optimization methods and software

2010-05-30T22:38:00.009+04:00

I hoped I would never post a sorry-for-not-posting message, but I do (and now I feel like I owe you a long post =). In fact, I have been being really busy, particularly with putting my masters thesis down to paper. However, it has a positive outcome: I systematized my knowledge about inference techniques in MRFs, and I'd like to share them here.

Please don't consider it a survey. While it claims to be quite comprehensive, it is not enough deep and verbose. You are not gonna see a lot of formulas, but the links to papers and implementations along with the recommendations on applicability of the methods and the software. It could be useful for anybody who wants to quickly try energy minimization in her task, but don't wanna spend a lot of time digging into the literature and implementing algorithms. So let's call this form of posting unsurvey. You can always find more details on the topic in Stan Li's book (not to be confused with Stan Lee recently appeared in The Big Bang Theory).

Max-product energy minimization problem arises in a number of fields such as statistical physics, social network analysis, and, of course, computer vision, where the problems like image denoising, dense stereo reconstruction, semantic segmentation lead to the single discrete optimization problem: maximize the product of some functions defined over nodes and edges of the graph G=(N,E), typically a grid over image pixels in low-level vision. Due to using logarithms, it is equivalent to maximizing the sum

where each Y_i corresponds to a node of the graph and takes on a value from a fixed discrete range. It could be a class label in semantic segmentation, or a disparity value in the pixel in dense stereo. So-called potential functions φ (unary in the first term and pairwise in the second one) define possibility of the assignment given class labels to the nodes and edges correspondingly. They could be conditioned by the data. For example, unary potentials could reflect colour information in the pixel, and pairwise potentials could enforce assignment of the similar labels to the ends of an edge to provide smoothness in the resulting labelling. If the graph contains cliques of the order 3 and greater, one should consider more terms (as I explained earlier), but in practice higher order cliques are often ignored. Also, an important particular case, 4-connected grid, contains only second order cliques, that's why the research community focused on this "pairwise" problem.

In general, this maximization problem is NP-hard. That's why in the 1980s they solved it using genetic algorithms or simulated annealing. Fortunately, specific methods have been developed.

First of all, there are two cases when the exact global optimum could be found in polynomial time. The first is when the graph has a tree structure. Actually, I don't know application where this case is useful. Probably, it is good for analysis of parsing trees in natural language processing. In this case the maximum is found using the dynamic programming based belief propagation algorithm. One node is selected as the root, and messages are passed from the root and then back to the root. The optimal assignment is thus found.

Another polynomial case allows an arbitrary graph topology, but restricts the number of labels and the form of pairwise potentials. Only one of the two labels could be assigned to each node. Pairwise potentials should be submodular, i.e. φ(0,0) + φ(1,1) >= φ(0,1) + φ(1,0). Thus, the binary assignment implies that all the nodes should be divided into the two groups according to their labels. This division is found using the algorithm for finding minimum cut on the supplementary graph. Two fake nodes are added to the graph and declared as the source and the sink. Both fake nodes are adjacent to all the nodes of the "old" graph. Using your favourite min-cut/max-flow algorithm you can separate the nodes into two sets, which gives you the resulting labelling.

Unfortunately, the binary labelling problem is not so common too. In practice people want to choose one of the multiple labels for the nodes. This problem is NP-hard, but the iterative procedures of α-expansion and αβ-swap give good approximations with certain theoretical guarantees. [Boykov et al., 2001] During each iteration the min-cut algorithm is run, so there is an important constraint. Each projection to any two variables of pairwise potentials should be submodular. If it is hold for your energy, I recommend you to use this method since it is really fast and accurate. The implementation by Olga Veksler is available.

What should we do if the energy is not submodular and the graph contains cycles? There are some methods too, but they are not so fast and typically not so effective. First of all, the stated integer programming problem could be relaxed to linear programming. You can use any LP solver, but it will eventually take days to find the optimum. Moreover, it won't be exact, because the relaxed problem solution could be rounded back in multiple ways. No surprise here, because the possibility of getting the global optimum would prove that P = NP.

One of the methods for approaching the general problem is Loopy Belief Propagation [Kschischang, 2001]. No doubt, it is really loopy. Dynamic programming is used on the graph with loops, and it can eventually fall into the endless loop passing some messages along the loop. It is now considered outdated, but you can still try it, it is implemented in libDAI. The input is a factor graph, which is inconvenient in most cases, but really flexible (you could create cliques of arbitrary order).

State-of-the-art approach in general case, tree-reweighted message passing (TRW), has been developed by Wainwright and Kolmogorov. [Kolmogorov, 2006] It is based on the decomposition of the original graph to some graphs where exact message-passing inference is possible, i.e. trees. Message passing is done iteratively on the trees, and trees are enforced to assign the same values in particular nodes. The procedure is guaranteed to converge, but unfortunately not always to the global maximum. However, it is better than Loopy BP. Kolmogorov's implementation contains LBP and TRW-S under a common interface, so you can compare their performance. To understand the decomposition technique better, you could read Komodakis's paper [2007]. It describes a general decomposition framework.

Once a company of the world-leading MRF researchers gathered and implemented LBP, graph-cuts and TRW-S under common interface, investigated performance and even shared their code on a Middlebury college page. It would be great to use those implementations interchangeably, but unfortunately the interface is tailored for the stereo problem, i.e. it is impossible to use the general form of potentials. My latest research is about usage MRFs for laser scan classification, where the topology of the graph is far from a rectangular grid, and the potentials are more complex than the ones in the Potts model. So I ended up in writing my own wrappers.

Another interesting method was re-discovered by Kolmogorov and Rother [2007]. It is known as quadratic pseudo-boolean optimization (QPBO). This graph-cut based method can either assign a label to a node, or reject to classify it. The consistency property is guaranteed: if the label has been assigned, this exact label is assigned in the global optimum. The equivalent solution could be obtained using a specific LP relaxation with 1/2 probabilities for class labels allowed. I have not used the technique, so I cannot recommend an implementation.

To summarize, the algorithm for choosing an optimization method is the following. If your graph is actually a tree, use belief propagation. Otherwise, if your energy is submodular, use graph-cut based inference; it is both effective and efficient (even exact in the binary case). If not, use TRW-S, it often yields a good approximation.

On Fundamental Artificial Intelligence

2010-04-07T22:51:00.003+04:00

Today I attended Mikhail Burtsev's lecture on evolutionary approach to AI. The lecture was hosted by Moscow Polytechnic Museum's lecture hall. First of all, the organization was great, and the quality of presentation was high. Unsurprisingly, the hall was almost totally occupied by the listeners. I recommend you to attend their lectures.

Mikhail talked a lot about the history and foundations of AI, which was not new to me. He did not bore the audience with the psychology-related stuff, but featured two approaches to AI, that have been being developed simultaneously all the way since 1950s: artificial neural networks and symbolic computational AI. ANNs attempt to model human brain functioning by means of artificial neurons and axons. The problem here is if we build even human-scale artificial brain (which was actually done in Allen Institute for Brain Science in 2005), it will be isolated from the world, and could not be trained like real human brain. Symbolic AI uses formal logic to solve the problems. It also suffers certain problems, like the lack of uncertainty. So, vanilla AI is in the period of stagnation now (it dates bake to the late 1980s, when Rodney Brooks started to criticize it).

Mikhail's point was the one that most researchers attempt to build a straight away model of human intelligence. He suggested to look at the evolution process. We need to start with understanding how the neural system of an amoeba operates, and then track the evolution of it to find out how a human being's mind works. Evolutionary algorithms might be useful there.

I cannot agree with that point. Last 50 years witnessed the failure of fundamental AI research. Their common problem was they tried to model some cognitive mechanisms instead of tackling actual problems, while those problems were being solved by different techniques. Consider the autonomous robot control problem (e.g. a robotic vacuum cleaner). It can be formulated in terms of reinforcement learning and solved by the methods not connected to the vanilla AI (dynamic programming-based, I suppose). Mikhail does not depart from the problem, again. So I don't really believe in success of the method. I am also sceptic to the computational methods inspired by biology. They could be a good starting point, but they used to be supplanted by mathematically founded ones.

Another issue raised in the discussion after the lecture was AI safety, which is probably the most popular philosophical question connected to AI. As far as I understood, there are two main concerns: the AI could become self-replicated (or self-improved) uncontrollably, and it could become self-motivated. If the AI is self-replicated, it is not so dangerous unless it is self-motivated. If it is motivated by a human, it is bad just like nuclear weapon, which is scary only if an evil party possesses it (so, nothing brand new here). If the AI will be motivated to gain the world domination, it could be harmful. But where such self-motivation can come from? In my opinion, the only option is the biological obsession to propagate (imagine some joint AI system with bio-motivator), but such a disaster has already been overcome once. Do you remember that rabbits in Australia? I hope, an uncontrolled AI won't be a bigger problem.

ICVSS 2010

2010-04-06T22:16:00.003+04:00

This summer I'm going to take part at the International Computer Vision Summer School. I have already been accepted and registered for it. I'm really looking forward this event and hope it will not be too hot in July in Sicily. =)

I am now seeking for a room-mate, because accommodation is quite expensive there. If you are a participant too and have a similar problem, please feel free to contact me!

One of the activities of the school is a reading group leaded by Prof. Stefano Soatto. As a homework, we need to investigate the reference trees on three certain subjects. Moreover, there will be prizes for students who will have discovered papers that could not be found via standard search engines. I suppose I have a bonus here: Russian science has been isolated from the, well, science due to that iron curtain thing (it is still quite isolated, by inertia). So, I just need to dig in a library and find something appropriate in old Soviet journals.

read all my posts about ICVSS 2010

Web-scale Content Based Image Retrieval

2010-03-19T00:38:00.008+03:00

Do you remember the concept of Computer Blindness? It is about people intuitively expecting from computer vision algorithms results unreachable by the state-of-the-art methods. Believe or not, recently I fell for that trick too.

I was looking throw Navneet Dalal's slides on Histograms of Oriented Gradients. They contained a lot of frames captured from the movies as examples. There was the following one among them:

It seemed familiar to me. I endeavoured to remember the movie, but I failed.¹ So I decided to check out some web-sites that offered the inverse image retrieval.

Sure, first I turned to St. Google. The similar image service disappointed me since it was not able to find the similar image of what I want. Actually, it has some indexed base (not very large), and one can find the similar images only within that base. If one somehow find the image from the base (e.g. using a text query), (s)he is shown a button that allows similar image retrieval.

There are different web-sites for this purpose. TinEye positions itself as a reverse image search engine. However, it failed to find anything. It honestly admitted that nothing similar was found. GazoPa found something, but that was different from what I had expected, though the found images were similar in saturation. It was strange because usually such methods work on greyscale images to be robust to the colour levels shifts.

Then I decided to check if the situation is common, and tried a different image, which I found on my desktop:²

I wanted to find the name of its author and the title³. The result was almost the same. TinEye found nothing, GazoPa found a lot of pictures of different girls.

Why is the web-scale CBIR not possible to date? Because there are simply a lot of images in the web, and it is intractable to perform search in such a large index. The common workflow implies feature extraction and further feature matching. From each image hundreds of features could be extracted. Each feature is a high-dimension vector (e.g. 128D). Suppose we have N images in the index. If we extract 100 features from each (which is fairly the lower bound), to handle the given picture we should match 100 * 100 * N features in 128D space. It is really hard to do it instantly even if N is small. In 128D, indexing structures like kd-trees do not improve performance over exhaustive search, because branch and bound method is unable to reduce the search space in practice (approximate methods partly solve the problem). For example, it took 13 hours to match 150,000 photos on 496 processor cores for the Building Rome in a Day project. This also tells us that there are 150K photos of Rome in the web, so try to imagine the whole number of pictures!

But there is a certain hope for success in the web-scale CBIR. First, when we deal with billions of photos (and trillions of features) kd-trees are likely to give sublinear performance. Second, one could use the web context of an image to seed out come obviously wrong matches.

In the long run, we need to develop more descriptive image representation and learn how to combine the textual content with the content. Also, using the user interest prior could be useful. The engine may start the search from the most popular photos and ignore the least popular ones. Thus, the task could be formulated as a sequential test, where the predictor should be able to say if the found match is good enough, or it should continue search.

UPD (Apr 7, 2010). Here is a rather broad list of visual image search engines.

¹ The first thought was about Roman Polanski's "The Pianist", which is surely wrong. If you recognize the movie please let me know!

² I've seen the picture in the Hermitage Museum and downloaded it after returning from St. Petersburg, because the girl had reminded me my friend Sveta.

³ It is actually Franz von Lenbach's Portrait of Marion Lenbach, his daughter.

Olga's CVPR paper

2010-02-25T10:33:00.006+03:00

I'd like to congratulate my colleague Olga Barinova on the paper, which is accepted to CVPR international conference! To my knowledge, it is the first paper from our lab, which is accepted to a Rank 1 conference (though it was written during Olga's internship at Microsoft Research).

The paper is on multiple object retrieval. They extend the Hough transform with some graphical model, which makes the results more robust. As soon as the paper become publicly available, I'll add the link here.

UPD. (Apr 20, 2010) PDF

UPD (Jul 30, 2010) Video

Visual Assist's Tip of the Century

2010-02-19T22:39:00.006+03:00

Probably you know the Visual Assist plug-in for Microsoft Visual Studio, which makes C++ programming in the environment zillion times handier. The story is about the bootstrap tip that highlights the feature of restoring files. While the tip window is shown, there is a second dialog box painted in the window. Since it is centred w.r.t. the screen, you perceive it as a real dialog box. Moreover, it is the usual case when Visual Assist suggests you to load some files from backup while MSVS is loading, because it does not always shut down properly. Thus, you try to close it clicking Yes or No, but nothing happens! The box is still in its place! That was really annoying.

In the later versions the developers solved the problem. They just marked the box as the example. The nice lack and the nice solution.

Quantum Machine Learning

2010-02-13T16:30:00.005+03:00

Recently, Google announced their intentions to use quantum algorithms for the search. They implemented Grover's algorithm on the D-Wave chip. Whatever they say about D-Wave, we should admit that quantum computers are going to change the nature of machine learning, it is only a matter of time.

In spite of I had the university course on quantum computing, I am not able to make head or tails of it. (See my recent post about our university education) But, as far as I know, the key idea is a computer can perform exhaustive search in constant time. This means that for quantum algorithms P=NP. For example, the problem of exact MAP inference in an MRF could be efficiently solved via exhaustive search in the space of all possible assignments.

However, quantum computers return probabilistic results, so there remains a work for mathematicians. But it is the work of the different kind. In the field of MRF MAP inference, all the algorithms like loopy BP will be forgotten. Another example: Google's Hartmut Neven developed a quantum version of AdaBoost. So, machine learners, go study quantum mechanics!

University education reform

2010-02-11T23:20:00.003+03:00

Recently, me and my friend Andrew Korolev came up with the plan of reforming Russian higher education system.

There are some evident problems in the system one can notice even in our faculty. The most courses are obsolete (or, well, legacy), a lot of courses are not enough developed (e.g. they contain only lectures without any support), some of them are also over-theorized and not applicable in real world (or at least they don't touch upon their applications). As a result, students are not motivated, they don't attend lectures and learn everything during the two-day period prior to the exam. The grades are often lousy, but nobody cares since such grades are sufficient to continue studying. (It is difficult to fail totally, especially for non-freshmen). Such knowledge is not solid and quite useless.

We make use of the following facts. The professors are well-qualified here, the students are witty and communicate with each other and with the graduates. Also, we suppose that everyone wants get more money, which is not always hold though is pretty common.

First, we need to improve the quality of courses. The problem is how to measure the quality. We state that it is proportional to the number of students who choose the course. Since the students have enough information about the course (from the lecturers and other students) and they all want to make a magnificent career, the useful courses become popular. The professors should be paid according to the number of students who attend their courses. But students also want to save their time. So, they are likely to choose the least challenging courses, which are not useful. In order to penalize them, the course part of professor's salary should be eliminated by the fraction of positive grades students get. Thus, a professor is motivated to make a comprehensive course (to attract students) and to implement a severe grade policy (to eliminate the freebie).

However, it will never work if the students are not motivated to get the good grades. In Russia, we have 4-level grades (2 through 5; 3 is enough for the pass), and most of the students are happy with 3s. Today, there are two stimuli to get greater grades, but they are quite subtle. The first is one need almost all 5s to receive the degree with honours, but who needs that? The second is 20% increment to the scholarship, which amounts not as much as one can desire. I have all excellent grades and receive some personal Sberbank scholarship, and totally it is about €100 per month. So, this is not a stimulus.

Well, one can ask, why do the students study now, if the courses are far from perfect? The answer is the conscription. In Russia, while you keep studying, you have a delay. If you fail at an exam, you get expelled and go to the army. Obviously, nobody wants to go to the Russian Army. So, everybody can learn a bit to pass an exam. Our point is to motivate students this way: if you have lousy grades, instead of summer holidays you move to a military camp. Better grades you get, less term you should serve. Thus, students WILL get good grades! But it is hard to get them, because professors loose their money. It is kind of a dual problem.

Surely, the model is way rough and could not be applied directly. Moreover, it is too funny to be taken seriously, though, as Russian proverb says, every joke contains a bit of truth.

On MRF factorization

2010-01-28T22:51:00.005+03:00

Recently, I figured out I didn't understand two simple things about MRFs:

When we are talking about MRF factorization, in the formulation of the likelihood
should we consider all the cliques in the network or only maximal ones?
Generally, why do we have a right to factorize the likelihood this way?

I asked some folks, and it turned out that nobody understood this basic property clearly (In spite of Dmitry Vetrov assured me he had explained that fact in his courses). Finally, I've found the answers in Christopher Bishop's book. If you are not familiar with Markov Random Fields or graphical models, I recommend you to read the book, it is relatively understandable.

So, let's start with the second question. For those of you who like names, it is exactly the necessity part of the Hammersley-Clifford theorem. As Bishop put it:

If we consider two nodes x_i and x_j that are not connected by a link, then these variables must be conditionally independent given all other nodes in the graph. This follows from the fact that there is no direct path between the two nodes, and all other paths pass through nodes that are observed, and hence those paths are blocked. This conditional independence property can be expressed as
where x_\{i,j} denotes the set x of all variables with x_i and x_j removed. The factorization of the joint distribution must therefore be such that x_i and x_j do not appear in the same factor in order for the conditional independence property to hold for all possible distributions belonging to the graph.

One could find the answer to the first question in Bishop's book as well. Normally, we should include all the cliques to the product. Actually, every function of variables X is also a function of any Y that is a superset of X. Based on that, a potential for a non-maximal clique could be merged into a potential for any maximal clique such that it is a supergraph of the first clique! Thus, both formulations (with all cliques and only maximal cliques) are equally expressive.

On image labelling

2010-01-23T20:42:00.005+03:00

Labelling data is a labourous side task that arises in most computer vision projects. Since the developers usually don't want to spend their time for such a dumb work, there exist a number of workarounds. Let me enumerate some I've heard of:

At Academia, the task of labelling is usually being endured on [PhD] students' broad shoulders. The funny part is the students are not always enrolled in the relevant project. At Graphics & Media Lab, students who have not attended enough seminars by the time of revision, should label some data sets for the lab projects.
One could also hire some people to label her data. Since the developers/researchers are relatively high-paid, it is economic to hire other folks (sometimes, they are students as well). UPDATE: hr0nix mentioned in the comment that there exists the Mechanical Turk service that helps requesters to find contractors.
The more witty way is to use applied psychology. For example, Google transformed the labelling process to the game. During the gameplay, you and your randomly chosen partner tag images. Sooner you tag an image with the same tag, more points you get. The brilliant idea! Believe or not, when I first saw it, I was carried away and could not stop playing until my friends dragged me out for a pizza!
The most revolutionary approach was introduced by Densey Tan. Here is a popular explanation of what he has done. The idea is to capture labels straight from one's brain using EEG/fMRI/whatnot. Now they can perform only 2 or 3 class labelling, but (I hope) it is only the beginning.

The last point reminds me my old thoughts about the future of machine learning (or at least ML applied to Vision). Nowadays we deal with ensembles of weak classifiers, such as decision trees, stamps etc. One can use guinea pigs as weak classifiers! I suppose their brain is developed enough to understand 3d structure of the scene in the way human brain does, while modern computer vision systems lack for this ability. The animals are to be learned, for example, by experiencing an electric shock in case of wrong answers. Now, it is not obligatory to train "experts", it is sufficient to analyse their brain activity. Isn't it a breakthrough? :)

OpenCV bindings

2010-01-22T23:27:00.008+03:00

If you are a computer vision researcher or an engineer, you cannot miss OpenCV library. Even if you are not, it could be useful to you. For example, here is a funny application: camera shots a programmer's face when a merge fails. If you are not familiar with the library, I recommend you to look through the list of its features on Wikipedia.

OpenCV is written in C to be extremely portable (for example, to DSP). The fact is C is not very popular nowadays. The recent release 2.0 contains (besides the other decent stuff) also C++ and Python wrappers. What about the other languages?

There are a number of C# wrappers. The most known is EmguCV, which is reported to be the only C# wrapper that supports OpenCV 2.0 (actually, I don't now what it means, but I suppose the API should correspond the C++ interface). It is distributed under GPL or the "Commercial License with a small fee".

As for Java, JavaCV seems to be the only viable wrapper. It also contains wrappers for other popular libraries like FFmpeg. It is also distributed under GPL, but the author promised to discuss weakening it if needed.

OpenCV was being supported by Intel, but it became a FOSS project recently. They are also going to participate in Google Summer of Code. If they will succeed, you might try to apply. I think it is a nice experience to develop such a popular library and be paid for it. :)

One of the fields they want to develop is augmented reality support for Android operating system. When I get known that there is an AR API in Android, I decided to try it. So, this is going to be a good opportunity!

UPD (Aug 6, 2011). There appeared a Haskell (!) wrapper for OpenCV by Noam Lewis.

Also, OpenCV folks are developing the official Java wrapper. Looking forward to use it!

Computer Vision: Fact & Fiction

2010-01-17T14:30:00.006+03:00

I was surfing the web today and came upon Stanford CS 223B course (Introduction to Computer Vision), which is said to be fucking hard. The first course homework is to watch the series of films "Computer Vision: Fact & Fiction" where computer vision stars (like David Forsyth and Andrew Zisserman) analyse computer vision technologies featured in Hollywood movies. The videos require no background in Vision and might be interesting to everyone. To me, it is also interesting to see how the famous vision folks look and talk.

My friend Tolya Yudanov spoke about that to talk about realistic in The Terminator movie is like "arguing about physical correctness of animé. Terminator is the complex AI of the future, and it is stupid to apply modern computer vision criteria to it." So, it is a good illustration of the concept of computer blindness. I encourage you to watch the videos, they are worth watching.

The disruption of scholarly publishing [in Russia]

2010-01-15T10:39:00.006+03:00

You know, I am relatively new to the big science. The first 2-column paper I read was Antonin Guttman's paper about R-Trees.¹ It was about 2.5 years ago. So, I've never used published journals or conference proceedings. I have been wondering why do they spend money to printing journals if the researchers usually publish their papers on their home pages. Recently, I've read the article about the disruption of scholarly publishing by Michael Clarke. The article is quite dragged out, so I summarize its ideas in the following paragraphs.

When Tim Berners-Lee came up with the idea of WWW in 1991, he thought of its purpose as some kind of scientific media, which would replace conferences and journals. Nowadays, the Internet is used for social networking, illegal distribution of music and pornography, but we still have journals and conferences off-line. Why?

The author indicates 5 main points:

Dissemination - journals distribute papers all over the world
Registration of discovery - to know who was the first, Popov or Marconi
Validation - to ensure that the results are correct; now provided by peer-review
Filtration - you are likely to read a paper from the journal with bigger impact factor
Designation - if you have publications on top conferences, you might be a cool scientist

The author argues that only the last point is critical for the modern system of journals and conferences. The others could be better handled with on-line services, we already have a lot of examples.

But in Russia, we don't rank scientists according to their citation index!² (because we don't have one :) ) So, the designation problem is not solved here, and Russia is already ready to the new publishing system. Why do we still have journals? I don't know, probably the sluggishness of minds...

¹ Actually, I had read this paper about Google before, but it accidentally was not 2-column formatted. :)
² I am cunning a bit: some journals carry out designation purposes. I mean journals published by VAK. One should have at least one publication in such a journal to get Candidate of Science degree (Russian PhD equivalent). But the review process is usually lousy, there was also Rooter case with one of them.

Testing machine learning algorithms

2010-01-12T02:50:00.004+03:00

Tests are the only way to estimate the quality of a machine learning algorithm in practice. In order to prove your algorithm is usable, you need to design good tests. To design test you should collect the data and split them into the train set and the test set.

Machine learning theorists say that the train and the test sets should come from the single probability distribution (unless they are talking about transfer learning or some kinds of on-line learning). But in practice it is a bit more complicated. We are currently working on the problem of laser scan points classification. It is not a trivial task to design tests! We have scans from different domains (aerial scans, scans from moving vehicles, stationary terrestrial scans), and for each domain we would like to have kind of universal benchmark. It means that a wide range of algorithms are supposed to be tested with the test, so the test may not stimulate overfitting.

So, how can we split the data? To satisfy the claim of the single distribution, we can add the odd points from the cloud to the train set and even points to the test set. This is a bad idea. Suppose your classifier use 3D coordinates of a point as the features. For each point in the test set, we have a similar point in the train set. Therefore we get nearly 100% precision using such a primitive learner. Such benchmark is not enough challenging.

Well, let's split every scan into a few pieces then. If we compose the test set from different subscans, does it solve the problem? Not at all. For example, we have a number of aerial scans. The scans can be retrieved from different heights, different scanners, in different weather. So, if we add the pieces of a single scan both to the test set and to the train set, we will get a non-challenging test again. The rule is: the pieces of a single scan may not persist both in the test set and the train set, if we want to train the classifier once for the whole domain. Do the test set and the train set come from the single distribution? No! But we need to neglect the theory in favour of practice.

One could say that it is reasonable to use cross-validation here. Well, it makes a sense. According to Wikipedia, there are three types of cross-validation:

Repeated random sub-sampling validation
K-fold cross-validation
Leave-one-out cross-validation

According to the rule, only k-fold x-validation can be used, and each fold should contain points from its own scans. But it is very laborious to label scans. It takes more than 20 hours to label a standard million-points scan. So, we cannot have a lot of scans labelled.

This is not the only problem with testing point classification. Since the single point does not tell us anything, we should consider some neighbourhood of it, and approximate it with a surface. For every point in both sets there should be some neighbourhood. The problem is solved too you put the whole scan to the set.

Mendeley: the reference management software

2009-12-27T14:55:00.005+03:00

Yesterday, a friend of mine Dmitry Konstantinov told me about Mendeley. His problem was he had got a lot of papers within his computer and needed to handle them efficiently. After digging the Internet, he found Mendeley reference management system. The system allows you to sort papers, extract the title, abstract, authors, and references from textual PDFs, automatically retrieve meta-information about them from services like CiteSeer^x, annotate papers and even their paragraphs, tag papers, flag them as read/favourite etc. Full text search across all your library is very convenient too.

The project is based in London, and share some management with Last.fm. Unsurprisingly, they have a social network upon all that. You can share you paper collections, upload your articles, synchronize your library with Mendeley Web. A user has up to 500 Mb space on servers. Now I see, where the idea of SciPeople, Russian scientific network, comes from. I don't know if such networks are the future of science, but they are, however, worth paying attention.

My profile.

Science vs. Industry

2009-12-26T21:35:00.008+03:00

Yesterday I was called by an HR officer from NetCracker, my former employer. She told me they "have a lot of new activities", so now they "fulfil repeated recruiting" and suggested to return to NetCracker. It is really funny, because 1.5 years ago they told me that according to the corporate policy it was impossible to employ somebody who had left the company once. I politely rejected them, but the talk refreshed my memories about previous hesitations.

When I switched the company to Graphics & Media Lab, it was a hard decision. That time I firmly decided to prefer scientific career over industrial. I considered a lot of pros and cons to make the decision. Although they are often personal, I'd like to share my observations with you.

Advantages of research work:

When you work as a researcher, you invent something new instead of just coding different stuff. This job is creative, not just constructive.
When you work as a programmer, you result is just a code. You don't publish papers, no one knows about your results. Moreover, they are often proprietorial.
If you work as an office worker or a manager, you could be paid a lot of money, but you are supposed to work 24x7. It really sucks because you do really annoying paperwork or participate in meetings, but do not produce anything substantial. If you have a lot of money, you have no time or desire to spend them to anything interesting. That's the reason why my roommate Andrey Korolev left Shell.
When you work as a scientist, you should not learn all the boring technologies. You can't be a prominent Java programmer without knowing heaps of jXxx libraries, a number of frameworks and without having some useless certificates. Besides, your knowledge could be narrow, they are restricted by your employer's needs.
Scientists are mobile: they move from one university to another. Some universities do not prolong contracts with professors, even if they are very cool. For me, it seems boring to live all the life in one place. (Though you could be sent to business trips while you work at some big corporation)
If you work at university, you might have a teaching experience of some kind, which is useful for you, if you use it properly.

Advantages of industrial work:

The main advantage is a good salary. :) If you are not a complete geek, it does matter. Science is usually funded by grants, which is unstable.
Since your employer needs profit, you do something practical. You can be sure that you don't investigate some abstract stuff that will never be applied.

Trust or not, our lab combines advantages of both directions. We usually work on projects ordered by customers who pay for it. Of course, we select only those projects, in which we can get some scientific results. Actually, it is done automatically, because it is not profitable for a customer to pay us for coding. That's how applied science should work, I think.

Hello, world!

2009-12-25T03:17:00.001+03:00

Well, I've just started my technical/research blog.

Why?

I already have a personal blog, which is (I hope) used to be read by a number of my friends. In recent time I noticed that I had begun post a lot of technical stuff my friends were not interested in. Also, that blog is in Russian, which limits its audience. So, I preferred not to change the blog policy but create a new blog. It was also Boris Yangel's amazing blog that inspired me to create mine.

Computer blindness?

Well, yes. Folks who know me might already divine that the blog is primarily about computer vision, and they are certainly right. I chose such a fancy name because computer vision is somewhat disappointing. Let me explain.

Do you remember that story when Marvin Minsky at MIT asked his student to teach a computer understand the scene retrieved from a camera during the 1966 summer break? Unsurprisingly, the student failed. Moreover, the general task is far from being solved even now. That days computers were slow, and AI scientists thought that performing logical inference is way more complicated than just scene analysis. Now, we have Prolog and a pile of different verification systems (thanks to the university curriculum -- we used some of them), but a computer is not able to recognize even simple object categories on different classes of images (e.g. relatively robust face detection was done only in early 2000s by Viola and Jones).

Actually, not only Minsky was misled. If you are a vision researcher, when you tell people about your research, they are likely to reply: "Is that all you can? Man, it's simple!" Sure, it is simple for you to figure out that it is a cow on the meadow, not a horse, but try to explain it to computer! It is actually a problem in our lab: when vision guys try to defend a Masters/PhD thesis in front of the committee (which consists of folks who do research in computer hardware, system programming etc), and the committee is usually not impressed by the results, because they think it is not too difficult.

Okay, you've got the point. Computers are blind, and we should cope with that.

Next. Do you know, what's the difference between computer vision of 1980s and modern computer vision? In 80s, they used to solve particular problems, not general ones. They could implement quite a decent vision system that performed its task, but it could not be transferred to another domain. Nowadays, such approach is no more scientific, while it is still good for engineers. Today, computer vision science is about general tasks. It became possible because of extensive using of machine learning methods (a lot of them were developed in '90s). Vision is nothing without learning now. I hope you've got this point too: Vision + Learning = Forever Together. That's why my blog cannot ignore machine learning issues.

What else? Programming language is a tool, but it can be interesting per se. I am about to finish a 5-year university programme in Computer Science, so I have been being taught different language concepts and programming paradigms, and I find it interesting sometimes. That is another possible topic.

Finally,

Subscribe me, read me and comment me. Everybody is welcome! Let it roll!