Abstract: The Surface Realization Shared Task 2018 challenged participants to generate grammatical sentences from lemmatized dependency triples. This paper presents BinLin, a data-driven pipeline system developed for the "Shallow Track" of the competition. BinLin first orders lemmas using a novel sequential method and then inflects them into surface forms. Despite its simplicity, the approach achieves promising results across ten languages. We describe the system architecture, its effectiveness, and the inherent limitations of the pipeline approach.
Introduction to Surface Realization
In Natural Language Generation (NLG), Surface Realization (SR) is the final stage where a structured "sentence plan" is transformed into a human-readable string. The 2018 Shared Task focused on the Shallow Track, where the input is an unordered dependency tree. Words are provided as base lemmas with part-of-speech tags, requiring the system to solve two primary problems:
- Linearization: Determining the correct word order (e.g., {the, cat, sit, on, mat} $\rightarrow$ "The cat sat on the mat").
- Inflection: Converting lemmas into correct grammatical forms (e.g., sit $\rightarrow$ sat).
Because the search space for word ordering is exponentially large, the authors sought a method that avoids exhaustive search or complex hand-crafted rules.
The BinLin Method: Syntactic Ordering
The core of the system is the BinLin linearization method. Instead of attempting to order an entire sentence globally, the system decomposes the dependency tree into local "head-child" relationships.
Binary Classification for Ordering
A Multi-Layer Perceptron (MLP) classifier is trained to take a pair of nodes—a head and one of its children—and predict whether the child should be placed to the left or the right of the head.
From Dependency to Binary Trees
These binary decisions are used to recursively transform the dependency tree into a binary tree. The head node serves as the root, and children are inserted into left or right branches based on the classifier's output. Finally, a simple in-order traversal (reading the tree from left to right) produces the linearized word sequence.
Morphological Inflection
Once the word order is established, the system inflects the lemmas. The authors evaluated three models for this task:
- A basic MLP.
- A standard Encoder-Decoder (Seq2Seq) with soft attention.
- A Hard Monotonic Attention model.
The Hard Monotonic Attention model proved superior because morphological changes (like suffixation) typically involve local, sequential character alignments. Soft attention models often struggle with the noise inherent in character-level transitions.
Key Insights and Results
Decomposition and Branching
The authors found that the "low branching factor" of dependency trees justifies their local decision-making approach. Statistical analysis of the treebanks showed that the vast majority of nodes have between zero and three children, making the recursive binary insertion strategy highly efficient.
Performance and Sensitivity
On the original Universal Dependencies (UD) development set, BinLin achieved perfect ordering for 74.88% of sentences. Morphology accuracy was also high, with the hard monotonic attention model reaching over 99% exact match for languages like Czech and Spanish.
However, a significant challenge arose during the Shared Task: input-order sensitivity. The model had inadvertently learned to rely on the sequence of tokens in the training data. When the competition organizers scrambled the input, performance dropped (BLEU scores ranged from 0.16 to 0.34), revealing that the model was partially relying on the provided input order rather than purely on syntactic features.
Limitations and Future Work
While BinLin is effective for its simplicity, it faces three main hurdles:
- Non-Projectivity: The binary tree approach assumes dependency lines do not cross. This makes it difficult to represent non-projective constructions common in languages like Dutch or Czech.
- Input Sensitivity: Future iterations could benefit from training on randomly permuted sequences to ensure the model ignores input order.
- Pipeline Cascades: As a pipeline, errors in the linearization stage can negatively impact the context for the inflection stage. A joint model handling both tasks simultaneously could mitigate these "cascading" errors.
Summary updated