Learning with Partially Ordered Representations


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.

In Mathematics of Language 2019 (ACL SIGMOL)
Jon Rawski
Jon Rawski

I am a PhD student working at the interface of mathematics, linguistics, cognitive science, and algorithmic learning theory.