AF: Small: Learning in Worst-Case Noise Models

AF：小：在最坏情况噪声模型中学习

• 批准号: 1018829
• 负责人: Adam Klivans
• 金额: $ 49.99万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018829&HistoricalAwards=false
• 关键词: AF; Small; Learning; Worst; Case

Machine Learning algorithms are ubiquitous in computer science with important applications to data-mining, classification, and ranking. These algorithms are typically applied to data sets that contain a sizable fraction of noisy training examples. This project focuses on developing learning algorithms that can succeed in the presence of noisy data sets that have been corrupted in a potentially adversarial or malicious manner. Algorithms that can tolerate these types of worst-case noise are critical for the depolyment of complex machine learning systems, as real-world data sets (for example, data related to spam detection) are often noisy in unpredictable ways. Previous work on learning in the presence of noise focused on models with strong assumptions on how the noise is applied (e.g., independently for each data point).The intellectual merit of this project lies in understanding the computational complexity of optimization problems associated with learning in worst-case noise models. More specifically, the project will design algorithms that can find a classifier whose error is competitive with the best function from a large class of concepts. In order to design these algorithms, the project will prove new structural results on how well classes of Boolean functions can be approximated with respect to a variety of well-studied probability distributions. Additionally, the project will explore hardness results for learning functions with respect to adversarial noise via reductions to notoriously difficult problems in cryptography and computational complexity.The broader impact of this project is the potential to realize more powerful classification tools in a variety of application areas in the sciences such as computational biology (e.g., protein detection) and linguistics (e.g., text categorization). Additionally, the PI will develop a new graduate course that furthers the relationship between computational and statistical methods in machine learning theory.

机器学习算法在计算机科学中无处不在，在数据挖掘，分类和排名中进行了重要应用。 这些算法通常应用于包含相当一部分嘈杂训练示例的数据集。 该项目的重点是开发学习算法，这些算法可以在以潜在的对抗性或恶意方式破坏的嘈杂数据集中成功。 可以忍受这些类型的最坏情况噪声的算法对于复杂机器学习系统的变化至关重要，因为实际数据集（例如，与垃圾邮件检测有关的数据）通常以无法预测的方式嘈杂。 在存在噪声中学习的先前研究的工作集中在模型上，该模型对如何应用噪声进行了强烈的假设（例如，对于每个数据点独立）。该项目的智力优点在于理解与最差噪声模型中与学习相关的优化问题的计算复杂性。 更具体地说，该项目将设计算法，该算法可以找到一个分类器，该分类器的错误与大量概念的最佳功能具有竞争力。 为了设计这些算法，该项目将证明有关相对于各种研究良好的概率分布的布尔函数类别的效果如何。 此外，该项目将通过减少臭名昭著的加密和计算复杂性问题来探索学习功能的硬度结果。该项目的臭名昭著的困难问题。该项目的更广泛的影响是有潜力在科学的各种应用领域中实现更强大的分类工具，例如计算生物学（例如，蛋白质检测）和语言学类别（例如，蛋白质检测）。 此外，PI将开发新的研究生课程，以进一步发展机器学习理论中计算方法和统计方法之间的关系。