论文标题
在线性压缩下的线性可分离性上，并应用了硬支持向量机的应用
On Linear Separability under Linear Compression with Applications to Hard Support Vector Machine
论文作者
论文摘要
本文研究了在线性压缩下保持数据生成分布的线性可分离性的理论问题。尽管众所周知，线性可分离性可以通过线性变换来维持，该线性变换几乎保留了域点之间的内部产物，但保留内部产物以维持线性可分离性的极限是未知的。在本文中，我们表明，只要内部产物的失真小于原始数据生成分布的平方缘，就可以保持线性可分离性。该证明主要基于从有限的训练示例延伸到数据生成分布的（可能）无限域的硬支持向量机（SVM）的几何形状。作为应用，我们在随机亚高斯矩阵的（i）压缩长度上得出边界。 （ii）用硬vm进行压缩学习的概括误差。
This paper investigates the theoretical problem of maintaining linear separability of the data-generating distribution under linear compression. While it has been long known that linear separability may be maintained by linear transformations that approximately preserve the inner products between the domain points, the limit to which the inner products are preserved in order to maintain linear separability was unknown. In this paper, we show that linear separability is maintained as long as the distortion of the inner products is smaller than the squared margin of the original data-generating distribution. The proof is mainly based on the geometry of hard support vector machines (SVM) extended from the finite set of training examples to the (possibly) infinite domain of the data-generating distribution. As applications, we derive bounds on the (i) compression length of random sub-Gaussian matrices; and (ii) generalization error for compressive learning with hard-SVM.
