next up previous
Next: Comparison between IOHMMs and Up: Input-Output HMMs Previous: EM for HMMs and

Asynchronous IOHMMs

 

In a recent paper on asynchronous HMMs [&make_named_href('', "node31.html#Bengio+Bengio96","[93]")], it is shown how to extend the IOHMM formalism to the case of output sequences shorter than input sequences, which is normally the case in speech recognition (where the output sequence would typically be a phoneme sequence, and the input sequence a sequence of acoustic vectors). For this purpose an additional hidden variable is introduced, which controls whether an output is emitted or not at each time step. In the probabistic graphical model, the parents of this variable are the current state and the current input .

When conceived as a generative model of the output (given the input), an asynchronous IOHMM works as follows. At time t=0, an initial state is chosen according to the distribution , and the length of the output sequence l is initialized to 0. At other time steps t>0, a state is first picked according to the transition distribution , using the state at the previous time step and the current input . A decision is then taken as to whether or not an output will be produced at time t or not, according to the emit-or-not distribution, .

In the positive case, an output is then produced according to the emission distribution . The length of the output sequence is increased from to l. The parameters of the model are thus the initial state probabilities, , and the parameters of the emit-or-not, emission and transition conditional distribution models, , and .

The application of the EM algorithm to this model is similar to the one already outlined for HMMs and synchronous IOHMMs, but the forward and backward recurrences require amounts of storage and computation that are proportional to the product of the input and output lengths, times the number of non-zero transition probabilities (whereas ordinary HMMs and synchronous IOHMMs only require resources proportional to the product of the output length times the number of transitions).

A recognition algorithm (which looks for the most likely output and state sequence) can also be derived, similarly to the Viterbi algorithm for HMMs. This recognition algorithm has the same computational complexity as the recognition algorithm for ordinary HMMs, i.e., the number of transitions times the length of the input sequence.

Asynchronous IOHMMs have been proposed for speech recognition [&make_named_href('', "node31.html#Bengio+Bengio96","[93]")] but could be used in other applications to map input sequences to output sequences of a different length. They represent a particular type of probabilistic transducer, discussed in the next section.


next up previous
Next: Comparison between IOHMMs and Up: Input-Output HMMs Previous: EM for HMMs and

Yoshua Bengio
Tue Oct 7 08:34:36 EDT 1997