6. Linear classification
Classification predicts a discrete label from the same linear score \(\theta^T x\). This module starts from the idea of treating classification as regression, then builds the two classical linear classifiers: the perceptron, binary and multiclass, and logistic regression, binary with the sigmoid and multiclass with the softmax, all trained by gradient descent on the cross-entropy loss.
Objectives
- See why regressing the labels directly is a poor classifier, and how a squashing function fixes it.
- Classify with the perceptron, binary and multiclass, and know when it converges.
- Fit binary logistic regression with the sigmoid and the cross-entropy loss.
- Extend to many classes with the softmax, and relate the sigmoid and the softmax.
- Train these models by gradient descent.
6.1 Classification as a regression problem
One could fit least squares to the labels \(y \in \{0, 1\}\) directly, but the linear output is unbounded, is pulled around by outliers, and does not read as a probability. The fix is to keep the linear score and pass it through a squashing function that maps it to a class or a probability. The rest of the module is two choices of that function.
6.2 The perceptron
6.2.1 Binary perceptron
The perceptron passes the score through a hard step, so the output is a class label:
\[\boxed{ h_\theta(x) = g(\theta^T x), \quad g(z) = \begin{cases} 1 & \text{if } z \ge 0 \\ 0 & \text{otherwise} \end{cases} }\]It is trained online, correcting \(\theta\) only on a misclassified point:
\[\boxed{ \theta_j \leftarrow \theta_j + \alpha\left(y^{(i)} - h_\theta(x^{(i)})\right)x_j^{(i)} }\]
The perceptron finds one separating hyperplane, not necessarily the maximum-margin one the support vector machine will choose.
6.2.2 Multiclass perceptron
With \(k\) classes, keep one weight vector \(\theta_c\) per class and predict the highest-scoring one. On a mistake, reward the true class and penalize the predicted one:
\[\boxed{ \hat{y} = \arg\max_c \theta_c^T x, \qquad \theta_{y} \mathrel{+}= \alpha x, \quad \theta_{\hat{y}} \mathrel{-}= \alpha x }\]6.2.3 Convergence
If the data is linearly separable the perceptron converges in a finite number of updates, otherwise the weights oscillate forever.
Remark: the perceptron stops at the first separating hyperplane, which motivates the support vector machine (widest margin) and, stacked into layers, the neural network. A perceptron is a single unit, and stacked into layers it becomes a neural network, the starting point of the Deep Learning course.
6.3 Logistic regression, binary
Logistic regression replaces the hard step with the smooth sigmoid, so the output is the probability of the positive class:
\[\boxed{ \phi = p(y = 1 \mid x; \theta) = g(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}} }\]It is fit by minimizing the cross-entropy loss, the negative log-likelihood of the Bernoulli labels:
\[\boxed{ L(\theta) = -\sum_{i=1}^{m}\left[ y^{(i)}\log \phi^{(i)} + (1 - y^{(i)})\log(1 - \phi^{(i)}) \right] }\]
Left: the sigmoid maps any score into the interval (0, 1). Right: the decision boundary and the predicted probability.
6.4 Logistic regression, multiclass
For \(k\) classes the sigmoid generalizes to the softmax, one weight vector per class, normalized into a distribution:
\[\boxed{ p(y = c \mid x; \theta) = \frac{\exp(\theta_c^T x)}{\sum_{j=1}^{k}\exp(\theta_j^T x)} }\]trained by the categorical cross-entropy \(L = -\sum_i \log p(y^{(i)} \mid x^{(i)})\).
| sigmoid | softmax | |
|---|---|---|
| classes | 2 | \(k\) |
| output | one probability \(\phi\) | a distribution over \(k\) classes |
| relation | the \(k = 2\) softmax reduces to the sigmoid | generalizes the sigmoid |
6.5 Gradient descent
Both models are fit by gradient descent on the cross-entropy. The gradient takes the same clean form as the least-squares update, the residual times the input:
\[\boxed{ \theta_j \leftarrow \theta_j - \alpha \sum_{i=1}^{m}\left(\phi^{(i)} - y^{(i)}\right)x_j^{(i)} }\]Remark: the perceptron, linear regression, and logistic regression share one update, the residual times the input. Only the activation differs (step, identity, sigmoid or softmax). The Deep Learning course picks up exactly this thread, stacking such units into layers.
With linear models covered, the next module controls their complexity: regularization and inference when the regressors are many.
Next: Regularization and high-dimensional inference · Course overview