CPSC 502: Artificial Intelligence I

What do you need to know for the exam?

The exam is on November 13. You may bring in a sheet of letter-sized paper with anything written on it. You don't need to know anything beyond what is here and what was in the assignments. (Assume that asides were for your education and not examinable).

You need to be able to:

Module 0 - AI and Agents

• Explain the abstraction of an agent.
• Explain the dimensions of complexity.

Module 1 - Searching and Constraints

• Design the state space for a problem.
• Design an admissible heuristic.
• Trace depth-first, breadth-first, A*, branch and bound for particular example.
• Trace domain consistency, arc consistency, and domain splitting.
• Interpret the runtime distribution of a stochastic local search.
• Predict the effect of picking the best variable and/or value with picking a random one.
• Some previous exam questions: AIFCA Exercises 3.4, 4.2, 4.6.

Module 2 - Logic and Planning.

• Given a set of clauses, give an interpretation, model and the logical consequences.
• Write some clauses for some story.
• Predict the effect of negation-as-failure. Explain how it can be used for default reasoning.
• Find explanations, given assumables.
• Describe a domain using STRIPs and the feature-based representation.
• Trace: forward planner, regression planner, and planning as a CSP.
• Some previous exam questions: AIFCA Exercises 5.3, 5.4, 5.7, 8.1, 8.5.

Module 3 - Reasoning under Uncertainty

• Use the definition of possible worlds, conditioning and independence to explain or compute a probability.
• Predict the effect of observing on a belief network (what beliefs are changed).
• Trace variable elimination, rejection sampling, likelihood weighting, particle filtering for a simple example.
• Build a belief network or an HMM for some story.
• Predict the effect of observations in an HMM.
• Some previous exam questions: AIFCA Exercises 6.2, 6.6, 6.8, 6.13.

Module 4 - Making Decisions

• Design utilities that follow some story.
• Build a decision network for a story.
• Trace variable elimination for optimizing a decision network.
• Build an MDP for a story (knowing the components of an MDP).
• Trace value iteration and asynchronous value iteration.
• Some previous exam questions: AIFCA Exercises 9.3, 9.7, 9.8, 9.10, 9.15, 9.16, 9.17.

Module 5 - Machine Learning

• Explain why overfitting occurs and how it can be overcome.
• Explain the role of a training set, a validation set and a test set.
• Trace decision tree learning.
• Explain the difference between on-policy and off-policy learning.
• Trace Q-learning and SARSA.
• Some previous exam questions: AIFCA Exercises 7.9, 11.4, 11.5.

Module 6 - Individuals and Relations

• Relational Probabilistic models: how to specify them and their grounding
• Statistical language models: set of words, unigrams, bigrams, topic models

Last updated: 2013-10-29, David Poole