Supervised Learning: Linear Models

1. Setting & Technical Terms

In supervised learning, we are given a dataset:

• Features: ${\mathbf{x}}_i\in {\mathbb{R}}^d$ for $i=1,\dots ,n$.
• Labels: $y_i$, which can be real-valued (regression) or discrete (classification).

We seek a prediction function (hypothesis)

$$H:{\mathbb{R}}^d\to \mathcal{Y},$$

where $\mathcal{Y}=\mathbb{R}$ in regression or $\{0,1\}$, $\{-1,+1\}$ in classification.

Common terms:

• Training set: the data used to fit the model.
• Test set: held-out data to evaluate generalization.
• Overfitting: when the model fits the training data too closely and fails on unseen data.

---

2. General Pipeline

1. Choose a hypothesis class $\mathcal{H}$ (e.g., linear models).
2. Define a loss function $\ell (y,\hat{y})$ measuring prediction error.
3. Minimize empirical risk over $\mathcal{H}$: find $H^{\ast }$.
4. Evaluate on held-out data.

Graphically:

Data --> Model Choice --> Loss & Optimization --> Trained Model --> Prediction

---

3. Empirical Risk Minimization – Linear Regression

We illustrate ERM using linear regression.

3.1 Step 1: Hypothesis Class

We restrict to affine functions:

$$\mathcal{H}=\left\{H_{\mathbf{w},b}(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b:\mathbf{w}\in {\mathbb{R}}^d,b\in \mathbb{R}\right\}.$$

We often fold $b$ into $\mathbf{w}$ by augmenting $\mathbf{x}$ with 1:

$\tilde{\mathbf{x}}=[1,x_1,\dots ,x_d{]}^T,\tilde{\mathbf{w}}=[b,w_1,\dots ,w_d{]}^T$, so that $H(\mathbf{x})={\tilde{\mathbf{w}}}^T\tilde{\mathbf{x}}.$

3.2 Step 2: Loss Function

Choose the squared loss for regression:

$$\ell (y,\hat{y})=(y-\hat{y}{)}^2.$$

For a dataset of $n$ points, the empirical risk is:

$$R_{\mathrm{emp}}(\mathbf{w})=\frac{1}{n}\sum _{i=1}^n(y_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2.$$

3.3 Step 3: Minimize Empirical Risk

We solve:

$${\mathbf{w}}^{\ast }=\arg \underset{\mathbf{w}}{\min }{R}_{\mathrm{emp}}(\mathbf{w}).$$

This is a quadratic problem with a closed-form solution. Let:

• $X\in {\mathbb{R}}^{n\times d}$ be the data matrix (rows are ${\mathbf{x}}_i^T$).
• $\mathbf{y}\in {\mathbb{R}}^n$ be the vector of labels.

Then

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

Note: Matrix $X^{T}X$ must be invertible (or we add regularization).

3.4 Example: Movie Rating Prediction

Suppose you have ratings from 3 friends for a movie:

Friend	Rating (feature)
Alice	8
Bob	5
Charlie	7

You want to predict your own rating $y$ based on theirs. Let $\mathbf{x}\in {\mathbb{R}}^3$ be the feature vector $[8,5,7{]}^T$. Assume the model $y\approx w_1{x}_1+w_2{x}_2+w_3{x}_3$. Using least squares on past data, we solve for ${\mathbf{w}}^{\ast }$ by the formula above.

import numpy as np
 
# Example data
X = np.array([
    [8, 5, 7],  # Movie 1
    [7, 6, 8],  # Movie 2
    [6, 7, 6]   # Movie 3
])
y = np.array([7, 8, 6])  # Your ratings
 
# Add bias term
X_aug = np.column_stack([np.ones(len(X)), X])
 
# Compute optimal weights
w_star = np.linalg.inv(X_aug.T @ X_aug) @ X_aug.T @ y
print("Optimal weights:", w_star)
 
# Make prediction for new movie
new_movie = np.array([1, 8, 5, 7])  # [bias, Alice, Bob, Charlie]
prediction = new_movie @ w_star
print(f"Predicted rating: {prediction:.2f}")

---

4. Extension to Linear Classification

Linear models can also classify by thresholding:

$$f(\mathbf{x})=\mathrm{sign}({\mathbf{w}}^T\mathbf{x}+b)\in \{-1,+1\}.$$

This reduces classification to a regression output with a decision boundary at zero.

4.1 Example: Mango Ripeness

Features: sugar content $x_1$ and firmness $x_2$. We collect samples labeled $y=+1$ (ripe) or $-1$ (unripe). Fit $\mathbf{w}$ by minimizing squared loss as above, then predict:

$$\hat{y}=\{\begin{array}{ll}+1& \text{if }{\mathbf{w}}^T\mathbf{x}\ge 0,\\ -1& \text{otherwise.}\end{array}$$

# Example: Mango classification
X = np.array([
    [0.8, 0.3],  # Ripe mango
    [0.7, 0.4],  # Ripe mango
    [0.3, 0.8],  # Unripe mango
    [0.4, 0.7]   # Unripe mango
])
y = np.array([1, 1, -1, -1])
 
# Add bias term
X_aug = np.column_stack([np.ones(len(X)), X])
 
# Compute optimal weights
w_star = np.linalg.inv(X_aug.T @ X_aug) @ X_aug.T @ y
print("Optimal weights:", w_star)
 
# Make prediction for new mango
new_mango = np.array([1, 0.75, 0.35])  # [bias, sugar, firmness]
prediction = np.sign(new_mango @ w_star)
print(f"Predicted class: {'Ripe' if prediction > 0 else 'Unripe'}")

Caution: Using MSE for classification is sensitive to outliers in $y$ and can distort the decision boundary. For better probabilistic outputs, consider logistic loss and logistic regression.

---

Written Notes

• ERM: Framework for fitting models by risk minimization.
• Hypothesis Class: Choice balances bias vs. variance.
• Loss Function: Determines what “error” means; choose according to task.
• Optimization: Closed-form for linear regression; iterative methods for others.
• Classification: Linear separators work in feature space; use feature maps for nonlinearity.