论文推荐丨[ICML2020]用于图像到标记符号生成的树状结构解码器

本文简要介绍 2 020 年 6 月被 ICML 录用论文 “ A Tree-Structured Decoder for Image-to-Markup Generation” 的主要工作 [1] 。该论文提出新型的树形结构解码器，针对数学公式、化学分子式等树形结构的 Markup 识别优化编码 - 解码模型，能够有效解决编码 - 解码模型进行树形结构 Markup 识别时的结构泛化性不足的问题。该论文中介绍的方法获得了离线手写数学公式识别竞 赛 OffRaSHME 2020 的冠军 ，验证了该树形结构解码器较序列解码器的优势。

基于注意力机制的编码 - 解码模型近 3 年来被广泛应用于数学公式、编程语言等树形结构的 Markup 语言的识别 [2][3] ，这类算法普遍选用 LaTeX 或其他一维等价字符串来表示树形结构 Marku p ，然后采用序列解码器将这些一维等价字符串解码出来，以完成识别。此类算法较传统基于语法树的识别算法显著提升了识别性能，目前已成为了数学公式等树结构语言识别的主流算法。然而，本论文通过分析和实验证明这类基于序列解码器的编码 - 解码模型存在一个很严重的问题 — 缺乏结构泛化性，即当测试样本的树结构复杂度过高时，模型无法正确识别，也因此推测，基于序列解码器的编码 - 解码模型纯粹是基于从训练数据中学到的语言模型和全局图像特征来实现树结构语言识别，缺乏对结构的理解。本文创造性提出一个新型并可融于编码 - 解码模型端到端训练的树形结构解码器，通过与序列解码器对比，不仅在自定义的 Toy Problem 上充分验证了树解码器的结构泛化性优势，也在公开手写数学公式识别集合与化学分子式识别集合验证了树解码器的有效性。

Fig.1. Illustration of math formulas with increased structural complexity.

本文首先针对性设计了 Toy Problem 来验证结构泛化性问题，通过该实验结果发现序列解码器在面对训练集中从未结果的复杂结构数学公式时会完全崩溃。这个发现极大的激励了我们去研究树形结构解码器，以解决此不可接受的问题。本文将结构复杂度定义为树结构下遍历树结构的所有路径中含有不止一个子节点的非终端节点的数目的最大值。本文选取打印体数学公式来设计该 Toy Problem ，这样能（ i ）保证识别任务的难度集中在结构复杂度上，而不是字符识别上；（ ii ）便于我们设计不同结构复杂度的样本。 Fig.1 通过实例展示了输入数学公式图片与其结构复杂度的对应。像 “ x+1=y ” 这种一维公式，它的结构复杂度就是 0 。而随着“上标”、“分式”、“求和”等结构的出现，公式的结构复杂度逐渐增加。

本文的 Toy Problem 中设定了 6 个测试集，这六个测试集的结构复杂度从 0 增长到 5 。关于训练集样本的结构复杂度，本文做了针对性的限制。首先 Fig. 2 左图中所示的结果，训练集公式的复杂度仅为 0 和 1 ，可以看到序列解码器和树解码器在复杂度为 0 和 1 的测试集上表现都很好，然而当测试集复杂度在训练集里从未出现过时，比如 2 、 3 、 4 ，序列解码器的识别率直接降为 0 ，而树解码器能取得可接受的识别率；同样的， Fig.2 右图中所示的结果，训练集公式的复杂度仅为 0 、 1 、 2 ，我们发现序列解码器在未见过的复杂测试集上识别率仍为 0 ，而树解码器能获得很不错的识别率。由此可见序列解码器在未见过的复杂结构样本上完全没有泛化性，但是树解码器能处理的很好。

树形结构解码器主要由 4 部分构成，分别是父节点解码器、子节点解码器、 Memory 注意力机制和关系分类器，如 Fig.3 所示。

父节点解码器以前一时刻的子节点和子节点隐层状态为输入，用于生成当前时刻父节点状态预测值，并用其计算父节点注意力概率以得到父节点上下文全局向量，再和父节点状态预测值一起更新得到父节点隐层状态。

2.子节点解码器

子节点解码器以当前时刻父节点和父节点隐层状态为输入，类比父节点解码器的过程，得到子节点上下文全局向量和子节点隐层状态。注意到，在训练时，由于已获得父节点的真实值，因此模型输入是真实的父节点，而测试时无法得到父节点的真实值，因此取 Top-K 个父节点作为输入，并以此扩展 Beam Search 的路径数目。

为了实现递归的树结构解码，本文将树结构拆解成多个子树结构，每个子树结构主要由（子节点，父节点）构成。然而，在实际应用时会发现对于父节点的识别会存在歧义问题。以数学公式 “ x + x ^{2} ”为例，这个公式的子树结构序列为“ ( x , root), (+, x ), ( x , +), (2, x ) ”。在这个例子下可以看到，相同字符表示的子节点（如“ x ”），我们可以通过不同的解码顺序来确定，但是相同字符表示的父节点我们却无法区分，比如第 4 个子树结构中，我们无法正确区分“ 2 ”对应的父节点应该是第一个“ x ”还是第二个“ x ”。因此，本文使用了一个 Memory 模块，每次将识别出来的子节点存入 Memory 当中，再采用字符在 Memory 中的索引位置来表示父节点，因为父节点必然是已经解码出来的子节点，所以可以通过这种方式来转换表达方式。使用 Memory 后， “ ( x , root), (+, x ), ( x , +), (2, x ) ”则变成了“ ( x , 0), (+, 1 ), ( x , 2), (2, 3 ) ”，这样我们便能知道“ 2 ”的父节点是 Memory 中的第 3 个元素，也就是公式中的第 2 个“ x ”。

4.关系分类器

对于像数学公式识别这种父节点和子节点之间存在关系的任务，需要一个额外的关系分类器来识别父节点和子节点之间的关系。以数学公式 “ x+x^{2} ”为例，其完整的子树结构序列为“ (x, root, start), (+, x, right), (x, +, right), (2, x, sup) ”。对于关系识别，本文直接将父节点上下文全局向量和子节点上下文全局向量送入多层感知机以识别。

5. Attention 自正则化

除了上述介绍的四个部分，本文介绍的树解码器还有一个关键的正则化项，称为 Attention 自正则化。该正则化项的出发点是父节点注意力概率和子节点注意力概率之间存在很密切的关联。 Fig.4 所示的数学公式中，在第 1 个解码时刻，子节点为“ \sum ”，而在第 6 个解码时刻，子节点为“ \frac ”而父节点为“ \sum ”。可以发现，第 6 时刻的父节点和第 1 时刻的子节点是完全一样的（均为“ \sum ”），很自然的想法就是第 6 时刻的父节点注意力模型应该和第 1 时刻的子节点注意力模型。基于这种思想，本文使用 KL 距离来约束子节点和父节点之间的注意力概率，以达到自正则化的作用。

Table 1 将本文介绍的树结构解码器与其他方法在国际最大手写数学公式识别竞赛 CROHME 数据集上进行了公平对比（本文仅考虑离线场景）。其中 “ DenseWAP ”是目前公开单模型最好的序列解码器，采用官方基线系统复现了识别结果，表中所列结果为采用不同的初始化跑了 5 次的统计结果；“ DenseWAP-TD ”则是在“ DenseWAP ”的基础上将序列解码器改为树结构解码器，并保持编码器和更新策略完全一致，所以通过对比“ DenseWAP ”和“ DenseWAP-TD ”的结果可以清楚地看到树结构解码器带来的直接性能提升（在 3 个测试集上平均绝对提升 8% 的公式识别率）。

Fig.5 通过注意力概率可视化进一步解释了序列解码器和树解码器在解码时对结构理解的差别。 LaTeX 序列里会使用左右花括号 “ {} ”这类虚体字符来表示一个数学结构的开始和结束。 Fig.5 描述了当序列解码器遇到 “下标”的数学结构并尝试解码出左右花括号对时，注意力概率分布是随机混乱的，不具备任何可解释行。因此，本文合理推测序列解码器实现数学公式等结构化 Markup 的识别纯粹依赖隐式的语言模型来记忆训练集中的统计分布，对结构本身没有任何理解。对比看树结构解码器的注意力概率可视化，可以发现当识别下标 “ i ”的时候树解码器能准确的找到“ i ”（红色概率）的父节点是“ y ”（绿色概率），显现出很好的对结构的理解。