Lecture 1: Logistics and introduction

Definition:

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

Experience E (data): games played by the program or human
Performance measure P: winning rate
Task T: to win

Taxonomy of Machine Learning (A Simplistic View)

1. Supervised Learning

Core idea: Learns from labeled data.
Example Tasks:
- Regression: The prediction result is a continuous variable.
  - e.g., price prediction
  - (x = Area) → (y = Price)?
- Classification: The prediction result is a discrete variable.
  - e.g., type prediction
  - (x = Area, y = Price) → (z = Type)?

2. Unsupervised Learning

Core idea: Learns from unlabeled data.
Example Tasks:
- Clustering:
  - Given a dataset containing n samples:
    (x⁽¹⁾, y⁽¹⁾), (x⁽²⁾, y⁽²⁾), (x⁽³⁾, y⁽³⁾), ..., (x⁽ⁿ⁾, y⁽ⁿ⁾)
  - Task (vague): find interesting structures in the data.

3. Semi-supervised Learning

Core idea: Learns from a mix of labeled and unlabeled data.

4. Reinforcement Learning

Core idea: Learns from environment feedback (rewards/penalties).
Example Task: Multi-armed bandit problem (MAB)
- it involves a feedback loop between an Agent and an Environment:
  1. The Agent takes an Action (e.g., pull an arm).
  2. The Environment returns Feedback (e.g., a corresponding reward).
  3. The agent learns from this feedback to make better decisions in the future.

Learning Modes (When do we collect data?)

Offline learning: The model is trained on a static dataset before deployment.
Online learning: The model is trained incrementally as new data becomes available.

Mathematical Tools

Mathematics for Ai

Mathematics for Ai (Chinese)

Parameter Estimation: Maximum Likelihood Estimation (MLE)

A foundational method for estimating the parameters of a statistical model from data.

Core Principle: Find the parameter values ( $θ$ ) that maximize the likelihood function. in other words, we find the parameters that make the observed data most probable.
$\hat{θ_{M L}} = \arg max_{θ} P (D a t a | θ)$
Example: MLE for Bernoulli Distribution
- Scenario: We have a dataset $D = X ₁, . . ., X ₘ$ from a Bernoulli distribution (e.g., $m$ coin flips), where $X_{i}$ is 1 (heads) or 0 (tails).
- Goal: Estimate the probability of heads, $θ = P (X = 1)$ .
- Derivation Steps:
  1. Likelihood Function: Assuming data points are independent and identically distributed (i.i.d.), the likelihood of observing the entire dataset is the product of individual probabilities:
    $L (θ) = \prod_{i} p (X_{i}; θ)$
  2. Log-Likelihood Function: To simplify calculation (turning products into sums) and for numerical stability, we maximize the log-likelihood, which is equivalent.
    $\log L (θ) = \sum_{i} \log p (X_{i}; θ)$
  3. Substitute Bernoulli PMF: The probability mass function for a single $X i$ can be written as $p (X_{i}; θ) = θ (X_{i}) * (1 - θ) (1 - X_{i})$ . its logarithm is $\log p (X i; θ) = X i \log (θ) + (1 - X_{i}) \log (1 - θ)$ . The log-likelihood becomes:
    $\log L (θ) = \sum_{i} [X_{i} l o g (θ) + (1 - X_{i}) l o g (1 - θ)]$
  4. Simplify: Let $M ₁ = \sum_{i} X_{i}$ be the total count of 1s (heads). The total count of 0s is $m - M ₁$ . The expression simplifies to:
    $\log L (θ) = M ₁ \log (θ) + (m - M ₁) \log (1 - θ)$
- Result: To find the maximum, we take the derivative of this final expression with respect to $θ$ , set it to 0, and solve. The resulting estimate is highly intuitive:
  $\hat{θ_{M L}} = \frac{M_{1}}{m}$ (The proportion of 1s in the data)

Lecture 3: Supervised Learning: Regression and Classification II

Ridge Regression: Study Notes

1. Core Idea & Philosophy

Ridge Regression is an enhancement of Ordinary Least Squares (OLS). Its core idea is to address the problem of overfitting by sacrificing a small amount of bias to achieve a significant reduction in model variance.

Analogy:

OLS is like a "novice detective" who tries to create a complex theory that perfectly explains 100% of the current evidence. This theory is often fragile and performs poorly on new cases (high variance).
Ridge Regression is like a "veteran detective" who knows that evidence contains noise and coincidences. He seeks a simpler, more general theory that might not explain every tiny detail perfectly but is more robust and predictive for new cases (low variance).

2. Motivation: Why is Ridge Regression Necessary?

Ridge Regression is primarily designed to solve critical failures of OLS that occur in a specific, common scenario.

The Problem Scenario: High-Dimension, Low-Sample Data (d >> m)

The number of features $d$ is much larger than the number of samples $m$ .
This is common in modern datasets like genetics, finance, and text analysis.

Problems for OLS in this Scenario:

A. Conceptual Level: Severe Overfitting

With more features than samples, the model has enough flexibility to "memorize" the training data, including its noise and random fluctuations.
This results in learned model weights ( $w$ ) that are absurdly large, assigning huge importance to potentially irrelevant features.
The model performs perfectly on training data but fails to generalize to unseen test data.

B. Mathematical Level: The Matrix $X ᵀ X$ is Non-Invertible (Singular)

The analytical solution for OLS is: $w * = (X ᵀ X) ⁻ ¹ X ᵀ y$ .
This solution requires the matrix $X ᵀ X$ to be invertible.
$X ᵀ X$ is often non-invertible or ill-conditioned (nearly non-invertible) in two cases:
1. When $m < d + 1$ (Fewer Samples than Features): This is the main reason. By linear algebra, $r a n k (X ᵀ X) = r a n k (X) \leq m i n (m, d + 1)$ . If $m < d + 1$ , the rank of $X ᵀ X$ is less than its dimension ( $d + 1$ ), meaning it is not full rank and is therefore guaranteed to be singular (non-invertible).
2. Multicollinearity: When features are highly correlated (e.g., including both "house size in sq. meters" and "house size in sq. feet"). This makes the columns of $X$ linearly dependent, which in turn makes $X ᵀ X$ singular.

3. The Solution: How Ridge Regression Works

Ridge Regression introduces a penalty term into the objective function to constrain the size of the model's weights.

Step 1: Modify the Objective Function

Ordinary Least Squares (OLS) Objective:
- Minimize the Sum of Squared Errors (SSE)
- $J_{O L S} (w) = | | y - X w | | ₂ ²$
Ridge Regression Objective:
- Minimize SSE + λ * Penalty on Model Complexity
- $J_{R i d g e} (w) = | | y - X w | | ₂ ² + λ | | w | | ₂ ²$
Dissecting the Penalty Term:
- $| | w | | ₂ ² = Σ (w ᵢ) ²$ : This is the squared L2-Norm of the weight vector. It is the sum of the squares of all weights. A large value implies a complex model with large weights.
- $λ$ (Lambda): The regularization parameter. This is a hyperparameter that we set to control the strength of the penalty.
  - Large $λ$ : Strong penalty. The model is forced to shrink the weights towards zero to avoid a large penalty.
  - Small $λ$ : Weak penalty. The model behaves more like OLS.
  - $λ = 0$ : No penalty. Ridge Regression becomes identical to OLS.

Step 2: Derive the New Analytical Solution

By taking the derivative of the new objective function with respect to $w$ and setting it to zero, we get the analytical solution for Ridge Regression:

$w_{r i d g e}^{*} = (X ᵀ X + λ I) ⁻ ¹ X ᵀ y$

$I$ is the Identity Matrix.
Compared to the OLS solution, the only difference is the addition of the $+ λ I$ term. This single term is what solves the non-invertibility problem.

4. The Core Insight: Why $+ λ I$ is the "Special Medicine"

This term works by altering the eigenvalues of the matrix to guarantee its invertibility.

Invertibility and Eigenvalues: A matrix is singular (non-invertible) if and only if it has at least one eigenvalue that is 0.
Eigenvalues of $X ᵀ X$ : $X ᵀ X$ is a positive semi-definite matrix, which means all its eigenvalues $μ ᵢ$ are non-negative ( $μ ᵢ \geq 0$ ). When it's singular, it has at least one eigenvalue $μ ᵢ = 0$ .
The Effect of $+ λ I$ : When we add $λ I$ to $X ᵀ X$ , the eigenvalues of the new matrix $(X ᵀ X + λ I)$ become $(μ ᵢ + λ)$ .
The Result:
- We choose $λ$ to be a small positive number ( $λ > 0$ ).
- The original eigenvalues were $μ ᵢ \geq 0$ .
- The new eigenvalues are $μ ᵢ + λ$ .
- Therefore, all new eigenvalues are strictly positive ( $> 0$ ).
- A matrix whose eigenvalues are all greater than zero is guaranteed to be invertible.

Conclusion: The $λ I$ term acts as a "stabilizer" by shifting all eigenvalues of $X ᵀ X$ up by a positive amount $λ$ , ensuring that none are zero and thus making the matrix $(X ᵀ X + λ I)$ invertible.

5. Summary & Comparison

Aspect	Ordinary Least Squares (OLS)	Ridge Regression
Objective Function	Minimize SSE	Minimize [SSE + λ * L2-Norm of weights]
Model Complexity	Unconstrained, weights can be very large	Constrained by L2 penalty, forcing weights to be smaller
Handling $d > m$	$X ᵀ X$ is singular; no stable solution exists	$(X ᵀ X + λ I)$ is always invertible; provides a stable solution
Analytical Solution	$(X ᵀ X) ⁻ ¹ X ᵀ y$	$(X ᵀ X + λ I) ⁻ ¹ X ᵀ y$
Key Property	Unbiased estimate, but can have very high variance	Biased estimate, but with significantly lower variance
Best Use Case	Low-dimensional data, no multicollinearity	High-dimensional data (esp. $d > m$ ), multicollinearity is present

6. How to Choose $λ$ ?

$λ$ is a critical hyperparameter that controls the trade-off between bias and variance. It is not learned from the training data. The optimal value of $λ$ is typically found using Cross-Validation, a technique that evaluates the model's performance on unseen data for different $λ$ values and selects the one that generalizes best.