# Pocket algorithm for training perceptrons

When you read about perceptron variants at Wikipedia there is explained an algorithm: Pocket Algorithm It is said that:

solves the stability problem of perceptron learning by keeping the best solution seen so far "in its pocket"

However, there is not much explanation about the algorithm, and I would like to see some pseudocode for it, as well as an explanation of how to implement by hand.

It's discussed a little more fully in the neural networks book of Rojas, which is available from his website. I believe the book also contains a reference to the original paper which introduced the algorithm.

http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/pmwiki/pmwiki.php?n=Books.NeuralNetworksBook

Edit: yes, here is Gallant's original paper with pseudocode:

https://www.ling.upenn.edu/courses/Fall_2007/cogs501/Gallant1990.pdf

• Looking at Gallant's original paper, I'm fairly certain his pseudocode contains an error. On page 181, step 3B, I think that should say run_pi = 0, not run_w = 0.
– Ben
Mar 3 '21 at 3:10

Basically the pocket algorithm is a perceptron learning algorithm with a memory which keeps the result of the iteration. You can consider the pocket algorithm something similar to:

def pocket(training_list, max_iteration):
w = randomVector()
best_error = error(w)
for i in range(0, max_iteration):
x=misclassified_sample(w, training_list)
w=vector_sum(w, x.y(x))
if error(w) < best_error :
best_w = w
best_error = error(w)
return best_w


I have found the blog very helpful to understand Pocket Algorithm. I am giving excerpt from that blog.

Pocket Learning Algorithm

The idea is straightforward: this algorithm keeps the best result seen so far in its pocket (that is why it is called Pocket Learning Algorithm). The best result means the number of misclassification is minimum. If the new weights produce a smaller number of misclassification than the weights in the pocket, then replace the weights in the pocket to the new weights; if the new weights are not better than the one in the pocket, keep the one in the pocket and discard the new weights. At the end of the training iteration, the algorithm returns the solution in the pocket, rather than the last solution.

Pseudocode