ConceptDBISAI-written · not yet proofread

Linear Classifier

Also Decision Boundary · Linear Separability

A binary classifier that assigns x ∈ ℝ^d to one class iff w·x > b, so that the two classes are separated by the hyperplane H = {x | w·x = b}.

Formula#

Distance of a point to the hyperplane:

\operatorname{dist}(x, H) = \frac{|w \cdot x - b|}{\|w\|}, \qquad \|w\| = \sqrt{\textstyle\sum_i w_i^2}.

ProofDerivation

$w$ is orthogonal to $H$ : for $y, y' \in H$ , $w \cdot (y - y') = b - b = 0$ . Write $x = y + t \cdot \frac{w}{\|w\|}$ with $y \in H$ the foot of the perpendicular and $|t| = \operatorname{dist}(x, H)$ . Then $w \cdot x - b = (w \cdot y - b) + t \frac{w \cdot w}{\|w\|} = t \, \|w\|$ , so $|t| = |w \cdot x - b| / \|w\|$ .

Bias as an extra component. Appending a constant $1$ to $x$ and $-b$ to $w$ gives $w \cdot x - b = (w, -b) \cdot (x, 1)$ , a hyperplane through the origin in $\mathbb{R}^{d+1}$ . Logistic Regression uses this form (“bias term already included in $X$ ”).

Properties#

$w$ is the normal vector of $H$ ; the sign of $w \cdot x - b$ tells on which side $x$ lies, $\frac{w \cdot x - b}{\|w\|}$ is the signed distance.
$H$ contains the origin iff $b = 0$ , since $w \cdot 0 = 0$ (exam WS 22/23, Task 3.2).
Scaling invariance: $(\lambda w, \lambda b)$ for $\lambda > 0$ defines the same classifier and the same $H$ .
XOR is not linearly separable. Points $(1,1), (2,2)$ in class 0 and $(2,1), (1,2)$ in class 1: a separating $(w, b)$ would need $w \cdot (2,1) > b$ and $w \cdot (1,2) > b$ , so $w \cdot (3,3) > 2b$ , and also $w \cdot (1,1) \le b$ , $w \cdot (2,2) \le b$ , so $w \cdot (3,3) \le 2b$ . Contradiction. Hence no linear classifier reaches precision and recall $1$ on both classes (exam WS 22/23, Task 3.3).
Classifiers that are linear:
- the Perceptron learns $(w, b)$ directly and finds a separating one if the data is linearly separable;
- Logistic Regression predicts the positive class iff $\sigma(w \cdot x) > 1/2 \iff w \cdot x > 0$ (Sigmoid);
- the Naive Bayes Classifier with two classes is linear in the word-count vector, with $w_i = \log(p_{w_i X}/p_{w_i Y})$ and $b = \log(p_Y/p_X)$ .

Example#

Sources#

Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
Exam WS 21/22, Task 5.2 (not published) (distance to a plane)
Exam WS 22/23, Task 3.2 (not published) (origin, distance), Task 3.3 (not published) (XOR, $F_1$ )
Exam WS 16/17, Task 4.3–4.4 (not published) ( $w$ and $b$ of Naive Bayes)
Exam WS 15/16, Task 4 (not published) (convention $w \cdot x - b$ )

Connections

Mentioned in inline links5

Logistic Regression
Bias. A bias is included by a constant component $1$ in every $x$ (then $w$ contains the bias weight), see Linear Classifier. §
It is a Linear Classifier: predicting class 1 iff $\sigma(w \cdot x) > 1/2$ is the same as $w \cdot x > 0$ , because $\sigma$ is strictly increasing with $\sigma(0) = 1/2$ . Unlike the Perceptron, it also outputs a probability, and the updat… §
Naive Bayes Classifier
Naive Bayes is a Linear Classifier. For two classes $X, Y$ it predicts $X$ iff §
Perceptron
Given training points $x_1, \dots, x_m \in \mathbb{R}^d$ with labels $y_i \in \{+1, -1\}$ , the Perceptron algorithm learns a Linear Classifier $(w, b)$ that predicts $+1$ iff $w \cdot x - b > 0$ : §
Linear Classifiers and Logistic Regression
Linear Classifier — hyperplane $\{w \cdot x = b\}$ , distance formula, linear separability, XOR §
Same decision rule, different learning: all models below classify by the sign of $w \cdot x - b$ (Linear Classifier). §
Naive Bayes Classification
Naive Bayes is linear. With two classes the prediction is $w \cdot x > b$ for word counts $x$ (Linear Classifier); this links the topic to Linear Classifiers and Logistic Regression, where the same decision rule is learned directly instead… §

Search in these mentions →