VIII. 图形转换网络和转换器 Graph Transformer Networks and Transducers

在第四节中，图形转换网络（GTN）被介绍为多层、多模块网络的一种泛化，其中状态信息以图形而不是固定大小的向量表示。

本节将在广义转导框架中重新解释GTN，并提出了一个强大的图形组合算法。

A. 先前的工作

在语音识别领域，许多作者使用了梯度下降学习方法，将基于图形的统计模型（特别是HMM）与声学识别模块相结合，主要是高斯混合模型，但也包括神经网络。类似的想法已经应用于手写识别（参见[38]进行回顾）。

然而，对于基于图形的多层可训练系统，尚未提出系统化的方法。

将图形转换为其他图形的想法在计算机科学中受到了广泛的关注，通过加权有限状态转换器的概念。转换器已经应用于语音识别和语言翻译，并且已经提出了手写识别的方案。这项工作主要集中在有效的搜索算法和将转换器与图形（在这种情况下称为接受器）组合的代数方面，但很少有工作致力于构建全局可训练系统。

在接下来的章节中提出了一种系统化的方法来自动训练图形处理系统。另一种基于图形的可训练系统的方法，称为输入-输出HMM，在[104]，[105]中提出。

B. 标准转导

在已建立的有限状态转换器框架中，离散符号附加到图形的弧上。接受器图形中每个弧都有一个符号，而转换器图形有两个符号（一个输入符号和一个输出符号）。一个特殊的空符号会被任何其他符号吸收（当连接符号以构建符号序列时）。加权转换器和接受器也具有附加到每个弧的标量量。在这个框架中，合成操作将接受器图形和转换器图形作为输入，并构建一个输出接受器图形。这个输出图形中的每个路径（带有符号序列Sout）对应于输入接受器图形中的一个路径（带有符号序列Sin）和转换器图形中的一个路径以及相应的输入/输出序列（Sout，Sin）。输出图的弧上的权重是通过将输入接受器和转换器图中的匹配弧的权重相加而获得的。在本文的其余部分，我们将使用转换器进行图形合成操作称为（标准）转导操作。

转导的一个简单示例如图28所示。在这个简单的示例中，转换器弧上的输入和输出符号始终相同。这种类型的转换器图称为语法图。为了更好地理解转导操作，想象两个令牌分别位于输入接受器图和转换器图的起始节点上。令牌可以自由地沿着标有空输入符号的弧移动。如果另一个令牌也沿着标有相同输入符号的弧移动，则一个令牌可以沿着标有非空输入符号的弧移动。当两个令牌都到达其图的结束节点时（即，令牌已到达终端配置），我们有一个可接受的轨迹。此轨迹表示符合接受器和转换器的符号序列。然后，我们可以沿着转换器令牌的轨迹收集相应的输出符号序列。上述过程产生一棵树，但可以使用第VIII-C节中描述的简单技术来避免通过检测是否已经看到了特定输出状态来生成某些子图的多个副本。

转导操作可以非常高效地执行，但涉及复杂的记账问题，涉及处理所有空和非空符号的组合。如果将权重解释为概率（适当归一化），那么接受器图表示由图中所有可能路径（从开始到结束节点）关联的标签序列定义的语言的概率分布。

转导操作的一个应用示例是在识别单词或其他字符串时纳入语言约束（词汇表或语法）。识别变换器通过将神经网络识别器应用于每个候选段来生成识别图（接受器图）。这个接受器图与包含语法的转换器图进行组合。语法转换器包含每个符号的合法序列的路径，可能增加了用于指示可能序列的相对可能性的惩罚。弧包含相同的输入和输出符号。转导的另一个示例在第V节中提到：用于启发式过分割训练GTN的路径选择器可以通过合成来实现。转换器图是包含正确标签序列的线性图。将解释图与此线性图的组合产生约束图。

C. 广义转导

如果与每个弧关联的数据结构仅具有有限数量的值，则将输入图与适当的转换器进行组合将是一个有效的解决方案。

然而，对于我们的应用，附加到图的弧上的数据结构可能是矢量、图像或其他不容易枚举的高维对象。我们提出了一种解决这个问题的新组合操作。

我们感兴趣的不仅是处理具有离散符号和弧上的惩罚的图，而且还考虑到弧可能携带复杂数据结构的图，包括连续值数据结构，如矢量和图像。组合这样的图需要额外的信息：

  • 当检查一对弧（一个来自每个输入图）时，我们需要一个标准来决定是否基于附加到输入弧的信息在输出图中创建相应的弧和节点。我们可以决定构建一个弧、几个弧，或一个包含几个节点和弧的整个子图。

  • 当满足该标准时，我们必须在输出图中构建相应的弧和节点，并计算新创建的弧所附加的信息，作为输入弧的附加信息的函数。

这些函数封装在一个称为组合转换器的对象中。组合转换器的一个实例实现了三种方法：

  • check(arc1, arc2)：比较由弧arc1（来自第一个图）和arc2（来自第二个图）指向的数据结构，并返回一个布尔值，指示是否应在输出图中创建相应的弧。

  • fprop(ngraph, upnode, downnode, arc1, arc2)：当check(arc1, arc2)返回true时调用该方法。此方法在输出图ngraph的upnode和downnode之间创建新的弧和节点，并计算新创建的弧所附加的信息，作为输入弧arc1和arc2附加信息的函数。

  • bprop(ngraph, upnode, downnode, arc1, arc2)：在训练期间调用此方法，以将输出子图（在upnode和downnode之间）中的梯度信息传播到arc1和arc2上的数据结构，以及关于与fprop调用中相同参数的参数的梯度。这假设由fprop用于计算其输出弧附加值的函数是可微的。

check方法可以被视为构造一个功能依赖动态架构，而fprop方法执行对该架构的前向传播，以计算附加到弧上的数值信息。bprop方法通过相同的架构执行后向传播，以计算损失函数相对于附加到弧上的信息的偏导数。如图28所示。

  • F28

F28

图29显示了一个简化的广义图组合算法。此简化算法不处理空转换，并且不检查令牌轨迹是否可接受（即，两个令牌同时到达其图的结束节点）。空转换的管理是对令牌模拟函数的直接修改。在列举可能的非空联合令牌转换之前，我们循环处理每个令牌的可能空转换，递归调用令牌模拟函数，最后调用方法fprop。确定可接受轨迹的最安全方法是通过运行预处理传递来识别可以到达终端配置的令牌配置（即，两个令牌位于结束节点上）。这通过沿着上游方向枚举轨迹来轻松实现。我们从结束节点开始，并跟随上游的弧。在主传递期间，我们只构建允许令牌到达终端配置的节点。

  • F29
Function generalized_composition(PGRAPH graph1, PGRAPH graph2, PTRANS trans)
Returns PGRAPH
{
    // Create new graph
    PGRAPH ngraph = new_graph()

    // Create map between token positions and nodes of the new graph
    PNODE map[PNODE, PNODE] = new_empty_map()
    map[endnode(graph1), endnode(graph2)] = endnode(newgraph)

    // Recursive subroutine for simulating tokens
    Function simtokens(PNODE node1, PNODE node2)
    Returns PNODE
    {
        PNODE currentnode = map[node1, node2]

        // Check if already visited
        If (currentnode == nil)
        {
            // Record new configuration
            currentnode = ngraph->create_node()
            map[node1, node2] = currentnode

            // Enumerate the possible non-null joint token transitions
            For ARC arc1 in down_arcs(node1)
            {
                For ARC arc2 in down_arcs(node2)
                {
                    If (trans->check(arc1, arc2))
                    {
                        PNODE newnode = simtokens(down_node(arc1), down_node(arc2))
                        trans->fprop(ngraph, currentnode, newnode, arc1, arc2)
                    }
                }
            }
        }
        // Return node in composed graph
        Return currentnode
    }

    // Perform token simulation
    simtokens(startnode(graph1), startnode(graph2))
    
    Delete map
    Return ngraph
}

图29. 简化的广义组合算法的伪代码。为了简化演示，我们不处理空转换，也不实现避免死胡同。组合的两个主要组成部分在这里清楚地显示出来：(a) 递归函数simtoken()枚举令牌轨迹，以及(b) 用于记住已访问的合成图节点的关联数组map。

使用转换器（即标准转导）进行图组合易于实现且有效。check方法简单地测试两个弧上的输入符号的相等性，而fprop方法创建一个符号是转换器弧上的输出符号的弧。

对图对进行组合尤其有用，用于在手写识别器中包含语言约束。在第九节中描述的在线手写识别系统以及第十节中描述的支票阅读系统中给出了其使用示例。

在本文的其余部分，术语组合转换器将表示基于多个图的广义转换的图变换器。广义转导的概念非常通用。实际上，本文早期描述的许多图变换器，如分段器和识别器，都可以用广义转导来表述。在这种情况下，广义转导不是使用两个输入图，而是单个输入图。变换器的fprop方法可以为初始图的每个弧创建几个弧甚至一个完整的子图。实际上，（检查，fprop）对本身可以被视为过程化地定义一个转换器。

此外，可以证明单个图的广义转导在理论上等价于该图与特定转换器图的标准组合。然而，通过这种方式实现操作可能非常低效，因为转换器可以非常复杂。

实际上，广义转导产生的图是以过程方式表示的，以避免构建整个输出图（当解释图与语法图组合时可能会非常庞大）。

我们仅实例化搜索算法在识别期间访问的节点（例如Viterbi）。

这种策略将修剪算法（例如Beam Search）的好处传播到所有图变换器网络中。

D. 对图结构的注解

第六节讨论了通过简单的图变换器反向传播梯度进行全局训练的想法。bprop方法是用于通用图变换器的反向传播算法的基础。广义组合变换器可以被看作是在输入和输出弧上动态建立数值关系。一旦check函数决定建立关系，fprop函数就实现数值关系。check函数确定组合变换器内部临时网络的结构。由于假设fprop是可微的，梯度可以通过该结构反向传播。大多数参数影响系统连续图上的分数。少数阈值参数可能决定图中是否出现弧。由于不存在的弧等效于具有非常大的惩罚的弧，因此我们只考虑影响惩罚的参数。

在我们到目前为止讨论的系统中（以及第十节描述的应用中），由图变换器生成的图的结构大部分取决于图变换器的性质，但也可能取决于参数的值和输入。考虑到学习输出图的结构可能是有趣的。这可能被认为是一个组合问题，不适合基于梯度的学习，但解决这个问题的一个方法是生成一个包含图候选项的大图作为子图，然后选择适当的子图。

E. GTN和隐马尔可夫模型

GTNs可以被视为隐马尔可夫模型（HMMs）的一般化和扩展。一方面，可以保持概率解释（惩罚项为对数概率），将其推到最终决策阶段（将受限前向惩罚和非受限前向惩罚之间的差异解释为标签序列的负对数概率），或者完全放弃（网络仅表示输入空间中标签序列的决策面）。

另一方面，图转换网络通过允许在一个基本框架中结合多个层次的处理或多个模型（例如，Pereira等人一直在使用转换器框架来堆叠表示自动语音识别中不同处理层次的HMMs）扩展了HMMs。

将HMM在时间上展开会产生一个与我们的解释图（在图转换网络的最终处理阶段，在维特比识别之前）非常相似的图。它具有与模型中的每个时间步骤t和状态i相关联的节点n(t; i)。然后，从n(t-1; j)到n(t; i)的弧的惩罚ci对应于在时间间隔（t-1; t）内发射观察数据ot并从状态j转移到状态i的负对数概率。有了这种概率解释，前向惩罚就是整个观察数据序列的似然的负对数对数（给定模型）。

在第VI节中，我们提到当使用非判别性损失函数来训练神经网络/HMM混合系统时可能会发生崩溃现象。对于具有固定预处理的经典HMMs，这个问题并不会发生，因为发射和转移概率模型的参数被强制满足某些概率约束：随机变量在其可能值上的概率的和或积分必须为1。因此，当某些事件的概率增加时，其他事件的概率必须自动减少。另一方面，如果HMM（或其他概率模型）中的概率假设不现实，那么如第VI节所讨论的，判别性训练可以提高性能，因为这已经清楚地在语音识别系统中显示出来。

输入-输出HMM模型（IOHMM）与图转换器密切相关。将其视为概率模型，IOHMM表示给定输入序列（相同或不同长度）的输出序列的条件分布。它由发射概率模块和转移概率模块参数化。发射概率模块计算输出变量的条件发射概率（给定输入值和离散“状态”变量的值）。转移概率模块计算“状态”变量值变化的条件转移概率，给定输入值。将其视为图转换器，它将输出图（表示输出变量序列的概率分布）分配给输入图中的每条路径。所有这些输出图具有相同的结构，并且它们的弧上的惩罚项简单地相加，以获得完整的输出图。发射和转移模块的输入值从IOHMM图转换器的输入弧上读取。实际上，输出图可能非常大，并且不需要完全实例化（即，它被修剪：仅创建低惩罚路径）。

IX. 在线手写识别系统

自然手写往往是不同“风格”的混合体，包括小写印刷体、大写字母和草书。对于这种手写的可靠识别器将极大改进与基于笔的设备的交互，但其实施面临新的技术挑战。单独提取字符可能会非常模糊，但从整个单词的上下文中可以获得相当多的信息。我们建立了一个针对基于笔的设备的单词识别系统，该系统基于四个主要模块：一个预处理器通过将几何模型拟合到单词结构来规范化单词或单词组；一个模块从规范化的笔轨迹生成“带标注图像”；一个复制的卷积神经网络，用于检测和识别字符；以及一个考虑了单词级约束的GTN来解释网络的输出。网络和GTN被联合训练以最小化在单词级别定义的错误度量。

在这项工作中，我们比较了基于SDNNs的系统（如第VII节中所述），以及基于启发式过分割的系统（如第V节中所述）。

由于笔迹信息的顺序性质（比纯光学图像输入提供更多信息），启发式过分割在提出候选字符切割方案方面可以非常有效，特别是对于非草书体写法。

A. 预处理

输入规范化减少了字符内部变异，简化了字符识别。我们采用了基于拟合单词结构的几何模型的单词规范化方案。我们的模型有四条“灵活”的线，分别表示上升线、核心线、基线和下降线。这些线适配于笔迹的局部极小值或极大值。这些线的参数是用EM算法的修改版本估计的，以最大化观察点和参数值的联合概率，使用对参数的先验防止线彼此重叠。

从数字化表面的笔迹上识别手写字符通常是在时间域进行的。通常，笔迹被规范化，并提取局部几何或动态特征。然后可以使用曲线匹配或其他分类技术进行识别。虽然这些表示具有一些优点，但它们对笔画顺序和个体书写风格的依赖使它们在将分割与识别集成到高准确度、与书写者无关的系统中变得困难。

由于写作者的目的是产生可读的图像，因此在尽可能保留信号的图像性质的同时，利用轨迹中的顺序信息似乎是很自然的。为此，我们设计了一个表示方案，称为AMAP，其中笔迹通过低分辨率图像表示，其中每个图像元素包含关于笔迹的局部特性的信息。AMAP可以被视为一个“带标注图像”，其中每个像素是一个5元素特征向量：4个特征与像素周围的四个笔迹方向相关联，第五个特征与像素周围的局部曲率相关联。AMAP表示的一个特别有用的特征是它对输入轨迹的性质几乎没有假设。它不依赖于笔画顺序或书写速度，并且可以与所有类型的手写（大写、小写、草书、标点符号、符号）一起使用。

与许多其他表示不同（如全局特征），AMAP可以对完整的单词进行计算，而无需进行分割。

B. 网络架构

我们发现的用于在线和离线字符识别的最佳网络之一是一个5层卷积网络，与LeNet-5有些相似（见图2），但具有多个输入平面和最后两层上不同数量的单元。第1层：使用8个大小为3x3的卷积核进行卷积，第2层：2x2子采样，第3层：使用25个大小为5x5的卷积核进行卷积，第4层：使用84个大小为4x4的卷积核进行卷积，第5层：2x1子采样，分类层：95个RBF单元（在完整的可打印ASCII字符集中每个类别一个）。输出上的分布式代码与LeNet-5相同，但与LeNet-5不同，它们是自适应的。当在启发式过分割系统中使用时，上述网络的输入由一个包含五个平面、20行和18列的AMAP组成。确定了这个分辨率足以表示手写字符。在SDNN版本中，列的数量根据输入单词的宽度而变化。一旦确定了子采样层的数量和卷积核的大小，包括输入在内的所有层的大小都将明确确定。剩下要选择的唯一架构参数是每层的特征图数量，以及哪个特征图连接到哪个其他特征图的信息。在我们的情况下，子采样率尽可能选择得小（2x2），而第一层的卷积核尽可能小（3x3），以限制总连接数。上层的卷积核大小被选择为尽可能小，同时满足上述大小约束。更大的架构并不一定表现更好，并且需要更多的训练时间。一个非常小的架构，输入字段减少一半，也表现更差，因为输入分辨率不足。需要注意的是，与光学字符识别相比，输入分辨率仍然要低得多，因为角度和曲率提供的信息比每个像素的单个灰度级更多。

  • F30

F30

C. 网络训练

训练分为两个阶段。首先，我们固定了RBF（径向基函数）的中心，并训练网络权重，以使对应于正确类别的RBF单元的输出距离最小化。这相当于最小化前一层与正确类别RBF中心之间的均方误差。这个自举阶段是在孤立的字符上执行的。在第二阶段，所有参数、网络权重和RBF中心都被全局训练，以最小化单词级别的判别标准。

在启发式过分割方法中，GTN由四个主要的图转换器组成：

  1. 分割转换器执行启发式过分割，并输出分割图。然后，为与该图的弧相关联的每个图像计算一个AMAP。
  2. 字符识别转换器将卷积网络字符识别器应用于每个候选段，并输出识别图，每个弧上带有惩罚和类别。
  3. 组合转换器将识别图与表示包含词汇约束的语言模型的语法图进行组合。
  4. 波束搜索转换器从解释图中提取出一个好的解释。这个任务本来可以用通常的维特比转换器来完成。但是波束搜索算法实现了适用于大型解释图的修剪策略。

使用SDNN方法时，主要的图转换器如下：

  1. SDNN转换器将卷积网络复制到整个单词图像上，并输出一个识别图，该图是一个线性图，对于输入图像上以固定间隔居中的每个窗口，都带有类别惩罚。
  2. 字符级别组合转换器将识别图与每个字符类别的从左到右的HMM组合起来。
  3. 单词级别组合转换器将前一个转换器的输出与包含词汇约束的语言模型组合，并输出解释图。
  4. 波束搜索转换器从解释图中提取出一个好的解释。

在这个应用中，语言模型简单地将最终输出图约束为表示给定字典中字符标签序列。此外，解释图实际上并没有完全实例化：只有波束搜索模块需要的节点才会被创建。因此，解释图是以程序化方式而不是显式方式表示的。

这项研究的一个关键贡献是在网络内的所有图转换器模块上进行联合训练，基于单一标准，如第VI节和第VIII节所述。我们在最终的输出图上使用了判别前向损失函数：最小化受约束解释（即沿着所有“正确”路径）的前向惩罚，同时最大化整个解释图（即沿着所有路径）的前向惩罚。在全局训练期间，使用附录C中描述的随机对角列文伯格-马夸尔特过程优化损失函数，该过程使用二阶导数来计算最优学习率。此优化操作在系统中的所有参数上进行，特别是网络权重和RBF中心。

D. 实验结果

在第一组实验中，我们评估了神经网络分类器与单词规范化预处理和AMAP输入表示结合的泛化能力。所有结果都是在与作者无关的模式下进行的（训练和测试中的不同作者）。首先，对孤立字符进行了初始训练，使用了约100,000个手写字符的数据库（95个类别的大写、小写、数字和标点符号）。对孤立字符的数据库进行了单独测试，分别针对四种字符类型进行了测试：大写（9122个模式的误差率为2.99%）、小写（8201个模式的误差率为4.15%）、数字（2938个模式的误差率为1.4%）和标点符号（881个模式的误差率为4.3%）。实验使用了上述描述的网络架构。为了增强识别器对位置、大小、方向和其他失真的鲁棒性，通过对原始字符应用局部仿射变换生成了额外的训练数据。

第二和第三组实验涉及对小写单词的识别（与作者无关）。测试是在一个包含881个单词的数据库上进行的。首先我们评估了单词规范化对系统带来的改进。对于SDNN/HMM系统，由于网络一次只能看到一个完整的单词，因此我们必须使用单词级别的规范化。使用启发式过分割系统，在进行任何单词级别的训练之前，当搜索限制在一个包含25461个单词的词典中时，使用字符级别规范化时，得到了7.3%和3.5%的单词和字符错误（添加插入、删除和替换），当使用单词规范化预处理而不是字符级别规范化时，错误率分别下降到了4.6%和2.0%，即单词错误率和字符错误率分别下降了37%和43%。这表明，在实验的第三组中，我们测量了通过神经网络和后处理器的联合训练使用单词级别标准与仅基于字符级别错误训练相比的改进。在如上所述对单个字符进行初始训练后，使用一个包含3500个小写单词的数据库进行了全局单词级别的判别性训练。对于SDNN/HMM系统，在没有任何字典约束的情况下，单词和字符错误率从38%和12.4%分别降至26%和8.2%。对于启发式过分割系统和稍微改进的架构，在没有任何字典约束的情况下，单词和字符错误率从22.5%和8.5%分别降至17%和6.3%。使用一个包含25461个单词的词典，错误率从4.6%和2.0%的单词和字符错误率分别降至3.2%和1.4%。甚至可以通过大幅减少词典的大小至350个单词来获得更低的错误率，产生1.6%和0.94%的单词和字符错误率。这些结果清楚地证明了全局训练的神经网络/HMM混合系统在手写识别中的有用性，这也证实了早期在语音识别中得到的类似结果。

X. 支票阅读系统

本节描述了基于GTN的支票阅读系统，旨在实现即时的工业部署。

它还展示了梯度基础学习和GTN的使用如何使得部署快速和成本有效，同时提供准确可靠的解决方案。

验证支票金额是银行极为耗时和金钱的任务。因此，尽可能自动化这个过程具有非常高的兴趣（例如参见[112]，[113]，[114]）。即使部分自动化也将导致相当大的成本降低。由银行设定的自动支票阅读器的经济可行性阈值是，当50%的支票读取误差小于1%时。另外50%的支票被拒绝并发送给人工操作员。在这种情况下，我们描述系统的性能为50%正确/49%拒绝/1%错误。在业务和个人支票的典型混合情况下，这个系统是最早跨越这个阈值的之一。

支票上至少包含两个版本的金额。礼貌金额用数字写出，而法定金额用字母写出。在通常由机器打印的商业支票上，这些金额相对容易读取，但由于商业支票布局的缺乏标准，很难找到。另一方面，个人支票上的这些金额易于找到，但要读取起来要困难得多。

为了简化（并满足速度要求），我们最初的任务是仅读取礼貌金额。这个任务包括两个主要步骤：

  • 系统必须在所有字段（文本行）中找到最有可能包含礼貌金额的候选项。对于许多个人支票来说，这是显而易见的，因为金额的位置是标准化的。然而，正如前面已经提到的，即使对于人眼来说，找到金额在商业支票上也可能相当困难。有许多数字串，例如支票号码、日期，甚至“不超过”金额，可能会与实际金额混淆。在许多情况下，在进行完整识别之前，很难确定哪个候选项是礼貌金额。
  • 为了读取（和选择）一些礼貌金额候选项，系统必须将字段分割成字符，读取和评分候选字符，并最终利用由支票金额的随机语法表示的上下文知识找到最佳解释。

GTN方法论被用于构建一个支票金额阅读系统，可以处理个人支票和商业支票。

A. 支票金额识别的GTN

我们现在描述了一系列图形转换，使得该网络能够读取支票金额。每个图形转换器产生一个图形，其路径编码和评分当前在系统中考虑的假设阶段。

系统的输入是一个带有单个弧的平凡图，该弧携带整个支票的图像。字段位置转换器首先执行经典的图像分析（包括连通分量分析、墨水密度直方图、布局分析等），并启发式地提取可能包含支票金额的矩形区域。Tfield生成一个输出图，称为字段图，其中每个候选区域与一个将开始节点链接到结束节点的弧相关联。每个弧包含区域的图像和从区域提取的简单特征计算的惩罚项（绝对位置、大小、长宽比等）。如果特征表明该字段很可能是候选项，则惩罚项接近零，如果认为该字段不太可能是金额，则惩罚项较大。惩罚函数是可微分的，因此其参数是全局可调的。

一个弧可以表示分开的美元和分数金额作为字段的序列。实际上，在手写支票中，分数金额可能写在一个分数线上，与美元金额完全不对齐。在最坏的情况下，一个可能找到同一个美元金额的多个分数金额候选项（在分数线上方和下方）。

类似于第VIII节中描述的分割转换器Tseg，检查字段图中包含的每个区域，并使用启发式图像处理技术将每个图像切成墨水块。每个墨水块可以是一个完整的字符或一个字符的一部分。字段图中的每个弧都被其对应的分割图替换，该分割图表示所有可能的墨水块的分组。每个字段分割图附加到包含字段图中的字段的弧，其中包含该字段的惩罚。每个弧携带段图像，以及一个提供段实际包含字符的可能性的第一评估的惩罚。这个惩罚是通过一个可微分函数得到的，该函数结合了一些简单的特征，如墨水块之间的间隔或段图像与全局基线的一致性，以及一些可调参数。分割图表示所有字段图像的所有可能分割。我们可以通过沿着相应路径添加弧惩罚来计算一个分割字段的惩罚。与以前一样，使用一个可微分函数来计算惩罚将确保参数可以在全局优化。

分割器使用各种启发式方法来找到候选切割点。其中最重要的之一称为“撞击和偏移”[115]。其思想是从字段图像顶部向下投射线条。当一条线碰到黑色像素时，它被偏移到跟随对象的轮廓。当一条线碰到上半部分轮廓的局部最小值时，即当它不能继续向下而不穿过黑色像素时，它只是沿着墨水垂直向下传播。当两条这样的线相遇时，它们被合并成一个单一的切割。该过程可以从底部向上重复。这种策略允许分离触摸字符，如双零。

识别转换器Trec遍历分割图中的所有分割弧，并在相应的分割图像上运行字符识别器。在我们的情况下，识别器是LeNet-5，即在第二节中描述的卷积神经网络，其权重构成可调参数的最大且最重要的子集。识别器将分割图像分类为95个类别（全打印ASCII集）加上一个垃圾类别，用于未知符号或形态不良的字符。输入图Trec中的每个弧都被输出图中的96个弧替换。这96个弧中的每一个都包含一个类的标签，以及一个惩罚，该惩罚是对应输入（分割）图中的弧的惩罚和通过识别器对图像进行分类在对应类中的惩罚的总和。换句话说，识别图表示一个加权字符类的格子图。该图中的每条路径表示对应字段的可能字符字符串。我们可以通过沿着路径添加惩罚来计算这种解释的惩罚。这个字符序列可能是一个有效的支票金额，也可能不是。

组合转换器Tgram选择表示支票金额有效字符序列的识别图路径。该转换器接受两个图形作为输入：识别图和语法图。语法图包含构成形式良好的金额的所有可能符号序列。组合转换器的输出称为解释图，其中包含与语法兼容的识别图中的所有路径。将两个输入图组合成输出的操作是一种广义转换（见第八节）。一个可微函数用于计算附加到输出弧上的数据，该数据来自附加到输入弧上的数据。在我们的情况下，输出弧接收两个弧的类标签，并通过简单地将两个输入弧的惩罚相加（识别器惩罚和语法图中的弧惩罚）来计算惩罚。解释图中的每条路径表示对支票上一个字段的一个分割的一个解释。沿路径的惩罚之和表示相应解释的“不良程度”，并结合了沿着过程中每个模块以及语法的证据。

维特比转换器最终选择累积惩罚最低的路径，对应于最佳的语法正确解释。

B. Gradient-Based Learning

这个支票阅读系统的每个阶段都包含可调参数。虽然其中一些参数可以手动调整，例如字段定位器和分割器的参数，但其中绝大多数必须学习，特别是神经网络识别器的权重。在全局优化系统之前，每个模块的参数都会初始化为合理的值。字段定位器和分割器的参数是手动初始化的，而神经网络字符识别器的参数则是通过在预分割和标记的字符数据库上进行训练来初始化的。然后，整个系统从带有正确金额标签的整个支票图像中进行全局训练。训练系统时不需要明确分割金额：它是在支票级别上进行训练的。

我们的全局训练过程最小化的损失函数E是在第VI节中描述的判别前向准则：受约束的解释图（由正确的标签序列约束）的前向惩罚与未受约束的解释图的前向惩罚之间的差异。虽然可以通过整个结构进行反向传播的导数，但只有在分割器中才能实际进行。

C. Rejecting Low Condence Checks

为了能够拒绝最有可能产生错误维特比答案的支票，我们必须对它们进行评分，并在此置信度低于给定阈值时拒绝支票。

当决定我们最信任的答案时，对比两个不同支票的非规范化维特比惩罚是没有意义的。

最佳的置信度度量是给定输入图像的维特比答案的概率。正如在VI-E节中所见，给定一个目标序列（在这种情况下，将是维特比答案），判别前向损失函数是该概率的对数的估计。因此，获得置信度的良好估计的简单解决方案是重用解释图（见图33）来计算判别前向损失，如图21所述，将维特比答案作为我们的期望序列。

这在图34中总结如下：

置信度 = exp(Edforw)

以上系统的一个版本已经完全实现并在机器打印的商业支票上进行了测试。该系统基本上是一个通用的 GTN 引擎，具有任务特定的启发式方法封装在支票和 fprop 方法中。因此，需要编写的代码量很小：主要是将早期的分段器适应为分段变换器。处理手写或个人支票的系统基于早期实现，该实现以受限的方式使用了 GTN 概念。

神经网络分类器最初在来自各种来源的 500,000 张字符图像上进行了训练，跨越了整个可打印的 ASCII 集。其中包括之前已经在字符串级别进行了大小归一化的手写和机器打印字符。通过对原始图像进行简单的仿射变换，随机扭曲原始图像生成了额外的图像。然后，网络进一步训练了从支票图像中自动分割出的字符图像，并手动进行了验证。网络最初还被训练以拒绝由分割错误导致的非字符。然后将识别器插入到支票阅读系统中，并在整个支票图像上对一小部分参数进行了全局训练（在字段级别）。

在自动分类为机器打印的 646 张商业支票上，性能为：82% 正确识别的支票，1% 错误，17% 拒绝。这可以与之前系统在相同测试集上的性能进行比较：68% 正确，1% 错误，31% 拒绝。当检测到靠近标准位置的字符美元符号时，将支票分类为机器打印，或者如果在标准位置找不到任何内容，则在其他位置找到至少一个礼貌金额候选项。改进归因于三个主要原因。首先，神经网络识别器更大，并且在更多数据上进行了训练。其次，由于 GTN 架构，新系统可以比之前的系统更有效地利用语法约束。第三，GTN 架构为测试启发式方法、调整参数和调整系统提供了极大的灵活性。

最后一点比看起来更重要。GTN 框架将系统的“算法”部分与“基于知识”的部分分开，从而允许对后者进行轻松调整。在这项任务中，全局训练的重要性仅次于次要，因为全局训练仅涉及一小部分参数。

1995 年由系统集成商进行的独立测试显示，该系统优于其他商业礼貌金额阅读系统。该系统已集成到 NCR 的支票阅读系统产品线中。自 1996 年 6 月以来，它已经在美国的几家银行中得到应用，并且自那时起每天读取数百万支票。

XI. Conclusions

在自动模式识别的短暂历史中，增加学习的作用似乎无疑提高了识别系统的整体性能。本文描述的系统是这一事实的更多证据。卷积神经网络已经被证明能够消除手工特征提取器的需要。图形变换网络已被证明能够减少文档识别系统中手工启发式、手动标记和手动参数调整的需要。随着训练数据的丰富、计算机的速度提升以及我们对学习算法的理解不断改进，识别系统将越来越多地依赖于学习，并且其性能将得到提高。

就像反向传播算法优雅地解决了多层神经网络中的信用分配问题一样，本文介绍的基于梯度的学习过程解决了在每个新输入中功能体系结构动态变化的系统中的信用分配问题。这里介绍的学习算法在某种程度上只不过是在复杂、动态体系结构中的梯度下降的不寻常形式，而具有高效的反向传播算法来计算梯度。本文中的结果有助于建立梯度下降最小化方法作为大型系统学习的一般组织原理的有用性和相关性。

已经证明，文档分析系统的所有步骤都可以被公式化为图形变换器，通过这些变换器，梯度可以被反向传播。即使在系统的不可训练部分，也可以通过图形转换的设计理念清晰地区分领域特定的启发式方法（例如分割启发式方法）和通用的程序化知识（广义转换算法）。

值得指出的是，数据生成模型（如 HMM）和最大似然原理并未被调用来验证本文中描述的大多数体系结构和训练标准。应用于全局区分性损失函数的梯度基础学习保证了在不使用“难以证明”的原则的情况下对分类和拒绝进行最优化，这些原则会对系统架构施加严格的约束，往往以性能为代价。

更具体地说，本文中介绍的方法和架构提供了一系列用于模式识别系统中遇到的大量问题的通用解决方案：

  1. 特征提取传统上是一个固定的转换，通常是从任务的某些专家先验知识导出的。这依赖于可能不正确的假设，即人类设计者能够捕获输入中的所有相关信息。我们已经证明，将基于梯度的学习应用于卷积神经网络中，可以从示例中学习到适当的特征。这种方法的成功在 NIST 数据库上进行了广泛的比较数字识别实验中得到了证明。

  2. 图像中物体的分割和识别不能完全解耦。我们使用启发式过度分割来并行生成和评估大量假设，推迟任何决策直到整体标准被最小化。

  3. 通过训练多模块系统来优化性能的全局度量，而不需要耗费时间进行详细的手工验证，可以得到明显更好的识别性能，因为它允许这些模块朝着共同目标合作训练。

  4. 分割、字符识别和语言模型中固有的歧义应该被最优地整合。我们提出了一个统一的框架，其中应用了广义的转换方法，用于表示关于输入的加权假设集合。这种方法的成功在一个商业部署的支票阅读系统中得到了证明，该系统每天读取数百万张商业和个人支票：广义的转换引擎仅存在几百行代码。

  5. 传统的识别系统依赖于许多手工启发式方法来分隔单独可识别的对象。具有前景的 Space Displacement Neural Network 方法借鉴了卷积神经网络的稳健性和高效性，完全

避免了显式分割。使用基于梯度的学习方法可以实现分割和识别的同时自动学习。

本文提供了一小部分图形变换器模块的示例，但明显可以将这一概念应用于许多情况，其中领域知识或状态信息可以由图形表示。这在许多音频信号识别任务和视觉场景分析应用中都是如此。未来的工作将尝试将图形变换器网络应用于这些问题，希望能够更多地依赖于自动学习，而不是详细的工程化。

小结

这个系列的论文真的是太硬核了。

参考资料

http://vision.stanford.edu/cs598_spring07/papers/Lecun98.pdf