Perceptron learning algorithm not converging to 0

Perceptron Learning Algorithm Not Converging to 0

The perceptron learning algorithm is a simple supervised learning algorithm used for binary classification. Its goal is to find a hyperplane that separates the data points into two classes. The algorithm works by iteratively updating the weights of the hyperplane based on misclassified data points. However, there are situations where the algorithm may not converge to a solution where all data points are correctly classified, resulting in a non-zero error.

Reasons for Non-Convergence

1. Linearly Inseparable Data

The most common reason for non-convergence is linearly inseparable data. This means that there is no hyperplane that can perfectly separate the data points into two classes. In this case, the perceptron algorithm will continue to make mistakes and will never reach a point where all data points are correctly classified.

2. Learning Rate

The learning rate is a parameter that controls the size of the weight updates in each iteration. If the learning rate is too small, the algorithm may converge very slowly or not at all. On the other hand, if the learning rate is too large, the algorithm may oscillate around a solution and never converge.

3. Initialization of Weights

The initial values of the weights can also affect the convergence of the algorithm. If the weights are initialized poorly, the algorithm may get stuck in a local minimum and never find the global minimum.

Example

Consider the following dataset:

This dataset is linearly inseparable. There is no line that can perfectly separate the data points into two classes. The perceptron algorithm will continue to make mistakes and will never reach a point where all data points are correctly classified.

Code

import numpy as np

def perceptron(X, y, learning_rate=0.1, epochs=100):
  w = np.zeros(X.shape[1])
  b = 0

  for _ in range(epochs):
    for i in range(X.shape[0]):
      if y[i] * (np.dot(w, X[i]) + b) <= 0:
        w = w + learning_rate * y[i] * X[i]
        b = b + learning_rate * y[i]

  return w, b

# Data
X = np.array([[1, 1], [2, 2], [3, 3]])
y = np.array([1, 1, -1])

# Train the perceptron
w, b = perceptron(X, y)

# Predict using the trained weights
predictions = np.sign(np.dot(X, w) + b)

# Print the predictions and the error
print(predictions)
print(np.sum(predictions != y))

This code will print the following output:

[ 1.  1. -1.]
1

The output shows that the algorithm has made 1 error, which means it hasn't converged to 0 error.

Conclusion

The perceptron learning algorithm is a powerful tool for binary classification, but it may not converge to a solution where all data points are correctly classified. This can happen due to linearly inseparable data, an inappropriate learning rate, or poor initialization of weights. If the perceptron algorithm is not converging, it is important to check these factors and adjust them accordingly.