Learning Context-Free Grammars with a Simplicity Bias
Abstract
We examine the role of simplicity in directing the induction of context-free grammars from sample sentences. We present a rational reconstruction of Wolff’s SNPR — the Grids system — which incorporates a bias toward grammars that minimize description length. The algorithm alternates between merging existing nonterminal symbols and creating new symbols, using a beam search to move from complex to simpler grammars. Experiments suggest that this approach can induce accurate grammars and that it scales reasonably to more difficult domains.
Cite
Text
Langley and Stromsten. "Learning Context-Free Grammars with a Simplicity Bias." European Conference on Machine Learning, 2000. doi:10.1007/3-540-45164-1_23Markdown
[Langley and Stromsten. "Learning Context-Free Grammars with a Simplicity Bias." European Conference on Machine Learning, 2000.](https://mlanthology.org/ecmlpkdd/2000/langley2000ecml-learning/) doi:10.1007/3-540-45164-1_23BibTeX
@inproceedings{langley2000ecml-learning,
title = {{Learning Context-Free Grammars with a Simplicity Bias}},
author = {Langley, Pat and Stromsten, Sean},
booktitle = {European Conference on Machine Learning},
year = {2000},
pages = {220-228},
doi = {10.1007/3-540-45164-1_23},
url = {https://mlanthology.org/ecmlpkdd/2000/langley2000ecml-learning/}
}