The Support Vector Machine Tree

Support vector machines (SVMs) are an established binary classification model which enjoys good generalization performance. However, a long-standing problem is their high training and inference time. We propose a new model, the Support Vector Machine Tree, which applies a divide-and-conquer strategy but where, crucially, both the tree partition and the leaf SVMS are jointly optimized with an RKHS penalty. This brings several important improvements compared to the exact SVM as well as to existing approximate approaches. Computationally, the memory and runtime (at either training or inference) are far smaller, because the heavy SVM cost is confined to each leaf of the tree, which drastically reduces the number of support vectors in an instance-dependent way. The test accuracy is also improved, particularly in larger datasets, where other approaches cannot even run. Finally, the tree structure provides some interpretability.