DCSVM: Fast Multi-class Classification using Support Vector Machines
This is an incremental improvement for machine learning practitioners needing faster multi-class SVM classification.
The paper tackles multi-class classification with Support Vector Machines by introducing DCSVM, a divide-and-conquer algorithm that reduces decision steps to O(log k) in best cases and k-1 in worst cases, matching existing techniques.
We present DCSVM, an efficient algorithm for 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.