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.