CTC
Jak działa
1) Sieć generuje dla każdego z T kroków czasowych rozkład softmax nad etykietami plus symbol blank. 2) Definiuje się regułę zwijania ścieżki: scalenie kolejnych identycznych etykiet, a następnie usunięcie wszystkich blanków. 3) Prawdopodobieństwo docelowej sekwencji etykiet to suma prawdopodobieństw wszystkich ścieżek zwijających się do niej. 4) Sumę i gradienty oblicza algorytm forward-backward na rozszerzonej sekwencji etykiet (z blankami wstawionymi między i wokół etykiet). 5) Strata to ujemny logarytm tego prawdopodobieństwa; obliczenia prowadzi się w przestrzeni logarytmicznej dla stabilności numerycznej. 6) Przy inferencji dekoduje się wynik przez wybór najbardziej prawdopodobnej ścieżki (greedy/best-path) lub beam search (często z zewnętrznym modelem językowym).
Rozwiązany problem
Tradycyjne uczenie sekwencyjne wymagało wyrównania wejścia do etykiet na poziomie pojedynczych ramek (np. który fragment nagrania odpowiada której fonemie), co jest kosztowne i często niedostępne. CTC eliminuje potrzebę takiego wyrównania, ucząc model bezpośrednio z par (sekwencja wejściowa, sekwencja etykiet).
Komponenty
Dodatkowa etykieta oznaczająca brak wyjścia w danym kroku czasowym oraz separująca powtórzone etykiety, umożliwiająca poprawne zwijanie ścieżek.
Warstwa wyjściowa produkująca rozkład prawdopodobieństwa nad zbiorem etykiet powiększonym o blank, dla każdego kroku czasowego.
Programowanie dynamiczne sumujące prawdopodobieństwa wszystkich wyrównań zgodnych z docelową sekwencją i obliczające gradienty.
Procedura mapująca wyjścia sieci na końcową sekwencję etykiet (best-path lub beam search, opcjonalnie z modelem językowym).
Implementacja
Iloczyny wielu małych prawdopodobieństw powodują underflow; obliczenia należy prowadzić w przestrzeni logarytmicznej.
Dwie identyczne sąsiednie etykiety w celu muszą być rozdzielone blankiem, inaczej reguła zwijania je scali.
CTC zakłada niezależność warunkową etykiet w czasie przy danym wejściu, co daje słaby wbudowany model językowy; zwykle łączy się je z zewnętrznym LM.
Liczba kroków czasowych musi wystarczyć na reprezentację sekwencji etykiet (z uwzględnieniem blanków między powtórzeniami).
Ewolucja
Graves i wsp. przedstawiają CTC na ICML, umożliwiając trening RNN bez wyrównania na niezsegmentowanych danych sekwencyjnych.
Systemy takie jak Deep Speech wykorzystują CTC do kompleksowego rozpoznawania mowy bez ręcznego wyrównania fonemów.
Watanabe i wsp. łączą stratę CTC z dekoderem uwagowym, aby ustabilizować wyrównanie i poprawić end-to-end ASR; CTC pełni rolę regularizatora monotonicznego wyrównania.
Hiperparametry (konfigurowalne osie)
Pozycja symbolu pustego w zbiorze etykiet; musi być spójna między treningiem a dekodowaniem.
Liczba hipotez utrzymywanych podczas dekodowania beam search; kompromis między jakością a kosztem.
Liczba etykiet wyjściowych plus symbol blank.
Złożoność obliczeniowa
Złożoność czasowa: O(T · L). Złożoność przestrzenna: O(T · L).
Wąskie gardło obliczeniowe
Sumę po wszystkich wyrównaniach oraz gradienty liczy programowanie dynamiczne (forward-backward) o koszcie O(T·L), z rekurencją sekwencyjną wzdłuż osi czasu T. Dla długich sekwencji i dużych zbiorów etykiet ten etap dominuje koszt obliczenia straty, bo nie zrównolegla się po czasie.
Równoległość
Przejście sieci i batch są równoległe, ale rekurencja forward-backward jest sekwencyjna wzdłuż osi czasu.
Wymagania sprzętowe
CTC to kryterium straty i metoda dekodowania niezależne od konkretnego sprzętu; korzysta z akceleracji GPU/TPU tak jak każdy trening sieci.