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.