转载本文请注明出处：https://yudonglee.me/ctc-explained 作者：yudonglee 本文总共分为五部分来全面阐述CTC算法（本篇为Part 2）：Part 1：Training the Network（训练算法篇），介绍CTC理论原理，包括问题定义、公式推导、算法过程等。Part 1链接。Part 2：Decoding the Network（解码算法篇），介绍CTC Decoding的几种常用算法。Part 2链接。 在上一篇文章中我们详细介绍了CTC问题背景和模型训练的算法和原理，本篇是整体的第二部分，重点介绍CTC模型预测-解码算法。 一般在分类问题中，训练好模型之后，模型的预测过程非常简单，只需要加载模型文件从前到后执行即可得到分类结果。但在序列学习问题中，模型的预测过程本质是一个空间搜索过程，也称为解码，如何在限定的时间条件下搜索到最优解是一个非常有挑战的问题。下面，我们来详细介绍CTC的解码算法。 对CTC网络进行Decoding解码本质过程是选取条件概率最大的输出序列，即满足： 如上图的例子，按照时间序列展开得到栅格网络，解码的过程相当于空间搜索。我们可以选择暴力的解码策略：穷举搜索，但时间复杂度是指数级的，显然不可行。我们也可以选择简单的解码策略：在每一步选择概率最大的输出值，这样就可以得到最终解码的输出序列（如上图例子，最终解码的输出序列l=blank）。然而，根据上一篇介绍我们知道，CTC网络的输出序列只对应了搜索空间的一条路径，一个最终标签可对应搜索空间的N条路径，所以概率最大的路径并不等于最终标签的概率最大，即不是最优解（如上图例子，最优解是p(l=b)而不是p(l=blank)）。 本篇我们介绍两种常见的CTC解码算法：CTC Prefix Search Decoding和CTC Beam Search Decoding。简而言之，Prefix Search Decoding是基于前缀概率的搜索算法，它能确保找到最优解，但最坏情况下耗时可能会随着序列长度呈指数增长；CTC Beam Search Decoding是一种Beam Search算法，它能在限定时间下找到近似解，但不保证一定能找到最优解。 1. CTC Prefix Search Decoding CTC Prefix Search Decoding本质是贪心算法，每一次搜索都会选取“前缀概率”最大的节点扩展，直到找到最大概率的目标label，它的核心是利用动态规划算法计算“前缀概率”。下面先通过一个简单的例子来介绍CTC Prefix Search… Continue Reading →
转载本文请注明出处：https://yudonglee.me/ctc-explained作者：yudonglee 现实应用中许多问题可以抽象为序列学习（sequence learning）问题，比如词性标注（POS Tagging）、语音识别（Speech Recognition）、手写字识别（Handwriting Recognition）、机器翻译（Machine Translation）等应用，其核心问题都是训练模型把一个领域的（输入）序列转成另一个领域的（输出）序列。近年来基于RNN的序列到序列模型（sequence-to-sequence models）在序列学习任务中取得了显著的效果提升，本文介绍一种RNN（Recurrent Neural Networks）的端到端训练方法——CTC（Connectionist Temporal Classification）算法，它可以让RNN直接对序列数据进行学习，而无需事先标注好训练数据中输入序列和输出序列的映射关系，打破了RNN应用于语音识别、手写字识别等领域的数据依赖约束，使得RNN模型在序列学习任务中取得更好的应用效果。 本文总共分为五部分来全面阐述CTC算法（本篇为Part 1）：Part 1：Training the Network（训练算法篇），介绍CTC理论原理，包括问题定义、公式推导、算法过程等。Part 1链接。Part 2：Decoding the Network（解码算法篇），介绍CTC Decoding的几种常用算法。Part 2链接。 接下来，我们先从“问题”的背景说起。 1. 背景介绍 在序列学习任务中，RNN模型对训练样本一般有这样的依赖条件：输入序列和输出序列之间的映射关系已经事先标注好了。比如，在词性标注任务中，训练样本中每个词（或短语）对应的词性会事先标注好，如下图（DT、NN等都是词性的标注，具体含义请参考链接）。由于输入序列和输出序列是一一对应的，所以RNN模型的训练和预测都是端到端的，即可以根据输出序列和标注样本间的差异来直接定义RNN模型的Loss函数，传统的RNN训练和预测方式可直接适用。 然而，在语音识别、手写字识别等任务中，由于音频数据和图像数据都是从现实世界中将模拟信号转为数字信号采集得到，这些数据天然就很难进行“分割”，这使得我们很难获取到包含输入序列和输出序列映射关系的大规模训练样本（人工标注成本巨高，且启发式挖掘方法存在很大局限性）。因此，在这种条件下，RNN无法直接进行端到端的训练和预测。 如下图，输入是“apple”对应的一段说话音频和手写字图片，从连续的音频信号和图像信号中逐一分割并标注出对应的输出序列非常费时费力，在大规模训练下这种数据要求是完全不切实际的。而如果输入序列和输出序列之间映射关系没有提前标注好，那传统的RNN训练方式就不能直接适用了，无法直接对音频数据和图像数据进行训练。 因此，在语音识别、图像识别等领域中，由于数据天然无法切割，且难以标注出输入和输出的序列映射关系，导致传统的RNN训练方法不能直接适用。那么，如何让RNN模型实现端到端的训练成为了关键问题。 Connectionist Temporal Classification（CTC）[1]是Alex Graves等人在ICML 2006上提出的一种端到端的RNN训练方法，它可以让RNN直接对序列数据进行学习，而无需事先标注好训练数据中输入序列和输入序列的映射关系，使得RNN模型在语音识别等序列学习任务中取得更好的效果，在语音识别和图像识别等领域CTC算法都有很比较广泛的应用。总的来说，CTC的核心思路主要分为以下几部分： 接下来，通过一个语音识别的实际例子来引出CTC的解决思路 2. 一个实际的例子–声学模型 语音识别的核心问题是把一段音频信号序列转化文字序列，传统的语音识别系统主要分为以下几部分，如下图。 其中，X表示音频信号，O是它的特征表示，一般基于LPC、MFCC等方法提取特征，也可以基于DNN的方式“学到”声学特征的表示。为了简化问题，我们暂且把O理解为是由实数数组组成的序列，它是音频信号的特征表示。Q是O对应的发音字符序列，即建模单元，一般可以是音素、音节、字、词等。W是音频信号X对应的文字序列，即我们最终的识别结果。… Continue Reading →