7th International Conference on Spoken Language Processing September 16-20, 2002 Denver, Colorado, USA

Arc Minimization in Finite State Decoding Graphs with Cross-Word Acoustic Context

Geoffrey Zweig (1), George Saon (1), F. Yvon (2)

(1) IBM T.J. Watson Research Center, USA; (2) ENST, France

Recent approaches to large vocabulary decoding with finite state graphs have focused on the use of state minimization algorithms to produce relatively compact graphs. This paper extends the fi- nite state approach by developing complementary arc-minimization techniques. The use of these techniques in concert with state minimization 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, and describe the reduction from 3-SAT. We present experimental results that illustrate the moderate sizes and runtimes of graphs for the Switchboard task.

Full Paper

Bibliographic reference.  Zweig, Geoffrey / Saon, George / Yvon, F. (2002): "Arc minimization in finite state decoding graphs with cross-word acoustic context", In ICSLP-2002, 389-392.