^March April – 2010 ^May

It is well known that there cannot be a single ``best'' heuristic for optimal planning in general. One way of overcoming this is by combining admissible heuristics (e.g. by using their maximum), which requires computing numerous heuristic estimates at each state. However, there is a tradeoff between the time spent on computing these heuristic estimates for each state, and the time saved by reducing the number of expanded states. We present a novel method that reduces the cost of combining admissible heuristics for optimal search, while maintaining its benefits. Based on an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for that decision rule, and employ the learned model to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms each of the individual heuristics that were used, as well as their regular maximum.

In recent years there is increasing interest in learning from both labeled and unlabeled data (a.k.a. semi-supervised learning, or SSL). The key assumption in SSL, under which an abundance of unlabeled data may help, is that there is some relation between the unknown response function to be learned and the marginal density of the predictor variables.

In the first part of this talk I'll present a statistical analysis of two popular graph based SSL algorithms: Laplacian regularization method and Laplacian eigenmaps.

In the second part I'll present a novel multiscale approach for SSL as well as supporting theory. Some intimate connections to harmonic analysis on abstract data sets will be discussed.

Joint work with Nati Srebro (TTI), Xueyuan Zhou (Chicago), Matan Gavish (WIS/Stanford) and Ronald Coifman (Yale).