Mapping to Declarative Knowledge for Word Problem Solving

Summary

Instead of learning each arithmetic operation directly from text, this solver first picks a mathematical concept for every operation in the expression tree and then a specific declarative rule under that concept, which fixes the operation. Four concepts are covered: transfer of objects (verb classes HAVE, GET, GIVE, CONSTRUCT, DESTROY combined with coreference of participants), dimensional analysis (units and rate components), part–whole relations (hyponym, hypernym, siblings) and explicit math phrases ("more than", "times"). Rules operate on pairs of numbers, with a subtree represented by a heuristically chosen representative quantity. The choice of rule is treated as a latent variable, so no expensive rule-level annotation is needed; training uses latent structured SVM followed by a standard structured SVM. The authors also expose dataset biases (e.g. "give" appearing only with subtraction) and collect a minimally perturbed problem set to show that knowledge-based rules generalize better than purely lexical learning.

How Mova uses it

Possession and changes in quantity: a first-level knowledge seed with verb classes have, get, give, make, lose, move (adapted from the HAVE/GET/GIVE/CONSTRUCT/DESTROY scheme, together with ARIS, Hosseini et al. 2014) and their links to increase/decrease of a possessor's quantity; "give" decreases for the giver and increases for the receiver, and the question decides which side is asked.
math/src/steps.rs: the verb class of each quantity is read from these compiled links and used as a non-lexical feature of the solver's transition model.
The verb lists are wired in at build time as constants rather than learned latent rules; there is no latent-variable SVM.

Effectiveness in Mova

Non-lexical features (verb classes, rates, binding to the question; together with the Unit Dependency Graph paper, Roy & Roth 2017): SVAMP 44.7% → 48.0% (improvement). The contribution of the verb classes alone is not measured separately.

👨‍🔬💥

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00012 · arXiv 1712.09391

@article{roy2018mapping,
  title = {{Mapping to Declarative Knowledge for Word Problem Solving}},
  author = {Roy, Subhro and Roth, Dan},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.1162/tacl\_a\_00012},
  eprint = {1712.09391},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1162/tacl_a_00012}
}

References

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

Yonatan Bisk and Julia Hockenmaier. 2012. Simple robust grammar induction with combinatory categorial grammars. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), pages 1643– 1649, Toronto, Canada, July. find
Ming-Wei Chang, Lev Ratinov, and Dan Roth. 2007. Guiding semi-supervision with constraint-driven learning. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 280–287, Prague, Czech Republic, 6. Association for Computational Linguistics. find
Ming-Wei Chang, Lev Ratinov, and Dan Roth. 2012. Structured learning with constrained conditional models. Machine Learning, 88(3):399–431, 6. find
Danqi Chen and Christopher D. Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 740–750, Doha, Qatar, October. Association for Computational Linguistics. find our card
James Clarke, Dan Goldwasser, Ming-Wei Chang, and Dan Roth. 2010. Driving semantic parsing from the world’s response. In Proc. of the Conference on Computational Natural Language Learning (CoNLL), 7. find
Gerald DeJong. 1993. Investigating explanation-based learning. Kluwer International Series in Engineering and Computer Science. find
Kluwer Academic Publishers. Gerald DeJong. 2014. Explanation-based learning. In T. Gonzalez, J. Diaz-Herrera, and A. Tucker, editors, CRC Computing Handbook: Computer Science and Software Engineering, pages 66.1–66.26. CRC Press, Boca Raton. Kuzman Ganchev, Joao Graça, Jennifer Gillenwater, and Ben… find
Kevin Gimpel and Mohit Bansal. 2014. Weakly-supervised learning with cost-augmented contrastive estimation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1329–1341, Doha, Qatar, October. Association for Computational Linguistics. find
Mark Hopkins, Cristian Petrescu-Prahova, Roie Levin, Ronan Le Bras, Alvaro Herrasti, and Vidur Joshi. 2017. Beyond sentential semantic parsing: Tackling the math SAT with a cascade of tree transducers. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 8… find
Mohammad Javad Hosseini, Hannaneh Hajishirzi, Oren Etzioni, and Nate Kushman. 2014. Learning to solve arithmetic word problems with verb categorization. In Proceedings of the Conference on Empirical Methods for Natural Language Processing (EMNLP). find our card
Danqing Huang, Shuming Shi, Chin-Yew Lin, and Jian Yin. 2017. Learning fine-grained expressions to solve math word problems. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 816–825, Copenhagen, Denmark, September. Association for Computational Linguis… find
Robin Jia and Percy Liang. 2017. Adversarial examples for evaluating reading comprehension systems. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2021–2031. Association for Computational Linguistics, September. find our card
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, and Dan Roth. 2016. Question answering via integer programming over semi-structured knowledge. In Proceedings of the International Joint Conference on Artificial Intelligence (IJ-CAI). find
Rik Koncel-Kedziorski, Hannaneh Hajishirzi, Ashish Sabharwal, Oren Etzioni, and Siena Ang. 2015. Parsing Algebraic Word Problems into Equations. Transactions of the Association of Computational Linguistics. find
Rik Koncel-Kedziorski, Subhro Roy, Aida Amini, Nate Kushman, and Hannaneh Hajishirzi. 2016. MaWPS: A math word problem repository. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics. find
Nate Kushman, Luke Zettlemoyer, Regina Barzilay, and Yoav Artzi. 2014. Learning to automatically solve algebra word problems. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 271–281. find
Percy Liang, Michael Jordan, and Dan Klein. 2011. Learning dependency-based compositional semantics. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL). find
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 the 55th Annual Meeting of the Association for Computational Linguistics. find
Takuya Matsuzaki, Takumi Ito, Hidenao Iwane, Hirokazu Anai, and Noriko H. Arai. 2017. Semantic parsing of pre-university math problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2131–2141, Vancouver, Canada, July. Associ… find
Arindam Mitra and Chitta Baral. 2016. Learning to use formulas to solve simple arithmetic problems. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. find our card
Tahira Naseem, Harr Chen, Regina Barzilay, and Mark Johnson. 2010. Using universal linguistic knowledge to guide grammar induction. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, EMNLP ’10, pages 1234–1244, Stroudsburg, PA, USA. Association for Computation… find
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). find
Dan Roth and Wen-Tau Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Hwee Tou Ng and Ellen Riloff, editors, Proceedings of the Conference on Computational Natural Language Learning (CoNLL), pages 1–8. Association for Computational Linguistics. find
Subhro Roy and Dan Roth. 2015. Solving general arithmetic word problems. In Proc. of the Conference on Empirical Methods in Natural Language Processing (EMNLP). find our card
Subhro Roy and Dan Roth. 2017. Unit dependency graph and its application to arithmetic word problem solving. In Proceedings of the Conference on Artificial Intelligence (AAAI). find our card
Subhro Roy, Shyam Upadhyay, and Dan Roth. 2016. Equation parsing: Mapping sentences to grounded equations. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). find
Shuming Shi, Yuehui Wang, Chin-Yew Lin, Xiaojiang Liu, and Yong Rui. 2015. Automatically solving number word problems by semantic parsing and reasoning. In Empirical Methods in Natural Language Processing. find
Noah Smith and Jason Eisner. 2006. Annealing structural bias in multilingual weighted grammar induction. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), ACL-44, pages 569–576, Stroudsburg, PA, USA. Association for Computational Linguistics. find
Shyam Upadhyay, Ming-Wei Chang, Kai-Wei Chang, and Wen-tau Yih. 2016. Learning from explicit and implicit supervision jointly for algebra word problems. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. find
Lipu Zhou, Shuaixiang Dai, and Liwei Chen. 2015. Learn to solve algebra word problems using quadratic programming. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/roy-2018-mapping-declarative-knowledge-word-problem/