decode.tex

隐马尔科夫模型工具箱

%/* ----------------------------------------------------------- */
%/*                                                             */
%/*                          ___                                */
%/*                       |_| | |_/   SPEECH                    */
%/*                       | | | | \   RECOGNITION               */
%/*                       =========   SOFTWARE                  */ 
%/*                                                             */
%/*                                                             */
%/* ----------------------------------------------------------- */
%/*         Copyright: Microsoft Corporation                    */
%/*          1995-2000 Redmond, Washington USA                  */
%/*                    http://www.microsoft.com                */
%/*                                                             */
%/*   Use of this software is governed by a License Agreement   */
%/*    ** See the file License for the Conditions of Use  **    */
%/*    **     This banner notice must not be removed      **    */
%/*                                                             */
%/* ----------------------------------------------------------- */
%
% HTKBook - Steve Young 1/12/97
%

\mychap{Decoding}{decode}

\sidepic{Tool.decode}{80}{ }
The previous chapter has described how to construct a recognition
network specifying what is allowed to be spoken and how
each word is pronounced.  Given such a network, its associated
set of HMMs, and an unknown utterance,  the probability of
any path through the network can be computed.   The task of a 
decoder is to find those paths which are the most likely.\index{decoder}

As mentioned previously, decoding in \HTK\ is performed by a library
module called \htool{HRec}.  \htool{HRec} uses the token passing
paradigm to find the best path and, optionally, multiple alternative
paths.  In the latter case, it generates a lattice containing the
multiple hypotheses which can if required be converted to an N-best
list.  To drive \htool{HRec} from the command line, \HTK\ provides a
tool called \htool{HVite}.  As well as providing basic recognition,
\htool{HVite} can perform forced alignments, lattice rescoring and
recognise direct audio input.  

To assist in evaluating the performance
of a recogniser using a test database and a set of reference transcriptions, 
\HTK\ also provides a tool called \htool{HResults} to compute word 
accuracy and various related statistics.  
The principles and use of these recognition facilities are described
in this chapter.


\mysect{Decoder Operation}{decop}

\index{decoder!operation}
As described in Chapter~\ref{c:netdict} and illustrated by
Fig.~\href{f:recsys}, decoding in \HTK\ is controlled by a recognition
network compiled from a word-level network, a dictionary and a set of
HMMs.  The recognition network consists of a set of nodes connected
by arcs.  Each node is either a HMM model instance or a word-end.
Each model node is itself a network consisting of states connected by
arcs.  Thus, once fully compiled, a recognition 
network\index{recognition!network} ultimately
consists of HMM states connected by transitions.  However, it can be
viewed at three different levels: word, model and state.
Fig.~\href{f:recnetlev} illustrates this hierarchy.

\sidefig{recnetlev}{62}{Recognition Network Levels}{2}{
For an unknown
input utterance with $T$ frames, every path from the start node to the
exit node of the network which passes through exactly $T$ emitting HMM
states is a potential recognition 
hypothesis\index{recognition!hypothesis}.
Each of these paths has a log probability which is computed by summing
the log probability of each individual transition in the path and the
log probability of each emitting state generating the corresponding
observation.  Within-HMM transitions are determined from the HMM
parameters, between-model transitions are constant and word-end
transitions are determined by the language model likelihoods attached
to the word level networks.

The job of the decoder is to find those paths through the network
which have the highest log probability.  These paths
are found using a \textit{Token Passing} algorithm.  A token represents
a partial path through the network extending from time 0 through to time $t$.
At time 0, a token is placed in every possible start node.  \index{token passing}
}

Each time step,
tokens are propagated along connecting transitions stopping whenever they
reach an emitting HMM state.  When there are multiple exits from a node,
the token is copied so that all possible paths are explored in parallel.
As the token passes across transitions and through nodes, its log probability
is incremented by the corresponding transition and emission probabilities.
A network node can hold at most $N$ tokens.  Hence, at the end of each time step,
all but the $N$ best tokens in any node are discarded.


As each token passes through the network it must maintain a history
recording its route.  The amount of detail in this history\index{token history} depends
on the required recognition output.  Normally, only word sequences
are wanted and hence, only transitions out of word-end nodes\index{word-end nodes} need
be recorded.  However, for some purposes, it is useful to know the
actual model sequence and the time of each model to model transition.
Sometimes a description of each path down to the state level
is required.  All of this information, whatever level of detail is
required, can conveniently be represented using a lattice structure.

Of course, the number of tokens allowed per node and the amount of
history information requested will have a significant impact on
the time and memory needed to compute the lattices.  The most
efficient configuration is $N=1$ combined with just 
word level history information and this is sufficient
for most purposes.

A large network will have many nodes and one way to make a significant
reduction in the computation needed is to only propagate tokens which
have some chance of being amongst the eventual winners.  This process
is called \textit{pruning}.  It is implemented at each time step by
keeping a record of the best token overall and de-activating all
tokens whose log probabilities fall more than a \textit{beam-width}
below the best.  For efficiency reasons, it is best to implement primary
pruning\index{pruning} at the model rather than the state level.  Thus, models
are deactivated when they have no tokens in any state within the beam and
they are reactivated whenever active tokens are propagated into them.
State-level pruning is also implemented by replacing any token by a 
null (zero probability) token if it falls outside of the beam.
If the pruning beam-width\index{beam width} is set too small then the most likely
path might be pruned before its token reaches the end of the utterance.
This results in a \textit{search error}.  Setting the beam-width is
thus a compromise between speed and avoiding search errors.

When using word loops with bigram probabilities, tokens emitted from
word-end nodes will have a language model probability added to them
before entering the following word.  Since the range of language
model probabilities is relatively small, a narrower beam can be
applied to word-end nodes without incurring additional 
search errors\index{search errors}.
This beam is calculated relative to the best word-end token and
it is called a \textit{word-end beam}.  In the case, of a recognition
network with an arbitrary topology, word-end pruning may still be
beneficial but this can only be justified empirically.

Finally, a third type of pruning control is provided.  An upper-bound
on the allowed use of compute resource can be applied by setting
an upper-limit on the number of models in the network which can
be active simultaneously.  When this limit is reached, the pruning
beam-width is reduced in order to prevent it being exceeded.


\mysect{Decoder Organisation}{decorg}

The decoding process itself is performed by a set of core functions 
provided within the library module \htool{HRec}\index{hrec@\htool{HRec}}.  The process
of recognising a sequence of utterances is illustrated in 
Fig.~\href{f:decflow}.

\index{decoder!organisation}
The first stage is to create a \textit{recogniser-instance}.  This is
a data structure containing the compiled recognition network and
storage for storing tokens.  The point of encapsulating all of the
information and storage needed for recognition into a single object is
that \htool{HRec}\index{hrec@\htool{HRec}} is re-entrant and can support 
multiple recognisers\index{multiple recognisers}
simultaneously.  Thus, although this facility is not utilised in the
supplied recogniser \htool{HVite}\index{hvite@\htool{HVite}}, it does provide applications
developers with the capability to have multiple recognisers running
with different networks.

Once a recogniser has been created, each unknown input is 
processed by first executing a \textit{start recogniser} call, and then
processing each observation one-by-one.  When all input observations
have been processed, recognition is completed by generating a lattice.
This can be saved to disk as a standard lattice format (SLF) file or
converted to a transcription.

The above decoder organisation is extremely flexible and this is
demonstrated by the \HTK\ tool \htool{HVite} which is a simple 
shell program designed to allow \htool{HRec} to be driven from
the command line.  

Firstly, input
control in the form of a recognition network allows three distinct modes
of operation

\sidefig{decflow}{62}{Recognition Processing}{2}{
\begin{enumerate}
\item \textit{Recognition} \\
This is the conventional case in which the recognition network
is compiled from a task level word network.\index{decoder!recognition mode}

\item \textit{Forced Alignment} \\
In this case, the  recognition network
is constructed from a word level transcription (i.e.\ orthography)
and a dictionary. The compiled network may include optional silences
between words and pronunciation variants.  Forced alignment is often useful
during training to automatically derive phone level transcriptions.
It can also be used in automatic annotation systems.
\index{decoder!alignment mode}

\item \textit{Lattice-based Rescoring} \\
In this case, the input network is compiled from a lattice generated
during an earlier recognition run.  This mode of operation can be
extremely useful for recogniser development since rescoring can be
an order of magnitude faster than normal recognition.   The required
lattices are usually generated by a basic recogniser running with
multiple tokens, the idea being to generate a lattice containing both
the correct transcription plus a representative number of confusions.
Rescoring can then be used to quickly evaluate the performance of more 
advanced recognisers and the effectiveness of new recognition techniques.
\index{decoder!rescoring mode}

\end{enumerate}

The second source of flexibility lies in the provision of multiple
tokens and recognition output
in the form of a lattice.  In addition to providing a mechanism
for rescoring, lattice output can be used as a source of multiple
hypotheses either for further recognition processing or input
to a natural language processor.  Where convenient, lattice output
can easily be converted into N-best lists.
}

Finally, since \htool{HRec} is explicitly driven step-by-step at the
observation level, it allows fine control over the recognition process and a
variety of traceback and on-the-fly output possibilities.

For application developers, \htool{HRec} and the \HTK\ library modules
on which it depends can be linked directly into applications.  It 
will also be available in the form of an industry standard API.  However, 
as mentioned earlier the \HTK\ toolkit 
also supplies a tool called \htool{HVite} which is a shell program
designed to allow  \htool{HRec} to be driven from the command line.
The remainder of this chapter will therefore explain the various facilities
provided for recognition from the perspective of \htool{HVite}.

\mysect{Recognition using Test Databases}{hvrec}

When building a speech recognition system or investigating speech
recognition algorithms, performance must be monitored by testing
on databases of test utterances for which reference transcriptions
are available.  To use \htool{HVite} for this purpose it is
invoked with a command line of the form
\begin{verbatim}
    HVite -w wdnet dict hmmlist testf1 testf2 ....
\end{verbatim}
where \texttt{wdnet} is an SLF file containing the word level network, 
\texttt{dict} is the pronouncing dictionary and hmmlist contains
a list of the HMMs to use.  The effect of this command is that
\htool{HVite} will use \htool{HNet} to compile the word level network
and then use \htool{HRec} to recognise each test file.   The parameter kind
of these test files must match exactly with that used to train the HMMs.
For evaluation purposes, test files are normally stored in parameterised
form but only the basic static coefficients are saved on disk.  For example,
delta parameters are normally computed during loading.  As explained in
Chapter~\ref{c:speechio}, \HTK\ can perform a range of parameter conversions
on loading and these are controlled by configuration variables.  Thus,
when using \htool{HVite}, it is normal to include a configuration file
via the \texttt{-C} option in which the required target parameter kind 
is specified.  Section~\ref{s:recaudio} below on processing direct
audio input explains the use of configuration files in more detail.
\index{decoder!evaluation}

In the simple
default form of invocation given above, \htool{HVite} would
expect to find each HMM definition in a separate file in the current
directory and each
output transcription would be written to a separate file in the current directory.
Also, of course, there will typically be a large number of test files.

In practice, it is much more convenient to store HMMs in master macro files (MMFs),
store transcriptions in master label files (MLFs) and list data files
in a script file.  Thus, a more common form of the above invocation would
be 
\begin{verbatim}
    HVite -T 1 -S test.scp -H hmmset -i results -w wdnet dict hmmlist 
\end{verbatim}
where the file \texttt{test.scp} contains the list of test file names,
\texttt{hmmset} is an MMF containing the HMM definitions\footnote{
Large HMM sets will often be distributed across a number of MMF files,
in this case, the \texttt{-H} option will be repeated for each file.},
and  \texttt{results} is the MLF for storing the recognition output.

\index{decoder!progress reporting}
As shown, it is usually a good idea to enable basic progress reporting
by setting the trace option as shown.  This will cause the recognised
word string to be printed after processing each file.  For example,
in a digit recognition task the trace output might look like
\begin{verbatim}
   File: testf1.mfc
   SIL ONE NINE FOUR SIL 
   [178 frames] -96.1404 [Ac=-16931.8 LM=-181.2] (Act=75.0)
\end{verbatim}
where the information listed after the recognised string is the total
number of frames in the utterance, the average 
log probability\index{average log probability} per frame,
the total acoustic likelihood, the total language model likelihood and
the average number of active models.\index{decoder!trace output}

The corresponding transcription
written to the output MLF form will contain an entry of the form
\index{decoder!output MLF}

\begin{verbatim}
    "testf1.rec"
           0  6200000 SIL  -6067.333008
     6200000  9200000 ONE  -3032.359131
     9200000 12300000 NINE -3020.820312
    12300000 17600000 FOUR -4690.033203
    17600000 17800000 SIL   -302.439148