Linear RegressionHow a Machine Draws the Best Straight Line

Linear regression belongs to a family called supervised learning. A supervised learning model uses labeled data to learn a mapping from inputs to outputs:

The data comes as pairs. Every input arrives with its correct answer attached, and that answer is the label:

where \(x_i\) is an input (a feature vector), \(y_i\) is the corresponding output, and \(n\) is the number of training examples. Each \(x_i \in \mathcal{X}\), the input space of all possible features, and each \(y_i \in \mathcal{Y}\), the output space.

A concrete example, house prices:

So the dataset is \(\{(1000, 100000), (1500, 150000), \dots\}\). Here \(\mathcal{X}\) is all possible house features (size, rooms, and so on) and \(\mathcal{Y}\) is all possible prices. When the output is a continuous number like a price, the task is called regression. When it is a category, it is classification, and that story is in the logistic regression note.

What is an 1800 sq ft house worth? We need a rule that converts house size into house price. A first guess:

Testing it against the data: \(1000 \times 100 = 100{,}000\), \(1500 \times 100 = 150{,}000\), \(2000 \times 100 = 200{,}000\). It fits every row. So using the rule, \(1800 \times 100 = \$180{,}000\). That is a prediction: using a learned rule to estimate outputs for new, unseen inputs.

But what if the rule isn't perfect? Maybe the actual price of that house turns out to be \$175,000, so our prediction was off by \$5,000. That gap is the error, how wrong our prediction is. And trying different rules to find the one with the smallest error, that process is optimization. These three words, prediction, error, optimization, are the skeleton of everything below.

Linear regression is a supervised learning algorithm that models the relationship between input features and a continuous target variable by fitting a straight line. The school equation of a line is exactly the model:

In machine learning clothes it reads: price equals a weight (slope) times house size, plus a bias (intercept), the base price when size is zero. The slope \(m\) says how much the price changes per square foot. This candidate line has a formal name, the hypothesis function.

Statisticians write the same line with betas, \( y = \beta_0 + \beta_1 x \). One input feature makes it simple linear regression. But a house price doesn't just depend on size. It also depends on number of bedrooms, age, location. With \(x_1 = \) size, \(x_2 = \) bedrooms, \(x_3 = \) age:

and in general, for \(n\) features, multiple linear regression:

It is tidy to collect all parameters into one symbol \(\beta\). Add a fake feature \(x_0 = 1\) for the bias, so \(\beta_0\) multiplies it directly:

With the parameter vector \(\beta = [\beta_0, \beta_1, \dots, \beta_n]\) and the feature vector \(x = [1, x_1, \dots, x_n]\), the whole sum collapses into one dot product:

Stacking all \(m\) training examples as rows of a matrix \(X\) (each row starting with the 1) gives the matrix form used everywhere in practice:

where \(\varepsilon\) is the residual, the part the line cannot explain: \( \varepsilon = y - \hat{y} \). Here \(\beta_i\) are the parameters parameterizing the space of linear functions mapping \(x\) to \(y\) (the general theory of gradient descent calls this same collection \(\theta\); it's the identical idea under a different name). Learning means choosing them well.

We want predictions as close as possible to the real answers. The cost function measures error, how wrong we are, over the whole dataset. The obvious first idea, just add up the errors, fails in a funny way. Take two houses (working in thousands of dollars):

Zero total error from two wrong predictions. Wait a minute...! The positive and negative misses cancel. That is why instead of subtracting we square the difference. Squaring kills the sign, so errors can't cancel, and it penalizes big mistakes much more than small ones:

Total 800, and the failure is visible. Averaging over \(n\) examples gives the Mean Squared Error, the standard cost function of linear regression. The model needs one number to say how bad it is, and MSE answers "on average, how wrong is the model?":

In the \(\beta\) notation the convention adds a factor of \(\tfrac{1}{2}\), purely to make the derivative cleaner during gradient descent (the 2 that falls out of \(\frac{d}{dx}x^2 = 2x\) cancels it):

where \(h_\beta(x^{(i)})\) is the predicted output for the \(i\)-th example and \(y^{(i)}\) the actual output. The smaller \(J(\beta)\), the better the model fits the data.

Watch it happen. Dataset: hours studied vs exam score, \((1, 35), (2, 45), (3, 55)\). Move the two knobs of the line and watch the MSE respond:

A positive error means the model predicted too low, a negative error means too high. Squaring folds both into "wrong". And a minimum of the cost is not always zero error. Real data is noisy, so the best line usually keeps some irreducible error. Zero here only happens because these three points are secretly collinear.

Fix the slope at \(\beta_1 = 10\) and plot MSE as a function of the intercept alone. Each guess becomes a point \((\beta_0, \text{MSE})\): \((0, 625)\), \((20, 25)\), \((25, 0)\), \((30, 25)\), \((50, 625)\). They trace a parabola, a U-shape:

With two free parameters the picture gains a dimension: x-axis \(\beta_0\), y-axis \(\beta_1\), z-axis MSE. The parabola becomes a bowl (an elliptic paraboloid), and the very bottom of the bowl is the pair \((\beta_0, \beta_1) = (25, 10)\).

The bowl shape is not luck. The MSE cost of linear regression is convex. A function \(f\) is convex if for any two points \(x_1, x_2\) in its domain and any \(\lambda \in [0,1]\):

In words, the straight segment between any two points on the graph lies on or above the graph. Convex means curving upward, and it guarantees the function has one and only one minimum, the global minimum. A global minimum is a point where the function value is lower than at all other points in the entire domain. In linear regression that point corresponds to the best coefficients. Non-convex functions, which show up in non-linear models, have multiple peaks and valleys: local minima, points lower than their neighbours but not lowest overall. There an optimizer can get stuck. The full convex story, with pictures, lives in the gradient descent note.

So the best line is the bottom of a bowl. How does a machine walk there? Gradient descent: an optimization algorithm that minimizes the cost by iteratively updating the parameters in the direction of steepest decrease, the negative gradient. For every parameter \(\beta_j\):

where \(\alpha\) is the learning rate, the step size. For the MSE cost the two partial derivatives work out to (derivation in the gradient descent note):

or, in the \(\tfrac{1}{2m}\) convention where the 2 cancels:

The learning rate decides how fast and how stable the walk is:

Everything deeper, the worked example computed by hand, batch versus stochastic descent, the convergence theorem, and an interactive descent you can break on purpose, is in the dedicated note: Gradient Descent, walking downhill in math.

Can we solve linear regression without gradient descent? Yes. A closed-form solution is a direct, explicit formula for a mathematical problem. The linear equation \(2x - 6 = 0\) has the closed form \(x = b/a\). The quadratic \(2x^2 - 7x + 3 = 0\) has one too, the quadratic formula \(x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\). Linear regression is no different.

Write the sum of squared errors, take its partial derivatives, and set them to zero (at a minimum the slope is zero):

Solving that system in matrix form gives the normal equation:

with \(X\) the feature matrix and \(y\) the target vector. One formula, no iterations, no learning rate. The catch: inverting \(X^{\mathsf T}X\) costs roughly cubic time in the number of features, so for very large feature counts gradient descent wins. For small problems the normal equation is instant and exact.

The same machinery on different data. A used car dataset, mileage against price:

Here the slope comes out negative, which is exactly right: more mileage, lower price. The least-squares fit of this table is

so for a car with 60,000 km, \( \text{Price} = (-0.2 \times 60{,}000) + 30{,}000 = \$18{,}000 \). The intercept \$30,000 is the model's price at zero mileage, and every kilometre driven subtracts 20 cents. A quick slope check with any two rows: \( m = \frac{\Delta y}{\Delta x} = \frac{24{,}000 - 28{,}000}{30{,}000 - 10{,}000} = -0.2 \). Same idea as the apartment-rent slope \( m = \frac{4000 - 2000}{200 - 100} = 20 \) dollars per square metre, one number that says what one more unit of input buys.

A straight line is a strong promise, and it only pays off when the data keeps a few promises back. Six assumptions, each with symptoms and fixes.

stats.probplot(residuals, dist="norm", plot=plt)

pd.get_dummies(df['region'], drop_first=True)

Overfitting: the model is too complex and learns the noise in the training data. Training error goes down, test error goes up. Underfitting: the model is too simple to capture the underlying patterns. Training error stays up, and the test error is no better. The telltale of overfitting in one line: train \(R^2 = 0.98\), test \(R^2 = 0.45\). The model learned the training data very well but failed on unseen data.

Four standard evaluation metrics for regression:

RMSE undoes the squaring so the number is back in the target's own units. MAE averages absolute misses and is gentler on outliers. The fourth is the coefficient of determination:

\(R^2\) means how much of the variation in the target our model can explain. In simple words, it tells us how much better the model is compared to simply predicting the average value every time (the baseline model). \(R^2 = 1\): the model predicts perfectly, all residuals are zero. \(R^2 = 0\): the model predicts no better than the mean of the target variable.

Polynomial regression is used when the relationship between \(x\) and \(y\) is curved, not linear:

For example, \( \text{charges} = \beta_0 + \beta_1(\text{age}) + \beta_2(\text{age})^2 \). If charges increase slowly as age increases and then very fast, a straight line model underfits, but this bent one follows.

Here is the good question: how is polynomial regression still linear regression, doesn't it break the linearity assumption? The model is \( \hat{y} = \beta_0 + \beta_1 x + \beta_2 x^2 \), and it is still linear in the coefficients. Nothing multiplies a \(\beta\) with another \(\beta\), no \(\beta\) sits inside a square. From the algorithm's point of view \(x^2\) is just another input column. Polynomial regression creates polynomial features, so it is basically linear regression plus polynomial feature engineering.

Regularization is a technique used to reduce overfitting by controlling how large the model coefficients become. Overfitting → add a penalty that discourages large coefficients. That is regularization. For linear regression the three main regularized models are Ridge, Lasso, and ElasticNet.

Ridge regression (L2) adds the sum of squared coefficients:

It shrinks coefficients toward zero but usually doesn't make them exactly zero.

Lasso regression (L1) adds the sum of absolute values:

It shrinks coefficients and can make some of them exactly zero, so Lasso doubles as automatic feature selection.

ElasticNet (L1 + L2) combines Ridge and Lasso:

Here \(\lambda\) is the regularization strength (in scikit-learn it is called alpha). Small \(\lambda\) → weak regularization. Large \(\lambda\) → strong regularization. And one convention worth remembering: usually we do not penalize the intercept \(\beta_0\), the penalty starts from \(\beta_1, \beta_2, \dots, \beta_n\).

Everything above, in practice, is a few lines. The closed form by hand with NumPy, then the library version:

# normal equation, by hand
import numpy as np
X = np.array([[1,1],[1,2],[1,3]])        # column of 1s = the x0 trick
y = np.array([35,45,55])
beta = np.linalg.inv(X.T @ X) @ X.T @ y
print(beta)                               # [25. 10.]  → ŷ = 25 + 10x

# the same with scikit-learn
from sklearn.linear_model import LinearRegression, Ridge, Lasso
model = LinearRegression().fit([[1],[2],[3]], y)
print(model.intercept_, model.coef_)      # 25.0 [10.]
print(model.predict([[4]]))               # [65.]  next exam score

Swap LinearRegression() for Ridge(alpha=1.0) or Lasso(alpha=0.1) and section 12 comes alive.

• Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani · An Introduction to Statistical Learning · chapter 3, Linear Regression
• Andrew Ng · CS229 Lecture Notes, Stanford · Part I, Linear Regression & the LMS algorithm
• scikit-learn documentation · Linear Models (LinearRegression, Ridge, Lasso, ElasticNet)
• Companion notes in this series: Gradient Descent · Logistic Regression