Perceptron

machine-learning

Definition

Perceptron

The perceptron is a learning algorithm traditionally used in online learning for training binary linear classifier.

Given a sequence of training examples $({\mathbf{x}}_i,y_i)$, the algorithm iteratively updates the weight vector $\mathbf{w}$ whenever an instance is misclassified.

Update Rule

Let ${\mathbf{x}}_t\in {\mathbb{R}}^d$ be an element from the input space and $y_t\in \{-1,1\}$ be an element from the label space. Further, let $f_t(\mathbf{x})$ be the hypothesis (the model’s prediction) at time $t$.

$$\begin{array}{rl}{w}_0& =0\\ w_t& =w_{t-1}+\{\begin{array}{ll}0& \text{if }{f}_t(x_t)=y_t\\ y_i{x}_i& \text{else}\end{array}\end{array}$$

If the model is correct, i.e. $f_t(x)=y_t$, the weights remain unchanged. If the model is wrong, we add the input vector scaled by the true label to the weights.

Example $f_t$

$$f_t(x)=\mathrm{sign}(⟨x_t,w_t⟩)$$

where $w_t$ is the weight vector at time $t$ (orientation of the decision boundary), $⟨\cdot ,\cdot ⟩$ is the inner product, and $\mathrm{sign}$ be the signum function.

Why does this work?

Assume that we made a wrong prediction at time $t$ with input $x_t$ and true label $y_t$. The model predicted the wrong sign, i.e.:

• If $y_t=+1$, the model predicted $-1$, i.e. the inner product $⟨w_t,x_t⟩$ was negative.
• If $y_t=-1$, the model predicted $+1$, i.e. the inner product $⟨w_t,x_t⟩$ was positive.

We want to update $w_t$ to $w_{t+1}$ such that the new inner product $⟨w_{t+1},x_t⟩$ is closer to the correct sign than the old one.

Derivation: We want to see how the inner product (the score) changes for this specific input $x_t$ after the update. So we take the inner product on both sides with $x_t$:

$$⟨x_t,w_{t+1}⟩=⟨x_t,(w_t+y_t{x}_t)⟩$$

The inner product is linear, thus:

$$⟨x,w_{t+1}⟩=⟨x_t,w_t⟩+y_t⟨x_t,x_t⟩$$

By definition of the Euclidean norm, the inner product of a vector with itself is its squared length. Substituting this rigorously gives us this equation:

$$\underset{\text{New Score}}{\underbrace{⟨x_t,w_{t+1}⟩}}=\underset{\text{Old Score}}{\underbrace{⟨x_t,w_t⟩}}+\underset{\text{Correction Term}}{\underbrace{y_t+||x_t|{|}^2}}$$

The term $||x_t|{|}^2$ is always positive, which means that the direction of the change is entirely controlled by the label $y_t$.

• Case A: $y_t=+1$. The model predicted $-1$, meaning the old score was negative, i.e.: $⟨x,w⟩<0$. We want the score to become positive. Since $y_t=+1$, the correction term is positive, $+||x|{|}^2$. The new score increases and moves from the negative side closer to zero towards the positive side.
• Case B: $y_t=-1$. The model predicted $+1$, meaning the old score was positive, i.e.: $⟨x,w⟩<0$. We want the score to become negative. Since $y_t=-1$, the correction term is negative, $-||x|{|}^2$. The new score decreases and moves from the positive side closer to zero towards the negative side.

Expressiveness

Geometrically, the perceptron draws a hyperplane through the data. Everything on the side is $+1$, everything on the other side is $-1$. It can represent simple Boolean functions like AND and OR. But given that it’s a linear classifier, it’s not very expressive, and it can’t model everything, e.g. XOR.

Fixes: Kernel Perceptron, Multi-Layer Perceptron

Convergence Theorem

Novikoff (1962)

If the training data is linearly separable with a margin $\gamma >0$ (i.e., there exists a unit vector $\mathbf{u}$ such that $y_i({\mathbf{x}}_i^{\top }\mathbf{u})\ge \gamma$ for all $i$) and the instances are bounded by $\Vert {\mathbf{x}}_i\Vert \le R$, then the perceptron algorithm converges after at most $(R/\gamma {)}^2$ mistakes.

The XOR Problem

A simple linear model, such as the perceptron, fails on non-linearly separable data. A classic example is the XOR function, which cannot be partitioned by a single hyperplane. Resolving such tasks requires the composition of multiple layers, leading to artificial neural networks.