{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T13:05:52Z","timestamp":1777727152515,"version":"3.51.4"},"reference-count":39,"publisher":"MIT Press - Journals","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p> Recent years have seen increasingly complex question-answering on knowledge bases (KBQA) involving logical, quantitative, and comparative reasoning over KB subgraphs. Neural Program Induction (NPI) is a pragmatic approach toward modularizing the reasoning process by translating a complex natural language query into a multi-step executable program. While NPI has been commonly trained with the \u2018\u2018gold\u2019\u2019 program or its sketch, for realistic KBQA applications such gold programs are expensive to obtain. There, practically only natural language queries and the corresponding answers can be provided for training. The resulting combinatorial explosion in program space, along with extremely sparse rewards, makes NPI for KBQA ambitious and challenging. We present Complex Imperative Program Induction from Terminal Rewards (CIPITR), an advanced neural programmer that mitigates reward sparsity with auxiliary rewards, and restricts the program space to semantically correct programs using high-level constraints, KB schema, and inferred answer type. CIPITR solves complex KBQA considerably more accurately than key-value memory networks and neural symbolic machines (NSM). For moderately complex queries requiring 2- to 5-step programs, CIPITR scores at least 3\u00d7 higher F1 than the competing systems. On one of the hardest class of programs (comparative reasoning) with 5\u201310 steps, CIPITR outperforms NSM by a factor of 89 and memory networks by 9 times. <jats:sup>1<\/jats:sup> <\/jats:p>","DOI":"10.1162\/tacl_a_00262","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T18:09:19Z","timestamp":1556561359000},"page":"185-200","source":"Crossref","is-referenced-by-count":32,"title":["Complex Program Induction for Querying Knowledge Bases in the Absence of Gold Programs"],"prefix":"10.1162","volume":"7","author":[{"given":"Amrita","family":"Saha","sequence":"first","affiliation":[{"name":"IBM Research India."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ghulam Ahmed","family":"Ansari","sequence":"additional","affiliation":[{"name":"IBM Research India."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhishek","family":"Laddha","sequence":"additional","affiliation":[{"name":"IBM Research India."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthik","family":"Sankaranarayanan","sequence":"additional","affiliation":[{"name":"IBM Research India."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soumen","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"bib1","first-page":"1545","volume-title":"NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies","author":"Andreas Jacob","year":"2016"},{"key":"bib2","first-page":"1545","volume-title":"NAACL-HLT","author":"Andreas Jacob","year":"2016"},{"key":"bib3","first-page":"438","volume-title":"Proceedings of the 8th Conference on Intelligent Autonomous Systems IAS-8","author":"Bakker B.","year":"2004"},{"issue":"1","key":"bib4","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1022140919877","volume":"13","author":"Barto Andrew G.","year":"2003","journal-title":"Discrete Event Dynamic Systems"},{"key":"bib5","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1145\/2806416.2806472","volume-title":"CIKM","author":"Bast Hannah","year":"2015"},{"key":"bib6","first-page":"1533","volume-title":"EMNLP Conference","author":"Berant J.","year":"2013"},{"key":"bib7","first-page":"2787","volume-title":"NIPS Conference","author":"Bordes Antoine","year":"2013"},{"key":"bib8","first-page":"547","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Bosnjak Matko","year":"2017"},{"key":"bib9","volume-title":"International Conference on Learning Representations (ICLR)","author":"Bunel Rudy","year":"2018"},{"key":"bib10","first-page":"358","volume-title":"ACL (2)","author":"Das Rajarshi","year":"2017"},{"key":"bib11","first-page":"271","volume-title":"Advances in Neural Information Processing Systems 5, [NIPS Conference]","author":"Dayan Peter","year":"1993"},{"issue":"1","key":"bib12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1613\/jair.639","volume":"13","author":"Dietterich Thomas G.","year":"2000","journal-title":"Journal of Artificial Intelligence Research"},{"key":"bib13","first-page":"33","volume-title":"ACL","volume":"1","author":"Li Dong","year":"2016"},{"key":"bib14","volume-title":"EMNLP Conference","author":"Guu Kelvin","year":"2015"},{"key":"bib15","first-page":"1821","volume-title":"ACL","volume":"1","author":"Iyyer Mohit","year":"2017"},{"issue":"1","key":"bib16","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.ipm.2011.02.009","volume":"48","author":"Karimi Sarvnaz","year":"2012","journal-title":"Information Processing & Management"},{"key":"bib17","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1007\/978-3-540-78646-7_83","volume-title":"Proceedings of the IR Research, 30th European Conference on Advances in Information Retrieval","author":"Khalid Mahboob Alam","year":"2008"},{"issue":"6266","key":"bib18","doi-asserted-by":"crossref","first-page":"1332","DOI":"10.1126\/science.aab3050","volume":"350","author":"Lake Brenden M.","year":"2015","journal-title":"Science"},{"key":"bib19","volume-title":"International Conference on Learning Representations (ICLR)","author":"Li Chengtao","year":"2016"},{"key":"bib20","first-page":"556","volume-title":"COLING","author":"Li X.","year":"2002"},{"key":"bib21","first-page":"23","volume-title":"Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics","author":"Liang Chen","year":"2017"},{"key":"bib22","first-page":"132","volume-title":"Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2017, Volume 1: Long Papers","author":"McCallum Andrew","year":"2017"},{"key":"bib23","first-page":"1400","volume-title":"EMNLP","author":"Miller Alexander H.","year":"2016"},{"key":"bib24","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/0743-1066(94)90035-3","volume":"19","author":"Muggleton Stephen","year":"1994","journal-title":"Journal of Logic Programming"},{"key":"bib25","author":"Neelakantan Arvind","year":"2016","journal-title":"arXiv preprint, arXiv: 1611.08945"},{"key":"bib26","author":"Neelakantan Arvind","year":"2015","journal-title":"CoRR"},{"key":"bib27","first-page":"1043","volume-title":"Proceedings of the 1997 Conference on Advances in Neural Information Processing Systems 10","author":"Parr Ronald","year":"1998"},{"key":"bib28","author":"Pasupat Panupong","year":"2015","journal-title":"arXiv preprint arXiv:1508.00305"},{"key":"bib29","author":"Ranzato Marc\u2019Aurelio","year":"2015","journal-title":"CoRR"},{"key":"bib30","volume-title":"International Conference on Learning Representations (ICLR)","author":"Reed Scott","year":"2016"},{"key":"bib31","volume-title":"AAAI","author":"Saha Amrita","year":"2018"},{"issue":"1","key":"bib32","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(99)00052-1","volume":"112","author":"Sutton Richard S.","year":"1999","journal-title":"Artificial Intelligence"},{"key":"bib33","doi-asserted-by":"crossref","first-page":"1296","DOI":"10.3115\/v1\/D14-1136","volume-title":"Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Tsarfaty Reut","year":"2014"},{"key":"bib34","first-page":"241","volume-title":"Proceedings of the 1st International Joint Conference on Artificial Intelligence","author":"Waldinger Richard J.","year":"1969"},{"key":"bib35","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-1-4615-3618-5_2","volume-title":"Reinforcement Learning","author":"Williams Ronald J","year":"1992"},{"key":"bib36","author":"Kun Xu","year":"2016","journal-title":"arXiv preprint, arXiv: 1603.00957"},{"key":"bib37","first-page":"66","volume-title":"NAACL Conference","author":"Yao Xuchen","year":"2015"},{"key":"bib38","first-page":"1321","volume-title":"ACL Conference","author":"Yih Scott Wen-tau","year":"2015"},{"key":"bib39","first-page":"201","volume-title":"Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)","volume":"2","author":"Yih Wen-tau","year":"2016"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:39:20Z","timestamp":1615585160000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/43524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":39,"alternative-id":["10.1162\/tacl_a_00262"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00262","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}