# D2KE: From Distance to Kernel and Embedding

## ResearchSpace/Manakin Repository

 dc.contributor.author Wu, L en dc.contributor.author Yen, IE-H en dc.contributor.author Xu, F en dc.contributor.author Ravikumar, P en dc.contributor.author Witbrock, Michael en dc.date.accessioned 2019-09-12T22:20:09Z en dc.date.issued 2018-05-25 en dc.identifier.citation Arxiv (1802.04956v4). 25 May 2018. 15 pages en dc.identifier.uri http://hdl.handle.net/2292/47664 en dc.description.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. en dc.relation.ispartof Arxiv en dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en dc.rights.uri https://arxiv.org/licenses/nonexclusive-distrib/1.0/license.html en dc.subject stat.ML en dc.subject stat.ML en dc.subject cs.LG en dc.title D2KE: From Distance to Kernel and Embedding en dc.type Report en dc.rights.holder Copyright: The authors en pubs.author-url http://arxiv.org/abs/1802.04956v4 en dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en pubs.subtype Working Paper en pubs.elements-id 774209 en pubs.org-id Science en pubs.org-id School of Computer Science en pubs.arxiv-id 1802.04956 en pubs.number 1802.04956v4 en pubs.record-created-at-source-date 2019-09-23 en
﻿