The proximal problem for structured penalties obtained via convex relaxations of submodular functions is known to be equivalent to minimizing separable convex functions over the corresponding submodular polyhedra. In this paper, we reveal a comprehensive class of structured penalties for which penalties this problem can be solved via an efficiently solvable class of parametric maxflow optimization. We then show that the parametric maxflow algorithm proposed by and its variants, which runs, in the worst-case, at the cost of only a constant factor of a single computation of the corresponding maxflow optimization, can be adapted to solve the proximal problems for those penalties. Several existing structured penalties satisfy these conditions; thus, regularized learning with these penalties is solvable quickly using the parametric maxflow algorithm. We also investigate the empirical runtime performance of the proposed framework.
The sufficient condition in is closely related to the class of energy minimization problems solvable by graph-cut algorithm @cite_3 @cite_37 . Energy minimization is a formulation of the maximum a posteriori (MAP) estimation on MRFs (see, for example, @cite_52 ). Similar results are found in the context of realization of a submodular function as a cut function in combinatorial optimization @cite_43 @cite_7 .
@cite_37 @cite_7 @cite_52 @cite_3 @cite_43
2101309634 2000478304 2120340025 2143516773 2021902776
In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available. Abstract We consider the problems of realizing set functions as cut functions on graphs and hypergraphs. We give necessary and sufficient conditions for set functions to be realized as cut functions on nonnegative networks, symmetric networks and nonnegative hypernetworks. The symmetry significantly simplifies the characterization of set functions of nonnegative network type. Set functions of nonnegative hypernetwork type generalize those of nonnegative network type (cut functions of ordinary networks) and are submodular functions. For any constant integer k⩾2 , we can discern in polynomial time by a max-flow algorithm whether a given set function of order k is of nonnegative hypernetwork type. The formalism of probabilistic graphical models provides a unifying framework for capturing complex dependencies among random variables, and building large-scale multivariate statistical models. Graphical models have become a focus of research in many statistical, computational and mathematical fields, including bioinformatics, communication theory, statistical physics, combinatorial optimization, signal and image processing, information retrieval and statistical machine learning. Many problems that arise in specific instances — including the key problems of computing marginals and modes of probability distributions — are best studied in the general setting. Working with exponential family representations, and exploiting the conjugate duality between the cumulant function and the entropy for exponential families, we develop general variational representations of the problems of computing likelihoods, marginal probabilities and most probable configurations. We describe how a wide variety of algorithms — among them sum-product, cluster variational methods, expectation-propagation, mean field methods, max-product and linear programming relaxation, as well as conic programming relaxations — can all be understood in terms of exact or approximate forms of these variational representations. The variational approach provides a complementary alternative to Markov chain Monte Carlo as a general source of approximation methods for inference in large-scale statistical models. Many tasks in computer vision involve assigning a label (such as disparity) to every pixel. A common constraint is that the labels should vary smoothly almost everywhere while preserving sharp discontinuities that may exist, e.g., at object boundaries. These tasks are naturally stated in terms of energy minimization. The authors consider a wide class of energies with various smoothness constraints. Global minimization of these energy functions is NP-hard even in the simplest discontinuity-preserving case. Therefore, our focus is on efficient approximation algorithms. We present two algorithms based on graph cuts that efficiently find a local minimum with respect to two types of large moves, namely expansion moves and swap moves. These moves can simultaneously change the labels of arbitrarily large sets of pixels. In contrast, many standard algorithms (including simulated annealing) use small moves where only one pixel changes its label at a time. Our expansion algorithm finds a labeling within a known factor of the global minimum, while our swap algorithm handles more general energy functions. Both of these algorithms allow important cases of discontinuity preserving energies. We experimentally demonstrate the effectiveness of our approach for image restoration, stereo and motion. On real data with ground truth, we achieve 98 percent accuracy. Abstract The problem of maximizing a pseudoboolean function (or equivalently a set function) which is supermodular, has many interesting applications e.g. in combinatorial optimization, Operations Research etc. Up to now, a number of special cases of pseudoboolean functions have been known, the maximization of which can be converted into the search for a maximum flow in an associated network. These were essentially the so-called negative-positive pseudoboolean functions (which, as will be noted here, turn out to be supermodular). First it is shown here how these results on negative-positive functions can be more easily derived by using the concept of conflict graph . The conflict graph approach is then generalized to extend the class of problems amenable to maximum network flow problems to the whole set of cubic supermodular pseudoboolean functions.