Effective Search of Logical Forms for Weakly Supervised Knowledge-Based Question Answering

Tao Shen, Xiubo Geng, Guodong Long, Jing Jiang, Chengqi Zhang, Daxin Jiang

Abstract

Training semantic parsers for Knowledge-Based Question Answering (KBQA) typically relies on weak supervision, where models are trained on question-answer pairs without explicit logical forms. This approach faces two major challenges: an astronomical search space for potential logical paths and the presence of "spurious" logical forms that yield correct answers through incorrect reasoning. This paper introduces an operator predictor that prunes the search space by identifying functional operators likely to appear in a question's logical form. By bootstrapping from a denoised 10% subset of the data, the proposed method achieves a 20x search speedup and sets a new state-of-the-art on the Complex Sequential Question Answering (CSQA) dataset.

Introduction

To answer complex natural language questions using a Knowledge Base (KB), systems must translate queries into machine-readable logical forms (e.g., translating "How many rivers flow through Paris?" into a COUNT operation). In weakly supervised settings, these forms are latent. Systems must search the KB for any path that produces the ground-truth answer. However, for complex questions, the search space can reach $10^4$ to $10^5$ paths. This not only increases computational costs but also leads to "spurious" forms—logical paths that happen to reach the correct answer by coincidence (e.g., counting airports instead of rivers), which degrades model training.

Methods

The authors propose a multi-step pipeline to refine the search process before training the final semantic parser:

  1. Initial Seed Search: A naive search is performed on a small 10% subset of the training data to identify potential logical forms.
  2. Unsupervised Question Typing: Using K-means clustering on the discovered logical forms, the system groups questions by type and defines a "legitimate operator set" for each, filtering out logically inconsistent operators.
  3. Operator Predictor Training: A Bi-LSTM model is trained on the cleaned 10% subset to predict functional operators (e.g., FIND, COUNT, UNION) directly from question text.
  4. Constrained Re-searching: The predictor is applied to the entire dataset, pruning the search tree by only exploring paths that use predicted operators.
  5. Final Parser Training: A standard sequence-to-sequence parser is trained using the high-quality, filtered logical forms discovered through the constrained search.
The proposed multi-step pipeline for training and testing.

Experimental Setup

The approach was evaluated on the Complex Sequential Question Answering (CSQA) dataset, which contains 1.6 million question turns across 200,000 dialogues. The underlying Knowledge Base is built on Wikidata, featuring 21.2 million triplets and 12.8 million entities. CSQA's variety—including direct, indirect, comparative, and quantitative questions—provides a rigorous test for search efficiency and parsing accuracy.

Key Results

The proposed method significantly outperformed existing baselines and improved search quality across several metrics:

  • Accuracy: The model achieved new state-of-the-art results, improving the F1 score of the D2A baseline by 4.53% and the MaSP model by 2.02%.
  • Efficiency: Constrained search was 20x faster than naive Breadth-First Search (BFS), reducing average search time per dialog turn from 1.19 seconds to 0.06 seconds.
  • Data Quality: Human evaluation confirmed a reduction in spurious logical forms in the training data, dropping from 54.5% to 26.7%.
  • Search Success: The overall search success ratio (finding at least one valid logical form) increased to 76%, with notable gains in complex reasoning categories like comparative and logical questions.
Overall performance comparison on the CSQA dataset.

Discussion and Key Insights

The core contribution of this work is the realization that functional operators (the "verbs" of the logic) are strongly signaled by natural language phrasing (e.g., "how many" suggests COUNT). By treating operators as semantic anchors, the system can bootstrap a reliable guide from a small, denoised data slice. This "pruning-first" philosophy proves far more efficient than searching the entire space and filtering results post-hoc.

However, challenges remain. Entity Ambiguity continues to be a hurdle; if a system cannot distinguish between different entities with the same name (e.g., a movie vs. its soundtrack), the resulting logical form will be incorrect regardless of operator accuracy. Additionally, as a pipeline approach, errors in early stages like question typing can propagate, preventing the discovery of correct logical forms later. Future work may involve tighter integration between operator prediction and entity linking.

Summary updated

Abstract

Many algorithms for Knowledge-Based Question Answering (KBQA) depend on semantic parsing, which translates a question to its logical form. When only weak supervision is provided, it is usually necessary to search valid logical forms for model training. However, a complex question typically involves a huge search space, which creates two main problems: 1) the solutions limited by computation time and memory usually reduce the success rate of the search, and 2) spurious logical forms in the search results degrade the quality of training data. These two problems lead to a poorly-trained semantic parsing model. In this work, we propose an effective search method for weakly supervised KBQA based on operator prediction for questions. With search space constrained by predicted operators, sufficient search paths can be explored, more valid logical forms can be derived, and operators possibly causing spurious logical forms can be avoided. As a result, a larger proportion of questions in a weakly supervised training set are equipped with logical forms, and fewer spurious logical forms are generated. Such high-quality training data directly contributes to a better semantic parsing model. Experimental results on one of the largest KBQA datasets (i.e., CSQA) verify the effectiveness of our approach and deliver a new state-of-the-art performance.
BibTeX
@inproceedings{shen2020effective,
  author = {Tao Shen and Xiubo Geng and Guodong Long and Jing Jiang and Chengqi Zhang and Daxin Jiang},
  title = {{Effective Search of Logical Forms for Weakly Supervised Knowledge-Based Question Answering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/308},
}
Figure