Elamur Research⌕
☰
home / papers / 2015 / Semantic Parsing via Staged Query Graph Generation: Question Answering with Knowledge Base

Semantic Parsing via Staged Query Graph Generation: Question Answering with Knowledge Base

Summary

The paper addresses natural-language question answering over a large knowledge base (KBQA). The central problem is that classical semantic parsers build the logical form independently of the knowledge base. This leads to mismatches between their predicates and the KB schema, and finding the right relation among a vast number of predicates becomes very difficult. The authors, from Microsoft Research, propose representing the meaning of a question as a query graph. This is a graph resembling a fragment of the Freebase knowledge base itself, which maps directly to a λ-calculus query. The graph is built in stages, as a search. First, the system identifies the topic entity in the question, then it determines the core chain of relations leading to the answer, and finally it adds constraints and aggregation. Each candidate is scored by a log-linear reward model, and the search follows a best-first strategy. Because the knowledge base is involved from the early steps, the search space is substantially reduced. To match a question to a sequence of predicates, the authors use a deep CNN, and for entity recognition, a strong entity linking system. On WebQuestions, the system achieved an F1 of 52.5%, clearly outperforming previous methods.

Key points

  • Result: F1 = 52.5% on WebQuestions. This is 7.2 points (absolute) higher than the best previous method. On the subset of 570 test questions used by Reddy et al. (2014), the system achieves an F1 of 67.0%.
  • Graph generation stages: selecting the topic entity (A_e), building the core inferential chain (A_p), adding constraints (A_c) and aggregation functions, for example argmin (A_a).
  • CNN contribution: when only chain graphs are generated, the PatChain model yields an F1 of 49.6. Adding QuesEP raises it to 50.9, and then ClueWeb raises it to 51.8.
  • Training data: from the training questions, 17,277 query graphs with non-zero F1 and approximately 1.7 million completely incorrect ones were obtained. The CNN was trained on 4,058 "question — predicate chain" pairs. Freebase served as the knowledge base: over 46 million topics and 2.6 billion facts.
  • Error analysis (sample of 100 questions): 35% are due to an incorrect relation chain, 23% to incorrect or missing constraints, and 8% to entity linking. Roughly a third of the "errors" are actually caused by annotation flaws.

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

Fields: AI & machine learning

Topics Question answering Knowledge graphs & ontologies Semantic parsing & meaning representation

Cite

Cite as Wen-tau Yih, Ming-Wei Chang, Xiaodong He and Jianfeng Gao. 2015. Semantic Parsing via Staged Query Graph Generation: Question Answering with Knowledge Base. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p15-1128

@inproceedings{yih2015semantic,
  title = {{Semantic Parsing via Staged Query Graph Generation: Question Answering with Knowledge Base}},
  author = {Wen-tau Yih, Ming-Wei Chang, Xiaodong He and Jianfeng Gao},
  booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)},
  year = {2015},
  doi = {10.3115/v1/p15-1128},
  url = {https://doi.org/10.3115/v1/p15-1128}
}

References

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

  1. Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007. DBpedia: A nucleus for a web of open data. In The semantic web, pages 722–735. Springer. find
  2. 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 Computatio… find
  3. Jonathan Berant and Percy Liang. 2014. Semantic parsing via paraphrasing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1415–1425, Baltimore, Maryland, June. Association for Computational Linguistics. our card
  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… our card
  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, SIGMOD ’08, pages 1247–1250, New York, NY, USA.… 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), pages 615–620, Doha, Qatar, October. Association for Computational Linguistics. find
  7. Antoine Bordes, Jason Weston, and Nicolas Usunier. 2014b. Open question answering with weakly supervised embedding models. In Proceedings of ECML-PKDD. find
  8. Jane Bromley, James W. Bentz, Léon Bottou, Isabelle Guyon, Yann LeCun, Cliff Moore, Eduard Säckinger, and Roopak Shah. 1993. Signature verification using a “Siamese” time delay neural network. International Journal Pattern Recognition and Artificial Intelligence, 7(4):669–688. find
  9. Christopher JC Burges. 2010. From RankNet to LambdaRank to LambdaMart: An overview. Learning, 11:23–581. find
  10. Qingqing Cai and Alexander Yates. 2013. Large-scale semantic parsing via schema matching and lexicon extension. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 423–433, Sofia, Bulgaria, August. Association for Computational Li… find
  11. Evgeniy Gabrilovich, Michael Ringgaard, and Amarnag Subramanya. 2013. FACC1: Freebase annotation of ClueWeb corpora, version 1. Technical report, June. find
  12. Jianfeng Gao, Patrick Pantel, Michael Gamon, Xiaodong He, Li Deng, and Yelong Shen. 2014. Modeling interestingness with deep neural networks. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. find
  13. Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013. Learning deep structured semantic models for Web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, pages 2333–2338. ACM. find
  14. Tom Kwiatkowski, Eunsol Choi, Yoav Artzi, and Luke Zettlemoyer. 2013. Scaling semantic parsers with on-the-fly ontology matching. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1545–1556, Seattle, Washington, USA, October. Association for Computation… our card
  15. Percy Liang. 2013. Lambda dependency-based compositional semantics. Technical report, arXiv. find
  16. Hoifung Poon. 2013. Grounded unsupervised semantic parsing. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 933–943. find
  17. 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
  18. Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Gregoire 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. 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 MSR-TR-2014-121, Microsoft, Sep. find
  21. Yi Yang and Ming-Wei Chang. 2015. S-MART: Novel tree-based structured learning algorithms applied to tweet entity linking. In Annual Meeting of the Association for Computational Linguistics (ACL). find
  22. Min-Chul Yang, Nan Duan, Ming Zhou, and Hae-Chang Rim. 2014. Joint relational embeddings for knowledge-based question answering. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 645–650, Doha, Qatar, October. Association for Computational Lingu… find
  23. 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 (Volume 1: Long Papers), pages 956–966, Baltimore, Maryland, June. Association for Comput… find
  24. Wen-tau Yih, Xiaodong He, and Christopher Meek. 2014. Semantic parsing for single-relation question answering. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 643–648, Baltimore, Maryland, June. Association for Computational… our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yih-2015-semantic-parsing-staged-query-graph/