PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties from Positive Data
Abstract
In recent years different interesting subclasses of cfl s have been found to be learnable by techniques generically called distributional learning . The theoretical study on the exact learning of cfl s by those techniques under different learning scheme is now quite mature. On the other hand, positive results on the pac learnability of cfl s are rather limited and quite weak. This paper shows that several subclasses of context-free languages that are known to be exactly learnable with membership queries by distributional learning techniques are pac learnable from positive data under some assumptions on the string distribution.
Cite
Text
Shibata and Yoshinaka. "PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties from Positive Data." International Conference on Algorithmic Learning Theory, 2013. doi:10.1007/978-3-642-40935-6_11Markdown
[Shibata and Yoshinaka. "PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties from Positive Data." International Conference on Algorithmic Learning Theory, 2013.](https://mlanthology.org/alt/2013/shibata2013alt-pac/) doi:10.1007/978-3-642-40935-6_11BibTeX
@inproceedings{shibata2013alt-pac,
title = {{PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties from Positive Data}},
author = {Shibata, Chihiro and Yoshinaka, Ryo},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2013},
pages = {143-157},
doi = {10.1007/978-3-642-40935-6_11},
url = {https://mlanthology.org/alt/2013/shibata2013alt-pac/}
}