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.
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.
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