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.