AitF: FULL: From Worst-Case to Realistic-Case Analysis for Large Scale Machine Learning Algorithms

这个项目的目的是开发数学模型、分析和算法，以促进大规模机器学习系统的设计和理解。近年来，机器学习在一系列应用中得到了广泛的应用，我们也看到在学习过程的理论理解方面取得了重大进展。然而，尽管取得了这些成功，理论和应用之间仍然存在着鸿沟。例如，应用程序通常在理论告诉我们在最糟糕的情况下难以解决的问题上证明是成功的。此外，随着现代机器学习应用从单一任务的学习扩展到同时学习多个任务，需要新的理论来分析这些更大规模的多任务学习环境。这个项目旨在通过开发和应用针对学习问题的现实案例分析的理论来弥合这一差距，这些理论捕捉到了使应用程序能够成功的结构，即使理论分析表明在最糟糕的情况下也不可能这样做。这项工作将以Nell和InMind这两个当前的学习系统的核心问题为指导，这两个学习系统解决了大规模多任务机器学习问题，用于阅读Web并为数百个相互连接的手机用户提供高度个性化的电子助手。更具体地说，这个项目有三个主要组成部分：(1)开发对大规模机器学习至关重要的聚类、约束优化和相关优化任务的计算高效算法，并在自然、现实的非最坏情况分析模型。(2)开发多任务和终身学习的基础和实用算法，利用显式和隐式结构来最小化包括计算时间和人工标记工作在内的关键资源，并解决诸如隐私等关键限制。(3)应用为解决当前两个大规模学习系统Nell和InMind中的关键挑战而开发的算法。所提出的工作将有助于大规模机器学习应用的开发，并在现代机器学习和理论计算机科学中的多个重要领域之间建立重要的联系。除了就与该项目相关的主题向学生提供建议外，研究进展(关于多任务学习、终身学习和集群)将被纳入CMU几门课程的课程中，课程材料将在万维网上提供。基于这项研究的课程项目将提供给CMU机器学习入门课程的学生，该课程每年招收600多名学生。此外，寻求本科生毕业论文或自主学习主题的学生也可以从事与该项目相关的研究。

The aim of this project is to develop mathematical models, analysis, and algorithms that will advance both the design and understanding of large-scale machine learning systems. In recent years, machine learning has come into widespread use across a range of applications, and we have also seen significant advances in the theoretical understanding of learning processes. Yet despite these successes, there remains a gulf between theory and application. For example, applications often demonstrate success on problems that theory tells us are intractable in the worst case. Furthermore, as modern machine learning applications scale up from learning of single tasks to learning many tasks simultaneously, new theory is needed to analyze these larger scale multi-task learning settings. This project aims to bridge this gap by developing and applying theory targeted toward realistic-case analysis of learning problems, which capture the structures that enable applications to succeed even when theoretical analyses show the impossibility of doing so in the worst case. This work will be guided by problems at the core of NELL and InMind, two current learning systems that address large-scale multi-task machine learning problems, for reading the web and providing highly personalized electronic assistants to hundreds of interconnected mobile phone users.More specifically, this project has three main components:(1) To develop computationally efficient algorithms for clustering, constrained optimization, and related optimization tasks crucial to large-scale machine learning, with provable guarantees under natural, realistic non-worst-case analysis models.(2) To develop foundations and practical algorithms for multi-task and life-long learning that exploit explicit and implicit structure to minimize key resources including computation time and human labeling effort, as well as address key constraints such as privacy.(3) To apply the algorithms developed to solve key challenges in two current large-scale learning systems, NELL and InMind.The proposed work will aid the development of large-scale machine learning applications, as well as create important connections between multiple areas of significant importance in modern machine learning and theoretical computer science. In addition to advising students on topics connected to this project, research progress (on multi-task learning, life-long learning, and clustering) will be integrated in the curricula of several courses at CMU and course materials will be made available on the world wide web. Course projects based on this research will be available to students in the introductory machine learning course at CMU, which enrolls over 600 students each year. In addition, students seeking topics for undergraduate thesis or independent study may also pursue research affiliated with this project.