Jeffrey A. Bilmes
E E 596
Topics of current interest in signal and image processing. Content may vary from offering to offering. Prerequisite: permission of instructor.
Submodular Functions, Optimization, and Application to Machine Learning.
This class will be a thorough introduction to submodular functions. Applications of submodularity are vast, and include areas in in computer vision, constraint satisfaction, game theory, social networks, economics, information theory, structured convex norms, natural language processing, sensor networks, graphical models and probabilistic inference, and other areas of machine learning. Submodularity is a good model for cooperation, complexity, and attractiveness as well as for diversity, coverage, and information.
In this class, we will learn about a variety of properties of submodularity and supermodularity. Motivated by applications, we'll cover submodularity's definitions, its properties, the many operations that preserve submodularity, variants and extensions of submodularity, and certain special submodular functions, and computational properties. The goal of this section will be to develop a deep intuitive understanding of both submodular and supermodular functions.
Other topics we will overview include: the theory of matroids and lattices, polyhedral properties of submodular functions, subdifferentials and superdifferentials, the Lovasz extension (i.e., the Choquet integral) of submodular functions, and convex and concave extensions in general.
As for submodular optimization, we'll discuss submodular maximization algorithms in the unconstrained and constrained (i.e., knapsack, matroid, combinatorial, etc.) cases, the greedy algorithm and its uses, etc. For submodular minimization, we'll give a history of submodular minimization, including both numerical and combinatorial algorithms, computational properties of these algorithms, and descriptions of both known results and currently open problems in this area (as well as discuss both unconstrained and constrained cases).
Other problems we'll discuss include submodular cover problems, submodular flow problems, and the principle partition of a submodular function and its variants. We'll see, for example, how submodularity can be used to solve non-submodular problems, for example difference of submodular programs, and submodular relaxation strategies.
Student learning goals
General method of instruction
Class assignments and grading