## COMP 3211 - Spring 2016

**Spring 2016, COMP 3211 Introduction to Artificial Intelligence [3-0-1:3]**

Lecture 1, MoWe 09:00-10:20, Rm 2304 at L17/18

**Prof. Dekai WU**, Rm 3539,
2358-6989, dekai@cs.ust.hk

Lab 1A TA: **Meriem BELOUCIF**, Fr 12:00-12:50, Rm 2404 at L17/18, mbeloucif@cs.ust.hk

You are welcome to knock on the door of the instructor any time. The TAs' office hours are posted at http://course.cs.ust.hk/comp3211/ta/.

### ANNOUNCEMENTS

Welcome to COMP3211! (This course was formerly called COMP221.) Tutorials will begin after Week 2.

**Always** check the Discussion Forum for up-to-the-minute
announcements.

**Discussion forum** is at http://comp151.cse.ust.hk/~dekai/content/?q=forum/3.
Always read before asking/posting/emailing your question.

**Course home page** is at http://www.cs.ust.hk/~dekai/3211/.

**Tutorial info** is at http://course.cs.ust.hk/comp3211/ta/.

### ORIENTATION

#### Course Description

**COMP 3211.** Foundations underlying design of
intelligent systems. Relations between logical, statistical,
cognitive, biological paradigms; basic techniques for heuristic
search, theorem proving, knowledge representation, adaptation;
applications in vision, language, planning, expert systems.

#### Course Outcomes

- Identify the fundamental concepts and techniques of AI: autonomous agents, search, knowledge representation, and machine learning.
- Understand and apply techniques for searching state spaces, including breadth-first, depth-first, best-first, A* search, minmax game tree search, minmax with alpha-beta pruning, and hill-climbing search.
- Appreciate some cutting edge research in AI such as multiagent systems, game theory, ontology, semantic web, big data, deep learning, and others.

### TEXTBOOKS

*Introduction to Text Alignment: Statistical Machine Translation Models from Bitexts to Bigrammars*(forthcoming), by**Dekai WU**. Springer, 2016.*Artificial Intelligence: A Modern Approach*(2nd Edition), by**Stuart RUSSELL**and**Peter NORVIG**. Prentice-Hall, 2003. ISBN-13: 978-0137903955.*Structure and Interpretation of Computer Programs*(2nd edition), by**Harold ABELSON**and**Gerald Jay SUSSMAN**, with**Julie SUSSMAN**. MIT Press, 1984. ISBN-10: 0-262-01077-1.

**Full text and code are available online at no cost**for the Scheme book (*Structure and Interpretation of Computer Programs*) at http://mitpress.mit.edu/sicp/.

### HONOR POLICY

To receive a passing grade, you are required to sign an honor statement acknowledging that you understand and will uphold all policies on plagiarism and collaboration.#### Plagiarism

All materials submitted for grading must be your own work. You are advised
against being involved in any form of copying (either copying other people's
work or **allowing others to copy yours**). If you are found to be involved
in an incident of plagiarism, **you will receive a failing grade for the
course and the incident will be reported for appropriate disciplinary
actions**.

University policy requires that students who cheat more than once be expelled. Please review the cheating topic from your UST Student Orientation.

Warning: sophisticated plagiarism detection systems are in operation!

#### Collaboration

You are encouraged to collaborate in study groups. However, you must write up solutions on your own.**You must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates.**Other cases will be dealt with as plagiarism.

### GRADING

The course will be graded on a curve, but no matter what the curve is, I guarantee you the following.

If you achieve | 85% |
you will receive at least a | A |
grade. |

75% |
B |
|||

65% |
C |
|||

55% |
D |

Your grade will be determined by a combination of factors:

Midterm exam | ~20% |

Final exam | ~25% |

Participation | ~5% |

Assignments | ~50% |

#### Examinations

No reading material is allowed during the examinations. No make-ups will be given unless prior approval is granted by the instructor, or you are in unfavorable medical condition with physician's documentation on the day of the examination. In addition, being absent at the final examination results in automatic failure of the course according to university regulations, unless prior approval is obtained from the department head.There will be one midterm worth approximately 20%, and one final exam worth approximately 25%.

#### Participation

Science and engineering (including software engineering!) is about communication between people. Good participation in class and/or the online forum will count for approximately 5%.

#### Assignments

All assignments must be submitted by **23:00** on the due date. Scheme programming assignments must run under **Chicken Scheme** on **Linux**. Assignments will be collected electronically using the automated CASS assignment collection system. Late assignments cannot be accepted. Sorry, in the interest of fairness, exceptions cannot be made.

Programming assignments will account for a total of approximately 50%.

#### Tutorials

All information for tutorials is at http://course.cs.ust.hk/comp3211/ta/.

### SYLLABUS

Date |
Wk |
Event |
Topic |
||

2016.02.01 | 1 | Lecture | Does God play dice? Assumptions: scientific method, hypotheses, models, learning, probability; linguistic relativism and the Sapir-Whorf hypothesis; inductive bias, language bias, search bias; the great cycle of intelligence | ||

2013.09.03 | 1 | Lecture | Languages of the world Admiinistrivia (honor statement, HKUST classroom conduct) |
||

2016.09.08 | 2 | Holiday | Lunar New Year | ||

2016.09.10 | 2 | Holiday | Lunar New Year | ||

2016.02.12 | 2 | Lecture | Learning to translate: engineering, social, and scientific motivations; "It's all Chinese to me": linguistic complexity; challenges in modeling translation [at tutorial] | ||

2015.02.15 | 3 | Lecture | Is machine translation intelligent? Interactive simulation | ||

2016.02.17 | 3 | Lecture | Evaluating translation quality: adequacy, fluency, fidelity, speed, memory, n-grams, BLEU | ||

2013.02.19 | 3 | Lecture | Functional programming; Scheme [at tutorial] | ||

2016.02.22 | 4 | Lecture | Scheme (cont'd) | ||

2016.02.24 | 4 | Lecture | Basic probability theory; conditional probabilities; Bayes' theorem | ||

2016.02.29 | 5 | Lecture | Introduction to search; anagrams | ||

2016.03.02 | 5 | Lecture | Markov models, n-gram models | ||

2016.03.07 | 6 | Lecture | Uninformed search; BFS, DFS, depth-bounded search, iterative deepening | ||

2016.03.09 | 6 | Lecture | Informed search; Dijkstra's shortest path algorithm | ||

2016.03.14 | 7 | Lecture | Anagrams with replacement; Chinese anagrams; word n-grams | ||

2016.03.16 | 7 | Lecture | Bag translation | ||

2016.03.21 | 8 | Lecture | HMM/SFSA/WFSA: hidden Markov models, finite-state models; parts of speech; generation vs recognition/parsing | ||

2016.03.23 | 8 | Lecture | Converting state-based to transition based FSAs; segmental HMM/SFA/WFSAs | ||

2016.03.28 | 8 | Holiday | Easter Monday | ||

2016.03.30 | 8 | Lecture | HMM/SFSA/WFSA decoding, evaluation, learning: unrolling in time; ways to traverse the lattice; formalization for Viterbi decoding and evaluation [slides] | ||

2016.04.04 | 9 | Holiday | Ching Ming Festival | ||

2016.04.06 | 9 | Exam | Midterm | ||

2016.04.11 | 10 | Lecture | HMM/SFSA/WFSA: forward algorithm, backward algorithm, expectations | ||

2016.04.13 | 10 | Lecture | HMM/SFSA/WFSA: forward-backward algorithm, expectation maximization (EM) algorithm | ||

2016.04.15 | 10 | Lecture | In-class quiz/exercise: expectation maximization (EM) algorithm | ||

2016.04.18 | 11 | Lecture | In-class quiz/exercise: expectation maximization (EM) algorithm | ||

2016.04.20 | 11 | Lecture | Heuristic functions; admissibility; A* search | ||

2016.04.22 | 11 | Lecture | Knowledge representation: conjunctive normal form; 3-CNF; AND/OR graphs; FSGs (finite-state grammars) and segmental FSGs; FSGs as hypergraphs; Knuth's algorithm | ||

2016.04.25 | 12 | Lecture | FOPL (first-order predicate logic); CFGs (context-free grammars); DCGs (definite clause grammars); stochastic CFGs; weighted CFGs; segmental CFGs; instantiating CFGs in time | ||

2016.04.27 | 12 | Lecture | Applying abstract models to different task domains; HMM alignment | ||

2016.05.02 | 13 | Holiday | Labor Day | ||

2016.05.04 | 13 | Lecture | Representing compositional knowledge; syntax-directed transduction grammars; inversion transduction grammars [article]; generative capacity of ITGs; bracketing ITGs; optimal bilingual parsing for alignment, bibracketing, translation-driven segmentation, learning phrasal translation lexicons, projection/coercion | ||

2016.05.09 | 13 | Lecture | Knowledge representation with semantic frames; the magic number 4: how the generative capacity of ITGs explains the evolution of semantic frame structure | ||

2016.05.19 | 14 | Exam | COMP3211 Final [TKPH, 08:30-11:30] |

#### Background review

- Scheme slides
- Scheme R5RS [html, pdf]
- Chicken Scheme 4.10 manual
- Chicken Scheme 4 eggs
- A1 (due 2016.04.01)

*dekai@cs.ust.hk*

Last updated: 2016.05.09