Kernel method works with any distance for better machine learning
A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings
Machine Learning
Summary
Many machine learning methods need special ways to measure distances between data points, but some real-world distances don’t fit these special rules. The authors propose a new method that turns any distance into a kind of feature that can be used with common machine learning tools, making them work properly and efficiently. Their method keeps computations manageable by representing data sparsely and works well even on complex data types like shapes or distributions. They show it can predict more accurately and provide reliable uncertainty estimates.
What this means in practice
- •For machine learning engineers: Build predictive models on complex data with unusual distance measures that previously hindered kernel-based methods.
- •For computer vision developers: Improve recognition systems by using geodesic distances on shapes while maintaining stable and efficient kernels.
Authors
Marcus M. Noack, Maher B. Alghalayini, Mark D. Risser
Abstract
Kernel methods, and Gaussian Processes (GPs) in particular, require a Hilbertian distance measure---one whose square is conditionally negative definite (CND)---to guarantee positive semi-definiteness (PSD) of the kernel matrix; a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all |D| training points; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and demonstrate, using geodesic and Wasserstein distances, that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification.