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

Office Hours: 1 hour prior to class

URL of this page:

http://www.cs.columbia.edu/~sal/AI-Spring13.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?

Text Book

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: TBA

- 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 EXCEPT THE FIRST ONE.

Python may be the one for you!

You Must Read: Lisp vrs Python: http://norvig.com/python-lisp.html

[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, 14 and 18, 19.

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.

Detailed Course Schedule

Session	Date	Topic/chapter	Free code/ HW Project Assigned or Due
1	1/22	Overview of AI (Chapter 1 and 2)	Intro-Slides and Agents, Symbolic AI/Cognitive AI
2	1/24	CLICK ON THIS LINK–History of AI/LISP http://norvig.com/python-lisp.html	Project#1: Simple Pattern Matcher MUST BE IN LISP Pattern Match Function Code – A general schema (Pre-recorded Lecture by (Fat) Prof Stolfo – don’t laugh. Viewable on the CU network only, or by CVN students.)
3	1/29	Intro to LISP (to understand code examples) LISP at High Speed 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/31	Intro Problem Solving Click on the title and watch Lecture 4 (Chp 3) State Space Search	LAST DAY TO DROP. PLEASE DON’T GO. Search slides
5	2/5	Weak search methods&algs (BFS, DFS, etc.) (Chp 3)	Basic search, Iterative DFS search, 8 Puzzle state Convert states to symbols
6	2/7	IDDFS, Complexity measures	Project #1 DUE
7	2/12	Uniform cost, Greedy, Bidirectional Search
8	2/14	Heuristic Search A* (Chp 4)	Project#2: Search programs, An improved NORTH operator for 15 puzzle Uniform cost, Greedy search, Bidirectional search
9	2/19	Beyond Classical Search (Chpt 4) Heuristic Admissibility/consistency	A star search Iterative A star search A*and local search heuristics
10	2/21	Problem-reduction problem solving, Constraint satisfaction problems (Chpt 6)	CSP slides
11	2/26	AND/OR	A*-And-Or-Search
12	2/28	Game Playing (Chp 5)	Project#3: Isolation Game Playing Slides Minimax/Alpha-Beta
13	3/5	Minimax/Alpha-beta	Project #2 DUE TUESDAY March 5 Local search
14	3/7	Hill Climbing/Simulated Annealing/Genetic Algs	More local search
15	3/12	MIDTERM	All material on search, up to the lecture on 3/12 1 hr 15 min. time limit Propositional logic is NOT covered on the exam.
16	3/14	Intro to Knowledge Representation	Go over the MIDTERM
	3/18-3/22	SPRING BREAK
17	3/26	Propositional Logic Mechanical Theorem Proving (Chpt 7,8)	Propositional Logic Slides Propositional Logic Slides 2
18	3/28	Resolution Thm. Proving (Chp 9)	Inference Slides
19	4/2	First Order Logic, Godel Thms. (Chp 8) Resolution Thm Proving in FOL (Chp 9) Unification, Herbrand Universe	FOL slides
20	4/4	More logic	Theorem Proving Code & examples Project #3 DUE TUESDAY 2 April FOR ALL IN-CLASS AND CVN STUDENTS . If you love logic, prove 2+2=4
21	4/9	Semantic nets/Frames Inference in nets (Chp 12) Frames, Rule-based Systems Backward chaining, Prolog	TOURNAMENT PLAYOFFS FRIDAY APR 5 Pictures from the Tournament Play from 2013 The winning strategy Intersection search Rules
22	4/11	Uncertainty (Chp 13, 14)	Uncertainty slides
23	4/16	Bayesian Inference	Bayesian inference slides
24	4/18	Intro to Machine Learning (Chp 18)	Learning Slides Project #4: Decision Tree Learning
25	4/23	Generalization, Inductive Inference (Chp 19)	Chpt19-slides
26	4/25	Decision Tree Learning Naive Bayes Classifier	ID3 and example NB-slides
27	4/30	Unsupervised Learning
28	5/2	LAST CLASS – INCLASS FINAL EXAM	Resurgence of AI – or more of the same? http://www.nytimes.com/2009/12/08/science/08sail.html
	5/7		Project #4 DUE TUE 7 MAY, 2013 In case I’m late, this is filler time.
			End of Spring 2013 TERM. Summer Break begins. Hurray. I will miss you.