CS472 / CS473 Foundations of Artificial Intelligence

Foundations of Artificial Intelligence

CS472 / CS473 - Fall 2005
Cornell University
Department of Computer Science

Time and Place

First lecture: Friday, August 26, 2005
Last lecture: Friday, December 2, 2005

Monday, 11:15am - 12:05pm in OH 155
Wednesday, 11:15am - 12:05pm in OH 155
Friday, 11:15am - 12:05pm in OH 155

First Prelim Exam: Friday, September 30
Second Prelim Exam: November 16
Final Exam: Monday, December 12, 9:00am - 11:30am, Upson Hall B17
Project Demos: December 13, 10:30-12:00 and 1:00-3:30, Olin Hall 165

Instructor

Thorsten Joachims [tj@cs.cornell.edu], 4153 Upson Hall.

Mailing List and Newsgroup

[cs472-l@cs.cornell.edu] We'd like you to contact us by using this mailing list. The list is set to mail all the TA's and Prof. Joachims -- you will get the best response time by using this facility, and all the TA's will know the question you asked and the answers you receive. This makes both of our jobs easier.

[cornell.class.cs472] We will post announcements to this newsgroup and students can use it to communicate among each other. You can find instruction for accessing the newsgroup at http://www.cit.cornell.edu/services/netnews/

Teaching Assistants

Filip Radlinski [filip@cs.cornell.edu], 5154 Upson Hall

Alexa Sharp [asharp@cs.cornell.edu], 5157 Upson Hall

Justin Dewitt [jrd33@cs.cornell.edu]

David Lin [del29@cs.cornell.edu]

Office Hours

Monday 2:30pm - 3:30pm	Alexa Sharp	5157 Upson Hall
Tuesday 1:30pm - 2:30pm	Filip Radlinski	5154 Upson Hall
Wednesday 10:00am - 11:00am	David Lin	315 Upson Hall (CSUG Lab)
Wednesday 2:30pm - 3:30pm	Alexa Sharp	5157 Upson Hall
Wednesday 5:30pm - 6:00pm	Thorsten Joachims	4153 Upson Hall
Thursday 9:00am - 10:00am	Justin Dewitt	331 Upson Hall (knock or call 5-1008 from the outside phone)
Thursday 2:30pm - 3:30pm	Filip Radlinski	5154 Upson Hall
Fridays at 1:30pm - 2:30pm (not on Dec 9 due to travel)	Thorsten Joachims	4153 Upson Hall

Syllabus

This course introduces the theoretical and computational techniques that serve as a foundation for the study of artificial intelligence (AI). Topics to be covered include the following:

Introduction of AI and background: What is AI? Related fields
Problem solving by search: principles of search, uninformed (�blind�) search, informed (�heuristic�) search, genetic algorithms, game playing
Learning: inductive learning, concept formation, decision tree learning, statistical approaches, neural networks
Knowledge representation and reasoning: knowledge bases and inference; constraint satisfaction; planning; theorem-proving; Bayesian networks
Natural language understanding: syntactic processing, ambiguity resolution, text understanding

Reference Material

The main textbook for the class is

Artificial Intelligence: A Modern Approach, Russell and Norvig, Prentice-Hall, Inc., second edition.

Prerequisites

This course has no prerequisites other than familiarity with basic data structures and programming (e.g., CS211) and the basic mathematical skills obtained in CS280. An understanding of inference in first-order logic and basic blind search techniques (i.e., breadth-first and depth-first search) is also assumed, but background readings in these topics can be provided for those with a deficiency in this area.

Readings

8/26: R&N Chapter 1
8/29: R&N Chapter 2
8/31: R&N Chapter 3
9/5: R&N Section 4.1
9/7: R&N Section 4.2
9/9: R&N Section 4.3
9/14: R&N Sections 5.1 - 5.2
9/16: R&N Sections 5.3 - 5.5
9/19: R&N Chapter 6
9/23: R&N Sections 18.1-18.2, Section 20.4 (more detail on K-NN in Tom Michell "Machine Learning", Section 8.2)
9/28: R&N Section 18.3
10/07: R&N Section 18.5 (more detail in Tom Michell "Machine Learning", Sections 7.1 - 7.3)
10/14: R&N Section 20.5 (single layer)
10/17: Schoelkopf & Smola, Learning with Kernels, Sections 7.1 - 7.3 (PDF) (see annotations in class)
10/19: Schoelkopf & Smola, Learning with Kernels, Section 7.5 (PDF) (see annotations in class)
10/24: R&N Section 20.5 (remainder)
10/28: R&N Sections 20.6 - 20.7, Schoelkopf & Smola, Learning with Kernels, Section 7.4 (PDF) (see annotations in class)
10/31: R&N Section 17.1
11/02: R&N 17.2-17.3
11/04: R&N 21.1-21.2
11/07: R&N 21.3-21.4
11/09: R&N 7.1-7.5
11/11: R&N 7.6
11/14: R&N Chapter 8
11/18: R&N 9.1-9.3, 9.5
11/23: R&N 10.3 (up to page 334)
11/28: R&N 11.1-11.3
12/02: R&N 22.1, 24.1, 25.1

Slides and Handouts

8/26: Introduction (PDF)
8/29: Uninformed Search 1 (PDF)
8/31: Uninformed Search 2 (PDF)
9/5: Heuristic Search 1 (PDF)
9/7: Heuristic Search 2 (PDF)
9/9: Local and Genetic Search (PDF)
9/14: Constraint Satisfaction 1 (PDF)
9/16: Constraint Satisfaction 2 (PDF)
9/19: Games 1 (PDF)
9/21: Games 2 (PDF)
9/23: Instance-Based Learning (PDF) (Prelim 1 2003, Prelim 1 2004 [Solution 2004])
9/28: Decision-Tree Learning (PDF)
10/05: Machine Learning Experiments and Overfitting (PDF)
10/07: Statistical Learning Theory (PDF)
10/14: Linear Classifiers 1 (PDF)
10/19: Linear Classifiers 2 (PDF)
10/24: Neural Nets 1 (PDF)
10/26: Neural Nets 2 (PDF)
10/28: Support Vector Machines and Kernels (PDF)
10/31: Reinforcement Learning (PDF)
11/09: Knowledge-Based Systems 1 (PDF) (Prelim 2 2003 [Solution 2003], Prelim 2 2004 [Solution 2004])
11/11: Knowledge-Based Systems 2 (PDF)
11/14: Knowledge-Based Systems 3 (PDF)
11/23: Planning 1 (PDF)
11/28: Planning 2 (PDF)
11/30: Planning 3 (PDF)
12/02: Wrap-up (PDF)

Homework Assignments

9/2: Homework 1 (due 9/9 before class) (see CMS)
Sample paper critiques: sample 1, sample 2, and sample 3.
9/16: Homework 2 (due 9/23 before class) (see CMS)
9/30: Homework 3 (due 10/7 before class) (see CMS)
10/21: Homework 4 (due 10/28 before class) (see CMS)
11/04: Homework 5 (due 11/11 before class) (see CMS)
11/18: Homework 6 (due 12/02 before class) (see CMS)

The graded homework assignments and the prelims can be picked-up in Upson 360. The opening hours are Monday-Friday, 10am-12pm and 2pm-4pm.

Project (CS 473 Only)

8/31: Project Pre-Proposal (PDF) - due 9/12
9/14: Project Proposal due 9/21 (PDF)
10/7: Status Report 1 due 10/17 (PDF)
11/2: Status Report 2 due 11/7 (see CMS)
12/13: Project Demos, sign-up sheet at Upson 4153 (let us know if you have a conflict)
12/14 (noon): Final Project Report and Source Code due via CMS (report template)

Grading CS472

This is a 3-credit course. Grades will be determined based on two written exams, a final exam, homework assignments, and class participation.

25%: 2 Prelim Exams
25%: Final Exam
45%: Homework (~6 assignments)
5%: Participation

All assignments are due at the beginning of class on the due date. Assignments turned in late will drop 5 points for each period of 24 hours for which the assignment is late. In addition, no assignments will be accepted after the solutions have been made available.

Roughly: A=90-100; B=80-90; C=70-80; D=60-70; F= below 60

Grading CS473

The main assignment for CS473 is a course project. Students will work in groups to design, build, and evaluate an intelligent system of their choice. Throughout the semester, project status reports and partial programs will be required.

5%: Preliminary Project Proposal
10%: Project Proposal
10%: Status Report 1
10%: Status Report 2
65%: Final Report (Write-up 40%, Code 15%, Demo 10%)

All assignments are due at the beginning of class on the due date. Assignments turned in late will drop 5 points for each period of 24 hours for which the assignment is late.

Academic Integrity

This course follows the Cornell University Code of Academic Integrity. Each student in this course is expected to abide by the Cornell University Code of Academic Integrity. Any work submitted by a student in this course for academic credit will be the student's own work. Violations of the rules (e.g. cheating, copying, non-approved collaborations) will not be tolerated.