Machine Learning 1 (Winter Term 2021/2022)

Overview

• Online course (2/2/0) consisting of:
  • Live video lectures with Q&A on Fridays, 14:50 - 16:20 → Join here
    • On 2022-01-28, we are offering recorded video lectures on the topics of supervised structured learning and conditional graphical models (see below). Bjoern Andres will discuss the contents of these video lectures also in the exercise group on Monday.
    • On 2021-12-17, we are offering a recorded video lecture instead of a live video lecture
  • Assignments, self-study and moderated discussion in a forum
  • Live discussion of assignments with Q&A, beginning the week of October 25th:
    • Mondays, 11:10 - 12:40 → Join here
    • Mondays, 16:40 - 18:10 → Join here
    • Thursdays, 14:50 - 16:20 → Join here
• Lecturer: Bjoern Andres
• Teaching Assistants: Shengxian Zhao and Jerome Thiessat
• 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-LE-MA, INF-PM-FOR, INF-VERT2, INF-VERT7, INF-VMI-8, INF-VMI-8A, MATH-MA-INFGDV, MCL-AI, MCL-PI
• Examinations (announced on 2021-12-10):
  • Review of written examinations: April 8th, 8:00 - 8:30. Registration required via email until April 6th.
  • In the study program Computational Modelling and Simulation (CMS) only, we are offering a remote written examination for this course on February 15th, 11:30 - 13:00. In order to take this examination, eligible students need to complete all of the following steps:
    • register for the examination via SELMA before January 16th
    • send to us via this email template before January 25th:
      • the filled-in and signed declaration of consent to an alternative form of performance of a non-objective examination
      • the filled-in spreadsheet file.
  • In all other degree programs offered by the faculty of computer science, we are offering remote oral examinations. In order to take these examinations, eligible students need to complete all of the following steps:
    • register for the examination with the examination office before January 16th, as described here
    • schedule an appointment for the examination before January 25th, by sending the confirmation of the registration to the secretary of the main examiner. If Bjoern Andres is to act as the main examiner, send to us via this email template before January 25th:
      • the confirmation of the registration
      • the filled-in and signed declaration of consent to an alternative form of performance of a non-objective examination
      • the filled-in spreadsheet file.

    These deadlines are strict. Students who are not registered or have not scheduled an appointment will not be able to take the examination this term.

Contents

• Lecture notes
• Assignments
  • Exercise sheet 1
  • Exercise sheet 2
  • Exercise sheet 3
  • Exercise sheet 4
  • Exercise sheet 5
  • Exercise sheet 6
• Lectures
  • Introduction (slides)
  • Supervised learning
    • Introduction (slides)
    • Learning of disjunctive normal forms (DNFs) (slides)
      • NP-hardness
    • Learning of binary decision trees (BDTs) (slides)
      • NP-hardness
      • Local search algorithm
    • Learning of linear functions (slides)
      • Logistic regression
      • Gradient descent algorithm
  • Semi-supervised and unsupervised learning
    • Introduction (slides)
    • Classifying (slides)
    • Partitioning (slides)
    • Set partition problem
    • Local search algorithms
    • Clustering (slides, video lecture)
    • Multicut problem
    • Local search algorithms
    • Ordering (slides)
      • Linear ordering problem
      • Local search algorithms
  • Supervised structured learning (slides, Video 1/3, Video 2/3, Video 3/3)
    • Factor graphs
    • Conditional graphical models
    • Message passing algorithms

Related Literature

• Machine Learning Textbooks
  • Barber, Bayesian Reasoning and Machine Learning
  • Bishop, Pattern Recognition and Machine Learning
  • Shai, Understanding Machine Learning

Preparation

The following questions are similar in style to questions that are asked during an oral 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!
• 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)?