Summary
The course presents various existing optimization techniques for such important machine learning tasks, as inference and learning for graphical models and neural networks. In particular, it addresses such topics as combinatorial algorithms, integer linear programs, scalable convex and non-convex optimization and convex duality theory. Graphical models and neural networks play a role of working examples along the course. The goal of the course is to give a strong background for analysis of existing, and development of new scalable optimization techniques for machine learning problems.
Schedule and Information
The lectures and exercises will be given in English.
Venue: Mathematikon B: Berliner Str. 43, 3rd floor, seminar room B128. Simply
ring the bell "HCI am IWR" to open the front door.
- Lecture: Tue, 11:15 – 12:45, Mathematikon B, Berliner Str. 43, SR B128, the first lecture will be given on October 16
- Lecture: Wed, 11:15 – 12:45, Mathematikon B, Berliner Str. 43, SR B128
- Exercises: Wed, 09:15 – 10:45, Raum: Mathematikon B, Berliner Str. 43, SR B128, the first exercise will take place on October 24
Contact for lectures: Dr. Bogdan Savchynskyy
Contact for exercises: Stefan Haller
The seminar Combinatorial Optimization in Computer Vision and Machine Learning complements this lecture by taking a closer look at recent results and developments. We highly recommend it to all students interested in the topic.
Registration
Please register for the course in Müsli.
Course Material
Lecture notes, slides and exercise sheets are available for download.
Thanks to Bálint Csanády, for some lectures there exists a video recording. We will update this page as soon as they become available. Use the username "optml" when prompted.
- 2018-10-16: Not available.
- 2018-10-17: Acyclic Graphical Models, Dynamic Programming
- 2018-10-23: Optimization problems, Relaxations, Polytopes
- 2018-10-24: Convexity, Linear Programs
- 2018-10-30: Integer Linear Programs, Integer Hull, LP relaxation
- 2018-10-31: MAP-inference as ILP
- 2018-11-06: Convex Analysis: extended value functions, convex functions
- 2018-11-07: Convex Analysis: subgradient and piecewise linear functions
- 2018-11-13: Lagrange duality
- 2018-11-14: Lagrange relaxation of ILPs, reparametrization, optimality conditions
- 2018-11-20: Lagrange duality for MAP-inference: reparametrization, dual rounding
- 2018-11-27: Arc-consistency, relaxation labeling, arc-consistency for acyclic graphs
- 2018-11-28: Basics of convex optimization
- 2018-12-05: ICM, block ICM, dual subgradient methods
- 2018-12-11: Min-sum diffusion. Empirical comparison of algorithms
- 2018-12-12 (01): Dynamic programming as anisotropic diffusion, TRW-S
- 2018-12-12 (02): Lagrange decomposition: grid-graph, general graphs, primal problem
- 2018-12-18: Equivalence of all acyclic decompositions. Maximization of decomposition-based dual: sub-gradient and subproblem averaging.
- 2018-12-19: TRW-S/SRMP Algorithm derivation. Comparison of algorithms based on different decompositions
- 2019-01-08: Sub-modularity. Submodular energy minimization
- 2019-01-09: Binary and multilabel submodular energy minimization as min-cut
- 2019-01-15: Move-making algorithms
- 2019-01-16: Binary LP relaxation as min-cut
- 2019-01-22: Persistency, Fusion Moves. Comparison to dual algorithms
- 2019-01-29: Learning problem: training set (fully and partially annotated images), loss function, discriminative formulation, StructSVM, hinge loss
- 2019-01-30: Subgradient and stochastic gradient methods. Linear StructSVM: cutting plane method
Exercises
Deadline submission exercise 4: 2019-02-10
Table of Contents
I Graphical Models
- Acyclic Graphical Models. Dynamic Programming
- Background: Basics of Linear Programs and Their Geometry
- Inference in Graphical Models as Integer Linear Program
- Background: Basics of Convex Analysis and Convex Duality
- Duality of the LP Relaxation of Inference Problem
- Background: Basics of Convex Optimization
- Sub-Gradient and Block-Coordinate Ascent for Inference in Graphical Models
- Lagrangian (Dual) Decomposition
- Min-Cut/Max-Flow Based Inference
- LP Relaxation of Inference Problem as st-Min-Cut Problem
- Summary: Inference Algorithm Selection
II Neural Networks
- Overview of Architectures
- Stochastic Gradient for Training Neural Networks
III Joint Learning of Graphical Models and Neural Networks
- Structured Risk Minimization for Graphical Models
- CRF+CNN Models: Joint Training of Graphical Models and Neural Networks.