Increasingly real world problems require multiple predictions. For instance in advertisement placement on the web a list of advertisements is placed on a page with the objective of maximizing click-through rate. Traditionally machine learning has focused on producing a single best prediction. More generally in this thesis we build an efficient framework for making multiple predictions where the objective is to optimize any utility function which is (monotone), submodular over a sequence of predictions.
Other examples of tasks where multiple predictions are important include: grasp selection in robotic manipulation where the robot arm must evaluate a sequence of grasps with the aim of finding a grasp which is successful as early on in the sequence as possible, trajectory selection for mobile ground robots where the task is to select a sequence of trajectories from a much larger set of feasible trajectories for minimizing expected cost of traversal. Such tasks fall either into the case where there is an a priori distribution of data (e.g. web search) wherein the order of observing data points is fixed or the case where the next observed data point is a consequence of the current prediction (e.g. trajectory selection in ground robots). For each of these cases we optimize for the content and order of the sequence of predictions. We additionally extend the methods to make multiple predictions in structured output domains e.g. challenging vision tasks like semantic scene labeling and monocular pose estimation.
The developed framework reduces the problem of predicting lists to training a series of classification/regression tasks thus having the powerful flexibility to use any existing prediction method. In upcoming work we make multiple budgeted predictions for bridging the gap between perception and control for enabling safe and stable, pure vision-based autonomous aerial vehicle navigation through dense clutter.
J. Andrew (Drew) Bagnell, (Chair)
Eric Horvitz (Microsoft Research)
Rich Caruana, (Microsoft Research)