AF: Small: Learning in Worst-Case Noise Models

机器学习算法在计算机科学中无处不在，在数据挖掘、分类和排名方面有着重要的应用。这些算法通常应用于包含相当大一部分噪声训练示例的数据集。该项目侧重于开发学习算法，该算法可以在存在噪声数据集的情况下取得成功，这些数据集已被潜在的敌对或恶意方式破坏。能够容忍这些类型的最坏情况噪声的算法对于复杂机器学习系统的部署至关重要，因为现实世界的数据集（例如，与垃圾邮件检测相关的数据）通常以不可预测的方式存在噪声。以前关于噪声存在下的学习的工作主要集中在对噪声如何应用（例如，独立于每个数据点）有很强假设的模型上。这个项目的智力价值在于理解在最坏情况噪声模型中与学习相关的优化问题的计算复杂性。更具体地说，该项目将设计算法，可以找到一个分类器，其误差与一大类概念中的最佳函数相竞争。为了设计这些算法，该项目将证明新的结构结果，即布尔函数类可以如何很好地近似于各种经过充分研究的概率分布。此外，该项目将通过减少密码学和计算复杂性中众所周知的难题来探索关于对抗性噪声的学习函数的硬度结果。这个项目更广泛的影响是有可能在科学的各种应用领域实现更强大的分类工具，如计算生物学（如蛋白质检测）和语言学（如文本分类）。此外，PI将开发一门新的研究生课程，进一步推动机器学习理论中计算方法和统计方法之间的关系。

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.