Source: CS7641 Machine Learning Prep · cs7641-Machine-Learning-Prep.md · updated 2026-08-06 · 🔒 secret gist

Synced verbatim from gist.github.com/bl9.

CS 7641 Machine Learning — Preparedness Study Guide

Target: be able to answer Yes to all nine questions on the official OMSCS CS 7641 Machine Learning preparedness sheet.

Source: https://omscs.gatech.edu/sites/default/files/documents/2023/CS%207641-Course%20Preparedness%20Questions.pdf

Official prerequisite framing from that document: an introductory AI course, plus representational issues in AI, some AI programming, and background (or willingness to pick up background) in statistics and information theory.

Table of Contents

1. The nine questions at a glance
2. Eigenvectors and eigenvalues
3. Singular Value Decomposition
4. Conditions of a valid distance metric
5. Bayes Rule
6. Expectation of a random variable
7. Covariance and correlation
8. Search algorithms — BFS, DFS, A*
9. Asymptotic analysis of search algorithms
10. Programming background
11. Information theory (implied by the prerequisite text)
12. Reading list, mapped to questions
13. Self-test with answers
14. Three-week study plan
15. The study plan, worked
    • Week 1, Days 1–2 — Vectors, matrices, rank, null space, orthogonality
    • Week 1, Days 3–4 — Eigenvalues and eigenvectors, five 2×2 and two 3×3
    • Week 1, Days 5–6 — SVD by hand, end to end
    • Week 1, Day 7 — PCA from scratch, two ways
    • Week 2, Days 1–2 — Conditional probability and five base-rate problems
    • Week 2, Days 3–4 — Expectation, variance, and the distribution table derived
    • Week 2, Day 5 — Covariance by hand, then with numpy
    • Week 2, Day 6 — Information gain of a decision-tree split
    • Week 2, Day 7 — Bias–variance decomposition, derived
    • Week 3, Days 1–2 — BFS, DFS, UCS implemented
    • Week 3, Days 3–4 — A* and the node-expansion comparison
    • Week 3, Day 5 — The complexity table, derived and measured
    • Week 3, Days 6–7 — The scikit-learn warm-up, run

1. The nine questions at a glance

Practical note: CS 7641 Machine Learning assignments are analysis-and-writeup heavy. Question 9 says "not necessarily programmed," but in practice you will be running scikit-learn, ABAGAIL-style optimization code, and plotting a lot of learning curves. Treat Python + numpy + scikit-learn + matplotlib as the real bar.

2. Eigenvectors and eigenvalues

Definition

For a square matrix A (n×n), a nonzero vector v is an eigenvector with eigenvalue λ if:

A v = λ v

Interpretation: A acts on v by pure scaling — no rotation. Eigenvectors are the invariant directions of the linear map.

How to compute

1. Rearrange: (A − λI) v = 0 with v ≠ 0.
2. A nonzero solution exists only if A − λI is singular, so solve the characteristic equation:

   det(A − λI) = 0
   

   This is a degree-n polynomial in λ; its roots are the eigenvalues.
3. For each λ, solve the null space of (A − λI) to get the eigenvector(s). Normalize if you want unit length.

Worked example (2×2)

A = [ 4  1 ]
    [ 2  3 ]

Characteristic polynomial:

det([4−λ  1 ; 2  3−λ]) = (4−λ)(3−λ) − (1)(2)
                       = λ² − 7λ + 12 − 2
                       = λ² − 7λ + 10
                       = (λ − 5)(λ − 2)

So λ₁ = 5, λ₂ = 2.

• λ = 5: (A − 5I) = [−1 1; 2 −2] → −x + y = 0 → v₁ = (1, 1)ᵀ
• λ = 2: (A − 2I) = [ 2 1; 2 1] → 2x + y = 0 → v₂ = (1, −2)ᵀ

Sanity checks:

• trace(A) = 4 + 3 = 7 = 5 + 2 = Σλᵢ ✅
• det(A) = 12 − 2 = 10 = 5 × 2 = Πλᵢ ✅

Properties worth memorizing

• Σ λᵢ = trace(A), Π λᵢ = det(A)
• A is invertible ⟺ no eigenvalue is 0
• Eigenvalues of Aᵏ are λᵏ; of A⁻¹ are 1/λ
• Symmetric real matrices: all eigenvalues real, eigenvectors for distinct eigenvalues are orthogonal, and A = QΛQᵀ with Q orthogonal (spectral theorem)
• Positive semi-definite ⟺ all λ ≥ 0; positive definite ⟺ all λ > 0
• Algebraic multiplicity (root multiplicity) ≥ geometric multiplicity (null-space dimension). When they differ, A is not diagonalizable.
• Eigendecomposition requires square; SVD does not — that's why SVD is the workhorse in ML

Why CS 7641 Machine Learning cares

• PCA: eigenvectors of the covariance matrix are the principal components; eigenvalues are variance explained per component
• Spectral clustering: eigenvectors of the graph Laplacian
• Markov chains / MDPs: stationary distribution is the eigenvector of the transition matrix for λ = 1
• Optimization: eigenvalues of the Hessian tell you curvature, conditioning, and whether a critical point is a min, max, or saddle

numpy

import numpy as np
A = np.array([[4., 1.], [2., 3.]])
vals, vecs = np.linalg.eig(A)          # general square
vals, vecs = np.linalg.eigh(A)         # symmetric/Hermitian — faster, sorted, real
# vecs[:, i] is the eigenvector for vals[i]

3. Singular Value Decomposition

Definition

For any real m × n matrix A (square or not, full rank or not):

A = U Σ Vᵀ

• U: m × m orthogonal — columns are left singular vectors
• Σ: m × n diagonal, entries σ₁ ≥ σ₂ ≥ … ≥ σᵣ > 0, rest zero — singular values
• V: n × n orthogonal — columns are right singular vectors
• r = rank(A) = number of nonzero singular values

Thin/compact SVD: keep only the first r columns of U and V → A = U_r Σ_r V_rᵀ. This is what you almost always use.

Relationship to eigendecomposition

AᵀA = V Σᵀ Σ Vᵀ   → V = eigenvectors of AᵀA, σᵢ² = eigenvalues of AᵀA
AAᵀ = U Σ Σᵀ Uᵀ   → U = eigenvectors of AAᵀ, same nonzero eigenvalues

That relationship is the hand-computation recipe.

Procedure for computing by hand

1. Form AᵀA (pick whichever of AᵀA / AAᵀ is smaller).
2. Eigendecompose it → eigenvalues λᵢ, eigenvectors vᵢ.
3. σᵢ = √λᵢ, sorted descending. Columns of V are the vᵢ.
4. uᵢ = A vᵢ / σᵢ for each σᵢ > 0. Extend to a full basis with Gram–Schmidt if you need full U.

Worked example (rank-deficient)

A = [ 1  1 ]
    [ 1  1 ]

AᵀA = [2 2; 2 2] → eigenvalues 4 and 0.

• σ₁ = 2, σ₂ = 0 → rank 1
• λ=4 eigenvector: (1,1)ᵀ → v₁ = (1/√2, 1/√2)ᵀ
• λ=0 eigenvector: (1,−1)ᵀ → v₂ = (1/√2, −1/√2)ᵀ
• u₁ = A v₁ / σ₁ = (2/√2, 2/√2)ᵀ / 2 = (1/√2, 1/√2)ᵀ

So A = 2 · u₁ v₁ᵀ, a single rank-1 term. Verify: 2 · (1/√2)(1/√2) = 1 in every entry ✅

Second example (symmetric PSD)

A = [ 3  1 ]
    [ 1  3 ]

Symmetric with positive eigenvalues 4 and 2, so SVD = eigendecomposition: σ = (4, 2), u₁ = v₁ = (1,1)ᵀ/√2, u₂ = v₂ = (1,−1)ᵀ/√2.

Caution: SVD equals eigendecomposition only when A is symmetric positive semi-definite. If a symmetric matrix has a negative eigenvalue λ, then σ = |λ| and the sign moves into u.

Key facts

• Always exists, for every matrix. Singular values are unique; singular vectors are not (sign/rotation freedom in repeated σ).
• Eckart–Young–Mirsky: truncating to the top-k singular triplets gives the best rank-k approximation in both Frobenius and spectral norm. This is the theoretical basis for PCA, LSA, and matrix-completion recommenders.
• ‖A‖₂ = σ₁, ‖A‖_F = √(Σ σᵢ²), condition number κ = σ₁/σᵣ
• Pseudoinverse: A⁺ = V Σ⁺ Uᵀ where Σ⁺ inverts the nonzero σ. This is how least squares is solved stably.
• PCA = SVD of the mean-centered data matrix. Centering is not optional.

numpy

U, s, Vt = np.linalg.svd(A, full_matrices=False)   # thin SVD; s is a 1-D array
A_k = (U[:, :k] * s[:k]) @ Vt[:k, :]               # best rank-k approximation

4. Conditions of a valid distance metric

A function d: X × X → ℝ is a metric iff, for all x, y, z ∈ X:

Note: (1) is implied by (2)+(3)+(4), so some texts list only three axioms. If asked, give all four — say the four and note that non-negativity is derivable.

Weakened variants (know the names)

• Pseudometric: drops "only if" in (2) — distinct points can have distance 0
• Quasimetric: drops symmetry (e.g. one-way street driving distance)
• Semimetric: drops the triangle inequality
• Divergence: only d ≥ 0 and d(x,x) = 0 (e.g. KL)

Common metrics

Non-examples — these are the exam questions

• Squared Euclidean — violates the triangle inequality. On the line: d(0,2) = 4, but d(0,1) + d(1,2) = 1 + 1 = 2, and 4 > 2. ❌
• Cosine "distance" 1 − cos θ — violates the triangle inequality. (The angular version θ/π fixes it.) ❌
• KL divergence D(P‖Q) — violates symmetry and the triangle inequality. It's a divergence, not a metric. Jensen–Shannon distance (√JSD) is a proper metric. ❌
• Lp with p < 1 — e.g. p = 0.5 violates the triangle inequality. ❌

Why CS 7641 Machine Learning cares

k-NN, k-means, kernel methods, and DBSCAN all assume some notion of proximity. Whether it's a true metric determines whether you can use metric-tree indexes (KD-tree, ball tree), whether triangle-inequality pruning is valid, and whether clustering guarantees hold. Also: L2 in high dimensions concentrates (the curse of dimensionality), which is why L1 or cosine often works better on high-dimensional data.

5. Bayes Rule

Statement

P(A | B) = P(B | A) · P(A) / P(B)

with P(B) > 0. In ML naming:

posterior = likelihood × prior / evidence

P(h | D) = P(D | h) · P(h) / P(D)

Derivation (one line — be able to do this)

By definition of conditional probability, P(A|B) = P(A∩B)/P(B) and P(B|A) = P(A∩B)/P(A). Therefore P(A∩B) = P(B|A)P(A), and substituting gives the rule.

Law of total probability (the denominator)

P(B) = Σᵢ P(B | Aᵢ) P(Aᵢ)        for a partition {Aᵢ}

Worked example — base rate fallacy

Disease prevalence 1%. Test sensitivity P(+ | D) = 0.99. Specificity P(− | ¬D) = 0.95, so false positive rate P(+ | ¬D) = 0.05. You test positive. What is P(D | +)?

P(+) = P(+|D)P(D) + P(+|¬D)P(¬D)
     = (0.99)(0.01) + (0.05)(0.99)
     = 0.0099 + 0.0495
     = 0.0594

P(D | +) = 0.0099 / 0.0594 = 0.1667

≈ 16.7%, not 99%. The prior dominates when the base rate is low. If you find this surprising, redo it until you don't.

ML forms you must recognize

• MAP: h_MAP = argmax_h P(D|h)P(h) — the evidence P(D) drops out because it doesn't depend on h
• MLE: h_MLE = argmax_h P(D|h) — MAP with a uniform prior
• Naive Bayes: assume features conditionally independent given the class:

  P(y | x₁…xₙ) ∝ P(y) Πᵢ P(xᵢ | y)
  

  Work in log space to avoid underflow. Use Laplace smoothing for unseen feature values.
• Bayesian vs frequentist framing: Bayesians treat parameters as random variables with priors; MAP/MLE is where CS 7641 Machine Learning spends most of its time (the Bayesian Learning lectures).

Related identities

• Chain rule: P(A,B,C) = P(A|B,C)P(B|C)P(C)
• Conditional independence: P(A,B|C) = P(A|C)P(B|C) — the assumption behind both Naive Bayes and Bayes nets
• Odds form: posterior odds = likelihood ratio × prior odds

6. Expectation of a random variable

Definitions

Discrete:

E[X] = Σₓ x · P(X = x)

Continuous:

E[X] = ∫ x · f(x) dx

LOTUS (law of the unconscious statistician) — expectation of a function, no need to derive the distribution of g(X):

E[g(X)] = Σₓ g(x) P(X = x)     or     ∫ g(x) f(x) dx

Properties

Linearity holding without independence is the single most-used fact in ML derivations. Know it cold.

Worked example — fair six-sided die

E[X]  = (1+2+3+4+5+6)/6 = 21/6 = 3.5
E[X²] = (1+4+9+16+25+36)/6 = 91/6 ≈ 15.167
Var(X) = 91/6 − (3.5)² = 15.167 − 12.25 = 2.9167 = 35/12
SD(X) ≈ 1.708

Standard distributions — memorize these

Why CS 7641 Machine Learning cares

• Expected loss / risk minimization is the definition of the learning objective
• Bias–variance decomposition: E[(y − ŷ)²] = Bias² + Variance + Irreducible error — this is a pure expectation manipulation and it shows up in every assignment writeup
• Value functions in reinforcement learning are expectations over trajectories: V(s) = E[Σ γᵗ rₜ | s₀ = s]
• Entropy is E[−log p(X)]

7. Covariance and correlation

Covariance

Cov(X, Y) = E[(X − μₓ)(Y − μ_y)] = E[XY] − E[X]E[Y]

Sample estimators:

population:  Cov = (1/n)   Σ (xᵢ − x̄)(yᵢ − ȳ)
sample:      Cov = (1/(n−1)) Σ (xᵢ − x̄)(yᵢ − ȳ)     ← Bessel's correction, unbiased

Units are units-of-X × units-of-Y, so the magnitude is not interpretable on its own — that's what correlation fixes.

Pearson correlation

ρ(X, Y) = Cov(X, Y) / (σₓ σ_y)        ρ ∈ [−1, 1]

Dimensionless. ρ = ±1 ⟺ perfect linear relationship.

Worked example

X = [1, 2, 3, 4]     Y = [2, 4, 5, 4]
x̄ = 2.5              ȳ = 3.75

• Population covariance = 3.5 / 4 = 0.875
• Sample covariance = 3.5 / 3 ≈ 1.167
• Var(X)_pop = 5/4 = 1.25 → σₓ = 1.118
• Var(Y)_pop = 4.75/4 = 1.1875 → σ_y = 1.090
• ρ = 0.875 / (1.118 × 1.090) = 0.875 / 1.2183 ≈ **0.718**

(Use the same convention — population or sample — in numerator and denominator; ρ is identical either way since the n vs n−1 cancels.)

Properties

• Cov(X, X) = Var(X)
• Symmetric: Cov(X,Y) = Cov(Y,X)
• Bilinear: Cov(aX + b, cY + d) = ac · Cov(X, Y)
• Independent ⟹ Cov = 0. The converse is false. Classic counterexample: X ~ Uniform(−1,1), Y = X². Then Cov(X,Y) = E[X³] − E[X]E[X²] = 0 − 0 = 0, but Y is fully determined by X.
• Correlation captures linear dependence only. Use mutual information (or Spearman rank correlation) for monotone/nonlinear dependence.
• Correlation ≠ causation. Say it out loud in every assignment writeup.

Covariance matrix

For a random vector X ∈ ℝᵈ:

Σ = E[(X − μ)(X − μ)ᵀ]      d × d, symmetric, positive semi-definite
Σᵢⱼ = Cov(Xᵢ, Xⱼ),  Σᵢᵢ = Var(Xᵢ)

From a centered data matrix X_c (n × d): Σ̂ = X_cᵀ X_c / (n − 1).

PCA = eigendecomposition of Σ̂ = SVD of X_c. That's the through-line from §2, §3, and §7 into the unsupervised-learning half of the course.

numpy

np.cov(X, Y)                # sample covariance (ddof=1 by default) — returns 2×2
np.corrcoef(X, Y)           # correlation matrix
np.cov(data, rowvar=False)  # d×d covariance from an n×d data matrix

8. Search algorithms — BFS, DFS, A*

The general framework

All three are the same loop with a different frontier data structure:

frontier ← {start}
explored ← {}
loop:
    node ← frontier.remove()
    if goal(node): return path
    explored.add(node)
    for child in expand(node):
        if child not in explored ∪ frontier: frontier.add(child)

Breadth-First Search

• Explores level by level. Finds the shallowest goal.
• Optimal only when all step costs are equal. With varying costs, use UCS.
• Complete (if b is finite).
• Space is the killer: the whole frontier lives in memory, O(b^d).
• Goal test on generation rather than expansion saves one full level of work.

Depth-First Search

• Dives to the deepest node, backtracks on dead ends.
• Not optimal, and not complete in infinite-depth or cyclic spaces (graph-search version with an explored set is complete on finite graphs).
• Space is the win: O(bm) — only the current path plus siblings.
• Iterative Deepening DFS (IDS) = DFS space with BFS optimality: repeatedly run depth-limited DFS with limit 0, 1, 2, … Re-expansion cost is negligible because the last level dominates the node count.

A*

f(n) = g(n) + h(n)

• g(n): actual cost from start to n
• h(n): heuristic estimate of cost from n to the goal
• h(goal) = 0

Admissible: h(n) ≤ h*(n) for all n — never overestimates the true remaining cost. → A* with tree search is optimal.

Consistent (monotonic): h(n) ≤ c(n, a, n') + h(n') for every successor n' — a triangle inequality on the heuristic. → A* with graph search is optimal. Consistency ⟹ admissibility (not the converse). Under consistency, f is non-decreasing along any path, and the first time you expand a node you already have its optimal g.

Optimally efficient: no other optimal algorithm using the same heuristic expands fewer nodes (up to tie-breaking).

Dominance: if h₂(n) ≥ h₁(n) for all n and both are admissible, h₂ dominates and A* expands no more nodes with h₂. A larger admissible heuristic is always at least as good.

Special cases:

• h(n) = 0 → A* degenerates to UCS/Dijkstra
• h(n) = h*(n) → A* walks straight to the goal
• g(n) = 0 → greedy best-first (fast, not optimal)

Variants worth naming: IDA* (memory-bounded), weighted A* (f = g + w·h, w > 1 — bounded suboptimality, much faster).

Trace practice

Take any small weighted graph, pick a start and a goal, and hand-trace all three, writing down the frontier contents at every step. If you can do that on a 8–10 node graph without hesitation, question 7 is a Yes.

9. Asymptotic analysis of search algorithms

Notation

• b — branching factor
• d — depth of the shallowest goal
• m — maximum depth of the search tree (may be ∞)
• C* — cost of the optimal solution
• ε — minimum step cost (> 0)

The table

Points that get asked

• Why is IDS O(b^d) and not worse despite re-expansion? Node counts are dominated by the deepest level. Total generated is (d+1)b⁰ + d·b¹ + … + 1·b^d, which is O(b^d) — a constant factor of roughly b/(b−1) above BFS. For b = 10, about 11% overhead. You trade that for O(bd) space instead of O(b^d).
• A's real bottleneck is memory, not time.* It stores every generated node. IDA*, RBFS, and SMA* exist to fix that.
• A time complexity with a good heuristic*: if |h(n) − h*(n)| ≤ O(log h*(n)), growth is sub-exponential. In general it's exponential in the relative error of the heuristic.
• Bidirectional search halves the exponent, which is a much bigger win than any constant-factor optimization — but it requires a well-defined predecessor function and an easily-tested goal state.
• Big-O refresher: O is an upper bound, Ω a lower bound, Θ a tight bound. Drop constants and lower-order terms. O(b^d) with b=10, d=12 is 10¹² nodes — this is why heuristics matter.

10. Programming background

The question only asks whether you have worked with Python, R, MATLAB, or Java. The honest bar for succeeding in CS 7641 Machine Learning is higher. Checklist:

Python core

• Comfortable with list/dict comprehensions, zip, enumerate, classes, virtualenv/conda
• Can read a stack trace and debug someone else's code

numpy

• Vectorization instead of loops; broadcasting rules; axis= semantics
• Slicing, boolean masks, reshape, argsort, linalg module

pandas

• Load CSV, handle missing values, groupby, merge, one-hot encode

scikit-learn — this is the actual course toolkit

• fit / predict / transform API and Pipeline
• train_test_split, cross_val_score, GridSearchCV
• StandardScaler (fit on train only — leakage is a common assignment mistake)
• Classifiers used in Assignment 1: decision trees, boosting, k-NN, SVM, neural nets
• Unsupervised: KMeans, GaussianMixture, PCA, FastICA, SparseRandomProjection
• learning_curve and validation_curve — you will generate dozens of these

matplotlib / seaborn

• Multi-series line plots with labeled axes and legends; subplots; save to file

Warm-up exercise: load a UCI dataset (e.g. Wine or Adult), build a pipeline with scaling + a decision tree, tune max_depth with GridSearchCV, and plot the learning curve and validation curve. If you can do that end-to-end in under an hour, you're ready.

11. Information theory (implied by the prerequisite text)

The preparedness doc doesn't ask a question about this, but the prerequisite paragraph explicitly names information theory, and CS 7641 Machine Learning uses it from the first decision-tree lecture onward.

Entropy — expected surprise, in bits (log base 2):

H(X) = −Σ p(x) log₂ p(x)

Maximized by the uniform distribution (H = log₂ n), zero for a deterministic variable.

Conditional entropy:

H(Y | X) = Σ p(x) H(Y | X = x)

Information gain — the decision-tree splitting criterion:

IG(Y, X) = H(Y) − H(Y | X)

Mutual information:

I(X; Y) = H(X) + H(Y) − H(X,Y) = H(Y) − H(Y|X) ≥ 0

Zero iff X and Y are independent. Unlike correlation, it captures nonlinear dependence.

KL divergence — relative entropy:

D_KL(P ‖ Q) = Σ p(x) log(p(x)/q(x)) ≥ 0

Asymmetric, no triangle inequality (see §4). Cross-entropy loss = H(P) + D_KL(P‖Q); since H(P) is fixed by the data, minimizing cross-entropy = minimizing KL.

Gini impurity — the CART alternative to entropy:

Gini = 1 − Σ p(x)²

Cheaper to compute, behaves very similarly in practice.

Worked micro-example: a node with 9 positives and 5 negatives.

H = −(9/14)log₂(9/14) − (5/14)log₂(5/14)
  = −(0.643)(−0.637) − (0.357)(−1.485)
  ≈ 0.410 + 0.530 = 0.940 bits

12. Reading list, mapped to questions

As given in the official document

Linear algebra — either one:

1. Numerical Linear Algebra — Trefethen & Bau. Read Part I (Fundamentals) through Lecture 5.
2. Introduction to Linear Algebra, 4th ed. — Gilbert Strang.

Probability and statistics:

1. All of Statistics — Larry Wasserman. Read Part I (Probability).

Artificial intelligence (optional):

1. Artificial Intelligence: A Modern Approach — Russell & Norvig.

Which reading covers which question

Useful free supplements

• 3Blue1Brown, Essence of Linear Algebra — the eigenvector and change-of-basis episodes are the fastest intuition available
• MIT 18.06 (Strang) lectures — free on OCW/YouTube
• Mitchell, Machine Learning (1997) — the course's own primary text; Ch. 3 (decision trees) and Ch. 6 (Bayesian learning) map directly onto §5 and §11 here
• Berkeley CS188 Pacman projects — hands-on BFS/DFS/UCS/A* implementation
• MacKay, Information Theory, Inference, and Learning Algorithms — free PDF, for §11

13. Self-test with answers

Do these closed-book. Answers follow each question.

1. Find the eigenvalues of [[2, 1], [1, 2]].

det([2−λ, 1; 1, 2−λ]) = (2−λ)² − 1 = λ² − 4λ + 3 = (λ−3)(λ−1). λ = 3, 1. Eigenvectors (1,1) and (1,−1).

2. What are the singular values of [[3, 0], [0, −4]]?

AᵀA = [[9,0],[0,16]], eigenvalues 16 and 9 → σ = 4, 3 (descending). Note σ is the absolute value; the sign of −4 goes into U.

3. Is d(x,y) = (x − y)² on ℝ a valid metric? Justify.

No. It fails the triangle inequality: d(0,2) = 4 > d(0,1) + d(1,2) = 2.

4. 1 in 1000 people have a condition. A test is 99% sensitive and 98% specific. Given a positive result, what is P(condition)?

P(+) = 0.99(0.001) + 0.02(0.999) = 0.00099 + 0.01998 = 0.02097. P(D|+) = 0.00099 / 0.02097 ≈ **4.7%**.

5. X ~ Uniform(0, 10). Compute E[X] and Var(X).

E[X] = (0+10)/2 = **5**. Var(X) = (10−0)²/12 = 100/12 ≈ **8.33**.

6. If Cov(X,Y) = 0, are X and Y independent?

No. Zero covariance means no linear relationship. Counterexample: X ~ Uniform(−1,1), Y = X².

7. Which of BFS, DFS, and A* guarantee an optimal solution, and under what conditions?

BFS: optimal only with uniform step costs. DFS: never guaranteed. A*: optimal with an admissible heuristic under tree search, and a consistent heuristic under graph search.

8. State the time and space complexity of iterative deepening and explain why the re-expansion is cheap.

Time O(b^d), space O(bd). The deepest level contains the overwhelming majority of nodes, so re-generating all the shallower levels adds only a constant factor of roughly b/(b−1).

9. h₁ and h₂ are both admissible and h₂(n) ≥ h₁(n) everywhere. Which should you use?

h₂ — it dominates, so A* expands no more nodes with it. Larger admissible heuristics are strictly better.

10. A node has 6 positive and 2 negative examples. Compute its entropy.

H = −0.75 log₂ 0.75 − 0.25 log₂ 0.25 = 0.75(0.415) + 0.25(2) = 0.311 + 0.5 = **0.811 bits**.

11. Why is centering the data required before PCA?

Without centering, the first principal component points toward the data's mean rather than the direction of maximum variance. X_cᵀX_c / (n−1) is only the covariance matrix when X_c has zero column means.

12. Write Bayes Rule and identify each term by its ML name.

P(h|D) = P(D|h)P(h)/P(D) — posterior, likelihood, prior, evidence (marginal likelihood).

14. Three-week study plan

Assumes roughly 8–10 hours per week. Compress or stretch as needed.

Week 1 — Linear algebra (Questions 1, 2, and part of 3)

• Days 1–2: vectors, matrices, rank, null space, orthogonality. Strang Ch. 1–3 or Trefethen Lectures 1–3.
• Days 3–4: eigenvalues and eigenvectors. Compute five 2×2 and two 3×3 by hand. Watch the 3Blue1Brown eigenvector episode.
• Days 5–6: SVD. Trefethen Lectures 4–5. Compute one 2×2 by hand end to end, then verify with np.linalg.svd.
• Day 7: implement PCA from scratch with np.linalg.eigh on the covariance matrix, and again with SVD on the centered data. Confirm the components match.

Week 2 — Probability and statistics (Questions 4, 5, 6, plus information theory)

• Days 1–2: sample spaces, conditional probability, independence, Bayes Rule. Wasserman Ch. 1. Do five base-rate problems.
• Days 3–4: random variables, expectation, variance, LOTUS. Wasserman Ch. 3. Memorize the distribution table in §6.
• Day 5: covariance, correlation, covariance matrices. Compute one by hand, verify with np.cov.
• Day 6: entropy, information gain, KL divergence. Hand-compute the information gain of a decision-tree split.
• Day 7: derive the bias–variance decomposition from scratch using linearity of expectation.

Week 3 — Search, complexity, and tooling (Questions 7, 8, 9)

• Days 1–2: Russell & Norvig Ch. 3. Implement BFS, DFS, and UCS on a grid or graph.
• Days 3–4: A*, admissibility, consistency, dominance. Implement A* with Manhattan distance on a grid; compare expanded-node counts against UCS.
• Day 5: reproduce the complexity table in §9 from memory. Verify empirically by counting node expansions.
• Days 6–7: the scikit-learn warm-up from §10 — pipeline, grid search, learning curve, validation curve on a real dataset.

Final check: retake the nine questions. Every one should be a confident Yes with a worked example you can produce on demand.

15. The study plan, worked

Section 14 lists what to do. This section does it — every day of the plan, with the explanation and the finished exercise. All numeric results below were computed and verified, not estimated.

Week 1, Days 1–2 — Vectors, matrices, rank, null space, orthogonality

What it requires: be able to say what rank, null space, and orthogonality mean, and connect them to whether a system has a solution.

The four fundamental subspaces. For A of size m × n:

Rank–nullity theorem: rank(A) + dim N(A) = n. Row rank always equals column rank.

Orthogonality relations: N(A) ⊥ C(Aᵀ) and N(Aᵀ) ⊥ C(A). Those two facts are the whole geometry of least squares.

Worked: rank and null space of a rank-deficient matrix.

A = [ 1  2  3 ]
    [ 2  4  6 ]
    [ 1  1  1 ]

Row-reduce. R2 − 2·R1 → [0 0 0]. R3 − R1 → [0 −1 −2].

[ 1  2  3 ]
[ 0 −1 −2 ]
[ 0  0  0 ]

Two pivots → rank = 2. Nullity = 3 − 2 = 1. Solve Ax = 0: from row 2, −y − 2z = 0 → y = −2z. From row 1, x + 2(−2z) + 3z = 0 → x = z. So N(A) = span{(1, −2, 1)ᵀ}.

Verify: A(1,−2,1)ᵀ = (1−4+3, 2−8+6, 1−2+1)ᵀ = (0,0,0)ᵀ ✅

Why this matters downstream. A rank-deficient design matrix means the normal equations AᵀA x = Aᵀb have infinitely many solutions — this is exactly multicollinearity in linear regression, and it's why you either regularize (ridge adds λI, making AᵀA + λI invertible) or use the pseudoinverse from SVD.

Orthogonality and projection. The projection of b onto C(A) is p = A(AᵀA)⁻¹Aᵀb. The least-squares solution x̂ = (AᵀA)⁻¹Aᵀb is exactly the x making the residual b − Ax orthogonal to the column space. Orthonormal bases make this trivial: if Q has orthonormal columns, QᵀQ = I and the projection is just QQᵀb.

Norms (needed for §4): ‖x‖₁ = Σ|xᵢ|, ‖x‖₂ = √(Σxᵢ²), ‖x‖∞ = max|xᵢ|. Every norm induces a metric via d(x,y) = ‖x − y‖. That's the bridge between this day and the distance-metric question.

Day 1–2 checkpoint: given a 3×4 matrix, state its rank, the dimension of its null space, and whether Ax = b has zero, one, or infinitely many solutions.

Week 1, Days 3–4 — Eigenvalues and eigenvectors, five 2×2 and two 3×3

What it requires: five 2×2 by hand and two 3×3 by hand. Here they are, all verified against np.linalg.eig.

2×2 problem 1 — distinct real eigenvalues

A = [ 5  4 ]      det(A−λI) = (5−λ)(2−λ) − 4 = λ² − 7λ + 6 = (λ−6)(λ−1)
    [ 1  2 ]

• λ = 6: [−1 4; 1 −4] → x = 4y → v = (4, 1)ᵀ
• λ = 1: [ 4 4; 1 1] → x = −y → v = (1, −1)ᵀ
• Check: trace 7 = 6+1 ✅, det 10−4 = 6 = 6·1 ✅

2×2 problem 2 — negative eigenvalues

A = [  0   1 ]    det(A−λI) = (−λ)(−3−λ) + 2 = λ² + 3λ + 2 = (λ+1)(λ+2)
    [ −2  −3 ]

• λ = −1: [1 1; −2 −2] → v = (1, −1)ᵀ
• λ = −2: [2 1; −2 −1] → 2x + y = 0 → v = (1, −2)ᵀ
• Both eigenvalues negative → this is the matrix form of a stable linear system (x' = Ax decays).

2×2 problem 3 — complex eigenvalues

A = [ 2  −1 ]     λ² − 4λ + 5 = 0  →  λ = 2 ± i
    [ 1   2 ]

Real matrices can have complex eigenvalues; they arrive in conjugate pairs. Geometrically this is a rotation combined with a scaling — there is no real invariant direction. |λ| = √5 is the scale factor, arg(λ) = arctan(1/2) the rotation angle. Real symmetric matrices can never do this, which is why the spectral theorem is such a strong guarantee.

2×2 problem 4 — defective (repeated eigenvalue, one eigenvector)

A = [ 3  1 ]      det(A−λI) = (3−λ)² = 0  →  λ = 3 (algebraic multiplicity 2)
    [ 0  3 ]

(A − 3I) = [0 1; 0 0] → y = 0 → the null space is only span{(1,0)ᵀ}. Geometric multiplicity 1 < algebraic multiplicity 2 → A is not diagonalizable. numpy returns two identical eigenvector columns here, which is the numerical symptom of the same fact. This is the standard counterexample to "every matrix has a full eigenbasis," and the reason SVD (which always exists) is preferred in practice.

2×2 problem 5 — symmetric, orthogonal eigenvectors

A = [  6  −2 ]    λ² − 15λ + 50 = (λ−10)(λ−5)
    [ −2   9 ]

• λ = 10: [−4 −2; −2 −1] → y = −2x → v = (1, −2)ᵀ
• λ = 5: [ 1 −2; −2 4] → x = 2y → v = (2, 1)ᵀ
• v₁ · v₂ = 2 − 2 = 0 ✅ orthogonal, as the spectral theorem guarantees. Both eigenvalues positive → positive definite → this is a legitimate covariance matrix.

3×3 problem 1 — block structure

B = [ 2  0  0 ]
    [ 0  3  4 ]
    [ 0  4  9 ]

The top-left is a 1×1 block, so λ = 2 with eigenvector (1,0,0)ᵀ. The bottom-right 2×2 gives λ² − 12λ + (27 − 16) = λ² − 12λ + 11 = (λ−11)(λ−1). Eigenvalues: 11, 2, 1. Verified numerically. Block-diagonal matrices let you decompose the problem — worth spotting before grinding out a cubic.

3×3 problem 2 — triangular

C = [ 4  −2   1 ]
    [ 0   3  −1 ]
    [ 0   0   2 ]

Triangular → eigenvalues are the diagonal: 4, 3, 2. No characteristic polynomial needed.

• λ = 4: (C−4I) = [0 −2 1; 0 −1 −1; 0 0 −2] → z = 0, y = 0 → v = (1,0,0)ᵀ
• λ = 3: [1 −2 1; 0 0 −1; 0 0 −1] → z = 0, x = 2y → v = (2,1,0)ᵀ
• λ = 2: [2 −2 1; 0 1 −1; 0 0 0] → y = z, 2x − 2y + z = 0 → 2x = y → v = (1,2,2)ᵀ
• Verify: C(1,2,2)ᵀ = (4−4+2, 6−2, 4)ᵀ = (2,4,4)ᵀ = 2·(1,2,2)ᵀ ✅

Note the eigenvectors are not orthogonal here — C isn't symmetric.

Day 3–4 checkpoint: you should now be able to spot, before computing, whether a matrix will have real eigenvalues (symmetric), complex ones (rotation-like), a defective spectrum (repeated root with a rank-deficient A − λI), or free eigenvalues (triangular/block).

Week 1, Days 5–6 — SVD by hand, end to end

What it requires: one full 2-column SVD computed by hand, verified with numpy.

The example (the classic non-square case):

A = [ 3   2 ]
    [ 2   3 ]     (3 × 2)
    [ 2  −2 ]

Step 1 — form AᵀA (2×2 is smaller than the 3×3 AAᵀ, so use it):

AᵀA = [ 9+4+4    6+6−4 ]  =  [ 17   8 ]
      [ 6+6−4    4+9+4 ]     [  8  17 ]

Step 2 — eigendecompose it. det([17−λ, 8; 8, 17−λ]) = (17−λ)² − 64. So 17 − λ = ±8 → λ = 25, 9.

Step 3 — singular values. σ₁ = √25 = 5, σ₂ = √9 = 3. Two nonzero singular values → rank(A) = 2.

Step 4 — right singular vectors (eigenvectors of AᵀA):

• λ = 25: [−8 8; 8 −8] → x = y → v₁ = (1, 1)ᵀ/√2
• λ = 9: [ 8 8; 8 8] → x = −y → v₂ = (1, −1)ᵀ/√2

Step 5 — left singular vectors via uᵢ = A vᵢ / σᵢ:

A v₁ = (1/√2)(3+2, 2+3, 2−2)ᵀ = (5, 5, 0)ᵀ/√2
u₁ = A v₁ / 5 = (1, 1, 0)ᵀ/√2

A v₂ = (1/√2)(3−2, 2−3, 2+2)ᵀ = (1, −1, 4)ᵀ/√2
u₂ = A v₂ / 3 = (1, −1, 4)ᵀ/(3√2)

Check ‖u₂‖ = √((1 + 1 + 16)/18) = √(18/18) = 1 ✅ and u₁ · u₂ = (1 − 1 + 0)/6 = 0 ✅

Result:

A = 5 · u₁v₁ᵀ + 3 · u₂v₂ᵀ

Numpy verification (signs may flip — that's the sign ambiguity, not an error):

sigma = [5.  3.]
U  = [[-0.7071,  0.2357], [-0.7071, -0.2357], [-0.0000,  0.9428]]
Vt = [[-0.7071, -0.7071], [ 0.7071, -0.7071]]
U @ diag(s) @ Vt  reproduces A exactly ✅

Note 0.2357 = 1/(3√2) and 0.9428 = 4/(3√2) — the hand computation matches column for column.

Step 6 — the truncation experiment (this is the point of SVD in ML). Best rank-1 approximation:

A₁ = 5 · u₁v₁ᵀ = [ 2.5  2.5 ]
                 [ 2.5  2.5 ]
                 [ 0.0  0.0 ]

Frobenius error ‖A − A₁‖_F = 3.0000, which is exactly σ₂. That's Eckart–Young made concrete: the error of the best rank-k approximation equals √(Σ_{i>k} σᵢ²), and here that's just σ₂. No other rank-1 matrix does better.

Day 5–6 checkpoint: given any small matrix, produce σ, U, V by hand, state the rank, write the rank-1 approximation, and predict its Frobenius error before computing it.

Week 1, Day 7 — PCA from scratch, two ways

What it requires: implement PCA via eigendecomposition of the covariance matrix and via SVD of the centered data, and confirm they agree.

Why they must agree. Let X_c be the mean-centered n × d data matrix. Then:

Σ̂ = X_cᵀ X_c / (n − 1)

Substituting the SVD X_c = UΣVᵀ:

Σ̂ = (VΣᵀUᵀ)(UΣVᵀ)/(n−1) = V (Σ²/(n−1)) Vᵀ

This is exactly the eigendecomposition of Σ̂. So:

• Principal directions = columns of V = right singular vectors of X_c
• Eigenvalues of Σ̂ = σᵢ²/(n−1)
• Scores (projected data) = X_c V = UΣ

The code:

import numpy as np
from sklearn.datasets import load_wine

X = load_wine().data
Xc = (X - X.mean(0)) / X.std(0)          # standardize: center + unit variance

# Route A: eigendecomposition of the covariance matrix
cov = np.cov(Xc, rowvar=False)
w, V = np.linalg.eigh(cov)               # eigh: symmetric, returns ascending
idx = np.argsort(w)[::-1]                # sort descending
w, V = w[idx], V[:, idx]

# Route B: SVD of the centered data
U, s, Vt = np.linalg.svd(Xc, full_matrices=False)

print(w[:5])                              # eigenvalues
print((s**2 / (len(Xc) - 1))[:5])         # should be identical

Actual output on the Wine dataset (13 features, 178 samples):

eigendecomposition eigenvalues : [4.7324  2.5111  1.4542  0.9242  0.8580]
svd  s²/(n−1)                  : [4.7324  2.5111  1.4542  0.9242  0.8580]
max |component_1| difference   : 5.97e-16       (machine precision)
variance explained ratio       : [0.3620  0.1921  0.1112  0.0707  0.0656]

They agree to floating-point noise. First two components explain 55.4% of variance; first five explain 80.2%.

Three things to internalize from this exercise:

1. Standardize before PCA when features have different units. The Wine dataset has proline in the hundreds and hue near 1. Without scaling, proline alone would dominate PC1 because PCA maximizes raw variance. Centering is mandatory; scaling is a modeling choice that is almost always right for heterogeneous features.
2. Prefer the SVD route numerically. Forming XᵀX squares the condition number. svd(Xc) works on Xc directly and is what sklearn.decomposition.PCA actually calls.
3. Eigenvalue = variance along that component. The explained-variance ratio λᵢ/Σλⱼ is what you plot in a scree plot to pick k. In CS 7641 Machine Learning Assignment 3 you will justify your choice of k with exactly this plot, so know what the axis means.

Week 2, Days 1–2 — Conditional probability and five base-rate problems

What it requires: five base-rate problems worked. The pattern is always the same — compute the denominator with the law of total probability, then divide.

Problem 1 — Spam filter

P(spam) = 0.4. The word "free" appears in 30% of spam and 2% of ham. An email contains "free".

P(free) = (0.30)(0.4) + (0.02)(0.6) = 0.120 + 0.012 = 0.132
P(spam | free) = 0.120 / 0.132 = 0.909

≈ 90.9%. A strong likelihood ratio (15:1) plus a near-balanced prior gives a confident posterior — contrast with Problem 2.

Problem 2 — Drug test

5% of a population use a drug. Test is 95% sensitive, 90% specific. Someone tests positive.

P(+) = (0.95)(0.05) + (0.10)(0.95) = 0.0475 + 0.0950 = 0.1425
P(user | +) = 0.0475 / 0.1425 = 1/3

33.3%. A "95% accurate" test leaves you twice as likely to be innocent as guilty, because the 10% false-positive rate applies to a population 19× larger. This is the base-rate fallacy in one line.

Problem 3 — Two machines

Machine A produces 60% of output at a 2% defect rate; machine B produces 40% at 5%. A defective item is found.

P(D) = (0.02)(0.6) + (0.05)(0.4) = 0.012 + 0.020 = 0.032
P(A | D) = 0.012 / 0.032 = 0.375     P(B | D) = 0.625

Machine B makes less output but most of the defects. Prior 60/40 flips to posterior 37.5/62.5.

Problem 4 — Monty Hall, as Bayes

You pick door 1. Host (who knows) opens door 3, revealing a goat.

Prior:      P(C₁) = P(C₂) = P(C₃) = 1/3
Likelihood: P(open3 | C₁) = 1/2   (host picks freely between 2 and 3)
            P(open3 | C₂) = 1     (host is forced)
            P(open3 | C₃) = 0     (host won't reveal the car)

P(open3) = (1/3)(1/2) + (1/3)(1) + 0 = 1/6 + 1/3 = 1/2

P(C₁ | open3) = (1/6)/(1/2) = 1/3
P(C₂ | open3) = (1/3)/(1/2) = 2/3

Switch. The asymmetry lives entirely in the likelihood: the host's constrained behaviour when the car is behind door 2 is what carries the information.

Problem 5 — Naive Bayes, end to end

Training data, 5 documents:

Priors: P(spam) = 2/5 = 0.4, P(ham) = 3/5 = 0.6.

Vocabulary V = {cheap, buy, now, meeting, project, report}, |V| = 6. Token counts: spam has 6 tokens (cheap×3, buy×2, now×1); ham has 9 tokens (meeting×3, project×2, now×2, report×2).

With Laplace (add-1) smoothing, P(w|c) = (count(w,c) + 1)/(N_c + |V|):

P(cheap|spam) = 4/12 = 0.3333      P(cheap|ham)   = 1/15 = 0.0667
P(buy|spam)   = 3/12 = 0.2500      P(buy|ham)     = 1/15 = 0.0667
P(now|spam)   = 2/12 = 0.1667      P(now|ham)     = 3/15 = 0.2000

Classify the new document "cheap buy now":

score(spam) = 0.4 × 0.3333 × 0.2500 × 0.1667 = 0.005556
score(ham)  = 0.6 × 0.0667 × 0.0667 × 0.2000 = 0.000533
P(spam | doc) = 0.005556 / (0.005556 + 0.000533) = 0.912

Classify as spam, 91.2% posterior.

Three practical notes this exercise is meant to teach:

• Smoothing is not optional. Without add-1, P(cheap|ham) = 0 sends the entire ham score to zero — one unseen word vetoes a class.
• Work in logs. With hundreds of features, the products underflow. Use log P(c) + Σ log P(wᵢ|c) and compare log-scores.
• The independence assumption is wrong and it works anyway. "cheap" and "buy" clearly co-occur. Naive Bayes gets miscalibrated probabilities but often the right argmax, which is why it survives as a baseline.

Week 2, Days 3–4 — Expectation, variance, and the distribution table derived

What it requires: memorize the distribution table. Memorization sticks better after deriving a few, so here are the derivations.

Bernoulli(p). X ∈ {0,1}.

E[X]  = 1·p + 0·(1−p) = p
E[X²] = 1²·p + 0²·(1−p) = p       (since X² = X for a 0/1 variable)
Var   = p − p² = p(1−p)

Maximized at p = 0.5 — a fair coin is the most uncertain Bernoulli, which is also why entropy peaks there.

Binomial(n,p). Write X = Σᵢ Xᵢ as a sum of n iid Bernoullis.

E[X]  = Σ E[Xᵢ] = np                          (linearity — no independence needed)
Var(X) = Σ Var(Xᵢ) = np(1−p)                  (independence needed here)

This decomposition trick — rewrite a complicated variable as a sum of indicators — is the single most useful move in applied probability.

Geometric(p), number of trials until the first success. Condition on the first trial:

E[X] = 1 + (1−p)·E[X]          → E[X](1 − (1−p)) = 1 → E[X] = 1/p

That's the tower property doing real work.

Uniform(a,b).

E[X]  = ∫ₐᵇ x/(b−a) dx = (b² − a²)/(2(b−a)) = (a+b)/2
E[X²] = (b³ − a³)/(3(b−a)) = (a² + ab + b²)/3
Var   = (a² + ab + b²)/3 − (a+b)²/4 = (b−a)²/12

Exponential(λ). Integrate by parts:

E[X] = ∫₀^∞ x λe^(−λx) dx = 1/λ
E[X²] = 2/λ²   →   Var = 2/λ² − 1/λ² = 1/λ²

Memoryless: P(X > s+t | X > s) = P(X > t).

Poisson(λ). E[X] = Var(X) = λ. Mean equals variance is the diagnostic — if your count data has variance far above the mean, you have overdispersion and Poisson is the wrong model.

The one identity to drill: Var(X) = E[X²] − (E[X])². Every derivation above is an application of it.

LOTUS in practice. To get E[X²] you never need the distribution of X². Just sum x²·p(x). Same for E[e^X], E[log X], and any loss function.

Jensen's inequality, and why it matters. For convex g, E[g(X)] ≥ g(E[X]). Consequence: the average of squared errors exceeds the square of the average error, and E[log X] ≤ log E[X] — the latter is the inequality that produces the ELBO in variational inference and the E-step bound in EM.

Day 3–4 checkpoint: state mean and variance for all seven distributions in §6 from memory, then derive any two of them cold.

Week 2, Day 5 — Covariance by hand, then with numpy

What it requires: compute one covariance matrix by hand and verify with np.cov.

Data — 4 observations, 2 features:

X = [1, 2, 3, 4]        Y = [2, 4, 5, 4]
x̄ = 2.5                 ȳ = 3.75

Deviations and products:

Sample covariance matrix (divide by n−1 = 3):

       [ 5.00/3   3.50/3 ]     [ 1.6667   1.1667 ]
Σ̂  =   [ 3.50/3   4.75/3 ]  =  [ 1.1667   1.5833 ]

Correlation:

ρ = 1.1667 / (√1.6667 × √1.5833) = 1.1667 / (1.2910 × 1.2583) = 1.1667 / 1.6246 = 0.718

Identical to the population-convention answer in §7, because the n vs n−1 factor cancels in the ratio.

Verification:

np.cov(X, Y)      # → [[1.6667, 1.1667], [1.1667, 1.5833]]
np.corrcoef(X, Y) # → [[1.0, 0.7181], [0.7181, 1.0]]

Why n−1. The sample mean x̄ is itself estimated from the data, so deviations from it are systematically too small — dividing by n underestimates variance. Bessel's correction fixes the bias by accounting for the one degree of freedom spent on x̄. np.cov uses ddof=1 by default; np.std uses ddof=0. Mixing them silently is a classic source of wrong numbers.

The scaling trap. Covariance magnitude depends on units. Convert X from metres to centimetres and the covariance grows 100×, while ρ doesn't move. This is exactly why PCA on unstandardized heterogeneous features is meaningless, and it connects Day 5 back to Day 7 of Week 1.

Week 2, Day 6 — Information gain of a decision-tree split

What it requires: hand-compute the information gain of a split. Using the canonical 14-example PlayTennis dataset (9 positive, 5 negative), all values verified numerically.

Root entropy:

H(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14)
     = −(0.6429)(−0.6374) − (0.3571)(−1.4854)
     = 0.4098 + 0.5305 = 0.9403 bits

Candidate split: Outlook.

H(S | Outlook) = (5/14)(0.9710) + (4/14)(0) + (5/14)(0.9710) = 0.6935
IG(Outlook)    = 0.9403 − 0.6935 = 0.2467 bits

All four candidates:

ID3 splits on Outlook at the root, then recurses on the Sunny and Rain branches. Overcast is already pure and becomes a leaf immediately.

Five things this computation is teaching:

1. Entropy of a pure node is 0; of a 50/50 node is 1 bit. Those are the anchors — if a hand computation falls outside [0, 1] for a binary target, you made an arithmetic error.
2. Information gain is always ≥ 0. Conditioning never increases expected entropy. If you compute a negative IG, recheck the weighting.
3. The weights matter. H(S|A) is a weighted average by branch size, not a plain average. Overcast's zero entropy only helps in proportion to its 4/14 share.
4. IG is biased toward high-cardinality attributes. An ID column would split every example into its own pure branch and score maximum gain while generalizing not at all. Gain ratio (C4.5) divides by the split's intrinsic information −Σ (|Sᵥ|/|S|) log₂(|Sᵥ|/|S|) to correct this. Expect this as an exam question.
5. Gini gives nearly the same tree. For the root, Gini = 1 − (9/14)² − (5/14)² = 1 − 0.4133 − 0.1276 = 0.4592. It's cheaper (no logarithm) and ranks splits almost identically — which is why sklearn defaults to it and why the criterion choice rarely changes your Assignment 1 conclusions.

Week 2, Day 7 — Bias–variance decomposition, derived

What it requires: derive it from scratch using linearity of expectation. This is the most quoted result in the course and the one most often recited without understanding.

Setup. True relationship y = f(x) + ε where E[ε] = 0 and Var(ε) = σ². We fit f̂(x) on a random training set D; f̂ is therefore itself random. Fix a test point x.

Goal: decompose E[(y − f̂(x))²], where the expectation is over both the noise ε and the draw of D.

Step 1 — insert and subtract f(x):

E[(y − f̂)²] = E[(f + ε − f̂)²]
            = E[(f − f̂)²] + 2·E[ε(f − f̂)] + E[ε²]

Step 2 — kill the cross term. ε is independent of the training set, and E[ε] = 0:

E[ε(f − f̂)] = E[ε] · E[f − f̂] = 0

And E[ε²] = Var(ε) + (E[ε])² = σ². So:

E[(y − f̂)²] = E[(f − f̂)²] + σ²

Step 3 — decompose the remaining term. Let f̄ = E[f̂], the average prediction over all possible training sets. Insert and subtract it:

E[(f − f̂)²] = E[(f − f̄ + f̄ − f̂)²]
            = (f − f̄)² + 2(f − f̄)·E[f̄ − f̂] + E[(f̄ − f̂)²]

The middle term vanishes because E[f̄ − f̂] = f̄ − E[f̂] = 0, and (f − f̄) is a constant with respect to D.

Result:

E[(y − f̂(x))²]  =  (f(x) − E[f̂(x)])²  +  E[(f̂(x) − E[f̂(x)])²]  +  σ²
                 =        Bias²         +          Variance        +  Irreducible

Reading the three terms:

Diagnosing from curves — the practical payoff.

• Learning curve (error vs training-set size): high train error and high validation error converging to a plateau → high bias. Low train error with a persistent large gap that shrinks as n grows → high variance.
• Validation curve (error vs model complexity): train error falls monotonically; validation error is U-shaped. The minimum is the bias–variance sweet spot.

How this maps to specific algorithms in the course:

• Decision tree depth ↑ → bias ↓, variance ↑
• k-NN k ↑ → bias ↑, variance ↓ (k=1 is minimum bias, maximum variance)
• SVM C ↑ → bias ↓, variance ↑
• Neural net width/epochs ↑ → bias ↓, variance ↑
• Bagging / random forests attack variance by averaging decorrelated high-variance learners; bias stays roughly constant
• Boosting attacks bias by sequentially fitting the residuals of weak (high-bias) learners

Caveat worth knowing. The classic U-shaped curve is not universal — very overparameterized models can show "double descent," where test error falls again past the interpolation threshold. The decomposition above still holds; the assumption that variance grows monotonically with parameter count is what breaks.

Week 3, Days 1–2 — BFS, DFS, UCS implemented

What it requires: implement all three on a grid and observe the behavioural differences.

The test environment: a 10×10 grid, start (0,0), goal (9,9), 4-connected moves, unit costs, with two walls forming a snake — a vertical wall at x=3 for y ∈ [0,6] and another at x=6 for y ∈ [3,9]. That leaves 86 reachable cells and forces a detour, so a naive heuristic can't just walk diagonally.

Shared skeleton. All three algorithms are the same loop; only the frontier structure changes.

def search(start, goal, frontier_pop, frontier_push):
    frontier = init([start]); came = {start: None}; explored = set()
    while frontier:
        node = frontier_pop()
        if node in explored: continue
        explored.add(node)
        if node == goal: return reconstruct(came, goal)
        for child in neighbors(node):
            if child not in explored:
                came[child] = node
                frontier_push(child)
    return None

• BFS — collections.deque, popleft(). Mark nodes as seen when generated, not when expanded, or you duplicate work.
• DFS — a plain list, pop(). Same code, different end of the list. That one-character difference is the whole algorithm.
• UCS — heapq keyed on g(n). Requires the "skip if already expanded" guard because a node can sit in the heap multiple times with different costs.

Measured results:

What the numbers are telling you:

1. BFS and UCS are identical here. With uniform step costs, g(n) = depth, so the priority queue orders nodes exactly the way the FIFO queue does. UCS only earns its extra machinery when edge costs vary.
2. DFS expanded fewer nodes but returned a worse path — 36 steps instead of 28. It got lucky on effort and unlucky on quality. Change the neighbour ordering and both numbers move unpredictably. DFS offers no guarantees about either.
3. BFS and UCS expanded all 86 reachable cells because the goal is in the far corner — the frontier had to sweep the entire space. This is the O(b^d) space problem made concrete: for a real problem with b=10, d=12, "sweep everything shallower than the goal" means 10¹² nodes.
4. DFS's real advantage is memory, not expansions. Its frontier held at most a few dozen nodes along one path; BFS's frontier held a growing fringe.

The bug to watch for: in graph search, add nodes to the explored set (or a "seen" set) so cycles don't cause infinite loops. Tree search without an explored set will loop forever on a grid, since (0,0) → (1,0) → (0,0) is a legal path.

Week 3, Days 3–4 — A* and the node-expansion comparison

What it requires: implement A* with Manhattan distance and compare expansions against UCS.

Implementation. Identical to UCS except the priority key:

heapq.heappush(frontier, (g[child] + h(child), g[child], child))
#                          ^^^^^^^^^^^^^^^^^^  f(n) = g(n) + h(n)

The second tuple element (g) is a tie-breaker; without it Python tries to compare the coordinate tuples, which works but breaks the moment your states aren't orderable.

Measured results on the same grid:

Reading the table — this is the entire lesson of A:*

1. h = 0 reduces A to UCS exactly.* 86 expansions, identical behaviour. A* is not a different algorithm; it's UCS with an informed priority.
2. Manhattan dominates Euclidean on a 4-connected grid. Both are admissible (neither can overestimate when diagonal moves are illegal), but Manhattan is always ≥ Euclidean, so by the dominance theorem it expands no more nodes — 74 vs 77, confirmed. Rule: among admissible heuristics, always pick the largest.
3. The savings are real but modest here (86 → 74, about 14%) because the walls make the Manhattan estimate badly wrong in the detour region — the heuristic doesn't know about obstacles. On an open grid the same heuristic would cut expansions dramatically. Heuristic quality, not heuristic existence, drives the win.
4. Weighted A (w=2) expanded only 59 nodes* — a 31% saving over UCS — and on this particular map still happened to find the 28-step path. But 2h can overestimate, so the optimality guarantee is gone; weighted A* only promises a solution within a factor w of optimal. Getting the optimal answer once is not evidence the guarantee holds.

Admissibility vs consistency, checked concretely. Manhattan distance on a unit-cost grid is consistent: moving one step changes h by at most 1, and the step cost is exactly 1, so h(n) ≤ c(n,n') + h(n') always holds. That's why the graph-search version above is safe to write with a simple "skip if expanded" guard. With an admissible-but-inconsistent heuristic, you would need to reopen closed nodes when a cheaper path to them is discovered.

Constructing admissible heuristics — the standard recipe. Relax the problem. For the 8-puzzle:

• Relax "a tile can move anywhere" → misplaced-tile count h₁
• Relax "a tile can move to any adjacent square, occupied or not" → Manhattan distance h₂
• h₂ ≥ h₁ everywhere, so h₂ dominates. Any exact solution to a relaxed problem is an admissible heuristic for the original — that's the general theorem.
• max(h₁, h₂, …) of several admissible heuristics is admissible and dominates all of them.

Week 3, Day 5 — The complexity table, derived and measured

What it requires: reproduce §9's table from memory, then verify empirically. Here is where each entry comes from.

Counting nodes in a uniform tree. A tree with branching factor b has bᵏ nodes at depth k. Levels 0 through d total:

1 + b + b² + … + b^d = (b^(d+1) − 1)/(b − 1) = O(b^d)

The last level dominates; every complexity entry in the table is a variation on this sum.

• BFS O(b^d) time and space. It expands every node shallower than the goal, and the frontier at depth d holds O(b^d) nodes simultaneously.
• DFS O(b^m) time, O(bm) space. Worst case it explores the entire tree to depth m. But it only stores the current path (m nodes) plus the unexpanded siblings at each level (b−1 each) → O(bm). That's linear, not exponential. This is DFS's entire reason to exist.
• UCS O(b^(1+⌊C*/ε⌋)). UCS expands nodes in order of g, so it processes everything with cost < C*. With minimum step cost ε, the effective depth is ⌊C*/ε⌋. When all costs equal 1, this collapses to O(b^d) and UCS = BFS. The +1 accounts for UCS expanding the goal only after popping it, one level later than BFS.
• IDS O(b^d) time, O(bd) space. Derived below.
• Bidirectional O(b^(d/2)). Two frontiers of depth d/2 meeting in the middle: 2b^(d/2) ≪ b^d. For b=10, d=12, that's 2×10⁶ instead of 10¹² — six orders of magnitude, far more than any constant-factor optimization can buy.

The IDS re-expansion question, measured. IDS re-runs depth-limited DFS at limits 0, 1, …, d. Nodes at depth i are generated (d + 1 − i) times:

IDS nodes = (d+1)b⁰ + (d)b¹ + (d−1)b² + … + 1·b^d
BFS nodes = b⁰ + b¹ + … + b^d

Computed for b = 10, d = 5:

BFS generated : 111,111
IDS generated : 123,456
ratio         : 1.111×

11% overhead to trade O(b^d) space for O(bd) space. As b grows the overhead shrinks toward b/(b−1); at b=2 it's 2×, still only a constant. The intuition: the deepest level is generated once, and it contains more nodes than every shallower level combined.

The measured completeness/optimality claims from the grid experiment above:

Day 5 checkpoint: write out the nine-row table from memory, then justify each O(·) in one sentence.

Week 3, Days 6–7 — The scikit-learn warm-up, run

What it requires: load a dataset, build a scaling + decision-tree pipeline, tune with GridSearchCV, and plot learning and validation curves. Here is the exercise completed on the Wine dataset (178 samples, 13 features, 3 classes).

The code:

from sklearn.datasets import load_wine
from sklearn.model_selection import (train_test_split, GridSearchCV,
                                     learning_curve, validation_curve, StratifiedKFold)
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.tree import DecisionTreeClassifier

X, y = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3,
                                      random_state=42, stratify=y)

pipe = Pipeline([("scale", StandardScaler()),
                 ("clf",   DecisionTreeClassifier(random_state=42))])

grid = {"clf__max_depth":        [1, 2, 3, 4, 5, 6, 8, 10, None],
        "clf__min_samples_leaf": [1, 2, 5, 10],
        "clf__criterion":        ["gini", "entropy"]}

cv = StratifiedKFold(5, shuffle=True, random_state=42)
gs = GridSearchCV(pipe, grid, cv=cv, scoring="accuracy", n_jobs=-1).fit(Xtr, ytr)

Results:

best params      : criterion='gini', max_depth=3, min_samples_leaf=1
best CV accuracy : 0.8950
held-out test    : 0.9630

Learning curve (fixed at the best estimator, 5-fold CV):

Reading it: train accuracy pinned near 1.0 while CV accuracy climbs and the gap narrows from 0.39 to 0.09 — the signature of a variance-limited model. The curves are still converging at n=99, so more data would help. If the two curves had flattened together at a mediocre value, that would be bias instead, and more data would be wasted effort. Note the non-monotonic dip at n=81: with 178 samples the CV estimates are noisy, so read the trend, not individual points.

Validation curve over max_depth:

Reading it — this is the bias–variance derivation from Week 2 Day 7, made visible:

• Depth 1 is underfitting. Train 0.673, CV 0.646, tiny gap. One split cannot separate three classes. High bias, low variance.
• Depth 3 is the sweet spot. CV accuracy peaks at 0.895.
• Depth 4+ is overfitting. Train hits 1.000 while CV drops to 0.878 and the gap widens to 0.122.
• Curves flatten past depth 6 because the tree stops growing — with 124 training samples and clean class structure, it achieves purity around depth 5 and further depth allowance is inert. Not every hyperparameter range produces movement; say so in your writeup rather than pretending the plateau is a finding.

Five habits this exercise is drilling — all of which are graded in CS 7641 Machine Learning:

1. Scale inside the Pipeline, never before the split. StandardScaler fitted on the full dataset leaks test-set statistics into training. Inside a pipeline, GridSearchCV refits the scaler on each CV fold correctly. Data leakage is the most common silent error in Assignment 1.
2. Stratify the split. stratify=y preserves class proportions. On a 3-class dataset of 178 samples an unstratified split can badly skew a fold.
3. Never tune on the test set. Select with cross-validation on the training data; touch the held-out set exactly once, at the end. Here CV said 0.895 and test said 0.963 — the test set happened to be easy, which is precisely why you don't tune against it.
4. Report the gap, not just accuracy. The train–CV gap is your empirical variance estimate and the thing your analysis should discuss.
5. Fix random_state everywhere. Splits, CV shuffling, and the estimator. Your results must reproduce, and grading rewards being able to explain a number rather than regenerate a different one.

Extension for the last day: swap DecisionTreeClassifier for KNeighborsClassifier, SVC, MLPClassifier, and AdaBoostClassifier, keeping the pipeline and curve code identical. That is structurally the whole of Assignment 1 — five learners, two datasets, learning and validation curves, and an analysis of what each curve says about bias and variance. If you can do it now, you start the course ahead.

Final self-assessment

Go back to the nine questions in §1. For each one, you should be able to produce, without notes:

1. A characteristic polynomial and its eigenvectors ✅ (§15 W1 D3–4 — seven worked matrices)
2. A full SVD by hand plus its rank-1 truncation error ✅ (§15 W1 D5–6)
3. All four metric axioms and a counterexample for each ✅ (§4)
4. A base-rate posterior computed correctly ✅ (§15 W2 D1–2 — five problems)
5. Mean and variance of seven standard distributions, derived ✅ (§15 W2 D3–4)
6. A covariance matrix by hand, with the right denominator ✅ (§15 W2 D5)
7. BFS, DFS, and A* traced and implemented ✅ (§15 W3 D1–4)
8. The complexity table with a justification per row ✅ (§15 W3 D5)
9. An end-to-end scikit-learn pipeline with tuned hyperparameters and diagnostic curves ✅ (§15 W3 D6–7)

That's nine Yes answers, each backed by something you've actually done rather than read.