MFML · Interview Notes

Matrix Form of Linear System

• System Ax = B → augmented matrix [A | B]
• Coefficient matrix: just A (n×n)
• Augmented matrix: [A | b] includes RHS
• System has solution iff rank(A) = rank([A|b])

Elementary Row Operations

• Rᵢ ↔ Rⱼ — swap two rows
• Rᵢ → c·Rᵢ — multiply row by nonzero constant
• Rᵢ → Rᵢ + a·Rⱼ — add multiple of one row to another
• All are reversible · do not change solution set

REF & RREF

• REF (Row Echelon Form): leading entry each row to right of row above; rows of zeros at bottom
• RREF (Reduced REF): additionally, each pivot = 1 and only nonzero in its column
• Pivot variable: corresponds to pivot column
• Free variable: corresponds to non-pivot column → infinite solutions
• Eigenvalues of triangular matrix = diagonal entries

Rank & Consistency

• Rank: number of pivot elements (= dim of row/column space)
• No solution: rank(A) < rank([A|b]) — last row [0…0 | c≠0]
• Unique solution: rank(A) = rank([A|b]) = n
• Infinite solutions: rank(A) = rank([A|b]) < n (free variables)
• Homogeneous Ax=0: always consistent; nontrivial soln iff rank(A) < n

Special Matrices

• Upper triangular U: all entries below diagonal = 0
• Lower triangular L: all entries above diagonal = 0
• Diagonal D: all non-diagonal entries = 0; D^k = diag(d₁^k, …, dₙ^k)
• det(triangular) = product of diagonal entries
• Inverse of diagonal: replace each dᵢ with 1/dᵢ

Vector Space

• Set V with addition + and scalar multiplication · that satisfies closure, associativity, commutativity, identity, inverse, distributivity
• Rⁿ = {(x₁,…,xₙ) : xᵢ∈R} is a vector space
• Vectors used in ML: data encoding, embeddings, model weights, activations

Linear Independence

• Set {v₁,…,vₖ} is linearly independent if c₁v₁+…+cₖvₖ=0 implies all cᵢ=0
• Linearly dependent if some vector is a linear combination of others
• n vectors in Rᵐ where n>m → always linearly dependent
• Any subset of an LI set is LI; any superset of LD set is LD

Span, Basis & Dimension

• Span(A): set of all linear combinations of vectors in A
• A generates/spans V if every v∈V can be written as linear combination of A
• Basis: linearly independent generating set · minimal spanning set
• Dimension: number of vectors in any basis
• All bases of a vector space have the same size

ML Relevance

• Inputs encoded as vectors (tabular, image pixels, token embeddings)
• Neural net layers: linear maps between vector spaces
• Rank = number of "independent directions" in data — used in PCA
• Free variables → underdetermined systems → regularization needed

Data Matrix

• n data objects × p attributes → matrix X of size n×p
• Dissimilarity matrix: n×n symmetric matrix D where d(i,j)=d(j,i), d(i,i)=0
• Measures how unlike two data points are

Key Distance Measures

When to Use Which

Inner Product Axioms

• Symmetry: ⟨x,y⟩ = ⟨y,x⟩
• Linearity: ⟨αx+y, z⟩ = α⟨x,z⟩ + ⟨y,z⟩
• Positive-definiteness: ⟨x,x⟩ > 0 for x≠0
• General inner product: ⟨x,y⟩ = x̂ᵀAŷ where A is symmetric positive definite
• Dot product is the standard inner product when A = I

Orthogonality

• x ⊥ y iff ⟨x,y⟩ = 0
• Zero vector is orthogonal to all vectors
• Orthogonality depends on which inner product is used
• cos(ω) = ⟨x,y⟩ / (‖x‖·‖y‖)

Orthogonal Matrices

• Preserve lengths: ‖Ax‖² = xᵀAᵀAx = xᵀx = ‖x‖²
• 2D rotation matrix is orthogonal: [[cosθ, -sinθ], [sinθ, cosθ]]
• Left-inverse = right-inverse for square matrices

Norms (from inner products)

• L2 → ridge regularization; L1 → lasso (sparsity)

Definitions

• λ: eigenvalue · v: corresponding eigenvector (non-zero)
• Eigenspace = set of all eigenvectors for λ + zero vector
• Find λ: solve det(A-λI)=0 · find v: solve (A-λI)v=0

Key Properties

• Eigenvalues of triangular matrix = diagonal entries
• A and Aᵀ have the same eigenvalues
• Symmetric positive-definite matrices → all eigenvalues real and positive
• Repeated eigenvalues → may have 1 or 2 eigenvectors (algebraic vs geometric multiplicity)
• det(A) = product of eigenvalues · trace(A) = sum of eigenvalues

Diagonalization

• A is diagonalizable iff it has n linearly independent eigenvectors
• Allows fast matrix powers: Aᵏ = P Dᵏ P⁻¹
• All symmetric matrices are diagonalizable (spectral theorem)

ML Relevance

• PCA: eigenvectors of covariance matrix = principal components
• Largest eigenvalue → direction of maximum variance
• Spectral clustering: eigenvectors of graph Laplacian
• Page Rank: dominant eigenvector of transition matrix
• Stability of RNNs related to spectral radius of weight matrix

Cholesky Decomposition

• det(A) = det(L)² = (product of diag entries of L)²
• ML uses: sampling from multivariate Gaussian, solving linear systems efficiently
• If A not SPD → Cholesky fails (use LU decomposition instead)

SVD (Singular Value Decomposition)

SVD Properties & Uses

• Exists for ANY matrix (not just square/symmetric)
• Rank of A = number of nonzero singular values
• Low-rank approximation: keep top-k singular values → best rank-k approx
• Connection to PCA: eigenvalues of S = σ²/N where σ are singular values of X
• Moore-Penrose pseudoinverse: A⁺ = V Σ⁺ Uᵀ
• Condition number = σ_max / σ_min (large = ill-conditioned)

Derivative (Univariate)

• Chain rule: d/dx f(g(x)) = f'(g(x))·g'(x)
• Product rule: d/dx(fg) = f'g + fg'

Partial Derivatives & Gradient

• Gradient of f(x) = xᵀAx is (A + Aᵀ)x; if A symmetric → 2Ax
• Setting gradient to zero → critical points (min, max, saddle)

Jacobian

• Row i = gradient of fᵢ
• Used in backpropagation to compute weight gradients

Hessian

• 2nd order optimality test (multivariate):
• fₓₓ > 0 and det(H) > 0 → local min
• fₓₓ < 0 and det(H) > 0 → local max
• det(H) < 0 → saddle point
• H positive definite → convex function → global min unique

Chain Rule (Multivariate)

• Each layer in a neural net applies chain rule
• Neural net layer: fᵢ(xᵢ₋₁) = σ(Aᵢ₋₁xᵢ₋₁ + bᵢ₋₁)

Taylor Polynomial & Series

2nd-Order Multivariate Taylor

• Sign of Q(h,k) = h²fₓₓ + 2hkfₓᵧ + k²fᵧᵧ determines min/max/saddle

ML Applications

• Optimization: approximate cost function locally → enables gradient/Newton methods
• Newton's method: uses 2nd-order Taylor (Hessian) for faster convergence
• Regression: polynomial features come from Taylor approximation
• Model interpretation: expanding model around a point reveals feature sensitivity
• Taylor approx is exact for polynomials of degree ≤ n

Unconstrained Optimization

• Goal: minimize differentiable objective function f(θ)
• Necessary condition for local min: ∇f(θ*) = 0
• Sufficient condition: ∇f = 0 AND H is positive definite
• Gradient descent: use negative gradient to walk toward minimum

Batch vs SGD vs Mini-Batch

SGD: gradient of 1 sample is good approximation of true gradient (law of large numbers)

Learning Rate Issues

• Too large α: overshoots, oscillates around optimum
• Too small α: very slow convergence
• Best practice: use decaying learning rate — large initially, decreasing over time
• Decaying update: θ_{t+1} = θ_t − αₜ·∇L, where αₜ decreases with t
• With decaying α, SGD converges almost surely to local minimum

GD Failure Modes

• Local optima: ∇f=0 but not global min — bad initialization causes this
• Saddle points: ∇f=0 but neither min nor max — common in high-dim
• Flat regions: gradient ≈ 0, updates nearly zero — GD stalls
• High-dim functions have exponentially many local minima

Momentum

• Accumulates velocity in direction of consistent gradient
• Dampens oscillations in directions with conflicting gradients
• Helps escape flat regions and local optima
• Analogy: marble rolling down hill — builds momentum over consistent slopes

Loss Function (Regression)

• Least squares is convex → unique global minimum
• Separability of L enables stochastic approximation

Lagrange Multipliers

• At extremum, objective and constraint surfaces share a tangent plane
• Each constraint gets its own λ

KKT Conditions (Inequality Constraints)

Duality

• Lagrangian dual: D(λ) = minₓ L(x,λ) — unconstrained in x
• Weak duality: D(λ) ≤ f(x*) always — dual gives lower bound
• Strong duality: D(λ*) = f(x*) — primal = dual optimal
• Slater's condition: if f convex, gᵢ convex, hⱼ linear, and strict interior feasible point exists → strong duality holds
• SVM uses duality to move from primal (w,b) to dual (αᵢ)

Complementary Slackness (Intuition)

• λᵢ*·gᵢ(x*) = 0 means: for each constraint either…
• λᵢ* = 0 → constraint is inactive (not binding at solution)
• gᵢ(x*) = 0 → constraint is active (binding / tight)
• In SVM: αᵢ = 0 for non-support vectors, αᵢ > 0 for support vectors

Goal & Intuition

• Linear dimensionality reduction: D → M dimensions (M < D)
• Find projection directions that retain maximum variance
• Each principal component = direction of maximum residual variance
• Output: lower-dim representation zₙ = Bᵀxₙ ∈ Rᴹ
• B: D×M matrix with orthonormal columns (principal axes)

Algorithm (Step-by-Step)

• 1. Standardize: subtract mean μ_d, divide by σ_d per dimension
• 2. Compute covariance matrix: S = (1/N) Σ xₙxₙᵀ = (1/N)XXᵀ
• 3. Eigendecompose S: Sb = λb → eigenvalues + eigenvectors
• 4. Sort: eigenvectors by descending eigenvalue
• 5. Select top M eigenvectors as columns of B
• 6. Project: z* = Bᵀx* (new coordinates)
• 7. Reconstruct: x̃ = BBᵀx* (in original space)

PCA via SVD

Key Properties

• Projected variance on m-th PC = λₘ (m-th eigenvalue of S)
• Total variance retained = Σ_{m=1}^{M} λₘ / Σ_{d=1}^{D} λ_d
• PCs are orthogonal → projections are uncorrelated
• PCA minimizes reconstruction error = MSE in lower-dim space
• Limitation: linear only; no class labels used (unsupervised)
• Use LDA instead for class-discriminant dimensionality reduction

Choosing Number of Components

• Scree plot: plot λ₁, λ₂, …; look for "elbow"
• Variance threshold: choose M s.t. Σλ_m / Σλ_d ≥ 0.95 (95% variance retained)
• For reconstruction: pick M where reconstruction error is acceptable

Core Idea

• Binary classifier: f(x,w,b) = sign(wᵀx + b)
• Goal: find hyperplane that maximizes margin between classes
• Margin: distance between hyperplane and nearest points of each class
• Support vectors: data points closest to hyperplane (on margin boundary)
• Only support vectors determine the decision boundary

Hard-Margin SVM (Primal)

• Requires perfectly linearly separable data
• Maximizing margin = minimizing ‖w‖²

Soft-Margin SVM (with C)

• ξᵢ: slack variable — allows misclassification
• Large C: penalize misclassification heavily → small margin, overfit
• Small C: allow more misclassification → large margin, underfit

Dual Formulation

• αᵢ = 0 → non-support vector (doesn't affect decision boundary)
• αᵢ > 0 → support vector
• Dual depends on data only through inner products xᵢᵀxⱼ → enables kernel trick

Kernel Trick

• Replace xᵢᵀxⱼ with K(xᵢ,xⱼ) = φ(xᵢ)ᵀφ(xⱼ) — implicit high-dim feature map
• Never compute φ(x) explicitly — only need kernel evaluations

Valid kernel must correspond to an inner product in some feature space