Learning with Partially Ordered Representations
This addresses a theoretical problem in formal language learning for applications needing enriched representations, but it appears incremental as it extends traditional model-theoretic approaches.
The paper tackles the problem of learning grammars from enriched string models where positions can have multiple properties, showing these structures are partially ordered and presenting an algorithm that uses this ordering to prune the hypothesis space, proving it finds the most general grammar covering positive examples.
This paper examines the characterization and learning of grammars defined with enriched representational models. Model-theoretic approaches to formal language theory traditionally assume that each position in a string belongs to exactly one unary relation. We consider unconventional string models where positions can have multiple, shared properties, which are arguably useful in many applications. We show the structures given by these models are partially ordered, and present a learning algorithm that exploits this ordering relation to effectively prune the hypothesis space. We prove this learning algorithm, which takes positive examples as input, finds the most general grammar which covers the data.