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 meOffice: 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
- Sticky: Almost all of the announcements, homework postings, homework solutions, and electronic discussion for our class are going to be posted on canvas, and can be found at this link. However, do see the links below for the lecture slides.
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.- 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 | 9/30/2020 | 9/30/2020 | Logistics, Intro, Motivation, Applications. | See canvas. | |||
| 2 | 10/5/2020 | 10/5/2020 | Sums concave(modular), uses (diversity/costs, feature selection), information theory. | See canvas. | |||
| 3 | 10/7/2020 | 10/7/2020 | Monge, More Definitions, Graph and Combinatorial Examples | See canvas. | |||
| 4 | 10/12/2020 | 10/12/2020 | Graph and Combinatorial Examples, Matrix Rank, Properties, Other Defs, Independence | See canvas. | |||
| 5 | 10/14/2020 | 10/14/2020 | Properties, Many defs of Submodularity, Independence | See canvas. | |||
| 6 | 10/19/2020 | 10/19/2020 | Matroids, Matroid Examples, Matroid Rank, | See canvas. | |||
| 7 | 10/21/2020 | 10/21/2020 | Matroid Rank, More on Partition Matroid, Laminar Matroids, System of Distinct Reps, Transversals | See canvas. | |||
| 8 | 10/26/2020 | 10/26/2020 | Transversal Matroid, Matroid and representation, Dual Matroid, Other Matroid Properties, Combinatorial Geometries, Matroid and Greedy | See canvas. | |||
| 9 | 10/28/2020 | 10/28/2020 | Other Matroid Properties, Combinatorial Geometries, Matroid and Greedy, Polyhedra, Matroid Polytopes | See canvas. | |||
| 10 | 11/2/2020 | 11/2/2020 | Matroid Polytopes, Matroids to Polymatroids | See canvas. | |||
| 11 | 11/4/2020 | 11/4/2020 | Matroids to Polymatroids, Polymatroids | See canvas. | |||
| 12 | 11/9/2020 | 11/9/2020 | Polymatroids, Polymatroids and Greedy | See canvas. | |||
| 13 | 11/16/2020 | 11/16/2020 | Polymatroids and Greedy, Possible Polytopes, Extreme Points, Cardinality Constrained Maximization | See canvas. | |||
| 14 | 11/18/2020 | 11/18/2020 | Cardinality Constrained Maximization, Curvature | See canvas. | |||
| 15 | 11/23/2020 | 11/23/2020 | Curvature, Submodular Max w. Other Constraints, Start Cont. Extensions | See canvas. | |||
| 16 | 11/25/2020 | 11/25/2020 | Submodular Max w. Other Constraints, Cont. Extensions, Lovasz extension | See canvas. | |||
| 17 | 11/30/2020 | 11/30/2020 | Choquet Integration, Non-linear Measure/Aggregation, Definitions/Properties, Examples. | See canvas. | |||
| 18 | 12/2/2020 | 12/2/2020 | Multilinear Extension, Submodular Max/polyhedral, Most Violated Ineq., Matroids Closure/Sat | See canvas. | |||
| 19 | 12/7/2020 | 12/7/2020 | Fund.\ Circuit/Dep, SFM, L.E.\ primal, Start SFM via Min-Norm Point | See canvas. | |||
| 20 | 12/9/2020 | 12/9/2020 | support for min-norm, proof that min-norm gives optimal, computing min-norm vector in B_f, SFM | 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.