Elamur Research⌕
☰
home / papers / 2016 / Constraint-Based Question Answering with Knowledge Graph

Constraint-Based Question Answering with Knowledge Graph

Paper · 2016 · Junwei Bao, Nan Duan, Zhao Yan et al.

Summary

Popular KBQA benchmarks such as WebQuestions and SimpleQuestions consist mostly of questions answerable through a single Freebase relation. They therefore reveal little about how systems handle questions with several restrictions on the answer. Bao et al. address this gap in two ways.

First, they release ComplexQuestions, a dataset of 2,100 multi-constraint question–answer pairs. It combines filtered search-engine queries, existing resources and manual labeling. Second, they propose a systematic KBQA approach. A question is mapped to a multi-constraint query graph (MulCG): a basic subject–path–answer graph is extended step by step with an ordered sequence of constraints. These constraints are expressed through relational edges and functional predicates such as comparison, ranking and counting, and the graph is then executed against Freebase.

Compared with a re-implemented STAGG baseline, the method gains roughly 4 F1 points on ComplexQuestions and stays on par on WebQuestions. It also performs reasonably on SimpleQuestions. The work matters because it gives the field both a benchmark and a structured method for compositional questions beyond single-relation lookup.

Key points

  • The paper defines six constraint categories, with these frequencies in web queries: multi-entity (30.6%), type (38.8%), explicit temporal (10.4%), implicit temporal (3.5%), ordinal (5.1%) and aggregation (1.2%).
  • ComplexQuestions has 2,100 QA pairs, split into 1,300 train and 800 test. Its sources are:
    • 596 training and 326 test pairs from WebQuestions,
    • 300 pairs from Yin et al. (2015),
    • 878 newly hand-labeled pairs drawn from a three-month 2015 search log of about 21M distinct 5W1H questions.
  • Functional predicates in the query graph include Equal, <, >, MaxAtN, MinAtN and Count. Each is triggered by cues such as "before/after", WordNet superlatives or "how many".
  • On ComplexQuestions, the best setting reaches 42.33 F1 versus 37.69 for STAGG. Removing constraints costs about 10.5 points.
  • On WebQuestions the method scores 54.36 average F1 (STAGG re-implementation: 54.30). On SimpleQuestions it reaches 72.78 accuracy using a dictionary-based entity linker.

Interesting ideas

  • I1. Building a "hard" benchmark by mining logs with cheap heuristics. The authors filter real queries with simple rules before annotation: length limits, no pronouns, a detected entity, vocabulary overlap with the training data, and category triggers. This keeps human effort focused on relevant candidates and could be reused to build challenge sets for low-resource languages.
  • I2. Sampling annotation candidates by the observed distribution of phenomena. The selected candidates mirror the observed frequency of each constraint type. As a result, the benchmark reflects what users actually ask rather than what is easy to generate.
  • I3. Composing a query incrementally. The query starts from a simple core graph, and constraints are attached one at a time in a fixed order. This modular design lets new constraint types (e.g., temporal or ordinal) be added without redesigning the whole parser.
  • I4. Rewriting implicit time as explicit time. Clauses like "when the Civil War started" are first resolved to a concrete date and then treated as a normal temporal comparison. Reducing a hard case to an already solved one is a reusable trick for temporal QA.
  • I5. Ablating constraints and training-data mixtures separately. The authors measure the effect of adding constraints independently from the effect of enlarging CNN training data with other datasets. This clarifies where the gains actually come from, which is a good evaluation practice for any pipeline.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢MicrosoftRedmond · United States240 works · 123,537 citations🎓Harbin Institute of TechnologyHarbin · China76 works · 27,918 citations🎓Beihang UniversityBeijing · China27 works · 8,089 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 2Research subjects and languages the work is about.Question answering · 242 worksKnowledge graphs & ontologies · 103 works

Cite

Cite as Junwei Bao, Nan Duan, Zhao Yan, Ming Zhou and Tiejun Zhao. 2016. Constraint-Based Question Answering with Knowledge Graph. Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{bao2016constraint,
  title = {{Constraint-Based Question Answering with Knowledge Graph}},
  author = {Junwei Bao, Nan Duan, Zhao Yan, Ming Zhou and Tiejun Zhao},
  booktitle = {Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers},
  year = {2016},
  url = {https://aclanthology.org/C16-1236/}
}

References

29 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Junwei Bao, Nan Duan, Ming Zhou, and Tiejun Zhao. 2014. Knowledge-based question answering as machine translation. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 967–976, Baltimore, Maryland, June. Association for Computation… find
  2. Jonathan Berant and Percy Liang. 2014. Semantic parsing via paraphrasing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 1: Long Papers, pages 1415–1425.
  3. Jonathan Berant and Percy Liang. 2015. Imitation learning of agenda-based semantic parsers. Transactions of the Association for Computational Linguistics, 3:545–558. find
  4. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on Freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1533–1544, Seattle, Washington, USA, October. Association for Computational Ling…
  5. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247–1250. ACM. find
  6. Antoine Bordes, Sumit Chopra, and Jason Weston. 2014a. Question answering with subgraph embeddings. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL, pages… find
  7. Antoine Bordes, Jason Weston, and Nicolas Usunier. 2014b. Open question answering with weakly supervised embedding models. In Machine Learning and Knowledge Discovery in Databases, pages 165–180. Springer. find
  8. Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015. Large-scale simple question answering with memory networks. arXiv preprint arXiv:1506.02075. find
  9. Christopher JC Burges. 2010. From ranknet to lambdarank to lambdamart: An overview. Learning, 11:23–581. find
  10. Marie-Catherine De Marneffe, Bill MacCartney, Christopher D Manning, et al. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of LREC, volume 6, pages 449–454.
  11. Li Dong, Furu Wei, Ming Zhou, and Ke Xu. 2015. Question answering over freebase with multi-column convolutional neural networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volum… find
  12. Anthony Fader, Luke Zettlemoyer, and Oren Etzioni. 2014. Open question answering over curated and extracted knowledge bases. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1156–1165. ACM. find
  13. Jenny Rose Finkel, Trond Grenager, and Christopher Manning. 2005. Incorporating non-local information into information extraction systems by gibbs sampling. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 363–370. Association for Computational Linguistic…
  14. Jianfeng Gao, Li Deng, Michael Gamon, Xiaodong He, and Patrick Pantel. 2015. Modeling interestingness with deep neural networks, December 17. US Patent 20,150,363,688. find
  15. George A Miller. 1995. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39–41.
  16. Siva Reddy, Mirella Lapata, and Mark Steedman. 2014. Large-scale semantic parsing without question-answer pairs. Transactions of the Association for Computational Linguistics, 2:377–392. find
  17. Siva Reddy, Oscar Täckström, Michael Collins, Tom Kwiatkowski, Dipanjan Das, Mark Steedman, and Mirella Lapata. 2016. Transforming dependency structures to logical forms for semantic parsing. Transactions of the Association for Computational Linguistics, 4:127–140. find
  18. Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014a. A latent semantic model with convolutional-pooling structure for information retrieval. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 101–110. ACM. find
  19. Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014b. Learning semantic representations using convolutional neural networks for web search. In Proceedings of the companion publication of the 23rd international conference on World wide web companion, pages 373–374. Internation… find
  20. Zhenghao Wang, Shengquan Yan, Huaming Wang, and Xuedong Huang. 2014. An overview of microsoft deep qa system on stanford webquestions benchmark. Technical report, Technical report, Microsoft Research. find
  21. Kun Xu, Siva Reddy, Yansong Feng, Songfang Huang, and Dongyan Zhao. 2016. Question answering on freebase via relation extraction and textual evidence. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2326–2336, Berlin, Germany,…
  22. Yi Yang and Ming-Wei Chang. 2015. S-mart: Novel tree-based structured learning algorithms applied to tweet entity linking. find
  23. Min-Chul Yang, Nan Duan, Ming Zhou, and Hae-Chang Rim. 2014. Joint relational embeddings for knowledge-based question answering. In EMNLP, pages 645–650. find
  24. Xuchen Yao and Benjamin Van Durme. 2014. Information extraction over structured data: Question answering with freebase. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 1: Long Papers, pages 956–966. find
  25. Xuchen Yao. 2015. Lean question answering over freebase from scratch. In Proceedings of NAACL-HLT, pages 66–70. find
  26. Wen-tau Yih, Xiaodong He, and Christopher Meek. 2014. Semantic parsing for single-relation question answering. In ACL (2), pages 643–648. Citeseer.
  27. Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao. 2015. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natur…
  28. Pengcheng Yin, Nan Duan, Ben Kao, Junwei Bao, and Ming Zhou. 2015. Answering questions with complex semantic constraints on open knowledge bases. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 1301–1310. ACM. find
  29. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA - Short Papers, pages 1… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bao-2016-constraint-based-question-answering-knowledge/