欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

CTC原理

0A062478-561B-4ECB-A0BE-41CEB6F8B50B

不搞语音识别得人开这个论文确实有点费劲,结合上图,思考一下语音识别的场景,输入是一段录音,输出是识别的音素, 输入的语音文件的长度和输出的音素个数之间没有一一对应关系,通常将语音文件「分片」之后,会出现多对一的关系。这个场景在「翻译问题」和「OCR问题」中也普遍存在。

本文的特点是,提出来一种end-to-end的方法,直接将语音转问音素。不需要添加规则/后处理等过程。

几个定义

损失函数定义为平均编辑距离:

QQ20170519-142650

一种路径的概率为:

QQ20170522-111511

其中 \(\pi=(\pi_1,\pi_1,...,\pi_{T})\) 表示的是选择的Label, \(\pi\) 有也称为「路径」,可以发现路径的种数是指数级的 \(T^{|L'|}\)

在现实之中,多个路径会对应一个正确的序列,并且这个序列长度往往小于路径长度,那么序列最终的概率可以使用路径的概率之和表示:

QQ20170522-151311

构造分类器

让我们再确定一下我们的目标,我们的目标是通过输入序列 \(x\) 得到输出序列 \(y\) ,如果我们可以获得输出序列的分布 \(p(I|x)\) ,选择其中概率最大的那一个作为「输出序列」即可。这个逻辑可以通过下面公式表示:

QQ20170522-152210

解码方法

这里介绍两种解码方法,解码是对path的分布进行的,输入为path的分布,输出为最终的序列。作者也没有找到比这两种更好的方法了。

Best path decoding

按照上面思路,需要找到序列 \(I\) 的所有路径的概率,一种简化的方式是:找到路径中概率最大的,然后其对应的序列 \(I\) 就是最优序列,这个方法被称为「Best path decoding」。

这个方法相当于是假设,最优序列的最优路径也是全局最优的(最优表示概率最大),形式化表示为:

QQ20170522-164515

prefix search decoding

接着介绍第二种方法,「prefix search decoding」是一种剪枝的算法,剪枝主要在两个方面,一是同路径不重复计算,二是不可能状态不再搜索,下图中第一层的Y不搜索就是因为同层的X和下层的Y概率都比他高。

prefix search decoding

这个方法是一种比较好的启发式搜索的方法。

网络训练

上面两种方式都是在模型已经训练出来,得到path概率分布之后的解码过程,那么如何训练一个网络,可以更好的预测path分布(即进行编码)呢?

首先这是一个有监督的过程,我们的输入是分片之后的语音文件, 输出是长度没有限制的音素序列。

前向后向算法

既然要训练,就要有「损失」,损失是定义预估的Label和正确的Label之间的「距离」,所以我们是希望每一条样本得到的path都可以有较高的概率生成其对应的Label。

对一条样本来说,如果给定了path如何确定生成当前样本的label(最终序列)的概率呢?根据定义,需要穷举所有可以生成正确label的path的概率,最后加到一起,这个计算量最差情况是「指数」级别的,这里可以使用类似HMM中的动态规划的方法,将时间复杂度变为 \(O(T* |L|)\) ;其中 \(T\) 表示输入序列长度, \(|L|\) 表示输出Label长度。接下来就是如何巧妙地定义状态和寻找动态转移方程。

状态定义为:

QQ20170524-171429

其中 \(\alpha_t(s)\) 表示输入前 \(t\) 个片段,输出为Label中前 \(s\) 个音素的概率。

为了实现end-to-end的训练,空格可能出现在任何两个音素之间,所以需要将原始的Label中每一个音素之间添加一个「元素」,这个「元素」可以为NULL和空格(blank)。仔细体会这个修改,对理解后面过程很重要。

理解动态转移方程之前,需要强调几个点:

  • 我们的目标是根据所有的路径(path)计算出来一个长度为 \(2|L|+1\) 的Label,即 \(L'\) 生成(解码)的概率
  • path中每一个片段的内容为:音素、NULL、空格,其中每一个都可以连续出现多个
  • 序列 \(L'\) 中,也是包含三种内容:「音素、NULL、空格」,但是有一些约束,例如下面模式不能出现:「...,音素x,NULL,音素x,...」,因为相同的音素如果是紧挨着肯定是需要合并的。

状态转移方程:

QQ20170526-174413

大概解释一下,如果当前元素为「空格」, \(\alpha_{t-1}(s-2)\) 不可能转移过来,又因为相同音素不可能挨着,所以前一个音素和当前音素相等的情况下,不能转移。

QQ20170526-180627

其中虚线的转移,需要满足条件,具体为:如果当前状态label为空格或相邻两个音素一样(中间必有空格),就不能转移。

到这里「前向算法」已经介绍完了,下面介绍「后向算法」,后向算法原理和前向算法一模一样,只是定义上有一些差别,后向概率 \(\beta_t(s)\) 定义为满足 \(B(\pi_{t:T})=l_{s:|L'|}\) 的概率,具体为:

QQ20170531-145211

似然函数

序列的似然

让我们回忆一下似然函数的定义,简单来说就是「观测到的样本生成的概率」。在我们现在的场景, 对一条样本来说,观测到的是一个序列,如果认为序列中的元素是相互独立,似然函数可以表示为:

\(ln(p(l|x))=ln \prod_{s=1}^{s=|L'|} p(s|x)=\sum_{s=1}^{s=|L'|} ln(p(s|x))=\sum_{s=1}^{s=|L'|} ln \sum_{t=1}^{t=T}{\alpha_t(s)}\)

路径的似然

路径的似然假设路径的每一个输出都是相互「独立的」,结合似然的定义,似然这里要表达的就是路径是「合法」的概率(设立合法表示可以推导到标注序列的中间状态),可以表示为:

\(ln(p(path|x))=ln \prod_{t=1}^{T}p(path_t \in True|x)=ln \prod_{t=1}^{T} \sum_{s=1}^{s=|L'|}{\alpha_t(s)}\)

其中 \(p(path_t \in True|x)=\sum_{s=1}^{s=|L'|}\alpha_t(s)\) 表示的是 \(path_{1:t}\) 可以生成合法序列的概率。

极大似然训练

这里介绍一种快速计算,如果保证t时刻生成 \(l_s\) ,那么整个label生成的概率是多少?首先理解一下下面式子的物理意义:

QQ20170531-160932

用一个图形象表示一下,可以表示为:

QQ20170531-161601

这个计算过程,将 \(y^t_s\) 计算了两次,所以除以 \(y^t_s\) 表示的就是t时刻生成 \(l_s\) 的约束下,整条label生成的概率:

QQ20170531-161720

这里就容易推导出来,表示整个样本生成的概率公式了,穷举所有可切割位置,将他们加和到一起即可:

QQ20170531-195113

我们的目标是希望得到路径上面每一个点的梯度,损失函数是极大似然的前提下,如何将梯度简化的表示(求解)是需要考虑的问题。具体计算的时候,梯度需要沿着每一个时刻的每一个分类往后传,所以需要对 \(y_k^t\) 求偏导数, \(y_k^t\)\(k\) 表示的是第k个分类,具体偏导为:

QQ20170531-203700

需要好好理解一下 \(s \in lab(l,k)\) ,表达的意思是所有 \(l_s=k\)\(s\) 的集合,因为满足条件的地方都是潜在的 \(y_k^t\) 的概率贡献方

整个似然函数对softmax未归一化之前的变量求偏导数得到(下面有链接详细介绍这个推导过程):

QQ20170531-203713

梯度反向传播的过程如下图:

QQ20170531-204114

详细的推导:CTC最后一个公式推导

实现

tensorflow 中的ctc层:https://www.tensorflow.org/versions/r0.11/api_docs/python/nn/conectionist_temporal_classification__ctc_

参考资料

https://zhuanlan.zhihu.com/p/21775142 第一次下的论文是错误的,这里有说明。

论文:Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks

未经允许不得转载:大数据算法 » CTC原理

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站