Classification predicts a discrete label from the same linear score $\theta^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.

- Read a linear classifier as a separating hyperplane whose score tells the side, making prediction one dot product.

- Situate the classical methods by their assumption (Gaussian or none) and their fit (closed form or gradient descent).

- Classify by least squares, binary and multiclass, and see where it breaks.

- Train the perceptron from its criterion, and know its convergence guarantee and its limits.

- Distinguish batch from stochastic gradient descent, and know that fancier optimizers exist.

- Fit logistic regression by gradient descent on the cross-entropy, binary and multiclass.

- Regularize any of these fits with a penalty, the maximum a posteriori view.

A linear classifier assigns the class from the sign of the linear score, and the set of inputs scoring zero is the decision boundary:

$$\boxed{ h_\theta(x) = \mathrm{sign}(\theta^T x), \qquad \theta^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 $\theta = (-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.

The classical methods fit that hyperplane, and they split cleanly by what they assume about the data and how they are solved.

| Method | Assumption on the data | How it is fitted |

| --- | --- | --- |

| Least squares | Gaussian-shaped classes | closed form (matrix inversion) |

| Perceptron | none | gradient descent |

| Logistic regression | none | gradient descent |

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 other two assume nothing and pay with iterative optimization.

Code the two classes as $y \in \{-1, +1\}$, treat them as regression targets, and everything from [Linear regression](/en/Machine%20Learning/04%20Linear%20regression) applies verbatim, closed form included:

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

For $K > 2$ classes, code each label as a one-hot row of $Y \in \mathbb{R}^{m \times K}$ and reuse the multiple-output regression of [Linear regression](/en/Machine%20Learning/04%20Linear%20regression), predicting the class with the highest score:

$$\boxed{ W = (X^T X)^{-1}X^T Y, \qquad \hat{y} = \arg\max_k \; (W^T x)_k }$$

It can work, but the squared loss penalizes large scores even deep on the correct side, so the points least in doubt pull on the boundary. That is the Gaussian assumption at work: least squares treats the labels as Gaussian targets, and data far from that story breaks it.


The first assumption-free method takes the definition of a linear classifier at face value, a dot product followed by a hard activation, the historical neuron:

$$\boxed{ h_\theta(x) = \mathrm{sign}(\theta^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)}\,\theta^T x^{(i)} < 0$, so over the set $\mathcal{M}$ of misclassified points:

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

always positive and piecewise linear. Minimizing it introduces the workhorse of everything in this course that lacks a closed form, gradient descent: repeatedly step the parameters against the gradient of the loss, scaled by a learning rate $\alpha > 0$:

$$\boxed{\,\theta \leftarrow \theta - \alpha\,\nabla_\theta E(\theta)\,}$$

The batch variant computes the gradient over the whole training set before each step, a smooth descent that reads every example every time. The stochastic variant (SGD) steps on one example at a time, cheap and noisy, and is the default on large datasets. If $\alpha$ is too large the iterates can diverge, if too small convergence crawls.

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

On a single misclassified example the gradient of the criterion is $-y^{(i)} x^{(i)}$, so the stochastic step is the perceptron update: on a mistake,

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

and no update otherwise. In the $\{0, 1\}$ coding this is the residual-times-input update $\theta_j \leftarrow \theta_j + \alpha\,(y^{(i)} - h_\theta(x^{(i)}))\,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 }$$

The network view extends naturally: one score neuron per class, and an argmax where the binary perceptron had a sign. Gathering the $\theta_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.


A worked example with $k = 3$ classes and the input $x = (1.1, -2.0)$, augmented with $x_0 = 1$:

$$ W^T x = \begin{bmatrix} -2 & -4 & 1 \\ -4 & 2 & 4 \\ -6 & 4 & -5 \end{bmatrix}\begin{bmatrix} 1 \\ 1.1 \\ -2.0 \end{bmatrix} = \begin{bmatrix} -8.4 \\ -9.8 \\ 8.4 \end{bmatrix} $$

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

If the data is linearly separable the perceptron converges in a finite number of updates, otherwise the weights oscillate forever. And since the criterion is zero on every separating hyperplane, all of them count as "optimal", including those that graze the data.

*Remark:* three upgrades fix these limits, and each one opens a module. A smooth activation and loss give logistic regression, next section. Margins and basis functions lead to the [Support Vector Machine](/en/Machine%20Learning/07%20Support%20Vector%20Machines). 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\}$):

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


*Remark:* the sigmoid is not an arbitrary squashing choice. Writing the posterior with Bayes' rule gives $p(C_1 \mid x) = 1/(1 + e^{-a})$ with $a = \ln \frac{p(x \mid C_1)\,p(C_1)}{p(x \mid C_0)\,p(C_0)}$, so a well-trained logistic output is exactly a posterior probability.

The likelihood of Bernoulli labels, taken through $-\log$, gives the cross-entropy loss:

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

Unlike least squares, this loss has no closed-form minimizer: the sigmoid makes the stationarity equations transcendental, so the fit falls to the same gradient descent as the perceptron. Differentiating the cross-entropy through the sigmoid rewards the effort: almost everything cancels and the gradient collapses to 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:* unlike the perceptron, the gradient involves every training point, not only the misclassified ones: each point pulls in proportion to its residual $\phi^{(i)} - y^{(i)}$. That is what makes logistic regression more stable than the perceptron and usable on non-separable data.


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

With one-hot labels the loss is the categorical cross-entropy $L = -\sum_i \log p(y^{(i)} \mid x^{(i)})$, whose gradient keeps the same residual-times-input form.

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

Nothing pins down the scale of $\theta$: doubling it moves no perceptron boundary and only sharpens the probabilities of logistic regression, and different weight vectors can produce identical scores. The maximum a posteriori recipe of [Linear regression](/en/Machine%20Learning/04%20Linear%20regression) applies verbatim, adding a penalty to whichever loss is being minimized:

$$\boxed{ J_\lambda(\theta) = \sum_{i=1}^{m} L\!\left(h_\theta(x^{(i)}),\,y^{(i)}\right) + \lambda\,\Omega(\theta), \qquad \Omega(\theta) = \lVert \theta \rVert_2^2 \ \text{or} \ \lVert \theta \rVert_1 }$$

For the cross-entropy with the L2 penalty, the gradient simply gains a pull toward zero, $\sum_i (\phi^{(i)} - y^{(i)})\,x^{(i)} + 2\lambda\theta$.

*Remark:* libraries expose exactly this menu, a loss plus a penalty (scikit-learn's `SGDClassifier` takes a `loss` and a `penalty` argument). The strength $\lambda$ is chosen by the validation of [General concepts](/en/Machine%20Learning/02%20General%20concepts), and the lasso's selecting behaviour is covered in [Linear regression](/en/Machine%20Learning/04%20Linear%20regression).

The assumption-free methods share one update, the residual times the input:

| Model | Activation | Update (one example) |

| --- | --- | --- |

| Perceptron | step | $\theta_j \leftarrow \theta_j + \alpha\,(y - h_\theta(x))\,x_j$ (mistakes only) |

| Linear regression | identity | $\theta_j \leftarrow \theta_j + \alpha\,(y - \theta^T x)\,x_j$ |

| Logistic regression | sigmoid or softmax | $\theta_j \leftarrow \theta_j + \alpha\,(y - \phi)\,x_j$ |

*Remark:* only the activation differs (step, identity, sigmoid or softmax). The Deep Learning course picks up exactly this thread, stacking such units into layers.

And the losses at a glance:

| Loss | Penalizes | Used by |

| --- | --- | --- |

| Perceptron criterion | misclassified points only | perceptron |

| Hinge $\max(0,\,1 - y\,\theta^T x)$ | mistakes and small margins | [SVM](/en/Machine%20Learning/07%20Support%20Vector%20Machines) |

| Cross-entropy | every point, by its residual | logistic regression |

---

Next: [Multilayer neural networks](/en/Machine%20Learning/06%20Multilayer%20neural%20networks) · [Course overview](/en/Machine%20Learning)