Salvatore J. Stolfo
606 CEPSR
212.939.7080
Email: sal@cs.columbia.edu

Office Hours: 1 hour prior to class

URL of this page:

http://www.cs.columbia.edu/~sal/AI-Spring09.htm

FINAL EXAM SCHEDULE
(Definitely the last class)

Can you guess what this picture means?

To access the course discussion board
1. Go to http://courseworks.columbia.edu and log in
2. Click the link for COMS W4701 course listing
3. Click the link for "Discussion" on the left-hand side

Artificial Intelligence, A Modern Approach,
Russell and Norvig, (Prentice Hall), SECOND EDITION,
ISBN: 0-13-790395-2

URL: http://aima.cs.berkeley.edu/

Syllabus

- Overview of AI: Strong, Weak, History, Symbolic AI/Cognitive AI

- Introduction to LISP: Programming and Examples

- Assignment #1: A moderately complex Lisp programming project, pattern matching, memory retrieval, etc.

- Problem Solving:

* Problem Formulation as Search, State Spaces, Problem Reduction

* Basic Weak Search Methods & Algorithms: Breadth, Depth, Best-first, Generate and Test, Hill Climbing, etc.

* Lisp Implementations

* Assignment #2: Implementation of a basic search method for a moderate-scale problem, comparative evaluation of alternative search algorithms.

* Game Playing: Minimax, Alpha-Beta

*Assignment #3: Game Playing Tournament, TBA

- First Order Logic

* Mechanical Theorem Proving

* Unification

- Midterm: Closed Book

- Knowledge Representation:

* Structured Representations: Semantic Nets, Frames, Blackboards, Rules

* Subsumption and Classification

* Lisp Implementation of nets, frames or rules.

- Machine Learning and Generalization

* Inductive Inference

* Version Spaces, ID3, CART, etc. as examples

* Bayesian Learning

*Support Vector Machines

* Assignment #4: Lisp Implementation of a machine learning program classifier

- Final Exam: Closed Book, Entire Material Presented in Class

There are many code examples on the AIMA website to guide your work in LISP.

LISPworks (http://www.lispworks.com/) is free and probably the easiest LISP implementation for you to use. The course structure by lecture is specified in the table below, annotated with required book chapters from Russel & Norvig’s AIMA text. Useful slides/code/background material are provided in the right most column. Some of these are likely to change from time to time.

The basic required chapters include chapters 1-4, 5-10, 13 and 18.

We will follow a general theme throughout the progression of the course describing alternative styles of logical inference, from Deductive Inference, to Abductive and finally Inductive Inference in the context of an intelligent agent architecture. Auto-epistemic will have to wait for another course.

Session	Date	Topic/chapter	Free code/ HW Project Assigned or Due
1	1/20	Overview of AI (Chapter 1 and 2)	Intro-Slides and Agents, Symbolic AI/Cognitive AI
2	1/22	Intro to LISP	How to run Lisp Download personal edition Lisp from www.lispworks.com LISP Primer Load and compile in Lispworks See http://www.cs.berkeley.edu/~russell/code/doc/install.html
3	1/27	LISP examples
4	1/29	Equality/Pattern matching	Project#1: Pattern Matcher Some useful string functions
5	2/3	Intro Problem Solving (Chp 2) State Space Search	Search slides
6	2/5	Weak search methods&algs (BFS, DFS, etc.) (Chp 3)	Basic search, Iterative DFS search, 8 Puzzle state Convert states to symbols
7	2/10	IDDFS, Complexity measures
8	2/12	Uniform cost, Greedy, Bidirectional Search	Project #1 DUE
9	2/17	Heuristic Search A* (Chp 4)	Project#2: Search programs, Some useful clock functions An improved NORTH operator for 15 puzzle Uniform cost, Greedy search, Bidirectional search Heuristic search slides
10	2/19	Problem-reduction problem solving, Constraint satisfaction problems	A star search, Iterative A star search Minimax/Alpha-Beta CSP slides
11	2/24	AND/OR	A*-And-Or-Search
12	2/26	Game Playing (Chp 6)	Project #3: ISOLATION Game Playing Slides Project #2 DUE MONDAY MAR 2
13	3/3	Minimax/Alpha-beta
14	3/5	Intro to Knowledge Representation	Proposition Logic Slides
15	3/10	MIDTERM	All material on search, up to the lecture on 3/3 1 hr 15 min. time limit Knowledge representation and propositional logic NOT covered on the exam.
16	3/12	More Intro to Knowledge Representation	FOL slides
	3/16-3/20	SPRING BREAK
17	3/24	Propositional Logic Mechanical Theorem Proving	Theorem Proving Code & examples
18	3/26	Resolution Thm. Proving (Chp 7)	Inference Slides Project #3 DUE SUNDAY 29 MARCH FOR ALL STUDENTS (INCLASS AND CVN).
19	3/31	First Order Logic, Godel Thms. (Chp 8) Resolution Thm Proving in FOL (Chp 9) Unification, Herbrand Universe
20	4/2	More logic	TOURNAMENT PLAYOFFS FRIDAY APR 3 Pictures from the Tournament Play The Intense Championship Round Winner Board Photo Winner Ladder
21	4/7	Semantic nets/Frames Inference in nets (Chp 10)	Intersection search
22	4/9	Frames, Rule-based Systems Backward chaining, Prolog
23	4/14	Uncertainty and Bayesian Inference (Chp 13)	Uncertainty slides Bayesian inference slides
24	4/16	Intro to Machine Learning (Chp 18.1 – 18.3)	Learning Slides Project #4: Decision Tree Learning
25	4/21	Generalization, Inductive Inference (Chp 19.1 – 19.2)	Chpt19-slides
26	4/23	Decision Tree Learning	ID3 and example
27	4/28	Naive Bayes Classifier	NB-slides
28	4/30	LAST CLASS – INCLASS FINAL EXAM
**	5/1 – 5/4	STUDY DAYS	Project #4 DUE MON 4 MAY
**	5/5 – 5/8	FINALS WEEKS	End of Spring 09 TERM. Summer Break begins.