Efficient Density Evaluation for Smooth Kernels
Efficient Density Evaluation for Smooth Kernels
复制标题
光滑内核的有效密度评估
DOI：
10.1109/focs.2018.00065
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Paris Siminelakis
中科院分区：
文献类型：
--
作者：
A. Backurs;M. Charikar;P. Indyk;Paris Siminelakis
给定一个核函数k（.,.）和一个数据集P∧R^d， P在点xε R^d处的核密度函数等于KDF_P(x):= 1/|P| Σ_yεP k（x, y）。核密度评价在科学计算、统计学、计算机视觉、机器学习等领域有着广泛的应用。在所有这些方法中，都需要快速计算KDF_P(x)，通常对于许多输入x和大型点集p。在本文中，我们提出了一组有效的KDF计算算法，假设核k是“光滑的”，即值最多随距离多项式变化。这个假设被几个研究得很好的核满足，包括（广义的）t-student核和有理二次核。对于光滑核，我们给出了一个数据结构，经过O（dn log （Φ n）/ε^2）预处理后，在O（dlog （Φ n）/ε^2）时间内估计KDF_P(x)达到1±ε的因子，其中Phi；是纵横比。在k的附加衰减条件下，log（Φn）项可以进一步替换为log n，上述示例满足了这一条件。我们以两种方式进一步扩展结果。首先，我们使用低失真嵌入来将结果扩展到为除__2以外的空间定义的核。这种约简的关键特征是嵌入的失真只影响算法的运行时间，而不影响估计的准确性。因此，我们得到了在其他的_p范数、土移距离和其他度量空间上的核的(1+ε)-近似估计算法。其次，对于随距离减小的光滑核，我们提出了一种从密度估计到底层空间近似近邻的一般简化方法。这允许我们构造一般加倍度量的算法，以及l_p范数和其他空间的替代算法。
Given a kernel function k(.,.) and a dataset P⊂ R^d, the kernel density function of P at a point xε R^d is equal to KDF_P(x):= 1/|P| Σ_yεP k(x, y). Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDF_P(x) quickly, often for many inputs x and large point-sets P. In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i.e. the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log (Φ n)/ε^2) preprocessing, estimates KDF_P(x) up to a factor of 1 ± ε in O(dlog (Φ n)/ε^2) time, where Phi; is the aspect ratio. The log(Φn) term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples. We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than ℓ_2. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1+ε)-approximate estimation algorithms for kernels over other ℓ_p norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for l_p norms and other spaces.
慢性乙型肝炎病毒 (HBV) 感染患者血清中 IFIT3 增加，并在体外通过 JAK-STAT2 促进干扰素α的抗 HBV 作用
影响因子：
3.7
作者：
Xu, Siyi;Huang, Jinlan;Xun, Zhen;Li, Shiqi;Fu, Ya;Lin, Ni;Wu, Wennan;Chen, Tianbin;Liu, Can;Ou, Qishui
通讯作者：
Ou, Qishui