CTC Decoding Algorithms
You'll learn how to convert CTC output probabilities into readable text using greedy decoding and beam search strategies.
Why Decoding Matters
Remember that CTC (Connectionist Temporal Classification) outputs probabilities at every time step for each possible character, including a special "blank" token. But these raw probabilities aren't text yet—we need a decoding algorithm to find the most likely character sequence.
Greedy Decoding
The simplest approach: at each time step, pick the character with the highest probability. Then apply CTC's collapse rules:
- Merge repeated characters
- Remove blanks
Example: If outputs are h-h-ee-ll-ll-oo, greedy decoding gives us hello.
Think of it like taking the obvious path at every fork in the road—fast but sometimes missing better routes.
Beam Search with Prefix Merging
Beam search maintains multiple hypotheses (paths) simultaneously, keeping only the top-k most probable sequences at each step. The key innovation for CTC is prefix merging: since h-e and he- both collapse to "he", we combine their probabilities.
How it works:
- Keep a "beam" of the k best partial sequences
- At each time step, extend each hypothesis with all possible characters
- Merge sequences that have identical prefixes after CTC collapse
- Prune to keep only top-k survivors
This is like exploring several promising paths at once, recognizing when different routes lead to the same place, and abandoning the least promising ones.
Beam search typically improves accuracy by 10-30% over greedy decoding, especially when combined with a language model that scores prefix plausibility.
Key Takeaway: Greedy decoding picks the best character at each step (fast, simple), while beam search with prefix merging explores multiple paths and intelligently combines equivalent hypotheses for better ASR accuracy.