Biography:Dana Angluin

From HandWiki
Short description: Professor of computer science
Dana Angluin
Alma materUniversity of California, Berkeley
Known for
  • L* Algorithm
  • Query learning
  • Exact learning
  • Population protocols
Scientific career
Fields
  • Computer Science
  • Machine Learning
InstitutionsYale University
ThesisAn Application of the Theory of Computational Complexity to the Study of Inductive Inference (1976)
Doctoral advisorManuel Blum[1]
Doctoral studentsEhud Shapiro

Dana Angluin is a professor emeritus of computer science at Yale University.[2] She is known for foundational work in computational learning theory[3][4][5] and distributed computing.[6]

Education

Angluin received her B.A. (1969) and Ph.D. (1976) at University of California, Berkeley.[7] Her thesis, entitled "An application of the theory of computational complexity to the study of inductive inference" [8] was one of the first works to apply complexity theory to the field of inductive inference.[9] Angluin joined the faculty at Yale in 1979.[9]

Research

Angluin's work helped establish the theoretical foundations of machine learning.[10]


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.[11] 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.[12] 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".[12]

Learning from Noisy Examples

Angluin's work on learning from noisy examples[13] has also been very influential to the field of machine learning.[10] 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.[10]

Other Achievements

In distributed computing, she co-invented the population protocol model and studied the problem of consensus.[6][14] In probabilistic algorithms, she has studied randomized algorithms for Hamiltonian circuits and matchings.[15][9][16]

Angluin helped found the Computational Learning Theory (COLT) conference, and has served on program committees and steering committees for COLT[17][18][19] She served as an area editor for Information and Computation from 1989–1992.[20][21] She organized Yale's Computer Science Department's Perlis Symposium in April 2001: "From Statistics to Chat: Trends in Machine Learning".[22] 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.[23][10]

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

Selected publications

  • Dana Angluin (1988). Queries and concept learning. Machine Learning. 2 (4): 319-342.
  • Dana Angluin (1987). "Learning Regular Sets from Queries and Counter-Examples". Information and Control 75 (2): 87–106. doi:10.1016/0890-5401(87)90052-6. http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf. 
  • Dana Angluin and Philip Laird (1988). Learning from noisy examples. Machine Learning 2 (4), 343-370.
  • Dana Angluin and Leslie Valiant (1979). Fast probabilistic algorithms for Hamiltonian circuits and matchings. Journal of Computer and system Sciences 18 (2), 155-193
  • Dana Angluin (1980). "Finding Patterns Common to a Set of Strings". Journal of Computer and System Sciences 21: 46–62. doi:10.1016/0022-0000(80)90041-0. 
  • Dana Angluin (1980). "Inductive Inference of Formal Languages from Positive Data". Information and Control 45 (2): 117–135. doi:10.1016/s0019-9958(80)90285-5. http://www-personal.umich.edu/~yinw/papers/Angluin80.pdf.  [4]
  • Dana Angluin, James Aspnes, Zoë Diamadi, Michael J Fischer, René Peralta (2004). Computation in networks of passively mobile finite-state sensors. Distributed computing 18 (4), 235-253.
  • Dana Angluin (1976). An Application of the Theory of Computational Complexity to the Study of Inductive Inference (Ph.D.). University of California at Berkeley.

See also

References

  1. Dana Angluin at the Mathematics Genealogy Project
  2. "Dana Angluin, B.A., Ph.D. University of California at Berkeley, 1969, 1976. Joined Yale Faculty 1979. | Computer Science" (in en). https://cpsc.yale.edu/people/dana-angluin. 
  3. Angluin, Dana (April 1988). "Queries and concept learning". Machine Learning 2 (4): 319–342. doi:10.1007/bf00116828. ISSN 0885-6125. 
  4. Angluin, Dana (November 1987). "Learning regular sets from queries and counterexamples". Information and Computation 75 (2): 87–106. doi:10.1016/0890-5401(87)90052-6. ISSN 0890-5401. 
  5. Angluin, Dana; Laird, Philip (April 1988). "Learning from noisy examples". Machine Learning 2 (4): 343–370. doi:10.1007/bf00116829. ISSN 0885-6125. 
  6. 6.0 6.1 Angluin, Dana; Aspnes, James; Diamadi, Zoë; Fischer, Michael J.; Peralta, René (2006-03-01). "Computation in networks of passively mobile finite-state sensors" (in en). Distributed Computing 18 (4): 235–253. doi:10.1007/s00446-005-0138-3. ISSN 1432-0452. https://doi.org/10.1007/s00446-005-0138-3. 
  7. "Dana Angluin, B.A., Ph.D. University of California at Berkeley, 1969, 1976. Joined Yale Faculty 1979. | Computer Science" (in en). https://cpsc.yale.edu/people/dana-angluin. 
  8. Angluin, Dana Charmian (1976). An Application of the Theory of Computational Complexity to the Study of Inductive Inference (PhD Thesis thesis). University of California, Berkeley.
  9. 9.0 9.1 9.2 "Dana Angluin, B.A., Ph.D. University of California at Berkeley, 1969, 1976. Joined Yale Faculty 1979. | Computer Science". http://cpsc.yale.edu/people/dana-angluin. 
  10. 10.0 10.1 10.2 10.3 "Dana Angluin | Faculty of Arts and Sciences". https://fas.yale.edu/book/faculty-retirement-tributes-2021/dana-angluin. 
  11. Grinchtein, Olga; Jonsson, Bengt; Leucker, Martin (October 2010). "Learning of event-recording automata" (in en). Theoretical Computer Science 411 (47): 4029–4054. doi:10.1016/j.tcs.2010.07.008. https://linkinghub.elsevier.com/retrieve/pii/S0304397510003944. 
  12. 12.0 12.1 Vaandrager, Frits (2017-01-23). "Model learning" (in en). Communications of the ACM 60 (2): 86–95. doi:10.1145/2967606. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/2967606. 
  13. Angluin, Dana; Laird, Philip (April 1988). "Learning from noisy examples" (in en). Machine Learning 2 (4): 343–370. doi:10.1007/BF00116829. ISSN 0885-6125. http://link.springer.com/10.1007/BF00116829. 
  14. Angluin, Dana; Aspnes, James; Eisenstat, David (2008-07-01). "A simple population protocol for fast robust approximate majority" (in en). Distributed Computing 21 (2): 87–102. doi:10.1007/s00446-008-0059-z. ISSN 1432-0452. https://doi.org/10.1007/s00446-008-0059-z. 
  15. Angluin, Dana; Valiant, Leslie G. (1977). "Fast probabilistic algorithms for hamiltonian circuits and matchings". Proceedings of the ninth annual ACM symposium on Theory of computing - STOC '77. New York, New York, USA: ACM Press. pp. 30–41. doi:10.1145/800105.803393. ISBN 9781450374095. http://dx.doi.org/10.1145/800105.803393. 
  16. D Angluin (1976). "An Application of the Theory of Computational Complexity to the Study of Inductive Inference." Available from ProQuest Dissertations & Theses Global. (302813707)
  17. [1], COLT '89 Proceedings
  18. [2], COLT '02 Proceedings
  19. [3], COLT '08 Proceedings
  20. "Editorial Board". Information and Computation 82 (1): i. 1989. doi:10.1016/0890-5401(89)90061-8. 
  21. "Editorial Board". Information and Computation 99 (1): i. 1992. doi:10.1016/0890-5401(92)90023-9. 
  22. "Symposium will explore 'trends in machine learning'". Yale Bulletin and Calendar. April 20, 2001. http://www.yale.edu/opa/arc-ybc/v29.n27/story11.html. 
  23. "DeVane Medalists | Yale Phi Beta Kappa". https://pbk.yalecollege.yale.edu/information/devane-medalists. 
  24. Case, Bettye Anne; Leggett, Anne M. (2005) (in en). Complexities: Women in Mathematics. Princeton University Press. p. 60. ISBN 9781400880164. 

External links