Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation
We consider energy minimization for undirected graphical models, also known as the MAP-inference problem for Markov random fields. Although combinatorial methods, which return a provably optimal integral solution of the problem, made a significant progress in the past decade, they are still typically unable to cope with large-scale datasets. On the other hand, large scale datasets are often defined on sparse graphs and convex relaxation methods, such as linear programming relaxations then provide good approximations to integral solutions. We propose a novel method of combining combinatorial and convex programming techniques to obtain a global solution of the initial combinatorial problem. Based on the information obtained from the solution of the convex relaxation, our method confines application of the combinatorial solver to a small fraction of the initial graphical model, which allows to optimally solve much larger problems. We demonstrate the efficacy of our approach on a computer vision energy minimization benchmark.
Summary: The paper considers MAP inference in 
      pairwise MRFs, a problem that is generally NP-hard. The central idea 
      is to decompose the problem into two almost disjoint problems, except 
      for boundary variables, these are variables that are included in both 
      node sets. The central theorem of the paper says that if the two optimal 
      solutions given by solving both problems independently agree on 
      the boundary, then the overall problem is solved to optimality. The 
      authors introduce an algorithm that initially determines a 
      decomposition of the graph into two sets with a common boundary (based 
      on arc consistency) and then solves the larger set with LP based 
      approaches and the smaller problem with exact combinatorial solvers 
      (but possibly very expensive; integer programming solvers). If the 
      solutions on the boundary don't agree or the LP-based approach leads 
      to a fractional solution, then some variables are determined with a 
      heuristic to be included in solving with the combinatorial method. 
      This procedure is reiterated till the solution agrees on the boundary. 
      Pros: - Simple idea. - Clearly written paper. - Seems 
      to give optimal solutions for problems that have not been solved before 
      (did not double-check this claim in detail). - Nice property that 
      the LP part of the problem does not need to be resolved, when the 
      combinatorial set is increased. - Hardens the evidence that many MAP 
      inference problems are solved almost exactly by LP relaxations. 
      Cons: - Most of the statements in the paper are relatively 
      trivial, especially the main theorem. - I would have appreciated a 
      possible comparison to cutting plane approaches that tighten the local 
      marginal polytope with additional constraints e.g. by Sontag et al. 
      UAI 2008. Software is available so it should be relatively 
      straightforward to compare. It might be that the solvers are too slow, 
      in this case I would have appreciated a remark about this. - The 
      paper is very short on explanations/theory on why the heuristic presented 
      in the paper should work, it is mostly motivated by the empirical 
      observation that LP solvers do a good job on many problems. - I 
      find the experiments lacking: the authors do not described the exact form 
      of the potentials they used in the experiments for the Middleburry 
      dataset (Potts, l1, l2, truncated ?). Does the quality of the 
      solutions of the proposed algorithm somehow get influenced by the form 
      of the potentials? Quality: Theory is rather simple. 
      Experiments do not match my expectations. Clarity: The paper 
      is well written and easy to understand. The main idea is well 
      presented, I would have hoped to get a better understanding in which 
      situations the authors would expect the method to work well. 
      Originality: Theorem 3.0.1 and 3.0.2 are relatively trivial, 
      otherwise few original ideas except for the combination of 
      combinatorial and LP-based approaches. Significance: The paper 
      might be significant in the sense that for a few more MAP problems the 
      research community knows the optimal labeling. It is however hard to 
      judge from the paper how practical and relevant the method is for the 
      bulk of MAP problems. Minor points: 067: to a convex and a 
      combinatorial solver (no s!) 069: . in the end 060: Figure 1 is 
      not very illustrative, what's the difference between the figure on the 
      left and right, why is this useful? You should explain this in the 
      caption. 099: ofthe 192/210: Improve numbering of remarks / 
      theorems (just one digit) 256: Let x by a solution... 305: had to 
      serve (why is that? use serve if you decided so) 270: would appreciate 
      an energy comparison to the solution obtained by TRW-S 322: This might 
      not be the final number of variables you would need to solve for! 
      368: multiway-cut problem 370: for which the optimal 377: 
      performance of our method 400: can be solved an order