// doc/chain.dox
  
  // Copyright 2015   Johns Hopkins University (author: Daniel Povey)
  
  // 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 chain 'Chain' models
  
    \section chain_intro Introduction to 'chain' models
  
    The 'chain' models are a type of DNN-HMM model, implemented using \ref dnn3 "nnet3", and differ from the
    conventional model in various ways; you can think of them as a different
    design point in the space of acoustic models.
  
     - We use a 3 times smaller frame rate at the output of the neural net,
       This significantly reduces the amount of computation required in
       test time, making real-time decoding much easier.
     - The models are trained right from the start with a sequence-level
       objective function-- namely, the log probability of the correct sequence.  It is
       essentially MMI implemented without lattices on the GPU, by doing a full
       forward-backward on a decoding graph derived from a phone n-gram language
       model.
     - Because of the reduced frame rate, we need to use unconventional
       HMM topologies (allowing the traversal of the HMM in one state).
     - We use fixed transition probabilities in the HMM, and don't train
       them (we may decide train them in future; but for the most part the neural-net
       output probabilities can do the same job as the transition probabilities,
       depending on the topology).
     - Currently, only nnet3 DNNs are supported (see \ref dnn3), and
       online decoding has not yet been implemented (we're aiming for April to June 2016).
     - Currently the results are a bit better then those of conventional
       DNN-HMMs (about 5\% relative better), but the system is about 3 times
       faster to decode; training time is probably a bit faster too, but
       we haven't compared it exactly.
  
    \section chain_scripts  Where to find scripts for the 'chain' models
  
    The current best scripts for the 'chain' models can be found in the
    Switchboard setup in egs/swbd/s5c; the script local/chain/run_tdnn_2o.sh is
    the current best one.  This is currently available in the 'chain' branch of
    the official github repository (https://github.com/kaldi-asr/kaldi.git) and
    eventually will be merged to the master.
  
    This script uses TDNNs as the neural net (we've been doing the development
    with TDNNs because they are easier to tune then LSTMs), and gives a better WER
    WER than the baseline TDNN: 11.4\%, versus 12.1\% for the best TDNN baseline
    (on the Switchboard-only portion of eval2000).
  
    \section chain_model  The chain model
  
    The chain model itself is no different from a conventional DNN-HMM, used with
    a (currently) 3-fold reduced frame rate at the output of the DNN.  The input
    features of the DNN are at the original frame rate of 100 per second; this makes
    sense because all the neural nets we are currently using (LSTMs, TDNNs) have some kind
    of recurrent connections or splicing inside them, i.e. they are not purely feedforward
    nets.
  
    The difference from a normal model is the objective function used to train it:
    instead of a frame-level objective, we use the log-probability of the correct
    phone sequence as the objective function.  The training process is quite
    similar in principle to MMI training, in which we compute numerator and
    denominator 'occupation probabilities' and the difference between the two is
    used in the derivative computation.  There is no need to normalize the DNN
    outputs to sum to one on each frame any more- such normalization makes no difference.
  
    Because of the reduced frame rate (one frame every 30 ms), we need to use a
    modified HMM topology.  We would like the HMM to be traversable in one
    transition (as opposed to the 3 transitions of a model mat the normal frame
    rate).  The currently favored topology has a state that can only occur once,
    and then another state that can appear zero or more times.  The state-clustering
    is obtained using the same procedure as for GMM-based models, although
    of course with a different topology (we convert the alignments to the new topology
    and frame-rate).
  
    \section chain_training The training procedure for 'chain' models
  
    The training procedure for chain models is a lattice-free version of
    MMI, where the denominator state posteriors are obtained by the
    forward-backward algorithm over a HMM formed from a phone-level decoding graph,
    and the numerator state posteriors are obtained by a similar forward-backward
    algorithm but limited to sequences corresponding to the transcript.
  
    For each output index of the neural net (i.e. for each pdf-id), we
    compute a derivative of of the form (numerator occupation probability -
    denominator occupation probability), and these are propagated back to the
    network.
  
  
    \subsection chain_training_denominator  The denominator FST
  
    For the denominator part of the computation we do forward-backward over a HMM.
   Actually, because we represent it as a finite state acceptor, the labels
   (pdf-ids) are associated with the arcs and not the states, so it's not really a
   HMM in the normal formulation, but it's easier think of it as a HMM because
   we use the forward-backward algorithm to get posteriors.
   In the code and scripts we refer to it as the 'denominator FST'.
  
    \subsubsection chain_training_denominator_phone_lm Phone language model for the denominator FST
  
    The first stage in constructing the denominator FST is to create a phone
    language model.  This language model is learned from the training-data phone
    alignments.  This is an un-smoothed language model, meaning that we never do
    backoff to lower order n-grams.  However, some language-model states are
    removed entirely, so transitions to those states go instead to the lower-order
    n-gram's state.   The reason we avoid smoothing is to reduce the number of
    arcs that there will be in the compiled graph after phonetic context expansion.
  
   The configuration that we settled on is to estimate a 4-gram language model,
    and to never prune LM states below trigram (so we always maintain at least a
    2-phone history).  On top of the number of states dictated by the no-prune
    trigram rule, we have a specifiable number (e.g. 2000) of 4-gram language
    model states which are to be retained (all the rest are identified with the
    corresponding trigram state), and the ones we choose to retain are determined
    in a way that maximizes the training-data likelihood.  All probabilities are
    estimated to maximize the training-data likelihood.  The reason not to prune
    the trigrams is that any sparsity of which trigrams are allowed, will tend to
    minimize the size of the compiled graph.  Note that if our phone LM was just a
    simple phone loop (i.e. a unigram), it would get expanded to triphones anyway
    due to phonetic context effects, but it would have arcs for all possible
    trigrams in it.  So any sparsity we get from using the un-pruned trigram model
    is a bonus.  Empirically, an un-smoothed trigram LM is what expands to the
    smallest possible FST; and pruning some of the trigrams, while it increases
    the size of the compiled FST, results in little or no WER improvement (at
    least on 300 hours of data expanded 3-fold with speed perturbation; on less
    data it might help).
  
    On the Switchboard setups the phone-LM perplexities for the various models we
    tried were in the range 5 to 7; the phone-LM perplexity with our chosen
    configuration (4-gram, pruned to trigram for all but 2000 states) was about 6.
    It was not the case that lower phone-LM perplexity always led to better WER
    of the trained system; as for conventional (word-based) MMI training, an
    intermediate strength of language model seemed to work best.
  
   \subsubsection chain_training_denominator_compilation  Compilation of the denominator FST
  
    The phone language model described in the previous section is expanded into a
    FST with 'pdf-ids' as the arcs, in a process that mirrors the process of
    decoding-graph compilation in normal Kaldi decoding (see \ref
    graph_recipe_test), except that there is no lexicon is involved, and at the
    end we convert the transition-ids to pdf-ids.
  
    One difference lies in how we minimize the size of the graph.  The normal
    recipe involves determinization and minimization.  We were not able to
    reduce the size of the graph using this procedure, or variants of it with
    disambiguation symbols.  Instead, our graph-minimization process can be described
    compactly as follows: "Repeat 3 times: push, minimize, reverse; push, minimize reverse.".
    'push' refers to weight-pushing; 'reverse' refers to reversing the directions of arcs, and
    swapping initial and final states.
  
  
   \subsubsection chain_training_denominator_normalization Initial and final probabilities, and 'normalization FST'
  
    The graph-creation process mentioned above naturally gives us an initial
    state, and final probabilities for each state; but these are not the ones we
    use in the forward-backward.  The reason is that these probabilities are
    applicable to utterance boundaries, but we train on split-up chunks of
    utterance of a fixed length (e.g. 1.5 seconds).  Constraining the HMM at these
    arbitrarily chosen cut points to the initial and final states is not
    appropriate.  Instead, we use initial probabilities derived from 'running the HMM' for
    a fixed number of iterations and averaging the probabilities; and final probabilities
    equal to 1.0 for each state.  We have a justification for this but don't have time to
    explain it right now.  In the denominator forward-backward process we apply these initial and
    final probabilities to the initial and final frame as part of the computation.  However, we also
    write out a version of the denominator FST that has these initial and final probabilities, and we refer to
    this as the 'normalization FST.'  (The initial probabilities are emulated using epsilon arcs, because
    FSTs do not support initial probabilities).  This 'normalization FST' will be used to add probabilities to the
   numerator FSTs in a way that we'll describe later.
  
    \subsection chain_training_numerator  Numerator FSTs
  
   As part of our preparation for the training process we produce something
   called a 'numerator FST' for each utterance.  The numerator FST encodes the
   supervision transcript, and also encodes an alignment of that transcript
   (i.e. it forces similarity to a reference alignment obtained from a baseline
   system), but it allows a little 'wiggle room' to vary from that reference.
   By default we allow a phone to occur 0.05 seconds before or after its
   begin and end position respectively, in the lattice alignment.
   Incorporating the alignment information is important because of the way we
   train not on entire utterances but on split-up fixed-length pieces of
   utterances (which, in turn, is important for GPU-based training): splitting up
   the utterance into pieces if we know where the transcript aligns.
  
   Instead of enforcing a particular pronunciation of the training data, we use as
   our reference a lattice of alternative pronunciations of the training data,
   generated by a lattice-generating decoding procedure using an
   utterance-specific graph as the decoding graph.  This generates all alignments
   of pronunciations that were within a beam of the best-scoring pronunciation.
  
    \subsubsection chain_training_numerator_splitting Splitting the numerator FSTs
  
   As mentioned, we train on fixed sized pieces of utterances (e.g. 1.5 seconds in
   length).  This requires that we split up the numerator FSTs up into fixed-size
   pieces.  This isn't hard, since the numerator FSTs (which, remember, encode
   time-alignment information), naturally have a structure where we can identify
   any FST state with a particular frame index.  Note: at the stage where we do this
   splitting, there are no costs in the numerator FST yet-- it's just viewed as
   encoding a constraint on paths-- so we do not have to make a decision how to split up the costs
  on the paths.
  
    \subsubsection chain_training_numerator_normalization Normalizing the numerator FSTs
  
   Above (\ref chain_training_denominator_compilation) we mentioned how we compute
   initial and final probabilities for the denominator FST, and how we encode
   these in a 'normalization FST'.  We compose the split-up pieces of numerator
   FST with this this 'normalization FST' to ensure that the costs from the
   denominator FST are reflected in the numerator FST.  This ensures that
   objective functions can never be positive (which makes them easier to
   interpret), and also guards against the possibility that the numerator FST
   could contain state sequences not allowed by the denominator FST, which in
   principle could allow the objective function to increase without bound.  The
   reason why this could happen is that the phone LM lacks smoothing, and is
   estimated from 1-best alignments, so the lattices could contain phone n-grams
   sequences not seen in training.
  
   It happens occasionally (but very rarely) that this normalization process
   generates an empty FST: this can occur when the lattice contains triphones that
   were not not present in the 1-best alignment used to train the phone language
   model, and does not have any alternative paths at that point in the lattice
   that could make up for the resulting 'failed' paths.  This can happen because
   the 1-best alignment and the lattice-producing alignment chose different
   pronunciations of a word.  These pieces of utterances are just discarded.
  
    \subsubsection chain_training_numerator_format Format of the numerator FSTs
  
    The numerator FSTs are weighted acceptors where the labels correspond to
    pdf-ids plus one.  We can't use pdf-ids, because they could be zero; and zero
    is treated specially (as epsilon) by OpenFst.  When we form minibatches, instead
    of storing an array of separate numerator FSTs we actually append them together to form a longer FST;
    this enables us to do a single forward-backward over all utterances in the minibatch,
    which directly computes the total numerator log-probability.  (This isn't an important
    feature, it's just a software detail, which we explain here lest it generate confusion).
  
    \subsection chain_training_splitting  Fixed-length chunks, and minibatches
  
    In order to train on minibatches, we split up our utterances into fixed-length
    chunks of speech (of length 1.5 seconds in our current scripts).  Utterances
    shorter than this are discarded; those longer, are split into chunks with
    either overlaps between the chunks, or small gaps between the chunks.  Note that
    our acoustic models typically require left or right frames for acoustic
    context; we add that, but this is separate issue; the context is added after
    the chunks are decided on.
  
    Our minibatch size is usually a power of 2, and it can be limited by GPU
    memory considerations.  Many of our example scripts use 128 chunks per
    minibatch.  The largest single consumer of GPU memory is the alpha
    probabilities in the forward-backward computation.  For instance, with 1.5
    second chunk, we have 50 time steps after the 3-fold subsampling.  In our
    Switchboard setup a typical denominator FST has 30,000 states in it.  We use
    single-precision floating point for the alphas, so the memory used in
    gigabytes is (128 * 50 * 30000 * 4) / 10^9 = 0.768G.
  
    This won't use up all the GPU memory, but there are other sources of memory,
    e.g. we keep around two copies of the nnet outputs in memory, which takes a
    fair amount of memory depending on the configuration-- e.g. replace the 30000
    above with about 10000 and it will give you the amount of memory used for one
    copy of the nnet outputs in a reasonable configuration.
  
  
    \subsection chain_training_shifting  Training on frame-shifted data
  
    In neural net training we already have ways of generating perturbed data to
    artificially increase the amount of data we train on.  Our standard nnet3
    neural-net training example scripts do time-warping of the raw audio, by
    factors of 0.9, 1.0 and 1.0, to create 3-fold augmented data.  This is
    orthogonal to the 'chain' models, and we do it (or not) just as we would for
    the baseline.  However, there is an extra way we can augment the data for the
    chain models, by shifting the frames.  The output frame rate for these models
    is one third the regular frame rate (configurable, of course), meaning we only
    evaluate nnet output at <code>t</code> values that are multiples of 3, so we
    can generate different versions of the training data by shifting the training
    examples by 0, 1 and 2 frames.  This is done automatically in the training
    script, and it's done 'on the fly' as we read the training examples from
    disk-- the program <code>nnet3-chain-copy-egs</code> has a
    <code>--frame-shift</code> option that is set by the script.  This affects how
    the number of epochs is interpreted.  If the user requests, for instance, 4
    epochs, then we actually train for 12 epochs; we just do so on 3
    differently-shifted versions of the data.  What the option
    <code>--frame-shift=t</code> option actually does is to shift the input frames
    by <code>t</code> and shift the output frames by the closest multple of 3 to
    <code>t</code>.  (In general it might not be 3, it's a configuration variable
    named <code>--frame-subsampling-factor</code>).
  
    \subsection chain_training_gpu GPU issues in training
  
   The parts of the computation that are specific to the 'chain' computation are
   the forward-backward over the numerator FST and over the denominator HMM.  The
   numerator part of this is very fast.  The denominator forward-backward takes
   quite a lot of time, because there can be a lot of arcs in the
   denominator FST (e.g. 200,000 arcs and 30,000 states in a typical Switchboard setup).
   The time taken can be almost as much as the time taken in the neural-net
   parts of the computation.  We were quite careful to ensure memory locality.
  
   The next step to further speed this up is probably to implement a pruned
   version of the forward-backward computation (like pruned Viterbi, but
   computing posteriors).  In order to get a speedup we'd have to prune away a
   very high percentage of states, because we'd need to make up for the loss of
   memory locality that pruning would bring.  In our current implementation we are
   careful to ensure that a group of GPU threads are all processing the same
   HMM-state and time, just from different chunks (we call these different
   'sequences' in the code); and we make sure that the memory locations
   corresponding to a these different sequences are all next to each other in
   memory, so the GPU can do 'consolidated memory access'.  With state-level
   pruning, since the memory access for the different sequences would no longer be
   'in sync', we would lose this advantage.  It should still be doable to get a
   pruned version of the forward-backward algorithm, though.
  
   For speed, we don't use log values in the alpha-beta computation for the
   denominator graph.  In order to keep all the numerical values in a suitable
   range, we multiply all the acoustic probabilities (exponentiated nnet outputs)
   on each frame, by an 'arbitrary value' selected to ensure that our alpha scores
   stay in a good range.  We call this an 'arbitrary value' because the algorithm
   is designed so that we could choose any value here, and it would still be
   mathematically correct.  We designate one HMM state as a 'special state', and
   the 'arbitrary constant' is chosen is the inverse of that special state's alpha
   on the previous frame.  This keeps the special state's alpha values close to
   one.  As the 'special state' we choose a state that has high probability in the
   limiting distribution of the HMM, and which can access the majority of states
   of the HMM.
  
   \section chain_decoding  Decoding with 'chain' models
  
   The decoding process with 'chain' models is exactly the same as for regular nnet3
   neural-net based models, and in fact uses the same script (steps/nnet3/decode.sh).
   There are a few configuration differences:
  
      - Firstly, the graph is built with a different and simpler topology; but this requires
        no special action by the user, as the graph-building script anyway takes the
        topology from the 'final.mdl' produced by the 'chain' training script, which
        contains the correct topology.
  
      - By default when we compile the graph, we use a 'self-loop-scale' of 0.1.
        This affects how the transition probabilities on self-loops are treated
        (it generally works better).  However, for the 'chain' models, because of
        how they were trained, we need to use exactly the same
        transition-probability scaling we trained with, which for simplicity we
        have set to 1.0.  So we supply the option <code>--self-loop-scale
        1.0</code> to the <code>utils/mkgraph.sh</code> script.
  
      - There is no 'division by the prior' necessary in these models.  So we simply
        don't set the vector of priors in the <code>.mdl</code> files; we made sure
        that the decoder just omits the division by the prior if the priors are not set.
  
      - The default acoustic scale we typically use in decoding (0.1) is not
        suitable-- for 'chain' models the optimal acoustic scale is very close to 1.
        So we supply the option <code>--acwt 1.0</code> to the script
        <code>steps/nnet3/decode.sh</code>.
  
      - The scoring scripts can only search the language-model scale in increments
        of 1, which works well in typical setups where the optimal language model scale
        is between 10 and 15, but not when the optimal language-model scale is close
        to 1 as it here.  (Note: for current purposes you can treat the language-model
        scale as the same as the inverse of the acoustic scale).  In order to
        work around this issue without changing the scoring scripts (which are
        database-specific), we supply a new option <code>--post-decode-acwt 10.0</code>
        to the script <code>steps/nnet3/decode.sh</code>,
        which scales the acoustic probabilities by 10 before dumping the lattice.
        After this, the optimal language-model scale will be around 10, which might
        be a little confusing if you are not aware of this issue, but is convenient
        for the way the scoring scripts are set up.
  
     - The default decoding and lattice beams are suitable without modification
       for the 'chain' models, once you use the <code>--acwt 1.0</code> option.
       However, they won't show the full possible speedup and you can get faster
       decoding by using slightly tighter beams.  By tightening the beam in the
       Switchboard setup we were able to get decoding time down from around 1.5
       times real time to around 0.5 times real time, with only around 0.2\%
       degradation in accuracy (this was with neural net evaluation on the CPU; on
       the GPU it would have been even faster).  Note from Dan: this is all to the best
       of my recollection as I write this; actually the degradation may have been more than
       that.  And bear in mind that this was on high-powered modern server machines
      (single-threaded).
  
   You might notice in the current example scripts that we use iVectors.  We do so
   just because they generally help a bit, and because the baseline setup we were
   comparing with, uses them.  There is no inherent connection with 'chain'
   models, and no fundamental requirement to use them.
  
  
  */
  
  }