[Crib-list] Computational Research in Boston Seminar (CRiB) -- Friday, 10/07/2005 -- Stata Center -- Room 32-144 (fwd)

[Shirley Entzminger]

 			COMPUTATIONAL RESEARCH IN BOSTON SEMINAR

DATE:		Friday, October 7, 2005
TIME:		12:30 PM
LOCATION:	Building 32, Room 144
  (Stata Center)

(Pizza and beverages will be provided.)


TOPIC:  THE PYRAMID MATCH KERNEL:
  	DISCRIMINATIVE CLASSIFICATION AND REGRESSION WITH SETS OF FEATURES


SPEAKER:	KRISTEN GRAUMAN
  		Massachusetts Institute of Technology

ABSTRACT:

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.

*******************************************************************************

Massachusetts Institute of Technology
Department of Mathematics
Cambridge, MA  02139

http://www-math.mit.edu/crib

For information on CRiB, contact:

Alan Edelman:  edelman at math.mit.edu
Steven G. Johnson:  stevenj at math.mit.edu
Jeremy Kepner:  kepner at ll.mit.edu