(以下内容搬运自 PaddleSpeech)

Derivative of CTC Loss

关于CTC的介绍已经有很多不错的教程了，但是完整的描述CTCLoss的前向和反向过程的很少，而且有些公式推导省略和错误。本文主要关注CTC Loss的梯度是如何计算的，关于CTC的介绍这里不做过多赘述，具体参看文末参考。

CTC主要应用于语音和OCR中，已语音Deepspeech2模型为例，CTC的网络一般如下图所示，包含softmax和CTCLoss两部分。反向传播需要求得loss L相对于logits $u^i$​的梯度。下面先介绍CTCLoss的前向计算。

图片来源于文末参考

CTC Loss 的计算

CTC中path的定义与概率的计算如下：

path 是 $ L’^T$​​的元素，用 $\pi$​​表示。 $\text{x}$​​ 是输入特征，$\text{y}$​​ 是输出label， 都是序列。 $L$​​ 是输出的 vocab, L‘ 是 $L\cup blank$​​。 $y_{{\pi }_t}^t$​​ 表示在t时刻，${\pi }_t$​​ label时的观察概率。其中${\pi }_t$​​ 表示 $\pi$​​ path在t时刻的label。$\pi$​​ 是 $\text{y}$​​ 与 $\text{x}$​​ 的一个alignment，长度是$T$​​，取值空间为$L^{\prime }$​​​。path也称为alignment。

公式（2）解释了给定输入 $\text{x}$​ ，输出 $\pi$​ path 的概率，即从时间t=1到T每个时间点的概率 $y_{{\pi }_t}^t$​ 相乘。

求出单条path后，就可以计算$p(l\mid x)$​ 的概率，计算如下：

这里边 $\mathcal{B}$ 就是映射， 即所有多对一的映射（many-to-one mapping )的集合。 这样就算出来对应一个真正的 label $\text{l}$ 的概率了，这里是求和。 求和的原因就是 aab 和 abb 都是对应成ab, 所以 aab 的概率 + abb 的概率才是生成ab的概率。

公式（3）解释了给定输入 $\mathbf{x}$​​​​​​ ，求输出$\mathbf{l}$​​​​​​ 的概率， 即所有集合 ${\mathcal{B}}^{-1}(\mathbf{l})$​​​​​​​​​​ 中 path的概率和。

CTC forward-backward 算法

CTC的优化采用算最大似然估计MLE (maximum likelihood estimation), 这个和神经网络本身的训练过程是一致的。

这个CTC 计算过程类似HMM的 forward-backward algorithm，下面就是这个算法的推导过程：

上图中的定义很清楚， 但是${\alpha }_{t-1}(s)$ and ${\alpha }_{t-1}(s-1)$ 和 ${\alpha }_t(s)$ 的关系也不那么好看出来，下图给出了具体的关于 ${\alpha }_t(s)$ 的推导过程：

这里的公式比较适合用下面的图来理解，${\alpha }_1(1)$​​​​ 其实对应的就是下图中左上角白色的圆圈。 就是上来第一个是blank 的概率， 而 ${\alpha }_1(2)$​​​​是label l 的第一个字母。 这里边我们假设每个字母之间都插入了空白，即label l扩展成l’，例如，l=[a, b, b, c]， l’=[-, a, -, b, -, b, -, c, -]。 然后对于其他圆点，在时间是1 的情况下概率都是 0. Figure 3中横轴是时间 t，从左到右是1到T；纵轴是s（sequence），从上到下是 1 到 $\mid {\mathbf{l}}^{\prime }\mid$​​​​.

接下来我们分析递归公式 (resursion)，更多介绍可以参看 [2]. 公式6分情况考虑:

• 第一种情况就是当前的label是blank， 或者 ${{\mathbf{l}}^{\prime }}_s={{\mathbf{l}}^{\prime }}_{s-2}$​​​​​​​(相邻是重复字符)：

这个时候他的概率来自于过去t-1的两个label 概率， 也就是 $a_{t-1}(s)$​​ 和 $a_{t-1}(s-1)$​​​ 。

$a_{t-1}(s)$​​ 就是说当前的 sequence 已经是 s 了，figure 3中表现为横跳， blank -->blank（例如t=3, s=3）；

而 $a_{t-1}(s-1)$是说明当前的字符还不够， 需要再加一个， 所以在figure 3中就是斜跳，从黑色圆圈到白色圆圈（例如，t=3, s=5）。

仔细观察figure 3， 除了第一排的白色圆圈， 其他白色圆圈都有两个输入， 就是上述的两种情况。 当然判断blank 的方法也可以是判断$I_{s-2}^{\prime }=I_s^{\prime }$​. 这种情况也是说明$I_s^{\prime }$​​​ 是blank, 因为每一个字符必须用 blank 隔开， 即使是相同字符。

• 第二章情况 也可以用类似逻辑得出， 只不过当前的状态s 是黑色圆圈， 有三种情况输入。

最终的概率就如公式8 所示， 这个计算过程就是 CTC forward algroirthm， 基于 Fig. 3 的左边的初始条件。

基于Fig. 3 右边的初始条件，我们还是可以计算出一个概率， 那个就是 CTC backward. 这里我就不详细介绍了， 直接截图。

这样一直做乘法， 数字值越来越小，很快就会underflow。 这个时候就需要做 scaling.

算出了forward probability 和 backward probability 有什么用呢， 解释如下图。

上图是说 forward probability and backward probability 的乘积， 代表了这个 sequence $\mathbf{l}$ t时刻，是s label 的 所有paths 的概率。 这样的话 我们就计算了 Fig. 3 中的每个圆圈的概率。为什么${\alpha }_t(s){\beta }_t(s)$ 中多出一个 $y_{{\mathbf{l}}_{\mathbf{s}}^{\prime }}^t$ ，这是因为它在 $\alpha$ 和 $\beta$ 中都包含该项，合并公式后就多出一项。

$p(\mathbf{l}|\mathbf{x})$​ 可以通过任意时刻 t 的所有 s 的 foward-backward 概率计算得来。取负对数后就是单个样本的NLL（Negative Log Likelihood）。

总结

总结一下，根据前向概率计算CTCLoss函数，可以得出如下结论：

1. 对于时序长度为T的输入序列x和输出序列z，前向概率：
   $$\begin{array}{rl}{\alpha }_t(s)& =\sum _{\underset{{\pi }_t=l_s^{\prime }}{\pi \in {\mathcal{B}}^{-1}(z)}}p({\pi }_{1:t}|x)\\ {\alpha }_1(1)& =y_{-}^1;{\alpha }_1(2)=y_{l_2^{\prime }}^1,{\alpha }_1(s)=0,\forall s>2\\ {\alpha }_t(s)& =0,\forall s<|l^{\prime }|-2(T-t)-1,\text{or}\forall s<1\\ {\alpha }_t(s)& =\{\begin{array}{ll}({\alpha }_{t-1}(s)+{\alpha }_{t-1}(s-1))y_{l_s^{\prime }}^t& \text{if ls′=b or ls−2′=ls′}\\ ({\alpha }_{t-1}(s)+{\alpha }_{t-1}(s-1)+{\alpha }_{t-1}(s-2))y_{l_s^{\prime }}^t& \text{otherwise}\end{array}\end{array}$$

2. 利用 ${\alpha }_t(s)$ 计算CTCLoss：
   $$-ln(p(l\mid x))=-ln({\alpha }_T(|l^{\prime }|)+{\alpha }_T(|l^{\prime }|-1))$$

根据后向概率计算CTCLoss函数，可以得出如下结论：

1. 对于时序长度为T的输入序列x和输出序列z，后向概率：
   $$\begin{array}{rl}{\beta }_t(s)& =\sum _{\underset{{\pi }_t=l_s^{\prime }}{\pi \in {\mathcal{B}}^{-1}(z)}}p({\pi }_{t:T}|x)\\ {\beta }_T(|l^{\prime }|)& =y_{-}^T;{\beta }_T(|l^{\prime }|-1)=y_{l_{|l^{\prime }|-1}^{\prime }}^T,{\beta }_T(s)=0,\forall s<|l^{\prime }|-1\\ {\beta }_t(s)& =0,\text{∀s>2t or ∀s<∣l′∣}\\ {\beta }_t(s)& =\{\begin{array}{ll}({\beta }_{t+1}(s)+{\beta }_{t+1}(s+1))y_{l_s^{\prime }}^t& \text{if ls′=b or ls+2′=ls′}\\ ({\beta }_{t+1}(s)+{\beta }_{t+1}(s+1)+{\beta }_{t+1}(s+2))y_{l_s^{\prime }}^t& \text{otherwise}\end{array}\end{array}$$

2. 利用 ${\beta }_t(s)$计算CTCLoss：

$$-ln(p(l\mid x))=-ln({\beta }_1(1)+{\beta }_1(2))$$

根据任意时刻的前向概率和后向概率计算CTC Loss函数，得到如下结论：

1. 对于任意时刻t，利用前向概率和后向概率计算CTCLoss：

$$\begin{gathered} p(l\mid x)=\sum _{s=1}^{|l^{\prime }|}\frac{{\alpha }_t(s){\beta }_t(s)}{y_{l_s^{\prime }}^t} \\ -ln(p(l\mid x))=-ln(\sum _{s=1}^{|l^{\prime }|}\frac{{\alpha }_t(s){\beta }_t(s)}{y_{l_s^{\prime }}^t}) \end{gathered}$$
我们已经得到CTCLoss的计算方法，接下来对其进行求导。

CTC梯度计算

微分公式

在计算梯度前，我们先回顾下基本的微分公式：
$$\begin{gathered} C^{\prime }=0 \\ {x}^{\prime }=1 \\ {x}^n=n\cdot x^{n-1} \\ (e^x{)}^{\prime }=e^x \\ log(x{)}^{\prime }=\frac{1}{x} \\ (u+v{)}^{\prime }=u^{\prime }+v^{\prime } \\ (\frac{u}{v}{)}^{\prime }=\frac{u^{\prime }v-u{v}^{\prime }}{v^2} \\ \frac{\mathrm{d}f(g(x))}{\mathrm{d}x}=\frac{\mathrm{d}f(g(x))}{\mathrm{d}g(x)}\cdot \frac{\mathrm{d}g(x)}{\mathrm{d}x} \end{gathered}$$

CTC梯度

最大似然估计训练就是最大化训练集中每一个分类的对数概率，即最小化Eq. 12。

最后就是算微分了， 整个推导过程就是加法和乘法， 都可以微分。 $O^{ML}$关于神经网络的输出 $y_k^t$的梯度见Eq. 13。因为训练样本是相互独立的，所以可以单独考虑每个样本，公式如Eq.13。

下面是CTCLoss的梯度计算：

### CTC梯度推导

回顾下之前的公式，便于理解后续推导过程。

$$\begin{gathered} p(l\mid x)=\sum _{s=1}^{|l^{\prime }|}\frac{{\alpha }_t(s){\beta }_t(s)}{y_{l_s^{\prime }}^t} \\ \begin{array}{c}{\alpha }_t(s){\beta }_t(s)=\sum _{\underset{{\pi }_t=l_s^{\prime }}{\pi \in {\mathcal{B}}^{-1}(l):}}{y}_{l_s^{\prime }}^t\prod _{t=1}^T{y}_{{\pi }_t}^t\end{array} \end{gathered}$$

其中Eq. 15的计算过程如下：

$$\begin{array}{rl}\frac{\partial p(l\mid x)}{\partial y_k^t}& =\sum _{s\in lab(z,k)}\frac{\partial \frac{{\alpha }_t(s){\beta }_t(s)}{y_k^t}}{\partial y_k^t}\\ & =\sum _{s\in lab(z,k)}\frac{({\alpha }_t(s){\beta }_t(s))’y_k^t-{\alpha }_t(s){\beta }_t(s){y_k^t}^{\prime }}{{y_k^t}^2}\\ & =\sum _{s\in lab(z,k)}\frac{({\prod }_{t^{\prime }=1}^{t-1}{y}_{{\pi }_{t^{\prime }}}^{t^{\prime }}\cdot y_k^t\cdot y_k^t\cdot {\prod }_{t^{\prime }=t+1}^T{y}_{{\pi }_{t^{\prime }}}^{t^{\prime }})’y_k^t-{\alpha }_t(s){\beta }_t(s){y_k^t}^{\prime }}{{y_k^t}^2}\\ & =\sum _{s\in lab(z,k)}\frac{2{\alpha }_t(s){\beta }_t(s)-{\alpha }_t(s){\beta }_t(s)}{{y_k^t}^2}\\ & =\sum _{s\in lab(z,k)}\frac{{\alpha }_t(s){\beta }_t(s)}{{y_k^t}^2}\\ & =\frac{1}{{y_k^t}^2}\sum _{s\in lab(z,k)}{\alpha }_t(s){\beta }_t(s)\end{array}\text{\hspace{1em}(1)}$$

NLL的公式推导如下：
$$\begin{array}{rl}\frac{\partial ln(p(l\mid x))}{\partial y_k^t}& =\frac{1}{p(l\mid x)}\frac{\partial p(l\mid x)}{\partial y_k^t}\\ & =\frac{1}{p(l\mid x){y_k^t}^2}\sum _{s\in lab(z,k)}{\alpha }_t(s){\beta }_t(s)\end{array}\text{\hspace{1em}(2)}$$

已经算出了CTCLoss对于 $y_k^t$​ 的梯度，接下来我们需要计算 CTCLoss对于$u_k^t$​（logits）的梯度。套用链式法则，并替换$y_k^t$​ 为 $y_{k^{\prime }}^t$​，结果如下图。图中 $k^{\prime }$​ 表示vocab中的某一个token，$K$​​ 是vocab的大小。

图中公式4根据链式法则得到：
$$

• \frac{ \partial ln(p(l \mid x)) }{ \partial u^t_k }
  = - \sum_{k’=1}^{K} \frac{ \partial ln(p(l \mid x)) }{ \partial y^t_{k’} } \frac{ \partial y^t_{k’} }{ \partial u^t_k } \tag{4}
  $$

图中公式3是softmax的梯度，参考 [4]，计算过程如下：
$$softmax(j)=S_j=\frac{e^{a_j}}{{\sum }_{k=1}^K{e}^{a_k}},\forall j\in 1\dots K$$

$$\begin{array}{rl}\frac{\partial S_i}{\partial a_j}& =\frac{\partial (\frac{e^{a_i}}{{\sum }_k{e}^{a_k}})}{\partial a_j}\\ & =\{\begin{array}{llc}\frac{e_i^a\sum -e_j^a{e}_i^a}{{\sum }^2}& =\frac{e_i^a}{\sum }\frac{\sum -e_j^a}{\sum }& \\ & =S_i(1-S_j)& \text{i = j, ∑ stands for ∑k=1Keka}\\ \frac{0-e_j^a{e}_i^a}{{\sum }^2}& =-\frac{e_j^a}{\sum }\frac{e_i^a}{\sum }& \\ & =-S_j{S}_i& \text{i = j, ∑ stands for ∑k=1Keka}\end{array}\\ & =\{\begin{array}{ll}{S}_i(1-S_j)& \text{i=j}\\ -S_j{S}_i=S_i(0-S_j)& \text{i=j}\end{array}\\ & =S_i({\delta }_{ij}-S_j)\end{array}\text{\hspace{1em}(3)}$$
$${\delta }_{ij}=\{\begin{array}{ll}1& \text{if i = j}\\ 0& \text{otherwise}\end{array}$$

下图中黄色框中的部分表示公式（1），即遍历所有的vocab中的token，其结果是$p(l\mid x)$​。这是因为label $l$​ 中的token一定在vocab中，且 $s\in lab(l,k^{\prime })$​ 可以是空集。当 $k^{\prime }$​ 在 l 中，s 则为label中token是$k^{\prime }$​的概率；当$k^{\prime }$​​​不在l中，s为空，概率为0。

公式（2），（3）带入（4），并结合公式（1）的结果如上图右边，即：
$$\begin{array}{rl}-\frac{\partial ln(p(l\mid x))}{\partial u_k^t}& =-\sum _{k^{\prime }=1}^K\frac{\partial ln(p(l\mid x))}{\partial y_{k^{\prime }}^t}\frac{\partial y_{k^{\prime }}^t}{\partial u_k^t}\\ & =-\sum _{k^{\prime }=1}^K\frac{y_{k^{\prime }}^t({\delta }_{k{k}^{\prime }}-y_k^t)}{p(l\mid x){y_{k^{\prime }}^t}^2}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =-\sum _{k^{\prime }=1}^K\frac{{\delta }_{k{k}^{\prime }}-y_k^t}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =\sum _{k^{\prime }=1}^K\frac{y_k^t-{\delta }_{k{k}^{\prime }}}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =\sum _{k^{\prime }=1}^K\frac{y^t}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)-\sum _{k^{\prime }=1}^K\frac{{\delta }_{k{k}^{\prime }}}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =\frac{y_k^t}{p(l\mid x)}(\sum _{k^{\prime }=1}^K\frac{1}{y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s))-\sum _{k^{\prime }=1}^K\frac{{\delta }_{k{k}^{\prime }}}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =\frac{y_k^t}{p(l\mid x)}p(l\mid x)-\sum _{k^{\prime }=1}^K\frac{{\delta }_{k{k}^{\prime }}}{p(l\mid x)y_{k^{\prime }}^t}\sum _{s\in lab(l,k^{\prime })}{\alpha }_t(s){\beta }_t(s)\\ & =y_k^t-\frac{1}{p(l\mid x)y_k^t}\sum _{s\in lab(l,k)}{\alpha }_t(s){\beta }_t(s)\end{array}$$

最终，为了通过softmax层传播CTCLoss的梯度，需要计算目标函数与 logits $u_k^t$ 的偏微分，即Eq. 16:

$$\begin{array}{rl}{\hat{\alpha }}_t(s)& \stackrel{def}{=}\frac{{\alpha }_t(s)}{C_t},C_t\stackrel{def}{=}\sum _s{\alpha }_t(s)\\ {\hat{\beta }}_t(s)& \stackrel{def}{=}\frac{{\beta }_t(s)}{D_t},D_t\stackrel{def}{=}\sum _s{\beta }_t(s)\\ -\frac{\partial ln(p(l\mid x))}{\partial u_k^t}& =y_k^t-\frac{1}{y_k^t{\sum }_{s=1}^{\mid l^{\prime }\mid }\frac{{\hat{\alpha }}_t(s){\hat{\beta }}_t(s)}{y_{l_s^{\prime }}^t}}\sum _{s\in lab(l,k)}{\hat{\alpha }}_t(s){\hat{\beta }}_t(s)\end{array}\text{\hspace{1em}(16)}$$

总结

• 通过动态规划算法计算${\alpha }_t(s)$ 和 ${\beta }_t(s)$

• 通过${\alpha }_t(s)$ 计算 $p(l\mid x)={\alpha }_T(\mid l^{\prime }\mid )+{\alpha }_T(\mid l^{\prime }\mid -1)$

• 通过${\alpha }_t(s)$ 和 ${\beta }_t(s)$

• 计算CTcLoss函数的导数:

$$\begin{array}{rl}-\frac{\partial ln(p(l\mid x))}{\partial u_k^t}& =y_k^t-\frac{1}{p(l\mid x)y_k^t}\sum _{s\in lab(l,k)}{\alpha }_t(s){\beta }_t(s)\\ & =y_k^t-\frac{1}{y_k^t{\sum }_{s=1}^{\mid l^{\prime }\mid }\frac{{\hat{\alpha }}_t(s){\hat{\beta }}_t(s)}{y_{l_s^{\prime }}^t}}\sum _{s\in lab(l,k)}{\hat{\alpha }}_t(s){\hat{\beta }}_t(s)\end{array}\text{\hspace{1em}(16)}$$

P.S. 欢迎关注我们的 github repo PaddleSpeech, 是基于飞桨 PaddlePaddle 的语音方向的开源模型库，用于语音和音频中的各种关键任务的开发，包含大量基于深度学习前沿和有影响力的模型。