SoftDoubleMaxMinOver: perceptron-like training of support vector machines

Area of Science:

• Machine Learning
• Computational Statistics

Background:

• The perceptron algorithm is a foundational method for binary classification.
• Existing algorithms like MinOver offer maximum-margin classification but lack bias and efficient support vector storage.
• Kernel formulations require storing training patterns, not exclusively support vectors.

Purpose of the Study:

• To introduce DoubleMinOver, an extension of MinOver that incorporates a bias term.
• To develop DoubleMaxMinOver, which addresses the storage of non-support vectors in kernelized MinOver algorithms.
• To extend these algorithms for soft margin classification and least squares support vector machines (SVMs).

Main Methods:

• Modification of the perceptron algorithm to create MinOver, DoubleMinOver, and DoubleMaxMinOver.
• Analysis of convergence rates, showing O(t(-1)) for DoubleMinOver.
• Implementation of kernel formulations and selective forgetting of non-support vectors.
• Extension to soft margin classification and least squares SVMs.

Main Results:

• DoubleMinOver achieves O(t(-1)) convergence with linear computational cost per step.
• DoubleMaxMinOver overcomes the drawback of storing non-support vectors by selectively forgetting them.
• The SoftDoubleMaxMinOver algorithm demonstrates performance on par with standard SVM software on benchmarks.

Conclusions:

• The developed algorithms provide efficient and effective maximum-margin classifiers.
• DoubleMaxMinOver offers an improvement by exclusively storing support vectors.
• The SoftDoubleMaxMinOver algorithm is a viable alternative to standard SVMs for soft margin classification and least squares SVMs.