RUI: Fourier Analysis of Learning Problems and Function Classes

RUI：学习问题和函数类的傅里叶分析

• 批准号: 0209064
• 负责人: Jeffrey Jackson
• 金额: $ 20.06万
• 依托单位: Duquesne University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0209064&HistoricalAwards=false
• 关键词: RUI; Fourier; Analysis; Learning; Problems

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.

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