3
$\begingroup$

I studied the perceptron algorithm and I'm trying to prove the convergence by myself. However, I'm wrong somewhere and I am not able to find the error.

Assumption:

  1. We assume that there is some $\gamma > 0$ such that $$y_{t}(\theta ^{*})^{T}x_{t} \geq \gamma $$ for all $t = 1, \ldots , n$. The additional number $\gamma > 0$ is used to ensure that each example is classified correctly with a finite margin.

  2. We will assume that all the (training) images have bounded Euclidean norms, i.e., $$\left \| \bar{x_{t}} \right \|\leq R$$ for all $t$ and some finite $R$

By hypothesis the learning rule is:

$$\theta ^{(k)}= \theta ^{(k-1)} + \mu y_{t}\bar{x_{t}}$$

Now, $$(\theta ^{*})^{T}\theta ^{(k)}=(\theta ^{*})^{T}\theta ^{(k-1)} + \mu y_{t}\bar{x_{t}} \geq (\theta ^{*})^{T}\theta ^{(k-1)} + \mu \gamma $$ so , by induction $$(\theta ^{*})^{T}\theta ^{(k)}\geq k\mu \gamma $$

At the same time, $$\left \| \theta ^{(k)} \right \|^{2} = \left \| \theta ^{(k-1)}+\mu y_{t}\bar{x_{t}} \right \|^{2} = \left \| \theta ^{(k-1)} \right \|^{2}+2\mu y_{t}(\theta ^{(k-1)^{^{T}}})\bar{x_{t}}+\left \| \mu \bar{x_{t}} \right \|^{2} \leq \left \| \theta ^{(k-1)} \right \|^{2}+\left \| \mu\bar{x_{t}} \right \|^{2}\leq \left \| \theta ^{(k-1)} \right \|^{2}+\mu ^{2}R^{2}$$

So, by induction

$$\left \| \theta ^{(k)} \right \|^{2} \leq k\mu ^{2}R^{2}$$

We can now combine parts 1) and 2) to bound the cosine of the angle between $\theta^∗$ and $\theta(k)$:

$$\cos(\theta ^{*},\theta ^{(k)}) =\frac{\theta ^{*}\theta ^{(k)}}{\left \| \theta ^{*} \right \|\left \|\theta ^{(k)} \right \|} \geq \frac{k\mu \gamma }{\sqrt{k\mu ^{2}R^{2}}\left \|\theta ^{2} \right \|}$$

Since cosine is bounded by one, we get:

$$k \leq \frac{R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$

The problem is that the correct result should be:

$$k \leq \frac{\mu ^{2}R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$

$\endgroup$
  • 1
    $\begingroup$ Could you define your variables or link to a source that does it? $\endgroup$ – Elias Strehle Feb 12 '18 at 12:34
1
$\begingroup$

What you presented is the typical proof of convergence of perceptron proof indeed is independent of $\mu$. Hence the conclusion is right.

Typically $\theta^*x$ represents a hyperplane that perfectly separate the two classes.

The formula $k \le \frac{\mu^2 R^2 \|\theta^*\|^2}{\gamma^2}$ doesn't make sense as it implies that if you set $\mu$ to be small, then $k$ is arbitarily close to $0$. It is saying that with small learning rate, it converges immediately. You might want to look at the termination condition for your perceptron algorithm carefully.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.