# linear classifier

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-07. [HTML](https://dictionaryofml.org/terms/linclass.html) · [typeset PDF](https://dictionaryofml.org/terms/linclass.pdf) · [LaTeX](https://dictionaryofml.org/terms/linclass.tex) · [Python demo](https://dictionaryofml.org/terms/linclass.py) · [notebook](https://dictionaryofml.org/terms/linclass.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

A linear classifier is a classifier whose decision regions are separated by hyperplanes. Each linear classifier is obtained by comparing the value of a linear hypothesis map against a threshold. For binary classification, the sign of the value can be used to determine the predicted label, and the absolute value measures the distance of the data point from the decision boundary. The model parameters of a linear classifier are the weight vector of the underlying hypothesis map and the threshold. They are learned by empirical risk minimization with different loss functions: logistic regression uses the logistic loss and the support vector machine the hinge loss. For multi-class classification, a linear classifier is characterized by several linear model hypothesis maps, one per label value, and the resulting decision regions are intersections of halfspaces.

## Definition

An aerial photograph of a wine-growing region is divided into small areas, and each area is to be classified as vineyard or not. Each area is a data point characterized by two features obtained from the photograph (Fig. 1). The label of each area indicates whether the area belongs to a vineyard ($y = 1$) or not ($y = -1$). The labeled areas form the training set. A linear classifier separates the two classes by a straight line, its decision boundary, which is fixed by a normal vector, and it classifies a new area by its signed distance from that line.

![Figure 1 of the entry linclass](https://dictionaryofml.org/terms/fig/linclass-fig1.svg)

*Figure 1: Scatterplot of data points, each characterized by two features and a binary label. The solid line is the decision boundary $h({\mathbf x}) = {\mathbf w}^{\top} {\mathbf x} + b = 0$ of a linear classifier learned from these data points, and the single-headed arrow is its normal vector ${\mathbf w}$. The double-headed arrow spans $|h({\mathbf x})| / \left\lVert {\mathbf w} \right\rVert_{2}$, the distance from the decision boundary of a new data point ${\mathbf x}$ (open square) that is not in the training set. Data generated by pythondemos/linclass.py*

A linear classifier is a classifier whose decision regions are separated by hyperplanes in $\mathbb{R}^{d}$ (Bishop, 2006, Sect. 4.1.1; Shalev-Shwartz and Ben-David, 2014, Sect. 9.1). For binary classification, with label space $\mathcal{Y} = \{-1, +1\}$, each linear classifier can be written as the thresholding rule $\widehat{y} =
\operatorname{sign}(h({\mathbf x}))$ with the hypothesis

$$
h({\mathbf x}) = {\mathbf w}^{\top} {\mathbf x}
+ b \text{.}
$$

The hypothesis map is parameterized by the weight vector ${\mathbf w} \in \mathbb{R}^{d} \setminus \{\mathbf{0}\}$ and the threshold $b \in \mathbb{R}$. A data point with feature vector ${\mathbf x}$ is classified as $\widehat{y} =
1$ if $h({\mathbf x}) \geq 0$ and as $\widehat{y} =
-1$ otherwise. The resulting decision boundary is the hyperplane

$$
\{ {\mathbf x} \in \mathbb{R}^{d} : {\mathbf w}^{\top}
{\mathbf x} + b = 0 \} \text{,}
$$

with normal vector ${\mathbf w}$. This boundary separates two halfspaces, which are the decision regions $\mathcal{R}_{1} = \{ {\mathbf x} : h({\mathbf x}) \geq 0 \}$ and $\mathcal{R}_{-1} = \{ {\mathbf x} : h({\mathbf x}) < 0 \}$.

Consider a feature vector ${\mathbf x}$ and any vector ${\mathbf x}'$ on the decision boundary, $h({\mathbf x}') = 0$. Subtracting ${\mathbf w}^{\top} {\mathbf x}' + b = 0$ from $h({\mathbf x})$ gives

$$
h({\mathbf x}) = {\mathbf w}^{\top}
\big( {\mathbf x} - {\mathbf x}' \big) \text{.}
$$

The Cauchy-Schwarz inequality bounds the right-hand side in magnitude by $\left\lVert {\mathbf w} \right\rVert_{2} \left\lVert {\mathbf x} -
{\mathbf x}' \right\rVert_{2}$ (Axler, 2024, Thm. 6.14). Every vector of the decision boundary is therefore at distance at least $|h({\mathbf x})| / \left\lVert {\mathbf w} \right\rVert_{2}$ from ${\mathbf x}$. That distance is attained by the orthogonal projection

$$
{\mathbf x}' = {\mathbf x} - \frac{h({\mathbf x})}
{\left\lVert {\mathbf w} \right\rVert_{2}^{2}} \, {\mathbf w} \text{.}
$$

The distance of ${\mathbf x}$ from the decision boundary is thus $|h({\mathbf x})| / \left\lVert {\mathbf w} \right\rVert_{2}$, and the hypothesis value $h({\mathbf x})$ is that distance multiplied by $\left\lVert {\mathbf w} \right\rVert_{2}$ (Bishop, 2006, Sect. 4.1.1; Hastie et al., 2009, Sect. 4.5, Eq. (4.40)). Fig. 1 illustrates the distance to the decision boundary for one data point.

The value $|h({\mathbf x})|$ is a measure of the noise tolerance at the feature vector ${\mathbf x}$. Perturbing ${\mathbf x}$ by a vector $\boldsymbol{\delta}$ changes the hypothesis value by ${\mathbf w}^{\top} \boldsymbol{\delta}$, which the Cauchy-Schwarz inequality bounds in magnitude by $\left\lVert {\mathbf w} \right\rVert_{2} \left\lVert \boldsymbol{\delta} \right\rVert_{2}$. The sign of $h({\mathbf x})$, and with it the prediction, is therefore unchanged by every perturbation with $\left\lVert \boldsymbol{\delta} \right\rVert_{2} < |h({\mathbf x})|
/ \left\lVert {\mathbf w} \right\rVert_{2}$.

Multiplying $h({\mathbf x})$ by the label $y$ gives the margin. A positive margin means that the data point is correctly classified, a negative margin that it is misclassified, and a zero margin that it lies on the decision boundary, where the rule above assigns $\widehat{y} = 1$.

The model parameters $({\mathbf w}, b)$ are learned from a training set $\mathcal{D}^{(\rm train)} = \{ ({\mathbf x}^{(r)},
y^{(r)}) \}_{r = 1}^{m}$ by empirical risk minimization. Using the 0/1 loss results in an objective function that is piecewise constant, and minimizing it is computationally hard in general (Shalev-Shwartz and Ben-David, 2014, Sect. 9.1). Practical methods replace the 0/1 loss by a convex loss of the margin: logistic regression uses the logistic loss and the support vector machine uses the hinge loss. For a linearly separable training set and a sufficiently small regularization parameter $\alpha$, the support vector machine learns the linear classifier whose smallest margin is largest (Shalev-Shwartz and Ben-David, 2014, Sect. 15.1, Eq. (15.1)). Both learn the model parameters of a linear classifier by minimizing a convex objective function: gradient descent minimizes the smooth objective function of logistic regression, and subgradient descent the non-smooth objective function of the support vector machine (Murphy, 2012, Sect. 8.3.2; Shalev-Shwartz and Ben-David, 2014, Sect. 14.2.3, Example 14.2).

For multi-class problems, with label space $\mathcal{Y} = \{1,
\ldots, K\}$ and $K > 2$, a linear classifier uses one linear model hypothesis $g_{c}({\mathbf x}) = \big( {\mathbf w}^{(c)}
\big)^{\top} {\mathbf x} + b^{(c)}$ per label value $c \in \mathcal{Y}$ and predicts the value with the largest score, $\widehat{y} = \mathop{\mathrm{arg\,max}}_{c \in \mathcal{Y}}
g_{c}({\mathbf x})$. The decision region $\mathcal{R}_{c}$ is then an intersection of $K - 1$ halfspaces and is therefore a convex set. The border between two decision regions $\mathcal{R}_{c}$ and $\mathcal{R}_{c'}$ lies in the hyperplane on which the two scores agree (Bishop, 2006, Sect. 4.1.2, Eq. (4.10)). The resulting partition of the feature space is shown in Fig. 2 for a linear classifier with $K = 3$ classes.

![Figure 2 of the entry linclass](https://dictionaryofml.org/terms/fig/linclass-fig2.svg)

*Figure 2: A linear classifier for $K = 3$ label values partitions the feature space $\mathbb{R}^{2}$ into three decision regions $\mathcal{R}_{1}, \mathcal{R}_{2}, \mathcal{R}_{3}$. Each border lies in the hyperplane on which the two competing scores agree, and each decision region is an intersection of halfspaces and therefore convex*

A linear classifier can be generalized to allow for non-linear decision boundaries by using a feature transformation. Applying a feature transformation $\phi:
\mathbb{R}^{d} \to \mathbb{R}^{d'}$ first and a linear classifier to $\phi({\mathbf x})$ afterwards gives a decision boundary that is a hyperplane in $\mathbb{R}^{d'}$ but non-linear in the original feature space. A kernel method constructs such a feature transformation from a kernel, and a deep net uses its first layers as a trainable feature transformation (Bishop and Bishop, 2024, Sect. 6.3.3; Schölkopf and Smola, 2002, Sect. 2.2).

**See also:** classifier, [binary classification](https://dictionaryofml.org/terms/binclass.html), [decision boundary](https://dictionaryofml.org/terms/decisionboundary.html), [decision region](https://dictionaryofml.org/terms/decisionregion.html), hyperplane, halfspace, linear model, margin, [logistic regression](https://dictionaryofml.org/terms/logreg.html), [support vector machine](https://dictionaryofml.org/terms/svm.html), [empirical risk minimization](https://dictionaryofml.org/terms/erm.html), $\bf 0/1$ loss, feature transformation.

## References

- Bishop (2006). Pattern Recognition and Machine Learning. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-45528-0>
- Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. *Cambridge Univ. Press*. <https://doi.org/10.1017/cbo9781107298019>
- Axler (2024). Linear Algebra Done Right. *Springer*. <https://doi.org/10.1007/978-3-031-41026-0>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Murphy (2012). Machine Learning: A Probabilistic Perspective. *MIT Press*.
- Bishop and Bishop (2024). Deep Learning: Foundations and Concepts. *Springer Nature*. <https://doi.org/10.1007/978-3-031-45468-4>
- Schölkopf and Smola (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. *MIT Press*. <https://doi.org/10.7551/mitpress/4175.001.0001>

## Cite this entry

```bibtex
@misc{dictml_linclass,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {linear classifier},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-11},
  url = {https://dictionaryofml.org/terms/linclass.html}
}
```