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 selfstudy
 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 CMSCEEL1, CMSCEEL2, CMSCLSELG, CMSCLSELV, CMSCORMLD, CMSVCELG, CMSVCELV1, CMSVCELV2, INF04FGIS, INFB510, INFB520, INFB530, INFB540, INFBAS2, INFBAS7, INFE3, INFPMFOR, INFVERT2, INFVERT7, INFVMI8, MCLAI, MCLPI
 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
 Semisupervised 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 SetCoverProblem to the LengthmDNF Problem?
 How can you show that exact learning of DNFs is NPhard?

Binary decision trees (BDTs)
 What is a BDT?
 What are suitable regularizers for BDTs?
 How can you reduce the ExactCoverby3Sets Problem to the DepthmDNF Problem?
 How can you show that exact learning of BDTs is NPhard?

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)

Semisupervised and unsupervised learning
 What do you know about semisupervised/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 (madeup or realworld) 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)?