Math Foundations — Lecture 4

Argmax, combinatorics, greedy vs exhaustive, softmax sampling, beam search, Viterbi DP.

Argmax & scoring

Given a model that assigns score \(s(\mathbf{x},\mathbf{y})\) to each (input, output) pair, inference seeks:

\[\hat{\mathbf{y}}=\arg\max_{\mathbf{y}\in\mathcal{Y}} s(\mathbf{x},\mathbf{y})\]

When \(|\mathcal{Y}|\) is small (e.g. class labels), exhaustive enumeration is fine. When \(\mathcal{Y}\) is structured (sequences, trees), search is needed.

Combinatorial explosion in tagging

Sequence of \(n\) tokens, tag set \(T\) with \(|T|\) tags. Exhaustive: score all \(|T|^n\) sequences.

\[|T|^n \quad\text{e.g.}\quad 17^{4}\approx 8.4\times 10^4,\qquad 17^{20}\approx 4\times 10^{24}\]

Grows exponentially in \(n\) → intractable for long sentences.

Quick Check: With 45 POS tags and a 15-word sentence, the exhaustive search space is roughly:

\(45^{15}\approx 10^{24.8}\)

\(45\times 15=675\)

Greedy decoding

At each step \(t\), pick the best tag independently:

\[\hat y_t = \arg\max_{y\in T}\; s_t(y)\]

Total cost: \(O(n\,|T|)\) — linear in sequence length. Not globally optimal; early mistakes propagate.

Softmax & sampling strategies

Turn scores into probabilities, then sample:

\[p(y_t=w)=\frac{e^{s_w/\tau}}{\sum_{w'}e^{s_{w'}/\tau}}\]

\(\tau\)Temperature. \(\tau\to 0\) → argmax; \(\tau\to\infty\) → uniform.

Top-\(k\)

Restrict to the \(k\) highest-scoring tokens, re-normalise, then sample. Fixed set size regardless of distribution shape.

Top-\(p\) (nucleus)

Keep the smallest set of tokens whose cumulative probability \(\ge p\). Adapts to distribution: sharp → few tokens; flat → many.

Quick Check: Which adapts its candidate set size to the distribution shape?

Top-\(k\)

Top-\(p\)

Beam search

Maintain a set of \(K\) partial hypotheses (the "beam"). At each step:

Extend each hypothesis by every possible next token.
Score all extensions.
Keep only the top-\(K\).

Complexity per step: \(O(K\,|V|)\). Total: \(O(T\,K\,|V|)\) where \(T\) is max length.

Log-prob & length normalisation

Scores are usually log-probabilities (sums instead of products). Shorter sequences have fewer negative terms → bias toward short outputs. Fix:

\[\text{score}_\text{norm}=\frac{1}{|\mathbf{y}|^\alpha}\sum_{t=1}^{|\mathbf{y}|}\log p(y_t\mid y_{

\(\alpha=1\) → average log-prob per token; \(\alpha=0\) → no normalisation.

Viterbi algorithm

For chain-structured models (e.g. HMM, CRF): score decomposes into per-step and transition terms.

\[s(\mathbf{y})=\sum_{t=1}^{n}\bigl[\text{emit}(y_t, \mathbf{x}_t)+\text{trans}(y_{t-1},y_t)\bigr]\]

Dynamic programming recurrence:

\[\delta_t(j)=\max_{i}\bigl[\delta_{t-1}(i)+\text{trans}(i,j)+\text{emit}(j,\mathbf{x}_t)\bigr]\]

Complexity: \(O(n\,|T|^2)\) — polynomial, not exponential. Back-pointers recover the best path.

Quick Check: Viterbi is \(O(n|T|^2)\). Exhaustive is \(O(|T|^n)\). For \(|T|=17, n=10\), which is smaller?

\(10\times 17^2=2890\) (Viterbi)

\(17^{10}\approx 2\times 10^{12}\) (Exhaustive)