Research Portal (King's College London) · 2004 · 81 citations · 14 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningProbability TheoryAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesProbabilistic Machine LearningAutomata LearningDeterministic Finite AutomataFinite Automata TheoryKullback-leibler DivergenceProbabilistic Finite AutomataProbabilistic Finite State MachinesSample ComplexitySample Complexity Analysis
We study the learnability of Probabilistic Deterministic Finite State Automata under a modified PAC-learning criterion. We argue that it is necessary to add additional parameters to the sample complexity polynomial, namely a bound on the expected length of strings generated from any state, and a bound on the distinguishability between states. With this, we demonstrate that the class of PDFAs is PAC-learnable using a variant of a standard state-merging algorithm and the KullbackLeibler divergence as error function.
14
Leslie G. Valiant · 1984 · 4.2K citations
Finite-state transducers in language and speech processing
Mehryar Mohri · 1997 · 922 citations
Elements of Information Theory, Wiley Series in Telecommunications
Thomas M. Cover, Thomas Allen · 1991 · 628 citations
On the learnability of discrete distributions
Michael Kearns, Yishay Mansour, Dana Ron et al. · 1994 · 287 citations · Full text