COMPUTATIONAL RESEARCH in BOSTON and BEYOND (CRIBB)

In numerous domains it is useful to represent a single example by the collection of the local features or parts that comprise it. However, kernel-based classification or regression is challenging with this representation, since the sets of features may vary in cardinality and elements lack a meaningful ordering. Existing methods compare feature sets by searching for explicit correspondences between their elements (which is too costly for large scale problems) or fitting parametric distributions to the sets (which makes restrictive assumptions about the data).

We present a new efficient kernel function which maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in this space. This "pyramid match" computation is linear in the number of features, and it implicitly finds correspondences based on the finest resolution histogram cell where a matched pair first appears. Since the kernel allows partial matches and does not penalize the presence of extra features, it is robust to clutter. We show the kernel function is positive-definite, making it valid for use in learning algorithms whose optimal solutions are guaranteed only for Mercer kernels. We demonstrate our algorithm on object recognition, 3-D human pose estimation, and time of publication inference tasks and show it to be accurate and dramatically faster than current approaches.