AF: Small: Linear Algebra++ and applications to machine learning

AF：小：线性代数及其在机器学习中的应用

• 批准号: 1527371
• 负责人: Sanjeev Arora
• 金额: $ 45万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527371&HistoricalAwards=false
• 关键词: AF; Small; Linear; Algebra++; applications

Many areas of unsupervised learning (i.e, learning with data that has not been labeled by humans) currently rely on heuristic algorithms that lack provable guarantees on solution quality or running time. In fact the underlying problems - as currently formulated - are often known to be computationally intractable (NP-hard, to use a technical term). This proposal identifies a big set of these problems that can be seen as twists - involving constraints such as nonnegativity and sparsity - on classical linear algebra problems like solving linear systems, rank computation, and eigenvalues/eigenvectors. The PI has proposed calling this set of problems collectively as Linear Algebra++. The project will seek to develop algorithms with provable guarantees for these problems. The methodology will be to make suitable assumptions about the structure of realistic inputs. The algorithms will be applied to problems in unsupervised learning, in areas such as topic modeling, natural language processing, semantic embeddings, sparse principle components analysis (PCA), deep nets, etc.The work will lead to new and more efficient algorithms for big data processing that will come with provable guarantees of quality. It will bring new rigorous approaches to machine learning. (Some recent work of the PI shows that the new rigorous approaches can be quite practical.) It will advance the state of art in theoretical computer science by expanding its range and its standard toolkit of algorithms. It will contribute fundamentally new primitives to classical linear algebra and applied mathematics.The project will train a new breed of graduate students who will be fluent both in theoretical algorithms and machine learning. The PI has a track record in this kind of work and training during the past few years and will continue this including working with undergrads and Research Experiences for Undergraduates (REU) students. Any new algorithms discovered as part of this project will be released as open source code. The PI also plans a series of other outreach activities in the next few years including (a) A workshop. (b) A special semester or year at the Simons Institute in 2016-17 on provable bounds in machine learning which he will coorganize. (c) A new book on graduate algorithms based upon his new grad course, which tries to re-orient algorithms training for today's computer science problems. (d) A series of talks aimed at broad audiences, of which he gives several each year.The techniques will build upon recent progress by the PI and others on problems such as nonnegative matrix factorization, sparse coding, alternating minimization etc. They involve average case analysis, classical linear algebra, convex optimization, numerical analysis, etc., as well involve completely new ideas. They could have a transformative effect on machine learning and algorithms.

无监督学习的许多领域（即使用未被人类标记的数据进行学习）目前依赖于启发式算法，这些算法缺乏对解决方案质量或运行时间的可证明保证。事实上，基本的问题--如目前所表述的--通常被认为是计算上难以处理的（用一个技术术语来说，是NP难的）。这个建议确定了一大组这些问题，可以被视为扭曲-涉及约束，如非负性和稀疏性-在经典的线性代数问题，如解决线性系统，秩计算，和特征值/特征向量。PI建议将这组问题统称为Linear Algebra++。该项目将寻求为这些问题开发具有可证明保证的算法。该方法将对现实投入的结构作出适当的假设。 这些算法将应用于无监督学习中的问题，如主题建模，自然语言处理，语义嵌入，稀疏主成分分析（PCA），深度网络等领域。这项工作将导致新的，更有效的大数据处理算法，将带来可证明的质量保证。它将为机器学习带来新的严格方法。(Some PI最近的工作表明，新的严格方法可能非常实用。它将通过扩大其范围和标准算法工具包来推进理论计算机科学的最新发展。该项目将为经典线性代数和应用数学提供全新的基元，培养出一批精通理论算法和机器学习的新型研究生。PI在过去几年中在这种工作和培训方面有着良好的记录，并将继续这一点，包括与本科生和本科生（REU）学生的研究经验。 作为该项目的一部分发现的任何新算法都将作为开源代码发布。PI还计划在未来几年内开展一系列其他外联活动，包括：（a）举办一次讲习班。(b)2016-17年在西蒙斯研究所的一个特殊学期或一年，他将共同组织机器学习中的可证明边界。(c)一本关于研究生算法的新书，基于他的新格拉德课程，试图重新定位算法培训，以解决当今的计算机科学问题。(d)一系列针对广大听众的演讲，他每年都会做几次。这些技术将建立在PI和其他人在非负矩阵分解，稀疏编码，交替最小化等问题上的最新进展之上。它们涉及平均情况分析，经典线性代数，凸优化，数值分析等，也包含了全新的想法。它们可能会对机器学习和算法产生变革性的影响。