Dana Angluin

Last updated
Dana Angluin
Alma mater University of California, Berkeley
Known for
  • L* Algorithm
  • Query learning
  • Exact learning
  • Population protocols
Scientific career
Fields
Institutions Yale University
Thesis An Application of the Theory of Computational Complexity to the Study of Inductive Inference (1976)
Doctoral advisor Manuel Blum [1]
Doctoral students Ehud 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]

Contents

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

See also

Related Research Articles

<span class="mw-page-title-main">Kolmogorov complexity</span> Measure of algorithmic complexity

In algorithmic information theory, the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory.

Hypercomputation or super-Turing computation is a set of models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word infer means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in Europe dates at least to Aristotle. Deduction is inference deriving logical conclusions from premises known or assumed to be true, with the laws of valid inference being studied in logic. Induction is inference from particular evidence to a universal conclusion. A third type of inference is sometimes distinguished, notably by Charles Sanders Peirce, contradistinguishing abduction from induction.

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.

Algorithmic learning theory is a mathematical framework for analyzing machine learning problems and algorithms. Synonyms include formal learning theory and algorithmic inductive inference. Algorithmic learning theory is different from statistical learning theory in that it does not make use of statistical assumptions and analysis. Both algorithmic and statistical learning theory are concerned with machine learning and can thus be viewed as branches of computational learning theory.

<span class="mw-page-title-main">Computational learning theory</span> Theory of machine learning

In computer science, computational learning theory is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms.

Solomonoff's theory of inductive inference is a mathematical theory of induction introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes' rule and some universal prior, that is, a prior that assigns a positive probability to any computable theory.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

Language identification in the limit is a formal model for inductive inference of formal languages, mainly by computers. It was introduced by E. Mark Gold in a technical report and a journal article with the same title.

Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."

<span class="mw-page-title-main">Grammar induction</span>

Grammar induction is the process in machine learning of learning a formal grammar from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. More generally, grammatical inference is that branch of machine learning where the instance space consists of discrete combinatorial objects such as strings, trees and graphs.

In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. The term was introduced by Mark Burgin, whose book "Super-recursive algorithms" develops their theory and presents several mathematical models. Turing machines and other mathematical models of conventional algorithms allow researchers to find properties of recursive algorithms and their computations. In a similar way, mathematical models of super-recursive algorithms, such as inductive Turing machines, allow researchers to find properties of super-recursive algorithms and their computations.

<i>Information and Computation</i> Academic journal

Information and Computation is a closed-access computer science journal published by Elsevier. The journal was founded in 1957 under its former name Information and Control and given its current title in 1987. As of July 2022, the current editor-in-chief is David Peleg. The journal publishes 12 issues a year.

In computational learning theory, induction of regular languages refers to the task of learning a formal description of a regular language from a given set of example strings. Although E. Mark Gold has shown that not every regular language can be learned this way, approaches have been investigated for a variety of subclasses. They are sketched in this article. For learning of more general grammars, see Grammar induction.

Inductive programming (IP) is a special area of automatic programming, covering research from artificial intelligence and programming, which addresses learning of typically declarative and often recursive programs from incomplete specifications, such as input/output examples or constraints.

<span class="mw-page-title-main">William Gasarch</span> American computer scientist

William Ian Gasarch is an American computer scientist known for his work in computational complexity theory, computability theory, computational learning theory, and Ramsey theory. He is currently a professor at the University of Maryland Department of Computer Science with an affiliate appointment in Mathematics.

<span class="mw-page-title-main">Glossary of artificial intelligence</span> List of definitions of terms and concepts commonly used in the study of artificial intelligence

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

Viliam Geffert is a Slovak theoretical computer scientist known for his contributions to the computational complexity theory in sublogarithmic space and to the state complexity of two-way finite automata. He has also developed new in-place sorting algorithms. He is a professor and the head of the computer science department at the P. J. Šafárik University in Košice.

Giovanni Pighizzini is an Italian theoretical computer scientist known for his work in formal language theory and particularly in state complexity of two-way finite automata. He earned his PhD in 1993 from the University of Milan, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual Descriptional Complexity of Formal Systems academic conference since 2006.

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". cpsc.yale.edu. Retrieved 2021-12-01.
  3. ↑ Angluin, Dana (April 1988). "Queries and concept learning". Machine Learning. 2 (4): 319–342. doi: 10.1007/bf00116828 . ISSN   0885-6125. S2CID   11357867.
  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. S2CID   29767720.
  6. 1 2 Angluin, Dana; Aspnes, James; Diamadi, Zoë; Fischer, Michael J.; Peralta, René (2006-03-01). "Computation in networks of passively mobile finite-state sensors". Distributed Computing. 18 (4): 235–253. doi:10.1007/s00446-005-0138-3. ISSN   1432-0452. S2CID   2802601.
  7. ↑ "Dana Angluin, B.A., Ph.D. University of California at Berkeley, 1969, 1976. Joined Yale Faculty 1979. | Computer Science". cpsc.yale.edu. Retrieved 2020-11-08.
  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. 1 2 3 "Dana Angluin, B.A., Ph.D. University of California at Berkeley, 1969, 1976. Joined Yale Faculty 1979. | Computer Science". cpsc.yale.edu. Retrieved 2016-12-11.
  10. 1 2 3 4 "Dana Angluin | Faculty of Arts and Sciences". fas.yale.edu. Retrieved 2023-10-10.
  11. ↑ Grinchtein, Olga; Jonsson, Bengt; Leucker, Martin (October 2010). "Learning of event-recording automata". Theoretical Computer Science. 411 (47): 4029–4054. doi:10.1016/j.tcs.2010.07.008. S2CID   5738947.
  12. 1 2 Vaandrager, Frits (2017-01-23). "Model learning". Communications of the ACM. 60 (2): 86–95. doi:10.1145/2967606. ISSN   0001-0782. S2CID   10955647.
  13. ↑ Angluin, Dana; Laird, Philip (April 1988). "Learning from noisy examples". Machine Learning. 2 (4): 343–370. doi:10.1007/BF00116829. ISSN   0885-6125. S2CID   29767720.
  14. ↑ Angluin, Dana; Aspnes, James; Eisenstat, David (2008-07-01). "A simple population protocol for fast robust approximate majority". Distributed Computing. 21 (2): 87–102. doi:10.1007/s00446-008-0059-z. ISSN   1432-0452. S2CID   2652934.
  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. S2CID   2624407.
  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. ↑ , COLT '89 Proceedings
  18. ↑ , COLT '02 Proceedings
  19. ↑ , 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. Archived from the original on April 18, 2009.
  23. ↑ "DeVane Medalists | Yale Phi Beta Kappa". pbk.yalecollege.yale.edu. Retrieved 2023-10-10.
  24. ↑ Case, Bettye Anne; Leggett, Anne M. (2005). Complexities: Women in Mathematics. Princeton University Press. p. 60. ISBN   9781400880164.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.