Dana Angluin is interested in algorithmic models of learning, both for their intrinsic interest and for their potential in the creation of ``smarter'' software. Learning components will increasingly be included in software, and it is important to have a clear understanding of their theoretical and practical strengths and limitations. The theory of computation provides useful tools for the specification of learning problems and the analysis of learning algorithms.
Progress in the areas of computational learning theory has produced many exciting models, results, and algorithms. For example, for the question of learning an unknown deterministic finite automaton, Kearns and Valiant have shown that without queries it is as hard as factoring, Angluin has shown that there is a polynomial-time algorithm if queries are available, and Rivest and Schapire have extended the algorithm to a map-learning scenario. Many other concept classes have been shown to be polynomial-time learnable with queries, and still others, such as general boolean formulas, nondeterministic finite automata, and context-free languages, have been shown to be as hard as factoring even when queries are available.
However, we have just begun to explore the huge body of phenomena related to learning. There are many fascinating and important issues to be explored, for example, the representation of concepts, errors, incomplete information, prior knowledge, and the role of teaching.