// doc/decoders.dox
  
  
  // Copyright 2009-2011 Microsoft Corporation  Mirko Hannemann
  
  // See ../../COPYING for clarification regarding multiple authors
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  
  //  http://www.apache.org/licenses/LICENSE-2.0
  
  // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
  // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
  // MERCHANTABLITY OR NON-INFRINGEMENT.
  // See the Apache 2 License for the specific language governing permissions and
  // limitations under the License.
  
  namespace kaldi {
  
  /**
     \page decoders Decoders used in the Kaldi toolkit
  
   In the Kaldi toolkit there is no single "canonical" decoder, or a fixed
   interface that decoders must satisfy.  There are currently two decoders
   available: SimpleDecoder and FasterDecoder; and there are also lattice-generating
   versions of these (see \ref decoders_lattice).  By "decoder" we mean
   the internal code of the decoder; there are command-line programs that
   wrap these decoders so that they can decode particular types of model
   (e.g. GMMs), or with particular special conditions (e.g.  multi-class fMLLR).
   Examples of command-line programs that decode are gmm-decode-simple,
   gmm-decode-faster, gmm-decode-kaldi, and gmm-decode-faster-fmllr.  We have
   avoided creating a single command-line program that can do every possible kind
   of decoding, as this could quickly become hard to modify and debug.
  
   \section decodable_interface The Decodable interface
  
   In order to minimize the interaction between the decoder and the acoustic modeling 
   code, we have created a base class (DecodableInterface) which mediates between
   the decoder and the acoustic modeling code.  The DecodableInterface object can 
   be viewed as a wrapper for the pair (acoustic model, feature file).  This might
   seem a slightly unnatural object.  However, there is a good reason for its existence.
   The interaction between the acoustic model and the features can be quite
   complex (think about adaptation with multiple transforms), and by taking
   this out of the decoder we substantially simplify what the decoder has to know.
   The DecodableInterface object can be thought of as a matrix of size (number of frames)
   by (number of nonzero input labels on the graph).
  
   The basic operation of a decoder is to "decode this object of type DecodableInterface".
  
   The DecodableInterface object has only three functions:
  \verbatim
    virtual BaseFloat LogLikelihood(int32 frame, int32 index);
    virtual int32 NumFramesReady() const;
    virtual bool IsLastFrame(int32 frame);
    virtual int32 NumIndices();
  \endverbatim
   The function \ref DecodableInterface::LogLikelihood() "LogLikelihood()" returns
   the log-likelihood for this frame and index; the index would normally be the
   (one-based) transition-id, see \ref transition_model_identifiers.  The frame is
   a zero-based quantity.  The most normal DecodableInterface object will just look
   up the appropriate feature vector (using the index "frame"), work out the pdf-id
   corresponding to that transition-id, and return the corresponding acoustic log-likelihood.
   Acoustic probability scales are also applied by the DecodableInterface object,
   but they are not part of its generic interface because the interface represents
   the minimum that the decoder "needs to know", and it does not need to know
   about the probability scales.
  
   The \ref DecodableInterface::NumFramesReady() "NumFramesReady()" function
   returns the number of frames currently available.  In an offline, batch-mode setting
   this will equal the number of frames in the file.  In an online setting this will
   be the number of frames we have already captured and processed into features, 
   and it will likely increase with time.  
   The \ref DecodableInterface::IsLastFrame() "IsLastFrame()" function is an older
   mechanism for online decoding; it returns true if the given frame is the last one
   (in the old online-decoding mechanism, which is still supported for back compatibility,
   the call to the IsLastFrame() function would block if it was not the last frame
   but the data was not yet available.
  
   \section decoders_simple SimpleDecoder: the simplest possible decoder
  
   As an illustration of a "prototypical" decoder, consider the class SimpleDecoder.
   This very simple decoder has been included mostly for reference and for debugging
   more highly optimized decoders.  
  
   \subsection decoders_simple_itf Interface of SimpleDecoder
  
   The constructor of SimpleDecoder takes the FST to decode with, and a decoding beam:
  \verbatim
    SimpleDecoder(const fst::Fst<fst::StdArc> &fst, BaseFloat beam);
  \endverbatim
  Decoding an utterance is accomplished by the following function:
  \verbatim
    void Decode(DecodableInterface &decodable);
  \endverbatim
  Here is an example code fragment where we construct a Decodable object and decode it:
  \verbatim
    DecodableAmDiagGmmScaled gmm_decodable(am_gmm, trans_model, features,
                                           acoustic_scale);
    decoder.Decode(gmm_decodable);
  \endverbatim
  The type DecodableAmDiagGmmScaled is a very simple object that, given
  a transition-id, works out from trans_model (type: TransitionModel) the appropriate
  pdf-id, gets the corresponding row from the features (type: Matrix<BaseFloat>),
  works out the likelihood from am_gmm (type: AmDiagGmm), and scales it by 
  acoustic_scale (type: float).
  
  After calling this, we can get the traceback with the following call:
  \verbatim
    bool GetBestPath(Lattice *fst_out);
  \endverbatim
  The output is formatted as a lattice but contains only one path.
  The lattice is a finite-state transducer whose input and output labels are whatever
  labels were on the FST (typically transition-ids and words, respectively), and
  whose weights contain the acoustic, language model and transition weights.
  
   \subsection decoders_simple_workings How SimpleDecoder works
   
   This decoder stores tracebacks at the token level that are garbage collected.
   The token is of type SimpleDecoder::Token, which has the following member
   variables:
  \verbatim
    class Token {
     public:
      Arc arc_;
      Token *prev_;
      int32 ref_count_;
      Weight weight_;
      ...
  \endverbatim
   The member of type Arc (this is a typedef to fst::StdArc) is a
   copy of the arc in the original FST, except it has the acoustic
   likelihood contribution added in.  It contains the input and output
   labels, the weight and the next state (in the FST).  The "prev_"
   member is the traceback; the "ref_count_" is used in the garbage
   collection algorithm; the "Weight" is a typedef to fst::StdArc::Weight
   but essentially it just stores a floating-point value which represents
   the accumulated cost up to this point.
  
   Class SimpleDecoder contains just four data members, declared as follows:
  \verbatim
    unordered_map<StateId, Token*> cur_toks_;
    unordered_map<StateId, Token*> prev_toks_;
    const fst::Fst<fst::StdArc> &fst_;
    BaseFloat beam_;
  \endverbatim
   The last two of these (the FST and the beam) are constant during decoding.  
   The members "cur_toks_" and "prev_toks_" store the currently active tokens
   for the current and previous frame respectively.  The central loop of
   the \ref SimpleDecoder::Decode() "Decode()" function is as follows:
  \verbatim
  for(int32 frame = 0; !decodable.IsLastFrame(frame-1); frame++) {
    ClearToks(prev_toks_);
    std::swap(cur_toks_, prev_toks_);
    ProcessEmitting(decodable, frame);
    ProcessNonemitting();
    PruneToks(cur_toks_, beam_);
  }
  \endverbatim
  These statements are all self-explanatory except for ProcessEmitting() and
  ProcessNonemitting().  The ProcessEmitting() function propagates tokens from
  prev_toks_ (i.e. the previous frame) to cur_toks_ (i.e. the current frame).
  It only considers emitting arcs (i.e. arcs with nonzero input label).  
  For each token (say "tok") in prev_toks_, it looks at the state associated with the
  token (in tok->arc_.nextstate), and for each arc out of that state that
  is emitting, it creates a new token with a traceback to "tok" and with an "arc_" field
  coped from that arc, except with the associated weight updated to include
  the acoustic contribution.   The "weight_" field, representing the accumulated
  cost up to this point, will be the sum (the product, in the semiring interpretation) 
  of tok->weight_ and the weight of the recently added arc.  Each time we attempt to
  add a new token to "cur_toks_", we have to make sure there is no existing token
  associated with the same FST state.  If there is, we keep only the best.
  
  The function ProcessNonemitting() deals only with cur_toks_ and not with prev_toks_;
  it propagates nonemitting arcs, i.e. arcs with zero/\<eps\> as the input label/symbol.
  The newly created tokens will point back to other tokens in cur_toks_.  The weights
  on the arcs will just be the weights from the FST.  ProcessNonemitting() may have to
  process chains of epsilons.   It uses a queue to store states that need to be processed.
  
  After decoding, the function GetOutput(), discussed above, will trace back from the
  most likely token at the final state (taking into account its final probability,
  if is_final==true), and produce a linear FST with one arc for each arc in the traceback
  sequence.  There may be more of these than the number of frames, since there are
  separate tokens created for nonemitting arcs.  
  
   \section decoders_faster FasterDecoder: a more optimized decoder
  
   The decoder FasterDecoder has almost exactly the same interface as
   SimpleDecoder.  The only important new configuration value is "max-active",
   which controls the maximum number of states that can be active at one time.
   Apart from enforcing the max-active states, the only major difference is a
   data-structure related one.  We replace the type std::unordered_map<StateId,
   Token*> with a new type HashList<StateId, Token*>, where HashList is our own
   templated type created for this purpose.  HashList stores a singly-linked-list
   structure whose elements are also accessible via a hash table, and it offers the
   capability to free up the hash table for a new list structure while giving
   sequential access to the old list structure.  This is so that we can use the
   hash table to access what in SimpleDecoder was cur_toks_, while still having
   access to what in SimpleDecoder was prev_toks_, in the form of a list.
  
   The main pruning step FasterDecoder takes place in ProcessEmitting.
   Conceptually what is happening is that we take the tokens in what in
   SimpleDecoder was prev_toks_, and just before ProcessEmitting we prune using the
   beam and specified maximum number of active states (whichever is tighter).  The
   way this is actually implemented is that we call a function \ref
   FasterDecoder::GetCutoff() "GetCutoff()", which returns a weight cutoff value
   "weight_cutoff" that corresponds to the tighter of these two criteria; this
   cutoff value applies to the tokens in prev_toks_.  Then when we go through
   prev_toks_ (this variable does not exist in FasterDecoder, but conceptually), we
   only process those tokens better than the cutoff.
  
   The code in FasterDecoder as it relates to cutoffs is a little more complicated
   than just having the one pruning step.  The basic observation is this: it's pointless
   to create a very large number of tokens if you are only going to ignore most of them
   later.  So the situation in ProcessEmitting is: we have "weight_cutoff" but
   wouldn't it be nice if we knew what the value of "weight_cutoff" on the next
   frame was going to be?  Call this "next_weight_cutoff".  Then, whenever we process
   arcs that have the current frame's acoustic likelihoods, we could just avoid
   creating the token if the likelihood is worse than "next_weight_cutoff".  In order
   to know the next weight cutoff we have to know two things.  We have to know the
   best token's weight on the next frame, and we have to know the effective beam
   width on the next frame.  The effective beam width may differ from "beam" if the
   "max_active" constraint is limiting, and we use the heuristic that the effective
   beam width does not change very much from frame to frame.  
   We attempt to estimate the best token's
   weight on the next frame by propagating the currently best token (later on,
   if we find even better tokens on the next frame we will update this estimate).  We
   get a rough upper bound on the effective beam width on the next frame by using the
   variable "adaptive_beam".  This is always set to the smaller of "beam" (the
   specified maximum beam width), or the effective beam width as determined by
   max_active, plus beam_delta (default value: 0.5).  When we say it is a "rough upper bound"
   we mean that it will usually be greater than or equal to the effective beam
   width on the next frame.  
   The pruning value we use when creating new tokens equals our current estimate of
   the next frame's best token, plus "adaptive_beam".  With finite "beam_delta", it
   is possible for the pruning to be stricter than dictated by the "beam" and
   "max_active" parameters alone, although at the value 0.5 we do not believe this
   happens very often.
   
   \section decoders_biglm BiglmDecoder: decoding with large language models.
  
   There are two basic ways in Kaldi to use large language models (i.e. language
  models larger than a few million arcs, for which it would be difficult to successfully
  build the decoding graph).  One way is to generate a lattice using a small LM,
  and to rescore this lattice with a large LM (see \ref decoders_lattice below,
  and also \ref lattices).  The other way is to use a "biglm" decoder, e.g.
  \ref BiglmFasterDecoder.  The basic idea is to create the decoding graph HCLG
  with a small grammar, and compose dynamically with the difference
  between a large grammar and the small grammar.  Note that while we use the word
  "grammar" for compatibility with the standard notation, we have in mind a statistical 
  language model.  Imagine that the small grammar is G (an FST), and the large one
  is G'.  The basic idea is to search, in decoding time, the graph formed by
  the triple composition \f$ HCLG \circ G^- \circ G' \f$, where \f$G^T-\f$
  is like \f$G\f$ but with its scores negated.
  We'll give the high-level idea of how we do this first.
  We construct an on-demand composed FST, call it F, which is \f$F = G^- \circ G' \f$.
  Then while decoding, we construct on-demand the FST \f$HCLG \circ F\f$.  The
  problem with this is that we would always take the worst-scoring path through G,
  e.g. improperly take the backoff arc, which would make the subtraction of the
  original FST scores incorrect.
  
  The way we solve the problem above is to use some knowledge about the structure of $G$ and $G'$
  (we assume they are are ARPA-style language models), and treat them as 
  epsilon-free, deterministic FSTs.  That is: when searching for 
  an arc from a particular state with a particular
  input label, if we find that input label we take it (and return just that arc),
  otherwise we follow the epsilon transition, and recursively look for an arc with
  that label.   In terms of the external interface of the FST, it looks like
  there was an arc from the original state (i.e. it looks like a
  language model FST that has been subjected to epsilon removal).
  We created a special interface for this type of FST,
  which we call fst::DeterministicOnDemandFst; it has a new function GetArc(),
  which finds the arc with a particular input label, if it exists (by assumption,
  there cannot be more than one).  Both G and G' are of type 
  fst::DeterministicOnDemandFst, and so is their composition.  This means that
  the decoder doesn't have to implement a generic composition algorithm;
  instead, whenever it crosses an arc in HCLG, it has only to update the language-model
  state (a state-identifier in F).  The decoding algorithm is almost exactly the
  same as for the baseline, except the state-space (a hash index that we use)
  is not just the state in HCLG, but a pair of (state in HCLG, state in F).
  There is no subtantial extra work introduced by this, but this decoder is
  still a bit slower (e.g. nearly twice as slow in a typical setup) versus
  a decoder with the same beam, without the "biglm" part.  The reason seems 
  to be that with the biglm decoder, more states are in the beam (because a
  state in HCLG may now have more ``copies'', corresponding to different 
  different histories with distinct langauage model states in HCLG.  However,
  with the same beam, the biglm decoder does give better accuracy than
  lattice rescoring of lattices produced with a small grammar.  The reason,
  we believe, is better pruning: the ``biglm'' decoder does the Viterbi
  beam pruning with closer-to-optimal language model scores.  Of course, it
  is still not as good pruning as we would get by using a HCLG compiled
  with the big grammar, because the biglm decoder only updates the
  ``good'' language model score every time it crosses a word.
  
  
  \section decoders_lattice Lattice generating decoders
  
   There are lattice-generating versions of some of the decoders described above.
  There is \ref LatticeFasterDecoder, \ref LatticeSimpleDecoder, and 
  \ref LatticeBiglmFasterDecoder.  See \ref lattices for more details on lattice
  generation.  
  
  
  
  */
  
  
  }