D2KE: From Distance to Kernel and Embedding

ResearchSpace/Manakin Repository

Show simple item record

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


Full text options

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Advanced Search

Browse