DCSVM: Fast Multi-class Classification using Support Vector Machines

DCSVM is a divide and conquer algorithm which relies on data sparsity in high dimensional space and performs a smart partitioning of the whole training data set into disjoint subsets that are easily separable. A single prediction performed between two partitions eliminates at once one or more classes in one partition, leaving only a reduced number of candidate classes for subsequent steps. The algorithm continues recursively, reducing the number of classes at each step, until a final binary decision is made between the last two classes left in the competition. In the best case scenario, our algorithm makes a final decision between k classes in O (log k) decision steps and in the worst case scenario DCSVM makes a final decision in k 1 steps, which is not worse than the existent techniques. 1. Introduction The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces (often with hundreds or thousands of dimensions) that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience. The expression was coined by Richard E. Bellman in a highly acclaimed article considering problems in dynamic optimization [1, 2]. In essence, as dimensionality increases, the volume of the space increases rapidly, and the available data become sparser and sparser.