AF: Small : Collaborative Research: The Polynomial Method for Learning

AF：小：协作研究：多项式学习方法

• 批准号: 0915893
• 负责人: Ryan O'Donnell
• 金额: $ 25万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915893&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Polynomial

The broad goal of this line of research is to give a principled answer to the question, "What sort of data is efficiently learnable, and by what algorithms?" The current state-of-the-art in machine learning is that there is an overwhelming number of possible algorithms that can be tried on a new machine learning problem, with no clear understanding of which techniques can be expected to work on which problems. Further, it is often the case that machine learning algorithms that work well "in theory" do not perform as well "in practice," and vice versa. The PIs have outlined a plan for resolving these difficulties, finding a unification of disparate methods via the Polynomial Method, and investigating how efficient this method can be. On a more immediate level the PIs will aim for broad impact through advising and guiding graduate students and widely disseminating research results.Specifically, the PIs will investigate the effectiveness of the "Polynomial Method" in machine learning theory. The PIs observe that nearly all learning algorithms, in theory and in practice, can be viewed as fitting a low-degree polynomial to data. The PIs plan to systematically develop this Polynomial Method of learning by working on the following three strands of research: 1. Understand the extent to which low-degree polynomials can fit different natural types of target functions, under various data distributions and noise rates. This research involves novel methods from approximation theory and analysis.2. Develop new algorithmic methods for finding well-fitting polynomials when they exist. Here the PIs will work to adapt results in geometry and probability for the purposes of identifying and eliminating irrelevant data.3. Delimit the effectiveness of the Polynomial Method. The PIs will show new results on the computational intractability of learning intersections of linear separators, and on learning linear separators with noise.

这一系列研究的广泛目标是对这个问题给出一个原则性的答案，“什么样的数据是有效学习的，通过什么算法？”“目前机器学习的最新技术是，有大量的可能算法可以在新的机器学习问题上尝试，但没有明确的理解哪些技术可以用于解决哪些问题。 此外，通常情况下，“理论上”工作良好的机器学习算法在“实践中”表现不佳，反之亦然。 PI已经概述了解决这些困难的计划，通过多项式方法找到不同方法的统一，并研究这种方法的效率。 在更直接的层面上，PI将通过指导和指导研究生以及广泛传播研究成果来产生广泛的影响。具体来说，PI将调查机器学习理论中“多项式方法”的有效性。PI观察到，几乎所有的学习算法，在理论上和实践中，都可以被视为将低次多项式拟合到数据中。 PI计划通过以下三个方面的研究来系统地开发这种多项式学习方法：1。了解在各种数据分布和噪声率下，低次多项式可以拟合不同自然类型的目标函数的程度。这项研究涉及新的方法，从近似理论和分析.开发新的算法方法，以便在存在良好拟合的多项式时找到它们。 在这里，PI将工作以适应几何和概率的结果，以识别和消除不相关的数据。确定多项式方法的有效性。 PI将显示新的结果，学习线性分离器的交叉点的计算困难性，并学习线性分离器与噪声。