Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Paper shows many shuffle ideals are not efficiently learnable from membership or contrastive queries.
The paper studies learning shuffle ideals from membership queries and from contrastive queries that return a similar in-language word when the queried word is absent. It shows that even very simple classes cannot be learned efficiently in either setting. Positive learnability holds only under structural conditions linked to universal words for membership queries and to shortlex-ordered word partitions for contrastive queries. The membership-query conditions raise new questions in word combinatorics.
- Even simple shuffle-ideal classes are not efficiently learnable from membership queries.
- Contrastive queries also fail to efficiently learn some simple classes.
- Positive results require structural conditions on the target language class.
- Membership conditions relate to universal words and word combinatorics.
From the original article
1 min read at arxiv.orgThis paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word $w$ is in the target language or not, but also provides a most similar word $w'$ that belongs to the target language if %and only if $w$ does not.
By S. Mahmoud Mousawi · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.