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

[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