The Complexity of Math Problems – Linguistic, or Computational?

International Joint Conference on Natural Language Processing, pages 73–81, Nagoya, Japan, 14-18 October 2013. The Complexity of Math Problems – Linguistic, or Computational? Takuya Matsuzaki1, Hidenao Iwane2, Hirokazu Anai2,3 and Noriko Arai1 1 National Institute of Informatics, Japan 2 Fujitsu Laboratories Ltd., Japan 3 Kyushu University, Japan {takuya-matsuzaki,arai}@nii.ac.jp; {iwane,anai}@jp.fujitsu.com Abstract We present a simple, logic-based archi- tecture for solving math problems writ- ten in natural language. A problem is firstly translated to a logical form. It is then rewritten into the input language of a solver algorithm and finally the solver finds an answer. Such a clean decomposi- tion of the task however does not come for free. First, despite its formality, math text still exploits the flexibility of natural lan- guage to convey its complex logical con- tent succinctly. We propose a mechanism to fill the gap between the simple form and the complex meaning while adhering to the principle of compositionality. Second, since the input to the solver is derived by strictly following the text, it may require far more computation than those derived by a human, and may go beyond the capa- bility of the current solvers. Empirical study on Japanese university en- trance examination problems showed pos- itive results indicating the viability of the approach, which opens up a way towards a true end-to-end problem solving system through the synthesis of the advances in linguistics, NLP, and computer math. 1 Introduction Development of an NLP system usually starts by decomposing the task into several sub-tasks. Such a modular design is mandatory not only for the reusability of the component technologies and the extensibility of the system, but also for the sound and steady advancement of the research field. Each module, however, has to attack its sub-task in isolation from the entirety of the task, usually with a quite limited form and amount of knowledge. The separated sub-task is hence not necessarily easy even for human. This problem has been investigated in various directions, includ- ing the solutions to the error-cascading in pipeline models (Finkel et al., 2006; Roth and Yih, 2007, e.g.), the injection of knowledge into the process- ing modules (Koo et al., 2008; Pitler, 2012, e.g.), and the invention of a novel way of modularization (Bangalore and Joshi, 2010, e.g.). In this paper, we present a simple pipeline archi- tecture for natural language math problem solving, and investigate the issues regarding the separation of the semantic composition mechanism and the mathematical inference. Although the separation between these two may appear to be of different nature than the above-mentioned issues regarding the system modularization, as we will see later, the technical challenges there are also in the tension between the generality of an implemented theory as a reusable component, and its coverage over domain-specific phenomena. In the system, a problem is analyzed with a Combinatory Categorial Grammar (Steedman, 2001) coupled with a semantic representation based on the Discourse Representation Theory (Kamp and Reyle, 1993) to derive a logical form. The logical form is then rewritten …

Content truncated to 500 words