SAN论文阅读

在OCR识别中引入树形编码器，从而加入更多语义信息

摘要

本文将语义信息融入ORC任务，具体来说本文提出了一套语法规则，用于将每个表达式的LaTeX标签转化为解析树，接着本文使用神经网络将标记序列预测任务建模为一个树遍历过程。因此本文提出的方法可以有效地描述表达式的语法上下文，缓解HMER的结构预测误差。在两个基准数据集上的实验表明，我们的方法取得了比现有方法更好的识别性能。为了进一步验证我们方法的有效性，我们创建了一个由来自一万个作者的100k张手写数学表达式图像组成的大规模数据集。

引言

随着深度学习方法的发展，在图像到序列的方法中，现有方案更商场与处理文本行。但是这些方法也许在对复杂结构的处理上效果不佳，例如处理数学表达式。本文调查了离线手写数学表达式识别（HMER）。HMER任务的难点在于二维结构关系对于数学公式的理解是非常重要的，但这一点再以往的基于深度学习的方法中很少被考虑到。此外，手写输入带来的歧义进一步增加了HMER的难度。

早期的工作已经很好地研究了ME的语法结构，并为HMER定义了合适的语法。这些语法仅用于将识别出的符号分组为结构化输出，严重依赖于符号识别的性能。此外，由于这些方法主要是基于手工特征设计的，其性能远远达不到实际应用的要求。

最近的编解码器或多或少都忽略了数学公式的语法信息。本文使用了WAP模型以及DWAP-TD模型来说明这一点。DWAP-TD模型尝试通过将目标句法结构树分解为一系列子树来考虑语法信息，其中每个子树由父节点和子节点组成。尽管DWAP - TD可以产生树结构的输出，但它仍然遵循"从一个字符到另一个字符"的范式，即下一个符号预测主要基于当前符号。本文认为，这类方法在学习过程中没有明确地考虑ME的语法关系，缺乏生成合理的树预测的语法约束。

为了解决结构误差并提升复杂语法树的理解，本文提出了一个语法精炼模块，可以自然地将语法树划分为不同的组件，有效地减少树结构歧义。

然后，本文建立了一个名为句法语义感知网络( SAN )的编码器-解码器网络，该网络将语法约束和特征学习融合在一个统一的框架中。

如图上图 ( c )所示，SAN的预测过程遵循语法树的遍历过程，语法树的子树是数学表达式的重要组成部分。通过这种方式，可以在提出的SAN模型中对相邻组件的句法关系进行编码。因此，SAN的预测是在解析过程中从一个组件到另一个组件进行的。

除了使用CROHME数据集外，为了进一步确认SAN的有效性，我们收集并注释了一个用于评估的大规模数据集，命名为HME100K。该数据集的数据量是CHROME的十倍。

本文的主要贡献在于提出的句法语义感知网络，首次有效地将句法信息嵌入到深度神经网络中。本文的另一个贡献是提出了大型多样的数据集HME100K。与先前的数据集相比，HME数据集拥有更多的长度，具有更多复杂结构，对于提升算法在真实数据上的鲁棒性更为有效。

结论

本文提出了一种非传统的手写数学表达式识别方法，通过结合语法信息和视觉表示来进行稳健的预测。据我们所知，提出的句法语义感知网络是第一个有效地将语法规则纳入深度特征学习的网络。本文的方法不仅可以预测LaTeX标记结果，而且可以直接生成树结构输出，可以精确地描述数学表达式的组成关系。在基准数据集和提出的HME100K数据集上的实验验证了本文方法的有效性和效率。

方法

SAN

SAN定义如下：

$G = (N, \Sigma, R, S,\Gamma,C,D )$

一个包含7个元素的tuple。

$N$ ：非终结符有限集

$\Sigma$ ：终结符有限集

$R$ ：产生规则有限集

$S$ ：开始符

$\Gamma$ ：关系有限集

$C$ ：encoder

$D$ ：decoder

本文设计了语法规则，该规则包含两项约束：

遵循标准的阅读顺序：从左到右，从上到下
利用了相邻符号之间的空间关系

对于HME中一对相邻的符号，共有9中可能的关系：左、右、上、下、左下、右下、左上、右上、内部。但由于约束1的存在，本文删除了其中的“左”和“左下”。尽管一个ME可能对应不同的LaTex序列，但由于这两项约束的存在，本文的语法规则生成的语法树是相同的

SAN将图像转化为解析树，其中叶子节点为终结符号或关系，其他为非终结符号。目前有两种非终结符S和E，S为开始符，并且将座位树的根节点。终结符 $\Sigma$ 包含所有可能在LaTeX表达式种使用的符号。

R产生规则能被用在构建解析树上。产生规则的形式为： $\alpha \to \beta \ where \ \alpha \in N, \beta \in (\Gamma \cup N \cup \Sigma)*$ 其中*表示Kleene star操作。因此父节点 $\alpha$ 能被分解为一个子节点 $\beta$ 的结合，包含非终结符、终结符和关系。

R包含两个产生规则：

一个S能够产生： $S \to \sigma S|E|\epsilon$ $S \to σ S ∣ E ∣ ϵ$
1. 任意一个终结符号其右边跟着一个S
2. 一个E
3. 一个空字符串表示为 $\epsilon$
4. $\sigma \in \Sigma$ 表示任意一个终结符
5. |分离备选方案
一个E能产生： $E \to [((\gamma _1)S|\epsilon),...,((\gamma_7)S|\epsilon)]$ $E \to [((γ_{1}) S ∣ ϵ), . . ., ((γ_{7}) S ∣ ϵ)]$
1. 为每种类型的关系建立一个字符串，然后将它们连接起来
2. 字符串可以是S后面的关系，也可以是空串
3. $\gamma _i \in \Gamma$ 代表第i个关系
4. $[.]$ 是连接运算符

如下图a所示是一个公式 $\sum ^n _i a$ 的产生过程：

产生式规则与输入图像和父节点的上下文状态条件概率相关联，条件概率表示如下：

$p(\alpha \to \beta|c(\alpha), X) = D_{\alpha \to \beta}(c(\alpha), E(x))$

X代表输入图像，E(X)是encoder的输出， $c(\alpha)$ 是 $\alpha$ 的上下文信息， $D_{\alpha \to \beta}(.)$ 是decoder的输出与生产规律相对应。

一个SAN的处理过程如下图所示：

其中树的遍历用一个栈来实现，用以保证训练过程是按照遍历顺序执行的。同样的预测过程也是通过栈来实现。一但找到解析树，识别的结果可以通过先序遍历解析树得到。

Encoder

DenseNet

Syntax-Aware Decoder

主要包含两个GRU单元，和一个Syntax-Aware Attention模块。Decoder的输入输出如下：

input：一个非终结符 $\alpha$ 的上下文状态，encoder向量 $E(X)$
output：以 $\alpha$ 开始的每个产生式的概率

本文使用历史状态和伙伴状态来描述当前解析非终端符号的上下文状态。历史状态 $c^\alpha _h$ 用来追踪非终端节点 $\alpha$ 是如何产生的。此外，将最新生成的终端符号或关系的word embedding作为非终端符号的伙伴状态 $c^\alpha _p$ 来捕获短期上下文信息。

decoder模型结构如下：

$GRU-\alpha$ 输入： $c_p ^\alpha$ 座位输入向量， $c_h ^\alpha$ 做为隐藏向量，输出一个新的隐藏向量 $c_o ^ \alpha$

$c_o^\alpha = GRU(c_p^\alpha,c_h^\alpha)$

随后一个注意力模块计算一个紧凑的视觉特征，使用 $att_\alpha(X)$ SAA的输出向量、encoder输出的特征、隐藏向量作为输入计算注意力：

$\Omega = Att(E(X), c_o^\alpha, att_\alpha(X))$

第二个GRU使用 $\Omega$ 作为输入向量， $c_o ^\alpha$ 作为隐藏向量，输出新的隐藏向量 $c_\beta ^\alpha$ ：

$c_\beta ^\alpha = GRU(\Omega, c_o ^\alpha)$

随后本模型整合 $c_p ^\alpha, c_\beta ^ \alpha , \Omega$ 来预测两个概率分支：

$p_{symbol}(\alpha \to \beta | c(\alpha), X) = softmax(W_s(W_pc_p^\alpha + W_gc_\beta ^\alpha + W_t \Omega)) \\ p_{relation}(\alpha \to \beta | c(\alpha), X) = softmax(W_r(W_pc_p^\alpha + W_gc_\beta ^\alpha + W_t \Omega))$

其中W代表权重。 $p_{symbol}(\alpha \to \beta | c(\alpha), X)$ 是一个包含 $|\Sigma| + 2$ 个维度的概率向量来表示三种情况：

$|\Sigma|$ 个维度用来表示预测的符号
一个维度用来表示预测E
最后一个维度用来预测空字符串

对于第一种场景，如果对终端符号 $( \sigma )$ 的预测概率最高，那么应用 $S\to \sigma S$ 的规则更新解析树，使用 $\sigma$ 的词嵌入作为新生成S的伙伴状态, $c_\beta ^\alpha$ 作为其历史状态。

对于第二种场景，如果预测到E的概率最高，则应用 $P_{relation}( \alpha \to \beta | c ( \alpha)，X )$ 预测每个关系出现的概率。概率高于0.5的关系是持续的，其他的被抛弃。对于每一个剩余关系，我们使用关系的嵌入作为后面S的伙伴状态，使用 $c_\beta ^\alpha$ 作为历史状态。此外，不需要考虑解析一个E，因为它已经从关系分支中获取。对于第三种情况，如果空字符串出现的概率最高，则按照 $S \to \epsilon$ 的规则更新解析树。

SAA Module

该模块通过注意力机制计算出紧凑的视觉特征。首先计算出图像每个局部区域的归一化权重，然后使用加权平均对局部特征进行聚合。本文使用 $E(X)$ ，隐藏状态 $c_o ^ \alpha$ 和一个syntax-aware attention向量 $att_\alpha (X)$ 来计算归一化权重向量：

$\xi _\alpha = softmax(W_w(tanh(W_o c_o ^ \alpha + W_\alpha att_\alpha (X) + W_e E(x))))$

其中W是科学系参数， $\xi _ \alpha$ 是一个长度为L的向量。随后通过矩阵乘法计算得到的紧凑的视觉特征

$Att(E(X),c_o ^ \alpha , att_\alpha(X)) = E(x) \xi _ \alpha$

不同于以往的使用基于所有过去注意力概率之和的覆盖向量，SAN不跟踪所有过去的注意力概率。

注意力漂移问题的发生是因为分子的注意力概率没有给出解析分母的信息，而是表现为噪声。本文将从解析树的根到当前解析节点的路径上过去的注意力概率加总，而不是所有过去的注意力概率。因此本文通过如下方式计算注意力向量：

$att_\alpha (X) = \sum _i \xi_i, i \in path_\alpha$

通过将句法语义感知注意力向量作为中间信息存储在堆栈中，可以有效地对其进行追踪。

采用注意力自正则化策略对注意力进行修正。本文使用一个额外的反向解码器来预测每个给定子节点的父节点。反向解码器与原始解码器结构相同，但对数据进行反向操作。因此有两个标准化的权重向量来预测每个非终端节点 $\beta$ ，正向 $\xi_\alpha$ 和反向 $\xi _\beta$ ，其中 $\alpha$ 是 $\beta$ 的父节点， $\beta$ 是 $\eta$ 的父节点。本文使用KullbackLeibler ( KL )散度来对其进行正则化正则：

$L_{reg} = -\sum_\beta \hat{\xi _\beta}log\frac{\hat{\xi_\eta}}{\xi _\alpha}$

反向解码器与SAN联合训练，但在推理过程中省略，以跳过额外的推理时间。

训练

SAN的训练目标是最小化以下损失的和：

symbol loss( $L_{symbol}$ )
relation loss( $L_{relation}$ )
reverse symbol loss( $L_{symbol}^{rev}$ )
attention self-regularization loss( $L_{reg}$ )

本文使用教师强制策略来加速收敛。通过深度优先搜索算法对LaTeX序列进行解析，得到每张训练图像的真值解析树，以便于从解析树种获取父子样本列表。随后根据树的先序遍历处理每一个样本，知道整棵树遍历完。同时本文使用反向decoder来预测每个子节点的父节点。然后使用真实标签计算symbol、reverse symbol、relation的损失。而attention self-regularization loss使用上文种提到的 $L_{reg}$ 公式计算得到。于是，参数的更新就是通过最小化以下公式进行：