On the Precise Error Analysis of Support Vector Machines
Abla Kammoun and Mohamed-Slim Alouini A. Kammoun and M.S. Alouini are with the Computer, Electrical, and Mathematical Sciences and Engineering (CEMSE) Division, KAUST, Thuwal, Makkah Province, Saudi Arabia (e-mail:
Abstract
This paper investigates the asymptotic behavior of the soft-margin and hard-margin support vector machine (SVM) classifiers for simultaneously high-dimensional and numerous data (large $n$ and large $p$ with $n/p\to\delta$ ) drawn from a Gaussian mixture distribution. Sharp predictions of the classification error rate of the hard-margin and soft-margin SVM are provided, as well as asymptotic limits of as such important parameters as the margin and the bias. As a further outcome, the analysis allow for the identification of the maximum number of training samples that the hard-margin SVM is able to separate. The precise nature of our results allow for an accurate performance comparison of the hard-margin and soft-margin SVM as well as a better understanding of the involved parameters (such as the number of measurements and the margin parameter) on the classification performance. Our analysis, confirmed by a set of numerical experiments, builds upon the convex Gaussian min-max Theorem, and extends its scope to new problems never studied before by this framework.
中文速览
支持向量机（SVM）的分类误差在高维大数据场景下难以精确预测，现有分析要么依赖非严格的物理方法，要么局限于特定问题结构。研究者借助凸高斯极小极大定理（convex Gaussian min-max theorem, CGMT）这一严格数学工具，对数据维度 p 和样本量 n 同比增长（n/p 趋于常数）的高斯混合分布数据，推导出了硬间隔和软间隔 SVM 分类误差、间隔及偏置参数的精确渐近公式，并首次严格确定了硬间隔 SVM 能够线性分离训练样本的最大样本数阈值。数值实验验证了这些理论预测即使在有限维度下也与实际结果高度吻合。这项工作不仅为调节 SVM 超参数提供了低计算成本的理论依据，还将 CGMT 框架推广到了此前从未涉及的优化问题类型，为高维分类器的严格理论分析开辟了新路径。
原文 arXiv:2003.12972;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2003.12972v1