Notes

Dynamic programming is applicable when a problem has two properties: overlapping subproblems (the same subproblem is solved multiple times in a naive recursive approach) and optimal substructure (an optimal solution can be constructed from optimal solutions to subproblems).

The core patterns to recognize:

1. 1D DP — State is a single index. Classic examples: Fibonacci, climbing stairs, house robber. Ask: what's the recurrence relating dp[i] to dp[i-1] or dp[i-2]?

2. 2D DP — State is two indices, often (i, j) representing positions in two sequences. Classic: longest common subsequence, edit distance. The table fills left-to-right, top-to-bottom.

3. Interval DP — State is a range [i, j]. Classic: matrix chain multiplication, burst balloons. Usually requires iterating over interval length first.

4. Knapsack variants — Choosing items with constraints. 0/1 knapsack, unbounded knapsack, subset sum. Key: does order matter? Can items repeat?

The mental model shift that makes DP click: stop thinking recursively top-down and start thinking about which previous states you need to answer the current state. Define the state, write the recurrence, handle the base cases, decide the order of iteration.

Expected prediction error can be decomposed into three components: bias squared, variance, and irreducible noise. The last term is a floor you can't beat — it's inherent randomness in the data. The first two are what model selection actually controls.

Bias is error from wrong assumptions in the learning algorithm. High bias means the model is too simple — it underfits. A linear model on a cubic relationship has high bias regardless of how much data you throw at it.

Variance is error from sensitivity to fluctuations in training data. High variance means the model is too complex — it memorizes training noise and fails to generalize. A deep decision tree with no pruning is a classic high-variance model.

The tradeoff: reducing bias (more complex model) tends to increase variance, and vice versa. The goal is to find the sweet spot.

In practice: if train error is high, you have a bias problem — make the model more expressive. If train error is low but validation error is high, you have a variance problem — regularize, get more data, or simplify. This diagnostic framework is more useful than the math in most real situations.

A module-by-module review of what the CS 7650 midterm emphasizes — with focus on the why, not just definitions.

Module 1 — Intro to NLP: Language is hard because of ambiguity (lexical, syntactic), non-literal meaning (metaphor, idiom, sarcasm), productivity (new words), and context-dependence. Pipeline vocab: tokenization, normalization, BPE for OOV.

Module 2 — Foundations: Bayes' theorem, chain rule, conditional independence. Generalized Bayes assumes effects are conditionally independent given the cause — the basis of Naive Bayes. "Independent" ≠ "mutually exclusive."

Module 3 — Classification: Bag-of-words loses word order but works well. Naive Bayes: generative, closed-form, needs Laplace smoothing. Logistic regression: discriminative, gradient descent, handles correlated features. Log space prevents underflow and preserves argmax.

Module 4 — Language Models: LMs predict the next token. RNNs suffer from vanishing gradients; LSTMs fix this with input, forget, and output gates plus an additive cell state. Perplexity = exp(average cross-entropy) — lower is better.

Module 5 — Semantics: CBOW predicts center word from context; Skip-Gram predicts context from center word. IDF = log(N / df) — know how to compute by hand. Cosine similarity measures vector alignment.

Module 6 — Modern Architecture: Positional embeddings inject sequence order. Cross-attention attends to encoder outputs; masked self-attention prevents attending to future tokens. RLHF trains a reward model on human preferences, then fine-tunes the LM via RL.