📂Machine Learning

Perceptron Convergence Theorem

Let’s say we have a training set that is linearly separable as represented by $X^{+}$, $X^{-}$. Consider $y$ as the following labels.

$$y_{i} = \pm 1\ (\mathbf{x}_{i} \in X^{\pm})$$

Suppose the entire training set $X = X^{+} \cup X^{-}$ has $N$ data points. Then, let’s say we insert input values in the following order.

$$\mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N), \mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N),\mathbf{x}(1), \mathbf{x}(2), \cdots$$

That is, once the learning process for the last data has finished, it starts over again from the beginning.

Theorem¹

Assume that every time a prediction fails for an input value, the following holds.

$$\mathbf{x}_{1}, \mathbf{x}_{2}, \cdots, \mathbf{x}_{n}, \cdots$$

Let’s say the initial value of the weight is $\mathbf{w}_{1}=\mathbf{0}$. For the $n$th prediction failure on input data, the weight update is assumed to be as follows.

$$\mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n}$$

Then, there exists a $n_{o}$ that satisfies the following equation.

$$\mathbf{w}_{n_{o}} = \mathbf{w}_{n_{o} + 1} = \mathbf{w}_{n_{o} + 2} = \cdots$$

$$\begin{cases} \mathbf{w}_{n_{o}}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{n_{o}}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases}$$

Description

To summarize the above summary in one sentence, ‘Perceptron completes learning within a finite number of iterations.’ This means that the weight does not update after $n_{o}$, implying that for all $\mathbf{x}$, $y = \hat{y}$ holds true.

The key point is the method of updating the weight, which is simply adding the wrong data, and showing mathematically that learning ends within a finite number of times.

Proof

Assuming the number of prediction failures for input data is $n$, it will be shown that there is an upper limit for $n$ when updating the weight as above.

---

Since the prediction failed for $\mathbf{x}_{n}$, the weight is updated as follows.

$$\begin{equation} \mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n} \label{eq3} \end{equation}$$ And because it was assumed that $X^{+}$ and $X^{-}$ are separable, a solution $\mathbf{w}_{\ast}$ that satisfies the following equation exists.

$$\begin{cases} \mathbf{w}_{\ast}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{\ast}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases} \quad \text{and} \quad \| \mathbf{w}_{\ast} \| = 1$$

Then, the following holds true.

$$\mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} = \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + y_{n}\mathbf{w}_{\ast}^{T}\mathbf{x}_{n}$$

And let’s define $\alpha>0$ as follows.

$$\alpha := \min \limits_{\mathbf{x} \in X} y \mathbf{w}_{\ast}^{T}\mathbf{x}$$

Then, the following inequality holds.

$$\mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} \ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha$$

But since the initial value of the weight was $\mathbf{w}_{1}=\mathbf{0}$, the following equation holds true.

$$\begin{equation} \begin{aligned} \\ \mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n-1} + 2\alpha \\ &\cdots \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{1} + n\alpha \\ &= n\alpha \end{aligned} \label{eq1} \end{equation}$$

And by the Cauchy-Schwarz inequality, the following equation holds true.

$$\begin{equation} \| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{\ast} \|^{2} \| \mathbf{w}_{n+1} \|^{2} \ge | \mathbf{w}_{\ast}^{T} \mathbf{w}_{n+1} |^{2} \label{eq2} \end{equation}$$

By $\eqref{eq1}$ and $\eqref{eq2}$, the following equation holds true.

$$\begin{equation} \| \mathbf{w}_{n+1} \|^{2} \ge n^{2}\alpha^{2} \label{eq4} \end{equation}$$

Again, from $\eqref{eq3}$, we obtain the below equation.

$$\| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} + 2 y_{n}\mathbf{w}^{T}_{n}\mathbf{x}_{n}$$

But since $y_{n}\mathbf{w}^{T}_{n} \mathbf{x}_{n} \le 0$, we obtain the following inequality.

$$\| \mathbf{w}_{n+1} \|^{2} \le \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} \le \| \mathbf{w}_{n} \| ^{2} + \beta$$

At this time, $\beta = \max \limits_{\mathbf{x} \in X} \| \mathbf{x} \|^{2}$. Since the initial value of the weight was $\mathbf{w}_{1}=\mathbf{0}$, the following equation holds true.

$$\begin{equation} \begin{aligned} \| \mathbf{w}_{n+1} \|^{2} &\le \| \mathbf{w}_{n} \| ^{2} + \beta \\ &\le \| \mathbf{w}_{n-1} \| ^{2} + 2\beta \\ &\le \| \mathbf{w}_{n-2} \| ^{2} + 3\beta \\ &\vdots \\ &\le \| \mathbf{w}_{1} \|^{2} + n\beta \\ &= n\beta \end{aligned} \label{eq5} \end{equation}$$

Combining the two inequalities $\eqref{eq4}, \eqref{eq5}$ gives the following.

$$n^{2} \alpha^{2} \le \| \mathbf{w}_{n+1} \|^{2} \le n\beta$$

Arranging for $n$ gives the following.

$$\begin{align*} && n^{2} \alpha^{2} &\le n\beta \\ \implies && n &\le \dfrac{\beta}{\alpha^2} \end{align*}$$

Therefore, we obtain the following.

$$n_{\text{max}} = \dfrac{\beta}{\alpha^{2}}$$

This means that the number of times a perceptron can fail in its predictions is at most $\dfrac{\beta}{\alpha^{2}}$, and thereafter, it succeeds in predicting all training data.

■