Detecting convergence for PLA

[melipone]

What's the best way to detect convergence for PLA? Check whether there is no misclassified examples in 1 iteration or Pr(f(x) != g(x)) does not change?

[yaser]

Originally Posted by melipone

What's the best way to detect convergence for PLA? Check whether there is no misclassified examples in 1 iteration or Pr(f(x) != g(x)) does not change?

Checking that there are no misclassified examples in the training data, which would naturally happen as you look for a misclassfied point for the next PLA iteration.

[gah44]

Since it takes longer to check for misclassified points than to do the update, what I do is actually:

Loop up to 10000 times:
Choose a random point.
If misclassified, update it and count the update.
Every 20 such tries, test for no more misclassified points and exit loop.

The 10000 avoids infinite loops due to mistakes in the algorithm.

My first PLA was in AWK, which is pretty slow.

I now have PLA in Java, which is plenty fast no matter how you do it.

Any number besides 20 will also work, that was my guess as a balance between the update time and testing time.