Perceptron convergence theorem

Making the following assumptions:

• The classes $C_0$ and $C_1$ are linearly separable
• $\eta = 1$
• $\ve{w}_{0} = \ve{0}$
• $\ve{x}_n$ pertaining to class $C_1$ $\forall \quad n$

From (4) we can write:

$$\ve{w}_{n+1} = \ve{w}_n + \ve{x}_n$$ (5)

And solving the recurrent equation:

$$\ve{w}_{n+1} = \sum_{k=1}^n \ve{x}_n$$ (6)

Because of the linearly separable assumption, $\exists \quad \ve{w}_o \quad \vert \quad \ve{w}_o^t\ve{x}_n > 0 \quad \forall n$ then we can define:

$$\alpha = \min_{\ve{x}_n \in C_1} \ve{w}_o^t\ve{x}_n$$ (7)

Multiplying both sides of (7) by $\ve{w}_o^t$:

$$\ve{w}_o^t \ve{w}_{n+1} = \ve{w}_o^t \sum_{k=0}^n \ve{x}_n$$ (8)

And applying (8):

$$\ve{w}_o^t \ve{w}_{n+1} \geq n\alpha$$ (9)

Applying Cauchy-Schwarz:

$$\vert\vert\ve{w}_o\vert\vert^2\vert\vert\ve{w}_{n+1}\vert\vert^2 \geq (\ve{w}_o^t \ve{w}_{n+1})^2$$ (10)

$$\vert\vert\ve{w}_{n+1}\vert\vert^2 \geq \frac{(n\alpha)^2}{\vert\vert\ve{w}_o\vert\vert^2}$$ (11)

From (6): ||w_k+1||^2 = ||w_k||^2 + ||x_k||^2 + 2w_k^tx_k         for         k=1,,n         and     x_n C_1

||w_k+1||^2 ||w_k||^2 + ||x_k||^2

||w_k+1||^2 - ||x_k||^2 ||w_k||^2         for         k=1,,n

Defining $\beta$ as: = _x_k C_1 ||x_k||^2

||w_k+1||^2 _k=1^n ||x_k||^2 n

So the squared norm of the weight vector grows at most linearly with the number of iterations $n$, which for large $n$ conflicts with (12), so to satisfy both (12) and (17):

(n_max)^2||w_o||^2 = n_max

n_max = ||w_o||^2^2

The adaptation of the perceptron thus, shall terminate after $n_{max}$ steps. A variation consists in presenting the same pattern to then network, until $\ve{w}_{n+1}^t\ve{x}_n$ has the correct sign. The choice of $\ve{w}_o$ just decreases or increases the number of steps required to converge.