Title: Lazy Generic Cuts: Efficient MAP inference in Higher Order MRFs

Speaker: Dinesh Khandelwal

Abstract: LP relaxation based message passing and flow based algorithms are two of the popular techniques for performing MAP inference in graphical models. Generic Cuts (GC) (Arora et al. 2012) combines the two approaches to generalize the traditional max-flow min-cut based algorithms for binary models with higher order clique potentials. The algorithm has been shown to be exponentially faster than the state of the art. The time and memory complexity of Generic Cuts is linear in the number of constraints which in turn is exponential in the clique size. We propose a lazy version of Generic Cuts exploiting the property that in most of such inference problems, a large fraction of the constraints are never used during the course of the minimization. We start with a small set of constraints (called the active constraints) which are expected to play a role during the minimization. GC is then run with this reduced set allowing it to be efficient in time and memory. The set of active constraints is adaptively learnt over multiple iterations while guaranteeing convergence to the optimal for submodular clique potentials. Our experiments show that the number of constraints required by the algorithm is typically less than 3% of the total constraints. Our algorithm requires time and memory linear in the number of such constraints `actually' used.