Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes
This work addresses theoretical limitations in language learning models for computational linguistics, but it is incremental as it builds on established criteria and settings.
The paper investigates learning languages from text using inductive inference machines with bounded memory states, showing that non-U-shapedness is not restrictive while conservativeness and monotonicity are, and establishes equivalences between iterative and bounded memory states learning for semantic restrictions.
We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and a bounded memory in form of states. Such a bounded memory states (BMS) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states. We give the complete map of all pairwise relations for an established collection of criteria of successfull learning. Most prominently, we show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. Some results carry over from iterative learning by a general lemma showing that, for a wealth of restrictions (the semantic restrictions), iterative and bounded memory states learning are equivalent. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.