Solving General Arithmetic Word Problems

Summary

The paper solves multi-step arithmetic word problems without predefined equation templates by representing the answer as an expression tree in which each number from the text is used at most once. The key result is that for "monotonic" trees (subtraction placed above addition, division above multiplication) the operation at the lowest common ancestor of any pair of numbers is uniquely determined. Building the tree therefore reduces to simple classification: one classifier decides whether each number is relevant, another predicts the LCA operation for each pair (including reversed subtraction and division). A bottom-up beam search then assembles the tree that maximises the sum of these scores, subject to constraints such as a positive, integer answer. Features come from a "quantity schema": the governing verb, its subject, the unit, related noun phrases and whether the quantity is a rate. Later work by the same authors refers to this system as LCA++.

How Mova uses it

• math/src/arith.rs — the core of the arithmetic tree model: a relevance judgement for each number and an operation judgement for each pair of numbers at their lowest common ancestor, both as averaged perceptrons over word features so the deciding words and weights are visible.
• The solver core enumerates expression trees bottom-up with dynamic programming over subsets of numbers and a beam per subset; a tree's score decomposes into the scores of its subtrees plus pairwise operation weights across the split, which keeps the beam search exact with respect to the model. Final answers are recomputed exactly in rational numbers.
• Training uses weak supervision from the gold answer only: for each training problem the smallest tree that yields the answer becomes the "gold" tree for a structured perceptron.

Effectiveness in Mova

The arith model has been measured as an extra signal for the main SVAMP solver's judge (its answer as a feature, computed fairly across folds): SVAMP 56.3% versus 57.3% without it, i.e. no gain. An earlier record of 58.3% turned out to be a lucky run caused by non-deterministic map ordering in arith (results varied between 55.3% and 58.3%); after making it deterministic the result is a stable 56.3%. The standalone accuracy of the arith model is not reported separately.

👨‍🔬💥

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/d15-1202 · arXiv 1608.01413

@inproceedings{roy2015solving,
  title = {{Solving General Arithmetic Word Problems}},
  author = {Roy, Subhro and Roth, Dan},
  booktitle = {Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  doi = {10.18653/v1/d15-1202},
  eprint = {1608.01413},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/d15-1202}
}

References

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

1. R. Barzilay and M. Lapata. 2006. Aggregation via Set Partitioning for Natural Language Generation. In Human Language Technologies - North American Chapter of the Association for Computational Linguistics, June. find
2. J. Berant, V. Srikumar, P. Chen, A. V. Linden, B. Harding, B. Huang, P. Clark, and C. D. Manning. 2014. Modeling biological processes for reading comprehension. In Proceedings of EMNLP. find
3. M. Chang, L. Ratinov, and D. Roth. 2012. Structured learning with constrained conditional models. Machine Learning, 88(3):399–431, 6. find
4. P. Clark. 2015. Elementary School Science and Math Tests as a Driver for AI: Take the Aristo Challenge! In Proceedings of IAAI. find
5. J. Clarke and M. Lapata. 2006. Constraint-based sentence compression: An integer programming approach. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 144–151, Sydney, Australia, July. ACL. find
6. Y. Goldberg and M. Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750, Los Angeles, California, June. find
7. M. J. Hosseini, H. Hajishirzi, O. Etzioni, and N. Kushman. 2014. Learning to solve arithmetic word problems with verb categorization. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, pages 523–533. find our card
8. N. Kushman, L. Zettlemoyer, R. Barzilay, and Y. Artzi. 2014. Learning to automatically solve algebra word problems. In ACL, pages 271–281. find
9. V. Punyakanok, D. Roth, and W. Yih. 2005. The necessity of syntactic parsing for semantic role labeling. In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1117–1123. find
10. V. Punyakanok, D. Roth, and W. Yih. 2008. The importance of syntactic parsing and inference in semantic role labeling. Computational Linguistics, 34(2). find
11. D. Roth and W. Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Hwee Tou Ng and Ellen Riloff, editors, Proc. of the Conference on Computational Natural Language Learning (CoNLL), pages 1–8. Association for Computational Linguistics. find
12. D. Roth and W. Yih. 2005. Integer linear programming inference for conditional random fields. In Proc. of the International Conference on Machine Learning (ICML), pages 737–744. find
13. S. Roy, T. Vieira, and D. Roth. 2015. Reasoning about quantities in natural language. Transactions of the Association for Computational Linguistics, 3. find
14. F. Sadeghi, S. K. Divvala, and A. Farhadi. 2015. Viske: Visual knowledge extraction and question answering by visual verification of relation phrases. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June. find
15. M. J. Seo, H. Hajishirzi, A. Farhadi, and O. Etzioni. 2014. Diagram understanding in geometry questions. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada., pages 2831– 2838. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/roy-2015-solving-general-arithmetic-word-problems/