Advanced Topics in Artificial Intelligence COMP4620/COMP8620 
Welcome to the Advanced AI course at the ANU !
This year (2013) the course will focus on the Foundations of AI, including inductive inference, decisionmaking 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.News
26Sep13: Assignment 2 available01Aug13: Assignment 1 available
28May13: website contents created
Formalities/Miscellaneous/Summary
Offered By: The AI Group @ Research School of Computer Science @ Australian National UniversityOffered In: Second Semester, 2013 (22 July to 31 October). See Schedule below
Lecturer: Marcus Hutter
Tutors/Labs/Assistance: Wen Shao
Target: Undergraduate (COMP4620) and Graduate (COMP8620) students. Others welcome.
Enrollment: Undergraduates: The usual way via ISIS. Honors&Graduates&Others: Contact lecturer.
Admin: Bindi Mamouney
Course Subjects: Computer Science & Mathematics & Statistics
Unit Value: 6 units
Time Table: See Schedule below for details
Office hours: Wed 9ºº10ºº, RSISE Bld 115, Room B259.
Assessment: Assignments (45%); Seminar (10%); Oral Examination (45%) [details]
Indicative Workload: 25h lectures, 10h tutorial, 10h lab, ~50h assignments, lots of selfstudy
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
Study@ANU page: http://studyat.anu.edu.au/courses/COMP4620;details.html
Wattle page: http://wattleprep.anu.edu.au/course/view.php?id=945
This page: http://cs.anu.edu.au/courses/COMP4620/2013.html
Prerequisites: If you have absolved the Machine Learning course COMP4670 or the Artificial Intelligence course COMP3620 or the Information Theory course COMP2610 you should have the necessary background for this course. Otherwise you can acquire the necessary background e.g. from the AI book Russell&Norvig (2010) Chp.2,3,5.2,5.5,13,15.12,17.13,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 advanced topics in Artificial Intelligence. Topics vary from one offering to the next (see Study@ANU page). This year (2013) the course will focus on the foundations of AI, including inductive inference, decisionmaking, 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 parameterfree 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, and is key to addressing many theoretical, philosophical, and practical AI 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. The course is for computer science students interested in knowing about or building general AI systems from first principles, and others interested in the formal foundations of intelligence.Learning Outcomes
While the Introduction to AI course taught a diversity of methods for solving a variety of AI problems, this Advanced AI course emphasizes the foundational, unifying, and general aspects of (artificial) intelligence. Course highlights are: Formal definitions of (general rational) Intelligence;
 Optimal rational agents for arbitrary problems;
 Philosophical, mathematical, and computational background;
 Some approximations, implementations, and applications;
 Stateoftheart artificial general intelligence.
 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;
 MonteCarlo tree search;
 philosophical foundations.
Schedule
Week  Lecture / Tutorial / Lab 

to be updated throughout the course  Monday 13ºº14ºº
& Wednesday 15ºº16ºº
& Thursday 14ºº15ºº N101 in CSIT Building 108 
22Jul  26Jul  Overview & Introduction [Advertisement] [Slides] Reading:[Legg08.Chp.1] 
29Jul 2Aug get assignment 1 
Mo: Information Theory & Kolmogorov Complexity [Slides] Reading:[UAIBook.Sec.2.2] We&Th: Tutorial 
5Aug  9Aug  Tutorial 
12Aug  16Aug  Tutorial 
19Aug  23Aug  Mo: Tutorial We&Th: Bayesian Probability Theory [Slides] Reading:[UAIBook.Sec.2.3] 
26Aug  30Aug  Algorithmic Probability & Universal Induction [Slides] Reading:[UAIBook.Sec.2.4] Minimum Description Length [Slides] Optional Reading:[MDL.Chp.1] 
2Sep  6Sep  Universal Similarity [Slides] Optional Reading:[USM] Bayesian Sequence Prediction [Slides] Reading: Parts of [UAIBook.Chp.3] Context Tree Weighting [Slides] Reading:[CTW] 
9Sep  20Sep  break 
23Sep  27Sep hand in assignment 1 
Universal Rational Agents
[Slides]
Reading:[UAIBook.Chp.4.1&4.2&5.1.1] MCAIXICTW [Slides] Reading:[MCAIXICTW] 
30Sep  4oct get assignment 2 
We&Th: Orientation Lab for assignment 2 
7oct  11oct  We&Th: Solutions to assignment 1 and Q&A for assignment 2 
14oct  18oct  Theory of Rational Agents [Slides] Reading:try [UAIBook.Chp.5] 
21oct  25oct hand in assignment 2 
Approximations and Applications [Slides] + extra labs 
28oct  1Nov 
Discussion
[Slides]
Reading:[UAIBook.Chp.8]
+ Student Presentation of Individual Contribution to Practical Assignment. Send slides in advance to Wen Shao 
Extra Labs & Student Presentation:
Where: In PC Lab room N112 in CSIT Building
When: Week 2125oct (Lab) and 28oct1Nov (Presentation), Thursday 15ºº17ºº.
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. Wen Shao 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 MCAIXICTW model, which is a recent practical scaleddown version of the theoretical universal AI agent AIXI. Students will acquire firsthand experience how a single algorithm can autonomously learn to solve various toy problems like playing TicTacToe 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 standalone 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 69 students. A group can selforganize and distribute work internally. The various modules/tasks/domains can be implemented by different students, each responsible for delivering a welltested 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 Wen Shao will supervise the practical group project during lab sessions.
Tutorials/Labs
Rehearsal of lecture material and help with assignments: See WattleAssessment
Theory: Individual Theory Assignments (20%).Practice: Practical Group Assignment (25%).
Seminar: Seminar = 5 minute presentation of individual contribution to group assignment (10%).
Exam: Final 30min oral examination (45%).
Know: 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.
Pass: To pass the course, students must pass each assignment and the final exam.
Plagiarism: Misconduct will result in failure of the course and disciplinary consequences (no exceptions)
See: [AcademicHonesty@ANU] [Student Handbook@RSCS] [Example@comp1100]
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 ANU bookshop or cheaper here). 
Shane Legg (2008) Machine Super Intelligence
This is a gentle more philosophical, less mathematical introduction to 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 contexttree 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.