Why won't Perceptron Learning Algorithm converge?

Question

I have implemented the Perceptron Learning Algorithm in Python as below. Even with 500,000 iterations, it still won't converge.

I have a training data matrix X with target vector Y, and a weight vector w to be optimized.

My update rule is:

while(exist_mistakes): 
    # dot product to check for mistakes
    output = [np.sign(np.dot(X[i], w)) == Y[i] for i in range(0, len(X))]

    # find index of mistake. (choose randomly in order to avoid repeating same index.) 
    n = random.randint(0, len(X)-1)
    while(output[n]): # if output is true here, choose again
        n = random.randint(0, len(X)-1)

    # once we have found a mistake, update
    w = w + Y[n]*X[n] 

Is this wrong? Or why is it not converging even after 500,000 iterations?

Answer 1

Perceptrons by Minsky and Papert (in)famously demonstrated in 1969 that the perceptron learning algorithm is not guaranteed to converge for datasets that are not linearly separable.

If you're sure that your dataset is linearly separable, you might try adding a bias to each of your data vectors, as described by the question: Perceptron learning algorithm not converging to 0 -- adding a bias can help model decision boundaries that do not pass through the origin.

Alternatively, if you'd like to use a variant of the perceptron learning algorithm that is guaranteed to converge to a margin of specified width, even for datasets that are not linearly separable, have a look at the Averaged Perceptron -- PDF. The averaged perceptron is an approximation to the voted perceptron, which was introduced (as far as I know) in a nice paper by Freund and Schapire, "Large Margin Classification Using the Perceptron Algorithm" -- PDF.

Using an averaged perceptron, you make a copy of the parameter vector after each presentation of a training example during training. The final classifier uses the mean of all parameter vectors.