Paper abstract

On the equivalence of the SMO and MDM Algorithms for SVM Training

Jose R. Dorronsoro - EPS-UAM, Spain
Alvaro Barbero - EPS-UAM, Spain
Jorge Lopez - EPS-UAM, Spain

Session: Kernel Methods
Springer Link:

SVM training is usually discussed under two different algorithmic points of view. The first one is provided by decomposition methods such as SMO and SVMLight while the second one encompasses geometric methods that try to solve a Nearest Point Problem (NPP), the Gilbert--Schlesinger--Kozinec (GSK) and Mitchell--Demyanov--Malozemov (MDM) algorithms being the most representative. In this work we will show that, indeed, both approaches are essentially coincident. More precisely, we will show that a slight modification of SMO in which at each iteration both updating multipliers correspond to patterns in the same class solves NPP and, moreover, that this modification coincides with an extended MDM algorithm. Besides this, we also propose a new way to apply the MDM algorithm for NPP problems over reduced convex hulls.