Learning Languages by Collecting Cases and Tuning Parameters
Abstract
We investigate the problem of case-based learning of formal languages. Case-based reasoning and learning is a currently booming area of artificial intelligence. The formal framework for case-based learning of languages has recently been developed by [JL93] in an inductive inference manner. In this paper, we first show that any indexed class of recursive languages in which finiteness is decidable is case-based representable, but many classes of languages including the class of all regular languages are not case-based learnable with a fixed universal similarity measure, even if both positive and negative examples are presented. Next we consider a framework of case-based learning where the learning algorithm is allowed to learn similarity measures, too. To avoid trivial encoding tricks, we carefully examine to what extent the similarity measure is going to be learned. Then by allowing only to learn a few parameters in the similarity measures, we show that any indexed class of recursive languages whose finiteness problem is decidable is case-based learnable. This implies that all context-free languages are case-based learnable by collecting cases and learning parameters of the similarity measures.
Cite
Text
Sakakibara et al. "Learning Languages by Collecting Cases and Tuning Parameters." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_88Markdown
[Sakakibara et al. "Learning Languages by Collecting Cases and Tuning Parameters." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/sakakibara1994alt-learning/) doi:10.1007/3-540-58520-6_88BibTeX
@inproceedings{sakakibara1994alt-learning,
title = {{Learning Languages by Collecting Cases and Tuning Parameters}},
author = {Sakakibara, Yasubumi and Jantke, Klaus P. and Lange, Steffen},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1994},
pages = {532-546},
doi = {10.1007/3-540-58520-6_88},
url = {https://mlanthology.org/alt/1994/sakakibara1994alt-learning/}
}