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

这项研究的重点是开发有效的组合算法的人工智能和优化的关键问题，以及提供这些问题的内在本质的更好的理解。 该项目特别涉及三个领域：机器学习、在线决策和计算困难问题的算法研究。 在机器学习领域，这项工作的一个主要组成部分是设计更好的算法，用于在大特征空间中学习。 这包括如何最好地联合收割机组合大量可能可用的低质量建议来源的问题（例如，通过互联网），以及一些与密码学关系密切的问题。 在在线算法和在线决策领域，本研究将研究加权缓存问题的新方法，以及使用机器学习方法（例如，结合建议来源的算法）来改进该领域许多问题的解决方案的潜力。 在解决计算困难问题的方法研究中，本项目将继续探索近似算法，以及一种新的通用规划方法，该方法基于在紧凑的图结构中表示规划问题，然后从图算法中引入工具和思想。 这种规划方法首先在Graphplan规划器中演示，并且在各种设置中，经验上似乎比传统的规划算法快得多。

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.