The Pyramid Match Kernel: Efficient Learning with Sets of Features

@article{citeulike:2819451, 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.}, author = {Grauman, Kristen and Darrell, Trevor }, citeulike-article-id = {2819451}, journal = {Journal of Machine Learning Research}, keywords = {image-processing, kernel-machines, scalability}, month = {April}, pages = {725--760}, posted-at = {2008-05-21 12:50:35}, priority = {2}, title = {The Pyramid Match Kernel: Efficient Learning with Sets of Features}, url = {http://www.jmlr.org/papers/volume8/grauman07a/grauman07a.pdf}, volume = {8}, year = {2007} }

TY - JOUR ID - citeulike:2819451 L3 - citeulike-article-id:2819451 TI - The Pyramid Match Kernel: Efficient Learning with Sets of Features JF - Journal of Machine Learning Research VL - 8 SP - 725 EP - 760 N2 - 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. KW - image-processing KW - kernel-machines KW - scalability AU - Grauman, Kristen AU - Darrell, Trevor PY - 2007/04// UR - http://www.jmlr.org/papers/volume8/grauman07a/grauman07a.pdf ER -