AF:Small:RUI:New directions in Fourier analysis, noise sensitivity, and learning theory

AF:Small:RUI：傅立叶分析、噪声敏感性和学习理论的新方向

• 批准号: 1117079
• 负责人: Karl Wimmer
• 金额: $ 23.15万
• 依托单位: Duquesne University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-06-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117079&HistoricalAwards=false
• 关键词: AF; Small; RUI; New; directions

One of the major concerns that practitioners have about theoretical machine learning is the focus on distributions where the attributes are independent: in other words, knowing one attribute gives no information about any others. As an example, while it is plausible that height and eye color are independent, it is much less believable that height and weight are independent. Thus, the output given by any algorithm that is based on the assumption that the attributes of a person (such as height and weight) are independent cannot be trusted. The goal of this project is to extend what we know about the theory of such problems while removing some of the mathematically convenient assumptions such as independence. The tools used focus on discrete Fourier analysis, but involve many other techniques from mathematics such as functional analysis and representation theory of finite groups. One recurring technique is the application of the "noise sensitivity" method, which quantifies the complexity of a function based on how similar the value of the function is on some input to the values of that input's neighbors. In many cases, the goal is to show that the Fourier spectrum of certain classes of functions is predictable; often, this predictability is a key component of algorithms for machine learning. The broader goal of this project is to discover new connections between mathematics and computer science with a special focus on questions motivated by machine learning. Answers to the underlying questions would be useful to theoreticians and could lead to better applied machine learning algorithms. Also, the mathematical questions raised are interesting independently of the machine learning connection. The problems considered in this project will provide an invigorating research opportunity for undergraduate and Master's students.

实践者对理论机器学习的主要担忧之一是关注属性独立的分布：换句话说，知道一个属性不会提供任何其他属性的信息。 例如，虽然身高和眼睛颜色是独立的，但身高和体重是独立的就不那么可信了。 因此，任何基于人的属性（如身高和体重）是独立的假设的算法给出的输出都是不可信的。这个项目的目标是扩展我们对这类问题的理论的了解，同时去除一些数学上方便的假设，如独立性。 所使用的工具集中在离散傅立叶分析，但涉及许多其他数学技术，如泛函分析和有限群的表示理论。 一种重复出现的技术是应用“噪声敏感度”方法，该方法基于函数在某些输入上的值与该输入的相邻值的相似程度来量化函数的复杂性。 在许多情况下，目标是证明某些类函数的傅立叶谱是可预测的;通常，这种可预测性是机器学习算法的关键组成部分。这个项目的更广泛的目标是发现数学和计算机科学之间的新联系，特别关注机器学习激发的问题。对潜在问题的回答将对理论家有用，并可能导致更好地应用机器学习算法。 此外，提出的数学问题是有趣的独立的机器学习连接。 本计画所考虑的问题，将为本科生与硕士生提供一个令人振奋的研究机会。