Perceptrons and Separating Hyperplanes

Definition In this lesson the two classes are coded $y = +1$ and $y = -1$. A linear classifier on feature vectors $\mathbf{x}$ in $\mathbb{R}^p$ has a weight vector $\mathbf{w}$ in $\mathbb{R}^p$ and an intercept $b$, computes the score

and predicts $\hat{y} = +1$ when $f(\mathbf{x}) \ge 0$ and $\hat{y} = -1$ when $f(\mathbf{x}) < 0$. For a labeled example $(\mathbf{x}, y)$ the product $y\,f(\mathbf{x})$ is the signed score. It is positive when the sign of the score agrees with the label, negative when it disagrees, and zero when the point lies on the boundary, whatever its label. Multiplying $\mathbf{w}$ and $b$ by the same positive number changes every score but no prediction.

Definition For $\mathbf{w} \ne \mathbf{0}$ the set of points $\mathbf{x}$ in $\mathbb{R}^p$ with score zero,

is a hyperplane, a flat set of dimension $p - 1$. It is a point when $p = 1$, a line when $p = 2$ and a plane when $p = 3$. The vector $\mathbf{w}$ is perpendicular to $H$ and points toward the side where the score is positive, and the signed distance from a point $\mathbf{x}$ to $H$ is $f(\mathbf{x})/\lVert \mathbf{w} \rVert_2$. Changing $b$ moves $H$ parallel to itself, and changing the direction of $\mathbf{w}$ turns it. The hyperplane separates a labeled training set $(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)$ if

for every $i$, so that every positive example lies strictly on the positive side and every negative example strictly on the negative side.

Definition A labeled training set is linearly separable if some $\mathbf{w}$ and $b$ satisfy $y_i(\mathbf{w}^{\top}\mathbf{x}_i + b) > 0$ for every example, that is, if a separating hyperplane exists. For a finite training set this holds exactly when some linear classifier makes no training mistakes under the rule above. Indeed, if every positive example scores at least $0$ and every negative example scores below $0$, raising $b$ by a positive amount smaller than the smallest absolute score of a negative example, or by any positive amount when there are no negative examples, makes every inequality strict. Separability is a property of the chosen features, so a set that is not separable in its original features can become separable once new features such as squares or products are added.

Definition Let $(\mathbf{w}, b)$ be the current parameters, $(\mathbf{x}, y)$ a training example with $y \in \{-1, +1\}$, and $\eta > 0$ a fixed step size. If the signed score satisfies $y(\mathbf{w}^{\top}\mathbf{x} + b) \le 0$, the perceptron update rule sets

and otherwise it leaves both unchanged. An update is triggered by every misclassified example and also by every example on the boundary, including a positive example with score exactly $0$, which the prediction rule labels correctly. Since $y^2 = 1$, the update changes the signed score of the same example to

where the $1$ comes from the intercept. Appending a constant feature $1$ to $\mathbf{x}$ and treating $b$ as its weight writes both updates as one.

Definition The perceptron is a training procedure for a linear classifier. Its inputs are training examples $(\mathbf{x}_i, y_i)$ with $y_i \in \{-1, +1\}$, a step size $\eta > 0$, starting values, usually $\mathbf{w} = \mathbf{0}$ and $b = 0$, an order of the examples and a maximum number of passes.

1. Visit the examples in order and apply the update rule to each one.
2. If a complete pass makes no update, stop. Every example then has a positive signed score, so the final hyperplane separates the training set.
3. Otherwise start another pass, unless the maximum number of passes has been reached. In that case stop and report that the procedure did not converge.

With zero starting values, every parameter after a given sequence of updates is $\eta$ times its value for step size $1$, so the step size changes no prediction and no update decision.

Definition Write each example in augmented form $\mathbf{z}_i = (\mathbf{x}_i, 1)$ in $\mathbb{R}^{p+1}$ and the parameters as $\boldsymbol{\theta} = (\mathbf{w}, b)$, so that the score is $\boldsymbol{\theta}^{\top}\mathbf{z}_i$. Suppose that

1. there is a number $R$ with $\lVert \mathbf{z}_i \rVert_2 \le R$ for every example, and
2. there are a unit vector $\mathbf{u}$ in $\mathbb{R}^{p+1}$ and a number $\gamma > 0$ with $y_i\,\mathbf{u}^{\top}\mathbf{z}_i \ge \gamma$ for every example.

Then the perceptron started at $\boldsymbol{\theta} = \mathbf{0}$, with any fixed step size $\eta > 0$ and the examples presented in any order, even one that changes from pass to pass, makes a total number of updates $M$ with

Every pass that does not stop contains an update, so the perceptron stops after finitely many passes at a separating hyperplane. For unit steps the proof follows two quantities. Each update adds $y_i\mathbf{z}_i$ to $\boldsymbol{\theta}$, which raises $\mathbf{u}^{\top}\boldsymbol{\theta}$ by at least $\gamma$. It changes $\lVert \boldsymbol{\theta} \rVert_2^2$ by $2y_i\boldsymbol{\theta}^{\top}\mathbf{z}_i + \lVert \mathbf{z}_i \rVert_2^2 \le R^2$, because updates happen only when $y_i\boldsymbol{\theta}^{\top}\mathbf{z}_i \le 0$. After $M$ updates the Cauchy-Schwarz inequality gives

and squaring gives the bound. For a finite training set the first condition always holds, and the second holds exactly when the set is linearly separable, with $\mathbf{u}$ a normalized separator and $\gamma$ its smallest signed score. For an unending stream of examples both conditions are real assumptions.