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.

- 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.

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.

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)} }$$


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 }$$

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.

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] }$$


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 |

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.

---

Next: [Regularization and high-dimensional inference](/en/Machine%20Learning/07%20Regularization%20and%20high-dimensional%20inference) · [Course overview](/en/Machine%20Learning)