An MDM solver for the nearest point problem in Scaled Convex Hulls

Scaled Convex Hulls (SCHs) have been recently proposed by Liu et al. as the basis of a method to build linear classifiers that, when extended to kernel settings, provides an alternative approach to more established methods such as SVMs. Here we show how to adapt the Mitchell-Dem´yanov-Malozemov (MDM) algorithm to build such SCH-based classifiers by solving a concrete nearest point problem. We shall discuss two possible approaches to do so and show that they produce the same updates; we shall also prove that the resulting algorithm converges to the optimal solution. Moreover, our experiments also show that MDM´s complexity is better than that of the SK method proposed in Liu´s work. However, while the SCH classifiers often give competitive accuracies, further work is needed, particularly to obtain the scaling parameter #, to ensure good classifier accuracies for general problems.