Limits and conditions for learning word patterns with queries
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Formal Languages and Automata TheoryMachine Learning
Summary
This paper investigates how to learn special sets of words, called shuffle ideals, by asking questions about whether words belong to them. It shows that for simple types of these word sets, learning them efficiently is impossible, even if the questions provide helpful contrast examples. However, the authors identify specific structural features that make some classes of shuffle ideals learnable. These features relate to how words are universally ordered or grouped, raising new research questions about word patterns.
What this means in practice
- •For formal language tool developers: Design algorithms for identifying complex word sets when structural conditions like universal words are met.
- •For natural language processing engineers: Inform limits on efficient learning methods using membership queries when working with certain word pattern classes.
A theory result. No direct application yet.
Authors
S. Mahmoud Mousawi, Pierluigi San Pietro, Sandra Zilles
Abstract
This 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. For both settings, it is shown that even some very simple classes of shuffle ideals cannot be learned efficiently. By contrast, we obtain positive learnability results for classes of shuffle ideals that meet certain structural conditions. In the case of membership queries, these structural conditions are related to the previously studied notion of universal words, and raise new questions in word combinatorics. In the case of contrastive queries, the structural conditions relate to partitioning sets of words that are listed in shortlex order.