Linear Regression

Linear Regression is a fundamental supervised learning algorithm for predicting a continuous target variable $y$ as a linear combination of input features $x$.

1. Mathematical Formulation

Hypothesis Function

For an input feature vector $x = [1, x_1, x_2, \dots, x_n]^T$ and parameter weight vector $\theta = [\theta_0, \theta_1, \dots, \theta_n]^T$:

$$h_\theta(x) = \theta^T x = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_n x_n$$

In matrix form for a dataset of $m$ examples with design matrix $X \in \mathbb{R}^{m \times (n+1)}$:

$$\hat{y} = X\theta$$

2. Cost Function (Mean Squared Error / OLS)

The parameters $\theta$ are chosen to minimize the Ordinary Least Squares (OLS) loss function:

$$J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \big( h_\theta(x^{(i)}) - y^{(i)} \big)^2 = \frac{1}{2m} \| X\theta - y \|_2^2$$

3. Parameter Optimization

Approach A: Gradient Descent (Iterative)

Simultaneously update all weights $\theta_j$ in the direction of the negative gradient:

$$\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta) = \theta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} \big( h_\theta(x^{(i)}) - y^{(i)} \big) x_j^{(i)}$$

In vectorized form:

$$\theta := \theta - \alpha \frac{1}{m} X^T (X\theta - y)$$

Where $\alpha$ is the learning rate.

Approach B: Normal Equation (Closed-Form Solution)

Setting the analytical gradient $\nabla_\theta J(\theta) = 0$ yields the exact closed-form solution:

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

• Pros: No need to choose learning rate $\alpha$; no iterations needed.
• Cons: Computing $(X^T X)^{-1}$ requires $O(n^3)$ time, becoming prohibitively slow when feature dimension $n > 10,000$.

4. Regularization

To prevent overfitting and handle multicollinearity, regularization penalties are added to the cost function:

Method	Penalty	Objective Function	Properties
Ridge ($L_2$)	$\lambda \sum_{j=1}^n \theta_j^2$	$J(\theta) + \frac{\lambda}{2m}\|\theta\|_2^2$	Shrinks weights toward zero; keeps all features; analytical solution: $\theta = (X^T X + \lambda I)^{-1} X^T y$.
Lasso ($L_1$)	$\lambda \sum_{j=1}^n \|\theta_j\|$	$J(\theta) + \frac{\lambda}{m}\|\theta\|_1$	Drives irrelevant feature weights exactly to zero; performs automatic feature selection.
Elastic Net	Combination of $L_1 + L_2$	$J(\theta) + r\lambda \|\theta\|_1 + \frac{1-r}{2}\lambda \|\theta\|_2^2$	Balances sparsity of Lasso with feature grouping stability of Ridge.

5. Key Assumptions of OLS Linear Regression

1. Linearity: The relationship between features and the target is linear in parameters.
2. Homoscedasticity: The variance of residual errors is constant across all levels of features.
3. Independence of Residuals: Observations and error terms are mutually independent (no autocorrelation).
4. Normality of Residuals: The error terms $\epsilon = y - \hat{y}$ are normally distributed $\mathcal{N}(0, \sigma^2)$.
5. No Multicollinearity: Features should not be linearly dependent on each other ($\det(X^T X) \neq 0$).

6. Evaluation Metrics

• Mean Squared Error (MSE): $\text{MSE} = \frac{1}{m} \sum_{i=1}^m (y_i - \hat{y}_i)^2$
• Root Mean Squared Error (RMSE): $\text{RMSE} = \sqrt{\text{MSE}}$ (interpretable in original target units)
• $R^2$ (Coefficient of Determination): $$R^2 = 1 - \frac{\sum (y_i - \hat{y}_i)^2}{\sum (y_i - \bar{y})^2}$$ Indicates the proportion of variance in $y$ explained by the model (ranges from 0 to 1).