BinLin: A Simple Method of Dependency Tree Linearization

Yevgeniy Puzikov, Iryna Gurevych2018 · DOI

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:

  1. Linearization: Determining the correct word order (e.g., {the, cat, sit, on, mat} $\rightarrow$ "The cat sat on the mat").
  2. 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.

Comparison between a standard dependency tree and the binary tree structure used by BinLin for linearization.

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.

Distribution of the number of children per node in the dataset, showing a low branching factor.

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:

  1. 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.
  2. Input Sensitivity: Future iterations could benefit from training on randomly permuted sequences to ensure the model ignores input order.
  3. 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

Abstract

Surface Realization Shared Task 2018 is a workshop on generating sentences from lemmatized sets of dependency triples. This paper describes the results of our participation in the challenge. We develop a data-driven pipeline system which first orders the lemmas and then conjugates the words to finish the surface realization process. Our contribution is a novel sequential method of ordering lemmas, which, despite its simplicity, achieves promising results. We demonstrate the effectiveness of the proposed approach, describe its limitations and outline ways to improve it.
BibTeX
@misc{puzikov2018binlin,
  author = {Yevgeniy Puzikov and Iryna Gurevych},
  title = {{BinLin: A Simple Method of Dependency Tree Linearization}},
  year = {2018},
  doi = {10.18653/v1/w18-3602},
}
Figure