The perceptron is a fundamental binary linear classifier introduced by (Rosenblatt 1958). It maps an input vector $\mathbf{x}\in {\mathbb{R}}^n$ to an output $y\in \{0,1\}$ using a weighted sum followed by a threshold function.

Introduction to the Perceptron

A mathematical model

Given an input vector $\mathbf{x}=(x_1,x_2,\dots ,x_n)$ and a weight vector $\mathbf{w}=(w_1,w_2,\dots ,w_n)$, the perceptron computes:

$$z={\mathbf{w}}^{\top }\mathbf{x}+b=\sum _{i=1}^n{w}_i{x}_i+b$$

where $b$ is the bias term. The output is determined by the Heaviside step function:

$$y=f(z)=\{\begin{array}{ll}1,& \text{if }z\ge 0\\ 0,& \text{otherwise}\end{array}$$

Learning Rule

Given a labeled dataset $\{({\mathbf{x}}^{(i)},y^{(i)}){\}}_{i=1}^m$, the perceptron uses the following weight update rule for misclassified samples ($y^{(i)}\ne f({\mathbf{w}}^{\top }{\mathbf{x}}^{(i)}+b)$):

$$\mathbf{w}\leftarrow \mathbf{w}+\eta (y^{(i)}-f(z^{(i)})){\mathbf{x}}^{(i)}$$ $$b\leftarrow b+\eta (y^{(i)}-f(z^{(i)}))$$

where $\eta >0$ is the learning rate. You continue to update until there are no more errors. If the data is linearly separable, this converges in finite time.

You can observe the following: If there is an error, then you basically add the value of the $x$ scaled by the learning part to the theta.

Key Properties

• Linear separability: The perceptron converges if and only if the data is linearly separable (perceptron convergence theorem).
• Limitations: It cannot solve problems like XOR due to its inability to learn non-linearly separable functions.
• Extension: The multi-layer perceptron (MLP) overcomes this limitation using hidden layers and nonlinear activation functions.

Perceptron Convergence Theorem

The perceptron learning algorithm converges in a finite number of updates if the training data is linearly separable.

Setup and Notation

• Let the training set be $\{({\mathbf{x}}^{(i)},y^{(i)}){\}}_{i=1}^m$, where ${\mathbf{x}}^{(i)}\in {\mathbb{R}}^n$ and $y^{(i)}\in \{-1,+1\}$.
• The perceptron updates its weight vector $\mathbf{w}$ as follows for each misclassified point $({\mathbf{x}}^{(i)},y^{(i)})$: $$\mathbf{w}\leftarrow \mathbf{w}+y^{(i)}{\mathbf{x}}^{(i)}$$ where we assume the bias is absorbed into $\mathbf{x}$ by appending an extra dimension with $x_0=1$.

We assume the update rate is $1$, the same argument can be done with any update rate.

• Assumption (Linear Separability): There exists a weight vector ${\mathbf{w}}^{\ast }$ and a margin $\gamma >0$ such that for all training points $y^{(i)}({\mathbf{w}}^{\ast }\cdot {\mathbf{x}}^{(i)})\ge \gamma$ where $\Vert {\mathbf{w}}^{\ast }\Vert =1$. This is the same condition we use for Support Vector Machines.

Proof

We first bound the Growth of $\mathbf{w}\cdot {\mathbf{w}}^{\ast }$ Define ${\mathbf{w}}_t$ as the weight vector after $t$ updates. Initially, let ${\mathbf{w}}_0=0$. Each update modifies $\mathbf{w}$ as ${\mathbf{w}}_{t+1}={\mathbf{w}}_t+y^{(i)}{\mathbf{x}}^{(i)}$ Taking the dot product with ${\mathbf{w}}^{\ast }$ we have:

$$\begin{array}{rl}{\mathbf{w}}_{t+1}\cdot {\mathbf{w}}^{\ast }& =({\mathbf{w}}_t+y^{(i)}{\mathbf{x}}^{(i)})\cdot {\mathbf{w}}^{\ast }\\ & ={\mathbf{w}}_t\cdot {\mathbf{w}}^{\ast }+y^{(i)}({\mathbf{x}}^{(i)}\cdot {\mathbf{w}}^{\ast })\\ & \ge {\mathbf{w}}_t\cdot {\mathbf{w}}^{\ast }+\gamma \end{array}$$

Since $y^{(i)}({\mathbf{x}}^{(i)}\cdot {\mathbf{w}}^{\ast })\ge \gamma$, summing over all updates,

$${\mathbf{w}}_T\cdot {\mathbf{w}}^{\ast }\ge T\gamma$$

Where $T$ is the number of updates till now. We then bound $\Vert {\mathbf{w}}_t{\Vert }^2$: The norm squared of $\mathbf{w}$ evolves as:

$$\begin{array}{rl}\Vert {\mathbf{w}}_{t+1}{\Vert }^2& =\Vert {\mathbf{w}}_t+y^{(i)}{\mathbf{x}}^{(i)}{\Vert }^2\\ & =\Vert {\mathbf{w}}_t{\Vert }^2+2y^{(i)}({\mathbf{w}}_t\cdot {\mathbf{x}}^{(i)})+\Vert {\mathbf{x}}^{(i)}{\Vert }^2\end{array}$$

Since the update happens only for misclassified points, $y^{(i)}({\mathbf{w}}_t\cdot {\mathbf{x}}^{(i)})<0$, so we drop it to get:

$$\Vert {\mathbf{w}}_{t+1}{\Vert }^2\le \Vert {\mathbf{w}}_t{\Vert }^2+R^2$$

where $R={\max }_i\Vert {\mathbf{x}}^{(i)}\Vert$. Iterating over $T$ updates,

$$\Vert {\mathbf{w}}_T{\Vert }^2\le T{R}^2$$

We wrap up with the convergence bound. Using the Cauchy-Schwarz inequality,

$${\mathbf{w}}_T\cdot {\mathbf{w}}^{\ast }\le \Vert {\mathbf{w}}_T{\Vert }^2\Vert {\mathbf{w}}^{\ast }{\Vert }^2⟹T\gamma \le \Vert {\mathbf{w}}_T{\Vert }^2\Vert {\mathbf{w}}^{\ast }{\Vert }^2=\Vert \mathbf{w}{\Vert }^2\cdot 1\le \sqrt{T{R}^2}$$

From this we conclude:

$$\sqrt{T}\ge \frac{T\gamma }{R}⟹T\le \frac{R^2}{{\gamma }^2}$$

Since $R$ and $\gamma$ are constants, this implies that the perceptron makes at most $\frac{R^2}{{\gamma }^2}$ updates, proving convergence in $\mathcal{O}(\frac{R^2}{{\gamma }^2})$.

References

[1] Rosenblatt “The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain.” 1958