Budget Online Learning Algorithm for Least Squares SVM.

Area of Science:

• Machine Learning
• Computational Statistics

Background:

• Batch-mode least squares support vector machine (LSSVM) struggles with large datasets due to an unbounded number of support vectors (SVs).
• Limited-scale LSSVM offers efficient updating but requires dynamic training methods for large-scale streaming data.

Purpose of the Study:

• To introduce a budget online LSSVM (BOLSSVM) algorithm for dynamic training of limited-scale LSSVM.
• To enable efficient model updates without retraining from scratch for online prediction tasks.

Main Methods:

• The BOLSSVM algorithm utilizes a fixed budget for SVs, allowing dynamic updates.
• Employs low-rank correction and the Sherman-Morrison-Woodbury formula to efficiently update the LSSVM model by computing the inverse of the saddle point matrix derived from the KKT system.
• The method supports k-fold cross-validation, reducing computational complexity for leave-one-out cross-validation from O(n^4) to O(n^3).

Main Results:

• The proposed BOLSSVM algorithm demonstrates effective and efficient model updating for LSSVM.
• Experimental results on benchmark and real-world datasets confirm the validity and effectiveness of BOLSSVM for classification and regression tasks.
• Significant reduction in computational complexity for cross-validation compared to batch-mode methods.

Conclusions:

• BOLSSVM provides an efficient solution for training limited-scale LSSVM in dynamic, large-scale streaming data environments.
• The algorithm is particularly well-suited for online prediction tasks and offers computational advantages for cross-validation.
• BOLSSVM proves effective and valid for both classification and regression applications.