Implementing Beam Search with a Language Model

Beam search decoders improve upon greedy search by keeping multiple candidate transcriptions. However, their decisions are often based solely on acoustic evidence. To produce linguistically coherent output, integrating a language model's score directly into the beam search process is necessary. This integration involves modifying the scoring function used to rank hypotheses at each step.

The decoder's goal shifts from finding the most acoustically likely path to finding the path that best satisfies both the acoustic model and the language model. The score for each hypothesis in the beam is updated using the combined formula introduced earlier:

$$\text{score}(W) = \text{score}_{\text{Acoustic}} + \alpha \cdot \text{score}_{\text{LM}} + \beta \cdot \text{word\_count}$$

Let's break down how each part is incorporated:

• $\text{score}_{\text{Acoustic}}$: This is the running log probability of the character sequence, calculated from the CTC output. This is the score a standard beam search decoder would use.
• $\text{score}_{\text{LM}}$: This is the log probability of the full word sequence, as calculated by the external n-gram language model. This score is only applied when a complete word is formed.
• $\alpha$ (alpha): The language model weight. This hyperparameter controls the influence of the LM. A higher α prioritizes grammatical correctness, sometimes at the expense of acoustic accuracy, while a lower α makes the decoder trust the acoustic model more.
• $\beta$ (beta): The word insertion bonus. This term adds a small bonus for each word in the hypothesis. It counteracts the natural tendency of probability models to favor shorter sequences (since multiplying more probabilities, which are less than 1, results in a smaller number). It helps ensure that the decoder does not unfairly penalize longer, correct sentences.

The Scoring Mechanism in Action

The integration of the language model occurs at specific moments during decoding. The beam search algorithm proceeds timestep by timestep, extending each hypothesis with new characters. The acoustic score is updated with every new character. However, the language model score is only calculated and added when a word boundary is identified, which is typically when a space character is appended to a hypothesis.

Consider two competing hypotheses in the beam: "recognize" and "wreck a nice". When the next part of the audio sounds like "speech", the acoustic model might produce high probabilities for the characters s-p-ee-ch.

1. Acoustic Update: The decoder extends "recognize" with a space, then s, p, and so on. The acoustic score is updated at each character extension.
2. LM Query: Once the hypothesis becomes "recognize ", the decoder identifies a complete word. It then queries the language model to get the probability of "speech" following "recognize". The LM will return a relatively high probability for this sequence.
3. Score Combination: The weighted LM score is added to the total score of this hypothesis, giving it a significant boost.

Simultaneously, the "wreck a nice" hypothesis is extended to "wreck a nice beach". When "wreck a nice " is finalized, the LM is queried for the probability of "beach" following "wreck a nice". While phonetically plausible, this phrase is less common, so the LM will assign it a lower score. As a result, the "recognize speech" hypothesis will likely achieve a higher total score and remain in the beam, while "wreck a nice beach" may be pruned.

The diagram above shows how two hypotheses are scored. Even if "wreck a beach" has a slightly better acoustic score, the high probability assigned by the language model to "recognize speech" can elevate its final score, making it the preferred transcription.

A Pseudocode Implementation

To make this process more concrete, here is a high-level algorithm for a CTC beam search decoder that incorporates an n-gram language model.

# A simplified representation of the algorithm

def ctc_beam_search_decoder(acoustic_probs, beam_width, lm, alpha, beta):
    # beam = [(prefix_text, acoustic_score, lm_state)]
    # lm_state stores the n-gram history for a hypothesis

    initial_lm_state = lm.initial_state()
    beam = [("", 0.0, initial_lm_state)]

    for timestep_probs in acoustic_probs:
        new_beam = []
        for prefix, acoustic_score, lm_state in beam:
            for char, char_prob in timestep_probs.items():

                # Standard CTC logic for handling blanks and repeated chars
                # (This part is omitted for clarity)
                new_prefix = prefix + char
                new_acoustic_score = acoustic_score + log(char_prob)

                # Check if a word was just completed
                if char == ' ':
                    # Score the completed word with the LM
                    word = get_last_word(new_prefix)
                    lm_score = lm.score(word, state=lm_state)

                    # Get new LM state for the next word
                    new_lm_state = lm.update_state(word, lm_state)

                    # Update total score with LM score and word bonus
                    total_score = new_acoustic_score + alpha * lm_score + beta

                    new_beam.append((new_prefix, total_score, new_lm_state))
                else:
                    # Not a word boundary, just carry over the LM state
                    total_score = new_acoustic_score
                    new_beam.append((new_prefix, total_score, lm_state))

        # Prune the beam: sort by score and keep the top `beam_width` hypotheses
        beam = sorted(new_beam, key=lambda x: x[1], reverse=True)[:beam_width]

    # Return the text from the best hypothesis in the final beam
    sorted(beam, key=lambda x: x[1], reverse=True)[0]
    return best_hypothesis[0]

Practical Notes

• State Management: As the pseudocode implies, each hypothesis in the beam must maintain its own language model state. For an n-gram model, this state is simply the last n-1 words of the hypothesis. This ensures that the probability of the next word is calculated based on its correct context.
• Tuning α and β: The α and β values are not fixed. They are important hyperparameters that must be tuned on a validation set to find the optimal balance for your specific acoustic model and language model. This is typically done by running decoding with different values and selecting the combination that yields the lowest Word Error Rate (WER).
• Performance: Querying an external language model for every new word in every hypothesis adds computational overhead. Efficient LM toolkits like KenLM are designed for fast queries, making this process feasible even for large beams.

By integrating a language model into the decoding search, you transform the ASR system from a simple acoustic-to-phonetic transcriber into a more intelligent system that understands and applies linguistic rules, significantly improving the quality and readability of the final transcription.