提出高维希尔伯特度量下高效支持向量机算法，突破以往指数级运行时间瓶颈。
Classifiers in High Dimensional Hilbert Metrics
- 基于线性规划设计多项式时间算法处理高维希尔伯特度量的分类问题
- 在点数、面数和维度均为输入参数时，运行时间为多项式复杂度
- 适用于需要几何结构建模的机器学习任务，如超球面或凸体空间分类
在高维空间中对点进行分类是机器学习中的基础几何问题。本文研究了在d维希尔伯特多边形度量下的点分类问题。希尔伯特度量是凯莱-克莱因双曲距离对任意凸体的推广，在机器学习与凸几何中有广泛应用。我们首先提出一种基于线性规划的高效算法，用于解决该度量下的大间隔SVM问题，其运行时间在点数、边界面数和维度上均为多项式关系。相比以往工作，该方法在理论运行时间上取得显著改进，此前方法或无理论保证，或存在指数级复杂度。我们还考虑了紧密相关的福恩克度量，并为软间隔SVM及基于最近邻的分类问题提出了高效算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。