Fast SVM training algorithm with decomposition on very large data sets

Area of Science:

• Machine Learning
• Computer Science

Background:

• Training support vector machines (SVMs) on large datasets with numerous classes presents significant computational challenges.
• Existing methods struggle with scalability when dealing with high-dimensional data and a vast number of categories.

Purpose of the Study:

• To propose an efficient algorithm for training large-scale SVMs.
• To address the limitations of current methods in handling massive datasets and thousands of classes.

Main Methods:

• Introduced a parallel optimization step to efficiently discard non-support vectors.
• Employed block diagonal matrices to approximate the kernel matrix, enabling problem decomposition into smaller, manageable subproblems.
• Integrated techniques like kernel caching and efficient kernel matrix computation to accelerate training.

Main Results:

• The proposed algorithm exhibits linear time complexity concerning the number of classes and dataset size.
• Demonstrated significantly better scaling capabilities compared to established SVM implementations like Libsvm, SVMlight, and SVMTorch.
• Achieved strong generalization performance on several large-scale databases.

Conclusions:

• The developed algorithm offers an efficient and scalable solution for training SVMs on massive datasets.
• The approach effectively handles problems with thousands of classes, outperforming existing state-of-the-art methods.
• The algorithm's efficiency and generalization performance make it suitable for real-world large-scale machine learning applications.