Source-linked AI summary
Modeling the Complexity and Descriptive Adequacy of Construction Grammars
Jonathan Dunn
TL;DR
The paper addresses how to evaluate usage-based CxGs learned from unannotated corpora while balancing their complexity against descriptive adequacy. It uses MDL to search for grammars that efficiently encode held-out corpus data, finding meaningful compression and stronger generalizations from multi-level grammars. More complex grammars achieve greater compression but are less stable across corpus subsets.
Problem
The paper asks how to model the complexity and descriptive adequacy of specific usage-based CxGs against observable language corpora.
Method
The paper uses MDL to balance grammar complexity against compression of held-out corpora while searching potential CxGs.
Results
Multi-level CxGs provide better corpus descriptions than purely lexical grammars, with CxGFULL generally achieving the highest compression and meaningful above-baseline generalizations.
Takeaways & Limitations
Compression provides an objective way to evaluate CxGs against unannotated corpora, while richer representations support greater generalizations than single-representation grammars.
Takeaways & Limitations
The implementation omits learned inheritance relations, allows only one representation type per slot, and does not let larger constructions fill other construction slots.
Abstract
from arXiv · showhide
This paper uses the Minimum Description Length paradigm to model the complexity of CxGs (operationalized as the encoding size of a grammar) alongside their descriptive adequacy (operationalized as the encoding size of a corpus given a grammar). These two quantities are combined to measure the quality of potential CxGs against unannotated corpora, supporting discovery-device CxGs for English, Spanish, French, German, and Italian. The results show (i) that these grammars provide significant generalizations as measured using compression and (ii) that more complex CxGs with access to multiple levels of representation provide greater generalizations than single-representation CxGs.
1 Complexity and Descriptive Adequacy
The paper models CxG complexity and descriptive adequacy against observed corpora using MDL, treating grammar quality as a balance between the two. It applies these measures to learning CxGs for five languages.
- CxGs can be more complex than purely syntactic grammars because they operate across lexical, syntactic, and semantic representations.
- MDL combines grammar complexity and corpus descriptive adequacy into an objective function for comparing potential CxGs.
- The approach learns CxGs for English, Spanish, French, German, and Italian.
- The paper asks how to model a specific usage-based CxG for a specific language using an observable corpus.
- Earlier computational CxG representations relied on linguists’ intuitions, limiting replicability, falsifiability, and scalability across domains and languages.
2 Representing CxGs
The paper represents constructions as slot sequences constrained by lexical, syntactic, or semantic units. It uses both item-specific and schematic representations, while acknowledging implementation limits relative to an ideal CxG.
- The representation system treats lexical word-forms, syntactic part-of-speech categories, and semantic word clusters as atomic units.
- Constructions are bracketed slot sequences whose slots are governed by constraints specifying which units may fill them.
- Multiple overlapping representations let CxGs distinguish idiomatic utterances from more schematic patterns, but each item-specific construction increases grammar complexity.
- A construct can be represented by multiple constructions, including more item-specific forms alongside more schematic forms.
- The implementation limits each slot to one representation type, excludes larger constructions from filling other construction slots, and does not model inheritance relations.
- Computationally, each construction is an array of slots, with each slot pointing to a constraining alphabet and a particular unit.
3 Finding CxGs
The learning procedure searches potential grammars against multilingual web corpora and builds representations in successive passes. This setup compares grammars with lexical, syntactic, and full multi-level access.
- Each language’s grammar is learned by searching potential grammars and evaluating them against a large web-crawled corpus.
- The search uses tabu search, with multi-unit association measures sampling potential constructions.
- The lexical pass learns fused sequences such as “could be” and “will be” as single lexical units.
- The syntactic pass learns syntactic constructions that later function as phrase-structure constituents.
- The full pass operates across all representation levels, accumulating structures from previous passes as atomic units.
- The staged setup tests whether grammars with access to multiple representation levels provide benefits despite their greater complexity.
4 Measuring Grammar Quality
Minimum Description Length measures grammar quality by balancing grammar encoding complexity against corpus compression, with held-out evaluation and restart stability providing complementary evidence.
- The optimum grammar minimizes the combined encoding size of the grammar and the dataset encoded by that grammar.
- MDL separates grammar complexity (L1), corpus encoding given the grammar (L2), and universal-code cost (L3).An uncompressed corpus encoding provides the baseline for measuring overall compression.
- Compression is reported as a relative measure where values near 1 indicate greater compression and negative values indicate that the grammar worsens MDL.The ratio removes dependence on the encoding size of a particular test set.
- Grammar stability measures agreement across search restarts, weighting disagreements by their differences in MDL quality.Higher scores toward 1 indicate stable grammars, while lower scores toward 0 indicate unstable grammars.
- The MDL measures avoid gold-standard annotations, enabling empirical comparison of grammars across languages and language varieties.This addresses settings where gold-standard annotations are unavailable and directly evaluates whether one grammar is better than another.
5 Measuring the Encoding Size of CxGs
CxG encoding assigns costs to constructions, representations, and undescribed units while preserving lossless encoding across abstraction levels. Because iterations encode different levels of abstraction, their grammar complexities are not directly comparable, although full MDL remains comparable.
- The MDL metric contains L1 for grammar encoding, L2 for corpus encoding given the grammar, and L3 for universal-code encoding.An uncompressed corpus encoding is also required as a baseline for overall compression.
- The encoding model divides units into Constructions and Regret, assigning each top-level category probability 0.5 and an initial cost of 0.693 nats.Regret contains corpus units not described by known constructions.
- Each undescribed unit is encoded independently in Regret, and its cost increases with the total number of undescribed units.This makes Regret a measure of model error within the dataset encoding.
- Construction complexity includes the cost of encoding the lexical, syntactic, and semantic units used in construction descriptions.For a full CxG, a three-way representation distinction costs 1.098 nats per slot before the unit vocabulary cost.
- 5.1 Maintaining Lossless Encoding: Lossless encoding requires each data unit to be represented by one representation type in the decoded dataset, with the optimum type selected during learning.CxGLEX reconstructs word-forms, whereas CxGSYN reconstructs the original part-of-speech sequence.
- 5.1 Maintaining Lossless Encoding: Grammar complexity is not directly comparable across iterations because each iteration encodes a different abstraction level.Full CxGs additionally incorporate lexical and semantic representations, while the full MDL metric remains comparable because it balances complexity and descriptive adequacy.
6 Searching Over Potential CxGs
The search algorithm optimizes potential CxGs by exploring construction-sampling parameters and construction inventories, using MDL to select grammar states while tabu restrictions limit cycling.
- Search procedure: The search combines random initialization, an indirect tabu search over sampling parameters, and a direct tabu search over construction inventories.These components respectively initialize the grammar, update sampling parameters, and test small inventory changes.
- Search procedure: The indirect search uses association measures to determine which constructions enter the grammar and explores moves from the current grammar state.Moves are evaluated as alternative parameter settings for construction sampling.
- MDL-guided optimization: The best available move is the one with the smallest MDL metric, even when it temporarily reduces overall grammar quality.A move remains available if it is not tabu or satisfies the aspiration criterion.
- MDL-guided optimization: The tabu list stores the last n moves, with n = 7, preventing changes to recently modified sampling parameters and reducing cycling between local optima.A new globally best MDL grammar can override the tabu restriction through the aspiration criterion.
7 Results and Discussion
Across five languages, the MDL-based evaluation learns grammars that compress held-out unannotated corpora, with richer multi-level grammars trading lower stability for stronger compression. The analysis also identifies unresolved variation between corpus subsets and supports MDL as a joint measure of CxG complexity and descriptive adequacy.
- Evaluation setup: The evaluation uses web-crawled corpora for English, Spanish, French, German, and Italian, with two-fold cross-validation and two search restarts.The learning algorithm makes four passes per iteration, allowing stability to be measured.
- Compression: Lexical constructions provide little held-out compression, with an average of 22 selected per language.Compression is measured relative to the unencoded dataset, where values near 1 indicate more compression.
- Compression: Syntactic constructions provide compression, with an average of 120 identified per language; CxGFULL has the highest compression rate in every language except English.CxGFULL grammars contain between 4k and 5k constructions.
- Grammar quality: MDL balances grammar complexity against corpus description, allowing multi-representation CxGs to justify larger construction inventories through better descriptions.The results also report improved descriptive adequacy when semantic representations are added.
- Stability and limitations: More complicated grammars are less stable: CxGLEX is highly stable but weakly compressive, whereas CxGFULL compresses more strongly with greater inventory variation.Variation can reflect tagging, parsing, or learning errors, as well as differences in usage across corpus portions.
- Stability and limitations: Determining whether grammar variation reflects error or genuine grammatical differences remains future work requiring data explicitly drawn from different language varieties.The current corpora contain multiple varieties, dialects, domains, and speakers.
- Conclusion: The paper concludes that MDL jointly models CxG complexity and descriptive adequacy against unannotated corpora without relying on gold-standard annotations.Gold-standard evaluations ultimately depend on the introspections behind those annotations.
Appendix A: Representative Examples
The appendix provides representative learned constructions, while the paper points to dialectometry as an application of these grammars and makes its code and models available online.
- Application: Separate dialectometry work reports that the learned CxGs model regional varieties with a high degree of accuracy.This is presented as an application-specific evaluation of a learned grammar.
- Resources: Code and models for the work are available at jdunn.name and github.com/jonathandunn/c2xg.The resource statement identifies both a personal website and a GitHub repository.
- Representative constructions: The representative English output includes an adverb-modification construction involving “about.”The construction is presented as modifying adverbs to encode vagueness.
- Representative constructions: The output also includes a verb-specific direct-object construction for “provide” and a complex verb-phrase construction such as “designed to ensure.”The “provide” construction constrains its object to members of an unlabeled semantic domain.