A network emits T frames. The transcript is U characters. Nobody labelled which frame belongs to which letter — and producing that labelling by hand is exactly the cost CTC exists to remove.
The answer: add a blank symbol, define a collapse (merge runs, then delete blanks), and make the loss the probability of every frame-path that collapses to the target.
cc-aa-t, -c-a-t- and ccaaat all collapse to cat. Sum them all, in O(T·U), with a forward recursion.
Live, with the trellis: https://dev48.infy.uk/dl/day63-ctc-loss.html
The blank is not decoration
Without it you cannot spell a doubled letter. Collapse merges repeats, so ll becomes l and "hello" is unreachable. The blank is a separator: l-l collapses to ll. That is why the extended label interleaves blanks and the trellis has 2U+1 rows.
The transition rule everyone gets wrong
From state s you may come from s (stay), s-1 (advance), or s-2 (skip a blank) — but only if the current symbol is not blank and differs from the symbol at s-2.
if (s > 1 && ext[s] !== BLANK && ext[s] !== ext[s-2])
v = logAdd(v, a[t-1][s-2]);
Skipping the blank between two identical letters would collapse them into one — the path would spell cat when the label is ccat.
Get it wrong and the loss still decreases during training. It looks completely healthy. It is just computing the probability of the wrong set of paths.
So I built an oracle that shares no code
For small T, enumerate every path in alphabet^T, collapse each, and sum the ones that match. No recursion, no dynamic programming.
- 72 cases across 6 labels: worst relative error 1.6e-15
- Deliberately broken transition rule: caught 20/20 times on a doubled letter
- All 25 reachable labellings sum to exactly 1 via the recursion
- Gradients vs central finite differences: worst 8.5e-11 over 75 entries
-
sum_s alpha*beta == Pat every frame, worst 9.6e-16
The second bullet is the one that matters. The broken version produces smooth, plausible numbers; only an independent enumerator says otherwise.
Log space, always
These are products of hundreds of probabilities. In float64 they underflow to exactly zero long before you finish, and then the gradient is 0/0. Every quantity is a log-probability and addition is logAdd(a,b) = max + log1p(exp(-|a-b|)).
Greedy decoding answers a different question
Argmax per frame then collapse gives the most likely path, not the most likely labelling — many paths collapse to the same string and their probabilities add. A labelling assembled from many mediocre paths can beat one made of a single excellent path.
They disagreed on 107 of 300 random emission matrices. That gap is what prefix beam search exists to close.
And the assumption worth stating: CTC assumes outputs are conditionally independent across frames. That is false for language, and it is why CTC systems are paired with an external language model.
Top comments (0)