Linear Programming Relaxation Based MAP Inference For Graphical Models

Probabilistic Graphical Models(PGMs)are widely used in computer vision,machine learning,pattern recognition bioinformatics and etc.It utilises graphical structures to factorise complicated joint distributions as summation of simpler local potentials or distributions,which results in a structured model.The maximum a posteriori(MAP)inference is the bottleneck when applying PGMs.Thus in various applications,e.g.image segmentation,classification and etc.,it is required that PGMs must have specific structure,which leads to efficient inference procedure.However,it has been shown that general PGMs are superior to PGMs with specific structures in various applications.In addition,several fundamental problems in computer science,such as graph matching problems,constraints satisfaction problems,travel salesman problems and etc.,can also be reformulated as PGM MAP inference problems.Thus efficient and effective PGM MAP inference algorithms is of important in both theory and applications.Our main contribution is as follows:(1)Recently,higher order graphical models draw more and more attention in various areas.Linear Programming Relaxation based methods are one of the most powerful tools for MAP inference over higher order graphical models.However,there are many redundant constraints and redundant computations in current based methods.To overcome this,we a new linear programming relaxation model,by using this model we are able to reduce the number of constraints without sacrificing the accuracy,and propose an efficient belief propagation framework with various redundant computations removed.The experiments on image segmentation,image matching and etc.show that our method is superior to the state-of-the-arts.(2)In image reconstruction,M-best problems and etc.,global constraints over random variables are required.Traditional approaches for these problems formulate global constraints as higher order potentials over all variables,which is intractable in general.Thus we proposed a class of constrained MAP inference problem,which can be used to model many important problems in computer vision,machine learning and combinatorial optimization.Unfortunately,it is required to solve NP-hard sub-problems for tradition approaches to solve the proposed model.Thus we proposed a novel Linear Programming Relaxation model,which can be solved in polynomial time.Theoretic analyis show that under certain conditions,the proposed LP relaxation is tight.(3)It is computationally expensive to use off-the-shelf solvers such as CPLEX to solve the proposed LP relaxation for constrained MAP inference.Thus we proposed an efficient augmented belief propgataion algorithm to solve the LP relaxation efficiently.The proposed belief algorithm consists of two parts.In the first part,we proposed an belief propagation algorithm for augmented belief propagation sub-problem;in the second part,an efficient binary search algorithm is proposed to optimize over the dual variable corresponding to additional constraints.Experiments show the the proposed belief propagation methods outperforms CPLEX and other specifically designed state-of-the-art solvers.(4)The feature matching problem is a fundamental problem in computer vision and pattern recognition.Traditional approaches with high accuracy often requires expensive computations.Here we extended the proposed LP relaxation for constrained MAP problems to feature matching problems,and by using the specifical structure of constraints,we propose a belief propagation scheme which exhibits the following advantages:(a)we offer a tighter relaxation of the original cost function than previous graphical-model-based approaches;and(b)our subproblems decompose into max-weight bipartite matching,which can be solved efficiently,leading to orders-of-magnitude reductions in execution time.Experimental results show that the proposed algorithm produces results superior to those of the current state-of-the-art.(5)Hyper graph matching problems have drawn attention recently due to their robustness to noise,outliers,rotation and scaling variation.We formulate hyper graph matching problems as constrained MAP inference problems in graphical models.Then we proposed a novel algorithm,in which the problem are decomposed into a(linear)bipartite matching problem and several belief propagation sub-problems?Bipartite matching can be solved by Hungarian,while the belief propagation sub-problem is further decomposed as sub-problems with optimal substructure.Then a newly proposed dynamic programming procedure is used to solve the belief propagation sub-problem.Experiments show that the proposed methods outperform state-ofthe-art techniques for hyper graph matching.