Structure-Unified M-Tree Coding Solver for MathWord Problem

• URL: http://arxiv.org/abs/2210.12432v2
• Date: Tue, 25 Oct 2022 04:57:08 GMT
• Title: Structure-Unified M-Tree Coding Solver for MathWord Problem
• Authors: Bin Wang, Jiangzhou Ju, Yang Fan, Xinyu Dai, Shujian Huang, Jiajun Chen
• Abstract summary: In previous work, models designed by taking into account the properties of the binary tree structure of mathematical expressions at the output side have achieved better performance. In this paper, we propose the Structure-Unified M-Tree Coding Coding (S-UMCr), which applies a tree with any M branches (M-tree) to unify the output structures. Experimental results on the widely used MAWPS and Math23K datasets have demonstrated that SUMC-r not only outperforms several state-of-the-art models but also performs much better under low-resource conditions.
• Score: 57.825176412485504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As one of the challenging NLP tasks, designing math word problem (MWP) solvers has attracted increasing research attention for the past few years. In previous work, models designed by taking into account the properties of the binary tree structure of mathematical expressions at the output side have achieved better performance. However, the expressions corresponding to a MWP are often diverse (e.g., $n_1+n_2 \times n_3-n_4$, $n_3\times n_2-n_4+n_1$, etc.), and so are the corresponding binary trees, which creates difficulties in model learning due to the non-deterministic output space. In this paper, we propose the Structure-Unified M-Tree Coding Solver (SUMC-Solver), which applies a tree with any M branches (M-tree) to unify the output structures. To learn the M-tree, we use a mapping to convert the M-tree into the M-tree codes, where codes store the information of the paths from tree root to leaf nodes and the information of leaf nodes themselves, and then devise a Sequence-to-Code (seq2code) model to generate the codes. Experimental results on the widely used MAWPS and Math23K datasets have demonstrated that SUMC-Solver not only outperforms several state-of-the-art models under similar experimental settings but also performs much better under low-resource conditions.

Related papers

• Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs [72.89652710634051]
  Knowledge graphs (KGs) complement Large Language Models (LLMs) by providing reliable, structured, domain-specific, and up-to-date external knowledge. We introduce Tree-of-Traversals, a novel zero-shot reasoning algorithm that enables augmentation of black-box LLMs with one or more KGs.
  arXiv  Detail & Related papers  (2024-07-31T06:01:24Z)
• Tree Prompting: Efficient Task Adaptation without Fine-Tuning [112.71020326388029]
  Tree Prompting builds a decision tree of prompts, linking multiple LM calls together to solve a task. Experiments on classification datasets show that Tree Prompting improves accuracy over competing methods and is competitive with fine-tuning.
  arXiv  Detail & Related papers  (2023-10-21T15:18:22Z)
• Non-Autoregressive Math Word Problem Solver with Unified Tree Structure [62.869481432887106]
  We propose a novel non-autoregressive solver, named textitMWP-NAS, to parse the problem and deduce the solution expression based on the unified tree. The results from extensive experiments conducted on Math23K and MAWPS demonstrate the effectiveness of our proposed MWP-NAS.
  arXiv  Detail & Related papers  (2023-05-08T08:53:37Z)
• Spatial Attention and Syntax Rule Enhanced Tree Decoder for Offine Handwritten Mathematical Expression Recognition [12.656673677551778]
  We propose a novel model called Spatial Attention and Syntax Rule Enhanced Tree Decoder (SS-TD) Our model can effectively describe tree structure and increase the accuracy of output expression. Experiments show that SS-TD achieves better recognition performance than prior models on CROHME 14/16/19 datasets.
  arXiv  Detail & Related papers  (2023-03-13T12:59:53Z)
• UNSAT Solver Synthesis via Monte Carlo Forest Search [10.754275929551593]
  We introduce Monte Carlo Forest Search (MCFS), a class of reinforcement learning (RL) algorithms for learning policies in tree MDPs Examples of such problems include proving unsatisfiability of a SAT formula; counting the number of solutions of a satisfiable SAT formula. We dub Knuth Synthesis, an MCFS algorithm that learns DPLL branching policies for solving the satisfiability (SAT) problem.
  arXiv  Detail & Related papers  (2022-11-22T20:52:50Z)
• METGEN: A Module-Based Entailment Tree Generation Framework for Answer Explanation [59.33241627273023]
  We propose METGEN, a Module-based Entailment Tree GEN framework that has multiple modules and a reasoning controller. Given a question, METGEN can iteratively generate the entailment tree by conducting single-step entailment with separate modules and selecting the reasoning flow with the controller. Experiment results show that METGEN can outperform previous state-of-the-art models with only 9% of the parameters.
  arXiv  Detail & Related papers  (2022-05-05T12:06:02Z)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  Spectral Top-Down Recovery (STDR) is a divide-and-conquer approach for inference of large latent tree models. STDR's partitioning step is non-random. Instead, it is based on the Fiedler vector of a suitable Laplacian matrix related to the observed nodes. We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability.
  arXiv  Detail & Related papers  (2021-02-26T02:47:42Z)
• Recursive Top-Down Production for Sentence Generation with Latent Trees [77.56794870399288]
  We model the production property of context-free grammars for natural and synthetic languages. We present a dynamic programming algorithm that marginalises over latent binary tree structures with $N$ leaves. We also present experimental results on German-English translation on the Multi30k dataset.
  arXiv  Detail & Related papers  (2020-10-09T17:47:16Z)
• Tree Echo State Autoencoders with Grammars [3.7280152311394827]
  Non-vectorial and discrete nature of trees makes it challenging to construct functions with tree-formed output. Existing autoencoding approaches fail to take the specific grammatical structure of tree domains into account. We propose tree echo state autoencoders (TES-AE), which are guided by a tree grammar and can be trained within seconds by virtue of reservoir computing.
  arXiv  Detail & Related papers  (2020-04-19T18:04:33Z)
• Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and Math Word Problem [33.610361579567794]
  We present a novel Graph-to-Tree Neural Networks, namely Graph2Tree consisting of a graph encoder and a hierarchical tree decoder, that encodes an augmented graph-structured input and decodes a tree-structured output. Our experiments demonstrate that our Graph2Tree model outperforms or matches the performance of other state-of-the-art models on these tasks.
  arXiv  Detail & Related papers  (2020-04-07T17:36:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.