CTC Beam Search

CTC 알고리즘

GT alignment가 없는 상황에서, 가장 그럴듯한 alignment를 학습하는 것
Forward Backward를 반복하면서, likelihood를 계산하고 maximize하는데, 이걸 계속해서 무한히 반복함으로써, 가장 그럴듯한 path들에 대한 확률을 높이는 것임

Full search하는 것에 대해서 계산량을 줄이기 위해서 dynamic programming을 한것

https://seunghyunseo.github.io/speech/2021/10/24/CTC/

CTC는 RNN이나 Transformer Decoder를 이용한 seq2seq이랑 전혀 다른 방식으로 생각을 해야한다. 모든 token에 대한 vocab probability를 BERT의 softmax(token feature) 같은걸 이용해서 미리 전부다 뽑아둔 상태(emission이라고함)에서, 그다음 가장 그럴듯한 probable path을 결정하는 것이다.

 

CTC Beam Search

CTC Beam Search는 그냥 Beam Search와 다르게 merge하는 결과가 추가 된다.
그리고 이 과정에서 연속된 문자를 합쳐서 merged된 결과를 기준으로 해석을 해야한다.
ex) -a 랑 aa랑 a-는 사실 다 같은 a를 의미한다.

즉, 모든 beam들이 항상 non_blank prob과 blank prob 두가지를 갖고 있다.
blank prob: a- 
blank로 끝날 확률
non_blank prob: -a, aa
blank로 끝나지 않을 확률

근데 이거 빔 확률 계산하는 거는 그냥, HMM의 forward 알고리즘하고 완전 똑같네.

그래서 CTC는 반드시 빔서치를 해야한다.(LM도 적용해야함. 왜냐하면 독립이라는 emission에 가정이 포함되어있기 때문에


Beam Size
History까지 고려한, 독립된 sequence의 총개수를 몇개로 유지할지.
따라서 seq_length가 길어질수록 더 정확한 빔서치를 위해서는 빔사이즈가 커야한다.


Beam Token Size(truncated Vocab 휴리스틱 방법)
계산속도를 빠르게 하기 위한 휴리스틱 방법으로, 32개의 vocab을 다 고려하지 않고, emission matrix에서 각 time step 마다 상위 확률을 가진 16개(가칭)만 고려해서 빔서치를 근사적으로 하겠다는 것임.


Emission matrix: [Batch, Time, Vocab]
근데 어차피 여기서 Batch는 for loop으로 처리함.
Time은 frame length개수
Vocab은 vocab사이즈 만큼에 대한 probability


좋은 구현 예시
https://github.com/flashlight/flashlight/blob/0.3/flashlight/lib/text/decoder/LexiconDecoder.cpp#L49