Foundations of Artificial Intelligence
FS 2012 - ETHZ 263-5110-00

Welcome to the Foundations of AI course at the ETHZ !

 The course will focus on the Foundations of AI, including inductive inference, decision-making under uncertainty, reinforcement learning, intelligent agents, information theory, philosophical foundations, and others.

Advanced AI

News

 02Mar12: Assignment 1 available
20Feb12: Lecture room on Tuesday has changed to ETHZ Building CAB Room G11.
20Dec11: website contents created

Formalities/Miscellaneous/Summary

 Offered By: The ML Group @ Computer Science Department @ ETH Zürich
Offered In: Spring Semester, 2012 (21 February to 29 May). See Schedule below
Lecturer: Marcus Hutter
Tutors/Labs/Assistance: Mahapatra Dwarikanath
Target: Advanced Undergraduate and Masters students. Others welcome.
Enrollment: The usual way online or contact lecturer.
Admin: Denise Spicher
Course Subject: Computer Science & Mathematics & Statistics
Unit Value: 5 KP units
Time Table: See Schedule below for details
Contact hours: After the lecture and per email.
Indicative Assessment: Assignments (45%); Seminar (10%); Written Examination (45%), each to be passed
Indicative Workload: 25h lectures, 10h tutorial, 10h lab, ~50h assignments, lots of self-study
Prescribed texts: Excerpts from (see resources for details)
- Shane Legg (2008) Machine Super Intelligence
- Marcus Hutter (2005) Universal Artificial Intelligence
- Joel Veness et al. (2011) A Monte Carlo AIXI Approximation
VVZ@ETHZ page: ETHZ 263-5110-00
This page: http://www.hutter1.net/ethz/uaiethz.htm

Prerequisites: If you have absolved the Machine Learning course or the Probabilistic Artificial Intelligence course, you will have the necessary background for this course. Otherwise you can acquire the necessary background e.g. from the book Russell&Norvig (2010) Chp.2,3,5.2,5.5,13,15.1-2,17.1-3,21.
Chapter 1 of Li&Vitanyi (2008) is a great refresher of basic computer, information, and probability theory.

Course Description

 This is an advanced undergraduate and graduate course that covers Foundations of Artificial Intelligence.
    The course will focus on the foundations of AI, including inductive inference, decision-making, reinforcement learning, information theory, and some game and agent theory.
    The dream of creating artificial devices that reach or outperform human intelligence is many centuries old. This course presents an elegant parameter-free theory of an optimal reinforcement learning agent embedded in an arbitrary unknown environment that possesses essentially all aspects of rational intelligence. The theory reduces all conceptual AI problems to pure computational questions.
    How to perform inductive inference is closely related to the AI problem. The course covers Solomonoff's theory, which solves the induction problem, at least from a philosophical and statistical perspective.
    Both theories are based on Occam's razor quantified by Kolmogorov complexity, Bayesian probability theory, and sequential decision theory.

Learning Outcomes

 Despite the grand vision above, most of the course necessarily is devoted to introducing the key ingredients of this theory, which are important subjects in their own right. On completing this course students will have a solid understanding of: Students will also learn about Monte-Carlo Tree Search; games; adaptive control theory; et al.
    The intention is to run tutorials throughout the first half of the course to consolidate the knowledge via theoretical exercises. In the second half, a group project will be run, which shall approximate, implement, and test the theory on some applications like Tic-Tac-Toe or Poker or Pacman.

Schedule
Week Lecture Tutorial/Lab
to be updated throughout the course Tuesday 13ºº-15ºº ETHZ Building CAB Room G11 &
Wednesday 13ºº-14ºº ETHZ Building NO Room C6 		Wed.14-15ºº 
Tut&Lab in NO C6
21Feb - 22Feb Overview & Introduction [Advertizement]
[Slides] Reading:[Legg08.Chp.1]		 ---
28Feb - 29Feb Information Theory & Kolmogorov Complexity
[Slides] Reading:[UAIBook.Sec.2.2]		 tutorial
6Mar - 7Mar Bayesian&Algorithmic Probability & Universal Induction
[Slides, Slides] Reading:[UAIBook.Sec.2.3&2.4]		 tutorial
get assignment 1
13Mar - 14Mar Minimum Description Length & Universal Similarity
[Slides] Optional Reading:[MDL.Chp.1,USM]		 tutorial
20Mar - 21Mar Bayesian Sequence Prediction & CTW
[Slides, Slides] Reading: Parts of [UAIBook.Chp.3,CTW]		 tutorial
27Mar - 28Mar Rational Agents
[Slides] Reading:[UAIBook.Chp.4.1&4.2]		 tutorial
3Apr - 4Apr Universal Artificial Intelligence
[Slides] Reading: try[UAIBook.Chp.5]		 hand in assignment 1
get assignment 2
10Apr - 11Apr break ---
17Apr - 18Apr Approximations and Applications [Slides]
MC-AIXI-CTW [Slides] Reading:[MC-AIXI-CTW]		 lab
24Apr - 25Apr Discussion
[Slides] Reading:[UAIBook.Chp.8]		 tutorial: solutions to assignment 1
1May - 2 May no lecture 1-2h lab
8May - 9May no lecture 1-2h lab
15May - 16May no lecture 1-2h lab
22May - 23May no lecture 1-2h lab
hand in assignment 2
29May - 30May Student Presentation of Individual Contribution to Practical Assignment. Send slides in advance to Tutor. student presentation

Assignments

 Theory Assignment 1: The theory assignment is to be done individually, and will involve various mathematical exercises that will deepen the understanding of the lectured material. Mahapatra Dwarikanath will be tutor and primary contact for the theory assignment.

Practical Group Assignment 2: The practical assignment will be a group project. Goal is to implement the MC-AIXI-CTW model, which is a recent practical scaled-down version of the theoretical universal AI agent AIXI. Students will acquire first-hand experience how a single algorithm can autonomously learn to solve various toy problems like playing Tic-Tac-Toe or PacMan or Poker just based on experience and reward feedback without ever being told the rules of the game. The implementation should be completely stand-alone in very light C++. Particular emphasis is on ease of use (installation, compilation, running, modification) and good documentation. The project involves programming of various sophisticated functions, and requires and furthers the understanding of the theoretical material taught in the main class.
    Each group will consist of 6-9 students. A group can self-organize and distribute work internally. The various modules/tasks/domains can be implemented by different students, each responsible for delivering a well-tested module including source and documentation. The group is responsible to deliver a final product consisting of documented source code, experimental results, and a final joint report.
    Lab director Mahapatra Dwarikanath will supervise the practical group project during lab sessions.

Tutorials/Labs

 Rehearsal of lecture material and help with assignments:

Assessment

 Individual Theory Assignments (20%).
Practical Group Assignment (25%).
Seminar = 5 minute presentation of individual contribution to group assignment (10%).
Final written examination (45%) Exam (90min,written,closed-book,informal&math questions).
What to know for the exam: Material in the course slides.
The other provided reading material should help you to better understand the slides, but will itself not be examined.

Resources

 Slides and assignments: See links in schedule.

Marcus Hutter (2005) Universal Artificial Intelligence
The lectures will draw heavily from this (tough) book, but only the easier parts will be covered. It is recommended that students have a copy of this book. (Available at the ETHZ bookshop and on Wed.29.Feb.14ºº-1415 in front of the lecture room for CHF 60.--)

Shane Legg (2008) Machine Super Intelligence
This is a gentle more philosophical, less mathematical introduction into the subject. It is highly recommended. It costs less than $20 and the pdf is even free.

Joel Veness et al. (2011) A Monte Carlo AIXI Approximation
This is a (tough and hot) research paper, which builds the basis for the group implementation project.

The lectures will also draw from the following paper(s)
F. Willems and Y. Shtarkov and T. Tjalkens
The context-tree weighting method: Basic properties
IEEE Transactions on Information Theory (41), 653 - 664, 1995
A more readable version of the same paper is here

If you're curious what's out there else (but this is clearly beyond the scope of the course), see further recommended AI books and the papers read in the RL reading group.