Abstract: Pascual Martínez-Gómez, Yusuke Miyao. Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing.
2016.
Introduction
Tree-to-tree transducers are a powerful framework for structural translation, such as converting natural language syntax trees into formal database queries. A common challenge in this field is the extraction of transformation rules from parallel data. The standard approach, the GHKM algorithm, relies heavily on precise word alignments. However, in large-scale Question Answering (QA) tasks over knowledge bases (KBs) like Freebase, data sparsity makes high-quality word alignments difficult to obtain. With millions of entities but limited training examples, traditional rule extraction often fails to provide sufficient coverage.
This paper introduces a novel algorithm that frames rule extraction as a cost minimization problem. By moving away from rigid heuristic alignments toward a flexible optimization-based approach, the system can generate transformation rules "on-the-fly," significantly improving performance on complex QA tasks.
Methodology: Rule Extraction as Cost Minimization
The core innovation is an algorithm that searches for a tree mapping that minimizes a total cost, rather than requiring perfect alignments. This is achieved through an ensemble of cost functions:
- Tree Size Regularizer: This function penalizes overly large or specific rules, encouraging the model to learn more generalizable patterns.
- Back-off Costs: These are assigned to rules generated dynamically for entities or predicates found in external lexicons.
To find the optimal sequence of rules, the system employs a beam search algorithm. It builds disjoint paths hierarchically from the leaves to the root, storing the results in a weighted hypergraph. This allows the model to tolerate minor noise in the data and find a globally optimal structural mapping.
Back-off Rules and On-the-fly Generation
Traditional transducers often fail when encountering unseen vocabulary. The authors address this by introducing back-off states (e.g., ent for entities, pred for predicates). When the system encounters an unknown phrase, it enters a back-off state and uses external lexicons to construct a rule on the spot.
For example, if the system sees a specific team name not present in the training data, it can use a lexicon to map the phrase to the corresponding KB entity. This "on-the-fly" generation is critical for handling the open-ended vocabulary of massive knowledge bases.
Evaluation and Results
The approach was evaluated on the FREE917 dataset, which consists of 917 questions annotated with logical forms (λ-DCS) executable against Freebase. The researchers used entity and predicate lexicons to facilitate mapping.
The proposed system, t2t, achieved 64% accuracy, outperforming the state-of-the-art SEMPRE parser (62%) and significantly surpassing the best GHKM-based transducer (49%). Key findings include:
- Essential Back-off: Disabling the back-off mechanism caused accuracy to drop to 0%, proving that traditional pre-extracted rules are insufficient for large-scale KB tasks.
- Data Efficiency: Performance saturated at approximately 400 training examples, indicating the model's effectiveness in low-resource scenarios.
Conclusion
By framing rule extraction as a search problem, the authors allow for the use of standard optimization techniques, such as the structured perceptron, to learn feature weights. While the system currently depends on external lexicons and is sensitive to initial parsing errors, it demonstrates that flexible, cost-based rule extraction is a viable path forward for robust semantic parsing. Future work will focus on learning cost function parameters directly from data and improving robustness to syntactic noise.
Summary updated