Slides for Grammatical Inference
Here are various versions of my slides about grammatical inference.
- I updated all my slides for the CLS summer school
that took place in Zadar, in August 2010:
- Introduction. (slides, pdf) Motivations and applications. One extensive example. Convergence and complexity issues.
- Learning from an informant. (slides, pdf) Complexity issues. State merging algorithms. Gold's algorithm. RPNI. EDSM.
- Learning from text. (slides, pdf) Identification from text is difficult. Different negative results. Learning k-testable machines and k-reversible languages.
- Learning probabilistic finite automata. (slides, pdf) What are probabilistic finie automata? How to use them. Distances between distributions. Evaluation issues. Algorithms Alergia, DSAI and MDI.
- Learning context-free grammars. (slides, pdf) Why the problem is complicated. A presentation of a number of algorithms and heuristics.
- Active Learning. (slides, pdf) Learning with queries. Negative results. Learning DFA from membershp and equivalence queries. The Zulu competition.
- I gave a tutorial on active learning at ICGI 2010, in Valencia. The slides are similar to those from Zadar, but there is a (I hope nice) paper that covered the topic.
- I gave a 3 hour course in July 2010 at the Pascal bootcamp
The slides are here
and the filmed talk can be seen here.
Earlier versions of slides were prepared for a series of courses given
at the International
PhD School in Formal Languages and Applications at the
University of Tarragona, in the Ecole
doctorale de Saint-Etienne, and the Master
in Web Intelligence of Saint-Etienne. Shorter versions
corresponded to tutorials given at the conferences ICML 1999, CAP
2001,ECML/PKDD 2003, IJCAI 2005 and ICML
The slides were also presented at the
Analysis of Patterns school at Centre "Ettore Majorana" for
Scientific Culture, Erice, Italy
October 28 - November 6, 2005. These
talks were filmed, and can be viewed here.
I have written a bibliographic
survey of the theme. An introduction
to grammatical inference for theoretical computer scientists
was written by Henning
Fernau and myself. A similar introduction,
but this time for computational linguists was written by Pieter
Adriaans and Menno
I have tried to put all this together in the book published in April 2010: Grammatical Inference: Learning Automata and Grammars.
the author / More information