Arc Minimization in Finite State Decoding Graphs with Cross-Word Decoding 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 a 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.