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.