前言

本文是阅读论文《Sequence Transduction with Recurrent Neural Networks》¹ 的笔记，主要讨论 RNN-T 在语音识别（ASR）中的应用，包含训练和解码两部分。
CTC² 的作者 Alex Graves 在 2012 年提出 RNN-T，论文中列举了 CTC 的两个问题：（1）不能解决输入序列比输出序列短的问题，如语音合成；（2）CTC 假设输出序列之间独立，并未建模输出之间的依赖关系。RNN-T 用来解决这两个问题。我们按照学习算法（训练）和预测算法（解码）的顺序介绍 RNN-T。

一、学习算法

RNN-T 能够将任何长度输入序列转换为有限的离散输出序列。输入序列
$$\mathbf{x}=(x_1,x_2,\dots ,x_T)\in {\mathcal{X}}^{\ast },x_i\in \mathcal{X},1\le i\le T$$
输出序列
$$\mathbf{y}=(y_1,y_2,\dots ,y_U)\in {\mathcal{Y}}^{\ast },y_j\in \mathcal{Y},1\le j\le U$$
其中 $x_t$ 和 $y_u$ 是实值有限长度向量，比如在 ASR 中， $x_t$ 是 80 维的 Fbank 特征，$y_u$ 是对应的独热标签。$T$ 是音频时长，$U$ 表示输出的文字长度。
定义拓展的输出空间 $\overline{\mathcal{Y}}=\mathcal{Y}\bigcup \text{Ø}$，$\text{Ø}$ 表示空向量，是一个输出占位符。比如解码后的序列为 $(y_1,\text{Ø},\text{Ø},y_2,\text{Ø},y_3)\in {\overline{\mathcal{Y}}}^{\ast }$，去除空占位符后得到$(y_1,y_2,y_3)\in {\mathcal{Y}}^{\ast }$。我们称 $\mathbf{a}\in {\overline{\mathcal{Y}}}^{\ast }$ 为一个对齐，给定 $\mathbf{x}$， RNN-T 表示条件概率分布 $\mathbb{P}(\mathbf{a}\in {\overline{\mathcal{Y}}}^{\ast }|\mathbf{x})$。注意，这个时候的对齐 $\mathbf{a}$ 是包含空向量的，真正解码后的文字序列 $\mathbf{y}\in {\mathcal{Y}}^{\ast }$ 不含空向量，那 $\mathbb{P}(\mathbf{y}\in {\mathcal{Y}}^{\ast }|\mathbf{x})$ 怎么算呢？和 HMM、CTC 一样，将所有可能的对齐都加起来
$$\mathbb{P}(\mathbf{y}\in {\mathcal{Y}}^{\ast }|\mathbf{x})=\sum _{\mathbf{a}\in {\mathcal{B}}^{-1}(\mathbf{y})}\mathbb{P}(\mathbf{a}|\mathbf{x})\text{\hspace{1em}(1)}$$
其中 $\mathcal{B}:{\overline{\mathcal{Y}}}^{\ast }\mapsto {\mathcal{Y}}^{\ast }$ 是去除空向量的映射。

如图 1 所示，为了解决 CTC 的问题，RNN-T 在 CTC 的基础上添加了 Prediction RNN 和 Joint network 两个模型。于是 RNN-T 由编码器（Encoder）、解码器（Decoder）、融合器（Joiner）3 部分构成。

1.1 RNN-T模型结构

1.1.1 编码器

编码器在论文中称作转写网络 $\mathcal{F}$（Transcription Network），由双向 RNN 构成，它的作用是将 $(x_1,\dots ,x_T)$ 映射到高维表示 ${\mathbf{f}}_{\mathbf{t}},1\le t\le T$，每个 ${\mathbf{f}}_{\mathbf{t}}$ 有 $K+1$ 个值，$K+1$ 是建模单元的个数加空记号。这部分相当于 CTC 的编码器主体，到如今，具体结构已经不重要，Transformer、Zipformer 等结构均可。

1.1.2 解码器

解码器在论文中称作预测网络 $\mathcal{G}$（Prediction Network），由一层 RNN 组成，输入序列 $\hat{\mathbf{y}}=(\text{Ø},y_1,\dots ,y_U)$，$\mathbf{g}=\mathcal{G}(\hat{\mathbf{y}})$，$\mathbf{g}$ 是输出序列。$\hat{\mathbf{y}}$ 的每个元素也都是向量，假设有 $K$ 个标签，比如中文拼音建模，$K$ 约是 200。$y_i$ 代表一个标签处是 1，其余为 0 的长度为 $K$ 的向量，$\text{Ø}$ 代表全是 0 的长度为 $K$ 的向量，故 $\hat{\mathbf{y}}$ 其实是一个形状为 $K\times (U+1)$ 的张量。解码器的输出则是形状为 $(K+1)\times (U+1)$ 的张量，因为每一次的输出节点包含空记号。

1.1.3 融合器

转写网络只处理音频信号，预测网络只处理文字信息，所以我们类比传统 ASR，有时候也将其称为声学模型（Acoustic model， AM）和语言模型（Linguistic model，LM）。传统 ASR 是利用加权有限状态转换器（Weighted Finite-State Transducer，WFST）来进行解码，将两者的信息融合起来。那 RNN-Transducer 怎么融合呢？

由于转写向量 ${\mathbf{f}}_{\mathbf{t}},1\le t\le T$ 和预测向量 ${\mathbf{g}}_{\mathbf{u}},0\le u\le U$ 的长度都是 $K+1$，确定了 $t$ 和 $u$，可以将对应向量加起来，于是有
$$h(k,t,u)=exp(f_t^k+g_u^k)\text{\hspace{1em}(2)}$$
其中 $k$ 代表向量的第 $k$ 个元素。于是输出分布为
$$\mathbb{P}(k\in \bar{\mathcal{Y}}|t,u)=\frac{h(k,t,u)}{{\sum }_{k^{\prime }\in \bar{\mathcal{Y}}}h(k^{\prime },t,u)}\text{\hspace{1em}(3)}$$
原论文只是简单相加进行融合，在2013年的文章⁵ 中，作者将其替换成了神经网络，我们称其为融合器（Joiner，Joint network），这样编码器和解码器的输出维度也不限于 $K+1$，利用 softmax 函数来生成（3）中的概率分布。
我们记
$$\begin{array}{rl}y(t,u)& :=\mathbb{P}(y_{u+1}|t,u)\\ \text{Ø}(t,u)& :=\mathbb{P}(\text{Ø}|t,u)\end{array}\text{\hspace{1em}(4)(5)}$$

我们结合图 3 来说明 $y(t,u)$ 和 $\text{Ø}(t,u)$ 的含义。图 3 中节点 $(t,u)$ 表示 $t$ 时刻输出了 $u$ 个非空标签（token）的概率。从节点 $(t,u)$ 出发的横向箭头 $\text{Ø}(t,u)$ 表示 $(t,u)$ 后输出空标记，在 $\mathcal{Y}$ 空间来讲就是什么都没输出。纵向箭头表示 $(t,u)$ 后输出 $y_{u+1}$ 的概率。底部的黑色实心节点表示空标记。按照解码顺序，网格永远是从左下角出发，最终到达右上角。图 3 中的红色代表一种可能的解码路径。
相比 CTC 的解码图，RNN-T 没有斜向箭头，摆脱了时间 $t$ 的限制，就有可能输出任意多的 token，这样就解决了 CTC 的第一个问题。而 RNN-T 的创新是增加了预测网络和融合网络，建立了输出之间的依赖关系，相比 CTC，输出概率分布从 $\mathbb{P}(y_{u+1}|x_1,\dots ,x_n)$ 变为 $\mathbb{P}(y_{u+1}|x_1,\dots ,x_n,y_1,\dots ,y_u)$，解决了 CTC 的第二个问题。

1.2 前向后向算法

回顾式（1），我们无法直接写出 $\mathbb{P}(\mathbf{y}\in {\mathcal{Y}}^{\ast }|\mathbf{x})$ 的计算公式，还是通过动态规划来算。

1.2.1 前向算法

（1）前向变量
$\alpha (t,u)$ 表示 $[1:t]$ 时刻输出 token ${\mathbf{y}}_{[1,u]}$，就是图 3 中的节点 $(t,u)$。
（2）初始化
$$\alpha (1,0)=1\text{\hspace{1em}(6)}$$
（3）递推公式
每个节点只接收来自左边和下边的箭头。对 $\forall 1\le t\le T,0\le u\le U$，有
$$\alpha (t,u)=\alpha (t-1,u)\text{Ø}(t-1,u)+\alpha (t,u-1)y(t,u-1)\text{\hspace{1em}(7)}$$
（4）终止
$$\mathbb{P}(\mathbf{y}|\mathbf{x})=\alpha (T,U)\text{Ø}(T,U)\text{\hspace{1em}(8)}$$
如图 3 中节点 $(4,3)$ 经过 $\text{Ø}(4,3)$ 到达终止节点。

1.2.2 后向算法

（1）后向变量
$\beta (t,u)$ 表示 $[t:T]$ 时刻输出 token ${\mathbf{y}}_{[u+1,U]}$。
（2）初始化
$$\beta (T,U)=\text{Ø}(T,U)\text{\hspace{1em}(9)}$$
（3）递推公式
每个节点只接收来自右边和上边的箭头。对 $\forall 1\le t\le T,0\le u\le U$，有
$$\beta (t,u)=\beta (t+1,u)\text{Ø}(t,u)+\beta (t,u+1)y(t,u)\text{\hspace{1em}(10)}$$
（4）终止
$$\beta (1,0)=\beta (2,0)\text{Ø}(1,0)+\beta (1,1)y(1,0)\text{\hspace{1em}(11)}$$

1.3 反向传播

已知输入序列 $\mathbf{x}$ 和目标输出序列 ${\mathbf{y}}^{\ast }$，训练模型就是减小负对数似然 $\mathcal{L}=-ln\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})$，需要算偏导数 $\frac{\partial \mathcal{L}}{\partial f_t^k}$ 和 $\frac{\partial \mathcal{L}}{\partial g_u^k}$。
根据前向变量和反向变量的定义，不难得出
$$\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})=\sum _{(t,u):t+u=n}\alpha (t,u)\beta (t,u)\forall n:1\le n\le U+T\text{\hspace{1em}(12)}$$
结合等式（7）（10）（12）和 $\mathcal{L}$ 的定义，可以得到
$$\frac{\partial \mathcal{L}}{\partial \mathbb{P}(k|t,u)}=\{\begin{array}{cc}-\frac{\alpha (t,u)\beta (t,u+1)}{\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}& k=y_{u+1}\\ -\frac{\alpha (t,u)\beta (t+1,u)}{\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}& k=\text{Ø}\\ 0& otherwise\end{array}\text{\hspace{1em}(13)}$$
由（13）又可以推出
$$\begin{array}{rl}& \sum _{u=0}^U\sum _{k^{\prime }\in \bar{\mathcal{Y}}}\frac{\partial \mathcal{L}}{\partial \mathbb{P}(k^{\prime }|t,u)}\frac{\partial \mathbb{P}(k^{\prime }|t,u)}{\partial f_t^k}\\ =& -\frac{1}{\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}\sum _{u=0}^U\left(\frac{\partial \mathbb{P}(y_{u+1}|t,u)}{\partial f_t^k}(\alpha (t,u)\beta (t,u+1))+\frac{\partial \mathbb{P}(\text{Ø}|t,u)}{\partial f_t^k}(\alpha (t,u)\beta (t+1,u))\right)\\ =& -\frac{1}{\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}\sum _{u=0}^U\left(\frac{\partial \alpha (t,u)\beta (t,u)}{\partial f_t^k}\right)\\ =& -\frac{1}{\mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}\frac{\partial \mathbb{P}({\mathbf{y}}^{\ast }|\mathbf{x})}{\partial f_t^k}\\ =& \frac{\partial \mathcal{L}}{\partial f_t^k}\end{array}$$
第 2 个等号是因为 $\frac{\partial \mathcal{L}}{\partial \mathbb{P}(k^{\prime }|t,u)}$ 沿 $k^{\prime }$ 求和，只有 2 项非零。第 3 个等号利用了等式（10）。于是有
$$\frac{\partial \mathcal{L}}{\partial f_t^k}=\sum _{u=0}^U\sum _{k^{\prime }\in \bar{\mathcal{Y}}}\frac{\partial \mathcal{L}}{\partial \mathbb{P}(k^{\prime }|t,u)}\frac{\partial \mathbb{P}(k^{\prime }|t,u)}{\partial f_t^k}\text{\hspace{1em}(14)}$$
同理可得
$$\frac{\partial \mathcal{L}}{\partial g_u^k}=\sum _{t=1}^T\sum _{k^{\prime }\in \bar{\mathcal{Y}}}\frac{\partial \mathcal{L}}{\partial \mathbb{P}(k^{\prime }|t,u)}\frac{\partial \mathbb{P}(k^{\prime }|t,u)}{\partial g_u^k}\text{\hspace{1em}(15)}$$
由等式（3）可得
$$\frac{\partial \mathbb{P}(k^{\prime }|t,u)}{\partial f_t^k}=\frac{\partial \mathbb{P}(k^{\prime }|t,u)}{\partial g_u^k}=\mathbb{P}(k^{\prime }|t,u)[{\delta }_{k{k}^{\prime }}-\mathbb{P}(k|t,u)]\text{\hspace{1em}(16)}$$
反向传播对偏导数 $\frac{\partial \mathcal{L}}{\partial f_t^k}$ 和 $\frac{\partial \mathcal{L}}{\partial g_u^k}$ 进行回传。

二、预测算法

模型训好后，通过预测算法（解码）转写出对应的文字。论文中介绍了波束搜索（Beam Search）算法，可以扩展到任意长的序列，并通过控制波束搜索宽度，对计算成本和搜索精度进行平衡。

如图 4 所示，每一层代表时刻 $t$ 的解码选择，每一层的数字是标签的序号。比如共有 $K$ 个标签，当 $t=1$ 时，可能的路径有 $K$ 条；当 $t=2$ 时，有 $K^2$ 条路径；当 $t=n$ 时，有 $K^n$ 条路径，显然这会导致内存爆炸。波束搜索是确定搜索宽度 $W,1\le W\le K$，每一时刻 $t$，选择路径概率最大的 $W$ 个节点保存，在 $t+1$ 时，在这 $W$ 个节点的基础上拓展，再选出 $t+1$ 时刻路径概率最大的 $W$ 个节点，以此类推，将节点拓展下去，最终概率最大的路径就是转写结果。CTC 中的最佳路径解码就是 $W=1$ 的情形，由此推知，波束搜索也是近似算法。
下面是语音工具包 k2 对论文中波束搜索算法的实现 ⁷。

# k2 中的 beam search 实现
def beam_search(
    model: Transducer,
    encoder_out: torch.Tensor,
    beam: int = 4,
) -> List[int]:
    """
    It implements Algorithm 1 in https://arxiv.org/pdf/1211.3711.pdf
    
    Args:
      model:
        An instance of `Transducer`.
      encoder_out:
        A tensor of shape (N, T, C) from the encoder. Support only N==1 for now.
      beam:
        Beam size.
    Returns:
      Return the decoded result.
    """
    assert encoder_out.ndim == 3

    # support only batch_size == 1 for now
    assert encoder_out.size(0) == 1, encoder_out.size(0)
    blank_id = model.decoder.blank_id		# 空记号，编号 0
    context_size = model.decoder.context_size  # 2，bigram

    device = model.device
		
    decoder_input = torch.tensor([blank_id] * context_size, device=device).reshape(
        1, context_size
    )

    decoder_out = model.decoder(decoder_input, need_pad=False)

    T = encoder_out.size(1)  # 解码音频的长度
    t = 0

    B = HypothesisList()
    # HypothesisList 对象 B 存储当前最优的假设，形如 '0_0_48_366_65_66_6': 
    # Hypothesis(ys=[0, 0, 48, 366, 65, 66, 6], log_prob=tensor([-1.0889])
    # 保存路径和对应的概率
    B.add(
        Hypothesis(
            ys=[blank_id] * context_size,
            log_prob=torch.zeros(1, dtype=torch.float32, device=device),
        )
    )

    max_sym_per_utt = 20000

    sym_per_utt = 0

    encoder_out_len = torch.tensor([1])
    decoder_out_len = torch.tensor([1])

    decoder_cache: Dict[str, torch.Tensor] = {}
    
    # 遍历每个时间步 t, 直至音频结束或符号数量上限
    while t < T and sym_per_utt < max_sym_per_utt:
        # fmt: off
        current_encoder_out = encoder_out[:, t:t+1, :]
        # fmt: on
        A = B		# A 承接了 t - 1 时刻的最优假设，将在此假设基础上继续延拓
        B = HypothesisList()		# B 中存储 t 时刻最优 beam 个假设

        joint_cache: Dict[str, torch.Tensor] = {}

        while True:
            y_star = A.get_most_probable() # 从 A 中选取最优假设
            A.remove(y_star)

            decoder_out = run_decoder(
                ys=y_star.ys, model=model, decoder_cache=decoder_cache
            )

            key = "_".join(map(str, y_star.ys[-context_size:]))
            key += f"-t-{t}"
            
            # 利用转写向量、预测向量和 joiner 计算联合概率
            log_prob = run_joiner(
                key=key,
                model=model,
                encoder_out=current_encoder_out,
                decoder_out=decoder_out,
                encoder_out_len=encoder_out_len,
                decoder_out_len=decoder_out_len,
                joint_cache=joint_cache,
            )
					
			# 先处理空记号，虽然不输出有效 token，但需要累积概率，此路径仍是潜在最优解 
            # First, process the blank symbol
            skip_log_prob = log_prob[blank_id]
            new_y_star_log_prob = y_star.log_prob + skip_log_prob
					
			# 更新 B
            # ys[:] returns a copy of ys
            B.add(Hypothesis(ys=y_star.ys[:], log_prob=new_y_star_log_prob))
		
			# 处理非空标签，对 A 进行延拓
            # Second, process other non-blank labels
            values, indices = log_prob.topk(beam + 1)
            # 相当于图 4 中第 2 层节点 5 往节点 8 和节点 9 延拓，每次都拓展 beam + 1 个
            # 这 beam + 1 个节点可能包括空记号，之所以是 beam + 1, 也是为了保证 B 最终能筛出最大的 beam 个假设
            for idx in range(values.size(0)):
                i = indices[idx].item()
                if i == blank_id:
                    continue

                new_ys = y_star.ys + [i]

                new_log_prob = y_star.log_prob + values[idx]
                A.add(Hypothesis(ys=new_ys, log_prob=new_log_prob))

            # Check whether B contains more than "beam" elements more probable
            # than the most probable in A
            A_most_probable = A.get_most_probable()

            kept_B = B.filter(A_most_probable.log_prob)
					
			# 根据设定的束宽,筛选并保留 B 中最优的假设
            if len(kept_B) >= beam:
                B = kept_B.topk(beam)
                break
		# 进入 t + 1 层
        t += 1
	
	# 从最终保留的假设中，选取经过长度归一化处理后的最优假设
    best_hyp = B.get_most_probable(length_norm=True)
    # 移除上下文中的空白符号，返回解码结果
    ys = best_hyp.ys[context_size:]  # [context_size:] to remove blanks
    return ys

总结

论文引入了预测网络和联合网络，解决了 CTC 不合理的独立假设问题。解码时候，可以对每帧输入进行预测输出，使得 RNN-T 天然具有自回归性，可以用于流式 ASR。且 AM + LM 的组合，让建模更加完备合理。
RNN-T 也有缺点，相比 CTC 的输出维度 (N, T, C)， RNN-T 则是 (N, T, U, C)，U 是解码器的输出长度，可达上百量级。故 RNN-T 内存占用大 ，训练复杂度高。
随着模型结构的进步，编码器中的 RNN 逐渐被各种 Former 类模型（Conformer，Zipformer等）替代。谷歌在深入研究解码器后也发现 ³，RNN 结构并不是必须的，直接将 $y_{u-1}$ 的嵌入（Embedding）送入联合网络，也能达到相近的效果。就像信乐团没有信，飞儿乐队没有飞一样，RNN-T 在如今的很多论文中，都只被称作 Transducer。

参考文献

---

1. Alex Graves. Sequence Transduction with Recurrent Neural Networks. 2012. ↩︎

2. Alex Graves, et al. Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks. 2006. ↩︎

3. Ghodsi, Mohammadreza , et al. “Rnn-Transducer with Stateless Prediction Network.” ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) IEEE, 2020. ↩︎ ↩︎

4. 洪青阳，李琳. 《语音识别原理与应用》， 2020. ↩︎

5. Alex Graves, et al. Speech recognition with deep recurrent neural networks. 2013. ↩︎

6. https://en.wikipedia.org/wiki/Beam_search. ↩︎

7. https://github.com/csukuangfj/icefall/blob/master/egs/librispeech/ASR/transducer_stateless/beam_search.py. ↩︎