# D2KE: From Distance to Kernel and Embedding

arXiv: https://arxiv.org/abs/1802.04956 · HTML: https://mlsanity.com/paper/1802.04956/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

## Built on by (most cited first, 4 of 4)

- [Lipschitz and H"older Continuity in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2310.18078/) (2023)
- [OsmT: Bridging OpenStreetMap Queries and Natural Language with Open-source Tag-aware Language Models](https://mlsanity.com/paper/2512.04738/) (2025)
- [Lipschitz bounds for integral kernels](https://mlsanity.com/paper/2604.02887/) (2026)
- [A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings](https://mlsanity.com/paper/2609.19083/) (2026)

## Abstract (arXiv)

For many machine learning problem settings, particularly with structured inputs such as sequences or sets of objects, a distance measure between inputs can be specified more naturally than a feature representation. However, most standard machine models are designed for inputs with a vector feature representation. In this work, we consider the estimation of a function f:X rightarrow R based solely on a dissimilarity measure d:X×X rightarrow R between inputs. In particular, we propose a general framework to derive a family of positive definite kernels from a given dissimilarity measure, which subsumes the widely-used representative-set method as a special case, and relates to the well-known distance substitution kernel in a limiting case. We show that functions in the corresponding Reproducing Kernel Hilbert Space (RKHS) are Lipschitz-continuous w.r.t. the given distance metric. We provide a tractable algorithm to estimate a function from this RKHS, and show that it enjoys better generalizability than Nearest-Neighbor estimates. Our approach draws from the literature of Random Features, but instead of deriving feature maps from an existing kernel, we construct novel kernels from a random feature map, that we specify given the distance measure. We conduct classification experiments with such disparate domains as strings, time series, and sets of vectors, where our proposed framework compares favorably to existing distance-based learning methods such as k-nearest-neighbors, distance-substitution kernels, pseudo-Euclidean embedding, and the representative-set method.