EE563 - Submodular Functions, Optimization, and Applications to Machine Learning, Fall Quarter, 2020

This page is located at https://people.ece.uw.edu/bilmes/classes/ee563/ee563_fall_2020/.

An older version of this class was taught previously, and its contents, slides, and YouTube videos can be found at https://people.ece.uw.edu/bilmes/classes/ee563/ee563_spring_2014

Instructor:

Prof. Jeff A. Bilmes --- Email me
Office: 418 EE/CS Bldg., +1 206 221 5236
Office hours: TBD, EEB-418 (+ online)

Time/Location

Class is held: Mon/Wed 10:30-12:20, via Zoom. See canvas for the Zoom link.

Announcements


Submodular Functions, Optimization, and Applications to Machine Learning

Description: This class will be a thorough introduction to submodular functions.

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 ever important greedy algorithm and its uses. 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, 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.


Homework

Homework must be done and submitted electronically via the following link https://canvas.uw.edu/courses/1397085/assignments.
  1. See Canvas announcements

Lecture Slides

Lecture slides will be made available as they are being prepared --- they will probably appear soon before a given lecture, and they will be in PDF format (original source is latex). Note, that these slides are corrected after the lecture (and might also include some additional discussion we had during lecture). If you find bugs/typos in these slides, please email me. The slides are available as "presentation slides" and also in (mostly the same content) 2-up form for printing. After lecture, the marked up slides will appear under the "presented slides" column (and might include typo fixes, ink corrections, and other little notes/discussions/drawings that occured during class).
Lec. # Slides 2-Up Slides Lecture Date Last Updated Contents Presented Slides Video
1 pdf pdf 9/30/2020 9/30/2020 Logistics, Intro, Motivation, Applications. pdf See canvas.
2 pdf pdf 10/5/2020 10/5/2020 Sums concave(modular), uses (diversity/costs, feature selection), information theory. pdf See canvas.
3 pdf pdf 10/7/2020 10/7/2020 Monge, More Definitions, Graph and Combinatorial Examples pdf See canvas.
4 pdf pdf 10/12/2020 10/12/2020 Graph and Combinatorial Examples, Matrix Rank, Properties, Other Defs, Independence pdf See canvas.
5 pdf pdf 10/14/2020 10/14/2020 Properties, Many defs of Submodularity, Independence pdf See canvas.
6 pdf pdf 10/19/2020 10/19/2020 Matroids, Matroid Examples, Matroid Rank, pdf See canvas.
7 pdf pdf 10/21/2020 10/21/2020 Matroid Rank, More on Partition Matroid, Laminar Matroids, System of Distinct Reps, Transversals pdf See canvas.
8 pdf pdf 10/26/2020 10/26/2020 Transversal Matroid, Matroid and representation, Dual Matroid, Other Matroid Properties, Combinatorial Geometries, Matroid and Greedy pdf See canvas.
9 pdf pdf 10/28/2020 10/28/2020 Other Matroid Properties, Combinatorial Geometries, Matroid and Greedy, Polyhedra, Matroid Polytopes pdf See canvas.
10 pdf pdf 11/2/2020 11/2/2020 Matroid Polytopes, Matroids to Polymatroids pdf See canvas.
11 pdf pdf 11/4/2020 11/4/2020 Matroids to Polymatroids, Polymatroids pdf See canvas.
12 pdf pdf 11/9/2020 11/9/2020 Polymatroids, Polymatroids and Greedy pdf See canvas.
13 pdf pdf 11/16/2020 11/16/2020 Polymatroids and Greedy, Possible Polytopes, Extreme Points, Cardinality Constrained Maximization pdf See canvas.
14 pdf pdf 11/18/2020 11/18/2020 Cardinality Constrained Maximization, Curvature pdf See canvas.
15 pdf pdf 11/23/2020 11/23/2020 Curvature, Submodular Max w. Other Constraints, Start Cont. Extensions pdf See canvas.
16 pdf pdf 11/25/2020 11/25/2020 Submodular Max w. Other Constraints, Cont. Extensions, Lovasz extension pdf See canvas.
17 pdf pdf 11/30/2020 11/30/2020 Choquet Integration, Non-linear Measure/Aggregation, Definitions/Properties, Examples. pdf See canvas.
18 pdf pdf 12/2/2020 12/2/2020 Multilinear Extension, Submodular Max/polyhedral, Most Violated Ineq., Matroids Closure/Sat pdf See canvas.
19 pdf pdf 12/7/2020 12/7/2020 Fund.\ Circuit/Dep, SFM, L.E.\ primal, Start SFM via Min-Norm Point pdf See canvas.
20 pdf pdf 12/9/2020 12/9/2020 support for min-norm, proof that min-norm gives optimal, computing min-norm vector in B_f, SFM pdf See canvas.
Lec. # Slides 2-Up Slides Lecture Date Last Updated Contents Presented Slides Video

Discussion Board

You can post questions, discussion topics, or general information at this link.