RUI: Learnability: Framework, Concepts, Algorithms

这个项目包括三条研究线，都与计算学习理论有关。(1)众所周知的“可能近似正确”（PAC）学习模型——以及其他模型——提供了一个强有力的框架，在这个框架内，各种学习概念都得到了正式的分析。然而，学习是一个广泛的概念，现有的模型没有很好地捕捉到一些学习的感觉。这个项目开发了一个框架来分析这样一种类型的学习，即在任务规划的背景下学习搜索控制规则。除了开发该框架外，还将寻求框架内可学习性的下限和上限。基于初步的工作，图论方法在产生这种边界方面显得特别有前途。(2)现有学习模式中的几个基本问题仍未解决。使用函数类的傅里叶分析以及相关的基于傅里叶的算法，已经获得了相关问题的一些最佳答案。因此，傅里叶和其他技术将应用于这些剩下的问题。(3)迄今为止产生的基于傅里叶的算法，虽然在多项式时间内运行是有效的，但在实践中没有使用，部分原因是运行时间的指数有些大。该项目旨在生成运行时间明显更好的算法。

This project encompasses three lines of research, all related to computational learning theory. (1) The well-known ``probably approximately correct'' (PAC) model of learning---and other models---have provided a robust framework within which various notions of learning have been formally analyzed. However, learning is a broad concept, and some senses of learning have not been captured well by existing models. This project develops a framework for analyzing one such type of learning, that of learning search-control rules within the context of task planning. In addition to developing this framework, lower and upper bounds on learnability within the framework will be sought. Based on preliminary work, graph-theoretic approaches appear to be particularly promising in producing such bounds. (2) Several fundamental questions within existing learning models still remain open. Some of the best answers to related questions have been obtained using Fourier analysis of function classes along with associated Fourier-based algorithms. Thus, Fourier and other techniques will be applied to several of these remaining questions. (3) Fourier-based algorithms that have been produced thus far, while efficient in the sense of running in polynomial time, are not used in practice in part because of somewhat large exponents in the running time. This project seeks to produce algorithms with noticeably better running times.