Machine Learning 1 (Winter Term 2020/2021)
Overview
-
Online course (2/2/0) consisting of:
- Video lectures published here on Mondays at 9:20am
- Assignments and self-study
- Q&A and discussion in a forum (OPAL)
- Interactive, with participation of Bjoern Andres, on Mondays, 9:20am - 11:10am
- Asynchronous, during the rest of the week
- Lecturer: Bjoern Andres
- Assistant: Mark Schöne
- Enrolment (OPAL). Additional rules for enrolment may apply, depending on the study programme.
- Creditable toward the modules CMS-CE-EL1, CMS-CE-EL2, CMS-CLS-ELG, CMS-CLS-ELV, CMS-COR-MLD, CMS-VC-ELG, CMS-VC-ELV1, CMS-VC-ELV2, INF-04-FG-IS, INF-B-510, INF-B-520, INF-B-530, INF-B-540, INF-BAS2, INF-BAS7, INF-E-3, INF-PM-FOR, INF-VERT2, INF-VERT7, INF-VMI-8, MCL-AI, MCL-PI
- Examinations: All students who wish to take an examination on the contents of this course need to carefully follow these instructions on time.
Contents
- Lecture notes
- Forum (OPAL)
-
Lectures
- Introduction (slides, video)
- Supervised learning (slides, video)
- Deciding
- Semi-supervised and unsupervised learning (slides, video)
- Classifying (slides, video)
- Partitioning (slides, video)
- Clustering (slides, video)
- Ordering (slides)
- Supervised structured learning (slides, video)
- Conditional graphical models (slides, video)
- Conditional graphical models II (slides, video)
- Conditional graphical models III (slides, video)
- Application: Clustering for Image Decomposition (slides, video)
- Application: Structured Learning for Pixel Classification (slides, video)
- Assignments
Related Literature
- Machine Learning Textbooks
Preparation
The following questions are similar in style to questions that are asked during the examination. They might be of help when preparing for the examination. We emphasize, however, that the examination is in no way constrained by, let alone limited to these questions.
-
Supervised learning
- What do you know about supervised learning?
- What is the purpose of a loss function? Give an example!
- What is the purpose of a regularizer? Give an example!
- What is the effect of making the regularization parameter larger?
- Suppose you have solved a supervised learning problem. How do you infer decisions for unlabeled data?
-
Deciding
-
Disjunctive normal forms (DNFs)
- What is a DNF?
- What are suitable regularizers for DNFs?
- How can you reduce the Set-Cover-Problem to the Length-m-DNF Problem?
- How can you show that exact learning of DNFs is NP-hard?
-
Binary decision trees (BDTs)
- What is a BDT?
- What are suitable regularizers for BDTs?
- How can you reduce the Exact-Cover-by-3-Sets Problem to the Depth-m-DNF Problem?
- How can you show that exact learning of BDTs is NP-hard?
-
Linear functions
- Which probabilistic assumptions are made in logistic regression?
- How can you derive the logistic loss function from these assumptions?
- What do you know about the learning problem in the special case of logistic regression?
- Describe an algorithm for solving this problem!
-
Disjunctive normal forms (DNFs)
-
Semi-supervised and unsupervised learning
- What do you know about semi-supervised/unsupervised learning?
- What is the learning and inference problem?
- Explain how the supervised learning problem is a special case of the learning and inference problem!
- How is the inference problem in unsupervised learning different from the inference problem in supervised learning?
- Give a (made-up or real-world) example of an unsupervised learning problem!
-
Classifying
- What do you know about classification?
- The lecture has introduced classification as a special case of the learning and inference problem. Explain how!
- What do you know about the learning problem for classification?
- What do you know about the inference problem for classification?
- How can you solve the inference problem for classification?
-
Partitioning and Clustering
- What do you know about partitioning?
- What do you know about clustering?
- What is a decomposition of a graph?
- What is a multicut of a graph?
- How can you encode any decomposition of a given graph in a binary vector of fixed dimension?
- How is partitioniong a special case of clustering?
- What is the difference between decision problems and clustering problems?
- What do you know about the learning problem in the special case of partitioning/clustering?
- What do you know about the inference problem in the special case of partitioning/clustering?
- How can you solve the inference problem in the special case of partitioning/clustering?
- How does the greedy joining algorithm work?
- How does the greedy moving algorithm work?
- Describe the technique of Kernighan and Lin!
-
Ordering
- What do you know about ordering?
- How can you encode any order of a given finite set in a binary vector of fixed dimension?
- What is the difference between decision problems and ordering problems?
- What do you know about the learning problem in the special case of ordering?
- What do you know about the inference problem in the special case of ordering?
- How can you solve the inference problem in the special case of ordering?
- How does the greedy transposition algorithm work?
- How can the technique of Kernighan and Lin be applied to this algorithm?
-
Supervised structured learning
- What is a factor graph?
- What does it mean for a function to factorize with respect to a factor graph?
- What is structured data?
- What is a conditional graphical model?
- What is the energy function of a conditional graphical model?
- What is supervised structured learning?
- How is supervised structured learning different from supervised learning?
- What do you know about the supervised structured learning problem (Section 6.3.4)?
- How can you solve the supervised structured learning problem (Section 6.3.4)?
- What do you know about the (structured) inference problem (Section 6.3.5)?
- How can you solve the (structured) inference problem (Section 6.3.5)?