Olga's CVPR paper

Posted in Labels: , , , , , , | at 10:33

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

Read Users' Comments (1)comments

Visual Assist's Tip of the Century

Posted in Labels: , , , | at 22:39

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.


Read Users' Comments (1)comments

Quantum Machine Learning

Posted in Labels: , , , , , , , | at 16:30

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!

Read Users' Comments (2)

University education reform

Posted in Labels: , , , | at 23:20

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.

Read Users' Comments (0)

On MRF factorization

Posted in Labels: , , , | at 22:51

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

  1. 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?
  2. 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 xi and xj 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 xi and xj removed. The factorization of the joint distribution must therefore be such that xi and xj 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.

Read Users' Comments (1)comments

On image labelling

Posted in Labels: , , , , , | at 20:42

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:

  1. 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.
  2. 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.
  3. 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!
  4. 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? :)

Read Users' Comments (2)

OpenCV bindings

Posted in Labels: , , , , , , , , , , , , , | at 23:27

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!

Read Users' Comments (0)

Computer Vision: Fact & Fiction

Posted in Labels: , , , , , | at 14:30

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.

Read Users' Comments (0)

The disruption of scholarly publishing [in Russia]

Posted in Labels: , , , , , , | at 10:39

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.1 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!2 (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...

1 Actually, I had read this paper about Google before, but it accidentally was not 2-column formatted. :)
2 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.

Read Users' Comments (2)

Testing machine learning algorithms

Posted in Labels: , , | at 02:50

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.

Read Users' Comments (9)

Subscribe to: Posts (Atom)