CAREER: The Computational Complexity of Halfspace-Based Learning

职业：基于半空间的学习的计算复杂性

• 批准号: 0643829
• 负责人: Adam Klivans
• 金额: $ 40万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-02-01 至 2014-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0643829&HistoricalAwards=false
• 关键词: CAREER; Computational; Complexity; Halfspace; Based

Algorithms for learning to classify data have important applications in almost every area of computer science including data mining, computer vision, compiler design, operating system design, speech recognition, computational biology, computational game theory, computational neuroscience, and traditional algorithm design. A common, simplifying assumption in learning theory is that labeled data can be classified by a halfspace in many dimensions. The intellectual merit of this research involves understanding the computational complexity of fundamental halfspace-based learning tasks. The investigators focus on the following three challenges: 1) develop algorithms for learning a halfspace in the presence of noise; 2) efficiently learn intersections of halfspaces; 3) prove hardness results for learning various halfspace-based concept classes. In terms of broader impact, as alluded to above, this research gives new tools for practitioners in a variety of fields including computational biology, economics, and statistics.The research relies heavily on new techniques from approximation theory and harmonic analysis to give provably efficient algorithms for learning halfspaces (also known as linear threshold functions) in malicious noise models with respect to many natural distributions. A recent polynomial-regression algorithm due to the principal investigator and his colleagues for agnostically learning halfspaces generalizes previous work in Fourier-based learning. The investigators study other applications of these techniques to discover new algorithms for learning intersections of halfspaces and, more generally, arbitrary convex sets with respect to natural distributions. In addition, the investigator applies properties of new lattice-based cryptosystems to show the intractability of learning intersections of halfspaces in distribution-free models.

学习分类数据的算法在计算机科学的几乎每个领域都有重要的应用，包括数据挖掘、计算机视觉、编译器设计、操作系统设计、语音识别、计算生物学、计算博弈论、计算神经科学和传统算法设计。 学习理论中一个常见的、简化的假设是，标记数据可以通过多个维度的半空间进行分类。这项研究的智力价值涉及理解基本的基于半空间的学习任务的计算复杂性。 研究人员重点关注以下三个挑战：1）开发在存在噪声的情况下学习半空间的算法； 2）有效学习半空间的交集； 3）证明学习各种基于半空间的概念类的硬度结果。 就更广泛的影响而言，正如上面提到的，这项研究为包括计算生物学、经济学和统计学在内的各个领域的从业者提供了新的工具。这项研究在很大程度上依赖于逼近论和调和分析的新技术，以提供可证明有效的算法来学习恶意噪声模型中关于许多自然分布的半空间（也称为线性阈值函数）。 首席研究员和他的同事最近提出的一种用于不可知学习半空间的多项式回归算法概括了之前基于傅立叶的学习的工作。 研究人员研究了这些技术的其他应用，以发现用于学习半空间交集的新算法，更一般地说，学习关于自然分布的任意凸集。 此外，研究人员应用新的基于格的密码系统的特性来展示在无分布模型中学习半空间交集的困难性。