用随机映射加速多项式核计算，提升大规模数据处理效率
Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
- 提出Tensor Sketch方法，通过随机映射快速近似多项式核
- 计算时间复杂度为O(n(d+D log D))，支持高维大数据集
- 理论保证近似精度，适用于大规模机器学习任务
使用随机特征映射近似非线性核已成为将核方法扩展到大规模数据集的强大技术。我们提出 extit{Tensor Sketch}，一种用于近似多项式核的高效随机特征映射。给定n个在$/mathbb{R}^d$中的训练样本，Tensor Sketch能在$/mathbb{R}^D$中以$/mathcal{O}ig(n(d+D /log{D})ig)$的时间计算低维嵌入，使其适用于高维和大规模场景。我们提供了近似误差的理论保证，确保所得核函数估计的保真度。此外，我们还讨论了扩展并强调了Tensor Sketch作为核心计算工具的应用场景。
原文摘要 · Abstract (English)
Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose $\textit{Tensor Sketch}$, an efficient random feature map for approximating polynomial kernels. Given $n$ training samples in $\mathbb{R}^d$ Tensor Sketch computes low-dimensional embeddings in $\mathbb{R}^D$ in time $\mathcal{O}\left( n(d+D \log{D}) \right)$ making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。