Dana Angluin

Last updated
Dana Angluin
Alma mater University of California, Berkeley (BA, PhD)
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">Inductive logic programming</span>

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical rather than mathematical induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

Hypercomputation or super-Turing computation is a set of hypothetical 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 could 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.

Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation.

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.

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.

<span class="mw-page-title-main">Gödel Prize</span> Computer science award

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.

In formal language theory, in particular in algorithmic learning theory, a class C of languages has finite thickness if every string is contained in at most finitely many languages in C. This condition was introduced by Dana Angluin as a sufficient condition for C being identifiable in the limit.

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, such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" 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."

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 parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As Anderson & Miller (1990) wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.

<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.

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.