Classification predicts a discrete label from the same linear score $w^T x$. This module surveys the classical linear classifiers as one menu: least squares, which assumes Gaussian-shaped classes and admits a closed form, and the perceptron and logistic regression, which assume nothing about the distribution and are fitted by gradient descent. Regularization closes the module.

$$\boxed{ h_w(x) = \mathrm{sign}(w^T x), \qquad w^T x = 0 \ \text{is the boundary} }$$

The boundary is a hyperplane: a line with two features, a plane with three. The sign of the score says on which side of the hyperplane the input falls, and its magnitude how far from the boundary it sits. With $w = (-4, 1, 2)$ (bias first, on the augmented input), the point $x = (3, 2)$ scores $-4 + 3 + 4 = 3$ and falls in front of the hyperplane, while $x = (1, 1)$ scores $-4 + 1 + 2 = -1$ and falls behind it.


*Remark:* two practical advantages follow. Once training is done the training set can be thrown away, and predicting costs a single dot product.

$$\boxed{ w = (X^T X)^{-1}X^T y, \qquad h_w(x) = \mathrm{sign}(w^T x) }$$

$$\boxed{ h_w(x) = \mathrm{sign}(w^T x), \qquad y \in \{-1, +1\} }$$

Fitting needs a loss, and counting mistakes does not work: the count is piecewise constant, so its gradient is zero almost everywhere. The perceptron criterion instead penalizes each misclassified point by how far it sits on the wrong side. A mistake means $y^{(i)}\,w^T x^{(i)} < 0$, so over the set $\mathcal{M}$ of misclassified points:

$$\boxed{ E(w) = -\sum_{i \in \mathcal{M}} y^{(i)}\, w^T x^{(i)} }$$

always positive and piecewise linear.

*Remark:* fancier optimizers exist, momentum, Adam and their cousins, refinements of this same rule that matter for deep networks ([Optimization](/en/Deep%20Learning/03%20Optimization) in the Deep Learning course). Everything in this module needs only the plain version.

$$\boxed{ w \leftarrow w + \alpha\, y^{(i)} x^{(i)} }$$

and no update otherwise. In the $\{0, 1\}$ coding this is the residual-times-input update $w_j \leftarrow w_j + \alpha\,(y^{(i)} - h_w(x^{(i)}))\,x_j^{(i)}$.

With $k$ classes, keep one weight vector $w_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 w_c^T x, \qquad w_{y} \mathrel{+}= \alpha x, \quad w_{\hat{y}} \mathrel{-}= \alpha x }$$

The network view extends naturally: one score neuron per class, and an argmax where the binary perceptron had a sign. Gathering the $w_c$ as the columns of a matrix $W \in \mathbb{R}^{(n+1) \times k}$, one product $W^T x$ computes every score at once, and the scores carve the input space into $k$ regions, each claimed by the class whose score is largest.

The third score wins, so the input is assigned to class 3. Reading off the third row, that score is $w_3^T x = -6 + 4 \times 1.1 + (-5) \times (-2.0) = 8.4$.

*Remark:* two upgrades fix these limits, and each one opens a module. A smooth activation and loss give logistic regression, next section. Stacking neurons into layers gives [multilayer neural networks](/en/Machine%20Learning/06%20Multilayer%20neural%20networks), the starting point of the Deep Learning course.

Logistic regression keeps the neuron but replaces the hard step with the smooth sigmoid, so the output is the probability of the positive class ($y \in \{0, 1\}$). It is still written $\hat{y}$, but the estimate of the label is now soft: the perceptron's $\hat{y}$ was a hard class, logistic regression's is a probability, and thresholding it at $\tfrac{1}{2}$ turns it back into a class whenever one is needed:

$$\boxed{ \hat{y} = p(y = 1 \mid x; w) = \sigma(w^T x) = \frac{1}{1 + e^{-w^T x}} }$$

$$\boxed{ L(w) = -\sum_{i=1}^{m}\left[ y^{(i)}\log \hat{y}^{(i)} + (1 - y^{(i)})\log(1 - \hat{y}^{(i)}) \right] }$$

$$\boxed{ w_j \leftarrow w_j - \alpha \sum_{i=1}^{m}\left(\hat{y}^{(i)} - y^{(i)}\right)x_j^{(i)} }$$

$$\sigma'(z) = \frac{e^{-z}}{\left(1 + e^{-z}\right)^2} = \frac{1}{1 + e^{-z}} \cdot \frac{e^{-z}}{1 + e^{-z}} = \sigma(z)\left(1 - \sigma(z)\right)$$


| output | one probability $\hat{y}$ | a distribution over $k$ classes |

<details class="proof">

Dividing numerator and denominator by $e^{w_1^T x}$ leaves

$$p(y = 1 \mid x; w) = \frac{1}{1 + e^{-(w_1 - w_0)^T x}} = \sigma\!\left((w_1 - w_0)^T x\right)$$

the sigmoid applied to the difference of the scores. Only the difference $w = w_1 - w_0$ matters (the general fact behind this: shifting every $w_c$ by the same vector leaves the softmax unchanged), so a single weight vector suffices, exactly the binary model this section started from. Read in the other direction, this is the recipe for the generalization: give each class its own score $w_c^T x$, exponentiate to make the scores positive, normalize so they sum to one, and the two-class case collapses back to one sigmoid. $\blacksquare$

The classical methods all fit the same hyperplane, and they split cleanly by what they assume about the data and how they are solved: least squares inherits the closed-form comfort of [Linear regression](/en/Machine%20Learning/04%20Linear%20regression) and pays for it with a distributional assumption, the perceptron and logistic regression assume nothing and pay with iterative optimization. Algorithm by algorithm, the formulas that define each one:

**Least squares**, the one with an assumption and a closed form:

| | Formula |

**The perceptron**, mistake-driven and assumption-free:

| | Formula |