token passing

[Jiahn K]

What’s the reason for HTK to use token passing for recognition instead of working on the lattice?

[Simon]

Token Passing uses a much smaller data structure: the HMM (= a finite state model) itself, which is one “column” (= all model states at a particular time) of the lattice.

So, Token Passing is equivalent to working with the lattice whilst only ever needing one column of it in memory at any given time.

Token Passing is a time-synchronous algorithm – all paths (= tokens) are extended forwards in time at once.

[Everything below this point is beyond the scope of Speech Processing]

There are non-time-synchronous algorithms. Working on the full lattice would allow paths to be extended over states, or over time, in many different ways. When combined with beam pruning, a clever ordering of the search can lead to doing fewer computations overall. This becomes important for large vocabulary connected speech recognition (LVCSR).

But we then also have the problem that the lattice is too big to construct in memory, so we create only the parts of it that we are going to search. Historical footnote: my Masters dissertation was an implementation of a stack decoder performing A* search; this avoids constructing the lattice in memory, whilst searching it in “best first” order.

In HTK, HVite does Token Passing, which becomes inefficient for LVCSR. For LVCSR, HDecode is much more sophisticated and efficient.

[Author]

Posts