Learnability of probabilistic automata via oracles

Omri Guttman; S. V.N. Vishwanathan; Robert C. Williamson

doi:10.1007/11564089_15

Learnability of probabilistic automata via oracles

Omri Guttman^*, S. V.N. Vishwanathan, Robert C. Williamson

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Citations (Scopus)

Abstract

Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ₂-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μ_p- distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.

Original language	English
Title of host publication	Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings
Pages	171-182
Number of pages	12
DOIs	https://doi.org/10.1007/11564089_15
Publication status	Published - 2005
Event	16th International Conference on Algorithmic Learning Theory, ALT 2005 - Singapore, Singapore Duration: 8 Oct 2005 → 11 Oct 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3734 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Algorithmic Learning Theory, ALT 2005
Country/Territory	Singapore
City	Singapore
Period	8/10/05 → 11/10/05

Access to Document

10.1007/11564089_15

Cite this

Guttman, O., Vishwanathan, S. V. N., & Williamson, R. C. (2005). Learnability of probabilistic automata via oracles. In Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings (pp. 171-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3734 LNAI). https://doi.org/10.1007/11564089_15

@inproceedings{4140e88db0c84e4eb4c277483a7d0720,

title = "Learnability of probabilistic automata via oracles",

abstract = "Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μp- distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.",

author = "Omri Guttman and Vishwanathan, {S. V.N.} and Williamson, {Robert C.}",

year = "2005",

doi = "10.1007/11564089_15",

language = "English",

isbn = "354029242X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "171--182",

booktitle = "Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings",

note = "16th International Conference on Algorithmic Learning Theory, ALT 2005 ; Conference date: 08-10-2005 Through 11-10-2005",

}

Guttman, O, Vishwanathan, SVN & Williamson, RC 2005, Learnability of probabilistic automata via oracles. in Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3734 LNAI, pp. 171-182, 16th International Conference on Algorithmic Learning Theory, ALT 2005, Singapore, Singapore, 8/10/05. https://doi.org/10.1007/11564089_15

Learnability of probabilistic automata via oracles. / Guttman, Omri; Vishwanathan, S. V.N.; Williamson, Robert C.
Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings. 2005. p. 171-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3734 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Learnability of probabilistic automata via oracles

AU - Guttman, Omri

AU - Vishwanathan, S. V.N.

AU - Williamson, Robert C.

PY - 2005

Y1 - 2005

N2 - Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μp- distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.

AB - Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μp- distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.

UR - http://www.scopus.com/inward/record.url?scp=33646529351&partnerID=8YFLogxK

U2 - 10.1007/11564089_15

DO - 10.1007/11564089_15

M3 - Conference contribution

SN - 354029242X

SN - 9783540292425

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 171

EP - 182

BT - Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings

T2 - 16th International Conference on Algorithmic Learning Theory, ALT 2005

Y2 - 8 October 2005 through 11 October 2005

ER -

Learnability of probabilistic automata via oracles

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this