Maximum Likelihood and Least Squares

Linear regression is the simplest yet most fundamental tool in machine learning for predicting a continuous target variable $y$ from input features $x$.

1. Foundations: Random Variables

Before diving into estimation, we must distinguish between the types of data we encounter:

• Discrete Random Variables: $X \in \{x_1, x_2, \dots, x_n\}$. We use a Probability Mass Function (PMF) where $P(X=x_i)$ is the probability of a specific outcome.
  • Example: A coin toss or a dice roll.
• Continuous Random Variables: $X \in \mathbb{R}$. We use a Probability Density Function (PDF). Note that for continuous variables, $P(X=x) = 0$ for any specific point; we instead measure the probability over an interval.
  • Gaussian (Normal) Distribution: The most common PDF in ML: $P(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{1}{2\sigma^2}(x-\mu)^2}$

2. The Dataset and Likelihood

We represent our dataset $D$ as a collection of $m$ samples: $D = \{(x^{(i)}, y^{(i)})\}_{i=1}^m$

For independent events, the joint probability is the product of individual probabilities: $P(A \cap B) = P(A)P(B) = P(A, B)$

Accordingly, the Likelihood of our data given parameters $\theta$ is: $L(\theta; D) = P(D; \theta)$

Generative vs. Discriminative View

• Generative Algorithms: Model the joint probability $P(x, y)$.
• Discriminative Algorithms: Model the conditional probability $P(y \mid x)$.

3. The Generative Model for Regression

In Linear Regression, we assume that the target variable $y$ is generated by: $y = \theta^T x + \epsilon$

Where the noise $\epsilon$ follows a Gaussian distribution: $\epsilon \sim \mathcal{N}(0, \sigma^2)$. This implies that $y$ itself is a random variable following a Gaussian distribution centered at our prediction: $y \sim \mathcal{N}(\theta^T x, \sigma^2)$

For a dataset of $m$ Independent and Identically Distributed (i.i.d.) observations: $L(\theta; D) = \prod_{i=1}^m P(y^{(i)} \mid x^{(i)}; \theta)$

4. Maximum Likelihood Estimation (MLE)

To find the optimal $\theta$, we maximize the Log-Likelihood (since $\log$ is a monotonic function, maximizing $\log L$ is the same as maximizing $L$):

$\log L(\theta; D) = \log \prod_{i=1}^m P(y^{(i)} \mid x^{(i)}; \theta) = \sum_{i=1}^m \log P(y^{(i)} \mid x^{(i)}; \theta)$

For the Gaussian case: $P(y \mid x; \theta) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{1}{2\sigma^2}(y - \theta^T x)^2}$

Taking the log: $\log L(\theta) = \sum_{i=1}^m \left[ \underbrace{\log \frac{1}{\sqrt{2\pi\sigma^2}}}_{\text{Constant}} - \frac{1}{2\sigma^2} (y^{(i)} - \theta^T x^{(i)})^2 \right]$

Connection to Least Squares

Since we want to maximize this expression, and the first term is constant, we focus on the second term. Maximizing a negative value is equivalent to minimizing the positive version: $\max \log L(\theta) \approx \min \sum_{i=1}^m (y^{(i)} - \theta^T x^{(i)})^2$

This is the Ordinary Least Squares (OLS) objective. The solution is: $\theta_{ML} = (X^T X)^{-1} X^T y$