Skip navigation
The Australian National University
Advanced Topics in Artificial Intelligence COMP4620/COMP8620

Advanced Topics in Artificial Intelligence COMP4620/COMP8620

Welcome to the Advanced AI course at the ANU !

This year (2010) 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. Note that traditionally the course varies significantly from year to year. Material from other years is available from the left menu.

Advanced AI

News

27Oct10: Oral exams are Tue.17 & Wed.18 Nov.13:30-18:00 in the RSISE Room A207.
19Oct10: Extended deadline: for Assignment 2 and Slides: 26.Oct.10ºº
30Aug10: Assignment 2 available
03Aug10: Assignment 1 available
14Jul10: Schedule and plan for assignments added
19Jun10: website contents created

Formalities/Miscellaneous/Summary

Offered By: The AI Group @ School of Computer Science @ Australian National University
Offered In: Second Semester, 2010 (19 July to 29 October). See Schedule below
Lecturer: Marcus Hutter
Tutors/Labs/Assistance: Tor Lattimore and Phuong Nguyen and Peter Sunehag
Target: Undergraduate (COMP4620) and Graduate (COMP8620) students. Others welcome.
Enrollment: Undergraduates: The usual way via ISIS. Honors&Graduates&Others: Contact lecturer.
Admin: Julie Arnold
Course Subject: Computer Science
Unit Value: 6 units
Time Table: See Schedule below for details
Office hours: Wed 9ºº-10ºº, RSISE Bld 115, Room B259.
Indicative Assessment: Assignments (45%); Seminar (10%); Examination (45%)
Indicative Workload: 25h lectures, 10h tutorial, 10h lab, ~50h assignments, lots of self-study
Prerequisite: COMP3620 (Intro2AI) or Russell&Norvig (2010) Chp.2,3,5.2,5.5,13,15.1-2,17.1-3,21
Advantageous background: COMP4670 (Intro2SML) or some statistics course
Prescribed texts: Excerpts from (see resources for details)
- Shane Legg (2008) Machine Super Intelligence
- Marcus Hutter (2005) Universal Artificial Intelligence
- Joel Veness et al. (2009) A Monte Carlo AIXI Approximation
Study@ANU page: http://studyat.anu.edu.au/courses/COMP4620;details.html
Wattle page: http://wattlecourses.anu.edu.au/course/view.php?id=7043
This page: http://cs.anu.edu.au/courses/COMP4620/2010.html

Course Description

This is an advanced undergraduate and graduate course that covers advanced topics in Artificial Intelligence. Topics vary from one offering to the next (see Study@ANU page).
    This year (2010) 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:
  • measures, tests, and definitions of intelligence;
  • Occam's razor;
  • universal Turing machines;
  • algorithmic information theory;
  • probability theory;
  • universal induction;
  • Bayesian sequence prediction;
  • minimum description length principle;
  • intelligent agents;
  • sequential decision theory;
  • reinforcement learning;
  • planning under uncertainty;
  • universal search;
  • philosophical foundations.
See Study@ANU for a brief description of some of these topics. 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 15ºº-16ºº & Wednesday 14ºº-15ºº
Engineering Lecture Theatre in Building 32
Tue.16-18ºº, Tut. in N109 / Lab in N115/116 CSIT Bld.108
19Jul - 23Jul Overview & Introduction
[Slides] Reading:[Legg08.Chp.1]
---
26Jul - 30Jul Information Theory & Kolmogorov Complexity
[Slides] Reading:[UAIBook.Sec.2.2]
tutorial
2Aug - 6Aug Bayesian Probability Theory
[Slides] Reading:[UAIBook.Sec.2.3]
tutorial+
get assignment 1
9Aug - 13Aug Algorithmic Probability & Universal Induction
[Slides] Reading:[UAIBook.Sec.2.4]
tutorial
16Aug - 20Aug Minimum Description Length & Universal Similarity
[Slides] Optional Reading:[MDL.Chp.1,USM]
tutorial+
23Aug - 27Aug Bayesian Sequence Prediction & CTW
[Slides, Slides] Reading: Parts of [UAIBook.Chp.3,CTW]
tutorial
30Aug - 3Sep Rational Agents
[Slides] Reading:[UAIBook.Chp.4.1&4.2]
hand in assignment 1
get assignment 2
6Sep - 10Sep Universal Artificial Intelligence
[Slides] Reading:try[UAIBook.Chp.5]
lab
13Sep - 17Sep Approximations and Applications
[Slides]
tutorial: solutions to assignment 1
20Sep - 24sep MC-AIXI-CTW
[Slides] Reading:[MC-AIXI-CTW]
lab
27Sep - 8oct break ---
11oct - 15oct Discussion
[Slides] Reading:[UAIBook.Chp.8]
lab
18oct - 22oct Discussion lab+
hand in assignment 2 (new deadline: 26.Oct.10ºº)
25oct - 29oct Student Presentation of Individual Contribution to Practical Assignment. Send slides in advance to Phuong Nguyen. lab

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. Tor Lattimore 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.
    The various modules will be assigned to different students, who are each responsible for delivering a well-tested module including source and external documentation, and to integrate them into the final product.
    Lab director Phuong Nguyen with support from ASC student Daniel Visentin will supervise the practical group project during lab sessions.

Tutorials/Labs

Rehearsal of lecture material and help with assignments: See Wattle

Assessment

Individual Theory Assignments (20%).
Practical Group Assignment (25%).
Seminar = 5 minute presentation of individual contribution to group assignment (10%).
Final Exam (20-30min,oral) (45%).
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 easy parts will be covered. It is recommended that students have a copy of this book (available at the ANU bookshop).

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. (2009) 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 course), see further recommended AI books and the papers read in the RL reading group.

Updated:  10 November 2010 / Responsible Officer:   JavaScript must be enabled to display this email address. / Page Contact:   JavaScript must be enabled to display this email address.