CAREER: Efficient Learning Algorithms for Rich Function Classes

从数据中学习的系统目前在许多领域得到了广泛的应用，毫无疑问，这样的系统在未来会更加普遍。随着基于学习的系统的激增和应用于越来越大的领域，对可证明有效和高效的学习算法的需求相应地变得更加迫切。本文的研究目标就是设计和分析这些算法。更具体地说，在PI之前在这一领域的工作的基础上，本职业发展建议的两个主要研究目标是：1。在计算学习模型中开发能够有效学习丰富而重要的布尔函数类的算法。这项工作的主要重点将是(a)学习析取范式（DNF）公式，这是一种标准的知识表示形式；(b)学习各种布尔电路，这些电路比DNF公式更具表达性；(c)在不相关信息存在的情况下学习，即只依赖于一小部分未知领域属性的学习函数。我们注意到，在这一领域之前的工作已经发现了这些学习问题与布尔函数的复杂性理论结构问题之间的许多有趣和有用的联系。这项研究的一个重要方面（实际上也是我们方法论的一个关键组成部分）是继续探索和利用学习和复杂性之间的这些联系。开发和分析其他动机良好的计算学习模型，并在这些模型中为布尔函数类开发高效的学习算法。这里预期的研究方向包括(a)为没有有效的最坏情况算法的重要概念类提供有效的平均情况学习算法；(b)发展一种从非恶意随机示例中学习的理论；(c)研究量子计算在学习理论中的作用。这些方向中的每一个都有可能产生积极的学习结果，这些结果超出了当前标准学习模型所能达到的效果。这项研究计划与一项计划紧密结合，该计划旨在通过涉及各级学生的教育实现更广泛的影响。该教育计划的重点包括：(a)在哥伦比亚大学为本科生到高级研究生的目标受众开发新的计算学习理论课程和其他理论课程；(b)通过在本科课程和课外项目中积极参与研究，让本科生感受到研究的乐趣；(c)建议和指导研究生发展为研究人员和教育工作者；(d)通过定期召开理论小组会议和组织理论日等活动，在哥伦比亚大学建立一个强大的理论小组。

Systems which learn from data are by now widely used in many areas, and such systems will doubtless beeven more ubiquitous in the future. As learning-based systems proliferate and are applied to larger and larger domains, the need for provably effective and efficient learning algorithms grows correspondingly more acute.The object of the proposed research is to design and analyze such algorithms. More specifically, buildingon the PI's previous work in this area, the two main research goals of this career development proposal are:1. To develop algorithms which can efficiently learn rich and important classes of Boolean functionsin well-studied models of computational learning. Major focuses of this work will be (a)learning Disjunctive Normal Form (DNF) formulas, which are a standard form of knowledge representation;(b) learning various classes of Boolean circuits, which can be substantially more expressivethan DNF formulas; and (c) learning in the presence of irrelevant information, i.e. learning functionswhich depend only on a small unknown subset of domain attributes.We note that previous work in this area has uncovered many interesting and useful connections betweenthese learning problems and complexity-theoretic structural questions about Boolean functions.An important aspect of this research (and indeed a key component of our methodology) is to continueto explore and exploit these connections between learning and complexity.2. To develop and analyze other well-motivated models for computational learning, and to developefficient learning algorithms for Boolean function classes in these models. Anticipated researchdirections here include (a) giving efficient average-case learning algorithms for important conceptclasses for which no efficient worst-case algorithms are known; (b) developing a theory of learningfrom nonmalicious random examples; and (c) studying the role of quantum computation in learningtheory. Each of these directions has the potential to yield positive learning results which go beyondwhat can be achieved in current standard learning models.This research plan is closely integrated with a plan to achieve broader impact through education whichinvolves students at all levels. Highlights of the education plan include: (a) developing new computationallearning theory courses and other theory courses at Columbia University for target audiences ranging fromundergraduates to advanced graduate students; (b) introducing undergraduates to the excitement of researchby actively engaging them in research, both in undergraduate courses and in extracurricular projects; (c)advising and guiding graduate students in their development as researchers and educators; and (d) buildinga strong theory group at Columbia by maintaining regular theory group meetings and organizing events suchas Theory Day.