M. Pawan Kumar 
HOME

MAP ESTIMATION OF SEMIMETRIC MRFs VIA HIERARCHICAL GRAPH CUTS M. Pawan Kumar and D. Koller In Proceedings of Conference on Uncertainity in Artificial Intelligence (UAI), 2009 We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an stMINCUT problem. Unlike previous move making approaches, e.g. the widely used $\alpha$expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interiorpoint algorithms or treereweighted message passing, our method is significantly faster as it uses only the efficient stMINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms. [Paper] [Tech Report] [Poster] 