음성인식에서 가장 기초적인 CTC를 공부하려는데, 명쾌하게 어떤 방식으로 돌아가는지 정리된 블로그가 없어 작성해보고합니다.
CTC는 아래 논문에서 처음 제시되었습니다.
https://www.cs.toronto.edu/~graves/icml_2006.pdf
A. Graves, S. Fern´andez, F. Gomez, and J. Schmidhuber, “Connection-ist temporal classification: labelling unsegmented sequence data withrecurrent neural networks,” in Proceedings of the 23rd internationalconference on Machine learning, 2006, pp. 369–376.
먼저 CTC는 target label $\textbf{l}$ 이 나올 수 있는 가능한 모든 alignment path들의 posterior probability들의 summation으로 정의가 됩니다.
예를 들어, 8초 길이의 input sequence x를 받고 target label sequence인 단어 'CAT'을 출력해야한다면, C, A, T가 어느 시간인지는 모르지만 slience ($\emptyset$; blank token)을 포함해서 쭉 순서대로 출력하게될 것 입니다. 그러면 아래처럼 다양한 alignment path가 존재나옵니다.
이 모든 alignment path들은 아래처럼 정의된 collapsing function $B(\pi)$를 거치면 $\emptyset$과 여러 번 중복되서 나오는 token들을 제거해 target token으로 맵핑합니다. (따라서 위 수식에서 $B^{-1}(\textbf{l})$은 target $\textbf{l}$에 대한 가능한 모든 path들의 집합을 의미)
이제 input sequence $\textbf{x}$가 들어갔을 때 $\textbf{l}$이 나올 확률을 구하기 위해서는 각 path $\pi$들의 posterior probability를 계산해주어야합니다. 해당 값을 아래 식처럼 모델을 통해 추정된 각 frame 별 classification 결과에 따른 probability $y_{\pi_{t}}^{t}$의 곱으로 계산할 수 있습니다.
해당 $y_{\pi_{t}}^{t}$는 병렬적으로 모델에서 frame-wise classification을 통해서 구하게 됩니다.
여기서 이 path를 찾을 때 CTC가 가정을 하는 점이 있습니다.
가정: "target token의 사이와 sequence의 양 끝에 blank token이 있다"는 점입니다. 따라서 모든 path는 아래의 확장된 target sequence를 따라서 계산하게 됩니다.
물론 그냥 무작정 계산을 할 수도 있겠지만, 그렇게 되면 시간복잡도가 exponential하게 증가하게 됩니다.
따라서 논문에서는 해당 연산을 여러 iteration으로 나눠서 처리하는 forward-backward algorithm을 제시하였습니다.
forward-backward algorithm의 식은 아래와 같이 복잡해보이지만... 사실 규칙을 그대로 반영한 것이기 때문에 그림으로 보았을 때 더 이해하기가 쉽습니다.
path를 구하는 과정은 아래와 같이 격자형태의 그래프로 나타낼 수 있습니다. CTC는 monotonic assumtion이기 때문에 아래와 같은 규칙에 따라 path를 찾아나갑니다.
규칙1: 제자리 유지, 앞으로 이동만 가능 (뒤로 이동이 불가)
규칙 2: 다른 위치면서 동일한 sequence로는 skip이 불가능하다.
forward variable은 현위치를 이동할 수 있는 후보들의 variable들의 합에 해당 토큰이 t번째 시간(=frame)에서 나올 확률$y_{l^{'}_v}^{t}$를 곱해 계산합니다.
예를 들어,
붉은 원의 forward variable을 구하게 되면 규칙에 따라 blank token에서 2번째 뒤에 blank token으로 이동이 불가하기 때문에 $\alpha(2, 2)$와 동일 위치인 $\alpha(2, 3)$만 해당 $\alpha(3, 3)$으로 이동이 가능합니다.
파란 원의 경우에는 위 if 조건에 해당이 되지 않으니 $\alpha(T-2, 6)$, $\alpha(T-2, 5)$, $\alpha(T-2, 4)$으로 부터 이동할 수 있습니다.
어떤 고정된 시점과 위치 $(t, v)$에 대하여 그 지점의 점유 확률(occupation probability)은 forward variable과 backward variable의 곱으로 구할 수 있게됩니다.
그럼 최종적으로 모든 alignment path $\pi$에 대하여 posterior probability $p(\pi|\textbf{x})$를 계산하여 해당 target sequence에 대한 posterior probability $P(\textbf{l}|\textbf(x))$를 구해 CTC loss를 계산할 수 있게됩니다.
*참고로 CTC loss는 negarive log likelibood입니다.
