Computer Blindness

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:

... about the LHC:

... about Higgs boson:

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

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.

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]

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_i looping. 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).

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.

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.

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...

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.

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.

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.

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.

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