Classifiers in High Dimensional Hilbert Metrics
This addresses a fundamental geometric classification problem in machine learning, with applications in convex geometry, but is incremental as it builds on existing SVM frameworks in specialized metrics.
The paper tackles the problem of classifying points in high-dimensional Hilbert polygonal metrics by developing efficient LP-based algorithms for large-margin SVM, achieving polynomial runtime in terms of points, facets, and dimension, which improves upon previous methods with exponential or no theoretical guarantees.
Classifying points in high dimensional spaces is a fundamental geometric problem in machine learning. In this paper, we address classifying points in the $d$-dimensional Hilbert polygonal metric. The Hilbert metric is a generalization of the Cayley-Klein hyperbolic distance to arbitrary convex bodies and has a diverse range of applications in machine learning and convex geometry. We first present an efficient LP-based algorithm in the metric for the large-margin SVM problem. Our algorithm runs in time polynomial to the number of points, bounding facets, and dimension. This is a significant improvement on previous works, which either provide no theoretical guarantees on running time, or suffer from exponential runtime. We also consider the closely related Funk metric. We also present efficient algorithms for the soft-margin SVM problem and for nearest neighbor-based classification in the Hilbert metric.