Discrepancy, Coresets, and Sketches in Machine Learning
Discrepancy, Coresets, and Sketches in Machine Learning
复制标题
机器学习中的差异、核心集和草图
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Edo Liberty
中科院分区：
文献类型：
--
作者：
Zohar S. Karnin;Edo Liberty
本文定义了函数族的类差异概念。它表明，低差异类承认小的离线和流coresets。我们提供了一般的技术来界定机器学习问题的类差异。作为一般技术的推论，我们绑定了逻辑回归的差异（以及因此的核心复杂性），sigmoid激活损失，矩阵协方差，核密度和点积或平方距离的任何解析函数。我们的结果证明了上述问题的ε-近似O（sqrt{d}/sqrt）大小的核心集的存在性.这解决了长期存在的开放问题的核心复杂性高斯核密度估计。我们提供了两个相关但独立的结果。首先，广泛使用的合并和减少技巧的指数改进，为任何低差异问题提供改进的流草图。第二，一个非常简单的确定性算法，用于找到任何半正定核的低差异序列（因此coresets）。本文建立了类差异，核心复杂性，可学习性和流算法之间的一些明确的联系。
This paper defines the notion of class discrepancy for families of functions. It shows that low discrepancy classes admit small offline and streaming coresets. We provide general techniques for bounding the class discrepancy of machine learning problems. As corollaries of the general technique we bound the discrepancy (and therefore coreset complexity) of logistic regression, sigmoid activation loss, matrix covariance, kernel density and any analytic function of the dot product or the squared distance. Our results prove the existence of epsilon-approximation O(sqrt{d}/epsilon) sized coresets for the above problems. This resolves the long-standing open problem regarding the coreset complexity of Gaussian kernel density estimation. We provide two more related but independent results. First, an exponential improvement of the widely used merge-and-reduce trick which gives improved streaming sketches for any low discrepancy problem. Second, an extremely simple deterministic algorithm for finding low discrepancy sequences (and therefore coresets) for any positive semi-definite kernel. This paper establishes some explicit connections between class discrepancy, coreset complexity, learnability, and streaming algorithms.