Scaling up minimum enclosing ball with total soft margin for training on large datasets

Area of Science:

• Machine Learning
• Computational Geometry

Background:

• Standard Minimum Enclosing Ball (MEB) and center-constrained MEB are effective for large datasets using Core Vector Machines (CVM).
• MEB with total soft margin (T-MEB) presents training challenges for large datasets due to violated inequality constraints, preventing direct CVM/GCVM application.

Purpose of the Study:

• To develop a fast learning algorithm (FL-TMEB) for scaling up T-MEB training on large datasets.
• To address the limitations of directly applying CVM/GCVM to T-MEB by modifying its constraints.

Main Methods:

• FL-TMEB relaxes T-MEB constraints to be equivalent to a center-constrained MEB, solvable by CVM and a Core Set (CS).
• Utilizes a sub-optimal solution theorem for T-MEB to construct an Extended Core Set (ECS) by incorporating neighbors of CS samples.
• Approximates the T-MEB solution using the optimal weights derived from the ECS.

Main Results:

• The proposed FL-TMEB algorithm effectively scales T-MEB training for large datasets.
• Experimental validation on UCI and USPS datasets demonstrates the method's effectiveness.

Conclusions:

• FL-TMEB provides an efficient approach for training T-MEB on large-scale data.
• The algorithm successfully overcomes the constraint violation issue in T-MEB training.