论文笔记 | Tree-structured Decoding for Solving Math Word Problems
这篇文章是由京都大学和北京大学合作发表在EMNLP 2019上的。主要是在seq2seq架构上做了改进,用树结构的decoder来生成抽象语法树(也可简单理解为表达式树)。并且利用栈结构辅助,能够清楚的知道下一次要生成的token是什么,还有什么时候可以停止解码。
文章目录
研究动机
目前已有很多用seq2seq结构来做解题的工作,但这些工作都没有充分利用抽象语法树。也就是,这篇文章在生成一个token的时候,会考虑其父token的表示,左边同级token的表示,以及在前缀表达式中的前一个token的表示。
并且,在生成token的过程中,也进行相应的入栈出栈操作,将中间操作过程也保存在栈中,最终出栈操作可以得到一个前缀表达式。
Decoding生成token的判断过程如下:
- 如果decoder预测出来的token是一个操作符,那么就将操作符入栈,接下来预测该操作符左孩子节点。
- 如果decoder预测出来的token是一个操作数,那就根据栈内的情况做不同的操作。如果栈顶是一个操作符,那就将该操作数入栈,然后去预测该操作数的同级右节点。如果栈顶是一个操作数,那就将取出栈顶的两个元素,分别是<op>和<num>,这可以和当前预测出来的token组成一个子树。然后直接将该子树(前缀表达式形式:<op><num><num>)入栈。
- 接着重复以上操作,直至栈内的表达式出栈。
预测生成的token的公式
其中中包含的三个元素分别是当前要预测的token的父节点的hidden表示,同级节点的embedding,前缀表达式中该token前一个token的embedding。然后利用LSTM去生成该时刻的hidden表示,再利用MLP对该hiddden表示操作,最终选择一个能使MLP输出值最大的token作为。
系统架构图
- Encoder部分就是一个Bi-LSTM,用于获取每个token的上下文信息。输出是整个问题文本的向量表示,也将作为decoder的输入。
- Decoder是抽象语法树的形式,具体的操作过程下面给出。
上图给出了一个例子,展示了decoder中生成token的过程。
- 首先,第一次生成的token是一个"-“号,接下来将”-"号入栈,然后去预测它的左孩子节点。
- 这里左孩子节点预测出来是一个"+“号,那么还是要预测它的左孩子节点,并且将”+"入栈。
- 接下来预测"+“的左孩子节点,这里预测出来是,此时栈顶元素是”+",所以将入栈,然后去预测的同级右节点。
- 这里预测出来的同级右节点是,此时栈顶元素是,所以将栈顶的两个token出栈,和操作,得到,将其入栈。
- 这时root节点"-"的左孩子已经完全生成好了,需要去预测右孩子节点,这里预测出来是,栈顶元素是,所以将栈顶的两个token出栈,和操作,得到KaTeX parse error: Double subscript at position 9: -+n_1n_2_̲n3,将其入栈。
- 此时,表达式树已经满了,所以进行出栈操作,得到的就是我们要求的前缀表达式的形式。
Strong Points
- 在Math23k数据集上达到了69.0%的准确率,比目前很多的方法要好。
- 对实验结果进行了误差分析,包括表达式长短、题目类型(关于题目类型,利用关键词将题目进行分类,附录也给出了相关关键词)对结果的影响分析。
- 在生成一个token的时候,抽象语法树提供了该token父节点、同级左节点的表示,对生成该token有帮助。
Weak Points
- 不能很好的处理表达式比较长的题目
- 虽然对题目的类型有了划分,但是是基于最简单的关键词匹配。题目类型的划分还可以进一步改进。
- 立体几何类型题目不能很好的解决,因为该类题目大多需要外部知识,比如求面积公式等等。
- 该工作没有开源的代码。
补充
这篇文章跟之前看过的一篇《Semantically-Aligned Equation Generation for Solving and Reasoning MathWord Problems》,有一些相似的地方,它里面也是在decoder部分用到了栈,只是需要两个选择器,一个用来选择栈操作,另一个用来选择操作数。