CS 6601:  Final Study Guide

Note:  R&N = AI, A Modern Approach, by Russell & Norvig

• Adversarial search (R&N Chapter 5)

• Observable games (e.g. isolation)
• Minimax
• Alpha-beta pruning

• Performance improvement

• Utility and evaluation functions

• Sensitivity

• Optimization tricks

• Move-ordering
• Symmetry

• Iterative deepening
• Multiplayer games
• Probabilistic games
• Partially observable games (e.g. poker)

• Search (R&N Chapter 3, uninformed and informed)

• Uninformed

• Breadth-first search
• Depth-first search
• Depth-limited search
• Iterative deepening depth-first search

• Informed

• Uniform-cost search
• Greedy search
• A* search
• Heuristics

• Consistency/admissibility
• Dominance
• Derivation by relaxation

• Bidirectional
• Tridirectional
• Tree vs. graph search
• Completeness, space/time complexity, path optimality

• Agent design (R&N Chapter 2)

• Rationality
• PEAS

• Performance
• Environment

• Observability
• Deterministic/stochastic
• Episodic/sequential
• Static/dynamic
• Discrete/continuous
• Single/multi-agent

• Actuators
• Sensors

• Uncertainty

• Agent types

• Reflex
• Reflex with state
• Goal-based
• Utility-based
• Learning

• Random algorithms (part of R&N Chapter 4)

• Hill-climbing
• Beam search
• Iterative improvement
• Simulated annealing
• Genetic algorithms
• Local vs. global maximum
• Local stochastic search

• Constraint satisfaction problems (R&N Chapter 6)

• Variables, domains, constraints
• Standard search
• Backtracking
• Heuristics

• Minimum remaining values
• Least constraining value

• Forward-checking
• Arc consistency
• Path consistency
• Problem re-structuring

• Probability (R&N Chapters 13 and 14a, 14b)

• Independence/dependence
• Discrete/continuous variables
• Joint distribution
• Central Limit Theorem
• Conditional probabilities

• Bayes’ Rule
• Chain Rule
• Conditional independence

• Bayesian networks

• How to construct
• Local independence
• Inference

• Exact (calculation)

• Enumeration
• Variable elimination

• Inexact (sampling)

• Rejection sampling
• Stochastic simulation
• MCMC simulation

• Decision/utility theory

• Expected value

• Machine learning (part of R&N Chapters 18 and 20)

• Classification problems
• Gaussian distribution

• Central limit theorem

• Maximum likelihood estimate
• Decision boundaries
• Distance metrics:  Euclidean vs. Mahalanobis
• Training and testing

• Cross-validation, LOOCV
• Over/underfitting

• Accuracy

• Precision/recall

• k nearest neighbors
• Naive Bayes
• Mixture of Gaussians
• No free lunch

• Separability

• Linear vs. nonlinear

• Decision trees

• Entropy
• Information gain
• C4.5
• Random forests
• Decision “stumps”

• Boosting
• Clustering (i.e. unsupervised learning)

• k-means
• Inter/intra-class variance
• Descriptive length
• Gaussian mixture models
• Expectation Maximization

• Neural Networks

• Single-layer perceptron
• Multilayer perceptron
• Backpropagation

• Support Vector Machines

• Reasoning over time (R&N Chapter 15)

• Dynamic Time Warping

• Sakoe-Chiba bands

• Hidden Markov Models

• Sequence decoding

• Viterbi

• Probability estimation

• Forward-backward

• Training

• Baum-Welch

• Improvements

• N-gram models
• State tying
• Pruning, beam search
• Context-Free Grammars
• Segmentally-boosted HMMs

• Complex decisions (R&N Chapter 17 and 21)

• Utility functions
• Policy (vs. path)
• Finding optimal policy

• Bellman equation
• Value iteration
• Policy Iteration
• Q-learning
• SARSA
• Local consistency vs. global optimality

• Partially-observed Markov Decision Processes

• Belief state
• Particle filter

• Logic (R&N Chapters 7, 8 and 9)

• Propositional knowledge
• First-order logic

• Operators
• Existential quantifiers

• Knowledge base
• Entailment
• Inference

• Soundness vs. completeness
• Enumeration
• Logical equivalence

• Validity vs. satisfiability
• Forward/backward chaining
• Horn clauses
• Conjunctive Normal Form
• Resolution

• Proof by contradiction

• Universal/existential instantiation
• Reduction
• Unification

• Planning (R&N Chapter 11 plus this)

• STRIPS planner

• States
• Conditions
• Operators
• Goals
• Actions
• Plan

• Partially-ordered plans
• Conditional planning
• Monitoring

• Execution vs. action monitoring

• Replanning

• Clobbering
• Demotion/promotion