CTC
Connectionist temporal classification, 直译为连接主义时序分类，简称CTC。用于端到端的语音识别中。设一段音频有T帧，而对应的音素一般来说只有U个(\(T\ge U\))，CTC要解决的问题就是从\(T\)帧的预测概率映射到长度\(U\)的音素，而这里\(U\)的大小是不确定的，因此如何对齐也是CTC要解决的问题之一。
设一共有\(k\)个音素，那么我们的RNN模型的输出结果是每一帧在\(k+1\)个类别上的概率，额外的1来自于我们新添加的标识{blank}。
形式化描述
令\(S\)是从分布\(\mathcal{D}_{\mathcal{X}\times\mathcal{Z}}\)中抽样出的样本的集合，其中\(\mathcal{X}=(\mathbb{R}^m)^*\)是所有的\(m\)维矢量输入序列，\(\mathcal{Z}=L^*\)是目标空间，是所有有限长的由字母表\(L\)中的字母组合成的序列的集合。\(S\)中的每一个样本包含一对序列\((x,z)\)，\(z=(z_1,z_2,\ldots,z_U)\)，\(\ x=(x_1,x_2,\ldots,x_T)\)，并且\(U\le T\)。CTC的目标是训练一个分类器 \(h:\mathcal{X}\mapsto\mathcal{Z}\)以最小化指定的error measure。
我们可以使用RNN对输入\(\mathcal{X}\)建模。设输入序列\(x\)长度\(T\)，features维数\(n\)，输出\(y_k^t\)表示在\(t\)时刻预测标签为\(k\)的概率，\(k\in L'=L\cup\{\mathrm{blank}\}\)： \[ p(\pi|x)=\prod^T_{t=1}y^t_{\pi_t}, \forall \pi\in L'^T. \] \(L'^T\)是所有长度为\(T\)的由字母表\(L'\)中的字母组合成的序列的集合。把\(L'^T\)中的元素称为paths。
然后我们要定义一个many-to-one的映射\(\mathcal{B}\)：\(L'^T\mapsto L^{\le T}\)，\(L^{\le T}\) 是由原字母表\(L\)的字母构成的长度不长于\(T\)的序列的集合。这一步可以简单地通过移除path中的{blank}得到 (比如 \(\mathcal{B}(a—bc—d-)=abcd\))。
最后，通过\(\mathcal{B}\) 可以定义给定输入\(x\)，预测标签\(l\in L^{\le T}\)的条件概率 \[ p(l|x) = \sum_{\pi\in\mathcal{B}^{-1}(l)}p(\pi|x). \] 有了上面的定义，我们期望CTC可以给出最可几的标签序列 \[ h(x) = \mathrm{arg\max}_{l\in L^{\le T}}p(l|x). \]
CTC 前向-反向 算法
因为计算量的问题，直接计算(2)式是不可行的，不过可以用动态规划的方法计算，与隐马尔科夫模型的Viterbi算法类似。
用\(l_{q:r}\)表示标签\(l\)中第\(q\)个字母和第\(r\)个字母之间（两端闭）的切片。定义前向概率\(\alpha_t(s)\)等于在\(t\)时刻标签\(l_{1:s}\)的概率 \[ \alpha_t(s)\equiv \sum_{\mathcal{B}(\pi_{1:t})=l_{1:s}} \prod^t_{t'=1}y^{t'}_{\pi_{t'}} \] 把在\(l\)的每个标签之间和两端插入blank得到的序列称作\(l'\)。 例如, \(l=\mathrm{CAT}\) ，那么 \[ l'=\mathrm{\_C\_A\_T\_} \] 其中“_“表示blank。\(l'\)的长度是\(2|l|+1\)。
允许预测出的前缀以blank或\(l\)的第一个符号 开始，考虑在\(l'\)上的前向传播，\(\alpha\)的初始化如下 \[ \begin{align*} \alpha_1(1) &= y_b^1 \\ \alpha_1(2) &= y_{l_1}^1 \\ \alpha_1(s) &=0,\ \forall s>2 \end{align*} \] 递归公式
\[ \begin{align} &\alpha_t(s)=0 \ \forall s<1,\\ &\alpha_t(s) = \left\{ \begin{aligned} &\bar\alpha_t(s)y^t_{l'_s}\quad &\mathrm{if}\ l'_s=b\ \mathrm{or} l'_{s-2}=l'_s \\ &(\bar\alpha_t(s)+\alpha_{t-1}(s-2))y^t_{l'_s}\quad& \mathrm{otherwise} \end{aligned} \right. \end{align} \] 其中
\[ \bar\alpha_t(s) \equiv \alpha_{t-1}(s) + \alpha_{t-1}(s-1). \] 并且令
\[ \alpha_t(s) = 0\ \forall s <|l'|-2(T-t)-1, \] 这是因为如果从这些变量出发，剩下的时间步不足以补全序列。
最终的\(l\)的概率是 \[ p(l|x)=\alpha_T(|l'|)+\alpha_T(|l'|-1). \] 类似地，可以定义反向概率\(\beta_t(s)\)等于在\(t\)时刻标签\(l_{s:|l|}\)的概率 \[ \beta_t(s)\equiv\sum_{\mathcal{B}(\pi_{t:T})=l_{s:|l|}}\prod^T_{t'=t}y^{t'}_{\pi_{t'}} \] 其反向传播与\(\alpha\)的正向传播类似
\[ \begin{align*} \beta_T(|l'|) &= y_b^T \\ \beta_T(|l'|-1) &= y_{l_{|l|}}^T \\ \beta_T(s) &=0,\ \forall s<|l'|-1 \end{align*} \] 递归公式
\[ \begin{align} &\beta_t(s)=0 \ \forall s>|l'|,\\ &\beta_t(s) = \left\{ \begin{aligned} &\bar\beta_t(s)y^t_{l'_s}\quad &\mathrm{if}\ l'_s=b\ \mathrm{or} l'_{s+2}=l'_s \\ &(\bar\beta_t(s)+\beta_{t+1}(s+2))y^t_{l'_s}\quad& \mathrm{otherwise} \end{aligned} \right. \end{align} \] 其中
\[ \bar\beta_t(s) \equiv \beta_{t+1}(s) + \beta_{t+1}(s+1). \] 并且令
\[ \beta_t(s) = 0\ \forall s >2t. \]
为了避免正向-反向传播过程中的数值下溢(underflow)，通常用\(\hat\alpha\)代替(7)、(8)式中的\(\alpha\)： \[ C_t\equiv \sum_s\alpha_t(s),\quad\hat\alpha_t(s)\equiv\frac{\alpha_t(s)}{C_t} \] 对于\(\beta\)的处理类似。在这组新的变量下目标标签的对数概率为 \[ \ln p(l|x) = \sum^T_{t=1}\ln(C_t) \]
最大似然训练
我们的目标是最小化负对数似然 \[ -\sum_{(x,z)\in S}\ln(p(z|x)) \] 各个样本是独立的，所以可以只看在一条样本上怎么算。采用梯度下降法，首先要计算目标函数对网络输出\(y^t_k\)的导数。计算的关键点是，注意到对于给定\(l\)，前向变量\(\alpha\)和后向变量\(\beta\) 在给定\(t\)和\(s\)的乘积是所有对应于\(l\)，且在\(t\)时刻经过\(l_s\)的path： \[ \alpha_t(s)\beta_t(s)=\sum_{\pi\in\mathcal{B}^{-1}(l):\ \pi_t = l'_s}y^t_{l'_s}\prod^T_{t=1}y^t_{\pi_t} \] 用(1)式带入得 \[ \frac{\alpha_t(s)\beta_t(s)}{y^t_{l'_s}}=\sum_{\pi\in\mathcal{B}^{-1}(l):\ \pi_t = l'_s}p(\pi|x). \] 总概率\(p(l|x)\)可以表达为所有的在时刻\(t\in[1,T]\)经过符号\(l_s\)的路径的概率和 \[ p(l|x)=\sum^{|l'|}_{s=1}\frac{\alpha_t(s)\beta_t(s)}{y^t_{l'_s}} \] 因为同一个符号\(k\)可能在\(l\)中出现许多次，所以定义\(\mathrm{lab}(l,k) = \{s:l'_s = k\}\)为符号\(k\)出现的位置，那么 \[ \frac{\partial p(l|x)}{\partial y^t_k} = \frac{1}{y_k^t*y_k^t}\sum_{s\in\mathrm{lab}(l,k)}\alpha_t(s)\beta_t(s). \] 请仔细注意这里的推导过程，结果中没有负号。
神经网络输出的logit为\(u^t_k\)，可以求得对数似然对\(u^t_k\)的导数 \[ \begin{align*} \frac{\partial(-\ln p(l|x))}{\partial u^t_k} & = -\frac{1}{p(l|x)}\frac{\partial p(l|x)}{\partial u^t_k} \\ & = -\frac{1}{p(l|x)} \sum_{k'}\frac{\partial p(l|x)}{\partial y^t_{k'}}\frac{\partial y^t_{k'}}{\partial u^t_k} \\ &=-\frac{1}{p(l|x)} \sum_{k'}\frac{\partial p(l|x)}{\partial y^t_{k'}}(y^t_{k'}\delta_{kk'}-y^t_{k'}y^t_k) \\ &= -\frac{1}{p(l|x)} \sum_{k'}\frac{1}{y_{k'}^t}\sum_{s\in\mathrm{lab}(l,k')}\alpha_t(s)\beta_t(s)(\delta_{kk'}-y^t_k) \\ &= -\frac{1}{p(l|x)} (\frac{1}{y_k^t}\sum_{s\in\mathrm{lab}(l,k)}\alpha_t(s)\beta_t(s)-y^t_k p(l|x)) \\ &= y^t_k - \frac{1}{y^t_k}\frac{\sum_{s\in\mathrm{lab}(l,k)}\alpha_t(s)\beta_t(s)}{p(l|x)} \\ &=y^t_k - \frac{1}{y^t_k}\frac{\sum_{s\in\mathrm{lab}(l,k)}\hat\alpha_t(s)\hat\beta_t(s)}{Z_t} \end{align*} \]
其中\(Z_t = \sum^{|l'|}_{s=1}\frac{\hat\alpha_t(s)\hat\beta_t(s)}{y^t_{l'_s}}\)。能从倒数第二步到最后一步是因为可以同时给分子分母加上hat。
剩下的反向传播和普通的神经网络一样。
参考文献
- Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks , ICML2006
PS. Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks网上流传着两个版本，一个是最初发表的版本，但这个版本中最大似然训练部分的推导存在错误。我这里用的是更正后版本使用的符号约定。一开始就被坑了，要注意甄别。
PPS. hexo的latex解析器（mathjax?)似乎有bug，当frac中套多层上下标时会报错，害我找错找了好久…