COMS W  4701

Artificial Intelligence

 

Spring 2013

Tuesday/Thursday 2:40-3:55PM

Room: 833 MUDD
CVN Course

 

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.

 

Grading Policy

Click Here

 

Project Submission Instructions

Click Here

 

How to use CLIC lab machines

AIMA Code base:

Just visit their link http://www.cs.berkeley.edu/~russell/code/doc/install.html

 

 

 

 

 

TA Details

 

Probable Final Grade Distribution

Final grades are curved.

The distribution is tentatively set at

 

Name:   Adrian Tang (Head TA)

E-mail:  atang@cs.columbia.edu

Office:  TA Room (Mudd 122a)    

TA office hours: Wed 6-8pm

 

Name:   John Sizemore

E-mail:  jcs2213@columbia.edu  

Office:  TA Room (Mudd 122a)    

TA office hours: Tue 4-6pm

 

Name:   Tingting Ai                          

E-mail:  ta2355@columbia.edu

Office:  TA Room (Mudd 122a)                                    

TA office hours: Thu 10am-12pm

 

Name:   Kangkook Jee                   

E-mail:  jikk@cs.columbia.edu

Office:  CSB 504

TA office hours: Mon 10am-12pm

 

Name:   Qiuzi Shangguan              

E-mail:  qs2130@columbia.edu

Office:  TA Room (Mudd 122a)    

TA office hours: Fri 4pm-6pm

 

HW/Test

Percentage

Project #1

15%

Project #2

15%

Project #3

20%

Project #4 

15%

MIDTERM

15%

FINAL

20%