ASR Head & Decoding Algorithms

CTC (Connectionist Temporal Classification)

モチベーション：アラインメント問題

音声認識では、アライメントの問題が長いこと存在する。これは、入力の音声フレーム列 $X$ は正解の文字列 $Y$ よりずっと長い（$T \gg U$）ことに起因する問題である。つまり、テキストと音声のフレームの長さが違うので、このフレームの長さをどうにかアライメントする必要がある。

例えば「こんにちは」という3秒の音声フレームを文字起こしすることを考える。16Khzの音声データだと仮定すると1秒につき16,000の時系列データになり、全部で48,000のサンプルとなる。これを特徴量空間で考えても、大体1秒50フレームくらいにはなる。となると3秒では大体150フレームとなる。これに対して、「こんにちは」は音素（音の最小単位、phoneme）で表記しても9ラベルである。つまり文字を認識するだけでなく、各文字のフレームの長さを推定してどうにか150フレームを9ラベルに集約させる必要がある。これをアライメントの問題という。

CTCはこのアライメントの問題をうまく解決したアルゴリズムの1つである。CTCの狙いは、アラインメントを明示的に与えず、あり得る全アライメントを確率的に足し合わせて、文字列全体の確率を end-to-end に最大化すること。またアライメントフリーのアルゴリズムなので、アライメント情報のアノテーションは必要とせず、音声と書き起こしのペアさえあれば学習できるように設計されている。

Blankトークンの導入

結論、CTCはblank tokenを導入することでアライメントの問題を解決している。blank tokenがなぜ必要なのかを理解するために、まずblank tokenを使わずに、“各フレームに1文字を割り当て連続する重複をまとめる”、というシンプルな方法を考えてみる。

ここで生じる問題は2つある。

1. 無音・無出力の問題：音声には無音区間があるので、すべてのフレームが文字に対応するわけではない。よって各フレームに1文字を割り当てるのは現実的に難しい。
2. 重複の問題：例えば”Hello”のアライメントを考えてみる。ここでフレーム毎に拡張された文字列 [h, h, e, l, l, l, o] を「重複をまとめる」だけで縮約すると helo になり、本来の hello の二重の l が失われる。

このような問題を解決するためにblank token $\varnothing$ が必要になる。blank tokenは「何も出力しない」を表す特別な記号であり、文字列の予測は以下の2ステップで行われる。

①連続する重複ラベルをまとめる 例えば上記の”hello”の出力文字列を考えると以下のように出力される: $(h,h,e,\varnothing,l,l,\varnothing,l,o,o)$ この文字列から重複されたラベルをまとめるので以下のようになる: $(h,e,\varnothing,l,\varnothing,l,o)$ ②blank を取り除く 重複ラベルをまとめた後にblank tokenを取り除く $(h,e,l,l,o) = hello$

このようにして、blank tokenは「重複ラベルの区切り」と「無出力フレーム」を示す役割を担っている。

ここでCTCにおける有効なアライメントであるための3つの条件を押さえておく。

• 単調性（monotonic）：フレームを1つ進めると、出力は同じラベルにとどまるか、次のラベルに進むかのみ。逆戻りはしない。
• many-to-one：複数のフレームが1つの文字に対応してよいが、その逆（1フレームが複数文字）は不可。
• 出力長が入力長より長くなることはできない：そして上記の理由から、インプットである音声フレーム長は出力であるテキスト長以上である必要がある

Loss関数の定義

ここで損失関数について定義する。CTCの損失関数は平たくいうと、特定の文字列（正解の文字列）が取りうる全てのアライメントの確率を計算し、その合計（周辺化）を最大化する設計になっている。

数学的に定義すると以下である。元の出力語彙（文字・音素・サブワードなど）の集合を $L$ とし、これに blank token を加えて拡張した語彙を $L' = L \cup \{\varnothing\}$ とする。CTCが各フレームで選ぶ選択肢はこの $L'$ の要素。

各フレーム $t$ でモデルは $L'$ 上のsoftmax分布 $y^t$ を出力する。ここで長さ $T$ のアライメント $\pi$ の確率を定義すると、条件付き独立の仮定、すなわち「各フレームの出力は $X$ さえ与えられれば過去の出力 $\pi_{<t}$ と独立」のもと以下のように定義できる： $p(\pi \mid X) = \prod_{t=1}^{T} y^t_{\pi_t}$

そして文字列 $Y$ の確率は、$Y$ に縮約される全ての有効なアライメントの周辺化（和）である： $p(Y \mid X) = \sum_{\pi \in \mathcal{B}^{-1}(Y)} p(\pi \mid X)$

ポイントは単一の最良経路ではなく同じ文字列に対して有効な全経路の和が、その文字列の確率になる点である。

モデルはこの確率を最大化するパラメータ $\theta$ を学習したいが、学習は損失を最小化するので、損失はこの確率の負の対数尤度で定義され

$\mathcal{L} = -\ln p(Y \mid X)$

これを最小化することで正解文字列の確率を最大化することができる。

動的計画法による効率的な周辺確率の計算

上で述べたように、損失を求めるには $p(Y\mid X) = \sum_{\pi} \prod_t y^t_{\pi_t}$、つまり「$Y$ に縮約される有効なアライメント」全部の確率を足す必要がある。しかしこの本数が入力長 $T$ に対して指数的に増える。

直感的には、長さ $U$ の文字列を長さ $T$ のフレーム列へ引き伸ばすとき、「どのフレームで同じ文字に留まり、どこで次の文字へ進み、どこに blank を挟むか」の組み合わせが膨大になる。フレームが1つ増えるごとに枝分かれが掛け算で効くので、本数はおよそ $T$ の指数オーダーになり計算量が膨大になる。

なので動的計画法のアルゴリズムを使い、効率的に損失を計算する。動的計画法は「大きな問題を、重なり合う小さな部分問題に分け、一度解いた部分問題の答えを保存して使い回す（メモ化する）」という汎用的な解法である。では動的計画法を使うとどのように計算が効率化されるのかをみていこう。

以下、分かりやすくするために正解文字列が $Y =$ cat（$U=3$）、入力が $T=6$ フレームの場合を例に進める。ここで計算過程を理解するために、まず $Y$ の前後と各文字の間に blank を挿入した、長さ $2U+1 = 7$ の拡張系列を作る： $Z = [\varnothing,\ c,\ \varnothing,\ a,\ \varnothing,\ t,\ \varnothing]$ 各文字の間に blank を挟んでおくのは、「重複文字の間には必ず blank が要る」規則と「文字の前後では blank を出しても出さなくてもよい」ことを、この後の格子の上で表現するため。

この $Z$ を縦軸、フレーム（$1$〜$6$）を横軸にとった格子を考えると、cat に縮約される1つの有効なアライメントは、格子の左上から右下へ向かう1本の単調な経路として描ける。例えば

• c c ε a t t（c に2フレーム、t に2フレーム使う）
• ε c a a a t（頭に無音、a を3フレーム伸ばす）

はどちらも縮約すると cat になる有効経路で、格子上の別々のルートに対応する。求めたい $p(\text{cat}\mid X)$ は、この格子上の全ルートの確率の総和である。

メモ化によって計算量が減る

格子をよく見ると、別々の経路が同じセル $(t, s)$ を通ることに気づく。たとえば「フレーム3までで a（$Z$ の $s=4$）まで到達している」というセル $(3, 4)$ には、

• c a a
• c c a
• ε c a
• c ε a

の4本の部分経路が集まる。それぞれの確率は異なるが、フレーム4以降の進み方はどの経路から来ても全く同じなので、この先の計算に必要なのは「ここまでの確率の合計」だけで、どの経路で来たかの内訳は要らない。

そこで、セル $(t, s)$ ごとにこの合計を1つの値として保存する。これが前向き変数 (forward variable) $\alpha_t(s)$ である。言葉で定義すると「フレーム $t$ までを使って、$Z$ の先頭から $s$ 番目までをちょうど説明し終えている、全部分経路の確率和」である。

上の例で書き下すと： $\alpha_3(4) = \underbrace{y^1_c\, y^2_a\, y^3_a}_{P(c\,a\,a)} + \underbrace{y^1_c\, y^2_c\, y^3_a}_{P(c\,c\,a)} + \underbrace{y^1_\varnothing\, y^2_c\, y^3_a}_{P(\varepsilon\,c\,a)} + \underbrace{y^1_c\, y^2_\varnothing\, y^3_a}_{P(c\,\varepsilon\,a)}$

つまり $\alpha_3(4)$ は4本の部分経路の確率の合計になる。以後はメモ化によりこの1つの数だけを使い回すので、同じ計算を経路の本数ぶん繰り返さずに済む。

ここでどれくらい計算が減るのか、このセル $(3, 4)$ を通る経路だけに絞って具体的に考えてみる。このセルを通る前半（フレーム1〜3）のアライメントは上の4本。そしてセルから先、残り3フレームで終端まで行くアライメントは10通りある。前半と後半は自由に組み合わせられるので、このセルを通る経路は全部で $4 \times 10 = 40$ 本になる。

メモ化を使わない場合は、この40本を1本ずつ独立に、6個の確率の積として計算する。たとえば前半が c a a の経路は10本あり、それぞれ

$\underbrace{(y^1_c\, y^2_a\, y^3_a)}_{\text{前半}} \times \underbrace{(y^4_a\, y^5_t\, y^6_t)}_{\text{後半その1}},\qquad \underbrace{(y^1_c\, y^2_a\, y^3_a)}_{\text{同じ前半}} \times \underbrace{(y^4_\varnothing\, y^5_t\, y^6_t)}_{\text{後半その2}},\qquad \dots$

と計算される。下線部に注目すると、同じ前半の積 $y^1_c y^2_a y^3_a$ が10本の経路に10回登場している。前半 c c a でも ε c a でも同じことが起き、前半の積は4種類しかないのに、それぞれが後半の数だけ（10回ずつ）ゼロから計算し直される。

しかし後半の確率は「前半までどの経路で来たか」に依存しない（条件付き独立と単調性のおかげ）ので、40本の確率の総和は分配法則（$ab + ac = a(b+c)$）により以下のように計算できる。

$\sum_{i=1}^{4}\sum_{j=1}^{10} P(\text{前半}_i)\, P(\text{後半}_j) = \underbrace{\Bigl(\sum_{i=1}^{4} P(\text{前半}_i)\Bigr)}_{=\ \alpha_3(4)\ \text{（メモ）}} \times \Bigl(\sum_{j=1}^{10} P(\text{後半}_j)\Bigr)$

つまりメモ化を使うことで、「前半4経路の和を1回だけ計算して保存（これが $\alpha_3(4)$）」、「後半10経路の和を1回計算」し、「最後に両者を1回掛ける」だけなので、前半の積を10回計算し直す必要が無くなる。

動的計画法はこれを、$(3, 4)$ というセルだけでなく格子の全セルで行うので計算量を大幅に減らすことができる。

具体的に各 $\alpha_t(s)$ をどう計算していくか

格子の全セルの値 $\alpha_t(s)$ を、フレーム $t=1$ の列から右へ、列ごとに順に計算していく。左隣の列の $\alpha$ はメモ化によりすべて計算済みなので、あるセル $\alpha_t(s)$ は「左隣の列のうち、そのセルへ入ってこられるいくつかの $\alpha$ を足し、今のフレームで $z_s$ を出す確率 $y^t_{z_s}$ を掛ける」だけで求まる。これを右端の列まで繰り返せば、そこから $p(Y\mid X)$ を計算することができる。

ここで、「どの $\alpha$ を足すか」は経路の取り得る動き方で決まる。単調性（留まるか次へ進むかのみ）から入口は最大3本に限られ、飛び先 $z_s$ のラベルで2つのケースに分かれる。

• Case 1：skip 不可（入口は2本）：$z_s = \varnothing$ のとき、または $z_s = z_{s-2}$（同じ文字の連続）のとき。たとえば $s=3$ の $\varnothing$ へは「$\varnothing$ に留まる」「c から進む」の2本だけ（blank を飛び越えて blank に入る経路は存在しない）。また、もし正解が egg のように同じ文字の連続を含むなら（$Z = [\varnothing, e, \varnothing, g, \varnothing, g, \varnothing]$）、2つ目の g（$s=6$）へ1つ目の g（$s=4$）から直接飛ぶことは許されない。直接繋ぐと縮約で1つの g に潰れてしまうので、間の blank を必ず経由させる必要があるからだ。よってこの場合は以下のように確率和が計算できる。 $\alpha_t(s) = \bigl(\alpha_{t-1}(s) + \alpha_{t-1}(s-1)\bigr)\, y^t_{z_s}$

• Case 2：skip 可（入口は3本）：$z_s$ が非blankで、かつ $z_{s-2}$ と別の文字のとき。cat の a（$s=4$）がこれにあたり、①同じ a に留まる、②直前の $\varnothing$（$s=3$）から進む、③その $\varnothing$ を飛び越えて c（$s=2$）から直接進む、の3本が入る。c と a は別文字なので、間に blank を挟まなくても縮約で潰れないので、飛び越しが許される。よってこの場合は以下のように確率和が計算できる。 $\alpha_t(s) = \bigl(\alpha_{t-1}(s) + \alpha_{t-1}(s-1) + \alpha_{t-1}(s-2)\bigr)\, y^t_{z_s}$

この2式は例示ではなくアルゴリズムそのもの（漸化式）であり、全セルがどちらかのルールで機械的に計算される。計算量は 状態数 × フレーム数、すなわち $O(T \cdot |Z|) = O(T \cdot U)$。cat の例なら $7 \times 6 = 42$ セルを埋めるだけで、全経路の総和が正確に求まる。

最終的な確率と学習

格子を右端まで埋めたら、$p(Y \mid X)$ は「$Z$ を最後まで説明し終えた」2状態、つまり最後の文字と末尾 blank の $\alpha_T$ の和として読み取れる。cat なら $p(\text{cat} \mid X) = \alpha_6(6) + \alpha_6(7)$ （$s=6$ が文字 t、$s=7$ が末尾の $\varnothing$）。同様に右下から左上へ埋める後ろ向き変数 $\beta_t(s)$ も計算すると、$\alpha$ と $\beta$ の積から各時刻・各ラベルの事後確率が求まり、そこから損失の勾配が解析的に得られる。前向き・後ろ向きの2方向を使うので forward-backward と呼ばれている。

実務イメージ：テンソルの形と擬似コード

実際のモデルでは、エンコーダの出力に線形層を1枚載せたものがCTC headで、その出力テンソルは

logits: [B, T, V+1]   # B=バッチ, T=フレーム数, V=語彙数, +1 が blank

という形をしている。ここから損失までの流れを1サンプル分の擬似コードで書くと以下の通り。なお $T$ 個の確率（すべて1未満）の積はすぐ数値アンダーフローするので、実装は必ず log 領域で行い、積は足し算、和は logsumexp に置き換える。

### あくまで理解を促進するためのpseudo code
log_probs = log_softmax(logits, dim=-1)      # [T, V+1]

Z = insert_blanks(target)     # "cat" → [ε, c, ε, a, ε, t, ε], 長さ S = 2U+1
alpha = full((T, S), -inf)    # log領域の格子

# 初期化: 経路は先頭の ε か最初の文字からしか始まれない
alpha[0, 0] = log_probs[0, blank]
alpha[0, 1] = log_probs[0, Z[1]]

for t in range(1, T):                                  # 列を左から右へ
    for s in range(S):                                 # 各セルを埋める
        acc = logsumexp(alpha[t-1, s], alpha[t-1, s-1])        # Case 1
        if Z[s] != blank and Z[s] != Z[s-2]:                   # Case 2
            acc = logsumexp(acc, alpha[t-1, s-2])
        alpha[t, s] = acc + log_probs[t, Z[s]]

log_p = logsumexp(alpha[T-1, S-1], alpha[T-1, S-2])   # 末尾 ε と最後の文字
loss = -log_p

実務ではこれを自分で書くことはなく、torch.nn.CTCLoss（F.ctc_loss）に log_probs [T, B, V+1]・ターゲット列・各系列の長さ（input_lengths, target_lengths）を渡せば、この forward 計算から勾配（backward）までを一括で行ってくれる。

CTCの重要な性質を再度まとめておく

• 条件付き独立：出力どうしは $X$ が与えられれば独立と仮定される。A を予測したら次も A が来やすい、といった出力間の言語的依存をモデル内部で持たない。
• 単調アラインメント：左→右の単調な経路のみ。音声・手書き認識には自然だが、語順が入れ替わる機械翻訳には使えない。
• many-to-one：複数のインプットが1つのアウトプットに帰結する。

推論時におけるDecoding

ここからは推論時におけるDecodingを考える。学習で得られた $p(Y \mid X)$ をもとに、推論では $\hat{Y} = \arg\max_Y p(Y \mid X)$ をとる。しかし、各候補 $Y$ について経路を周辺化する必要があり厳密に最も確率の高い文字列を厳密に探索するには計算量が膨大になり、Decoding時はこの探索を近似的に解くことで解決している。

Greedy decoding

Greedyは実務でよく使われているDecoding手法であり、各フレームで最も確率の高いトークンを選んで1本の経路 $\pi^\ast$ を作り、縮約 $\mathcal{B}$ をとる： $\hat{Y} = \mathcal{B}(\pi^\ast), \qquad \pi^\ast_t = \arg\max_{k \in L'} y^t_k$ たとえば各フレームの argmax が c c ε a ε t なら、縮約して出力は cat。実装は「argmax → 連続する重複をまとめる → blank を除く」だけで、計算量は $O(T)$。

ただし厳密には近似である。greedy が選んでいるのは「最も確率の高い1本の経路」であり（条件付き独立のおかげで、フレームごとの argmax がそのまま最良経路になる）、それを縮約した文字列を返しているに過ぎない。しかし本当に欲しいのは「最も確率の高い文字列」で、文字列の確率はそれに縮約される全経路の確率の和で決まる。最良経路を1本見ても和の大小は分からないので、両者は一致するとは限らない。

具体例として、$T=2$、語彙 $\{a, \varnothing\}$ で、各フレームとも $p(a) = 0.4,\ p(\varnothing) = 0.6$ とする。最良経路は ε ε（$0.36$）なので greedy の出力は空文字列。しかし文字列 a の確率は a a + a ε + ε a $= 0.16 + 0.24 + 0.24 = 0.64$ で、空文字列（$0.36$）の倍近く高い。このように、個々の経路としては弱くても、多数の経路が同じ文字列に集まって合計で勝つケースを greedy は取りこぼす。

それでも現代の実務では greedy が主流である。近年の強いエンコーダではCTCの事後分布が非常に確信的（peaky）になり、beam search との精度差が小さくなったため、速度と単純さで greedy が選ばれる。実際、NVIDIA NeMo や HuggingFace のCTCパイプラインのデフォルトは greedy である。

Prefix beam search

Prefix beam searchは外部のLMを統合するときによく使われるDecoding手法である。greedy が無視した「和」を、ビームの中で正しく計算しながら探索する方法。経路ではなく文字列（prefix ＝ 縮約後の作りかけの文字列）を単位に、フレームを進めながら有望な prefix をビーム幅ぶんだけ残していく。

CTC特有の工夫は、各 prefix の確率を2つに分けて持つこと。

• $p_b(\ell)$：prefix $\ell$ に縮約され、末尾が blank で終わる全経路の確率和
• $p_{nb}(\ell)$：prefix $\ell$ に縮約され、末尾が $\ell$ の最後の文字で終わる全経路の確率和

なぜ分ける必要があるのか、prefix a を例に具体的に見る。フレーム $t$ の時点で prefix が a ということは、「ここまでの出力を縮約すると a になる経路」たちがこの prefix に束ねられているということ。その中には、たとえば

• 末尾が文字で終わる経路：a、ε a、a a（どれも縮約すると a）
• 末尾が blank で終わる経路：a ε、ε a ε（これらも縮約すると a）

の2グループが混ざっている。ここで次のフレームでモデルが a を出したとする。各経路の行き先を追うと：

• a ε ＋ a → a ε a → 縮約すると aa。blank が区切りとして働くので、新しい2文字目の a になる。
• a a ＋ a → a a a → 縮約すると a のまま。区切りがないので、重複としてまとめられる。

つまり同じ prefix a に同じ文字 a を足したのに、経路の末尾次第で行き先が aa と a に分かれる。これらの理由から各 prefix の確率を伝うに分けて持っておく。

フレームごとの計算の更新は以下の3つにまとまる：

• 「blank を出す → $p_b$ へ集める」
• 「末尾と同じ文字を出す → $p_{nb}$ 側は重複としてまとめ、$p_b$ 側からだけ prefix を伸ばす」
• 「別の文字を出す → 両方の predix を伸ばす」

各フレーム後に $p_b + p_{nb}$ の上位 (beam size) だけ残して枝刈りし、最後に最大の prefix を出力する。

また prefix は blank と重複を畳んだテキストそのものなので、外部LMがそのまま条件付けでき、prefix が1文字伸びるごとに $p_{LM}$ を掛けて累積できる。よって外部LMを組み込んだDecodingでは Prefix beam search を使うことが多い。

References

• Graves, Fernández, Gomez, Schmidhuber, “Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks”, ICML 2006
• Hannun, “Sequence Modeling with CTC”, Distill, 2017（https://distill.pub/2017/ctc/）

---

RNN-T (RNN Transducer)

モチベーション：CTCの条件付き独立を外す

CTCの最大の制約は条件付き独立、すなわち各フレームの出力が「過去に何を出したか」に一切依存しないことだった。このためCTCは「q の次は u が来やすい」のような出力間の言語的な依存（内部言語モデル）をモデル内部に持てない。RNN-T（Graves, 2012）はこの制約を外すために設計された出力ヘッドで、過去に出力したラベル列に条件づけながら、CTCと同じく全アライメントを周辺化して学習する。

もう1つの実務的な動機はストリーミングである。エンコーダを causal（未来のフレームを見ない構造）にすれば、RNN-Tは音声を左から右へ読みながら逐次テキストを出力できる。このためモバイル・リアルタイム認識の実運用で標準的な選択肢になった（He et al., 2019）。

**CTCモデルがストリーミングに対応できないということではないです。昔の LAS (Listen, Attend, Spell) のような seq2seq モデルが ストリーミングに対応できないということがコンテキストにあります。

アーキテクチャ

RNN-Tは3つのコンポーネントからなる。

• Encoder：音声フレーム列を受け取り、フレームごとの表現 $f_t$ を出す。CTCなどで使われるエンコーダと同じ役割。
• Prediction network：これまでに出力した非blankラベル列 $y_1, \dots, y_u$ だけを受け取り、表現 $g_u$ を出す。音声を一切見ないので、実体は「ラベル列上の言語モデル」である。RNN-Tが内部言語モデルを持つのはこのネットワークのおかげ。
• Joint network：$f_t$ と $g_u$ を結合して、語彙＋blank 上の分布を出す： $P(k \mid t, u) = \mathrm{softmax}\bigl(W\, \sigma(W_f f_t + W_g g_u)\bigr)_k, \qquad k \in L \cup \{\varnothing\}$ ここで $\sigma$ は非線形の活性化関数。

$P(k \mid t, u)$ の意味は「フレーム $t$ まで聞き、すでに $u$ 個のラベルを出した状態で、次に $k$ を出す確率」。CTCの $y^t$ が $t$ だけに依存したのに対し、$u$（＝これまで何を出したか）にも依存する。これが「条件付き独立を外した」の具体的な中身である。

RNN-Tのアライメント

RNN-Tにも blank $\varepsilon$ があるが、役割がCTCと違う。CTCの blank は「無出力＋重複の区切り」だったのに対し、RNN-Tの blank は「このフレームからはもう出さない、次のフレームへ進め」というフレーム送りの合図である。

この違いにより、RNN-Tのアライメントは $T \times U$ の格子上の経路として描ける。cat（$U=3$）を $T=4$ フレームで認識する例：

• 右移動（→）：$\varepsilon$ を出してフレームを1つ進める（$t \mathrel{+}= 1$）
• 上移動（↑）：ラベルを1つ出す（$u \mathrel{+}= 1$）。フレームは進まない

経路は左下 $(1, 0)$ から出発し、右移動 $T-1$ 回と上移動 $U$ 回、最後に終端の $\varepsilon$ を出して右上 $(T, U)$ で終わる（経路長は常に $T+U$）。緑の経路のように上移動を連続させれば、1フレームから複数ラベルを出せる。

この構造から、以下のようなCTCとの差が生まれる。

• 1フレーム1トークンの縛りがないので、出力長の制約 $U \le T$ が消える
• 重複文字に blank の区切りが要らない（ll は上移動2連続でよい）ので、確率計算時においてCTCの Case 1/2 のような場合分けが消える
• アライメントの長さは常に $T+U$（CTCは $T$）

Loss関数の定義と確率の計算方法

アライメント $\bar{a}$（格子上の1本の経路）の確率は、各ステップの確率の積： $p(\bar{a} \mid X) = \prod_{(t,u) \in \bar{a}} P(k_{t,u} \mid t, u)$ そして文字列 $Y$ の確率は、CTCと全く同じく、$Y$ に対応する全経路の周辺化（和）であり、損失はCTCと同じく確率の負の対数尤度となる： $p(Y \mid X) = \sum_{\bar{a}} p(\bar{a} \mid X), \qquad \mathcal{L} = -\ln p(Y \mid X)$ ここで、正解の文字列が cat（$U=3$）でフレーム長が $T=4$ なら、経路は全部で20本になる。数え方は以下の通り。

格子の左下 $(1,0)$ から右上 $(T,U)$ まで行くには、どの経路も右移動（$\varepsilon$）を $T-1=3$ 回、上移動（文字を出す）を $U=3$ 回、計6回の移動が必要で、経路ごとに違うのはその順番だけである。たとえば

• 上上上右右右 → c a t ε ε ε（フレーム1で3文字全部出す）
• 上右上右上右 → c ε a ε t ε（1フレームに1文字ずつ）
• 右右右上上上 → ε ε ε c a t（最後のフレームで3文字全部出す）

つまり経路を1本決めることは「6回の移動のうち、どの3回を上移動にするか」を選ぶことと同じなので、経路数は組み合わせの数（二項係数）で書ける：

$\binom{(T-1)+U}{U} = \binom{6}{3} = {}_6\mathrm{C}_3 = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$

終端の $\varepsilon$ は全経路が最後に共通で1回出すので数え上げには含めない。

この経路数は $T, U$ が大きくなれば爆発的に増えるので、CTCと同様に動的計画法で和を計算する。

ここで、$P(k \mid t, u)$ は過去の予測ラベル $y_1, \dots, y_u$ だけに依存し、それをどのタイミングで出したか（経路の形）には依存しないのでCTC同様に動的計画法のメモ化を使って効率的に確率の計算を行うことができる。セル $(t, u)$ に到達した時点で過去の予測ラベルは $y_1, \dots, y_u$ に確定しているので、「$(t,u)$ に至る全部分経路の確率和」を1つの値にまとめることができる。

そこで前向き変数を $\alpha(t, u)$（フレーム $t$ まで消費し、ラベルを $u$ 個出し終えた全部分経路の確率和）と置くと、漸化式は： $\alpha(t, u) = \alpha(t-1, u)\, b(t-1, u) + \alpha(t, u-1)\, \hat{y}(t, u-1)$ ここで $b(t,u) = P(\varepsilon \mid t, u)$（blankを出す確率）、$\hat{y}(t,u) = P(y_{u+1} \mid t, u)$（正解の次のラベルを出す確率）。

入口は「左から（$\varepsilon$ でフレームを進めてきた）」と「下から（ラベルを出してきた）」の常に2本だけ。blank が区切りの役割を持たないため、CTCにあった skip の場合分けは存在せず、漸化式はCTCより単純になる。最終的な確率は、右上のセルで終端の $\varepsilon$ を出して： $p(Y \mid X) = \alpha(T, U)\, b(T, U)$ 計算量はセル数に比例して $O(T \cdot U)$。後ろ向き変数 $\beta$ も合わせて勾配を解析的に得るのは、CTCの forward-backward と同じ。

実装イメージ：テンソルの形とメモリ問題

f = encoder(x)         # [B, T, D]
g = pred_net(y_prev)   # [B, U+1, D]     (先頭に <s> を足すので U+1)
logits = joint(f, g)   # [B, T, U+1, V+1] ← ここが問題
loss = rnnt_loss(logits, y, T_lens, U_lens)   # torchaudio.functional.rnnt_loss など

CTCの logits が [B, T, V+1] の3次元だったのに対し、RNN-Tの joint 出力は格子の全セルで分布を持つ4次元テンソルになる。つまり、CTCに比べて損失計算が格段にメモリーインテンシブになる。

これらの問題には以下のような解決策が実装されている。

• Pruned RNN-T（Kuang et al., Interspeech 2022）：各 $t$ で $u$ の範囲を幅 $S$（4〜5程度）のバンドに制限し、[B, T, S, V+1] に削減する。k2 / icefallエコシステムの標準

• Fused joint / バッチ分割：NeMo のアプローチ。バッチ $B$ をサイズ $b$ のサブバッチ（NeMoの fused_batch_size、たとえば $b=4$）に割り、サブバッチ単位で

  1. $f, g$ のスライスから joint を計算（logits は [b, T', U'+1, V+1] だけ作る。$T', U'$ はサブバッチ内の最大長に切り詰めるので、パディングの無駄も減る）
  2. その場で loss（と勾配）まで計算して損失値に集約
  3. サブバッチの logits を捨ててから次のサブバッチへ

  と進める。joint と loss の計算を1ステップに「融合（fuse）」するのが名前の由来。ピークメモリは [B,...] から [b,...] になり $B/b$ 倍に減る。代償はサブバッチの逐次ループによる速度低下。

CTCとの対比まとめ

	CTC	RNN-T
出力間の依存	なし（条件付き独立）	あり（prediction network が $y_{<u}$ に条件づけ）
内部言語モデル	持たない	持つ
blank の役割	無出力＋重複の区切り	フレーム送り
アライメント長	$T$（フレーム同期）	$T+U$（格子上の階段）
出力長の制約	$U \le T$	なし（1タイムステップに複数ラベルを出力できる）
漸化式の入口	2〜3本（Case 1/2）	常に2本
学習時の logits	[B, T, V+1]	[B, T, U+1, V+1]（4D、メモリ対策が必要）

どちらも「全アライメントを forward-backward で周辺化する」枠組みは同じで、違いは「各ステップの確率が何に条件づくか」と「アライメントの格子の張り方」である。

推論時におけるDecoding

Greedy decoding

RNN-Tのgreedyは、格子を左下からGreedyにたどることに相当する：

t, u = 1, 0
while t <= T:
    k = argmax_k P(k | t, u)
    if k == ε:  t += 1            # 次のフレームへ
    else:       出力に k を追加; u += 1   # 同じフレームで続けて出せる

CTCのgreedyとの違いが2つある。まず、ラベルを出すたびに prediction network の状態が更新されるので、フレームごとの判断が独立ではない。また blank が区切りではないので縮約処理が不要で、出したラベルがそのまま出力になる。causal なエンコーダと組み合わせれば、このループがそのままストリーミング認識になる。

Beam search

複数の候補ラベル列を保持しながら格子を進める（Graves, 2012）。同じラベル列に到達した仮説のスコアを合算する点は、CTCの prefix beam search と同じ発想。

ただし実務でのbeam searchの位置づけは限定的である。整理すると：

• LMなしの素のbeam search の利得は、greedy に対して小さい。これは現代の強いモデルではCTCでも同様（greedy の節で述べた通り）で、RNN-T特有の話ではない
• 一方、RNN-Tの素朴なbeam searchは、ラベルを出すたびに prediction network を評価し直す必要があり計算コストが重い。このため ALSD（alignment-length synchronous decoding）や mAES などの高速化変種が発達した
• 実際、NeMoのRNN-Tデコードのデフォルトは greedy_batch である。

なお外部LM統合について、CTCとの重要な非対称がある。CTCは内部LMを持たないため外部LM（shallow fusion）の利得が大きかったが、RNN-Tは prediction network が既に言語的な事前分布を担っているため、外部LMの上積みは相対的に小さい。さらに外部LMを足すと内部LMと二重に言語バイアスがかかるため、内部LMの寄与を推定して差し引く補正（ILME: internal language model estimation）が研究されていたりする。ドメイン適応で外部LMを本格的に使う時などに応用できる。

補足：推論時のタイムスタンプ出力

字幕生成などで必要になる単語タイムスタンプは、RNN-Tでは次のように得る（NeMoの実装ベース）。

• 仕組み：デコードのループ中、非blankラベルを出した時のフレーム番号 $t$ を記録する。
• ラベルの長さ：NeMoは各非blankトークンに {start_offset: s, end_offset: s+1} を与える。つまりRNN-Tのトークンは持続時間を持たない点イベントとして記録され、幅は形式的に1フレームしかない。
• 単語への集約：トークンのオフセットを単語区切りでまとめ、単語の開始＝先頭トークンのフレーム、終了＝末尾トークンのフレーム＋1、として出力される。
• 秒への変換：フレーム番号 × エンコーダのフレームシフト（例：特徴量10msシフト × subsampling 8倍 = 80ms/フレーム）。

ただしRNN-Tは1フレームに複数ラベルが出力可能なので、emission delay という課題が存在する。これは一定程度音声を聞いてからラベルを出力する挙動で、出力に遅れが生じることがあることに留意しておく。正確な時刻が必要な用途では、アライメントの外部モデルを使ったり(forced alignment など) 、duration を明示的に予測するモデルを使うのが実務的な選択になる。

References

• Graves, “Sequence Transduction with Recurrent Neural Networks”, ICML Workshop 2012
• Graves, Mohamed, Hinton, “Speech Recognition with Deep Recurrent Neural Networks”, ICASSP 2013
• He et al., “Streaming End-to-end Speech Recognition for Mobile Devices”, ICASSP 2019
• Ghodsi et al., “RNN-Transducer with Stateless Prediction Network”, ICASSP 2020
• Kuang et al., “Pruned RNN-T for Fast, Memory-efficient ASR Training”, Interspeech 2022
• Saon, Tüske, Audhkhasi, “Alignment-Length Synchronous Decoding for RNN Transducer”, ICASSP 2020（ALSD）
• Kim, Lee, Kim, “Accelerating RNN Transducer Inference via Adaptive Expansion Search”, IEEE Signal Processing Letters 2020（mAES）
• Meng et al., “Internal Language Model Estimation for Domain-Adaptive End-to-End Speech Recognition”, SLT 2021（ILME）

---

TDT (Token-and-Duration Transducer)

モチベーション

前段で述べたようにRNN-Tは構造的に時間方向の前進が常に1フレームずつであり効率が悪い。右移動は必ず $\varepsilon$ を1個伴うので、たとえば長い無音区間では、出力すべきものが何もないのに $\varepsilon$ をフレーム数ぶん延々と出し続けることになる。デコードの判断回数は常に $T+U$ 回で、長い音声では $T$ がより長いので、つまり推論のほとんどが「$\varepsilon$ を出すだけ」という挙動になる。

また前章の最後で見たように、RNN-Tのトークンは持続時間を持たない点イベントで、タイムスタンプは幅1フレーム固定という構造的な欠落もあった。

TDT（Xu et al., ICML 2023, NVIDIA）はこの2つを同時に解決する。コアアイデアは「トークンを出すとき、次の判断まで何フレーム進むか（duration）も一緒に予測する」ということ。予測した $d$ を使ってフレームを一気にスキップできるため速く、$d$ がそのままトークンの持続時間情報にもなる。

なお先行研究として、blank だけに複数フレーム送りを許す multi-blank transducer（Xu et al., ICASSP 2023）があり、TDTはそれを全トークンに一般化したものと位置づけられる。

アーキテクチャ

Encoder / Prediction network / Joint の3部品構成はRNN-Tと全く同じ。違いは Joint の出力が2つのヘッドに分かれることだけである。

• トークンヘッド：$P_T(k \mid t, u)$、$k \in L \cup \{\varepsilon\}$。RNN-Tと同じ
• durationヘッド：$P_D(d \mid t, u)$、$d \in \{0, 1, \dots, D_{\max}\}$。進み幅の分布。$D_{\max}$ はハイパーパラメータで（NeMoのdefaultは $\{0,1,2,3,4\}$）

2つのヘッドは同じ joint 表現からそれぞれ独立に正規化され（トークンと duration の条件付き独立を仮定）、1ステップの出力は組 $(k, d)$ の確率になる： $P(k, d \mid t, u) = P_T(k \mid t, u) \cdot P_D(d \mid t, u)$

実装上は2本のヘッドを別々に持つのではなく、joint の最終線形層が $V{+}1{+}|D|$ 次元の1本のテンソルを出し、最終次元を「先頭 $V{+}1$（トークン）／末尾 $|D|$（duration）」にスライスしてそれぞれ別々に softmax する。

TDTのアライメント

1ステップの意味は「$k$ を出して、$d$ フレーム進む」である。

• $k$ が非blank：$u \mathrel{+}= 1$、$t \mathrel{+}= d$（$d=0$ なら同じフレームでもう1トークン出せる）
• $k$ がblank: $t \mathrel{+}= d$（何も出さずに $d$ フレームまとめてスキップ。長い無音を一足で飛ばせる）

図は cat（$T=6, U=3$）を (c, d=1) → (a, d=0) → (ε, d=3) → (t, d=1) の例。トークン付きの移動は斜め（上＋右）、$\varepsilon$ の大きなジャンプは長い横矢印になる。RNN-Tなら同じ設定で必ず $T+U = 9$ 回の判断が要るところ、スキップのぶん推論回数が減っている。

この見方をすると、RNN-Tは「トークンは常に $d=0$、blank は常に $d=1$」に固定したTDTの特殊ケースと言える。TDTはその固定を外し、進み幅そのものを予測に置き換えた一般化である。

またRNN-T同様、$(\varepsilon, d=0)$ は「何も出さずその場に留まる」ことになり無限ループするので許されない（実装では blank のとき $d \ge 1$ を強制するガードが入る）。

Loss

確率の構造はRNN-Tと同じである。まずアライメント $\bar{a}$ は $(k, d)$ の組の列であり、その確率は各ステップの「トークン確率 × duration確率」の積： $p(\bar{a} \mid X) = \prod_{i} P_T(k_i \mid t_i, u_i)\, P_D(d_i \mid t_i, u_i)$ ここで $(t_i, u_i)$ は $i$ 番目の判断を行った時点のセル位置で、それまでの $d$ の累積（$t$ 方向）と非blankの回数（$u$ 方向）で決まる。有効なアライメントの条件は「非blank をちょうど $U$ 回出す」「$d$ の合計が $T$ に達して右端を抜ける」こと。

そして文字列 $Y$ の確率は全ての有効なアライメントの周辺化（和）で、損失はその負の対数尤度： $p(Y \mid X) = \sum_{\bar{a}} p(\bar{a} \mid X), \qquad \mathcal{L} = -\ln p(Y \mid X)$

この和もRNN-Tと同じく、前向き変数 $\alpha(t, u)$（定義はRNN-Tと同一：フレーム $t$ まで消費し、ラベルを $u$ 個出し終えた全部分経路の確率和）の動的計画法で計算する。漸化式は、入口を「blank で入ってくる」「トークン $y_u$ で入ってくる」の2種類 × duration の選択肢ぶん足し合わせる形になる。

RNN-Tと同じく $b(t,u) = P_T(\varepsilon \mid t,u)$、$\hat{y}(t,u) = P_T(y_{u+1} \mid t,u)$ と置くと： $\alpha(t, u) = \sum_{d \in \mathcal{D} \setminus \{0\}} \alpha(t{-}d, u)\; b(t{-}d, u)\; P_D(d \mid t{-}d, u) \;+\; \sum_{d \in \mathcal{D}} \alpha(t{-}d, u{-}1)\; \hat{y}(t{-}d, u{-}1)\; P_D(d \mid t{-}d, u{-}1)$

• 第1項（blank で入る）：$d$ フレーム左の同じ行のセルから。$(\varepsilon, d=0)$ は禁止なので、和は $\mathcal{D} \setminus \{0\}$ の上で取る
• 第2項（トークンで入る）：$d$ フレーム左の1つ下の行のセルから。こちらは $d=0$ も許され、その場合は「同じ列の1つ下」つまりRNN-Tの垂直の入口とまったく同じものになる

具体的に $\mathcal{D} = \{0, 1, 2\}$ でセル $(4, 2)$ への入口を数えると、blank 側が $(3,2), (2,2)$ からの2本（$d = 1, 2$）、トークン側が $(4,1), (3,1), (2,1)$ からの3本（$d = 0, 1, 2$）で計5本。一般化すると入口は最大 $2|\mathcal{D}| - 1$ となる。

終端はRNN-Tの $\alpha(T, U)\, b(T, U)$ に対応する処理を duration 付きで行う。後ろ向き変数 $\beta$ と合わせて勾配を解析的に得る forward-backward の枠組みも同じ。計算量はセル数 × 入口数で $O(T \cdot U \cdot |\mathcal{D}|)$ となるが、$|\mathcal{D}|$ は5程度の小さい定数なので、RNN-T比での追加負担はそこまで大きくない。

Decoding

t, u = 1, 0
while t <= T:
    k = argmax P_T(k | t, u)
    d = argmax P_D(d | t, u)
    if k != ε: 出力に k を追加; u += 1
    t += d        # ← RNN-T との唯一の違い。d フレーム一気に進む

RNN-Tのgreedyとの違いは実質 t += d の1行だけ。論文では従来のTransducer比で最大2.82倍の推論高速化（精度は同等以上）が報告されている。注意点として、スキップで減るのはデコーダ側（joint + prediction network）の推論回数であり、エンコーダは全フレームを計算する。

タイムスタンプについては前章で見た通り、トークンオフセットが end_offset = start + d となり、予測した duration がそのまま幅になる。

References

• Xu, Jia, Majumdar, Huang, Watanabe, Ginsburg, “Efficient Sequence Transduction by Jointly Predicting Tokens and Durations”, ICML 2023
• Xu et al., “Multi-blank Transducers for Speech Recognition”, ICASSP 2023

---

AED (Attention-based Encoder Decoder)

モチベーション

これまでの3つのヘッド（CTC / RNN-T / TDT）は、いずれも「アライメントを潜在変数として導入し、全パターンを周辺化する」枠組みだった。blank を設計し、格子を張り、forward-backward で和を計算する。これらは、フレームとラベルの対応が未知である問題を明示的に解くためのものだった。

一方でAED はアライメントを明示的にモデル化することはせず、デコーダがテキストを言語モデルのように1トークンずつ自己回帰生成し、各ステップでcross-attention を通じて暗黙的にアライメントを勝手に学習する。

よって出力ラベル列の確率は連鎖律で定義できる： $p(Y \mid X) = \prod_{u=1}^{U+1} p(y_u \mid y_{<u},\, X)$ ここで $y_{U+1}$ は終了トークン EOT（end of text）で、blank も格子も周辺化も登場しない。

系譜としては、Attention を音声認識に持ち込んだ Chorowski et al.（2015）、LAS（Listen, Attend and Spell; Chan et al., 2016）を経てTransformer化が進み、現在の代表がOpenAIが出している Whisper（Radford et al., ICML 2023）である（基本的にLLMベースのASRモデルはこの形）。

アーキテクチャ

ここではWhisperのアーキテクチャを見る。EncoderとDecoderから構成され、Encoderの出力がcross-attentionを通じてDecoderに渡される形。基本的にはAttention is All You Needで提案されたTransformer と同じ構造である。

Loss

周辺化が存在しないので、損失は言語モデルと同様に連鎖律の各因子の負の対数尤度、つまり次トークン予測のクロスエントロピーの和で定義される： $\mathcal{L} = -\sum_{u=1}^{U+1} \ln p(y_u \mid y_{<u},\, X)$

学習は LLM の next token prediction と同じである。正解の接頭辞 $y_{<u}$ をデコーダに与えて次のトークンを当てさせる形にすると、causal mask を使って全位置を並列に計算できる。

Whisper では文字ラベルの予測だけでなく、言語ID・タスク指定（書き起こし / 翻訳）・タイムスタンプもすべて特殊トークンとして扱い、next token predictionで学習させている。書き起こし・翻訳・言語識別・時刻予測が全部「トークン列の生成」という同一の問題になり、1つのデコーダと1つのLossで完結する。

Decoding

LLM 同様、SOT（start of transcript）から始めて EOT が出るまで1トークンずつ。Autoregressive におけるデコーダーの推論回数は $U+1$ 回で、**$T$ に依存しない。

Greedy / Beam search

各ステップで argmax を取るか、複数仮説を保持するビームサーチを行う。CTC prefix beam search のような $p_b / p_{nb}$ の複雑な合算が不要でアライメントの周辺化が探索を複雑にしていたこれまでと対照的である。

References

• Chorowski et al., “Attention-Based Models for Speech Recognition”, NeurIPS 2015
• Chan, Jaitly, Le, Vinyals, “Listen, Attend and Spell: A Neural Network for Large Vocabulary Conversational Speech Recognition”, ICASSP 2016
• Watanabe et al., “Hybrid CTC/Attention Architecture for End-to-End Speech Recognition”, IEEE JSTSP 2017
• Radford et al., “Robust Speech Recognition via Large-Scale Weak Supervision”（Whisper）, ICML 2023

推論Headの対比まとめ

	CTC	RNN-T	TDT	AED
アライメント	離散経路を周辺化	離散経路を周辺化	離散経路＋durationを周辺化	明示的に扱わない（cross-attentionが暗黙的に学習）
Loss の計算	forward-backward	forward-backward	forward-backward	クロスエントロピーのみ
出力間の依存（内部LM）	なし	あり	あり	あり（decoder self-attention）
出力長の決め方	$U \le T$（構造的）	blank で終端	blank＋duration で終端	EOT の予測（学習任せ）
デコードステップ数	$T$	$T+U$	$T+U$ 未満（スキップ）	$U+1$（$T$ に依存しない）
代表モデル	wav2vec 2.0, Conformer-CTC	Parakeet-RNN-T	Parakeet-TDT	Whisper