CS5804 Spring 2015 Final Topic List

This is a list of concepts that I’ll expect you to have a good understanding of now that you’re finishing the course. You don’t need to know the exact details of every concept, but having a rough idea of what each means and connections to other concepts will help you use AI ideas in your future work. For the final exam, since you’re free to use the book, your class notes, and my class materials, as well as any properly cited external materials from the Internet or other books, you certainly don’t need to memorize specific details.

Search

• Problem formulations: states, actions, transitions, costs, goals
• Algorithmic framework: frontier, expansion
• Uninformed search algorithms: BFS, DFS, uniform-cost, iterative-deepening
• Informed search: greedy heuristic, A*, (Beam search)
• Properties of search algorithms: completeness, optimality, time and space complexity
• Properties of heuristics: admissibility, consistency

Adversarial search

• minimax search algorithm
• alpha-beta pruning
• Variants of minimax: maximax (or any order of agent goals), expectimax

Logic

• Knowledge base
• Propositional logic
• concepts: literals, negations, conjunctions, disjunctions, implications
• entailment
• inference rules: modus ponens, resolution
• completeness of inference
• First-order logic
  • quantifiers: existential, universal
  • predicates
• Horn clauses, definite clauses
• Forward-chaining, backward chaining

Probability and Bayesian networks

• conditional probability
• independence
• inference in Bayesian networks
• conditional independence in Bayesian networks
• hidden Markov models

Markov decision processes

• MDP descriptions: states, transition probabilities, rewards
• Bellman utility function
• conversion between different forms of rewards
• value iteration
• policy iteration

Reinforcement Learning

• Passive vs active learning
• Adaptive dynamic programming
• temporal-difference learning
• Q-learning
• approximate state functions

Machine learning

• supervised learning
• validation, fold-based cross-validation, leave-one-out cross validation

(Especially because I presented the material without a good accompanying text, I won’t be testing you on the details of the learning algorithms. Instead, I’ll test you on the macro-level concepts of machine learning: how supervised learning is set up, as described in 18.2 of R+N, and how to tune parameters via different forms of validation, as briefly discussed on the 1.5-page introduction of Section 18.4 in R+N.)

Topics covered in class not required for exam

• perceptron
• multi-class perceptron
• MIRA algorithm
• particle filter (and approximate inference)
• structured output perceptron
• self-driving car research
• knowledge graph research
• AI and society
• convergence of value iteration