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.