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

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

一、研究背景

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

二、结构泛化性介绍

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

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

Fig.2. Expression recognition rate (ExpRate in %) of string decoders and tree decoders along test sets with different structural complexities (0,1,2, ... ,5). “String-1” and “Tree-1” are trained on complexity {0, 1}, “String-2” and “Tree-2” are trained on complexity {0, 1, 2}.

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

三、Tree Decoder结构介绍

Fig.3. Illustration of tree decoder, including parent decoder part, child decoder part, memory attention part and an optional relation prediction part. “Pred” is short for “prediction”.

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

1.父节点解码器

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

2.子节点解码器

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

3.Memory注意力机制

为了实现递归的树结构解码，本文将树结构拆解成多个子树结构，每个子树结构主要由（子节点，父节点）构成。然而，在实际应用时会发现对于父节点的识别会存在歧义问题。以数学公式“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)”。对于关系识别，本文直接将父节点上下文全局向量和子节点上下文全局向量送入多层感知机以识别。

Fig.4. Illustration of what child attention and parent attention focuses at time step 1 and at time step 6. Red box denotes the region that child attention focuses on, green box denotes the region that parent attention focuses on.

5.Attention自正则化

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

四、主要实验结果

Table 1. Evaluation of math formula recognition systems on CROHME 2014, CROHME 2016 and CROHME 2019 test sets (in %). “ExpRate”, “≤ 1 s.error” and “≤ 1 s.error” means expression recognition rate when 0 to 2 symbol or structural level errors can be tolerated, “StruRate” means structure recognition rate. 

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

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

Fig.5. Comparison of attention visualization on analyzing “subscript” structure. For tree decoder, red color denotes the attention probabilities of child node, green color denotes the attention probabilities of parent node. 

Fig.6. Split the SMILES test set into four sub-sets (“Easy”, “Normal”, “Hard”, “Massive”) based on the length of testing SMILES strings.

本文除了在数学公式识别，还在化学分子式识别上验证了树结构解码器的有效性，并且化学分子式的结构复杂度要远高于数学公式。序列解码器识别化学分子式是采用序列解码器将化学分子式识别为SMILES字符串[3]。本文将SMILES字符串同样处理成子树结构序列，并采用树结构解码器进行结构化建模。我们选取了7000个训练集从未出现过的化学分子式作为测试集，并根据结构复杂度将测试集划成了4个难度，分别是“Easy”，“Normal”，“Hard”和“Massive”，如Fig.6所展示。

Table 2. Recognition rate comparison (in %) between string de- coder and tree decoder on SMILES dataset. “Easy”, “Normal”, “Hard”, “Massive” denote the four sub-sets of test set with different length of SMILES string, “All” means the overall recognition rate on the whole test set (in %). “SD” and “TD” refer to string decoder and tree decoder based approaches, respectively.

表2中的“SD”表示“String Decoder”即序列解码器，“TD”表示“Tree Decoder”即树结构解码器，对比TD和SD的结果能清楚的看到树结构解码器在化学公式识别上明显优于序列解码器，且随着结构复杂度的增加，树结构解码器的提升越显著。

（更详细的内容请参考原文，链接附后）。

五、总结及讨论

1. Tree Decoder是一种可融于编码-解码模型端到端训练的树形结构解码器，解决了当前常见的序列解码器实现树形结构Markup识别任务时结构泛化性不足的问题。

2. Tree Decoder在打印体数学公式、手写体数学公式、打印体化学分子式识别任务下都取得了显著性能提升，说明了该算法的实用性和通用性

3. 论文代码已经开源，可便利后续相关研究，且论文提出的树形结构解码器是一种通用算法，适用于任何树形结构建模任务。

六、相关资源

² TD论文地址：https://proceedings.icml.cc/static/paper_files/icml/2020/3307-Paper.pdf

² TD代码地址：https://github.com/JianshuZhang/TreeDecoder 

参考文献

[1] Zhang, J., Du, J., Yang, Y., Song, Y., Wei, S., and Dai, L. A Tree-Structured Decoder for Image-to-Markup Generation. In ICML, 2020.

[2] Zhang, J., Du, J., and Dai, L. Multi-scale attention with dense encoder for handwritten mathematical expression recognition. In ICPR, 2018.

[3] Dong, L. and Lapata, M. Language to logical form with neural attention. In ACL, 2016.

[4] Jin, W., Barzilay, R., and Jaakkola, T. Junction tree variational autoencoder for molecular graph generation. In ICML, 2018.

原文作者：Jianshu Zhang, Jun Du, Yongxin Yang, Yi-Zhe Song, Si, Wei, Lirong Dai

撰稿：张建树

编排：高 学

审校：连宙辉

发布：金连文

---

免责声明：（1）本文仅代表撰稿者观点，撰稿者不一定是原文作者，其个人理解及总结不一定准确及全面，论文完整思想及论点应以原论文为准。（2）本文观点不代表本公众号立场。 

▼

往期精彩内容回顾

▼

征稿启事：本公众号将不定期介绍文档图像分析与识别及相关领域的论文、数据集、代码等成果，欢迎自荐或推荐相关领域最新论文/代码/数据集等成果给本公众号审阅编排后发布。

(扫描识别如上二维码加关注）