Elamur Research⌕
☰
home / papers / 2020 / PRover: Proof Generation for Interpretable Reasoning over Rules

PRover: Proof Generation for Interpretable Reasoning over Rules

Paper · 2020 · Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava et al.

Summary

Clark et al. (2020) showed that RuleTakers, a fine-tuned RoBERTa, can decide whether a statement follows from facts and rules written in English. However, it gives no justification for its answers. PRover addresses this by producing an answer together with an explicit proof. Each proof is a directed graph whose nodes are facts, rules or a special NAF (negation as failure) node, and whose edges show how facts feed rules and how rule outputs feed other rules.

A shared RoBERTa encoder supports three components:

  • a binary QA head;
  • a node classifier that selects proof elements;
  • an edge classifier that predicts links and their direction.

The three are trained with a joint cross-entropy loss. During training, edges that cannot occur are masked out. At inference, an ILP enforces global validity constraints, including connectivity checked through a max-flow formulation.

On the synthetic, hand-authored and paraphrased rule-bases from Clark et al., PRover matches or exceeds RuleTakers on QA, generates exactly correct proofs about 87% of the time, and generalizes better to deeper reasoning. This makes it a step toward interpretable, structured explanations in NLP.

Key points

  • Exact proof accuracy is about 87%, falling to roughly 65% for depth-5 questions.
  • Zero-shot QA improves by up to 6% over RuleTakers, and unlike RuleTakers, PRover needs no extra fine-tuning on RACE.
  • When trained on shallow questions and tested on deeper ones, QA accuracy is up to 15% higher; with only 40% of the training data, PRover still reaches about 98% QA accuracy.
  • Error analysis on DU5 depth 5:
    • NAF is predicted correctly 95% of the time.
    • Among wrong node sets, 42% are subsets of the gold set and 25% are supersets, so the model tends to miss needed rules and facts.
    • Edge direction is almost never the cause of errors.
  • Code and models are available at github.com/swarnaHub/PRover.

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

🏢IBMArmonk · United States85 works · 66,118 citations🎓University of North Carolina at Chapel HillChapel Hill · United States37 works · 14,332 citations🎓Toyota Technological Institute at ChicagoChicago · United States29 works · 10,273 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

🧭 Topics 1 Reasoning · 510 works

Cite

Cite as Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava and Mohit Bansal. 2020. PRover: Proof Generation for Interpretable Reasoning over Rules. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.emnlp-main.9

@inproceedings{saha2020prover,
  title = {{PRover: Proof Generation for Interpretable Reasoning over Rules}},
  author = {Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava and Mohit Bansal},
  booktitle = {Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.9},
  url = {https://doi.org/10.18653/v1/2020.emnlp-main.9}
}

References

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

  1. Ralph Abboud, Ismail Ilkan Ceylan, and Thomas Lukasiewicz. 2020. Learning to reason: Leveraging neural networks for approximate DNF counting. In Proceedings of the 34th AAAI Conference on Artificial Intelligence. find
  2. Ibrahim Abdelaziz, Veronika Thost, Maxwell Crouse, and Achille Fokoue. 2020. An experimental study of formula embeddings for automated theorem proving in first-order logic. arXiv preprint arXiv:2002.00423. — [arXiv:2002.00423](https://arxiv.org/abs/2002.00423) find
  3. Mohit Bansal, Claire Cardie, and Lillian Lee. 2008. The power of negative thinking: Exploiting label disagreement in the min-cut classification framework. In COLING 2008: Companion Volume: Posters, pages 15–18. find
  4. Regina Barzilay and Mirella Lapata. 2005. Collective content selection for concept-to-text generation. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 331–338. Association for Computational Linguistics. our card
  5. 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. our card
  6. 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. our card
  7. Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom. 2018. e-SNLI: Natural language inference with natural language explanations. In Advances in Neural Information Processing Systems, pages 9539–9549. our card
  8. Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020. Transformers as soft reasoners over language. In International Joint Conference on Artificial Intelligence. our card
  9. Ido Dagan, Dan Roth, Mark Sammons, and Fabio Massimo Zanzotto. 2013. Recognizing textual entailment: Models and applications. Synthesis Lectures on Human Language Technologies, 6(4):1–220. find
  10. Finale Doshi-Velez and Been Kim. 2017. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608. our card
  11. Shimon Even and R Endre Tarjan. 1975. Network flow and testing graph connectivity. SIAM journal on computing, 4(4):507–518. find
  12. Peter Hase and Mohit Bansal. 2020. Evaluating explainable AI: Which algorithmic explanations help users predict model behavior? In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. our card
  13. Han He and Jinho Choi. 2020. Establishing strong baselines for the new decade: Sequence tagging, syntactic and semantic parsing with bert. In The Thirty-Third International Flairs Conference. find
  14. Shalmali Joshi, Oluwasanmi Koyejo, Been Kim, and Joydeep Ghosh. 2018. xGEMs: Generating examplars to explain black-box models. arXiv preprint arXiv:1806.08867. — [arXiv:1806.08867](https://arxiv.org/abs/1806.08867) find
  15. Aishwarya Kamath and Rajarshi Das. 2019. A survey on semantic parsing. In Automated Knowledge Base Construction (AKBC). find
  16. Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy. 2017. RACE: Large-scale reading comprehension dataset from examinations. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 785–794. our card
  17. Guillaume Lample and François Charton. 2020. Deep learning for symbolic mathematics. In 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net. find
  18. Tom Leighton and Satish Rao. 1999. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832. find
  19. Kevin Lin, Oyvind Tafjord, Peter Clark, and Matt Gardner. 2019. Reasoning over paragraph effects in situations. In Proceedings of the 2nd Workshop on Machine Reading for Question Answering, pages 58– 62, Hong Kong, China. Association for Computational Linguistics. our card
  20. Hui Liu, Qingyu Yin, and William Yang Wang. 2019a. Towards explainable NLP: A generative explanation framework for text classification. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5570–5581. find
  21. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b. find
  22. RoBERTa: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692. find
  23. Bill MacCartney and Christopher D Manning. 2014. Natural logic and natural language inference. In Computing meaning, pages 129–147. Springer. find
  24. Mark A Musen and Johan Van Der Lei. 1988. Of brittleness and bottlenecks: Challenges in the creation of pattern-recognition and expert-system models. In Machine Intelligence and Pattern Recognition, volume 7, pages 335–352. Elsevier. find
  25. Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever. 2016. Neural programmer: Inducing latent programs with gradient descent. In 4th International Conference on Learning Representations, ICLR 2016, Conference Track Proceedings. find
  26. Allen Newell and Herbert Simon. 1956. The logic theory machine–a complex information processing system. IRE Transactions on information theory, 2(3):61–79. find
  27. Bo Pang and Lillian Lee. 2004. A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts. In Proceedings of the 42nd annual meeting on Association for Computational Linguistics, page 271. Association for Computational Linguistics. our card
  28. Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. 2019. Explain yourself! leveraging language models for commonsense reasoning. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4932–4942. our card
  29. Scott E. Reed and Nando de Freitas. 2016. Neural programmer-interpreters. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. find
  30. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. ”Why should I trust you?”: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144. our card
  31. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018. Anchors: High-precision model-agnostic explanations. In Thirty-Second AAAI Conference on Artificial Intelligence. find
  32. Kyle Richardson, Hai Hu, Lawrence S Moss, and Ashish Sabharwal. 2020. Probing natural language inference models through semantic fragments. In Thirty-Fourth AAAI Conference on Artificial Intelligence. our card
  33. Cynthia Rudin. 2019. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206–215. our card
  34. Pouya Samangouei, Ardavan Saeedi, Liam Nakagawa, and Nathan Silberman. 2018. ExplainGAN: Model explanation via decision boundary crossing transformations. In Proceedings of the European Conference on Computer Vision (ECCV), pages 666–681. find
  35. David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. 2019. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations. our card
  36. Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. 2019. Learning a SAT solver from single-bit supervision. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. find
  37. Oyvind Tafjord, Matt Gardner, Kevin Lin, and Peter Clark. 2019. QuaRTz: An open-domain dataset of qualitative relationship questions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (E… find
  38. Alon Talmor, Yanai Elazar, Yoav Goldberg, and Jonathan Berant. 2019. oLMpics–on what language model pre-training captures. arXiv preprint arXiv:1912.13283. our card
  39. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008. our card
  40. Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F. Wong, and Lidia S. Chao. 2019. Learning deep transformer models for machine translation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1810–1822, Florence, Italy. Association for Co… our card
  41. Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. 2019. NLProlog: Reasoning with weak unification for question answering in natural language. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 6151–6161, Florence, Ital… find
  42. Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015. Towards AI-complete question answering: A set of prerequisite toy tasks. arXiv preprint arXiv:1502.05698. our card
  43. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier-ric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019. Huggingface’s transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.03771. train, validation and test split… our card
  44. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/saha-2020-prover-proof-generation-interpretable-reasoning/