Linear Regression

Palo Alto Housing Prices: 3D Linear Regression

Learning Rate (α): 0.100

0.01 (Slow)0.15 (Fast)

Iterations: 0

0 (None)200 (Converged)

Intercept (θ₀)

$0.000M

Distance (θ₁)

0.000

Room Size (θ₂)

0.000

MSE

0.0000

What is Linear Regression

Linear Regression is a supervised learning algorithm, which assumes a linear relationship between features (X) and a target (y). We can approximate our target y, as a linear function of x, such that:

$$h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_d x_d = \sum_{i=0}^{d} \theta_i x_i = \theta^T x$$

with parameters (or weights) $\theta_i$'s

Then, we minimize the least squares objective:

$$J(\theta) = \sum_{i=1}^{n} \left(h_\theta(x^{(i)}) - y^{(i)}\right)^2$$

Consider $y^{(i)} = \theta^T x^{(i)} + \varepsilon^{(i)}$ where $\varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2)$ independently and identically distributed (iid).

$\mathcal{N}(\mu, \sigma^2)$ is the Normal (Gaussian) distribution with probability density function:

$$f(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$$

Maximum Likelihood Estimation (MLE)

$$L(\theta) = \prod_{i=1}^{n} P(y^{(i)}; x^{(i)}, \theta)$$

$$= \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi\sigma}} \exp\left(-\frac{(y^{(i)} - \theta^T x^{(i)})^2}{2\sigma^2}\right)$$

Log-Likelihood (easier to work with):

$$\ell(\theta) = \log L(\theta)$$

$$= \log \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi\sigma}} \exp\left(-\frac{(y^{(i)} - \theta^T x^{(i)})^2}{2\sigma^2}\right)$$

$$= \sum_{i=1}^{n} \log \frac{1}{\sqrt{2\pi\sigma}} \exp\left(-\frac{(y^{(i)} - \theta^T x^{(i)})^2}{2\sigma^2}\right)$$

$$= n \log \frac{1}{\sqrt{2\pi\sigma}} - \frac{1}{\sigma^2} \cdot \frac{1}{2} \sum_{i=1}^{n} (y^{(i)} - \theta^T x^{(i)})^2$$

$$\ell(\theta) = \min_{\theta} \sum_{i=1}^{n} (y^{(i)} - \theta^T x^{(i)})^2$$

tip

$\sum_{i=1}^{n} (y^{(i)} - \theta^T x^{(i)})^2$ is also called Sum of Squared Errors (SSE).

Cost Function

The Mean Squared Error (MSE) cost function:

$$J(\theta) = \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x^{(i)}) - y^{(i)})^2$$

note

The factor $1/2n$ can be added to the cost function because it's a constant with respect to $\theta$ in $\arg\min_\theta$. It doesn't affect the location of the minimum, but makes derivatives easier (cleaner factors) when optimizing.

$$\nabla J(\theta) = \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}$$

Optimization Methods

To minimize this cost function, you can use Gradient Descent algorithms (Batch GD, SGD, Mini-batch GD) or the analytical Normal Equation. See the Gradient Descent page for details.

Normal Equation

Analytical solution to find optimal $\theta$:

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

Pros: No need to choose learning rate, no iterations
Cons: Slow if $n$ is large (computing inverse is $O(n^3)$)

Matrix Calculus Derivation

Using matrix notation, the Linear Regression Loss can be written as:

$$L(\mathbf{w}) = \|\mathbf{Xw} - \mathbf{y}\|^2 = (\mathbf{Xw} - \mathbf{y})^T(\mathbf{Xw} - \mathbf{y})$$

Taking the gradient with respect to $\mathbf{w}$:

$$\frac{\partial L}{\partial \mathbf{w}} = 2\mathbf{X}^T(\mathbf{Xw} - \mathbf{y})$$

Setting the gradient to zero to find the minimum:

$$2\mathbf{X}^T(\mathbf{Xw} - \mathbf{y}) = 0$$

$$\mathbf{X}^T\mathbf{Xw} = \mathbf{X}^T\mathbf{y}$$

Solving for $\mathbf{w}$ gives the Normal Equation:

$$\mathbf{w} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$$

Ridge Regression (L2 Regularization)

Regularization helps prevent overfitting by adding a penalty term to the cost function that discourages complex models.

Add the squared magnitude of coefficients to the cost function:

$$J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2 + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$$

• $\lambda$ is the regularization parameter
• Larger $\lambda$ means more regularization (simpler model)
• Does not include $\theta_0$ in the penalty term

Effect: Shrinks coefficients towards zero but doesn't set them exactly to zero.