Minimizing Submodular Discrete Energies by Integer Reparameterizations

Dr. Tomas Werner (speaker)
Czech Republic, Czech Technical University
Michail I. Schlesinger
Ukraine, International Research and Training Centre of Information Technologies and Systems, National Academy of Science of Ukraine, Cybernetica Centre
For minimizing discrete energy functions (or MAP inference in graphical models with discrete variables), a successful and widely used approach
is the linear programming (LP) relaxation, first proposed by Schlesinger in the 1970s. We typically solve the dual LP, which maximizes a concave lower bound on the true minimum over reparameterizations of the problem. Unfortunately, no algorithm is known that would maximize this lower bound efficiently in finite time and scale up to large instances.
The LP relaxation is often exact, in particular, it is exact for submodular energies. However, submodular energies can be much more efficiently minimized by reduction to maxflow/mincut. Though very efficient, this approach has a methodological drawback: it has no direct relation to concepts such as reparameterizations, which have a clear meaning in the original graphical model. In other words, the maxflow algorithm is used as a black box with no clear relation to the pattern recognition original problem. We present a class of algorithms that minimize submodular energies in finite time and do not have this drawback, since they directly maximize the above lower bound by reparameterizations.