Computational Learning Theory, Logic and Knowledge Representation

6 EC

Semester 1, period 2

5314CLTL6Y

Owner Master Logic
Coordinator Balder ten Cate
Part of Master Artificial Intelligence, Master Logic, Master Logic, track Logic and Computation, Master Logic, track Logic and Philosophy, Master Logic, track Logic and Language, Master Logic, track Logic and Mathematics, Master Logic, track Logic Year, year 1Master Logic, track Exchange, year 1

Course manual 2024/2025

Course content

Computational learning theory (CLT) studies the theory foundations (algorithms and complexity) of learning from examples. It offers a framework for studying the learnability and complexity of different learning problems. This course provides a basic introduction to CLT (including the PAC model, as well as interactive exact learning models), and covers applications in logic and KR, including learning Boolean formulas, conjunctive queries, logic programs ("inductive logic programming"), and description logic concepts. This topic dates back to the 1980s, but there has been continuous progress over the years, and this course, while introductory in nature, also aims to give an up to date overview. Concretely, in this course, you will become familiar with formal models of algorithmic learning; basic learning techniques; tools for proving non-efficient learnability; and how these apply to the various aforementioned logical languages.

Study materials

Literature

  • All study material (course notes and textbook chapters) will be provided electronically on canvas.

Objectives

  • explain core concepts from computational learning theory (PAC learning algorithm, exact learning, VC dimension, Ockham algorithm)
  • describe efficient learning algorithms for various concept classes, including classes of Boolean formulas and of first-order formulas.
  • disprove efficient learnability for various concept classes
  • compute bounds on the sample complexity of a learning algorithm

Teaching methods

  • Lecture
  • Seminar
  • Self-study

Learning activities

Activity

Hours

Hoorcollege

32

Werkcollege

16

Self study

120

Total

168

(6 EC x 28 uur)

Attendance

This programme does not have requirements concerning attendance (TER-B).

Additional requirements for this course:

Attendance is not mandatory but strongly encouraged.

Assessment

Item and weight Details

Final grade

Inspection of assessed work

Graded homework and model answers will appear on canvas.

Assignments

The grade is determined by the average score of the homework assignments (50%) and final exam (50%)

The students are allowed to collaborate in small groups on the homework, but each student is expected to write up and submit their answers themselves.

 

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Contact information

Coordinator

  • Balder ten Cate