|M. Pawan Kumar|
IMPROVED MOVES FOR TRUNCATED CONVEX MODELS
M. Pawan Kumar, O. Veksler and P. Torr
In Journal of Machine Learning Research (JMLR), 2011
We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-mincut based move making algorithms which we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of $\alpha\beta$-Swap and $\alpha$-Expansion respectively which fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (i.e. an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (LP) relaxation. Compared to previous approaches based on the LP relaxation, e.g. interior-point algorithms or tree-reweighted message passing (TRW), our methods are faster as they use only the efficient st-mincut algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems.