Can a perceptron be modified so as to converge with non-linearly separable data?

Question

Normally, a perceptron will converge provided data are linearly separable. Now if we select a small number of examples at random and flip their labels to make the dataset non-separable. How can we modify the perception that, when run multiple times over the dataset, will ensure it converges to a solution?

I know the pocket algorithm by S. I. Gallant provides an answer to this question, but I'm not sure how exactly it works or if there's any better solution. I'm a beginner in machine learning, so it would be great if someone could share a detailed explanation.

Answer 1

In the case that you are interested in (1) a perceptron classifier and (2) the data are not linearly separable, you have specified the motivation of the so-called "soft-margin" SVM. Briefly, we seek a solution

$$ \min_{w,b}~\lambda||w||^2_2 + \frac{1}{n}\sum_{i=1}^n \max \left\{ 0, 1 - y_i\left(w^\top x_i -b\right)\right\} $$

for $y_i \in\{-1,1\}$ for parameters $(w,b)\in \mathbb{R}^{p+1}$ where you have $p$ features. Configurations $(w,b)$ which put a sample on the "wrong side" of the hyperplane are penalized proportional to the distance from the hyper plane.

Notably, if $\lambda$ is set small enough, the solution is very similar to that of the hard-margin SVM, otherwise known as a perceptron, because $\lambda ||w||_2^2$ becomes negligible, although the learning procedure becomes convex, whether or not linear separation is possible.

More information can be found in Elements of Statistical Learning, chapter 12.