Markov random fields with unknown heterogeneous graphs

Markov Random Fields have been widely used in computer vision problems, for example image denoising, segmentation and human action recognition. The structure of the graph can be determined using human heuristics or domain knowledge, or can be learned from data when assuming graphs are homogeneous in topology. However, there are many applications for heterogeneous graphs. This research concentrates on estimating heterogeneous graphs and labels simultaneously from the observation. The joint estimation of graphs and labels is formulated into maximising a joint likelihood inference. Unfortunately, these inference problems are generally NP-complete, and we thus develop novel algorithms for effectively and efficiently finding approximate solutions. We also demonstrate how to learn Markov random field parameters from data with our inference techniques. Our contributions are as follows. First, we show that estimating graphs and performing maximum a posteriori inference can be achieved simultaneously by solving a bilinear programming problem, for which we provide a branch and bound solver. Second, we relax the inference problem into a tighter non-convex quadratic programming problem, and propose a convex-concave procedure algorithm to solve the non-convex quadratic programming. Third, we derive the partial-dual of a mixed integer programming relaxation of the inference problem, which admits a scalable message passing-style algorithm. Lastly, we show how to learn the parameters of Markov random fields with the structured max-margin training and the proposed inference algorithms. We evaluate the proposed algorithms on both synthetic data and real applications including human action/activity recognition and semantic image segmentation. Our inference algorithms usually outperform the state-of-the-art. Within our proposed algorithms, the quadratic programming algorithm often performs better than the bilinear programming and the message passing algorithms, while the message passing algorithm is the most efficient.Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2014