Submodular functions can be exactly minimized in polynomial time, and the special case that graph cuts solve with max flow KZ:PAMI04 has had significant impact in computer vision BVZ:PAMI01,Kwatra:SIGGRAPH03,Rother:GrabCut04 . In this paper we address the important class of sum-of-submodular (SoS) functions Arora:ECCV12,Kolmogorov:DAM12 , which can be efficiently minimized via a variant of max flow called submodular flow Edmonds:ADM77 . SoS functions can naturally express higher order priors involving, e.g., local image patches; however, it is difficult to fully exploit their expressive power because they have so many parameters. Rather than trying to formulate existing higher order priors as an SoS function, we take a discriminative learning approach, effectively searching the space of SoS functions for a higher order prior that performs well on our training set. We adopt a structural SVM approach Joachims et al 09a,Tsochantaridis et al 04 and formulate the training problem in terms of quadratic programming; as a result we can efficiently search the space of SoS priors via an extended cutting-plane algorithm. We also show how the state-of-the-art max flow method for vision problems Goldberg:ESA11 can be modified to efficiently solve the submodular flow problem. Experimental comparisons are made against the OpenCV implementation of the GrabCut interactive segmentation technique Rother:GrabCut04 , which uses hand-tuned parameters instead of machine learning. On a standard dataset Gulshan:CVPR10 our method learns higher order priors with hundreds of parameter values, and produces significantly better segmentations. While our focus is on binary labeling problems, we show that our techniques can be naturally generalized to handle more than two labels.
In this paper, we will learn submodular discriminant functions. Prior work on learning submodular functions falls into three categories: submodular function regression @cite_11 , maximization of submodular discriminant functions, and minimization of submodular discriminant functions.
@cite_11
340337472
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications that have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we use a learning theoretic angle for studying submodular functions. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing both extremal properties as well as regularities of submodular functions, of interest to many areas.