View source for Grammar induction

{{Short description|Machine-learning process}}
{{Machine learning|Problems}}

'''Grammar induction''' (or '''grammatical inference''')<ref name="Grammatical Inference">{{cite book|last=de la Higuera|first=Colin|title=Grammatical Inference: Learning Automata and Grammars|date=2010|publisher=Cambridge University Press|location=Cambridge|url=http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|access-date=2017-08-16|archive-date=2019-02-14|archive-url=https://web.archive.org/web/20190214170942/http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|url-status=dead}}</ref> is the process in [[Machine learning|machine learning]] of learning a [[Formal grammar|formal grammar]] (usually as a collection of ''re-write rules'' or ''productions'' or alternatively as a [[Finite-state machine|finite-state machine]] or automaton of some kind) 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.

==Grammar classes==

Grammatical inference has often been very focused on the problem of learning finite-state machines of various types (see the article [[Induction of regular languages]] for details on these approaches), since there have been efficient algorithms for this problem since the 1980s.

Since the beginning of the century, these approaches have been extended to the problem of inference of context-free grammars and richer formalisms, such as multiple context-free grammars and parallel multiple context-free grammars.
Other classes of grammars for which grammatical inference has been studied are [[Combinatory categorial grammar|combinatory categorial grammar]]s,<ref name="Kwiatkowski"/> stochastic context-free grammars,<ref>Clark, Alexander. "[https://www.aclweb.org/anthology/W01-0713 Unsupervised induction of stochastic context-free grammars using distributional clustering]." Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7. Association for Computational Linguistics, 2001.</ref> contextual grammars and pattern languages.

==Learning models==

The simplest form of learning is where the learning algorithm merely receives a set of examples drawn from the language in question: the aim is to learn the language from examples of it (and, rarely, from counter-examples, that is, example that do not belong to the language).
However, other learning models have been studied. One frequently studied alternative is the case where the learner can ask membership queries as in the exact query learning model or minimally adequate teacher model introduced by Angluin.<ref>{{cite journal|author=Dana Angluin |title=Learning Regular Sets from Queries and Counter-Examples |journal=Information and Control |year=1987 |volume=75 |issue=2 |pages=87–106 |url=http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |doi=10.1016/0890-5401(87)90052-6 |citeseerx=10.1.1.187.9414 |s2cid=11873053 |url-status=dead |archiveurl=https://web.archive.org/web/20131202232143/http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |archivedate=2013-12-02 }}</ref>

==Methodologies==
There is a wide variety of methods for grammatical inference. Two of the classic sources are {{Harvtxt|Fu|1977}} and {{Harvtxt|Fu|1982}}. {{Harvtxt|Duda|Hart|Stork|2001}} also devote a brief section to the problem, and cite a number of references. The basic trial-and-error method they present is discussed below. For approaches to infer subclasses of regular languages in particular, see ''[[Induction of regular languages]]''. A more recent textbook is de la Higuera (2010),<ref name = "Grammatical Inference"/> which covers the theory of grammatical inference of regular languages and finite state automata. D'Ulizia, Ferri and Grifoni<ref>D’Ulizia, A., Ferri, F., Grifoni, P. (2011) "[https://www.academia.edu/download/41900378/A_survey_of_grammatical_inference_method20160202-5760-79hwcu.pdf A Survey of Grammatical Inference Methods for Natural Language Learning] ", ''Artificial Intelligence Review'', Vol. 36, No. 1, pp. 1–27.</ref> provide a survey that explores grammatical inference methods for natural languages.

===Induction of probabilistic grammars ===

===Grammatical inference by trial-and-error===
The method proposed in Section 8.7 of {{Harvtxt|Duda|Hart|Stork|2001}} suggests successively guessing grammar rules (productions) and testing them against positive and negative observations.  The rule set is expanded so as to be able to generate each positive example, but if a given rule set also generates a negative example, it must be discarded.  This particular approach can be characterized as "hypothesis testing" and bears some similarity to Mitchel's version space algorithm. The {{Harvtxt|Duda|Hart|Stork|2001}} text provide a simple example which nicely illustrates the process, but the feasibility of such an unguided trial-and-error approach for more substantial problems is dubious.

=== Grammatical inference by genetic algorithms ===
Grammatical induction using [[Evolutionary algorithm|evolutionary algorithm]]s is the process of evolving a representation of the grammar of a target language through some evolutionary process. [[Formal grammar]]s can easily be represented as [[Tree (data structure)|tree structures]] of production rules that can be subjected to evolutionary operators. [[Algorithm]]s of this sort stem from the [[Genetic programming|genetic programming]] paradigm pioneered by [[Biography:John Koza|John Koza]]. Other early work on simple formal languages used the binary string representation of genetic algorithms, but the inherently hierarchical structure of grammars couched in the [[Extended Backus–Naur form|EBNF]] language made trees a more flexible approach.

Koza represented [[Lisp (programming language)|Lisp]] programs as trees. He was able to find analogues to the genetic operators within the standard set of tree operators. For example, swapping sub-trees is equivalent to the corresponding process of genetic crossover, where sub-strings of a genetic code are transplanted into an individual of the next generation. Fitness is measured by scoring the output from the functions of the Lisp code. Similar analogues between the tree structured lisp representation and the representation of grammars as trees, made the application of genetic programming techniques possible for grammar induction.

In the case of grammar induction, the transplantation of sub-trees corresponds to the swapping of production rules that enable the parsing of phrases from some language. The fitness operator for the grammar is based upon some measure of how well it performed in parsing some group of sentences from the target language. In a tree representation of a grammar, a terminal symbol of a production rule corresponds to a leaf node of the tree. Its parent nodes corresponds to a non-terminal symbol (e.g. a [[Social:Noun phrase|noun phrase]] or a [[Social:Verb phrase|verb phrase]]) in the rule set. Ultimately, the root node might correspond to a sentence non-terminal.

===Grammatical inference by greedy algorithms===
Like all [[Greedy algorithm|greedy algorithm]]s, greedy grammar inference algorithms make, in iterative manner, decisions that seem to be the best at that stage.
The decisions made usually deal with things like the creation of new rules, the removal of existing rules, the choice of a rule to be applied or the merging of some existing rules.
Because there are several ways to define 'the stage' and 'the best', there are also several greedy grammar inference algorithms.

These [[Context-free grammar|context-free grammar]] generating algorithms make the decision after every read symbol:
* Lempel-Ziv-Welch algorithm creates a context-free grammar in a deterministic way such that it is necessary to store only the start rule of the generated grammar.
* [[Sequitur algorithm|Sequitur]] and its modifications.

These context-free grammar generating algorithms first read the whole given symbol-sequence and then start to make decisions:
* [[Byte pair encoding]] and its optimizations.

===Distributional learning===
A more recent approach is based on distributional learning. Algorithms using these approaches have been applied to learning context-free grammars and mildly context-sensitive languages and have been proven to be correct and efficient for large subclasses of these grammars.<ref>Clark and Eyraud (2007) ''Journal of Machine Learning Research''; Ryo Yoshinaka (2011) ''Theoretical Computer Science''</ref>

===Learning of [[Pattern language (formal languages)|pattern languages]]===

Angluin defines a ''pattern'' to be "a string of constant symbols from Σ and '''variable symbols''' from a disjoint set".
The language of such a pattern is the set of all its nonempty ground instances  i.e. all strings resulting from consistent replacement of its variable symbols by nonempty strings of constant symbols.<ref group=note>The language of a pattern with at least two occurrences of the same variable is not regular due to the [[Pumping lemma for regular languages|pumping lemma]].</ref>
A pattern is called '''descriptive''' for a finite input set of strings if its language is minimal (with respect to set inclusion) among all pattern languages subsuming the input set.

Angluin gives a polynomial algorithm to compute, for a given input string set, all descriptive patterns in one variable ''x''.<ref group=note>''x'' may occur several times, but no other variable ''y'' may occur</ref>
To this end, she builds an automaton representing all possibly relevant patterns; using sophisticated arguments about word lengths, which rely on ''x'' being the only variable, the state count can be drastically reduced.<ref>{{cite journal| author=Dana Angluin| title=Finding Patterns Common to a Set of Strings| journal=Journal of Computer and System Sciences| year=1980| volume=21| pages=46–62| doi=10.1016/0022-0000(80)90041-0| doi-access=free}}</ref>

Erlebach et al. give a more efficient version of Angluin's pattern learning algorithm, as well as a parallelized version.<ref>{{cite book|author1=T. Erlebach |author2=P. Rossmanith |author3=H. Stadtherr |author4=A. Steger |author4-link=Angelika Steger|author5=T. Zeugmann | chapter=Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries| title=Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97| year=1997| volume=1316| pages=260–276| publisher=Springer|editor1=M. Li |editor2=A. Maruoka | series=LNAI|chapter-url=https://www.sciencedirect.com/science/article/pii/S0304397500001365/pdf?md5=c9bd770b62e31dcdce6b039a6c392c8f&pid=1-s2.0-S0304397500001365-main.pdf&_valck=1}}</ref>

Arimura et al. show that a language class obtained from limited unions of patterns can be learned in polynomial time.<ref>{{cite book|author1=Hiroki Arimura |author2=Takeshi Shinohara |author3=Setsuko Otsuki | chapter=Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data| title=Proc. STACS 11| year=1994| volume=775| pages=649–660| publisher=Springer| series=LNCS|chapter-url=http://ai2-s2-pdfs.s3.amazonaws.com/6a4c/0482e0030b0e5791cf75b0edd9f55fdfc10e.pdf}} </ref>

===Pattern theory===
[[Pattern theory]], formulated by [[Biography:Ulf Grenander|Ulf Grenander]],<ref>Grenander, Ulf, and Michael I. Miller. ''[http://www.ulb.tu-darmstadt.de/tocs/185410162.pdf Pattern theory: from representation to inference]''. Vol. 1. Oxford: Oxford university press, 2007.</ref> is a mathematical formalism to describe knowledge of the world as patterns. It differs from other approaches to [[Artificial intelligence|artificial intelligence]] in that it does not begin by prescribing algorithms and machinery to recognize and classify patterns; rather, it prescribes a vocabulary to articulate and recast the pattern concepts in precise language.

In addition to the new algebraic vocabulary, its statistical approach was novel in its aim to:
* Identify the [[Social:Latent variable|hidden variables]] of a data set using real world data rather than artificial stimuli, which was commonplace at the time.
* Formulate prior distributions for hidden variables and models for the observed variables that form the vertices of a Gibbs-like graph.
* Study the randomness and variability of these graphs.
* Create the basic classes of stochastic models applied by listing the deformations of the patterns.
* Synthesize (sample) from the models, not just analyze signals with it.
Broad in its mathematical coverage, pattern theory spans algebra and statistics, as well as local topological and global entropic properties.

== Applications ==
The principle of grammar induction has been applied to other aspects of [[Natural language processing|natural language processing]], and has been applied (among many other problems) to [[Semantic parsing|semantic parsing]],<ref name="Kwiatkowski">Kwiatkowski, Tom, et al. "[http://homes.cs.washington.edu/~lsz/papers/kzgs-emnlp2011.pdf Lexical generalization in CCG grammar induction for semantic parsing]." Proceedings of the conference on empirical methods in natural language processing. [[Organization:Association for Computational Linguistics|Association for Computational Linguistics]], 2011.</ref> [[Natural language understanding|natural language understanding]],<ref>Miller, Scott, et al. "[http://www.aclweb.org/anthology/P94-1004 Hidden understanding models of natural language]." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.</ref> example-based translation,<ref>Brown, Ralf D. "[https://web.archive.org/web/20180302044726/https://pdfs.semanticscholar.org/c537/ac8bac9d83651e0ce6b37333034a5f572e39.pdf Transfer-rule induction for example-based translation]." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.</ref> language acquisition,<ref>Chater, Nick, and Christopher D. Manning. "[https://www.stanford.edu/class/linguist1/Rdgs/chater.pdf Probabilistic models of language processing and acquisition]." Trends in cognitive sciences 10.7 (2006): 335-344.</ref> [[Grammar-based code|grammar-based compression]],<ref>Cherniavsky, Neva, and Richard Ladner. "[https://web.archive.org/web/20180206073621/https://pdfs.semanticscholar.org/1be9/0a2f40d10acd17d5910eb21fb3b4a117d08b.pdf Grammar-based compression of DNA sequences]." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).</ref> and [[Anomaly detection|anomaly detection]].<ref>Senin, Pavel, et al. [https://www.researchgate.net/profile/Pavel-Senin/publication/272161935_Time_series_anomaly_discovery_with_grammar-based_compression/links/54dc7ec10cf2a7769d965233/Time-series-anomaly-discovery-with-grammar-based-compression.pdf "Time series anomaly discovery with grammar-based compression."] Edbt. 2015.</ref>
=== Compression algorithms ===
{{excerpt|Grammar-based code}}

==See also==
* [[Artificial grammar learning]]
* [[Example-based machine translation]]
* [[Inductive programming]]
* [[Kolmogorov complexity]]
* [[Language identification in the limit]]
* [[Straight-line grammar]]
* [[Syntactic pattern recognition]]

==Notes==
{{reflist|group=note}}

==References==
{{Reflist}}

==Sources==
* {{Citation |last1=Duda |first1=Richard O. |last2=Hart |first2=Peter E. |last3=Stork |first3=David G. |title=Pattern Classification |publisher=John Wiley & Sons |place=New York |year=2001 |edition=2 |url=https://www.wiley.com/en-us/Pattern+Classification%2C+2nd+Edition-p-9781118586006}}
* {{Citation
  | last=Fu | first=King Sun
  | title=Syntactic Pattern Recognition and Applications
  | publisher=Prentice-Hall | place=Englewood Cliffs, NJ
  | year=1982}}
* {{Citation
  | last=Fu | first=King Sun
  | title=Syntactic Pattern Recognition, Applications
  | publisher=Springer-Verlag | place=[[Place:Berlin|Berlin]] | year=1977}}
* {{Citation
  | last=Horning | first=James Jay
  | title=A Study of Grammatical Inference
  | publisher=Stanford University Computer Science Department
  | place=Stanford | year=1969 | edition=Ph.D. Thesis
  | id={{ProQuest|302483145}}
 }}
* {{Citation
 |last         = Gold
 |first        = E. Mark
 |title        = Language Identification in the Limit
 |url          = http://groups.lis.illinois.edu/amag/langev/paper/gold67limit.html
 |year         = 1967
 |volume       = 10
 |pages        = 447–474
 |publisher    = Information and Control
 |access-date  = 2016-09-04
 |archive-url  = https://web.archive.org/web/20160828171937/http://groups.lis.illinois.edu/amag/langev/paper/gold67limit.html
 |archive-date = 2016-08-28
 |url-status     = dead
}}
* {{Citation
  | last=Gold | first=E. Mark
  | title=Language Identification in the Limit
  | volume=10
  | pages=447–474
  | url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf
  | publisher=Information and Control | year=1967}}

== Tools ==
[http://qsmm.org QSMM – adaptive parsers for the induction of context-free grammars by template]
[[Category:Genetic programming]]
[[Category:Natural language processing]]
[[Category:Computational linguistics]]
[[Category:Inference]]

{{Sourceattribution|Grammar induction}}