📄 Estimators for Stochastic “Unification-Based” Grammars

Summary

The paper tackles parameter estimation for stochastic versions of constraint-based ("unification-based") grammars such as LFG and HPSG. Unification constraints create non-local dependencies, so simple relative-frequency estimation, which works for PCFGs, no longer gives maximum-likelihood estimates. Abney's log-linear (Markov Random Field) framework is sound in principle, but his Monte-Carlo estimation scheme is too costly for realistic grammars.

The authors propose two tractable alternatives. The main one is a pseudo-likelihood estimator, an instance of Besag's method. It maximizes the conditional probability of the correct analyses given their strings, so expectations are computed only over each training sentence's own parses. The second is a "correct-parses" estimator.

They test both on two small LFG corpora from Xerox PARC (Verbmobil and Homecentre) with 10-fold cross-validation. Both estimators far outperform a uniform baseline and select the correct parse roughly 50–59% of the time. Pseudo-likelihood is usually the stronger of the two. The work shows that rich, non-production features can be estimated practically for SUBGs.

Key points

• Corpora: Verbmobil has 540 sentences, 314 of them ambiguous, with 3245 parses for the ambiguous ones. Homecentre has 980 sentences, 481 ambiguous, with 3169 parses.
• Feature sets: 191 features for Verbmobil (59 rule features) and 227 for Homecentre (57 rule features). Beyond rules, the features cover:
  • argument and adjunct attachment, including per grammatical function (SUBJ, OBJ, COMP, XCOMP, ADJUNCT);
  • high versus low attachment;
  • non-right-branching nodes;
  • non-parallel coordination;
  • f-structure attribute–value pairs;
  • date NPs.
• Correct-parse rate on Verbmobil: baseline 9.7%, pseudo-likelihood 58.7%, correct-parses 53.7%. On Homecentre: 15.2%, 58.8% and 53.2% respectively.
• Negative log pseudo-likelihood, where lower is better, follows the same pattern. On Verbmobil it is 533, 396 and 469; on Homecentre it is 655, 583 and 604.
• Optimization used conjugate gradient adapted from Press et al. (1992). The models overfit noticeably, and dropping features often improved results. Lexical dependency features were left out because the corpora were too small.

Interesting ideas

• I1. Condition on the observed input to avoid an intractable normalizer. Normalizing over each sentence's own candidate parses, instead of all possible analyses, makes gradient training feasible. The same trick applies to any structured model whose global partition function cannot be computed.
• I2. Separate the grammar from the scoring features. Once the estimator handles arbitrary features, there is no reason to limit features to grammar rules. Choosing features becomes an empirical modeling decision, which is useful for reranking parsers or taggers with hand-designed linguistic cues.
• I3. Give fractional credit for tied best parses. If several top-scoring parses are tied and one is correct, the sentence gets credit of 1 divided by the number of tied parses. This is a fair way to evaluate selection under ties in any ranking task.
• I4. Report probability mass on the correct analysis, not only top-1 accuracy. Pseudo-likelihood on held-out data shows how well the model ranks alternatives. This matters for human-assisted disambiguation or for presenting ordered options, such as candidate translations.
• I5. Cross-validate and sum scores when data is tiny. Using 10-fold cross-validation with summed scores extracts a reliable comparison from very small annotated corpora, which is relevant for low-resource treebank work.