D2KE: From Distance to Kernel and Embedding

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}\to \mathbb{R}$ based solely on a dissimilarity measure $d:\mathcal{X}\times \mathcal{X}\to \mathbb{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.

15 pages, 4 tables

Cited by in corpus (11)

• Multilevel Graph Matching Networks for Deep Graph Similarity Learning
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Exploiting Rich Syntactic Information for Semantic Parsing with Graph-to-Sequence Model
• Word Mover's Embedding: From Word2Vec to Document Embedding
• SQL-to-Text Generation with Graph-to-Sequence Model
• Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding
• Graph Random Neural Features for Distance-Preserving Graph Representations
• Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications
• Space-efficient Feature Maps for String Alignment Kernels
• Efficient Global String Kernel with Random Features: Beyond Counting Substructures
• Scalable Spectral Clustering Using Random Binning Features