D2KE: From Distance to Kernel and Embedding

Lingfei Wu, Ian En-Hsu Yen, Fangli Xu, Pradeep Ravikumar, Michael WitbrockarXiv 2018 · OpenReview

TL;DR

This paper introduces D2KE, a novel framework that bridges the gap between dissimilarity measures and standard machine learning models by deriving positive-definite kernels from arbitrary distance functions. This allows for effective learning on structured data where feature representations are difficult to define, outperforming existing distance-based methods in various domains.

What Problem Does This Paper Address?

Many real-world machine learning problems involve data with complex structures like sequences, sets, or time series. For these types of data, it's often much easier to define a meaningful way to measure how dissimilar two inputs are (e.g., edit distance for strings, Hausdorff distance for sets) than it is to create a good vector-based feature representation. However, most powerful machine learning algorithms, like Support Vector Machines (SVMs) and neural networks, are designed to work with vector inputs. This creates a challenge: how can we leverage these powerful models when we only have a distance measure and no natural feature representation? Existing methods often struggle with indefinite kernels or require specific properties of the distance function, limiting their applicability.

Methods

The core of D2KE is a general framework for constructing positive-definite (PD) kernels from any given dissimilarity measure $d(x, y)$. The key idea is to define a kernel $k(x, y)$ as an expectation over random features:

$k(x, y) := \mathbb{E}_{p(w)}[\phi_w(x) \phi_w(y)]$

where $\phi_w(x) = \exp(-\gamma d(x, w))$ is a random feature map, $w$ is a random object drawn from a distribution $p(w)$, and $\gamma$ is a scaling parameter. This approach is inspired by Random Features but, crucially, it derives the kernel from the distance, rather than using random features to approximate an existing kernel.

The paper then shows how this framework relates to existing methods:

  • Distance Substitution Kernel (DSK): In a limiting case (large $\gamma$), D2KE's kernel approaches the DSK.
  • Representative-Set Method (RSM): If the random objects $w$ are drawn from the training data itself, D2KE reduces to a scaled version of RSM.

A practical implementation uses a finite number of random features (R) to approximate the kernel, allowing for efficient learning. The paper also provides theoretical guarantees on the approximation error and the overall learning performance.

Datasets

The paper evaluates D2KE on three distinct domains:

  • Time-Series: Four datasets were used, including multivariate time-series from the UCI Machine Learning repository and a dataset from GMU.
  • Strings: Four datasets were used, with alphabet sizes ranging from 4 to 8, sourced from UCI and LibSVM.
  • Images: Four image datasets were used, represented by SIFT descriptors.

The paper does not introduce new benchmarks but uses established datasets to compare against existing methods.

Key Insights and Ideas

  • Bridging the Distance-Feature Gap: The most significant insight is the development of a general method to create valid (positive-definite) kernels from arbitrary distance metrics. This unlocks the power of kernel methods for a much wider range of structured data.
  • Random Features for Kernel Construction: Instead of using random features to approximate existing kernels, D2KE uses them to construct novel kernels based on distances. This is a reversal of the typical random feature application.
  • The Power of Synthetic Random Objects: The paper finds that using synthetically generated random objects (e.g., random time series, random strings) for the distribution $p(w)$ often leads to better performance than using actual data samples as representatives (as in RSM). This suggests that carefully chosen synthetic data can capture relevant semantic information more effectively.
  • Lipschitz Continuity: Functions learned within the D2KE framework are guaranteed to be Lipschitz-continuous with respect to the input distance, which is a desirable property for generalization.

Key Results

D2KE consistently demonstrated strong performance across all tested domains:

  • Time-Series: D2KE achieved higher classification accuracy than KNN, often by a significant margin (e.g., 26.62% higher on IQ_radio), and outperformed distance substitution kernels.
  • Strings: D2KE performed comparably to or better than other baselines, even when Levenshtein distance (a metric) was used by other methods. It showed a clear advantage over KNN.
  • Images: D2KE's performance was near other baselines, though GDK_LED performed slightly better on some image datasets. Crucially, D2KE achieved this with significantly less computation time than methods with quadratic complexity.
  • Computational Efficiency: D2KE's complexity is $O(NRL)$, which is linear in the number of samples ($N$) and sequence length ($L$), making it much more scalable than methods with $O(N^2L^2)$ complexity, especially for large datasets.

Limitations and Future Work

  • Theoretical Treatment of $p(w)$: The paper conjectures that the better performance of synthetic random objects is due to generating more relevant semantic information or allowing for a richer approximation of the exact kernel. However, a formal theoretical treatment of why specific distributions $p(w)$ work better is deferred to future work.
  • Deep Architectures: The authors suggest a promising future direction is to integrate these distance-based embeddings into deep learning architectures for end-to-end learning on structured inputs.
  • Tuning Parameters: While the framework is general, the choice of $\gamma$ and the distribution $p(w)$ are important parameters that require careful selection, often through cross-validation.

Summary updated

Abstract

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:\mathcal{X} \rightarrow \R$ based solely on a dissimilarity measure $d:\mathcal{X}\times\mathcal{X} \rightarrow \R$ between inputs. In particular, we propose a general framework to derive a family of \emph{positive definite kernels} from a given dissimilarity measure, which subsumes the widely-used \emph{representative-set method} as a special case, and relates to the well-known \emph{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.
BibTeX
@misc{wu2018d,
  author = {Lingfei Wu and Ian En-Hsu Yen and Fangli Xu and Pradeep Ravikumar and Michael Witbrock},
  title = {{D2KE: From Distance to Kernel and Embedding}},
  year = {2018},
  eprint = {1802.04956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.04956},
}
Figure