📄 An Empirical Verification of Coverage and Correctness for a General-Purpose Sentence Generator

Summary

The paper addresses a long-standing gap in natural language generation. General-purpose sentence realizers such as FUF/Surge, RealPro, Penman/KPML and Nitrogen had never been evaluated empirically for coverage or output quality. They were checked only against small regression suites built around each system's own capabilities. The author presents HALogen, a successor to Nitrogen with a hybrid design. Hand-written symbolic mapping rules expand a feature-value input into a packed forest of candidate realizations, and an n-gram language model then selects the most probable string. For evaluation, inputs were derived automatically from Penn Treebank section 23 and regenerated, with the output compared against the original sentences. Six experiments progressively removed information from the inputs. With nearly complete inputs, about 83% produced output, scoring roughly 0.92 Bleu and 94.5% NIST simple string accuracy, and over half were exact matches. With minimal inputs, quality fell to about 0.51 Bleu. The author describes this as the first empirical coverage measurement for a realizer. It shows that broad coverage and high quality need not be mutually exclusive.

Key points

• HALogen's symbolic stage uses about 255 mapping rules of four types: recasting, ordering, filling, and morphing. These produce a forest, which is a non-recursive context-free grammar.
• The ranker extracts the N best phrases with bottom-up dynamic programming. It uses n-gram models built with the CMU Statistical Language Modeling Toolkit (v2), trained on 250M words of Wall Street Journal text with the 1989 portion (the source of the Penn Treebank) excluded.
• The test set was about 2400 automatically built inputs from Penn Treebank section 23. The six specification levels ranged from "Almost fully spec" to "Min spec" and included settings with permuted same-role nodes, underspecified determiners, and removed leaf/clause features.
• Results:
  • "Almost fully spec": 82.8% of inputs produced output, 57.5% exact matches, SSA 94.5%, Bleu 0.924.
  • "Min spec": 79.3% produced output, 5.2% exact matches, SSA 55.3%, Bleu 0.514.
• For comparison, FERGUS, which only had to determine word order for 100 inputs, reached 58% NIST accuracy. This is roughly on par with HALogen's minimal-input setting. Existing regression suites were small: 500 inputs for Surge and about 210 for English in KPML.

Interesting ideas

• I1. Treebank as a source of test inputs. Annotated trees can be turned automatically into generator inputs, with the original sentence serving as the reference. This gives a large, unbiased test set for any realizer or text-to-structure system, and the same trick could apply to UD treebanks.
• I2. Graded underspecification as an evaluation axis. The same test set is run repeatedly while specific kinds of information are deliberately stripped out, such as determiners, ordering hints, or clause features. This shows which subproblems are hardest and how gracefully the system degrades, rather than producing a single score.
• I3. Recasting rules as an abstraction ladder. Semantic or domain-specific relations are mapped onto syntactic ones. Client applications can then choose how abstract or precise their input is, and the same mechanism lets them customize the system without touching its core rules.
• I4. Overgenerate symbolically, then rank statistically. HALogen dropped rigid grammar constraints that blocked scaling and let the language model enforce preferences over a packed forest. This is a practical pattern wherever hand-written rules prove both too loose and too strict at the same time.
• I5. Honest contamination and failure analysis. The paper explicitly discusses how the test section may have indirectly influenced rule development through tgrep. It also sorts failures into unhandled syntax, treebank annotation errors, input-construction errors, and malformed source phrases. Both are good habits for any benchmark report.