You're expected to still remember material from the two midterms. The final will partly focus on new concepts, but also contain some review questions. It will be about twice as long as a midterm and you'll have two hours to do it.

Neural Nets

• Basic design (i.e. connected set of linear classifiers)
• What kinds of functions can a neural net approximate?
• Training
  • Top-level (aka simple) update equation for a single weight in the network
  • What does backpropagation compute? (Not the details of how the computation is done.)
  • Symmetry breaking
  • Data augmentation
  • Dropout
• Convolutional neural networks
  • How does a convolutional layer work (e.g. connection pattern)?
  • What is a pooling layer?
  • Overall architecture, e.g. what kinds of features are detected in early vs. late layers?
  • What is a CNN typically used for? Why is it a better choice than a fully-connected network?
• What (briefly) is a
  • Recurrent neural network
  • Generative adversarial neural network
• Adversarial examples

Markov Decision Processes

• Model and terminology for an MDP
• Bellman equation
• Methods of solving the Bellman equation
  • Value iteration
  • Policy iteration
  • Asynchronous dynamic programming

Reinforcement Learning

• Model-based reinforcement learning
• Model-free reinforcement learning
  • Q-learning version of Bellman equation (expressing Q in terms of itself, without reference to the utility or transition probability functions)
  • TD update algorithm
  • SARSA update algorithm
  • How do TD and SARSA differ?
• The role of exploration in action selection (aka exploration vs. exploitation)
• Online, offline, experience replay

You've done an MP using Q-learning with TD update, so you should have a detailed understanding of how it works.

Game Search

• Game tree
• Zero-sum games
• Basic method
  • Minimax strategy
  • Minimax search (using depth-first search)
  • Depth cutoff
  • Heuristic state evaluation
• Alpha-beta pruning
  • How it works
  • How well it works
  • Impact of move ordering
  • You will not have to write out detailed code for alpha-beta search. Concentrate on understanding what branches it prunes and why.
• Optimizations around depth cutoff
  • Horizon effect
  • Quiescence search
  • Singular extension
  • Pruning unpromising branches
• Other optimizations
  • Memoization (transposition table)
  • Opening moves, endgames
• Adapting these methods to games involving chance

Vector Semantics

• Weaknesses of logic-based representations of meaning
• Basic feature vectors
  • From documents
  • From local context
• Normalization and smoothing
  • TF-IDF
  • PMI and PPMI
• Cosine/dot product similarity
• Singular value decomposition (Principal Components Analysis)
• Word2vec (skip-gram)
  • Main outline of algorithm
  • Negative sampling
  • Sigmoid function (definition, relating probabilities of good and bad)
  • Why are words and contexts embedded separately?
• Word2vec details
  • Uses more negative examples than positive ones
  • Raising context counts to a power
  • Weighting context words by distance from focus word
  • Deleting rare words, subsampling frequent ones
• How does word2vec model analogies and compositional semantics?