CS4804 Fall 2016 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.

Environments and Agents

• PEAS: performance measure, environment, actuators, sensors
• Single-agent vs. multi-agent
• Stochastic vs. deterministic
• Episodic vs. sequential
• Dynamic vs. static
• Continuous vs. discrete

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*
• 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

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

Probability and Bayesian networks

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

Machine learning

• supervised learning
• validation, fold-based cross-validation, leave-one-out cross validation
• Neural network concepts: activation/squashing functions, back-propagation
• (Especially because I presented the material without a good accompanying text, I won’t expect you to know the details of learning algorithms. Instead, I’ll expect you to understand 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.)