// doc/graph_recipe_test.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 graph_recipe_test Decoding-graph creation recipe (test time)

 Here we explain our normal graph creation approach step by step, along
 with certain data-preparation stages that are related to it.
 Most of the details of this approach are not hardcoded into our tools; we are
 just explaining how it is currently being done.
 If this section is confusing, the best remedy is probably to read
 <a href=http://www.cs.nyu.edu/~mohri/pub/hbka.pdf> "Speech Recognition
 with Weighted Finite-State Transducers" </a> by Mohri et al.
 Be warned: that paper is quite long, and reading it will take at least a
 few hours for those not already familiar with FSTs.
 Another good resource is the <a href=http://www.openfst.org> OpenFst website </a>
 which will provide more context on things like symbol tables.

 \section graph_symtab Preparing the initial symbol tables

We need to prepare the OpenFst symbol tables words.txt and phones.txt.  These
assign integer id's to all the words and phones in our system.  Note
that OpenFst reserves symbol zero for epsilon.  An example of how the
symbol tables look for the WSJ task is:
\verbatim
## head words.txt
<eps> 0
!SIL 1
<s> 2
</s> 3
<SPOKEN_NOISE> 4
<UNK> 5
<NOISE> 6
!EXCLAMATION-POINT 7
"CLOSE-QUOTE 8
## tail -2 words.txt
}RIGHT-BRACE 123683
#0 123684
## head data/phones.txt
<eps> 0
SIL 1
SPN 2
NSN 3
AA 4
AA_B 5
\endverbatim
The words.txt file contains the single disambiguation symbol "#0" (used for epsilon
on the input of G.fst).  This is the last-numbered word in our recipe.  Be careful
with this if your
lexicon contains a word "#0".  The phones.txt file does not contain disambiguation
symbols but after creating L.fst we will create a file phones_disambig.txt that
has the disambiguation symbols in (this is just useful for debugging).

  \section graph_lexicon Preparing the lexicon L

 First we create a lexicon in text format, initially without disambiguation symbols.
 Our C++ tools will never interact with this, it will just be used by a script that creates
 lexicon FST.  A small part of our WSJ lexicon is:
\verbatim
## head data/lexicon.txt
!SIL SIL
<s>
</s>
<SPOKEN_NOISE> SPN
<UNK> SPN
<NOISE> NSN
!EXCLAMATION-POINT EH2_B K S K L AH0 M EY1 SH AH0 N P OY2 N T_E
"CLOSE-QUOTE K_B L OW1 Z K W OW1 T_E
\endverbatim
The beginning, ending and stress markers on the phones (e.g. T_E, or AH0)
are specific to our WSJ recipe and as far as our toolkit is concerned,
they are treated as distinct phones (however, we do handle the tree-building
specially for this setup; read about the roots file in \ref tree_building).

Notice that we allow words with empty phonetic representations.
This lexicon will be used to create the L.fst used in training (without
disambiguation symbols).  We also create a lexicon with disambiguation
symbols, used in decoding-graph creation.  An extract of this file
is here:
\verbatim
# [from data/lexicon_disambig.txt]
!SIL    SIL
<s> #1
</s>    #2
<SPOKEN_NOISE>  SPN #3
<UNK>   SPN #4
<NOISE> NSN
...
{BRACE  B_B R EY1 S_E #4
{LEFT-BRACE L_B EH1 F T B R EY1 S_E #4
\endverbatim
This file is created by a script; the script outputs the number of
disambiguation symbols it had to add, and this is used to create
the symbol table phones_disambig.txt.  This is the same as phones.txt
but it also contains the integer id's for the disambiguation symbols
\#0, \#1, \#2 and so on (\#0 is a special disambiguation symbol which
comes from G.fst but will be "passed through" L.fst via self-loops).
A section of the middle of the file phones_disambig.txt is:
\verbatim
ZH_E 338
ZH_S 339
#0  340
#1  341
#2  342
#3  343
\endverbatim
The numbers are so high because in this (WSJ) recipe we added
stress and position information to the phones.
Note that the disambiguation symbols used for the empty words
(i.e. \<s\> and \</s\>) have to be distinct from those used for the normal
words, so the "normal" disambiguation symbols in this
example start from \#3.

The command to convert the lexicon without disambiguation symbols
into an FST is:
\verbatim
scripts/make_lexicon_fst.pl data/lexicon.txt 0.5 SIL | \
  fstcompile --isymbols=data/phones.txt --osymbols=data/words.txt \
  --keep_isymbols=false --keep_osymbols=false | \
   fstarcsort --sort_type=olabel > data/L.fst
\endverbatim
Here, the script make_lexicon_fst.pl creates the text representation
of the FST.  The 0.5 is the silence probability (i.e. at the
beginning of sentence and after each word, we output silence with
probability 0.5; the probability mass assigned to having no silence is
1.0 - 0.5 = 0.5.  The rest of the commands in this example
relate to converting the FST into compiled form; fstarcsort is
necessary because we are going to compose later.

The structure of the lexicon is roughly as one might expect.  There
is one state (the "loop state") which is final.  There is a start state
that has two transitions to the loop state: one with silence and one
without.  From the loop state there is a transition corresponding to
each word, and that word is the output symbol on the transition;
the input symbol is the first phone of that word.
It is important both for the efficiency of composition and the
effectiveness of minimization that the output symbol should be as early as
possible (i.e. at the beginning not the end of the word).  At the end of each
word, to handle optional silence, the transition corresponding to
the last phone is in two forms: one to the loop state and one to
the "silence state" which has a transition to the loop state.
We don't bother putting optional silence after silence words, which we define
as words that have just one phone that is the silence phone.

Creating the lexicon with disambiguation symbols is just slightly more
complicated.  The issue
is that we have to add the self-loops to the lexicon so that the
disambiguation symbol \#0 from G.fst can be passed through the lexicon.
We do this with the program fstaddselfloops (c.f. \ref fst_algo_disambig),
although we could easily have done it "manually" in the script make_lexicon_fst.pl.
\verbatim
phone_disambig_symbol=`grep \#0 data/phones_disambig.txt | awk '{print $2}'`
word_disambig_symbol=`grep \#0 data/words.txt | awk '{print $2}'`

scripts/make_lexicon_fst.pl data/lexicon_disambig.txt 0.5 SIL  | \
   fstcompile --isymbols=data/phones_disambig.txt --osymbols=data/words.txt \
   --keep_isymbols=false --keep_osymbols=false |   \
   fstaddselfloops  "echo $phone_disambig_symbol |" "echo $word_disambig_symbol |" | \
   fstarcsort --sort_type=olabel > data/L_disambig.fst
\endverbatim
The program fstaddselfloops is not one of the original OpenFst command-line
tools, it is one of our own (we have a number of such programs).

 \section graph_grammar Preparing the grammar G

The grammar G is for the most part an acceptor (i.e. input and output symbols are
identical on each arc) with words as its symbols.  The exception is the
disambiguation symbol \#0 which only appears on the input side.  Assuming the
input is an Arpa file, we use the Kaldi program arpa2fst to convert it to an FST.
The program arpa2fst outputs  an FST with embedded symbols.
In Kaldi we generally use FSTs without embedded symbols (i.e. we use separate symbol tables).
The steps we have to do aside from just running arpa2fst are as follows:
 - We have to remove the embedded symbols from the FST (and rely on the symbol tables
   on disk).
 - We have to make sure there are no out-of-vocabulary words in the language model
 - We have to remove "illegal" sequences of the start and end-of-sentence symbols, e.g.
    \<s\> followed by \</s\>, because these cause L o G to be non-determinizable.
 - We have to replace epsilons on the input side with the special disambiguation symbol \#0.

A slightly simplified version of the actual script that does this is as follows:
\verbatim
gunzip -c data_prep/lm.arpa.gz | \
  arpa2fst --disambig-symbol=#0 \
             --read-symbol-table=data/words.txt - data/G.fst
\endverbatim
The last command (fstisstochastic) is a diagnostic step (see \ref fst_algo_stochastic).
In one typical example, it prints out the numbers:
\verbatim
9.14233e-05 -0.259833
\endverbatim
The first number is small, so it confirms that there is no state that has
the probability mass of its arcs plus final-state significantly less than one.
The second number is significant, and this means that there are states that
have "too much" probability mass (the numeric values of the weights in the
FSTs can generally be interpreted as negated log probabilities).  Having
some states with "too much" probability mass is normal for the FST
representations of language models with backoff.  During later graph creation steps we will
be verifying that this non-stochasticity has not become worse than it was
at the start.

The resulting FST G.fst is of course only used in test time.  In training time
we use linear FSTs generated from the training word-sequences, but this is done
inside Kaldi processes, not at the script level.

 \section graph_lg Preparing LG

 When composing L with G, we adhere in outline to a fairly standard recipe, i.e. we
 compute min(det(L o G)).  The command line is as follows:
\verbatim
    fsttablecompose data/L_disambig.fst data/G.fst | \
        fstdeterminizestar --use-log=true | \
        fstminimizeencoded | fstpushspecial | \
         fstarcsort --sort-type=ilabel > somedir/LG.fst
\endverbatim
 There are some small differences from OpenFst's algorithms.
 We use a more efficient composition algorithm (see \ref fst_algo_composition)
 implemented by our command-line tool "fsttablecompose".  Our determinization
 is an algorithm that also removes epsilons, implemented by the command-line
 program fstdeterminizestar.  The option --use-log=true asks the program to first
 cast the FST to the log semiring; this preserves stochasticity (in the log semiring);
 see \ref fst_algo_stochastic.

 We do minimization with the program "fstminimizeencoded".  This is mostly the
 same as the version of OpenFst's minimization algorithm that applies to
 weighted acceptors; the only change relevant here is that
 it avoids pushing weights, hence preserving stochasticity (see \ref fst_algo_minimization
 for details).

 The program "fstpushspecial" is similar to OpenFst's "fstpush" program, but if
 the weights don't sum to one it ensures that all the states "sum to" the same
 value (possibly different from one), rather than trying to push the "extra"
 weight to the start or end of the graph.  This has the advantage that it
 can never fail ("fstpush" can fail or loop for a very long time if the FST "sums to" infinity);
 it is also much faster.   See push-special.cc for more detailed documentation.

 The "fstarcsort" stage sorts the arcs in a way that will help later composition
 operations to be fast.


 \section graph_clg Preparing CLG

 To get a transducer whose inputs are context-dependent phones, we need to prepare an FST
 called CLG, which is equivalent to C o L o G, where L and G are the lexicon and grammar and C
 represents the phonetic context.  For a triphone system, the input symbols of C would
 be of the form a/b/c (i.e. triples of phones), and the output symbols would be single
 phones (e.g. a or b or c).  See \ref tree_window for more context on the phonetic context
 windows, and how we generalize to different context sizes.  Firstly, we describe
 how we would create the context FST C if we were to make it by itself and compose
 normally (our scripts do not actually work this way, for efficiency and scalability
 reasons).

 \subsection graph_c Making the context transducer

 In this section we explain how we can obtain C as a standalone FST.

 The basic structure of C is that it has states for all possible phone windows of
 size N-1 (c.f. \ref tree_window; N=3 in the triphone case).  The first state,
 meaning begin-of-utterance, would just correspond to N-1 epsilons.  Each state
 has a transition for each of the phones (let's forget about self-loops for now).
 As a generic example, state a/b has a transition with c on the output and a/b/c
 on the input, going to state b/c.  There are special cases at the begin and end
 of utterance.

 At the beginning of utterance, suppose the state is \<eps\>/\<eps\> and the
 output symbol is a.  Normally, the input symbol would be \<eps\>/\<eps\>/a.  But
 this doesn't represent a phone since (assuming P = 1), the central element
 is \<eps\> which is not a phone.  In this case we let the input symbol of the
 arc be #-1 which is a special symbol we introduce for this purpose (we don't use
 epsilon here as the standard recipe does, as it can lead to nondeterminizability
 when there are empty words).

 The end-of-utterance case is a little complicated.  The context FST has, on the
 right (its output side), a special symbol $ that occurs at the end of
 utterances.  Consider the triphone case.  At the end of utterance, after seeing
 all symbols we need to flush out the last triphone (e.g. a/b/\<eps\>, where
 \<eps\> represents undefined context).  The natural way to do this would be to
 have a transition with a/b/\<eps\> on its input and \<eps\> on its output, from
 the state a/b to a final state (e.g. b/\<eps\> or a special final state).  But this is
 inefficient for composition, because if it was not the end of the utterance
 we would have to explore such transitions before finding them pruned away.
 Instead we use $ as the end-of-utterance symbol, and make sure it appears once
 at the end of each path in LG.  Then we replace \<eps\> with $ on the output of
 C.  In general the number of repetitions of $ is equal to N-P-1.  In order to
 avoid the hassle having to work out how many subsequential symbols to add to LG, we just
 allow it to accept any number of such symbols at the end of utterance.  This
 is acheived by the function AddSubsequentialLoop() and the command-line program
 fstaddsubsequentialloop.


If we wanted C on its own, we would first need a list of
disambiguation symbols; and we would also need to work out an unused symbol id we could use
for the subsequential symbol, as follows:
\verbatim
 grep '#' data/phones_disambig.txt | awk '{print $2}' > $dir/disambig_phones.list
 subseq_sym=`tail -1 data/phones_disambig.txt | awk '{print $2+1;}'`
\endverbatim
 We could then create C with the following command (however, see below
 regarding fstcomposecontext; we don't do this in practice as it is inefficient).
\verbatim
 fstmakecontextfst --read-disambig-syms=$dir/disambig_phones.list \
 --write-disambig-syms=$dir/disambig_ilabels.list data/phones.txt $subseq_sym \
   $dir/ilabels | fstarcsort --sort_type=olabel > $dir/C.fst
\endverbatim
The program fstmakecontextfst needs the list of phones, a list of disambiguation symbols
and the identity of the subsequential symbol.  In addition to C.fst, it writes
out the file "ilabels" that interprets the symbols on the left of C.fst
(see \ref tree_ilabel).  The composition with LG can be done as follows:
\verbatim
fstaddsubsequentialloop $subseq_sym $dir/LG.fst | \
 fsttablecompose $dir/C.fst - > $dir/CLG.fst
\endverbatim
For printing out C.fst and anything using the same symbols
that index "ilabels", we can make a suitable symbol table using the following
command:
\verbatim
 fstmakecontextsyms data/phones.txt $dir/ilabels > $dir/context_syms.txt
\endverbatim
This command knows about the "ilabels" format (\ref tree_ilabel).
An example random path through the CLG fst (for Resource Management), printed
out with this symbol table, is as follows:
\verbatim
## fstrandgen --select=log_prob $dir/CLG.fst | \
   fstprint --isymbols=$dir/context_syms.txt --osymbols=data/words.txt -
0   1   #-1 <eps>
1   2   <eps>/s/ax  SUPPLIES
2   3   s/ax/p  <eps>
3   4   ax/p/l  <eps>
4   5   p/l/ay  <eps>
5   6   l/ay/z  <eps>
6   7   ay/z/sil    <eps>
7   8   z/sil/<eps> <eps>
8
\endverbatim

 \subsection graph_compose_c Composing with C dynamically

 In the normal graph creation recipe, we use a program fstcomposecontext which
 dynamically creates the needed states and arcs of C without wastefully creating it
 all.  The command line is:
\verbatim
fstcomposecontext  --read-disambig-syms=$dir/disambig_phones.list \
                   --write-disambig-syms=$dir/disambig_ilabels.list \
                   $dir/ilabels < $dir/LG.fst >$dir/CLG.fst
\endverbatim
 If we had different context parameters N and P than the defaults (3 and 1), we
 would supply extra options to this program.  This program writes
 the file "ilabels" (see \ref tree_ilabel) which interprets the input symbols
 of CLG.fst.  The first few lines of an ilabels file from the Resource
 Management recipe are as follows:
\verbatim
65028 [ ]
[ 0 ]
[ -49 ]
[ -50 ]
[ -51 ]
[ 0 1 0 ]
[ 0 1 1 ]
[ 0 1 2 ]
...
\endverbatim
The number 65028 is the number of elements in the file.
Lines like [ -49 ] are for disambiguation symbols; lines like [ 0 1 2 ]
represent acoustic contexts windows; the first two entries are [ ] which is for
epsilon (never used), and [ 0 ] which is for the special disambiguation
symbol with printed form \#-1 that we use at the beginning of C in place
of epsilon, to ensure determinizability.

 \subsection graph_change_ilabel Reducing the number of context-dependent input symbols

 After creating CLG.fst, there is an optional graph creation stage
 that can reduce its size.
 We use the program make-ilabel-transducer, which works out from the decision
 tree and the HMM topology information, which subsets of context-dependent phones would
 correspond to the same compiled graph and can therefore be merged (we pick
 an arbitrary element of each subset and convert all context windows to that context
 window). This is a similar concept to HTK's logical-to-physical mapping.    The
 command is:
\verbatim
 make-ilabel-transducer --write-disambig-syms=$dir/disambig_ilabels_remapped.list \
  $dir/ilabels $tree $model $dir/ilabels.remapped > $dir/ilabel_map.fst
\endverbatim
 This program requires the tree and the model; it outputs a new ilabel_info
 object called "ilabels.remapped"; this is in the same format as the original
 "ilabels" file, but has fewer lines.  The FST "ilabel_map.fst" is composed
 with CLG.fst and remaps the labels.  After doing this we determinize
 and minimize so we can immediately realize any size reductions:
\verbatim
 fstcompose $dir/ilabel_map.fst $dir/CLG.fst  | \
   fstdeterminizestar --use-log=true | \
   fstminimizeencoded > $dir/CLG2.fst
\endverbatim
 For typical setups this stage does not actually reduce the graph size
 by very much (5\% to 20\% reduction is typical), and in any case
 it is only the size of intermediate graph-creation stages that we
 are reducing by this mechanism.  But the savings could become significant
 for systems with wider context.

 \section graph_h Making the H transducer

 In the conventional FST recipe, the H transducer is the transducer that has, on
 its output, context dependent phones, and on its input, symbols representing
 acoustic states.  In our case, the symbol on the input of H (or HCLG) is not the
 acoustic state (in our terminology, the pdf-id) but instead something we call the transition-id (see
 \ref transition_model_identifiers).  The transition-id encodes the pdf-id plus some
 other information including the phone.  Each transition-id can be mapped to a
 pdf-id.  The H transducer that we create does not encode the self-loops.  These
 are added later by a separate program.  The H transducer has a
 state that is both initial and final, and from this state there is a transition for
 every entry but the zeroth one in the ilabel_info object (the ilabels file, see above).  The
 transitions for the context dependent phones go to structures for the
 corresponding HMMs (lacking self-loops), and then back to the start state.  For
 the normal topology, these structures for the HMMs would just be linear
 sequences of three arcs.  H also has self-loops on the initial state for each of
 the disambiguation symbols (\#-1, \#0, \#1, \#2, \#3 and so on).

 The section of script that makes the H transducer (we call it Ha
 because it lacks self-loops at this point), is:
\verbatim
make-h-transducer --disambig-syms-out=$dir/disambig_tstate.list \
   --transition-scale=1.0  $dir/ilabels.remapped \
   $tree $model  > $dir/Ha.fst
\endverbatim
 There is an optional argument to set the transition scale; in our
 current training scripts, this scale is 1.0.  This scale only
 affects the parts of the transitions that do not relate to
 self-loop probabilities, and in the normal topology (Bakis model) it
 has no effect at all; see \ref hmm_scale for more explanation.
 In addition to the FST, the program also writes a list of
 disambiguation symbols which must be removed later.

 \section graph_hclg Making HCLG

 The first step in making the final graph HCLG is to make the
 HCLG that lacks self-loops.  The command in our current script is
 as follows:
\verbatim
  fsttablecompose $dir/Ha.fst $dir/CLG2.fst | \
   fstdeterminizestar --use-log=true | \
   fstrmsymbols $dir/disambig_tstate.list | \
   fstrmepslocal  | fstminimizeencoded > $dir/HCLGa.fst
\endverbatim
 Here, CLG2.fst is the version of CLG with a reduced symbol set ("logical"
 triphones, in HTK terminology).  We remove the disambiguation symbols and any
 easy-to-remove epsilons (see \ref fst_algo_eps), before minimizing; our
 minimization algorithm is one that avoids pushing symbols and weights (hence
 preserving stochasticity), and accepts nondeterministic input (see \ref
 fst_algo_minimization).

 \section graph_selfloops Adding self-loops to HCLG

 Adding self-loops to HCLG is done by the following command:
\verbatim
  add-self-loops --self-loop-scale=0.1 \
    --reorder=true $model < $dir/HCLGa.fst > $dir/HCLG.fst
\endverbatim
 See \ref hmm_scale for an explanation of how the self-loop-scale of 0.1
 is applied (note that it also affects the non-self-loop probabilities).
 For an explanation of the "reorder" option, see \ref hmm_reorder;
 the "reorder" option increases decoding speed but is not compatible with
 the \ref decoder_kaldi "kaldi decoder".
 The add-self-loops program does not just add self-loops; it may also
 have to duplicate states and add epsilon transitions in order to
 ensure that the self-loops can be added in a consistent way.  This
 issue is mentioned in slightly more detail in \ref hmm_reorder.
 This is the only stage of graph creation that does not preserve stochasticity;
 it does not preserve it because the self-loop-scale is not 1.   So
 the program fstisstochastic should give the same output for all of
 G.fst, LG.fst, CLG.fst and HCLGa.fst, but not for HCLG.fst.
 We do not determinize again after the add-self-loops stage; this would
 fail because we have already removed the disambiguation symbols.  Anyway,
 this would be slow and we believe that there is nothing further to be gained from
 determinizing and minimizing at this point.



*/


}