2020/10/09 by Timo Kötzing, Kötzing, Timo, Karen Seidel +1
Computer Science · #Machine Learning and Algorithms #semigroups and automata theory #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.2010.04782
We investigate learning collections of languages from texts by an inductive\ninference machine with access to the current datum and a bounded memory in form\nof states. Such a bounded memory states (BMS) learner is considered successful\nin case it eventually settles on a correct hypothesis while exploiting only\nfinitely many different states.\n We give the complete map of all pairwise relations for an established\ncollection of criteria of successfull learning. Most prominently, we show that\nnon-U-shapedness is not restrictive, while conservativeness and (strong)\nmonotonicity are. Some results carry over from iterative learning by a general\nlemma showing that, for a wealth of restrictions (the semantic restrictions),\niterative and bounded memory states learning are equivalent. We also give an\nexample of a non-semantic restriction (strongly non-U-shapedness) where the two\nsettings differ.\n