CAREER: Efficient Learning Algorithms for Rich Function Classes

点击翻译按钮获取中文摘要

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.