// doc/hmm.dox
  
  
  // Copyright 2009-2011 Microsoft Corporation
  
  // 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 hmm HMM topology and transition modeling
  
   \section hmm_intro Introduction
  
   In this page we describe how HMM topologies are represented by Kaldi and
   how we model and train HMM transitions.  We briefly mention how this interacts
   with decision trees; decision trees are covered more fully in \ref tree_externals and
   \ref tree_internals.  For a list of classes and functions in this group, see
   \ref hmm_group
  
   \section hmm_topology  HMM topologies
  
   The class HmmTopology is the way the user specifies to the toolkit the topology
   of the HMMs the phones.  In the normal recipe, the scripts create
   in a file the text form of the HmmTopology object, which is then given to the
   command-line programs.  To give some idea of what this object contains, below
   is the text format for the HmmTopology object in the "normal" case (the
   3-state Bakis model):
  \verbatim
   <Topology>
   <TopologyEntry>
   <ForPhones> 1 2 3 4 5 6 7 8 </ForPhones>
   <State> 0 <PdfClass> 0
   <Transition> 0 0.5
   <Transition> 1 0.5
   </State>
   <State> 1 <PdfClass> 1
   <Transition> 1 0.5
   <Transition> 2 0.5
   </State>
   <State> 2 <PdfClass> 2
   <Transition> 2 0.5
   <Transition> 3 0.5
   </State>
   <State> 3
   </State>
   </TopologyEntry>
   </Topology>
  \endverbatim
  There is one TopologyEntry in this particular HmmTopology object, and it covers
  phones 1 through 8 (so in this example there are just eight phones and they all
  share the same topology).  There are three emitting states (i.e. states that
  have pdfs associated with them and 'emit' feature vectors); each has a self-loop
  and a transition to the next state.  There is also a fourth, non-emitting state,
  state 3 (there is no \<PdfClass\> entry for it) which has no transitions out of it
  (implicitly, it connects to the next phone in the sequence).
  This is
  a standard feature of these topology entries; Kaldi treats the first state (state
  zero) as the start state, and the last state, which should always be nonemitting and
  have no transitions out of it, has final-probability one.  You
  can treat the transition-probability to the last state as equivalent to the
  "final-probability" in a HMM.
  All of emitting the states in this particular example can have different pdf's in
  them (since the PdfClass numbers are all distinct).  We can enforce tying by
  making the \<PdfClass\> numbers the same.
  The probabilities given in the HmmTopology object are those that are used to
  initialize training; the trained probabilities are specific to the
  context-dependent HMMs and are stored in the TransitionModel object.  The
  TransitionModel stores the HmmTopology object as a class member, but be aware
  that the transition probabilities in the HmmTopology object are generally not
  used after initializing the TransitionModel object.  There is an exception to
  this, however; for nonemitting states that are non-final (i.e. those that have
  transitions out of them but no \<PdfClass\> entry), Kaldi does not train the
  transition probabilities and instead it uses the probabilities given in the
  HmmTopology object.  The decision not to support trainable transition probabilities
  for non-emitting states simplifies our training mechanisms, and since it is not
  normal to have non-emitting states with transitions, we felt that this was no
  great loss.
  
  
  \section pdf_class Pdf-classes
  
  The pdf-class is a concept that relates to the HmmTopology object.  The
  HmmTopology object specifies a prototype HMM for each phone.  Each
  numbered state of a
  "prototype HMM" has two variables "forward_pdf_class" and "self_loop_pdf_class".
  The "self_loop_pdf_class" is a kind of pdf-class that is associated
  with self-loop transition. It is by default identical to "forward_pdf_class",
  but it can be used to define less-conventional HMM topologies
  where the pdfs on the self-loop and forward transitions are different.
  The decision to allow the pdf-class on just the self-loop to be different,
  while not embracing a fully "arc-based" representation where the pdfs on
  all transitions in the HMM are potentially independent, was made as a compromise,
  to allow for compatibility with previous versions of Kaldi while supporting the topology
  used in our "chain models" AKA lattice-free MMI.
  If two states have the same
  pdf_class variable, then they will always share the same probability
  distribution function (p.d.f.) if they are in the same phonetic context.  This
  is because the decision-tree code does not get to "see" the HMM-state directly,
  it only gets to see the pdf-class.  In the normal case the pdf-class is the same
  as the HMM state index (e.g. 0, 1 or 2), but pdf classes provide a way for the
  user to enforce sharing.  This would mainly be useful if you wanted richer
  transition modeling but wanted to leave the acoustic model otherwise the same.
  Another function of the pdf-class is to specify nonemitting states.  If the
  pdf-class for some HMM state is set to the constant \ref kNoPdf = -1, then the
  HMM state is nonemitting (it has no associated pdf).  This can be achieved
  simply by omitting the \<PdfClass\> tag and associated number, in the text form of the object.
  
  The set of pdf-classes for a particular prototype HMM is expected to start
  from zero and be contiguous (e.g. 0, 1, 2).  This is for the convenience of
  the graph-building code, and does not lead to any loss of generality.
  
  \section transition_model Transition models (the TransitionModel object)
  
  The TransitionModel object stores the transition probabilities and information
  about HMM topologies (it contains a HmmTopology object).
  The graph-building code depends on the TransitionModel object to get
  the topology and transition probabilities (it also requires a ContextDependencyInterface
  object to get the pdf-ids associated with particular phonetic contexts).
  
   \subsection transition_model_how How we model transition probabilities in Kaldi
  
  The decision that underlies a lot of the transition-modeling code is as follows:
  we have decided to make the transition probability of a
  context dependent HMM state depend on the following five things (you could view
  them as a 5-tuple):
    - The phone (whose HMM we are in)
    - The source HMM-state (as interpreted by the HmmTopology object, i.e.  normally 0, 1 or 2)
    - The \ref pdf_id "forward-pdf-id"
      (i.e. the index of the forward transition pdfs associated with the state)
    - The \ref pdf_id "self-loop-pdf-id"
      (i.e. the index of the self-loop pdfs associated with the state)
    - The index of the transition in the HmmTopology object.
  
  The last of these four items could be viewed as encoding the destination
  HMM-state in the HmmTopology object.
  The reason for making the transition probabilities depend on these things,
  is that this is the most fine-grained way we could model transitions without
  increasing the size of the compiled decoding graphs; it is also quite convenient
  for training the transition probabilities.  In practice, with conventional setups
  it probably does not make any difference to model the transitions as precisely
  as this, and the HTK approach of sharing the transitions at the monophone level
  would probably be sufficient.
  
   \subsection transition_model_mappings The reason for transition-ids etc.
  
  The TransitionModel object sets up a number of integer mappings when it is
  initialized, and is used by other parts of the code to perform these mappings.
  Apart from the quantities mentioned above, there are quantities called
  transition identifiers (transition-ids), transition indexes (which are not
  the same thing as transition-ids), and transition states.  The reason we
  have introduced these identifiers and the associated mappings is so that we can
  use a completely FST-based training recipe.  The most "natural" FST-based setups
  would have what we call pdf-ids on the input labels.  However, bearing in mind
  that given our tree-building algorithms it will not always be possible to map
  uniquely from a pdf-id to a phone, this would make it hard to map from an input-label
  sequence to a phone
  sequence, and this is inconvenient for a number of reasons;
  it would also make it hard in general to train the transition probabilities using
  the information in the FST alone.  For this reason we put
  identifiers called transition-ids on the input labels of the FST, and these can be mapped
  to the pdf-id but also to the phone and to a particular transition in a
  prototype HMM (as given in the HmmTopology object).
  
  \subsection transition_model_identifiers Integer identifiers used by TransitionModel
  
   The following types of identifiers are used in the TransitionModel interface.  All of
   them are represented as type int32.  Note that some of these quantities are one-based
   indices and some are zero-based.  We have tried to avoid one-based indices as
   much as possible in the toolkit
   because they are not very compatible with C++ array indexing, but because OpenFst
   treats zero as a special case (meaning the special symbol epsilon), we have decided
   to allow one-based indexing for quantities that frequently appear as input symbols
   on FSTs.  Most importantly, transition-ids are one based.
   Since we do not imagine \ref pdf_id "pdf-ids" appearing very frequently as
   FST labels, and since we often use them as C++ array indexes, we have decided
   to make them zero-based but if they appear as FST input symbols (which should be
   rarely) we add one to them.
   When reading the TransitionModel code, be aware that when indexing arrays with
   one-based quantities there are cases where we subtract one and some cases where we do not;
   this is documented where the member variables are declared.  In any case, such code
   is not in the public interface so it should not lead to too much confusion.
   A complete list of the various integer quantities used in TransitionModel are as follows:
  
      - phone (one-based): this type of identifier is used throughout the toolkit; it
          can be converted to a phone name via an OpenFst symbol table.  Not necessarily
          contiguous (the toolkit allows "skips" in the phone indices).
      - hmm-state (zero-based): this is an index into something of type HmmTopology::TopologyEntry.
          In the normal case, it is one of {0, 1, 2}.
      - pdf, or pdf-id (zero-based): this is the index of the p.d.f., as
         originally allocated by the decision-tree clustering; (see \ref pdf_id).
         There would normally be several thousand pdf-ids in a system.
      - transition-state, or trans_state (one-based): this is an index that is defined
        by the TransitionModel itself.  Each possible triple of (phone, hmm-state, pdf)
        maps to a unique transition-state.  Think of it is the finest granularity of
        HMM-state for which transitions are separately estimated.
      - transition-index, or trans_index (zero-based): this is an index into the
       "transitions" array of type HmmTopology::HmmState.  It numbers the
       transitions out of a particular transition-state.
      - transition-id, or trans_id (one-based): each of these corresponds to a
        unique transition probability in the transition model.  There is a mapping
        from (transition-state, transition-index) to transition-id, and vice versa.
  
    There are also in the transition-modeling code reference to the following concepts:
      - A tuple means a 4-tuple (phone, hmm-state, forward pdf, self-loop pdf) which is mappable to and from a transition-state.
      - A pair means a pair (transition-state, transition-index) which is mappable to and from a transition-id.
  
  \section hmm_transition_training Training the transition model
  
    The training procedure for the transition model is very simple.  The FSTs that
    we create (for both training and test) have transition-ids as their input
    labels.  In training we do a Viterbi decoding that gives us the input-label
    sequence, which is a sequence of transition-ids (one for each feature vector).
    The statistics we accumulate for training transitions are essentially counts of
    how many times each transition-id was seen in training (the code itself uses
    floating-point occupation counts but these are just integers in our normal
    training setup).  The function Transition::Update() does the ML update for each
    transition-state.  This works in the "obvious" way.  There are also some minor
    issues related to probability flooring and what to do if a particular
    transition-state is unseen; for these details, see the code.
  
   \section hmm_alignment Alignments in Kaldi
  
    At this point we introduce the concept of an alignment.  By "alignment", we
    generally mean something of type  vector<int32>, which contains a sequence
    of transition-ids (c.f. \ref transition_model_identifiers) whose length is
    the same as the utterance the alignment corresponds to.  This sequence of transition-ids
    would generally be obtained from the decoder as the input-label sequence.
    Alignments are used in training time for Viterbi training, and in test time
    for adaptation.  Because transition-ids encode
    the phone information, it is possible to work out the phonetic sequence from
    an alignment (c.f. SplitToPhones() and ali-to-phones.cc).
  
    We often need to deal with collections of alignments indexed by utterance.
    To do this conveniently, we read and write alignments with tables;
    see \ref table_examples_ali for more information.
  
    The function \ref ConvertAlignment() (c.f. the command-line program \ref
    convert-ali.cc "convert-ali") converts alignments from one transition-model to
    another.  The typical case is where you have alignments created using one
    transition-model (created from a particular decision tree) and want to convert
    them to be valid for another transition model with a different tree.  It
    optionally takes a mapping from the original phones to a new phone set; this
    feature is not normally needed but we have used it when dealing with simplified models
    based on a reduced (clustered) phone set.
  
    Programs that read in alignments generally have the suffix "-ali".
  
   \section hmm_post State-level posteriors
  
    State-level posteriors are an extension of the "alignment" concept (previous section),
    except that instead of having a single transition-id per frame we have an arbitrary
    number of transition-ids per frame, and each one has a weight.  It is stored in
    the following type of structure:
  \verbatim
  typedef std::vector<std::vector<std::pair<int32, BaseFloat> > > Posterior;
  \endverbatim
    where if we have an object "post" of type Posterior, post.size() will be equal
    to the length of the utterance in frames, and post[i] is a list of pairs (stored
    as a vector), where each pair consists of a (transition-id, posterior).
  
   In the current programs, there are only two ways to create posteriors: either
     - By converting alignments to posteriors using the program ali-to-post, which
       gives us a rather trivial Posterior object where each frame has a single transition-id
       with unit posterior
     - By modifying posteriors using the program weight-silence-post, which is usually
       used to weight down the posteriors corresponding to silence phones.
  
   In future, when lattice generation is added, we will add utilities to create posteriors
   from lattices.
  
   Programs that read in posteriors don't have a suffix comparable to "-ali", which is the
   suffix for programs that read in alignments.  This is for brevity; reading in
   state-level posteriors is considered the "default" behavior of programs that
   need this type of alignment information.
  
   \section hmm_gpost Gaussian-level posteriors
  
   A set of Gaussian-level posteriors for an utterance may be stored using the
   following typedef:
  \verbatim
  typedef std::vector<std::vector<std::pair<int32, Vector<BaseFloat> > > > GauPost;
  \endverbatim
   This is like the Posterior structure, except the floating-point value (which represents
   the posterior of the state) is now a vector of floating-point values, one for
   each Gaussian in the state.  The size of the vector would be the same as the
   number of Gaussians in the pdf corresponding to the transition-id which is the
   first element of the pair.
  
   The program post-to-gpost converts Posterior structures into GauPost structures; it
   uses the model and the features to compute the Gaussian-level posteriors.  This
   is mainly useful in situations where we may need to compute Gaussian-level posteriors
   with a different model or features than the ones we need to accumulate statistics
   with.  Programs that read in Gaussian-level posteriors have the suffix "-gpost".
  
  \section hmm_graph Functions for converting HMMs to FSTs
  
  A complete list of functions and classes involved in converting HMMs to FSTs may
  be found \ref hmm_group_graph "here".
  
   \subsection hmm_graph_get_h_transducer GetHTransducer()
  
  The most important one is the function
  GetHTranducer(), declared as follows:
  \code
  fst::VectorFst<fst::StdArc>*
  GetHTransducer (const std::vector<std::vector<int32> > &ilabel_info,
                  const ContextDependencyInterface &ctx_dep,
                  const TransitionModel &trans_model,
                  const HTransducerConfig &config,
                  std::vector<int32> *disambig_syms_left);
  \endcode
  There are aspects of this function which will be hard to understand
  without having first understood the \ref tree_ilabel "ilabel_info" object,
  the \ref tree_ctxdep "ContextDependencyInterface" interface, and at
  least the basics of how FSTs are used in speech recognition.  This function
  returns an FST whose input labels are \ref transition_model_identifiers "transition-ids"
  and whose output labels represent context-dependent phones (they are
  indices into the \ref tree_ilabel "ilabel_info" object).  The FST it
  returns has a state that is both initial and final, and all the transitions out
  of it have output-labels (for efficient composition with CLG).  Each transition
  out of it will typically enter a structure representing a 3-state HMM, and
  then loop back to the initial state.  The FST returned
  GetHTransducer() will only be valid for the phonetic contexts represented
  in ilabel_info, which the caller can specify.
  This is useful because for wide-context systems there can
  be a large number of contexts, most of which are never used.  The ilabel_info
  object can be obtained from the ContextFst object (which represents C) after
  composing it with something, and it contains just the contexts that have
  been used.  We would then provide this same ilabel_info object to
  GetHTransducer() to get an H transducer that covers everything we need.
  
  Note that GetHTransducer() function does not include the self-loops.  These
  must be added later by the function AddSelfLoops(); it is normally convenient
  to only add the self-loops after all stages of decoding-graph optimization.
  
  \subsection hmm_graph_config The HTransducerConfig configuration class
  
  The HTransducerConfig configuration class controls the behavior of
  GetHTransducer.
  
    - The variable \ref HTransducerConfig::trans_prob_scale
      "trans_prob_scale" is the transition probability scale.  When transition
      probabilities are included in the graph, they are included with this scale.
      As a command-line option this is called --transition-scale.
      See \ref hmm_scale for a discussion of the appropriate scale to use.
  
  \subsection hmm_graph_get_hmm_as_fst The function GetHmmAsFst()
  
  The function GetHmmAsFst() takes a phonetic context window and returns
  the corresponding finite state acceptor with transition-ids as the symbols.
  This is used in GetHTransducer().  A function GetHmmAsFstSimple() that
  takes fewer options is also provided as a form of documentation,
  in order to show in principle how the process works.
  
  \subsection hmm_graph_add_self_loops AddSelfLoops()
  
   The AddSelfLoops() function adds self-loops to a graph that has been
   created without self-loops.  A typical setup is to create the H transducer
   without self-loops, compose with CLG, do determinization and minimization,
   and then add the self-loops.  This enables more efficient determinization and
   minimization.  The AddSelfLoops() function has the option to reorder the
   transitions; see below \ref hmm_reorder for more details on this.  It also
   takes a transition-probability scale, "self_loop_scale", which does not
   have to be the same as the normal transition-probability scale; for more
   on this, see below \ref hmm_scale.
  
  \subsection hmm_graph_add_transition_probs Adding transition probabilities to FSTs
  
   The AddTransitionProbs() function adds transition probabilities to an FST.
   The reason this is useful is so that graphs can be created without transition
   probabilities on them (i.e. without the component of the weights that arises
   from the HMM transitions), and these can be added in later; this makes it
   possible to use the same graph on different iterations of training the
   model, and keep the transition-probabilities in the graph up to date.
   Creating the graph without transition-probabilities is accomplished by
   using a zero value for trans_prob_scale (command-line option: --transition-scale).
   In training time, our scripts tend to store the
   graphs on disk without the transition probabilities, and then each time we
   realign we add in the currently valid transition probabilities.
  
  \section hmm_reorder Reordering transitions
  
   The AddSelfLoops() function takes a boolean option "reorder" which
   tells it to reorder transion-probabilities so the self-loop comes after
   the transition out of the state.  Where applicable this becomes a
   boolean command-line option, e.g. you can do --reorder=true to enable
   reordering during graph creation.  This option makes the "simple" and
   "faster" decoders more efficient (see \ref decoders), although it is
   not compatible with the "kaldi" decoder.
  
   The idea of reordering is that we switch the order of the self-loop arcs
   with all the other arcs that come out of a state, so the self-loop is
   located at the destination state of each of the other arcs.  For this
   to work, we have to ensure that the FST has
   certain properties, namely that all the arcs into a particular state must
   induce the same self-loop (also, a state with a self-loop cannot have
   input arcs with epsilon inputs, or be the start state).  The AddSelfLoops()
   function modifies the graphs to ensure that they have this property.  A similar
   property is required even if the "reorder" option is set to false.
   The graphs created with the "reorder" option are exactly equivalent to the
   non-reordered graphs in terms
   of the acoustic and transition-model probabilities you get when decoding
   an utterance.  The transition-ids on the resulting alignment are in a different
   order, but this does not matter given the ways that we make use of these
   alignments.
  
  
  \section hmm_scale Scaling of transition and acoustic probabilities
  
  There are three types of scaling that can be applied in Kaldi:
    <table border="1">
  <tr>
  <td> Name in code</td> <td> Name in command-line arguments</td> <td> Example value (train) </td> <td> Example value (test) </td>
  </tr>
  <tr>
  <td> acoustic_scale </td> <td> --acoustic-scale=? </td> <td> 0.1 </td> <td> 0.08333 </td>
  </tr>
  <tr>
  <td> self_loop_scale </td> <td> --self-loop-scale=? </td> <td> 0.1 </td> <td> 0.1 </td>
  </tr>
  <tr>
  <td> transition_scale </td> <td> --transition-scale=? </td> <td> 1.0 </td> <td> 1.0 </td>
  </tr>
  </table>
  
  You may notice that there is no language model scale on this list; everything is
  scaled relative to the language model.  Also we don't support a word insertion
  penalty, in general (although the "kaldi" decoder does support this).
  The idea is that the language model represents "real"
  probabilities so it makes sense to scale everything else relative to them.
  The scales during training time are the scales we use in decoding to get Viterbi
  alignments.  In general, we use a figure of 0.1 whenever a parameter is not to
  critical and is expected to be small.  The acoustic scale used during
  test is quite critical and is typically tuned to the task.
  We now explain what these three scales do:
  
    - The acoustic scale is the scale applied to the acoustics (i.e. to the log-likelihood
      of a frame given an acoustic state).
    - The transition scale is the scale on the transition probabilities, but this only
     applies to HMM states that have multiple transitions out of them; it applies to the
     relative weight between such transitions.  It does not have any effect for typical
     topologoes.
    - The self-loop scale is the scale that we apply to the self-loops.  More specifically,
     when we add the self-loop, let the probability mass given to the self-loop be p
     and the mass given to the rest be (1-p).  We add a self-loop with log-probability
     self_loop_scale * log(p), and add (self_loop_scale * log(1-p)) to all the other
     log transition probabilities out of that state.  (Note: in the initial stage of
     graph creation we create a graph without self-loops, and with the non-self-loop
     transition probabilities renormalized to sum to one).  In typical topologies, the
     self-loop scale is the only scale that matters.
  
  The reason we feel it might make sense to apply a different probability scale to
  the self-loops versus the normal transition scale is we think they could be
  dictating the probabilities of events at different timescales.  A slightly more
  subtle argument is the following.  All the transition probabilities can be
  regarded as "real" probabilities (comparable to LM probabilities), because the
  problem of correlation between acoustic probabilities does not occur for
  transitions.  However, a problem arises because we use the Viterbi algorithm in
  testing (and in our case, in training too).  The transition probabilities would
  only represent real probabilities when summed over, as in the forward-backward
  algorithm.  We expect this to be more of an issue for the self-loops than for
  probabilities that dictate the weight to give entirely different paths through
  the HMM, as in the latter case the acoustic distributions will often be quite
  disjoint, and the difference between forward-backward and Viterbi will be
  small.
  
  
  
  
  
  
  
  */
  
  
  /**
    \defgroup hmm_group Classes and functions related to HMM topology and transition modeling
  
  
  
  */
  
  }