C om S earch: Equation Searching with Combinatorial Strategy for Solving Math Word Problems with Weak Supervision (2023)

Abstract: Previous studies have introduced a weakly-supervised paradigm for solving math word problems requiring only the answer value annotation. While these methods search for correct value equation candidates as pseudo labels, they search among a narrow sub-space of the enormous equation space. To address this problem, we propose a novel search algorithm with combinatorial strategy ComSearch, which can compress the search space by excluding mathematically equivalent equations. The compression allows the searching algorithm to enumerate all possible equations and obtain high-quality data. We investigate the noise in the pseudo labels that hold wrong mathematical logic, which we refer to as the false-matching problem, and propose a ranking model to denoise the pseudo labels. Our approach holds a flexible framework to utilize two existing supervised math word problem solvers to train pseudo labels, and both achieve state-of-the-art performance in the weak supervision task.

## introduction solving math word problems (mwps) is the task of extracting a mathematical solution from problems written in natural language. based on a sequenceto-sequence (seq2seq) framework that takes in the text descriptions of the mwps and predicts the answer equation @xcite , task-specialized encoder and decoder architectures @xcite @xcite @xcite @xcite , data augmentation and normalization @xcite @xcite , and pretrained models @xcite @xcite have been conducted on full supervision setting of the task. these settings require equation ex1 our code and data is available at https://github.com/ yiyunya/comsearch pression annotation, which is expensive and timeconsuming. recently @xcite (lbf) and chatterjee et al. (2021) (warm) addressed this problem and proposed the weak supervision setting, where only the answer value annotation is given for supervision. such a setting forms pseudo questioncandidate equation pairs, which hold the correct answer value for training with the complexity of o(n 2n ) for n variables enormous possible equation space. computational efficiently extracting such pairs becomes the major challenge since it is computationally impossible to traverse all possible equations, especially when the example has more variables (e.g., 88,473,600 for 6 variables). as we show in figure 1 , previous studies sample a limited set of equations via random walk @xcite or beam searching @xcite . however, the algorithms can only cover a limited part of the data, which we refer to as recall. as shown in we observe that although the equation search space is ample, many equations are mathematically equivalent under the commutative law, associative law, or other equivalent forms. hence, searching for these equivalent equations is redundant, especially for difficult examples with a larger number of variables. for example, a + b + c + d * e has 48 equivalent forms that hold the same mathematical meaning considering only the commutative law. eliminating such redundancy in the searching space could reduce computational complexity. in this paper, we propose a combinatorial-strategybased searching method comsearch that enumerates non-equivalent equations without repeating, which can robustly extract candidate equations for a wide range of unlabeled data and build a high recall pseudo data with equation annotation even for difficult examples. to this end, the main idea of comsearch is to use depth-first search (dfs) to enumerate only one representative equation for each set of equivalent equations and then check whether the equation holds the correct answer value. comsearch effectively compresses the searching space, e.g., up to 111 times for 6 variables compared to bruce-force searching. as shown in while comsearch only searches among nonequivalent equations, we observe that many examples still have multiple candidate equations through which we can get the final answer. as shown in figure 1 , equation 1 (eq1: @xmath1: @xmath2, but equation 3 holds a false mathematical reasoning logic, and using equation 3 as the pseudo label would bring in noise. we address this data noise as the false-matching problem, which has been ignored in previous studies, since their methods do not consider whether the multiple candidate equations of one example are caused by equivalent equation forms or false matching. to address this problem, we investigate how the false-matching problem drags down the system's performance and propose two ranking models to alleviate this problem. for examples with multiple candidate equations from comsearch, the ranking module first collects a set of candidate equations, then assign a score by a draft model trained on pseudo data with only a single candidate equation to each candidate to choose the best pseudo label. in addition to candidates from the searching result of com-search, we observe that beam search results of the draft model can also serve as a high-precision candidate equation. we investigate these two settings for candidate equation sets. we conduct experiments on two strong mwp solvers, achieving state-of-the-art (sota) results under the weakly supervised setting, especially for examples with many variables. the results also demonstrate the effectiveness and generalization ability of our method. in summary, our contribution is three-fold: ## methodology we show the pipeline of our method in figure 2 . our method consists of three modules: the search with combinatorial strategy (comsearch) module that searches for candidate equations; the mwp model that is trained to predict equations given the natural language text and pseudo labels; the ranking module that uses an explorer model to find candidate equations and select the best candidate equation with a scoring model. ## related work early approaches to solving math word problems mainly depend on hand-craft rules and templates @xcite . later studies either rely on semantic parsing @xcite @xcite , or try to obtain an equation template @xcite @xcite . recent studies focus on using deep learning models to predict the equation template for full supervision setting. for weakly supervised setting, hong et al. (2021) and @xcite suffers from two major drawbacks. first, they apply equation candidate searching on an enormous searching space, while our method can effectively extract high-quality candidate equations. @xcite results in low robustness and low performance on examples with more variables. @xcite results in low coverage of examples that can extract candidate equations. second, they use all candidate equa-tions for training and neglect the false-matching problem, which is the key issue that drags down the model performance in weakly supervised setting, while our ranking module addresses this issue and further boosts the performance. to eliminate equivalent expressions, @xcite proposed a model that decomposes the equation prediction problem into various classification problems, eliminating some equivalence forms of the equation. however, the compression is highly integrated with their model and cannot generalize to other models, including the sota seq2seq based models. moreover, it can only cover limited equivalence forms, leaving out various important forms such as commutative law and associative law. @xcite proposed a normalization method for supervised mwp systems that considers commutative law. the method merges several equivalent expressions into one expression, resulting in the compression of the target equation space. however, their method requires bruce-force enumeration before compression, which remains to have high computational complexity. only limited equivalent forms are considered in both studies, and the equation space is still considerably ample. various studies @xcite in arqmath competition @xcite and ntcir benchmark @xcite have investigated the math retrieval task that retrieves the most related mathematical passage for a question, which have clear semantic meanings given by the textual description. in our ranker setting, the scoring targets, i.e., plane mathematical equations, cannot provide the semantic meanings that contextual embedding similarity based methods used in math retrieval benchmarks require. with fully supervised training data, retrieval-based methods only achieve 40% accuracy @xcite on math23k. spurious programs in weakly supervised semantic parsing is a close analogy of the false-matching problem, which refers to incorrect programs that lead to correct denotations. the major difference is that the function names of the spurious programs are natural language defined, so the programs have semantic meanings. extra knowledge bases @xcite and lexicon clues @xcite were used to denoise the spurious programs, which is not applicable for complex lexicon patterns mwps that the solution equation uses operators '+, -, * , /' that have no semantic mean-ing. @xcite uses a small humanannotated dataset for denoising. @xcite , which proposes a re-weighted optimization loss for the examples. however, their method relies heavily on hyperparameter tuning and gains negative results on many datasets. thus these methods are not suitable for the setting in our paper. ## conclusion this paper proposes comsearch, a searching method based on a combinatorial strategy, to extract candidate equations for solving math word problems under weak supervision. comsearch compresses the enormous search space of equations beyond the exponential level, allowing the algorithm to enumerate all possible non-equivalent equations to search for candidate equations. we investigate the false-matching problem, which is the critical issue that drags down performance, and propose a ranking model to reduce noise. our experiments show that our method obtains high-quality pseudo data for training and achieves state-of-theart performance under weak supervision settings, outperforming strong baselines, especially for examples with more variables.