[Brown CS Talks] Brown CS Seminar: Gert Lanckriet in Lubrano May 7th, 2002 at noon

[talks-admin@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			    Gert Lanckriet
			     
      Department of Electrical Engineering and Computer Science
			University of Berkeley
	      
	       Lubrano Conference Room (CIT 4th floor)
		     Tuesday, May 7, 2002 at noon
	       Refreshments will be served at 11:45 am
		 

	   Advanced Convex Optimization in Machine Learning

			       Abstract

A general machine learning approach consists of two important tasks.
First, we want to find a representation of the data that makes it easy
to detect a certain given structure in the data. Then, we decide to
use a learning algorithm to exploit this structure. Kernel-based
learning methods work by embedding the data into a high-dimensional
feature space (implicit in the choice of the kernel function), and
then searching for linear relations among the embedded data
points. Advanced convex optimization and machine learning concerns are
merging nowadays to provide new approaches and powerful methods for
both tasks.

The kernel function implicitly defines the relative positions of the
embedded data points. However, the embedding of a finite set of data
points can be entirely specified by a symmetric positive semi-definite
kernel matrix. This suggests addressing the first task in terms of
kernel matrices rather than kernel functions.  We apply Semi-Definite
Programming techniques to a kernel matrix associated with both
training and test data, which results in a powerful transductive
algorithm: using the labelled part of the data, one can learn an
``optimal'' embedding also for the unlabelled part. These learning
problems are convex, which avoids problems with local minima.

To address the second task, a novel learning algorithm for
classification is presented as well. The Minimax Probability Machine
(MPM) considers a binary classification problem where the mean and
covariance matrix of each class are assumed to be known. No further
assumptions are made with respect to the class-conditional
distributions. The MPM formulation arises when minimizing an explicit
upper bound on the generalization error, over all possible
class-conditional distributions. This leads to a Second Order Cone
Program, which has a complexity similar to SVMs. We also address the
issue of estimation errors in the means and covariance matrices of the
classes and exploit Mercer kernels to obtain nonlinear decision
boundaries. This yields classifiers which prove to be competitive with
current methods, including SVMs.


		    Host: Professor Thomas Hofmann