Abstracts for Laurent El Ghaoui

The EECS Research Summary for 2003


Learning the Kernel Matrix with Semi-Definite Programming

Gert Lanckriet, Nello Cristianini1, and Peter Bartlett2
(Professors Laurent El Ghaoui and Michael I. Jordan)
(NSF) IIS-9988642 and (ONR) MURI N00014-00-1-0637

Kernel-based learning algorithms work by embedding the data into a Euclidean space, and then searching for linear relations among the embedded data points. The embedding is performed implicitly, by specifying the inner products between each pair of points in the embedding space. This information is contained in the so-called kernel matrix, a symmetric and positive definite matrix that encodes the relative positions of all points. Specifying this matrix amounts to specifying the geometry of the embedding space and inducing a notion of similarity in the input space--classical model selection problems in machine learning. In this project we show how the kernel matrix can be learned from data via semi-definite programming (SDP) techniques. When applied to a kernel matrix associated with both training and test data this gives a powerful transductive algorithm. Using the labeled part of the data one can learn an embedding also for the unlabeled part. The similarity between test points is inferred from training points and their labels. Importantly, these learning problems are convex, so we obtain a method for learning both the model class and the function without local minima. Finally, the novel approach presented in the project is supported by positive empirical results.

1Professor, Dept. of Statistics, UC Davis
2Visiting Professor, A.N.U., Canberra

More information (http://robotics.eecs.berkeley.edu/~gert/) or

Send mail to the author : (gert@eecs.berkeley.edu)

Robust Novelty Detection with Single-Class MPM

Gert Lanckriet
(Professors Laurent El Ghaoui and Michael I. Jordan)
(NSF) IIS-9988642 and (ONR) MURI N00014-00-1-0637

In this project we consider the problem of novelty detection, presenting an algorithm that aims to find a minimal region in input space containing a fraction alpha of the probability mass underlying a data set. This algorithm, the "single-class minimax probability machine (MPM)," is built on a distribution-free methodology that minimizes the worst-case probability of a data point falling outside of a convex set, given only the mean and covariance matrix of the distribution and making no further distributional assumptions. We present a robust approach to estimating the mean and covariance matrix within the general two-class MPM setting, and show how this approach specializes to the single-class problem. We provide empirical results comparing the single-class MPM to the single-class SVM and a two-class SVM method.


More information (http://robotics.eecs.berkeley.edu/~gert/) or

Send mail to the author : (gert@eecs.berkeley.edu)

Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices: Its Applications in Robust Aircraft Path Planning

Arnab Nilim
(Professor Laurent El Ghaoui)
Eurocontrol 014692, (DARPA) F33615-01-C-3150, and (NSF) ECS-9983874

Optimal solutions to the Markov decision problems (MDPs) are often sensitive with respect to the state transition probabilities. In many practical problems, the estimation of the transition probabilities is far from accurate. Hence, estimation errors are, together with the curse of dimensionality, a limiting factor in applying MDPs to real-world problems. We propose an algorithm for solving finite-state and finite-action MDPs, where the solution is guaranteed to be robust with respect to the estimation errors of the state transition probabilities. Our algorithm involves a statistically accurate yet numerically efficient representation of uncertainty via likelihood or entropy functions. The worst-case complexity of the robust algorithm is within a factor log n (n is the number of states) of the original Bellmann recursion. Hence, robustness can be added at almost no extra computing cost. We applied our algorithm to the problem of the dynamic routing of an aircraft under stochastic obstacles, where the probabilties of the obstacles are unknown but bounded. We showed that a siginificant reduction in delay can be obtained by using our robust strategies with respect to the nominal strategy when the data is uncertain.

[1]
L. El Ghaoui and A. Nilim, "Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices" (submitted for publication).
[2]
A. Nilim, L. El Ghaoui, and V. Duong, "Robust Dynamic Routing of Aircraft under Uncertainty," IEEE Digital Avionics Systems Conf., Irvine, CA, November 2002.
[3]
A. Nilim, L. El Ghaoui, and V. Duong, "Routing of Aircraft with Uncertain Weather Probabilities," Institute of Operations Research and Management Sciences, San Jose, CA, November 2002.
[4]
A. Nilim, L. El Ghaoui, M. Hansen, and V. Duong, "Trajectory-based Air Traffic Management (TB-ATM) under Weather Uncertainty," USA/EUROPE ATM R&D Seminar, Santa Fe, NM, December 2001.
[5]
A. Nilim, L. El Ghaoui, M. Hansen, and V. Duong, "Dynamic Routing of Aircraft under Uncertainty," Institute of Operations Research and Management Sciences, Miami, FL, November 2001.

More information (http://robotics.eecs.berkeley.edu/~nilim) or

Send mail to the author : (nilim@eecs.berkeley.edu)