WFST compression for automatic speech recognition

Diamantino CaseiroInterspeech 2010

TL;DR

This paper introduces a novel compression technique for Weighted Finite-State Transducers (WFSTs), the backbone of modern Automatic Speech Recognition (ASR) systems. By intelligently encoding the components of these large, complex structures, the authors achieve significant reductions in memory and disk footprint, often by a factor of three, without sacrificing recognition accuracy or speed. This is crucial for deploying ASR on resource-constrained devices and for scaling large-scale distributed ASR systems.

What Problem Does This Paper Address?

Automatic Speech Recognition (ASR) systems rely heavily on Weighted Finite-State Transducers (WFSTs) to represent complex knowledge sources like pronunciation lexicons and language models. When these are compiled into a single, integrated search network, the resulting WFST can become enormous, often spanning multiple gigabytes. This poses a significant challenge for:

  • Resource-constrained devices: Deploying ASR on mobile phones or embedded systems becomes difficult due to limited memory.
  • Large-scale ASR deployments: Distributing these massive models across server farms for services like voice search or question answering incurs substantial costs for hardware and upgrades.

Existing methods for reducing WFST size include optimizing the compilation process itself or pruning language models. However, this paper focuses on directly compressing the WFST structure, aiming for a general-purpose technique applicable to the specific types of WFSTs commonly used in ASR.

Methods

The proposed compression method is a multi-stage process designed to be effective for large WFSTs and efficient for incremental expansion. The core idea is to represent the WFST's components (states and arcs) in a more compact format.

  1. State Encoding: To reduce the memory overhead associated with accessing arcs from a given state, the authors propose a "paged indexing" method. States are grouped into pages, and addresses of arcs are computed using a combination of page and offset indices. This scheme aims to reduce memory requirements per state to under 3 bytes. Final state information and state potentials are also encoded efficiently, only being allocated if necessary.
  2. Arc Encoding: This is the most significant part of the compression. It involves two main steps:
  3. Field-Specific Transformation: For each field within an arc (destination state, input label, output label, cost), a transformation function is applied to reduce the magnitude of its values. Examples include representing destination states as differences from their origin or previous arc's destination, and using delta encoding or lookup tables for labels.
  4. Variable-Length Packing: The transformed field values are then encoded into a variable-length sequence of bytes. This allows fields with smaller values to use fewer bytes, unlike fixed-size representations. The method uses control bits within a byte to indicate the size of each field, optimizing for the specific WFST's characteristics. Different packing functions (e.g., byte code, explicit bit fields) and quantization for weights (e.g., 8-bit, 16-bit) are explored.
  5. Encoding Method Selection: An algorithm performs two passes over the WFST to determine the optimal combination of transformation and packing functions for each field, aiming for the most compact representation.
  6. "On-the-fly" Composition: For composite WFSTs (like CLG, which is a composition of C and LG), the paper proposes storing the component WFSTs separately and composing them "on-the-fly" during decoding. This significantly reduces the memory footprint of the combined structure.

Datasets

The paper evaluates its compression technique on two large-vocabulary ASR applications:

  • Voice-Search ASR application: Vocabulary of 212k words.
  • Question-Answering application: Vocabulary of 515k words.

These applications utilize different types of WFSTs, including language models (G), pronunciation dictionaries (L), and their compositions (LG, CLG). The paper does not introduce new datasets but uses existing large-scale ASR tasks to demonstrate the effectiveness of the compression.

Key Insights and Ideas

  • Variable-length encoding is key: The ability to use fewer bytes for smaller values in fields like destination states and labels is a major driver of compression. This is more efficient than fixed-size representations.
  • Context matters for compression: The optimal compression strategy (transformation and packing functions) is highly dependent on the specific WFST. The method's ability to automatically select these is crucial.
  • "On-the-fly" composition offers massive memory savings: For composite WFSTs, delaying the full composition until runtime can lead to dramatic reductions in memory usage, even if it might slightly impact decoding speed.
  • Compression doesn't hurt speed: Surprisingly, the compressed format can sometimes lead to faster recognition. This is attributed to improved cache locality and reduced memory access, which outweigh the computational cost of decompression.

Key Results

  • Significant Size Reduction: The proposed method typically reduces WFST memory and disk requirements to less than 35% of their original size.
  • Extreme Compression with "On-the-fly" Composition: For composite WFSTs, memory requirements can be reduced by factors of 8-10x (e.g., from 5,969 MB to 637 MB for the question-answering application).
  • No Accuracy Loss: Experiments show no loss in recognition accuracy due to the compression.
  • Comparable or Better Speed: Recognition speed is either maintained or slightly improved compared to uncompressed WFSTs.
  • Compression Ratios Comparable to gzip -9: The compression ratios achieved are similar to offline compression tools, but the proposed method is designed for runtime use.

Limitations and Future Work

  • State Renumbering: The authors acknowledge that the state renumbering procedure could be further improved, potentially by exploring methods developed for separable graphs.
  • Weight Quantization: While effective, weight quantization could be studied more deeply for specific WFST classes (like language models) to see if stronger quantization is possible without accuracy loss.
  • More Transformation/Packing Functions: The technique is extensible, and the authors plan to add more specific transformation and packing functions to further enhance compression.
  • Generalizability: The authors believe the technique is general enough to accommodate future improvements without substantial changes to the core framework.

Summary updated

BibTeX
@inproceedings{caseiro2010wfst,
  author = {Diamantino Caseiro},
  title = {{WFST compression for automatic speech recognition}},
  booktitle = {Interspeech},
  year = {2010},
}

Loading related content...

Figure