A confusion network, sometimes called a word confusion network or informally known as a sausage, is a data structure used in natural language processing to combine outputs from multiple automatic speech recognition or machine translation systems. It represents competing hypotheses about a sequence of words in a compact form, enabling downstream processes to defer decisions about ambiguous content until more context is available.
The structure is a simple linear directed acyclic graph. It has a single start node and a single end node, with the property that every path from start to end passes through all intermediate nodes in order. Between any two adjacent nodes, a set of edges represents alternative words or phrases that could occupy that position in the sequence. This set of alternatives is called a confusion set. Each edge typically carries a weight or probability reflecting the confidence of the underlying systems in that particular option.
Origins and Purpose
Confusion networks emerged from research in automatic speech recognition during the late 1990s and early 2000s. Speech recognizers often produce a lattice, a more complex graph of possible word sequences, but lattices can be computationally expensive for downstream components such as language models or machine translation systems to process. Confusion networks simplify this by collapsing the lattice into a linear structure, trading some expressive power for efficiency. The linear form allows algorithms to process the output in a single pass, which is particularly valuable in real-time applications like telephony or broadcast transcription.
The informal name "sausage" derives from the visual appearance of the graph, which resembles a chain of linked segments when drawn. The term appears in academic literature from the early 2000s, notably in work by researchers at Nokia Bell Labs and other institutions exploring lattice compression techniques.
Use in Machine Translation
In machine translation, confusion networks serve a distinct role. Rather than combining outputs from multiple recognizers, they allow a translation system to accept multiple ambiguous inputs and defer committal decisions until later stages of processing. For example, when translating speech that has been transcribed with uncertainty, the translation system can take a confusion network as input and generate a translation that considers all alternatives simultaneously. This approach avoids committing to a single transcription that might be wrong, and instead lets the translation model weigh the possibilities using its own knowledge.
The defining characteristic in this context is the deferral of decisions. A translation system using confusion networks can produce a target-language output that is itself a confusion network, which can then be rescored or decoded using additional models. This is particularly useful in spoken language translation, where recognition errors are common and the cost of a wrong early choice can propagate through the entire translation.
Software Implementations
Confusion networks are implemented in several widely used translation and speech processing tools. The open source machine translation software Moses, developed primarily at the university-of-edinburgh and Carnegie Mellon University with contributions from many institutions, includes support for confusion network decoding. Moses allows users to input confusion networks in a specific format and produces translations that account for the alternative hypotheses.
In the commercial sphere, the proprietary translation API in IBM Bluemix Watson, now part of ibm's cloud offerings, has used confusion networks as part of its speech-to-speech translation pipeline. The API accepts audio input, performs recognition, and constructs a confusion network that is then passed to the translation engine, improving robustness against recognition errors.
Relationship to Other Techniques
Confusion networks are related to but distinct from other methods for combining hypotheses. Beam Search is a decoding strategy that explores multiple partial hypotheses but does not produce a compact graph structure. Sequence-to-Sequence (Seq2Seq) models, such as those based on the Transformer (architecture) architecture, typically operate on a single input sequence and do not natively handle alternative inputs, although extensions have been proposed. Confusion networks are also used in system combination, where outputs from multiple independent recognizers are merged into a single network, a technique that has been shown to reduce word error rate compared to any single system.
In modern Deep learning based systems, confusion networks have seen less prominence, as end-to-end models trained on large datasets often handle ambiguity internally. However, they remain relevant in hybrid systems and in scenarios where multiple legacy systems must be integrated, such as in broadcast news transcription or multilingual call routing.
Limitations and Extensions
A key limitation of confusion networks is that they assume a fixed ordering of positions. This makes them unsuitable for representing word insertions or deletions across different hypotheses, which can occur when systems disagree on the presence of a word. Extensions such as generalized confusion networks or alignment-based variants address this by allowing null edges or by using more complex alignment procedures. Another limitation is that the linear structure can lose long-range dependencies that a full lattice would preserve, though in practice the efficiency gains often outweigh this loss.
Research has also explored using confusion networks in other tasks, such as Data Augmentation for training Neural network models, where the alternatives provide natural variation in training data. Some work has applied them to Large language model prompting, using the network to represent multiple possible interpretations of a user query.