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-Spring11.htm

FINAL EXAM SCHEDULE
(Definitely the last class)

$Description: Description: Description: Description: C:\Documents and Settings\Sal\My Documents\AI.small.gif$

Can you guess what this picture means?

Class picture

And another class picture

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

A special subset of :

Artificial Intelligence, A Modern Approach,
Russell and Norvig, (Prentice Hall), THIRD EDITION,
ISBN: 0558881173

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

Syllabus

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

- Introduction to LISP: Examples (LISP is NOT required for projects)

- Assignment #1: A set of questions from the R&N text book

- 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.

* 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 (Deduction)

* Mechanical Theorem Proving

* Unification

* Gödel’s theorems, SAT and relationship to NP-Completeness

- Midterm: Closed Book

- Knowledge Representation:

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

- Uncertainty and Bayesian Inference (Abduction)

- Machine Learning and Generalization (Induction)

* Inductive Inference

* Version Spaces, ID3, CART, etc.

* Bayesian Learning

* Support Vector Machines

* Assignment #4: 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 and Java.

LISP IS NOT REQUIRED FOR THE PROJECTS.

[For those who are brave enough:

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 of AIMA are 1-4, 5-10, 13 and 18, or 1-14 in the Custom version of the text.

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/18	Overview of AI (Chapter 1 and 2)	Intro-Slides and Agents, Symbolic AI/Cognitive AI
2	1/20	History of AI/LISP	Project#1: Updated Description of: Simple Pattern Matcher
3	1/25	Intro to LISP (to understand code examples) Equality of symbol structures	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
4	1/27	Intro Problem Solving (Chp 3) State Space Search	Search slides
5	2/1	Weak search methods&algs (BFS, DFS, etc.) (Chp 3)	Basic search, Iterative DFS search, 8 Puzzle state Convert states to symbols
6	2/3	IDDFS, Complexity measures	Project #1 DUE
7	2/8	Uniform cost, Greedy, Bidirectional Search
8	2/10	Heuristic Search A* (Chp 4)	Project#2: Search programs, An improved NORTH operator for 15 puzzle Uniform cost, Greedy search, Bidirectional search
9	2/15	Problem-reduction problem solving, Constraint satisfaction problems (Chpt 6)	A star search, Iterative A star search CSP slides
10	2/17	AND/OR	A*-And-Or-Search
11	2/22	Game Playing (Chp 5)	Project#3: Isolation Game Playing Slides
12	2/24	Minimax/Alpha-beta	Project #2 DUE THURSDAY FEB 24 Minimax/Alpha-Beta
13	3/1	Beyond Classical Search (Chpt 4) Heuristic Admissibility/consistency	A*and local search heuristics Local search
14	3/3	Hill Climbing/Simulated Annealing/Genetic Algs	More local search
15	3/8	MIDTERM	All material on search, up to the lecture on 3/3 1 hr 15 min. time limit Propositional logic is NOT covered on the exam.
16	3/10	Intro to Knowledge Representation Propositional Logic Mechanical Theorem Proving (Chpt 7,8)	Propositional Logic Slides Propositional Logic Slides 2
	3/14-3/18	SPRING BREAK
17	3/22	Resolution Thm. Proving (Chp 9)	Inference Slides
18	3/24	First Order Logic, Godel Thms. (Chp 8) Resolution Thm Proving in FOL (Chp 9) Unification, Herbrand Universe	FOL slides
19	3/29	More logic	Theorem Proving Code & examples Project #3 DUE TUESDAY 29 MARCH FOR ALL INCLASS AND CVN STUDENTS .
20	3/31	Semantic nets/Frames Inference in nets (Chp 10)	TOURNAMENT PLAYOFFS FRIDAY APR 1 About the winning program Pictures from the Tournament Play Sustaining energy levels. The Intense Championship Round Winner Board Photo
21	4/5	Frames, Rule-based Systems Backward chaining, Prolog	Intersection search
22	4/7	Uncertainty (Chp 11, 12)	Uncertainty slides
23	4/12	Bayesian Inference	Bayesian inference slides
24	4/14	Intro to Machine Learning (Chp 13)	Learning Slides Project #4: Decision Tree Learning
25	4/19	Generalization, Inductive Inference (Chp 14)	Chpt19-slides
26	4/21	Decision Tree Learning	ID3 and example
27	4/26	Naive Bayes Classifier	NB-slides
28	4/28	LAST CLASS – INCLASS FINAL EXAM A EYE	Resurgence of AI – or more of the same? http://www.nytimes.com/2009/12/08/science/08sail.html
**	5/3 – 5/6	STUDY DAYS	Project #4 DUE MON 2 MAY, 2011
**	5/5 – 5/8	FINALS WEEKS	End of Spring 2011 TERM. Summer Break begins.