Optimization for Machine Learning

Lecturer: Dr. Bogdan Savchynskyy
Assistant: Alexander Kirillov

Lagrange decomposition The course consists of lectures and practical exercises and concentrates on optimization techniques for machine learning tasks, such as inference and learning for graphical models. The course contains 3 parts: first, we briefly review basic convex optimization techniques widely used in machine learning. The second part  is devoted to inference problem for graphical models: we consider a number of existing algorithms, show their connection and their analysis from optimization point of view. In the final third part we consider the parameter's learning of graphical models, both probabilistic and discriminative.

- 8.06 Next Monday, June 13, the lecture will in the Room APB-E040 instead of E007! See the lecture plan below for details.
-18.04 On April 18 there might be a lecture in the Room APB-E040 instead of exercises!
-17.03 The first lecture will be held on April 4 in Room APB-E040 !

: Monday 13:00-14:30, Room APB-E007 (except the first lecture, which will be held in E040), Wednesday, 11:10 - 12:40, Room APB-E001, Start: April 4, 2016
Exercises: Monday 13:00-14:30, Room APB-E040, Start:  April 18
Prerequisites: Good knowledge of mathematics (linear algebra, analysis)
Credits: 3/1/0, oral exam. Enrolment: jExam . Attendees: max. 60
Note: Lectures are given in English.
Script: PDF-Dowload
Software installation readme: Download


L01. APB-E040 04.04 Introduction. Graphical models and their applications. Inference problem. Statistical and probabilistic meaning. [slides]
L02. APB-E001 06.04 (Integer) Linear programs. Polyhedral viewpoint. Marginal polytope. [slides] [annotated slides]
L03. APB-E007 11.04 Local polytope. ILP formulation, LP relaxation. [slides]
L04. APB-E001 11.04 Dynamic programming for inference in graphical models [slides]
---E01. APB-E040 18.04 Use of general LP and ILP solvers for inference in graphical models. [exercise-sheet] [results-table] [supplement]
L05. APB-E001 20.04 Convex functions. Lagrange dual problem. [slides-1] [slides-2]
L06. APB-E007 25.04 Lagrange dual for the local polytope relaxation. [slides-1] [slides-2]
L07. APB-E001 27.04 KKT conditions, arc consistency, relaxation labeling algorithm [slides-1]
---E02. APB-E040 2.05 Lagrange Dual to the LP Relaxation. Dual LP (TRWS) vs. Naive Solver [exercise-sheet] [results-table] [supplement]
L08. APB-E001 04.05 Basics of convex optimization: gradient and sub-gradient methods. [slides-1] [slides-2]
L09. APB-E007 09.05 Basics of convex optimization: sub-gradient method and block-coordinate descent. Min-sum Diffusion. [slides-1]
L10. APB-E001 11.05 ICM Algorithm. Lagrangian (Dual) Decomposition. Tree agreement. [slides-1] [slides-2]
---E03. APB-E040 23.05 Coordinate descent/ascent and sub-gradient methods for energy minimization. [exercise-sheet] [results-table] [supplement]
L11. APB-E001 25.05 General subgraph-wise decompositions. Relation to Lagrange dual. Equivalence of all acyclic decomposition. [slides]
L12. APB-E007 30.05 Block-coordinate ascent for decomposition-based dual. TRW-S. [slides]
1.06 Dies Academicus
---E04. APB-E040 06.06 Empirical comparison of algorithms based on different acyclic decompositions [exercise-sheet] [supplement]
L13. APB-E001 8.06 Sub-modularity. Energy minimization as a min-cut problem. [slides] [annotated slides]
L13. APB-E040 13.06 Min-cut based inference algorithms: alpha-expansion, alpha-beta-swap. Multilabel submodular problems. [slides]
L14. APB-E001 15.06 Binary LP relaxation as min-cut. [slides]
L15. APB-E007 20.06 Fusion Moves. Partial optimality. Inference algorithm selection. [slides] [ICCV2015-Tutorial]
L16. APB-E001 22.06 Discriminative Learning. Structured SVM. Loss-augmented inference. [script]
---E05. APB-E040 27.06 Min-cut based algorithms [exercise-sheet] [results-table]
29.06 No lecture.
L17. APB-E007 04.07 Algorithms for Struct-SVM. Subgradient-based methods. [script]
L18. APB-E001 06.07 Algorithms for Struct-SVM. Stochastic subgradient and cutting plane methods. [script]
---E05. APB-E040 27.06 Use this time to finish your unfinished exercises
L18. APB-E001 13.07 Outlook. What we have learned [slides]
image links: crops, lake, tsukubaR, tsukubaL, tsukubaTrueDisp