MP practicalities

Questions related to what you built in MP 8 and 9.

Sequential neural nets

• Historical names
  • Vaswani et al
  • BERT
  • GPT and Llama families of LLMs
• Input and output
  • tokenization
  • convert tokens to vectors (e.g. word2vec)
  • positional encoding
• Recurrent neural networks
  • High-level view of how they work
  • When would we compute loss from last unit vs. summed over all units?
  • Bidirectional RNN
  • How does a "Gated RNN" differ from a standard one?
• Encoder-Decoder architecture
• Attention
  • Weighted sum of vectors in context window
  • Assessing similarity (learned weights plus dot product)
  • "Attention head" (and you can have more than one)
• Transformer blocks
  • what's in them (high-level)
  • residual connections
• LLMs
  • Masked vs. autoregressive
  • BERT, Llama, GPT
  • Pre-training, fine-tuning, task head
  • Training BERT
  • What is BERT good for?
  • Self-training autoregressive model
  • Using autoregressive model
  • Prompt engineering
  • Some very approximate sense of the number of parameters, amount of training data, etc

Markov Decision Processes

• Model and terminology for an MDP
• Quantized representation of continuous state variables via randomized actions
• Bellman equation
• Methods of solving the Bellman equation
  • Value iteration
  • Policy iteration
  • Asynchronous dynamic programming
• How to choose a policy?

Reinforcement Learning

• Basic setup for reinforcement learning (e.g. main loop)
• 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?
• Selecting an action
  • Deriving a policy from utility values or from Q values.
  • Incorporating exploration
• Online learning, offline learning, experience replay

Constraint satisfaction problems

Historical trivia and key examples

• Waltz line labelling
• 4-color theorem (proved here!)
• N-queens problem
• Map/graph coloring
• Graph coloring is NP-complete.

Hill-climbing

• how it works (high-level idea only)
• how it differs from backtracking search

Backtracking search (DFS)

• Variable assignments can be done in any order, search is to a known depth
• Why does DFS work well? Why isn't looping a worry?
• Heuristics for variable and value selection
  • most constrained/most constraining variable
  • least constraining value
  • exploit any symmetries in the problem
• Forward checking, constraint propagation
• AC-3 algorithm
• How to incorporate constraint propagation into backtracking search