UNSPECIFIED (2005) PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. In: 16th Annual International Conference on Algorithmic Learning Theory (LAT 2005), Singapore, SINGAPORE, OCT 08-11, 2005. Published in: ALGORITHMIC LEARNING THEORY, 3734 pp. 157-170.

Full text not available from this repository.

Abstract

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs axe a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Series Name:	LECTURE NOTES IN ARTIFICIAL INTELLIGENCE
Journal or Publication Title:	ALGORITHMIC LEARNING THEORY
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-29242-X
ISSN:	0302-9743
Editor:	Jain, S and Simon, HU and Tomita, E
Date:	2005
Volume:	3734
Number of Pages:	14
Page Range:	pp. 157-170
Publication Status:	Published
Title of Event:	16th Annual International Conference on Algorithmic Learning Theory (LAT 2005)
Location of Event:	Singapore, SINGAPORE
Date(s) of Event:	OCT 08-11, 2005
URI:	http://wrap.warwick.ac.uk/id/eprint/34249

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item