Arc minimization in finite-state decoding graphs with cross-word acoustic context

Recent approaches to large vocabulary decoding with weighted finite-state transducers have focused on the use of determinization and minimization algorithms to produce compact decoding graphs. This paper addresses the problem of compiling decoding graphs with long span cross-word context dependency between acoustic models. To this end, we extend the finite-state approach by developing complementary arc factorization techniques that operate on non-deterministic graphs. The use of these techniques allows us to statically compile decoding graphs in which the acoustic models utilize a full word of cross-word context. This is in significant contrast to typical systems which use only a single phone. We show that the particular arc-minimization problem that arises is in fact an NP-complete combinatorial optimization problem. Heuristics for this problem are then presented, and are used in experiments on a Switchboard task, illustrating the moderate sizes and runtimes of the graphs we build. © 2003 Elsevier Ltd. All rights reserved.