Stanford CS229 - Machine Learning Principles & Core Algorithms Flashcards

Question 1

Linear Regression & Mean Squared Error Cost Function

Accepted Answer

The cost function $J(	heta)$ for linear regression measures the squared error between predicted values $h_	heta(x) = 	heta^T x$ and true targets $y$:

$$J(	heta) = \frac{1}{2m} \sum_{i=1}^{m} \left( h_	heta(x^{(i)}) - y^{(i)} ight)^2$$

where $m$ is the number of training examples, and the factor $\frac{1}{2}$ simplifies math during differentiation.

Question 2

Batch Gradient Descent Update Rule

Accepted Answer

Gradient descent minimizes $J(	heta)$ by iteratively updating parameters $	heta$ in the direction of steepest descent with learning rate $\alpha$:

$$	heta_j := 	heta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} \left( h_	heta(x^{(i)}) - y^{(i)} ight) x_j^{(i)}$$

All parameters $j \in \{0, \dots, n\}$ are updated simultaneously using the entire dataset per iteration.

Question 3

Normal Equation for Linear Regression

Accepted Answer

The analytical, closed-form solution to minimize $J(	heta)$ directly without iterations:

$$	heta = (X^T X)^{-1} X^T y$$

Where $X$ is the $m 	imes (n+1)$ design matrix. Computing $(X^T X)^{-1}$ costs $\mathcal{O}(n^3)$, making it computationally expensive when feature count $n$ is very large.

Question 4

Logistic Regression Hypothesis & Cross-Entropy Loss

Accepted Answer

Hypothesis models $P(y=1|x; 	heta)$ using the logistic (sigmoid) function $g(z) = \frac{1}{1 + e^{-z}}$:

$$h_	heta(x) = \frac{1}{1 + e^{-	heta^T x}}$$

The negative log-likelihood (cross-entropy) cost function is:

$$J(	heta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_	heta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_	heta(x^{(i)})) ight]$$

Question 5

Generative vs. Discriminative Algorithms

Accepted Answer

- **Discriminative Models**: Learn $P(y|x)$ directly or map inputs $x$ directly to class labels (e.g., Logistic Regression, Support Vector Machines).
- **Generative Models**: Learn joint distribution $P(x, y) = P(x|y)P(y)$ and apply Bayes' Rule $P(y|x) = \frac{P(x|y)P(y)}{P(x)}$ to infer class labels (e.g., Naive Bayes, Gaussian Discriminant Analysis).

Question 6

Naive Bayes Classifier & Conditional Independence Assumption

Accepted Answer

Generative model that assumes features $x_1, \dots, x_n$ are conditionally independent given label $y$:

$$P(x_1, \dots, x_n | y) = \prod_{j=1}^{n} P(x_j | y)$$

Prediction is made using Bayes' Rule:

$$y^* = \arg\max_y P(y) \prod_{j=1}^{n} P(x_j | y)$$

Question 7

SVM Hard-Margin Optimization Objective

Accepted Answer

Finds the hyperplanes $	heta^T x + b = 0$ that maximize the geometric margin $\frac{1}{||	heta||}$ for linearly separable data:

$$\min_{	heta, b} \frac{1}{2} ||	heta||^2 \quad 	ext{s.t.} \quad y^{(i)}(	heta^T x^{(i)} + b) \ge 1, \quad \forall i$$

Minimizing $\frac{1}{2} ||	heta||^2$ is equivalent to maximizing the functional/geometric margin.

Question 8

SVM Soft-Margin Optimization & Hyperparameter C

Accepted Answer

Allows for non-separable data by introducing slack variables $\xi_i \ge 0$:

$$\min_{	heta, b, \xi} \frac{1}{2} ||	heta||^2 + C \sum_{i=1}^{m} \xi_i \quad 	ext{s.t.} \quad y^{(i)}(	heta^T x^{(i)} + b) \ge 1 - \xi_i, \quad \xi_i \ge 0$$

$C$ controls the tradeoff: large $C$ strictly penalizes misclassifications (higher variance), while small $C$ allows more margin violations (higher bias).

Question 9

Kernel Method & Mercer's Theorem

Accepted Answer

The **Kernel Trick** replaces feature vector inner products $\langle \phi(x), \phi(z) \rangle$ with a kernel function $K(x, z)$ without explicitly computing high-dimensional vectors $\phi$.

**Mercer's Theorem**: $K(x, z)$ is a valid kernel if and only if the Gram matrix $K_{ij} = K(x^{(i)}, x^{(j)})$ is symmetric positive semi-definite for any dataset.

Question 10

Bias-Variance Tradeoff Decomposition

Accepted Answer

Expected test generalization error decomposes into three additive components:

$$	ext{Expected Error} = 	ext{Bias}^2 + 	ext{Variance} + 	ext{Irreducible Error}$$

- **Underfitting (High Bias)**: Model is overly simple (e.g., linear fit for non-linear data).
- **Overfitting (High Variance)**: Model fits noise in training data and fails to generalize.

Question 11

$L_1$ (Lasso) vs. $L_2$ (Ridge) Regularization

Accepted Answer

Both add parameter penalties to cost functions to reduce overfitting:

- **$L_2$ Regularization (Ridge)**: Adds $\lambda ||	heta||_2^2 = \lambda \sum_j 	heta_j^2$. Shrinks weights smoothly toward zero.
- **$L_1$ Regularization (Lasso)**: Adds $\lambda ||	heta||_1 = \lambda \sum_j |	heta_j|$. Drives non-essential weights to **exactly zero**, performing automated feature selection.

Question 12

Information Gain & Entropy in Decision Trees

Accepted Answer

Entropy $H(S)$ measures class impurity of set $S$:

$$H(S) = -\sum_{i=1}^{C} p_i \log_2(p_i)$$

Information Gain $IG(S, A)$ measures entropy reduction when splitting $S$ on attribute $A$:

$$IG(S, A) = H(S) - \sum_{v \in 	ext{Values}(A)} \frac{|S_v|}{|S|} H(S_v)$$

Question 13

Ensemble Methods: Bagging vs. Boosting

Accepted Answer

- **Bagging (Bootstrap Aggregating)**: Trains base models (e.g., deep decision trees) independently in parallel on bootstrap samples. Reduces **variance** (e.g., Random Forests).
- **Boosting**: Sequential training where each new weak learner targets residual errors of prior models. Reduces **bias** (e.g., AdaBoost, XGBoost).

Question 14

Neural Network Activation Functions: ReLU, Sigmoid, & Softmax

Accepted Answer

- **Sigmoid**: $g(z) = \frac{1}{1 + e^{-z}}$, maps inputs to $(0, 1)$; prone to vanishing gradients.
- **ReLU**: $g(z) = \max(0, z)$, standard hidden layer activation; avoids vanishing gradients for positive inputs.
- **Softmax**: Converts vector $z$ to a probability distribution across $K$ classes: $P(y=k|x) = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}$.

Question 15

Backpropagation Algorithm Principle

Accepted Answer

Uses the multivariable calculus **Chain Rule** to compute gradients of loss $L$ with respect to layer weights $W^{[l]}$:

$$\frac{\partial L}{\partial W^{[l]}} = \delta^{[l]} (a^{[l-1]})^T, \quad 	ext{where } \delta^{[l]} = \frac{\partial L}{\partial z^{[l]}}$$

Propagates error terms $\delta^{[l]}$ backwards from output to input layers.

Question 16

$k$-Means Clustering Distortion Objective & Algorithm

Accepted Answer

Unsupervised algorithm minimizing distortion cost function $J$:

$$J(c, \mu) = \sum_{i=1}^{m} ||x^{(i)} - \mu_{c^{(i)}}||^2$$

Alternates until convergence:
1. **Cluster Assignment**: $c^{(i)} := \arg\min_k ||x^{(i)} - \mu_k||^2$
2. **Centroid Update**: $\mu_k := \frac{\sum_{i=1}^m \mathbf{1}\{c^{(i)}=k\} x^{(i)}}{\sum_{i=1}^m \mathbf{1}\{c^{(i)}=k\}}$

Question 17

Expectation-Maximization (EM) Algorithm Structure

Accepted Answer

Optimization method for latent variable models (e.g., Gaussian Mixture Models):

- **E-Step (Expectation)**: Calculates expected values (responsibilities) of latent variables given current parameters: $w_j^{(i)} = P(z^{(i)}=j | x^{(i)}; 	heta)$.
- **M-Step (Maximization)**: Updates model parameters $	heta$ by maximizing log-likelihood using latent assignments from E-Step.

Question 18

Principal Component Analysis (PCA) Objective

Accepted Answer

Dimensionality reduction technique that projects data into a $k$-dimensional subspace while maximizing variance (or minimizing reconstruction error).

1. Normalize features to zero mean.
2. Compute empirical covariance matrix $\Sigma = \frac{1}{m} X^T X$.
3. Perform Singular Value Decomposition (SVD) on $\Sigma$ and project onto top $k$ principal eigenvectors.

Question 19

PAC Learning Framework & VC Dimension

Accepted Answer

- **Probably Approximately Correct (PAC)**: Formal framework bounds required training sample size so that hypothesis generalization error is $\le \epsilon$ with high probability $1 - \delta$.
- **VC Dimension $VC(H)$**: Measures model capacity as the maximum cardinality of a set of points that hypothesis class $H$ can shatter (label in all $2^n$ possible ways).

Question 20

Markov Decision Process (MDP) & Bellman Optimality Equation

Accepted Answer

An MDP is defined by $(S, A, P, R, \gamma)$. The optimal value function $V^*(s)$ satisfies the **Bellman Optimality Equation**:

$$V^*(s) = \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V^*(s') \right]$$

where $\gamma \in [0, 1)$ is the discount factor for future rewards.

Stanford CS229 - Machine Learning Principles & Core Algorithms

Cards in this deck

Related Flashcard Sets

HSK 1 - Basic Chinese Vocabulary, Pinyin & Character Recognition

Functional Programming - Immutability, Pure Functions & Higher-Order Functions

Neuroscience - Neuroanatomy & Brain Function

Microsoft Azure Administrator (AZ-104) - Compute, Storage & Networking