Numerous problems in machine learning and computer vision are discrete. As a complicating factor, they often involve large data sets and higher-order interactions between elements in the data. For example, segmenting an image into foreground and background requires assigning a label to each pixel in the image. As object and background commonly have significant wide-range coherency, the most probable label of a given pixel is not independent of the labels of other pixels. In general, if such interactions are important to a problem, it may be inappropriate to reduce it to efficiently solvable combinatorial problems like cuts in a neighborhood graph, because tractability frequently results from ignoring global interactions. This thesis addresses a class of combinatorial problems that admit high-order interactions between elements. The interactions take the form of a submodular set function over edges in a graph. In particular, the thesis introduces cooperative cuts whose cost function is not a sum of edge weights, but a submodular function on edges. We show that cooperative cuts generalize and enhance graph-based models and applications in machine learning and computer vision. The first part of the thesis studies theoretical and algorithmic questions, including upper and lower bounds on the approximation factor of the minimum cooperative cut problem. In addition to theoretical bounds, we empirically test the approximation algorithms on average and worst-case instances. The second part investigates the impact of coupling edges in graph cuts. Graph cuts are frequently used for representing functions and thereby offer a tool for minimizing those functions efficiently. Cooperative cuts widen the range of representable functions, and we employ them to define energy functions. An energy function characterizes a probabilistic model and determines the complexity of inference in this model. Although cooperative cut energies possess none of the commonly used properties that imply tractability, the algorithms from Part I solve the inference problem within a bounded approximation factor. Next, we explore an application. Cooperative cut energies encompass several recent models in the computer vision literature, and they establish the foundation for new models. In particular, the thesis introduces a new criterion for image segmentation that considers the homogeneity or congruity of the object boundary. This criterion remedies shortcomings of the popular graph cut method, notably, it preserves fine structures of the object even when the contrast is low. The next result is motivated by a corpus subset selection problem. Even though this problem corresponds to minimizing a submodular function and is solvable in polynomial time, the complexity of state-of-the-art exact algorithms is too high for large data sets. The observation that cooperative cuts can represent any submodular function is the key to a faster algorithm for minimizing submodular functions approximately. The third part of the thesis widens the scope and studies combinatorial problems with submodular cost functions in an online framework. Sequential decision problems ask to solve a problem repeatedly while an unknown cost function changes over time. The thesis proposes two generic Hannan-consistent algorithms building on the approximation methods discussed in Part I, and an algorithm for the subclass of ``label cost'' functions. The results generalize commonly studied linear loss functions and apply to a variety of problems.

@phdthesis{jegelka12thesis,
	author = {Stefanie Jegelka},
	school = {ETH Zurich},
	title = {Combinatorial Problems with Submodular Coupling in Machine Learning and Computer Vision},
	year = {2012}}