Dana Angluin

Research

Angluin's work helped establish the theoretical foundations of machine learning. After completing her Ph.D, Angluin got the opportunities of postdoctoral research positions working with Leslie Valiant at the Universities of Leeds and Edinburgh and with Ronald Book at the University of California, Santa Barbara. While she was there, she developed methods for analyzing randomized algorithm's and for learning formal languages from positive examples, while she also help create the influential Conference on Computational Learning Theory (COLT).

L* Algorithm

Angluin has written highly cited papers on computational learning theory, particularly in the context of learning regular language sets from membership and equivalence queries using the L* algorithm. This algorithm addresses the problem of identifying an unknown set. In essence, this algorithm is a way for programs to learn complex systems through the process of trial and error of educated guesses, to determine the behavior of the system. Through the responses, the algorithm can continue to refine its understanding of the system. This algorithm uses a minimally adequate Teacher (MAT) to pose questions about the unknown set. The MAT provides yes or no answers to membership queries, saying whether an input is a member of the unknown set, and equivalence queries, saying whether a description of the set is accurate or not. The Learner uses responses from the Teacher to refine its understanding of the set S in polynomial time. Though Angluin's paper was published in 1987, a 2017 article by computer science Professor Frits Vaandrager says "the most efficient learning algorithms that are being used today all follow Angluin's approach of a minimally adequate teacher".

Learning from Noisy Examples

Angluin's work on learning from noisy examples has also been very influential to the field of machine learning. Her work addresses the problem of adapting learning algorithms to cope with incorrect training examples (noisy data). Angluin's study demonstrates that algorithms exist for learning in the presence of errors in the data.

Other Achievements

In distributed computing, she co-invented the population protocol model and studied the problem of consensus. In probabilistic algorithms, she has studied randomized algorithms for Hamiltonian circuits and matchings.

Angluin helped found the Computational Learning Theory (COLT) conference, and has served on program committees and steering committees for COLT She served as an area editor for Information and Computation from 1989 to 1992. She organized Yale's Computer Science Department's Perlis Symposium in April 2001: "From Statistics to Chat: Trends in Machine Learning". She is a member of the Association for Computing Machinery and the Association for Women in Mathematics.

Angluin is highly celebrated as an educator, having won "three of the most distinguished teaching prizes Yale College has to offer": the Dylan Hixon Prize for Teaching Excellence in the Sciences, The Bryne/Sewall Prize for distinguished undergraduate teaching, and the Phi Beta Kappa DeVane Medal.

Angluin has also published works on Ada Lovelace and her involvement with the Analytical Engine.