Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction

Summary

The paper treats solving a math word problem as multi-step relation extraction between quantities, instead of generating an expression tree top-down as seq2tree and graph2tree models do. At each step the model, DeductReasoner, picks a pair of known quantities and an operation (including reversed subtraction and division), and adds the result to the pool of quantities. A result can be used again, so shared subexpressions are not duplicated. Quantity representations come from a pretrained encoder (BERT/RoBERTa). A pair is scored from the concatenation and element-wise product of its two vectors, with a separate scorer per operation and a binary terminator that decides when to stop. After each step a GRU-based "rationalizer" updates all quantity representations so the model does not repeat the same first step. On MAWPS, Math23k, MathQA and SVAMP it outperforms strong tree-generation baselines, especially on multi-step problems. Every step is an explicit binary operation over known values, which makes the reasoning chain inspectable.

How Mova uses it

• math/src/deduct.rs (math solver v5, mathsolve steps --dag): a transparent reimplementation of the DeductReasoner idea as a graph of subproblems (DAG). The pool holds the numbers from the text plus all intermediate results, nothing is ever removed, and each step combines two pool items with an operation. Stopping means the last created value is the answer, and the exact arithmetic core computes every step.
• Adaptation: the neural encoder, rationalizer and terminator are replaced by an averaged structured perceptron with beam search and early update. It uses the same non-lexical features as the tree solver (math/src/steps.rs: verb classes, rates, units, subject and question words), computed for each pooled value through a representative leaf. Weights are a dense feature-hashed array so that scanning all pool pairs stays fast. A dynamic oracle supplies training targets.

Effectiveness in Mova

Measured in the commit that introduced the module: SVAMP 49.7% with the reranking judge (45.7% without), and GSM8K 7.0%, both with canonical step order and with the dynamic oracle. The model did not learn long problems: the space of pool pairs is too large for the beam. The tree-based solver therefore stayed the working default, and the DAG solver is kept as an experiment. For reference, project notes list the neural DeductReasoner at 47.3 on SVAMP.

👨‍🔬💥

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/2022.acl-long.410 · arXiv 2203.10316

@inproceedings{jie2022learning,
  title = {{Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction}},
  author = {Jie, Zhanming and Li, Jierui and Lu, Wei},
  booktitle = {Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2022},
  doi = {10.18653/v1/2022.acl-long.410},
  eprint = {2203.10316},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2022.acl-long.410}
}

References

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

1. Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannaneh Hajishirzi. 2019. Mathqa: Towards interpretable math word problem solving with operation-based formalisms. In Proceedings of NAACL. find
2. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016. Neural module networks. In Proceedings of CVPR. find
3. Yoshua Bengio, Yann Lecun, and Geoffrey Hinton. 2021. Deep learning for ai. Communications of the ACM, 64(7):58–65. find
4. Tarek R Besold, Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pascal Hitzler, Kai-Uwe Kühnberger, Luis C Lamb, Daniel Lowd, Priscila Machado Vieira Lima, et al. 2017. Neural-symbolic learning and reasoning: A survey and interpretation. arXiv preprint arXiv:1711.03902. — [arXiv:1711.03902](https://arxiv.org/abs/1711.03902) find
5. Daniel G Bobrow. 1964. Natural language input for a computer problem solving system. find
6. Yixuan Cao, Feng Hong, Hongwei Li, and Ping Luo. 2021. A bottom-up dag structure extraction model for math word problems. In Proceedings of AAAI. find
7. Ting-Rui Chiang and Yun-Nung Chen. 2019. Semantically-aligned equation generation for solving and reasoning math word problems. In Proceedings of NAACL. find
8. Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder–decoder approaches. In Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation. find
9. Eldan Cohen and Christopher Beck. 2019. Empirical analysis of beam search performance degradation in neural sequence models. In Proceedings of ICML. find
10. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP. find our card
11. Alexis Conneau, Kartikay Khandelwal, Naman Goyal Vishrav Chaudhary Guillaume Wenzek, Francisco Guzmán, Edouard Grave Myle Ott Luke Zettlemoyer, and Veselin Stoyanov. 2020. Unsupervised cross-lingual representation learning at scale. In Proceedings of ACL. find
12. Yiming Cui, Wanxiang Che, Ting Liu, Bing Qin, Ziqing Yang, Shijin Wang, and Guoping Hu. 2019. Pre-training with whole word masking for chinese bert. arXiv preprint arXiv:1906.08101. find
13. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL. find
14. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep learning. MIT press. find
15. Nitish Gupta, Kevin Lin, Dan Roth, Sameer Singh, and Matt Gardner. 2020. Neural module networks for reasoning over text. In Proceedings of ICLR. find
16. Chris Hokamp and Qun Liu. 2017. Lexically constrained decoding for sequence generation using grid beam search. In Proceedings of ACL. find
17. Danqing Huang, Jing Liu, Chin-Yew Lin, and Jian Yin. 2018. Neural math word problem solver with reinforcement learning. In Proceedings of COLING. find
18. Daniel Kahneman. 2011. Macmillan. find
19. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In Proceedings of ICML. find
20. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. find
21. Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proceedings of ICLR. find
22. Philipp Koehn and Rebecca Knowles. 2017. Six challenges for neural machine translation. In Proceedings of the First Workshop on Neural Machine Translation, ACL. find
23. Rik Koncel-Kedziorski, Subhro Roy, Aida Amini, Nate Kushman, and Hannaneh Hajishirzi. 2016. Mawps: A math word problem repository. In Proceedings of NAACL. find
24. Nate Kushman, Yoav Artzi, Luke Zettlemoyer, and Regina Barzilay. 2014. Learning to automatically solve algebra word problems. In Proceedings of ACL. find
25. Yihuai Lan, Lei Wang, Qiyuan Zhang, Yunshi Lan, Bing Tian Dai, Yan Wang, Dongxiang Zhang, and Ee-Peng Lim. 2021. Mwptoolkit: An open-source framework for deep learning-based math word problem solvers. arXiv preprint arXiv:2109.00799. find
26. Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017. End-to-end neural coreference resolution. In Proceedings of EMNLP. find our card
27. Kenton Lee, Luheng He, and Luke Zettlemoyer. 2018. Higher-order coreference resolution with coarse-to-fine inference. In Proceedings of NAACL. find
28. Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2016. Rationalizing neural predictions. In Proceedings of EMNLP. find
29. Jierui Li, Lei Wang, Jipeng Zhang, Yan Wang, Bing Tian Dai, and Dongxiang Zhang. 2019. Modeling intra-relation in math word problems with different functional multi-head attentions. In Proceedings of the ACL. find
30. Shucheng Li, Lingfei Wu, Shiwei Feng, Fangli Xu, Fengyuan Xu, and Sheng Zhong. 2020. Graph-to-tree neural networks for learning structured input-output translation with applications to semantic parsing and math word problem. In Proceedings of Findings of EMNLP. find
31. Zhongli Li, Wenxuan Zhang, Chao Yan, Qingyu Zhou, Chao Li, Hongzhi Liu, and Yunbo Cao. 2021. Seeking patterns, not just memorizing procedures: Contrastive learning for solving math word problems. arXiv preprint arXiv:2110.08464. find
32. Chao-Chun Liang, Yu-Shiang Wong, Yi-Chung Lin, and Keh-Yih Su. 2018. A meaning-based statistical english math word problem solver. In Proceedings of NAACL. find
33. Zhenwen Liang, Jipeng Zhang, Jie Shao, and Xiangliang Zhang. 2021. Mwp-bert: A strong baseline for math word problems. arXiv preprint arXiv:2107.13435. find
34. Christian Liguda and Thies Pfeiffer. 2012. Modeling math word problems with augmented semantic networks. In International Conference on Application of Natural Language to Information Systems. find
35. Xin Lin, Zhenya Huang, Hongke Zhao, Enhong Chen, Qi Liu, Hao Wang, and Shijin Wang. 2021. Hms: A hierarchical solver with dependency-enhanced understanding for math word problem. In Proceedings of AAAI. find
36. Minh-Thang Luong, Hieu Pham, and Christopher D Manning. 2015. Effective approaches to attention-based neural machine translation. In Proceedings of EMNLP. find
37. Anirban Mukherjee and Utpal Garain. 2008. A review of methods for automatic understanding of natural language mathematical problems. Artificial Intelligence Review, 29(2):93–122. find
38. Mark-Jan Nederhof. 2003. Weighted deductive parsing and knuth’s algorithm. Computational Linguistics, 29(1):135–143. find
39. Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. Are NLP models really able to solve simple math word problems? In Proceedings of NAACL. find our card
40. Jean Piaget. 1952. Routledge. find
41. Jinghui Qin, Xiaodan Liang, Yining Hong, Jianheng Tang, and Liang Lin. 2021. Neural-symbolic solver for math word problems with auxiliary tasks. In Proceedings of ACL-IJCNLP. find
42. Cassandra A Richards and Jennifer A Sanderson. 1999. The role of imagination in facilitating deductive reasoning in 2-, 3-and 4-year-olds. Cognition, 72(2):B1–B9. find
43. Subhro Roy and Dan Roth. 2015. Solving general arithmetic word problems. In Proceedings of EMNLP. find our card
44. Subhro Roy and Dan Roth. 2018. Mapping to declarative knowledge for word problem solving. Transactions of the Association for Computational Linguistics, 6:159–172. find our card
45. Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu. 2021. Generate & rank: A multi-task framework for math word problems. In Proceedings of Findings of EMNLP. find
46. Yibin Shen and Cheqing Jin. 2020. Solving math word problems with multi-encoders and multi-decoders. In Proceedings of COLING. find
47. Stuart M Shieber, Yves Schabes, and Fernando CN Pereira. 1995. Principles and implementation of deductive parsing. The Journal of logic programming, 24(1-2):3–36. find
48. Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In Proceedings of ACL. find
49. Minghuan Tan, Lei Wang, Lingxiao Jiang, and Jing Jiang. 2021. Investigating math word problems using pretrained multilingual language models. arXiv preprint arXiv:2105.08928. find
50. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692. find
51. 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 Proceedings of NeurIPS. find
52. Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In Proceedings of ICLR. find
53. Piia Maria Vilenius-Tuohimaa, Kaisa Aunola, and Jari-Erik Nurmi. 2008. The association between mathematical word problems and reading comprehension. Educational Psychology, 28(4):409–426. find
54. Lei Wang, Dongxiang Zhang, Jipeng Zhang, Xing Xu, Lianli Gao, Bing Tian Dai, and Heng Tao Shen. 2019. Template-based math word problem solvers with recursive neural networks. In Proceedings of AAAI. find
55. Yan Wang, Xiaojiang Liu, and Shuming Shi. 2017. Deep neural solver for math word problems. In Proceedings of EMNLP. find
56. Ronald J Williams and David Zipser. 1989. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270– 280. find
57. Thomas Wolf, Julien Chaumond, Lysandre Debut, Victor Sanh, Clement Delangue, Anthony Moi, Pier-ric Cistac, Morgan Funtowicz, Joe Davison, Sam Shleifer, et al. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of EMNLP: System Demonstrations. find
58. Qinzhuo Wu, Qi Zhang, Jinlan Fu, and Xuan-Jing Huang. 2020. A knowledge-aware sequence-to-tree network for math word problem solving. In Proceedings of EMNLP. find
59. Qinzhuo Wu, Qi Zhang, Zhongyu Wei, and Xuan-Jing Huang. 2021. Math word problem solving with explicit numerical values. In Proceedings of ACL-IJCNLP. find
60. Zhipeng Xie and Shichao Sun. 2019. A goal-driven tree-structured neural model for math word problems. In Proceedings of IJCAI. find
61. Dmitry Zelenko, Chinatsu Aone, and Anthony Richardella. 2003. Kernel methods for relation extraction. Journal of machine learning research, 3(Feb). find
62. Jipeng Zhang, Lei Wang, Roy Ka-Wei Lee, Yi Bin, Yan Wang, Jie Shao, and Ee-Peng Lim. 2020. Graph-to-tree learning for solving math word problems. In Proceedings of ACL. find
63. Zexuan Zhong and Danqi Chen. 2021. A frustratingly easy approach for entity and relation extraction. In Proceedings of NAACL. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/jie-2022-learning-reason-deductively-math-word/