PAC-learnability of Probabilistic Deterministic Finite State Automata

Alexander Clark; Franck Thollard

PAC-learnability of Probabilistic Deterministic Finite State Automata

Alexander Clark, Franck Thollard

Philosophy

Research output: Contribution to journal › Article › peer-review

73 Citations (Scopus)

Abstract

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 Kullback-Leibler divergence as error function.

Original language	Undefined/Unknown
Pages (from-to)	473-497
Number of pages	25
Journal	JOURNAL OF MACHINE LEARNING RESEARCH
Volume	5
Publication status	Published - 1 May 2004

Cite this

@article{2e78e634bbb74d7aa056f90c09bf522e,

title = "PAC-learnability of Probabilistic Deterministic Finite State Automata",

abstract = "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 Kullback-Leibler divergence as error function.",

author = "Alexander Clark and Franck Thollard",

year = "2004",

month = may,

day = "1",

language = "Undefined/Unknown",

volume = "5",

pages = "473--497",

journal = "JOURNAL OF MACHINE LEARNING RESEARCH",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - PAC-learnability of Probabilistic Deterministic Finite State Automata

AU - Clark, Alexander

AU - Thollard, Franck

PY - 2004/5/1

Y1 - 2004/5/1

N2 - 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 Kullback-Leibler divergence as error function.

AB - 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 Kullback-Leibler divergence as error function.

M3 - Article

VL - 5

SP - 473

EP - 497

JO - JOURNAL OF MACHINE LEARNING RESEARCH

JF - JOURNAL OF MACHINE LEARNING RESEARCH

ER -