Machine Learning, On-Line Decision Making, and Algorithms for Computationally Hard Problems

点击翻译按钮获取中文摘要

The focus of this research is on developing efficient combinatorial algorithms for key problems in Artificial Intelligence and Optimization, as well as providing an improved understanding of the inherent nature of these problems. This project involves three areas in particular: machine learning, on- line decision-making, and the study of algorithms for computationally hard problems. In the area of machine learning, one main component of this work is the design of better algorithms for learning in large feature spaces. This includes questions of how to best combine a large number of low-quality sources of advice that may be available (e.g., via the internet), as well as a number of questions with close relations to crytography. In the area of on-line algorithms and on-line decision making, this research will investigate new approaches for the Weighted-Caching problem, as well as the potential for using methods from machine learning (for instance, algorithms for combining sources of advice) to produce improved solutions to a number of problems in this area. In the study of methods for solving computationally hard problems, this project will continue exploration of approximation algorithms, as well as a new approach to general purpose planning based on representing planning problems in a compact graph structure, and then bringing in tools and ideas from graph algorithms. This planning method was first demonstrated in the Graphplan planner, and empirically appears to be substantially faster than more traditional planning algorithms in a wide variety of settings.