Quote:
Originally Posted by clarkfitzg
Using the PLA on 100 points and counting the number of iterations required for convergence I observed some interesting behavior. I set the max number of iterations to 1000 and then ran 10,000 simulations. This histogram shows the results:
The data at 1000 can be interpreted as those simulations which would have taken over 1000 iterations to converge. When I removed the limit on the max number of iterations and ran the experiment I had one case take iterations to converge. From this I conclude that the perceptron doesn't always converge rapidly.
In my experiment the mean number of iterations required for convergence was around 240, which is not particularly close to the possible answers of 100 and 500. The median, however, is certainly near 100. Do other people have similar results?

I suspect you did not choose your points randomly for the iterative step. If you, for example, always search sequentially through the points for a misclassified point, I believe it is not so uncommon to get caught in a loop of misclassified points. This must eventually resolve itself, but might take a while, and this leads to more long runs and a lot higher average number of iterations. I found that randomly picking misclassified points decreases the average number of iterations a lot and shortens the long tail, presumably by limiting repeated bad choices of misclassified point.