Preserving Semantic Dependencies in Synchronous Tree Adjoining Grammar

William SchulerACL 1999 · DOI

Introduction: The Isomorphism Problem

In computational linguistics, translating between languages involves more than lexical substitution; it requires mapping complex structural "blueprints." Synchronous Tree Adjoining Grammar (STAG) has been a prominent framework for this task. However, standard Isomorphic STAG (ISTAG) relies on a strict assumption: that the sequence of tree-combining operations (the derivation) in the source language can be mirrored exactly in the target language.

The Challenge of Structural Mismatch

The primary limitation of ISTAG arises when languages use fundamentally different syntactic structures to express identical semantic dependencies. For example, consider the sentence: "X is supposed to be able to fly."

In English, "is supposed to" acts as a raising verb that attaches to a Verb Phrase (VP). In contrast, the Portuguese equivalent often employs a bridge verb construction (É pressuposto que...) which attaches to a Sentence node (S). This creates a "non-isomorphism": the source derivation tree and the target derivation tree have different topologies.

Semantic dependency chain for the English sentence "X is supposed to be able to fly."

As shown in the English dependency structure above, the predicates form a linear chain. However, the Portuguese equivalent requires a different arrangement to be grammatically correct within its own rules, often resulting in a branching structure where the "slots" for adjunction do not match.

Non-isomorphic semantic dependency structure for the Portuguese translation.

When a VP-adjunction in English needs to map to an S-adjunction in Portuguese, standard isomorphic systems fail to produce a well-formed target derivation because the target language doesn't have the right "hole" for the source language's "peg."

Proposed Methodology: Decoupling Derivation from Semantics

Schuler proposes a solution that shifts the focus from preserving the derivation process to preserving the semantic dependency structure. The core idea is to ensure "semantic isomorphism"—meaning the underlying links between predicates and arguments remain identical even if the grammatical trees look different.

1. Semantic Dependency Extraction

The system employs an algorithm during parsing to track "predicate variables." As elementary trees are combined via substitution or adjunction, the algorithm records which lexical items serve as arguments for specific predicates. This results in a semantic dependency graph that captures the core meaning independently of syntax.

2. Monotonic Compositional Semantics

By distinguishing between "modifier" and "predicative" auxiliary trees, the model allows predicate variables to be "passed up" the tree. This mechanism enables a verb to "migrate" to a different attachment level in the target language without breaking its semantic connection to its arguments.

3. Target Derivation Construction

Once the source dependencies are captured, a second algorithm "parses" this dependency graph to reconstruct a valid derivation forest in the target language. This allows the system to handle "non-local" jumps where a verb in the target language must attach much higher or lower than its counterpart in the source.

Results and Implications

The paper provides a formal proof-of-concept using complex linguistic examples. It demonstrates that the algorithm can successfully produce the Portuguese translation "É pressuposto que X é capaz de voar" from the English source—a task where traditional ISTAG fails.

From a computational standpoint, the paper shows that extracting semantic dependencies from a parse forest can be achieved in $O(n^7)$ time, while constructing the target derivation forest takes $O(n^4)$ time. While $O(n^7)$ is theoretically high, it represents a polynomial bound for a problem that previously lacked a robust general solution.

Conclusion

By prioritizing semantic dependencies over syntactic derivation history, Schuler’s approach bridges the gap between languages with divergent structural requirements. This work lays the groundwork for more flexible machine translation systems that can maintain meaning across "messy" linguistic boundaries.

Summary updated

BibTeX
@inproceedings{schuler1999preserving,
  author = {William Schuler},
  title = {{Preserving Semantic Dependencies in Synchronous Tree Adjoining Grammar}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/1034678.1034701},
}
Figure