# CTC誤差関数

原論文：https://www.cs.toronto.edu/~graves/icml_2006.pdf
参考テキスト：https://www.cs.toronto.edu/~graves/preprint.pdf

## 表記

原論文に準拠。

$U$: 正解ラベル長
$T$: 入力長（音響特徴量の時間フレーム数）。なお、$U\le T$ でなければいけない。
$L$: ラベルに使われる文字の集合
$L'=L\cup \{\mbox{blank}\}$: ブランクを含むラベルの文字集合
$L^{\le T}$: $T$ 以下の、$L$ の要素からなる列
$N=\{1, \dots, |L|\}$: ラベルに用いられる文字の番号の集合
$\boldsymbol{x} = (x_1, \dots , x_T) \in (\mathbb{R}^m)^T$: 音響特徴量。$m$ は特徴量の次元。 $m$ 次元対数メルスペクトルなど。
$\boldsymbol{z} = (z_1, \dots , z_U) \in L^U$: 正解ラベル列
$\boldsymbol{l}$: ブランクを含まないラベル列の例
$\boldsymbol{l}'$: ラベル列 $\boldsymbol{l}$ の両端と各ラベルの間にブランクを追加したブランク入りラベル列。$|\boldsymbol{l}'|=2|\boldsymbol{l}|+1$
$S$: データセット。$(\boldsymbol{x}, \boldsymbol{z})$ の組の集合
$h:X \mapsto Z$: 音声認識システム（temporal classifier）。音響特徴量から正解（だと思う）ラベル列を出力する。TODO: X, Z の定義
$\mathcal{N}_w: (\mathbb{R}^m)^T \mapsto (\mathbb{R}^n)^T$: 音響モデル（$n=|L|+1$）。ニューラルネットワークである。$w$ は重みパラメータのつもり。
$\boldsymbol{y} \in (\mathbb{R}^n)^T$: 音響モデル出力。 $\boldsymbol{y}=\mathcal{N}_w(\boldsymbol{x})$。時刻の添字は右上に付く（ $y^t$ が時刻 $t$ における出力）。TODO: $n$ の定義（|L|+1(blank)）。
$y_k^t$: 時刻 $t$ におけるラベル $k$ の確率
$\pi \in L'^T$: ブランクを含む縮約前ラベル列の例
$\mathcal{B}: L'^T \mapsto L^{\le T}$: CTC の縮約規則に従う縮約関数。ブランクがなくなる。逆関数は $\mathcal{B}^{-1}$ だがこちらは一対多になる。
$\boldsymbol{p}_{q:r}$: 系列 $p$ の $q$ 番目から $r$ 番目までの連続部分列

## 準備

入力 $\boldsymbol{x}$ における、ブランクを含むラベル列 $\pi$ の実現確率は

$$P(\pi | \boldsymbol{x})=\prod_{t=1}^T y_{\pi_t}^t$$

となる。縮約関数を考慮すると、縮約後のラベル列 $\boldsymbol{l}$ の実現確率は

$$P(\boldsymbol{l} | \boldsymbol{x})=\sum_{\pi \in \mathcal{B}^{-1}(\boldsymbol{l})}P(\pi | \boldsymbol{x})$$

となる。

音声認識システム $h$ は、入力の音響特徴量からもっとも実現されやすいラベル列を返す関数である。すなわち、

$$h(\boldsymbol{x})=\arg \max_{\boldsymbol{l}\in L^{\le T}}P(\boldsymbol{l} | \boldsymbol{x})$$

と表現される。

（式(4)省略）

$P(\boldsymbol{l} | \boldsymbol{x})$ を計算したい。そのために、以下のようなオートマトンを考える。

（オートマトンの説明）

これを時間方向に展開すると、以下のようなグラフになる。

（グラフの図）

このグラフにおいて、始点から終点まで移動する確率が $P(\pi | \boldsymbol{x})$ となる。これは DP で計算できる。

また、始点から頂点 $(s, t)$ に到達する確率を $\alpha_t(s|\boldsymbol{l})$、逆向きに見たときに終点から頂点 $(s, t)$ に到達する確率を $\beta_t(s|\boldsymbol{l})$ とする。これらは前から・後ろからの DP で計算できる。

これを用いると、任意の時刻 $t$ に対して、以下の等式が成り立つ。

$$P(\boldsymbol{l} | \boldsymbol{x})=\sum_{s=1}^{|\boldsymbol{l}'|}\frac{\alpha_t(s|\boldsymbol{l})\beta_t(s|\boldsymbol{l})}{y_{\boldsymbol{l}_s'}^t}$$

この等式は、「始点から終点まで移動する」という事象を「始点から終点まで、頂点 $(1, t)$ を通って移動する」「……頂点 $(2, t)$ を通って……」……という排反な事象に分割し、確率の和の法則を適用して得られる。なお、グラフの辺ではなく頂点に確率が設定されているため、$\alpha_t(s|\boldsymbol{l})\beta_t(s|\boldsymbol{l})$ だと $y_{\boldsymbol{l}_s'}^t$ が 2 回掛けられることに注意（辺に確率を設定する場合は、頂点 $(s, t)$ に前から・後ろから入る確率が両方 $y_{\boldsymbol{l}_s'}^t$ になっている）。

勾配降下法による学習のために、これを音響モデル出力 $y_k^t$ で微分したい。このとき、$\boldsymbol{l}'_s=k$ となる $s$ のみ考慮すればよい。そのような $s$ の集合を $lab(\boldsymbol{l},k)$ と書く。

また、$\alpha_t(s|\boldsymbol{l}), \beta_t(s|\boldsymbol{l})$ の漸化式を考えると、それぞれ 「$y_{\boldsymbol{l}'_s}^k$ によらない値$\times y_{\boldsymbol{l}'_s}^k$」の形になっているため、

$$\frac{\alpha_t(s|\boldsymbol{l})\beta_t(s|\boldsymbol{l})}{{y_{\boldsymbol{l}_s'}^t}^2}$$

は $y_{\boldsymbol{l}'_s}^k$ によらない値となる。したがって、シグマの中身はこの値に $y_{\boldsymbol{l}'_s}^k$ が掛かっている値であるため、偏微分の値は以下のようになる。

$$\frac{\partial}{\partial y_k^t}P(\boldsymbol{l} | \boldsymbol{x})=\frac{1}{{y_k^t}^2}\sum_{s\in lab(\boldsymbol{l},k)}\alpha_t(s|\boldsymbol{l})\beta_t(s|\boldsymbol{l})$$

## 目的関数

正解ラベルが出力される確率を最大化したいので、最小化したい目的関数は

$$O^{ML}(S, \mathcal{N}_w)=-\sum_{(\boldsymbol{x}, \boldsymbol{z}) \in S}\log P(\boldsymbol{z}|\boldsymbol{x})$$

となる。勾配降下法で学習するために、これをネットワーク出力である $y_k^t$ で微分する。

各データは独立なので 1 つのデータについて考えれば良い。また、合成関数の微分より

$$\frac{\partial}{\partial y_k^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)=-\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{\partial}{\partial y_k^t}P(\boldsymbol{z}| \boldsymbol{x})=-\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{{y_k^t}^2}\sum_{s\in lab(\boldsymbol{z},k)}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

となる。

次に、音響モデルの出力 $y_k^t$ は softmax 関数を通っているため、これを通る前の出力 $u_k^t$ で微分することを考える。

softmax 関数の定義より、

$$y_k^t=\frac{\exp(u_k^t)}{\sum_{k'} \exp(u_{k'}^t)}$$

であるので、

$$\frac{\partial y_{k'}^t}{\partial u_k^t}=y_{k'}^t\delta_{kk'}-y_{k'}^ty_k^t$$

となる。ただし、$\delta_{kk'}$ はクロネッカーのデルタである。

したがって、

$$\frac{\partial}{\partial u_k^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)=\sum_{k'}\frac{\partial}{\partial y_{k'}^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)\frac{\partial y_{k'}^t}{\partial u_k^t}$$

$$=-\sum_{k'}\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{{y_{k'}^t}^2}\left ( \sum_{s\in lab(\boldsymbol{z},k')}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})\right )\left (y_{k'}^t\delta_{kk'}-y_{k'}^ty_k^t\right )$$

ここで、

$$\sum_{k'}\sum_{s\in lab(\boldsymbol{z},k')}
\frac{\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})}{y_{k'}^t}=P(\boldsymbol{z}| \boldsymbol{x})$$

となるので、

$$\sum_{k'}\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{{y_{k'}^t}^2}y_{k'}^ty_k^t\sum_{s\in lab(\boldsymbol{z},k')}
\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

$$=\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}y_k^t\sum_{k'}\sum_{s\in lab(\boldsymbol{z},k')}
\frac{\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})}{y_{k'}^t}=y_k^t$$

したがって、

$$\frac{\partial}{\partial u_k^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)=y_k^t-\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{y_{k}^t}\sum_{s\in lab(\boldsymbol{z},k)}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

となる。（クロネッカーのデルタが付いてる方の項は $k'=k$ の場合だけ考えればいいので詳しく書いていない）

なお、実際に計算する際はアンダーフローを防ぐために、$\alpha_t(s|\boldsymbol{z}),\beta_t(s|\boldsymbol{z})$ の値を以下のように正規化して計算する。

$$\hat\alpha_t(s|\boldsymbol{l}):=\frac{\alpha_t(s|\boldsymbol{l})}{\sum_{s'} \alpha_t(s'|\boldsymbol{l})}$$

$$\hat\beta_t(s|\boldsymbol{l}):=\frac{\beta_t(s|\boldsymbol{l})}{\sum_{s'} \beta_t(s'|\boldsymbol{l})}$$

さらに、$P(\boldsymbol{l} | \boldsymbol{x})$ の代わりに

$$Z_t:=\sum_{s=1}^{|\boldsymbol{l}'|}\frac{\hat\alpha_t(s|\boldsymbol{l})\hat\beta_t(s|\boldsymbol{l})}{y_{\boldsymbol{l}_s'}^t}$$

を用いて

$$\frac{\partial}{\partial u_k^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)=y_k^t-\frac{1}{Z_t}\frac{1}{y_{k}^t}\sum_{s\in lab(\boldsymbol{z},k)}\hat\alpha_t(s|\boldsymbol{z})\hat\beta_t(s|\boldsymbol{z})$$

とすることで正規化を分母分子で打ち消す。

## 解釈

$$\frac{\partial}{\partial u_k^t}O^{ML}(\{(\boldsymbol{x}, \boldsymbol{z})\},\mathcal{N}_w)=y_k^t-\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{y_{k}^t}\sum_{s\in lab(\boldsymbol{z},k)}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

を解釈したい。

$$\frac{\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})}{y_{\boldsymbol{l}'_s}^t}$$

は、グラフにおいて、頂点 $(s,t)$ を通って始点から終点まで行く確率である。

したがって、

$$\frac{1}{y_{k}^t}\sum_{s\in lab(\boldsymbol{z},k)}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

は、$\boldsymbol{l}'_s=k$ となるような全ての $k$ に対して、頂点 $(k, t)$ を通って始点から終点へ行く確率である。

したがって、

$$\frac{1}{P(\boldsymbol{z}| \boldsymbol{x})}\frac{1}{y_{k}^t}\sum_{s\in lab(\boldsymbol{z},k)}\alpha_t(s|\boldsymbol{z})\beta_t(s|\boldsymbol{z})$$

は、グラフにおいて始点から終点へ行く、つまり音響特徴量 $\boldsymbol{x}$ から正解ラベル列 $\boldsymbol{z}$ が実現するという条件の下で、縮約前ラベル列において時刻 $t$ のラベルが $k$ である条件付き確率になる。

この値が $y_k^t$ より大きいとき、勾配が負になるので、$u_k^t$ の値が大きくなるようにパラメータを調整することになる。