SVM on Trees

We propose an SVM model in which labeled samples are organized as a tree derived from one-dimensional projections onto a fixed reference line. On the tree, classification boundaries are determined by pairs of vertices with opposite labels, which play a role similar to support vectors in classical SVMs. For a general margin-loss trade-off parameter λ, the training problem can be solved via a dynamic programming procedure with O(n 2 ) time complexity where n is the number of vertices. When λ = 1, the problem admits an O(n) solution. Experiments show training speedups over LinearSVC in certain regimes while maintaining competitive accuracy.