Improved Coresets for Kernel Density Estimates
Improved Coresets for Kernel Density Estimates
复制标题
改进的内核密度估计核心集
DOI：
10.1137/1.9781611975031.173
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
W. Tai
中科院分区：
文献类型：
--
作者：
J. M. Phillips;W. Tai
我们研究核密度估计的核心集的构造。也就是说，我们展示了如何用一个更小的点集的核密度估计来近似一个大的点集所描述的核密度估计。对于特征核（包括高斯核和拉普拉斯核），我们的近似保留了核密度估计之间的误差L_\infty$，核集大小为2/\epsilon ^2 $，但没有数据的其他方面，包括维数，点集的直径或其他近似所共有的核的带宽。当维度是不受限制的，我们表明这个界是紧的，这些内核以及一个更广泛的集。
这项工作提供了一个仔细的分析迭代弗兰克-沃尔夫算法适应这种情况下，一个算法称为\ldblquote {内核放牧}。该分析将涵盖统计、机器学习和几何的广泛工作结合起来。
当维度$d$是恒定的，我们证明了更严格的边界上的coreset的大小专门为高斯内核，表明它是有界的轴对齐的矩形的coreset的大小。目前最著名的构造性界是$O（\frac{1}{\displaystyle\log^d \frac{1}{\displaystyle\log^d \frac {1}}）$，而非构造性界，这可以通过$\sqrt{\log \frac{1}{\displaystyle\sqrt}}$来改进。这提高了最好的常数维界多项式为$d \geq 3$。
We study the construction of coresets for kernel density estimates. That is we show how to approximate the kernel density estimate described by a large point set with another kernel density estimate with a much smaller point set. For characteristic kernels (including Gaussian and Laplace kernels), our approximation preserves the $L_\infty$ error between kernel density estimates within error $\epsilon$, with coreset size $2/\epsilon^2$, but no other aspects of the data, including the dimension, the diameter of the point set, or the bandwidth of the kernel common to other approximations. When the dimension is unrestricted, we show this bound is tight for these kernels as well as a much broader set.
This work provides a careful analysis of the iterative Frank-Wolfe algorithm adapted to this context, an algorithm called \emph{kernel herding}. This analysis unites a broad line of work that spans statistics, machine learning, and geometry.
When the dimension $d$ is constant, we demonstrate much tighter bounds on the size of the coreset specifically for Gaussian kernels, showing that it is bounded by the size of the coreset for axis-aligned rectangles. Currently the best known constructive bound is $O(\frac{1}{\epsilon} \log^d \frac{1}{\epsilon})$, and non-constructively, this can be improved by $\sqrt{\log \frac{1}{\epsilon}}$. This improves the best constant dimension bounds polynomially for $d \geq 3$.