Learning stochastic regular grammars by means of a state merging method
Lecture notes in computer sciencePublished 1 January 1994
Rafael C. Carrasco, José Oncina
Citations352
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new algorithm is proposed which allows for the identification of any stochastic deterministic regular language as well as the determination of the probabilities of the strings in the language.
Abstract
We propose a new algorithm which allows for the identification of any stochastic deterministic regular language as well as the determination of the probabilities of the strings in the language. The algorithm builds the prefix tree acceptor from the sample set and merges systematically equivalent states. Experimentally, it proves very fast and the time needed grows only linearly with the size of the sample set.
Keywords
Computer Science
Journal of the Franklin InstituteAn introduction to probability theory and its applications
29,966 Citations1958
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
4,750 Citations1963Wassily Hoeffding
Journal of Verbal Learning and Verbal BehaviorImplicit learning of artificial grammars
1,947 Citations1967Arthur S. Reber
Information and ControlComplexity of automaton identification from given data
770 Citations1978Eric Gold
The question of whether there is an automaton with n states which agrees with a finite set D of data is shown to be NP-complete, although identification-in-the-limit of finite automata is possible in polynomial time as a function of the size of D.
Neural ComputationLearning and Extracting Finite State Automata with Second-Order Recurrent Neural Networks
392 Citations1992C. Lee Giles, CLIFFORD B. MILLER +4 more
It is shown that a recurrent, second-order neural network using a real-time, forward training algorithm readily learns to infer small regular grammars from positive and negative string training samples, and many of the neural net state machines are dynamically stable, that is, they correctly classify many long unseen strings.
Machine LearningThe induction of dynamical recognizers
298 Citations1991Jordan Pollack
A study of the automata resulting from the acquisition of previously published training sets indicates that while the architecture is not guaranteed to find a minimal finite automaton consistent with the given exemplars, it does appear capable of generating non-regular languages by exploiting fractal and chaotic dynamics.
Hidden Markov Model Induction by Bayesian Model Merging
241 Citations1992Andreas Stolcke, Stephen M. Omohundro
The algorithm is compared with the Baum-Welch method of estimating fixed-size models, and it is found that it can induce minimal HMMs from data in cases where fixed estimation does not converge or requires redundant parameters to converge.
Neural ComputationInduction of Finite-State Languages Using Second-Order Recurrent Networks
145 Citations1992Raymond L. Watrous, Gary M. Kuhn
Second-order recurrent networks that recognize simple finite state languages over {0,1}* are induced from positive and negative examples to obtain solutions that correctly recognize strings of arbitrary length.
International Journal of Neural SystemsLEARNING SEQUENTIAL STRUCTURE WITH THE REAL-TIME RECURRENT LEARNING ALGORITHM
40 Citations1989Anthony Smith, David Zipser
A more powerful recurrent learning procedure, called real-time recurrent learning2,6 (RTRL), is applied to some of the same problems studied by Servan-Schreiber, Cleeremans, and McClelland and revealed that the internal representations developed by RTRL networks revealed that they learn a rich set of internal states that represent more about the past than is required by the underlying grammar.
IEEE Transactions on ComputersInference of Finite-State Probabilistic Grammars
36 Citations1977Maryanski, Booth
The inference procedure developed provides a means of synthesizing a probabilistic model of both physical and abstract systems from samples of their behavior by means of assigning probability measures to rewrite rules of Probabilistic grammars.
Information and ControlOn the inference of stochastic regular grammars
25 Citations1978A. Van Der Mude, Adrian Walker
The relevance of grammatical inference techniques to the semiautomatic construction from empirical data, of a model of human decision making, is outlined and it is established that any best grammar is obtainable by repeated splitting of the initial grammar.
Lecture notes in computer scienceSimulation of stochastic regular grammars through simple recurrent networks
5 Citations1993M. Asunción Castaño, Francisco Casacuberta +1 more
Empirical evidence is shown that network architectures trained from positive samples or positive and negative samples generated by regular grammars to accept or reject new strings could also predict the generation probabilities of each character in the strings generated by Stochastic Regular Grammars.