Introduction to Search Algorithms

The decoder’s job is to find the single sequence of words ($W$) that best matches the input audio ($O$). It does this by combining scores from the acoustic model, $P(O|W)$, and the language model, $P(W)$. The challenge is that the number of possible word sequences is unimaginably large. A ten-second audio clip could correspond to millions, if not billions, of potential sentences.

Checking every single possibility, a method known as a "brute-force search," is computationally impossible. If you had a vocabulary of 20,000 words, the number of possible 5-word sentences would be $20,000^5$, a number so large that even the fastest computers could not check them all in a reasonable amount of time. The decoder needs a much more efficient strategy.

The Search Problem as a Pathfinding Task

A better way to approach this is to reframe it as a pathfinding problem. Imagine a giant graph where each point represents a possible word that could follow the previous one. The decoder's task is to find the "cheapest" or "most likely" path from a start point to an end point through this graph.

Each path through the graph represents a unique sentence, or a "hypothesis." Each step along a path has an associated cost, which is calculated from the acoustic and language model probabilities. A path with a low acoustic model score (meaning the sounds don't match well) or a low language model score (meaning the word sequence is unlikely) will become very "expensive" quickly.

A simplified search graph. The decoder checks different paths (hypotheses), such as "recognize speech" and "wreck a nice beach." The red path indicates the one with the best combined score from the acoustic and language models.

Pruning Unlikely Hypotheses

Instead of blindly exploring all paths, search algorithms use an intelligent technique called pruning. As the decoder builds up sentence hypotheses word by word, it keeps track of their scores. If one path becomes significantly less likely than the best-known path so far, the algorithm simply abandons it.

This is a form of "beam search," where the decoder only keeps a small number, or "beam," of the most promising hypotheses at each step and discards the rest. By pruning away the majority of bad paths early, the decoder can focus its computational effort on the hypotheses that actually have a chance of being correct.

This process is what makes modern speech recognition possible. Without efficient search algorithms that can navigate a massive space of possibilities, even the best acoustic and language models would be useless. In the next section, you'll learn about the Viterbi algorithm, a classic and effective algorithm that forms the basis for many decoders.