In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.
%0 Journal Article
%1 citeulike:3340265
%A Grauman, Kristen
%A Darrell, Trevor
%C Cambridge, MA, USA
%D 2007
%I MIT Press
%J J. Mach. Learn. Res.
%K features, kernel, vision
%P 725--760
%T The Pyramid Match Kernel: Efficient Learning with Sets of Features
%U http://portal.acm.org/citation.cfm?id=1248659.1248685
%V 8
%X In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.
@article{citeulike:3340265,
abstract = {In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.},
added-at = {2009-05-19T18:00:18.000+0200},
address = {Cambridge, MA, USA},
author = {Grauman, Kristen and Darrell, Trevor},
biburl = {https://www.bibsonomy.org/bibtex/2c3a4fd989f3a655278dba9ef0adabea2/earthfare},
citeulike-article-id = {3340265},
description = {CiteULike: Everyone's library},
interhash = {8126ada3e720e5ddca07a700f8b2a9aa},
intrahash = {c3a4fd989f3a655278dba9ef0adabea2},
issn = {1533-7928},
journal = {J. Mach. Learn. Res.},
keywords = {features, kernel, vision},
pages = {725--760},
posted-at = {2009-05-19 16:21:21},
priority = {3},
publisher = {MIT Press},
timestamp = {2009-05-19T18:03:27.000+0200},
title = {The Pyramid Match Kernel: Efficient Learning with Sets of Features},
url = {http://portal.acm.org/citation.cfm?id=1248659.1248685},
volume = 8,
year = 2007
}