Semantic Parsing with Relaxed Hybrid Trees

Wei LuEMNLP 2014 · OpenReview

Abstract

We propose a novel model for parsing natural language sentences into their formal semantic representations. The model is able to perform integrated lexicon acquisition and semantic parsing, mapping each atomic element in a complete semantic representation to a contiguous word sequence in the input sentence in a recursive manner, where certain overlappings amongst such word sequences are allowed. It defines distributions over the novel relaxed hybrid tree structures which jointly represent both sentences and semantics. Such structures allow tractable dynamic programming algorithms to be developed for efficient learning and decoding. Trained under a discriminative setting, our model is able to incorporate a rich set of features where certain unbounded long-distance dependencies can be captured in a principled manner. We demonstrate through experiments that by exploiting a large collection of simple features, our model is shown to be competitive to previous works and achieves state-of-the-art performance on standard benchmark data across four different languages.

Introduction

Semantic parsing—the process of transforming natural language into machine-readable formal logic—is a cornerstone of natural language understanding. A significant hurdle in this task is the non-isomorphism between the linear structure of human language and the hierarchical structure of formal semantics. For example, a query about rivers must be mapped to a complex tree structure that represents the underlying logic of the question.

A formal semantic representation for a query about rivers.

Previous generative models often imposed rigid constraints on how words could map to semantic units, limiting their ability to capture long-distance dependencies or utilize global features effectively. This paper introduces a way to bridge this gap by "relaxing" these structural constraints.

Methodology: Relaxed Hybrid Trees

The core contribution of this work is the Relaxed Hybrid Tree (RHT) representation. Unlike standard hybrid trees where each word is strictly tied to a single semantic unit, RHT allows for more flexible mappings between words and logic.

Structural Relaxation

In an RHT, a word can be "immediately associated" with a semantic node (directly explaining that unit) or "remotely associated" with a parent node (appearing within the subtree of that unit but belonging to a child). This allows the model to handle cases where a word's influence spans across different levels of the semantic hierarchy.

Comparison of a standard hybrid tree (a) and the proposed relaxed hybrid tree (b). The relaxed structure allows for overlapping word spans and remote associations.

As illustrated above, the relaxed structure (b) allows semantic units to cover overlapping contiguous word sequences. This flexibility is crucial for capturing the nuances of natural language where meaning is often distributed across non-contiguous or overlapping spans.

Discriminative Modeling and Latent Variables

The system is built as a discriminative log-linear model, focusing on the conditional probability of a semantic representation given a sentence. This framework supports a massive feature set—over 2 million features in our experiments—including unigrams, bigrams, and character-level prefixes. Because the exact alignments between words and semantic nodes are not observed in training data, they are treated as latent variables. We employ dynamic programming algorithms to marginalize over all valid tree structures during learning and decoding, ensuring the search space remains computationally tractable.

Experiments and Results

We evaluated the RHT model on the GeoQuery dataset, a benchmark of 880 geography-related questions. To demonstrate language independence, we tested on English, German, Greek, and Thai. The model achieved state-of-the-art (SOTA) results at the time of publication:

  • English: 83.6% Accuracy/F1, a significant improvement over the 76.8% achieved by previous hybrid models.
  • Thai & Greek: Achieved 79.3% and 78.2% respectively, leading previous benchmarks.
  • Efficiency: The model remains practical, with average learning and decoding times under half a second per instance.

Conclusion

Relaxed Hybrid Trees offer a robust solution to the non-isomorphism problem in semantic parsing. By relaxing structural constraints and leveraging discriminative learning with latent variables, the model achieves high accuracy across diverse languages without requiring extensive manual engineering. Future research will focus on scaling these methods to larger datasets and exploring weakly supervised learning paradigms.

Summary updated

Abstract

We propose a novel model for parsing natural language sentences into their formal semantic representations. The model is able to perform integrated lexicon acquisition and semantic parsing, mapping each atomic element in a complete semantic representation to a contiguous word sequence in the input sentence in a recursive manner, where certain overlappings amongst such word sequences are allowed. It defines distributions over the novel relaxed hybrid tree structures which jointly represent both sentences and semantics. Such structures allow tractable dynamic programming algorithms to be developed for efficient learning and decoding. Trained under a discriminative setting, our model is able to incorporate a rich set of features where certain unbounded long-distance dependencies can be captured in a principled manner. We demonstrate through experiments that by exploiting a large collection of simple features, our model is shown to be competitive to previous works and achieves state-of-theart performance on standard benchmark data across four different languages. The system and code can be downloaded from http://statnlp.org/research/sp/.
BibTeX
@inproceedings{lu2014semantic,
  author = {Wei Lu},
  title = {{Semantic Parsing with Relaxed Hybrid Trees}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=HyWWkfzu-r},
}
Figure