ComS 472: Principles of Artificial Intelligence
Department of
Computer
Science
Iowa
State
University
Fall 2009
STUDY GUIDE
The materials to be covered each week and the assigned readings (along with
online lecture notes, if available) are included on this page. The links to
lecture notes will not be in place usually until a week after the lecture. The
assigned readings are divided into required and recommended readings. You will
be responsible for the materials covered in the lectures and the assigned
required readings. You are strongly encouraged to explore the recommended
readings.
Survival Tips
- Keep up with the assigned
readings.
- If you don't understand
something in class, or the assigned problems/labs/readings, ask
questions!
- Do not postpone working on
assignments.
- Before you come to class,
review the materials from the previous lecture and come prepared to ask
any questions that you might have.
Week 1 (starting August 24, 2009)
Overview of the course
Overview of artificial intelligence: What is
intelligence? What is artificial intelligence (AI)? History of AI.
Introduction to intelligent agents. Rationality. PEAS description of the
environment. Environment types. Structure of agents.
Required
Readings
-- Artificial Intelligence
Assignments
Required
Readings
-- Programming
You may skip most of these readings if you have prior programming experience
in Java.
Recommended Materials
Week 2 (beginning August 31, 2008)
Problem-solving as state space search. Formulation of state-space search
problems. Tree and Graph search algorithms. Basic search algorithms and their
properties: completeness, optimality, space and time complexity. Breadth-first
search, depth-first search, depth-limited and iterative deepening search.
Required readings
Week 3 (beginning September 7, 2008)
Informed (Heuristic) search. A* Search. Optimality of the A* algorithm.
Heuristic functions
Required readings
Assignments
Week 4 (beginning September 14, 2009)
Local search: hill-climbing search and variants, Simulated annealing, local beam
search, genetic algorithm.
Constraint satisfaction problems (CSPs): Problem solving as Constraint
Satisfaction. Backtracking search, variable ordering heuristics, constraint
propagation.
Required readings
Recommended readings
Assignments
- Lab 1, due Wednesday Sep.
30, 2009, 11:00am.
Week 5 (beginning September 21, 2009)
Constraint satisfaction problems (CSPs): Local search. Problem structures.
Game-playing: The minimax algorithm. The alpha-beta-pruning algorithm.
Cutting-off search for real-time decisions.
Introduction to Knowledge-based agents. Knowledge representation using logic.
Required readings
Assignments
Announcements
- Jin Tian's office hours on Sep. 28 and 30 are cancelled.
Week 6 (beginning September 28, 2009)
Propositional Logic: Syntax and Semantics; Inference rules. Reasoning in
propositional logic: the resolution rule, Horn clauses, Forward and Backward
chaining. DPLL and WALKSAT algorithms.
Required readings
Week 7 (beginning October 5, 2009)
First-Order Logic (FOL): Syntax and semantics; using FOL; Knowledge
engineering in FOL.
Inference in FOL: propositionalization
Required readings
Assignments
Announcements
- The midterm is scheduled: Wednesday October 21, 2009 in class.
Closed-book, closed-notes. Cover materials up to and including Chapter 9.
Week 8 (beginning October 12, 2009)
Inference in FOL: Unification; Forward chaining; Backward chaining;
Resolution
Knowledge Representation and Reasoning Under Uncertainty. Review of elements
of probability
Required readings
Week 9 (beginning October 19, 2009)
Review of elements of probability: inference, independence, Bayes rule.
Midterm exam
Bayesian Networks: Syntax and Semantics
Required readings
Assignments
Additional Information
- Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference. (1997).
- Castillo, E., Gutierrez, J. M., Hadi, A. S. Expert Systems and
Probabilistic Network Models. Berlin: Springer (1996).
- Cowell, R. G. Lauritzen, S. L., and Spiegelhalter, D. J. Probabilistic
Networks and Expert Systems Berlin: Springer (2005).
- Korb, K.B., and Nicholson, A.E., Bayesian Artificial Intelligence,
Chapman and Hall (2004).
Week 10 (beginning October 26, 2009)
Bayesian Networks: D-separation, modeling, inference.
Required readings
Assignments
- Lab 2, due Friday November
6, 2009 11:00am.
Recommended readings
Additional Information
- Bayesian
Network software packages
- Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference. (1997).
- Castillo, E., Gutierrez, J. M., Hadi, A. S. Expert Systems and
Probabilistic Network Models. Berlin: Springer (1996).
- Cowell, R. G. Lauritzen, S. L., and Spiegelhalter, D. J. Probabilistic
Networks and Expert Systems Berlin: Springer (2005).
- Korb, K.B., and Nicholson, A.E., Bayesian Artificial Intelligence,
Chapman and Hall (2004).
Week 11 (beginning November 2, 2009)
Bayesian Networks: inference.
Learning agents. Machine learning. Bayesian decision theory: Bayes decision
rule, loss function, Minimum Risk Bayes Classifier, Minimum-error-rate
classification.
Parameter Estimation: Maximum-Likelihood estimation
Required readings
Recommended readings
- Chapter 2, Duda, R., Hart, P., & Stork, D., Pattern Classification. New
York: Wiley. (2001).
- Chapter 6, Mitchell, T., Machine Learning. New York: Mc Graw-Hill.
(1997).
Week 12 (beginning November 9, 2009)
Naive Bayes Classifier: classifying text documents. Performance evaluation:
Cross-validation.
Decision tree classifier: Decision Tree Learning Algorithm (Quinlan's ID3
Algorithm)
Required readings
Assignments
- Lab 3, due Friday November 20, 2009, 11am.
Recommended readings
- Chapter 6, Chapter 3, Mitchell, T., Machine Learning. New York: Mc Graw-Hill.
(1997).
Additional Information
Week 13 (beginning November 16, 2009)
Decision tree classifier: overfitting, missing data
Linear models for classification: Linear Discriminant Functions, Perceptrons,
Multi-category classification, Winner-Take-All (WTA) networks (linear machines).
Linear models for Regression: Least Mean Squared (LMS) Error Criterion,
Gradient descent algorithm
Required readings
Recommended readings
- Chapter 3, 4, Mitchell, T., Machine Learning. New York: Mc Graw-Hill.
(1997).
- Chapter 5, Duda, R., Hart, P., & Stork, D., Pattern Classification. New
York: Wiley. (2001).
Thanksgiving break