RUI: Fourier Analysis of Learning Problems and Function Classes

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

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.