The Library
PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance
Tools
Tools
Tools
Palmer, Nick and Goldberg, Paul W. (2007) PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. In: 16th Annual International Conference on Algorithmic Learning Theory (ALT 2005), Singapore, 08-11 Oct 2005. Published in: Theoretical Computer Science, Vol.387 (No.1). pp. 18-31. doi:10.1016/j.tcs.2007.07.023 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2007.07.023
Abstract
We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are 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 (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Theoretical Computer Science | ||||
| Publisher: | Elsevier Science BV | ||||
| ISSN: | 0304-3975 | ||||
| Official Date: | 6 November 2007 | ||||
| Dates: |
|
||||
| Volume: | Vol.387 | ||||
| Number: | No.1 | ||||
| Number of Pages: | 14 | ||||
| Page Range: | pp. 18-31 | ||||
| DOI: | 10.1016/j.tcs.2007.07.023 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 16th Annual International Conference on Algorithmic Learning Theory (ALT 2005) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Singapore | ||||
| Date(s) of Event: | 08-11 Oct 2005 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
