COMS W4701

Artificial Intelligence


Fall 2013

Tuesday & Thursday 2:40-3:55PM

Room: 833 MUDD


Jonathan Voris
612 CEPSR
jvoris at cs dot columbia dot edu

Office Hours: Tuesday & Thursday 4:00-5:00PM



Text Book

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

Syllabus

 

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

- Introduction to LISP: Examples

- Assignment #1: Pattern Matcher

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

* Game Playing: Minimax, Alpha-Beta

*Assignment #3: 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: TBA

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

Tentative Course Schedule

Session

Date

Topic/chapter

Course Material

1

9/3

What is AI? (Chapter 1)

Intro Slides

2

9/5

History of AI (Chapter 1)

Intelligent Agents (Chapter 2)

Intelligent Agents

3

9/10

Intelligent Agents Continued
(Chapter 2)

4

9/12

Introduction to LISP

Lisp Crash Course

Lisp Code Notes


Project#1: Pattern Matcher MUST BE IN LISP


Notes on Pattern Matcher Design

 

How To Run Lisp

LispWorks Personal Edition
LISP Primer
Load and compile in Lispworks

See http://www.cs.berkeley.edu/~russell/code/doc/install.html

5

9/17

Lisp Continued
Search Based Problem Solving

(Chapter 3)

Search Slides #1

Basic search

6

9/19

Search Based Problem Solving Continued
(Chapter 3)

Search Slides #2
Iterative DFS search
8 Puzzle state

Convert states to symbols

7

9/24

Problem Solving Agents
(Chapter 3)

Search Slides #3

8

9/26

Heuristic Aided Search
(Chapter 3)

Heuristic Search Slides

An improved NORTH operator for 15 puzzle
Uniform cost, Greedy search, Bidirectional search

9

10/1

Heuristic Admissibility & Consistency

Beyond Classical Search
(Chapter 4)

 

 

Local Search Slides

PROJECT #1 DUE AT 11:59:59 PM EDT

A star search

Iterative A star search

A* and local search heuristics

10

10/3

Beyond Classical Search Continued
(Chapter 4)

Project#2: Sokoban Agent

11

10/8

Game Playing

(Chapter 5)

Game Playing Slides

Last day to drop - more AI fun for the rest of us!

12

10/10

Game Playing

(Chapter 5)

Sokoban Puzzles

13 

10/15

Minimax/Alpha-beta

(Chapter 5)

MinimaxAlpha-Beta

14

10/17

Alpha-Beta Pruning Continued

Constraint Satisfaction Problems

(Chapters 5 & 6)

Another Alpha-Beta Pruning Example

Constraint Satisfaction Problem Slides

15

10/22

Pre-Midterm Review

16

10/24

MIDTERM

PROJECT #2 DUE AT 11:59:59 PM EDT

17

10/29

Post-Midterm Review

18

10/31

Constraint Satisfaction Problems Continued

(Chapter 6)

Project#3: Gomoku Agent

19

11/5

Election Day

No Class - Go vote!

20

11/7

Forward Checking Example

Logical Agents

(Chapters 6 &7)

Logical Agent Slides

21

11/12

Logical Agents Continued

(Chapter 7)

22

11/14

Logical Agents Continued

(Chapter 7)

23

11/19

Logical Agents Continued

(Chapter 7)

PROJECT #3 DUE AT 11:59:59 PM EST

24

11/21

Logical Agents Continued

First Order Logic

(Chapters 7 & 8)

First Order Logic Slides

11/22

Gomoku Agent Tournament

Starting at Noon

In the Clic Lab

25

11/26

First Order Logic Continued

(Chapter 8)

PROJECT #4: Inference Algorithms

26

11/28

Thanksgiving

No Class - Enjoy your turkey!

27

12/3

Resolution in First Order Logic

and/or Final Review

(Chapter 9 and/or all the Chapters)

28

12/5

FINAL

29

12/10

PROJECT #4 DUE AT 11:59:59 PM EST

 

Grading Policy


Project Submission Instructions


How to use CLIC lab machines

AIMA Code base

TA Details

 

Probable Final Grade Distribution

Final grades are curved.

The distribution is tentatively set at

 

Name: Tingting Ai

E-mail:  ta2355 at columbia dot edu

Office:  Mudd 122 (TA room)

TA office hours: Mon 4:00-6:00PM

                                   Wed 10:00AM-Noon

 

Name: John Sizemore

E-mail: jcs2213 at columbia dot edu

Office: Mudd 122 (TA room)

TA office hours: Tue 4:00-6:00PM

 

Name: Keqiu Hu

E-mail: kh2567 at columbia dot edu

Office: Mudd 122 (TA room)

TA office hours: Thu 4:00-6:00PM

 

Name: Ya Cai

E-mail: yc2788 at columbia dot edu

Office: Mudd 122 (TA room)

TA office hours: Tue 10:00-12:00AM

 

Name: Fang-Hsiang Su

E-mail: mikefhsu at cs dot columbia dot edu

Office: CEPSR 608

TA office hours: Thu 5:00-7:00PM

 

HW/Test

Percentage

Project #1

15%

Project #2

15%

Project #3

15%

Project #4 

15%

MIDTERM

15%

FINAL

20%

Class Participation 

5%