The generalized perceptron convergence theorem is for a defined threshold T.

When you do the maths it all comes to an upper bound and a lower bound.

The lower bound looks like this!


$$ (x^{\ast})^T x(k) > k \delta. \qquad\qquad (4.67)$$

We can see if the threshold is equal to zero, this is still true.

But what happens with the upper bound?

The generalized theorem looks like this:

We now have an upper bound (Eq. (4.75)) and a lower bound (Eq. (4.70)) on the squared length of the weight vector at iteration $k$. If we combine the two inequalities we find

$$ k\Pi \geq {\lVert x(k) \rVert}^2 > \frac{(k \delta)^2}{{\lVert x^\ast \rVert }^2} \quad \text{or} \quad k < \frac{\Pi {\lVert x^\ast\rVert}^2}{\delta^2}. \qquad \qquad (4.76)$$

Because $k$ has a an upper bound, this means that the weights will only be changed a finite number of times. Therefore, the perceptron learning rule will converge in a finite number of iterations.

I am struggling to find how this is true for a zero threshold too since you can't divide by zero.

Can someone help me here get it for this special case?


Your Answer

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

Browse other questions tagged or ask your own question.