Formula cheat sheet

Every definition, formula and complexity bound in 07-280, in course order, in the form the course states them. Built for the night before — not for learning from. Print it: the sidebar and top bar drop out automatically.

0. Notation you must not fumble

1. Search problems & the node record

→ Ch. 1 · Search problems, BFS/DFS/UCS

A solution is a sequence of actions (a plan) transforming the start state into a goal state. A state-space graph has one vertex per state (each state occurs once); edges are action transitions; the goal test picks out a set of goal vertices. Search trees can repeat states; state-space graphs cannot.

Node record

Nodes carry state, parent, action, path-cost. A child of parent_node via action $a$:

state     = result(parent_node.state, a)
parent    = parent_node
action    = a
path-cost = parent_node.path_cost
            + step_cost(parent_node.state, a, self.state)

Extract the solution by tracing back parent pointers and collecting actions (then reverse).

2. BFS / DFS / UCS / Greedy / A* at a glance

→ Ch. 1 · Ch. 2

$b$ = branching factor · $d$ = depth of the shallowest goal · $m$ = maximum depth of the tree · $C^{*}$ = optimal solution cost · $\varepsilon$ = smallest step cost. Greedy and A* worst cases assume a useless heuristic; a good $h$ shrinks the effective branching factor but the worst case stays exponential.

Special cases worth memorising: UCS is A* with $h = 0$. BFS is UCS when every step costs the same. Greedy is "A* with $g = 0$".

3. Heuristics, admissibility, consistency

→ Ch. 2 · Heuristics, Greedy & A*

$g(n)$ = cost of the path from the start to $n$ (backward cost, known) · $h(n)$ = estimate of the cheapest cost from $n$ to a goal (forward cost, guessed) · $h^{*}(n)$ = the true cheapest cost from $n$ to a nearest goal.

A* tree-search optimality proof, in five lines

Let $A$ be an optimal goal node and $B$ a suboptimal goal node, both on the frontier, and let $n$ be an ancestor of $A$ on the frontier (possibly the start, possibly $A$ itself).

Comparing and building heuristics

4. Games: minimax and expectimax

→ Ch. 3 · Minimax, α-β, Expectimax

"Standard" games are deterministic, observable, two-player, turn-taking and zero-sum. Zero-sum = opposite utilities, pure competition. General games = independent utilities, allowing cooperation, indifference, shifting alliances.

The one recursion that covers all three node types

function value(state)
    if state.is_leaf:        return state.value
    if state.player is MAX:  return max  over a in state.actions of value(state.result(a))
    if state.player is MIN:  return min  over a in state.actions of value(state.result(a))
    if state.player is CHANCE: return sum over s' in state.next_states of P(s') * value(s')

The answer at the root is an action:

Cost. Minimax is exhaustive DFS: time $O(b^{m})$, space $O(bm)$. Chess has $b \approx 35$, $m \approx 100$ — exact solution completely infeasible, hence bounded lookahead ("bounded rationality", Herbert Simon).

Evaluation functions (depth-limited search)

$f_i$ = a feature of the position, $w_i$ = its weight. Chess example: $w_1 = 9$, $f_1(s) = (\#\text{white queens} - \#\text{black queens})$. The ideal evaluation function returns the true minimax value; in practice it is a weighted linear sum of features. Deeper search generally means better play — or the same quality of play from a less accurate evaluation function.

Generalized minimax

For non-zero-sum or multi-player games: terminals carry utility tuples, node values are also tuples, and each player maximises its own component. E.g. with three players and terminal tuples $(0,0,7), (8,8,1), (7,7,2), (0,0,8)$, the player at each node picks the child whose tuple has the largest value in that player's slot. Cooperation and competition then emerge dynamically rather than being assumed.

5. α-β pruning

→ Ch. 3

def max-value(state, α, β):
    initialize v = -∞
    for each successor of state:
        v = max(v, value(successor, α, β))
        if v ≥ β
              return v
        α = max(α, v)
    return v

def min-value(state, α, β):
    initialize v = +∞
    for each successor of state:
        v = min(v, value(successor, α, β))
        if v ≤ α
              return v
        β = min(β, v)
    return v

Order matters inside the loop: test the cutoff first, update the bound second. In max-value you cut on $v \ge \beta$ and then raise $\alpha$; in min-value you cut on $v \le \alpha$ and then lower $\beta$.

6. Constraint satisfaction problems

→ Ch. 4 · Constraint Satisfaction

With finite domains of size $d$ and $n$ variables there are $O(d^{n})$ complete assignments. A binary CSP has constraints over at most two variables; its constraint graph has variables as nodes and constraints as edges.

Backtracking search

Backtracking search = DFS + two improvements.

• Idea 1 — one variable at a time. Variable assignments are commutative ([WA=red then NT=green] $\equiv$ [NT=green then WA=red]), so only ever assign a single variable per step. This cuts the branching factor from $nd$ to $d$.
• Idea 2 — check constraints as you go. Only consider values that do not conflict with previous assignments ("incremental goal test"). No need to check constraints for a complete assignment at the end.

Plain backtracking solves $n$-queens for $n \approx 25$; adding filtering + ordering makes 1000 queens feasible.

Filtering

Backtracking with AC-3 calls AC-3 many times — once per node of the backtracking tree — so this is the cost of one run.

Ordering heuristics

Not a contradiction: MRV picks a variable and you must eventually assign all of them, so fail fast. LCV picks a value and you only need one to work, so fail slow.

7. ML problem formulation

→ Ch. 5 · ML problem formulation

The i.i.d. assumption: all datapoints, training and test, are drawn independently and identically distributed from one unknown distribution on $\X \times \Y$. Without it, training tells you nothing about test.

We want to minimise $R(h)$ but we know neither $y^{(\mathrm{new})}$ nor the distribution — so we minimise the training average $\hat R(h)$ instead. That substitution is only defensible because of the i.i.d. assumption: $\hat R$ is an unbiased estimate of $R$.

Unsupervised learning (only $x^{(1)},\dots,x^{(N)}$, no labels): clustering; dimensionality reduction $\R^{d} \to \R^{\tilde d}$ with $\tilde d \ll d$ preserving $x^{(i)} \approx x^{(j)} \Rightarrow \tilde x^{(i)} \approx \tilde x^{(j)}$; representation learning and generation. Self-supervised learning converts unsupervised into supervised (hide a word, let it be $y$, the preceding text be $x$ — the basis of LLMs).

8. Decision trees

→ Ch. 6 · Decision trees

Internal nodes split on an attribute; leaves carry output labels. Major benefit: human interpretable. Setting: $\X = \{0,1\}^{d}$ ($d$ attributes), $\Y = \{0,1\}$.

Decision stump = split just once, then output a chosen label at each of the two leaves.

Construction (recursive)

function DT(dataset S, set of attributes A ⊆ {1,…,d}):
    if A = ∅ or all examples in S have the same label:
        return a leaf with value = majority vote of labels in S
    b = BestAttribute(S, A)                 ∈ A
    LeftNode  = DT({(x,y) ∈ S | x_b = 1}, A \ {b})
    RightNode = DT({(x,y) ∈ S | x_b = 0}, A \ {b})
    return tree  "Is the b-th attribute equal to 1?"  → Y: LeftNode,  N: RightNode

Called initially with $S = \{(x^{(i)}, y^{(i)})\}_{i=1}^{N}$ and $A = \{1,2,\dots,d\}$.

Majority vote at a leaf:

Count how many samples in this leaf carry each label $k$; output the most common. Ties: break arbitrarily but consistently.

Classification error rate of a node/tree $= \dfrac{\#\text{misclassified}}{\#\text{samples}}$ — i.e. the empirical risk under zero-one loss.

Stopping criteria & extensions

• Stop when $A = \emptyset$ (no attributes left) or all examples in $S$ share a label (homogeneous leaf).
• Stop when the split doesn't reduce training error by much.
• Attributes with more than $\{0,1\}$ values; real-valued attributes give threshold tests ("Is $x_2 \ge 4.5$?") and axis-aligned decision boundaries — the set of lines separating the class-0 from the class-1 regions.
• You need not remove the chosen attribute from $A$ in the recursive call (necessary once thresholds are allowed, since the same feature can be split again at a different threshold).

9. Information theory

→ Ch. 7 · Entropy & mutual information

Hand-computation lookup table

Everything below is $\log_2$, to 3 decimals. These nine numbers cover essentially every entropy an exam can ask you to compute by hand.

$H(p) = p\log_2\frac{1}{p} + (1-p)\log_2\frac{1}{1-p}$ is the binary entropy of a node that is a fraction $p$ one class and $1-p$ the other. It is symmetric: $H(p) = H(1-p)$, so $H(3/4) = H(1/4) = 0.811$, $H(7/8) = H(1/8) = 0.544$, $H(3/5) = H(2/5) = 0.971$, $H(5/8) = H(3/8) = 0.954$, $H(7/10)=H(3/10)=0.881$, $H(2/3)=H(1/3)=0.918$. Useful decompositions: $\log_2 6 = 1 + \log_2 3$, $\log_2 9 = 2\log_2 3$, $\log_2 10 = 1 + \log_2 5$, $\log_2 5 = \log_2 10 - 1 = 3.322 - 1$.

10. Linear regression

→ Ch. 8 · Linear regression

Model. With $\X = \R$: $h_{w,b}(x) = x\cdot w + b$. With $\X = \R^{d}$, fix the first coordinate $x_1 = 1$ and let $\theta = \begin{bmatrix} b \\ w \end{bmatrix}$ so that the bias is absorbed:

ERM under squared loss (squared loss because $\Y$ is real-valued):

Closed forms

$\bar x = \frac1N\sum_i x_i$, $\bar y = \frac1N\sum_i y_i$. The with-intercept formula is the no-intercept formula applied to centred data — which is why $b = \bar y - w\bar x$ simply puts the line back through $(\bar x, \bar y)$.

Derivation of the normal equations (completing the square)

Shapes and cost

Total cost of the closed form: $O(Nd^{2} + d^{3})$ — $O(Nd^{2})$ to build $X^{\top}X$, $O(d^{3})$ to invert/solve it. This is why huge $d$ pushes you to gradient descent instead.

11. Optimization: GD, SGD, mini-batch

→ Ch. 9 · Optimization: GD & SGD

The idea. To the right of the minimum of a parabola the derivative is positive (move left); to the left it is negative (move right); the magnitude of the derivative is large when you are far away. So move against the gradient, proportionally to its magnitude.

$\alpha$ is the learning rate / step size. Simple choice: a constant such as 0.01. Another: decay it with $t$, e.g. $\alpha_t = 1/\sqrt{t}$. Initialise $\theta^{(0)}$ anywhere; return $\theta^{(t)}$.

Gradient identities (denominator layout)

For $J : \R^{d} \to \R$, $\nabla_\theta J(\theta) = \frac{\partial J(\theta)}{\partial \theta} = \big[\frac{\partial J}{\partial\theta_1}, \dots, \frac{\partial J}{\partial\theta_d}\big]^{\top} \in \R^{d}$ — a column vector, the same shape as $\theta$. That shape convention is denominator layout (more popular in ML than numerator layout). Generally, $\partial J/\partial\theta$ is just the collection of scalar-by-scalar partial derivatives arranged into a suitable shape.

Setting $-2X^{\top}y + 2X^{\top}X\theta = 0$ recovers $\theta^{*} = (X^{\top}X)^{-1}X^{\top}y$ — linear regression is the special setting where a closed form exists. Most problems have none, which is why GD matters.

Learning rate and convergence

For $J(w) = cw^{2}$ with $c > 0$: $J'(w) = 2cw$, so one GD step is $w^{(t)} = w^{(t-1)} - \alpha\,2cw^{(t-1)} = (1 - 2\alpha c)\,w^{(t-1)}$, i.e. $w^{(t)} = (1-2\alpha c)^{t} w^{(0)}$. This converges iff $|1 - 2\alpha c| < 1$:

$\alpha = \frac{1}{2c}$ jumps to the minimum in one step. $\alpha = 1/c$ oscillates forever between $\pm w^{(0)}$. $\alpha > 1/c$ diverges.

GD may get stuck in a local minimum unless $J$ has special structure (a parabola / convex function has only one). It is still the workhorse because it finds a good solution efficiently. Note $\frac1N\sum_i (y^{(i)} - x^{(i)}w)^2$ is a parabola too, so the single-sample intuition carries over.

12. Feature engineering & overfitting

→ Ch. 10 · Feature engineering

The move. A model can be non-linear in the input while remaining linear in the parameters — and linear-in-parameters is all that linear regression requires. So transform the data, not the model.

13. Logistic regression

→ Ch. 11 · Logistic regression

Why not thresholding. $\hat y = g_{\text{threshold}}(wx+b)$ produces valid class labels but is maximally over-confident right at the boundary, and it has derivative zero essentially everywhere, making it impossible to optimise by gradient methods. Replace the step with a smooth squash.

The model

Bias assumed absorbed into $x$ (first coordinate 1). One-dimensional version: $h(x) = \sigma(wx + b)$. Binary classification, $y \in \{0,1\}$.

The gradient is literally (prediction − truth) × input, averaged — structurally identical to the linear-regression gradient. That is the payoff of pairing the sigmoid with cross-entropy: the $\sigma'$ factor cancels.

Multi-class: softmax

One weight vector $\theta_k$ per class; outputs are positive and sum to 1. With $K = 2$ this reduces exactly to the sigmoid. Loss generalises to cross-entropy $-\sum_k \1(y = k)\log P(Y=k\mid x)$.

Convexity

$f$ convex $\iff f(\lambda z_1 + (1-\lambda)z_2) \le \lambda f(z_1) + (1-\lambda)f(z_2)$ for all $z_1, z_2$, $\lambda\in[0,1]$ $\iff$ (if twice differentiable) $f'' \ge 0$. Every local minimum is global. Logistic cross-entropy is convex in $\theta$ ($\ell''(z) = \sigma(1-\sigma) \ge 0$); squared loss through a sigmoid is not.

14. Regularization & cross-validation

→ Ch. 12 · Model selection

Don't regularize the bias. Standardize features (subtract mean, divide by standard deviation). Hyperparameters (degree, $\lambda$, tree depth) are chosen on held-out data. Holdout: 80:20 split, high variance with little data. $k$-fold: average error over $k$ folds, $k = 5$ or $10$; $k = N$ is LOOCV. Always retrain on all data with the chosen value. Trainings for $C$ candidates: $Ck + 1$.

15. Neural networks

→ Ch. 13 · Neural networks

Without a nonlinear $g$, stacked layers collapse to one linear map. The network objective is not convex: results depend on initialization; ReLU neurons can "die" (zero gradient on every point). Vocabulary: output layer, hidden layers, "input layer" = data; fully connected = linear = dense; MLP.

16. Traps — the ten mistakes most likely to cost marks