RUI: Fourier Analysis of Learning Problems and Function Classes

这项研究的一般领域被称为计算学习理论。 这一领域研究的出发点通常是定义数学模型，即"学习“一词在各种环境中可能意味着什么。 这些模型捕获的学习概念，然后正式分析，经常导致算法解决模型内的学习问题，以及证明某些问题无法解决。 这些学习理论模型和结果为机器学习中更多的应用工作提供了支持，这反过来又证明了从电子商务到自动驾驶车辆的高级研究等应用中的实用性。该项目以多种方式增加了现有的学习理论知识，包括分析一个相对较新的模型，称为可能完全正确的学习，开发了一种算法，可以学习最广泛的函数类，但证明是可学习的（大多数AC0函数），并致力于扩展基本类（奇偶函数类）的可学习性的硬度结果。 在这些和其他项目任务中使用的关键工具是函数类的傅立叶分析。 虽然傅立叶分析的主要目的是支持对学习问题的研究，但它的另一个好处是增强了我们对几类有趣的函数的理解，例如大多数AC 0。 此外，这个项目提供了一个刺激的研究经验，本科生和硕士生在一所大学，从国家科学基金会的角度来看，主要是一个本科机构。

The general area within which this research is performed is known ascomputational learning theory. The starting point for research in thisarea is typically the definition of mathematical models of what the term``learning'' may mean in a variety of settings. The concept of learningcaptured by these models is then formally analyzed, frequently leadingto algorithms for solving learning problems within the models as well asto proofs that certain problems cannot be solved. Theselearning-theoretic models and results lend support to more applied workin machine learning, which in turn has demonstrated utility inapplications ranging from e-commerce to advanced research on vehiclesthat drive themselves.This project adds to the existing body of learning-theoretic knowledgein a number of ways, including analysis of a relatively new model calledProbably Exactly Correct learning, development of an algorithm thatlearns arguably the broadest class of functions yet shown to belearnable (majority of AC0 functions), and work toward extendinghardness results for learnability of a fundamental class, the class ofparity functions. The key tool used in these and other project tasks isFourier analysis of classes of functions. While the primary purpose ofthe Fourier analysis is to support research into learning questions, aside benefit is the enhancement of our understanding of severalinteresting classes of functions, such as majority of AC0. Furthermore,this project provides a stimulating research experience to undergraduateand master's students at a university that, from an NSF perspective, islargely an undergraduate institution.