This book provides a thorough introduction to the subfield of theoretical computer science known as grammatical inference from a computational linguistic perspective. Grammatical inference provides principled methods for developing computationally sound algorithms that learn structure from strings of symbols. The relationship to computational linguistics is natural because many research problems in computational linguistics are learning problems on words, phrases, and sentences: What algorithm can take as input some finite amount of data (for instance a corpus, annotated or otherwise) and output a system that behaves "correctly" on specific tasks?Throughout the text, the key concepts of grammatical inference are interleaved with illustrative examples drawn from problems in computational linguistics. Special attention is paid to the notion of "learning bias." In the context of computational linguistics, such bias can be thought to reflect common (ideally universal) properties of natural languages. This bias can be incorporated either by identifying a learnable class of languages which contains the language to be learned or by using particular strategies for optimizing parameter values. Examples are drawn largely from two linguistic domains (phonology and syntax) which span major regions of the Chomsky Hierarchy (from regular to context-sensitive classes). The conclusion summarizes the major lessons and open questions that grammatical inference brings to computational linguistics.
“The book is approachably short... The book is also organized very clearly with respect to laying out visually various subsections and formalisms. This organization makes the book a tremendously useful reference... The book gave a thorough and understandable overview of the field and is a very useful resource to return to in the future.” – Andrew Lamont & Lwin Moe, Indiana University for Linguist List
“This book is a strong introduction to grammatical inference and is written well for computational linguists and as such accomplishes exactly what it sets out to do. The book is self-contained, introducing and defining terms and concepts that readers need to be familiar with in order to understand the larger points. The book is approachably short, just over 120 dense pages with references; a determined reader should find it takes at most a weekend to read. As such, it makes a good read cover-to-cover. The book is also organized very clearly with respect to laying out visually various subsections and formalisms.” – Helen Aristar-Dry for The Linguist
