3. Linear models
Linear models predict from a linear score \(\theta^T x\). This module covers linear regression (continuous targets), logistic regression (binary classification), and the generalized linear model framework that unifies both through the exponential family. Each model is fit by maximum likelihood and shares the same gradient-based update.
Objectives
- Define the linear hypothesis and fit \(\theta\) by the LMS update or the closed-form normal equation.
- See why least squares is the maximum-likelihood estimate under Gaussian noise.
- Map the linear score through the sigmoid and fit it by gradient ascent or Newton's method.
- Classify with the perceptron and know when its learning rule converges.
- Recognize the exponential-family form and build a GLM from its three assumptions.
- Recover linear, logistic, and softmax regression as special cases.
3.1 Linear regression
3.1.1 Hypothesis
The hypothesis is linear in the augmented input \(x \in \mathbb{R}^{n+1}\) with \(x_0 = 1\) and parameters \(\theta \in \mathbb{R}^{n+1}\):
\[\boxed{ h_\theta(x) = \theta^T x }\]3.1.2 Cost function
The cost is defined as half the sum of squared residuals over the \(m\) examples:
\[\boxed{ J(\theta) = \tfrac{1}{2}\sum_{i=1}^{m}\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2 }\]3.1.3 LMS update
Gradient descent on \(J\) gives the least-mean-squares (Widrow-Hoff) update, applied per example \((x^{(i)}, y^{(i)})\):
\[\boxed{ \theta_j \leftarrow \theta_j + \alpha\left(y^{(i)} - h_\theta(x^{(i)})\right)x_j^{(i)} }\]with learning rate \(\alpha > 0\).
| variant | update rule | per step | use when |
|---|---|---|---|
| Batch GD | sum over all \(m\) examples | \(O(mn)\) | \(m\) small to moderate |
| Stochastic GD (SGD) | one example at a time | \(O(n)\) | \(m\) large, streaming |
3.1.4 Normal equation
Setting \(\nabla_\theta J(\theta) = 0\) gives a closed-form solution from the design matrix \(X\) and target vector \(y\):
\[\boxed{ \theta = (X^T X)^{-1}X^T y }\]Remark: the normal equation needs no learning rate and no iteration, but inverting \(X^T X\) costs \(O(n^3)\), so for large \(n\) the iterative LMS update is preferred.
3.1.5 Probabilistic interpretation
Assume \(y^{(i)} = \theta^T x^{(i)} + \varepsilon^{(i)}\) with i.i.d. Gaussian noise \(\varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2)\). Maximizing the log-likelihood then coincides with minimizing the least-squares cost:
\[\boxed{ \arg\max_\theta \ell(\theta) = \arg\min_\theta J(\theta) }\]Remark: this is why least squares is a principled objective and not merely a convenient one.
Least squares fits the line that minimizes the squared residuals (grey segments).
3.2 Logistic regression
3.2.1 Sigmoid
The sigmoid (logistic) function squashes a raw score \(z \in \mathbb{R}\) into a probability:
\[\boxed{ g(z) = \frac{1}{1 + e^{-z}} \in (0, 1) }\]Its derivative has the convenient form \(g'(z) = g(z)\left(1 - g(z)\right)\).
3.2.2 Model
The hypothesis outputs the probability of the positive class, with \(\phi\) the predicted probability:
\[\boxed{ \phi = h_\theta(x) = g(\theta^T x) = p(y = 1 \mid x; \theta) }\]Labels are \(y \in \{0, 1\}\), so the conditional law is Bernoulli:
\[\boxed{ p(y \mid x; \theta) = \phi^{y}(1 - \phi)^{1 - y} }\]3.2.3 Log-likelihood
Over \(m\) i.i.d. examples the log-likelihood is the negative cross-entropy summed over the data:
\[\boxed{ \ell(\theta) = \sum_{i=1}^{m}\left[ y^{(i)}\log \phi^{(i)} + (1 - y^{(i)})\log(1 - \phi^{(i)}) \right] }\]with \(\phi^{(i)} = h_\theta(x^{(i)})\).
3.2.4 Gradient ascent
Maximizing \(\ell\) by gradient ascent gives the same form as the LMS update:
\[\boxed{ \theta_j \leftarrow \theta_j + \alpha\left(y^{(i)} - h_\theta(x^{(i)})\right)x_j^{(i)} }\]Remark: the update matches linear regression in form, even though \(h_\theta\) is now the sigmoid. This is no coincidence, both are generalized linear models.
3.2.5 Newton's method
Newton's method converges faster near the optimum. In one dimension:
\[\boxed{ \theta \leftarrow \theta - \frac{\ell'(\theta)}{\ell''(\theta)} }\]In the vector case it uses the Hessian \(H\) of \(\ell\):
\[\boxed{ \theta \leftarrow \theta - H^{-1}\nabla_\theta \ell(\theta) }\]Remark: logistic regression has no closed-form solution for \(\theta\), so it is always fit iteratively (gradient ascent or Newton).
Left: the sigmoid maps scores into the interval (0,1). Right: the decision boundary and predicted probability.
3.3 Perceptron
The perceptron is the original linear classifier. It keeps the linear score \(\theta^T x\) of logistic regression but replaces the sigmoid with a hard threshold, so the output is a class label rather than a probability. Labels are \(y \in \{0, 1\}\).
3.3.1 Activation and hypothesis
The activation is the step function:
\[\boxed{ g(z) = \begin{cases} 1 & \text{if } z \ge 0 \\ 0 & \text{otherwise} \end{cases} }\]and the hypothesis applies it to the linear score:
\[\boxed{ h_\theta(x) = g(\theta^T x) }\]3.3.2 Learning rule
The perceptron is trained online, one example at a time, and corrects \(\theta\) only on a misclassified point:
\[\boxed{ \theta_j \leftarrow \theta_j + \alpha\left(y^{(i)} - h_\theta(x^{(i)})\right)x_j^{(i)} }\]Remark: this is the same form as the LMS update and the logistic gradient-ascent update. Only the activation \(g\) differs (identity, sigmoid, step). When the prediction is right the factor \(y^{(i)} - h_\theta(x^{(i)})\) is zero, so correctly classified points leave \(\theta\) unchanged.
The perceptron finds one separating hyperplane. It is not necessarily the maximum-margin one the SVM will choose.
3.3.3 Convergence
| data | behaviour |
|---|---|
| linearly separable | converges in a finite number of updates |
| not separable | never converges, the weights keep oscillating |
Remark: the perceptron stops at the first hyperplane that separates the data, usually not the one with the widest margin. This gap motivates the support vector machine (which maximizes the margin) and, stacked into layers, the neural network (a perceptron is a single unit).
3.4 Generalized linear models
3.4.1 Exponential family
A distribution is in the exponential family if its density can be written with natural parameter \(\eta\), sufficient statistic \(T(y)\), log-partition \(a(\eta)\), and base measure \(b(y)\):
\[\boxed{ p(y; \eta) = b(y)\exp\left(\eta\, T(y) - a(\eta)\right) }\]3.4.2 GLM assumptions
A GLM rests on three choices. The response is in the exponential family, the natural parameter is linear in the input, and the prediction is the expected sufficient statistic:
\[\boxed{ \eta = \theta^T x }\] \[\boxed{ h_\theta(x) = \mathbb{E}\left[T(y) \mid x; \theta\right] }\]3.4.3 Family table
| Distribution | \(\eta\) | \(T(y)\) | \(a(\eta)\) | \(b(y)\) |
|---|---|---|---|---|
| Bernoulli | \(\log\dfrac{\phi}{1-\phi}\) | \(y\) | \(\log(1 + e^{\eta})\) | \(1\) |
| Gaussian (\(\sigma^2 = 1\)) | \(\mu\) | \(y\) | \(\tfrac{1}{2}\eta^2\) | \(\dfrac{1}{\sqrt{2\pi}}e^{-y^2/2}\) |
| Poisson | \(\log\lambda\) | \(y\) | \(e^{\eta}\) | \(\dfrac{1}{y!}\) |
| Geometric | \(\log(1-\phi)\) | \(y\) | \(\log\dfrac{e^{\eta}}{1 - e^{\eta}}\) | \(1\) |
Remark: for the Bernoulli, \(\eta\) is the log-odds and its inverse is the sigmoid, \(\phi = g(\eta)\). This is why logistic regression has the form it does.
3.4.4 Softmax regression
For multiclass labels \(y \in \{1, \dots, k\}\) the GLM gives softmax regression, with one parameter vector \(\theta_k\) per class:
\[\boxed{ p(y = k \mid x; \theta) = \frac{\exp(\theta_k^T x)}{\sum_{j}\exp(\theta_j^T x)} }\]3.4.5 GLM recipe
graph TD A["pick a response distribution"] --> B["write it in exponential-family form"] B --> C["set natural parameter eta linear in x"] C --> D["prediction is expected sufficient statistic"] D --> E["fit theta by maximum likelihood"]
Linear models, including the perceptron, settle for any boundary that separates the classes. The next part asks for the best one: the support vector machine maximizes the margin.