// doc/grammar.dox
// Copyright 2018 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 grammar Support for grammars and graphs with on-the-fly parts.
This page explains our support for dynamically created grammars and graphs with
extra parts that you want be able to compile quickly (like words you want to
add to the lexicon; contact lists; things like that). We have used the word
"grammar" as an easy searchable term for this framework, but this is not the
only way to implement grammars in Kaldi. If you have a smallish, fixed grammar
it would probably be much easier to create an FST (G.fst) directly from the
grammar (ensuring it is determinizable by means of disambiguation symbols if
necessary), and using the normal graph creation recipe. This framework is
specifically for where you have a compelling need to pre-compile the HCLG.fst
for various sub-parts and have them dynamically stitched together (typically to
avoid recompiling large graphs at runtime).
This framework is limited to work only with left-biphone models. This is
without loss of performance, because our best models (chain models) already use
left-biphone context.
\section grammar_replace Relation to OpenFst's 'Replace()' operation
The design of these tools is inspired by OpenFst's "Replace()"" operation, as implemented
by its command-line tool fstreplace. The basic idea is illustrated by its usage message:
\verbatim
Recursively replaces FST arcs with other FST(s).
Usage: fstreplace root.fst rootlabel [rule1.fst label1 ...] [out.fst]
\endverbatim
Below is a very trivial example of using fstreplace; it just replaces the olabel 5
in the top-level FST with 6.
\verbatim
# (echo 0 1 0 5; echo 1 0) | fstcompile > top.fst
# (echo 0 1 0 6; echo 1 0) | fstcompile > x.fst
# fstreplace top.fst 1000 x.fst 5 | fstprint
0 1 0 0
1 2 0 6
2 3 0 0
3
\endverbatim
The framework of these tools is similar, in that at the G.fst level there are
symbols that will end up getting replaced by other FSTs. Most of the
complexity has to do with the need to handle phonetic context-- and this is
the reason why we can't just use the existing Replace() operation or its
on-demand equivalent.
A slight difference in interface of our tools versus fstreplace is that in our
tools, the top-level FST (corresponding to the 1st arg of fstreplace) does not
have a symbol assigned to it and thus cannot be "replaced into" any
FST.
\section grammar_overview Overview of the framework
To explain how this works, we'll take the "contact list" scenario, where you want to
build a large language model with a nonterminal, say \#nonterm:contact_list in it,
and at recognition time you quickly build some kind of small LM representing
the contact list (possibly with previously unseen words), and compile that graph.
Both the "big graph" and the "small graph" are fully compiled down to the HCLG level.
The GrammarFst code "stitches them together" at decode time. The way this is
accomplished is by putting special ilabels in the two HCLGs that the GrammarFst
code knows how to interpret. That is: most ilabels in the HCLGs correspond to
transition-ids, but there are "special ilabels" with values over ten million, that
the GrammarFst code knows how to interpret, and it uses them to stitch together
the FSTs, in a way that's related to OpenFst's Replace() operation, but is a little
more complicated due to the need to get the phonetic context right. (It only supports
left-biphone context, to keep the complexity manageable).
The GrammarFst has an interface very similar to OpenFst's "Fst" type--
sufficiently similar that the decoder can use it as a drop-in replacement for a
normal FST-- but it does not actually inherit from any OpenFst type; this is to
simplify the implementation and give us more freedom in designing it. The
decoders that use GrammarFst are templated on the FST type, and we use
GrammarFst as the template argument when we want to decode with them.
The StateId used in the GrammarFst code is a 64-bit StateId, which we interpret
as a pair of 32-bit integers. The high-order bits are the "fst instance" and the
low-order bits are the state in that "fst instance". In the contact-list example,
fst-instance zero would be the top-level graph, and there would potentially be
a new fst-instance, numbered 1, 2, ..., for each time the \#nonterm:contact_list nonterminal
appears in the big language model. However, these are only generated on demand
as those parts of the graph are actually accessed. The GrammarFst is a
lightweight object that does very little work at startup. It is designed to be
as fast as possible in the "normal case" when we are not crossing FST
boundaries, and are just traversing inside a single FST. The GrammarFst code
needs a fast-to-evaluate "signal" that it needs to do something special for a
particular FST state. We let the final-probabilities be that signal: that is,
each time we initialize an ArcIterator, the GrammarFst code tests
whether the final-prob has a special value or not. If it has that special value
(4096.0), then the GrammarFst code does a little bit of extra work to see whether
it needs to expand the state, and to look up a previously expanded
version of the state (or expand it if it wasn't already present). By "expand"
the state we mean compute the vector of arcs leaving it.
The FST compilation process-- i.e. the process of going from G.fst to HCLG.fst--
is a little different when we intend to support grammars. That is, we need to
extend some of the tools used in compilation to work correctly with certain
special symbols that we introduce. The differences are explained below.
\subsection grammar_overview Where to find example script
The top-level example scripts for this setup are in egs/mini_librispeech/s5;
see the scripts local/grammar/simple_demo.sh and local/grammar/extend_vocab_demo.sh.
There are also versions of these scripts that use silence probabilities, in
local/grammar/simple_demo_silprobs.sh and local/grammar/extend_vocab_demo_silprobs.sh.
(Actually the workflow is exactly the same in the silprob and no-silprob versions
of the scripts; we created those different versions for testing purposes, as those
demo scripts also help us test the correctness of the code).
\section grammar_symtabs Symbol tables and special symbols
When using this framework, we to add certain extra symbols to the words.txt
and phones.txt symbol tables. These extra symbols represent certain special
symbols intrinsic to the framework, plus the user-defined nonterminal symbols.
In the following example the user-defined special symbols are \#nonterm:foo
and \#nonterm:bar.
\verbatim
tail words.txt
ZZZ 8431
#0 8432
#nonterm_begin 8434
#nonterm_end 8435
#nonterm:foo 8437
#nonterm:bar 8438
\endverbatim
The phones.txt contains a couple more symbols:
\verbatim
tail phones.txt
Z_S 243
#0 244
#1 245
#2 246
#nonterm_bos 247
#nonterm_begin 248
#nonterm_end 249
#nonterm_reenter 250
#nonterm:foo 251
#nonterm:bar 252
\endverbatim
The user should never need to explicitly add these symbols to the words.txt and
phones.txt files; they are automatically added by utils/prepare_lang.sh. All the user
has to do is to create the file 'nonterminals.txt' in the 'dict dir' (the directory
containing the dictionary, as validated by validate_dict_dir.pl).
The C++ code never directly interacts with the nonterminal symbols in
words.txt; that is all done at the script level (e.g. creating L.fst), and the
C++ code only interacts with the nonterminal symbols in phones.txt. Therefore
there are no particularly strong constraints on the symbols in words.txt if you
are prepared to modify the scripts or create "LG.fst"-type graphs directly.
There are some constraints on the order of these symbols in phones.txt: in that case,
the inbuilt symbols (the ones without a colon) must be in the order shown,
the user-defined nonterminals must directly follow them, and there must be no
phones numbered higher than the nonterminal-related symbols (although higher-numbered
disambiguation symbols are allowed).
Some binaries accept an option --nonterm-phones-offset, which tell them
where to find the nonterminal symbols. This should always be equal to the
integer id of the symbol \#nonterm_bos in phones.txt. In the above example
it would be --nonterm-phones-offset=247.
\section grammar_special_g Special symbols in G.fst
If you are using this framework you will be creating several graphs, so there
may be several copies of G.fst (and the intermediate and fully compiled
versions thereof). All of them are allowed to include sub-graphs via
nonterminals, and this can be done recursively; it is OK if the fully
compiled graph is infinite, because it is only expanded on demand.
If you want to include a particular nonterminal (say the one for
\#nonterm:foo), you have to include that symbol \#nonterm:foo on the input
side of G.fst. As to what you include on the output side: that's up to you, as
the framework doesn't care, but bear in mind that symbols without
pronunciations may cause problems for lattice word alignment. Note to more
advanced users: the program lattice-align-words won't work if there are output
symbols in HCLG.fst that don't have any pronunciation, but the alternative
solution lattice-align-words-lexicon will still work, as long as you add
entries for those words with empty pronunciations, in align_lexicon.int; the
entries will be of the form 200007 200007, assuming 200007 is the integer id
of the word with the empty pronunciation. The script prepare_lang.sh adds
these entries for you.
For graphs which are not top-level graphs, all ilabel sequences in
G.fst should begin with the special symbol \#nonterm_begin and end with
\#nonterm_end. This can be accomplished via fstconcat from the command
line, or by just adding them directly as you create the graph. These
symbols will later be involved in selecting the correct phonetic context when we
enter the compiled HCLG.fst.
For some applications, such as the contact-list scenario where you are adding
new vocabulary items, it may be easier to skip creating G.fst and just create
LG.fst manually; this won't be hard to do once you know its expected structure.
The example script local/grammar/extend_vocab_demo.sh in egs/mini_librispeech/s5/
may be a good reference for this, even if you don't plan to actually use those
scripts in production.
\section grammar_special_lg Special symbols in LG.fst
Before we describe what L.fst does with the special symbols,
we will state what we expect LG.fst to contain after composition. All the
special symbols are on the ilabels of LG.fst.
Let us define the set of "left-context phones" as the set of phones that can
end a word, plus the optional silence, plus the special symbol \#nonterm_bos.
This is the set of phones that can possibly appear as the left-context when we
are beginning a word, plus \#nonterm_bos as a stand-in for the beginning-of-sequence
context where no previous phone was seen. We will italicize the phrase
left-context phones when we use it, to emphasize that it has a special meaning.
For non-top-level graphs only:
- All ilabel sequences in the FST must begin with \#nonterm_begin followed by each possible
left-context phone, i.e. parallel arcs enumerating all possible phonetic
left-contexts that could precede this nonterminal.
In non-word-position-dependent systems we can just let this set be all phones;
in word-position-dependent systems it can be all phones except word-internal
and word-begin phones, i.e. all phones except those that look like XX_B
and XX_I. If the set of possible left contexts is known to be smaller, it may
be more efficient to make this a smaller set. In addition to real phones,
we include \#nonterm_bos in this set, which represents the phonetic
context we encounter at the start of an utterance.
- All ilabel sequences must end with \#nonterm_end.
Whenever a nonterminal is invoked, whether from a top-level or non-top-level
graph, the ilabels in LG.fst will be, for example, \#nonterm:foo followed by
in parallel, all possible left-context phones. These left-context get added
by L.fst.
\section grammar_special_l Special symbols in L.fst
This section explains what sequences involving special symbols in L.fst we need to
add, in order to compile a LG.fst with the desired properties from G.fst.
The things we describe below are implemented by
utils/lang/make_lexicon_fst.py and utils/lang/make_lexicon_fst_silprob.py,
and is activated when you provide the --left-context-phones and --nonterminals
options. This is automatically called from prepare_lang.sh when it sees the
file nonterminals.txt in the input dictionary directory.
Let the loop-state of L.fst be the state in L.fst with very high out-degree,
from which all the words leave (and return).
The lexicon needs to include, in addition to the normal things:
- A sequence starting at the start state and ending at the loop-state, with
olabel \#nonterm_begin and ilabels consisting of, \#nonterm_begin
followed by all possible left-context phones (and \#nonterm_bos) in
parallel.
- An arc from the loop-state to a final state, with ilabel and olabel equal to \#nonterm_end.
- For each user-defined nonterminal (e.g. \#nonterm:foo) and for
\#nonterm_begin, a loop beginning and ending at the loop-state that starts with
the user-defined nontermal, e.g. \#nonterm:foo, on the ilabel and
olabel, and then has all left-context-phones on the ilabel only.
In order to keep LG.fst as stochastic as possible (i.e. as "sum-to-one" as possible
in probabilistic terms), when we have states from which there leave arcs containing
all left-context phones we add a cost equal to the log of the number of
left-context phones. This will allow us to push the weights later
on in the graph-building procedure, without causing strange effects that would
be harmful to decoding speed and accuracy. When the graphs actually get spliced
together, all but one of the alternative paths for "all possible left-context
phone" will be disallowed; and that that point we will cancel out the cost of
log(number of left-context phones). This happens in the function
GrammarFst::CombineArcs().
Note that the above means that each sub-graph corresponding to
a user-defined nonterminal will allow optional silence after the nonterminal
but not before it. This is consistent with the way the nonterminal is invoked
from the higher-level graph, and generates exactly one optional silence between each pair of
"real" words, plus one at the beginning and end of the top-level graph. This equivalence
is something we test at the end of the example script
egs/mini_librispeech/s5/local/grammar/simple_demo.sh.
Users should bear all this in mind if they are going to construct these sub-graphs
manually at the LG.fst level rather than using the provided scripts.
\subsection grammar_special_l Interaction with 'silprobs'
In the versions of the lexicons that have word-specific silence probabilities
(see this paper for explanation)
there are actually two versions of the loop state, one for after silence
and one for after nonsilence .
When using 'silprobs', each word has a word-specific cost at its beginning and end that
is associated with the transition to/from nonsilence and silence respectively (where by
"silence" we specifically mean the optional silence added by the lexicon, not silence phones
in a more general sense).
Please refer to utils/lang/make_lexicon_fst_silprob.py for the
details of how we handle nonterminal symbols in combination with these types of
graphs. We will just share the top-level idea here, which is this: when we
enter the HCLG.fst for the nonterminal, and when we return from it, we 'know' the
identity of immediately preceding phone. (That is how this framework works; read
further if you find this surprising). We use that information to implement
the 'silprob' idea without having to give the FST additional entry
points; basically, if the left-context phone was the optional-silence phone, we
go to the state in L.fst that would have been in after seeing optional silence.
This will do the right thing in the normal case. In the specific configuration
where you were not using word-position-dependent phones (c.f. the --position-dependent-phones
option of prepare_lang.sh) and where there are words in your lexicon that end with
the optional-silence phone (e.g. SIL), this will not quite do the right thing,
but we don't expect that this difference will be particularly significant in any real-world
use cases.
\section grammar_special_clg Special symbols in CLG.fst
First, some background: the symbols on the input of CLG.fst (i.e. the ilabels) have interpretation
given by a what we call the ilabel_info. This is explained more in \ref tree_ilabel. Programs
that consume CLG.fst always also consume the ilabel_info, which is a vector >.
For a particular ilabel, say 1536, ilabel_info[1536] = { 5, 21 } is a vector of integers representing
a phone-in-context. E.g. this would represent the phone 21 with a left-context of 5.
Disambiguation symbols also appear on the input of CLG.fst, and they are represented in the ilabel_info
a 1-dimensional vector like { -104 } containing the negative of the disambiguation symbol's
integer id.
The special symbols we add to the input of CLG.fst to support the grammar-decoding framework
always correspond to pairs of symbols,
specifically pairs (\#nontermXXX, left-context phone), where \#nontermXXX is any
of the symbols \#nonterm_begin, \#nonterm_end, \#nonterm_reenter, or user-defined
nonterminals like \#nonterm:foo. The ilabel-info for these special symbols will be
pairs like {-104, 21} where the first element is the negative of the \#nontermXXX symbol
and the second is the left-context phone. The negation makes it easy to distinguish these
ilabel_info entries from regular phones-in-context.
The special symbols in CLG.fst will be as follows.
The following special symbols may appear in any CLG graph, top-level or not:
- When any graph invokes a sub-graph, there will be an arc with an ilabel
(\#nonterm:foo, left-context-phone) representing the
user-specified nonterminal and the actual left-context, which will be
followed by arcs with ilabels of the form (\#nonterm_reenter,
left-context-phone), for all left-context phones.
For non-top-level CLG graphs only:
- These graphs will begin with ilabels representing pairs (\#nonterm_begin, left-context-phone),
representing all potential left-contexts.
- They will end with ilabels (\#nonterm_end, left-context-phone), representing
actual left-contexts.
\subsection grammar_special_c Special symbols in C.fst
First, background. Since this framework only supports left-biphone
context, the states of C.fst correspond to the left context phone, and the
ilabels on the transitions correspond to biphones (plus self-loops for
disambiguation symbols).
Next, what we are trying to accomplish. C.fst needs to do as follows
(describing how it needs to change sequences in LG.fst to sequences in CLG.fst):
- It needs to change the sequence \#nonterm_begin p1 (where p1 is a left-context-phone)
to a single symbol representing the pair (\#nonterm_begin, p1).
- It needs to change the symbol \#nonterm_end to a single symbol representing
the pair (\#nonterm_end left-context-phone), where left-context-phone
represents the current phonetic left-context.
- For each user-defined nonterminal e.g. \#nonterm:foo, it needs to change
the sequence \#nonterm:foo p1 (where p1 is a left-context-phone)
to a sequence of two symbols representing the pairs (\#nonterm:foo, p0) and
(\#nonterm_renter p1) respectively. Here, p0 represents the phone that was
previous to the symbol \#nonterm:foo.
In order to implement the above, we augment the state-space of C.fst by adding
three new states:
- One which we transition to when the olabel is
\#nonterm_begin
- One which we transition to when we see any user-defined
symbol \#nonterm:foo.
- One which we transition to when the olabel is \#nonterm_end.
In order to avoid changing the main context-fst code, we implement this in a
special class fst::InverseLeftBiphoneContextFst which implements these extensions
and which only supports the left-biphone case. See that code for more
details (search for "state space" in grammar-context-fst.h).
\section grammar_special_hclg Special symbols in HCLG.fst
The special symbols in the HCLG.fst graphs will represent the same thing as
those in CLG.fst graphs, discussed above; but their representation in integer
form is different.
Firstly, some background. At the input of CLG.fst the symbols are indexes
into an ilabel_info table. At the input of HCLG.fst the symbols, in general,
represent transition-ids-- and also disambiguation symbols, but those
are removed after determinization. The point is that HCLG.fst does not come with
a table like the ilabel_info that gives us the interpretation of symbols,
so we need to use an encoding that allows us to combine two integers into one.
We choose a representation of the special symbols in HCLG.fst that avoids
clashing with the transition-ids and which makes it relatively painless to
decode the symbols to find what they represent. The representation of
a pair (\#nonterm:XXX, left-context-phone) is,
in the typical case:
\verbatim
hclg_ilabel = 1000000 + 1000 * nonterm_xxx + left_context_phone
\endverbatim
where of course nonterm_xxx and left_context_phone are the corresponding
symbol-ids in phones.txt. Actually, in place of
the "1000" above we use the smallest multiple of 1000 that is greater than the value passed to the
--nonterm-phones-offset option; this allows us to handle large phone sets while also being fairly
human-readable.
\subsection grammar_special_h Special symbols in H.fst
Since H.fst only needs to change the integer represention of the special
symbols but otherwise leaves them unchanged, the changes to it are quite trivial.
H.fst has a high-out-degree state which we will refer to as the loop-state.
We just need to add a self-loop arc at the loop-state for each of the special
symbols referred to in the ilabel_info. The ilabel and olabel
are different since the integer encodings are different.
\section grammar_decoder The decoder
The current approach to decoding with grammars
is to wrap up the entire thing as an FST so that the same decoding code as
before can be used. That is, we just invoke the decoder with a different FST.
We use 64-bit state-ids, so that we can let the higher-order 32 bits encode the "fst instance"
and the lower-order bits encode the state within that instance. The fst instances
are created on the fly as states are visited. Instance 0 is always the "top-level" FST,
and we create new FST instances on the fly as needed, when we encounter arcs with
"special symbols" on.
The actual decoder code is the same as the regular decoder; we just template it on
a different FST type: type fst::GrammarFst instead of fst::Fst. Class fst::GrammarFst does not
inherit from class fst::Fst or support its entire interface (this would have been very
complex to implement); it only supports the parts of the interface actually needed
by the decoder.
\subsection grammar_decoder_arc_iterator The ArcIterator of GrammarFst
Probably the most critical part of the design is the ArcIterator
code, since the inner loop of the decoder is a loop over arcs. In order to avoid
having to copy the underlying FSTs, for "normal states" (those that don't have arcs
leaving them which enter or return from other FST instances), the ArcIterator code actually points into the
arcs of the underlying FSTs, which of course have a differently-typed 'nextstate', with 32 bits
not 64 bits. The ArcIterator also stores the higher 32 bits of the state-id, which
corresponds to the "fst instance" id, and every time you call its Next() function it
creates a new local copy of the 'current arc' it points to, which differs from the
underlying arc by having a 64-bit 'nextstate'. The overhead of copying the arc to a temporary will,
we hope, be mostly removed by compiler optimation. (In fact this does seem to be the
case: the overhead of GrammarFst decoding is about 15\% with -O0 and 5\% with -O2).
Some states in the GrammarFst are 'special' states because they have arcs leaving them that
cross FST boundaries. For these 'special' states we have to construct the arcs separately, and
we store this information in a hash in class GrammarFst.
To keep the decoder code fast and memory-efficient, we need to know quickly,
every time we visit a state, whether it is a "special" state or a normal state.
We don't want to do this with a big array indexed by state, because it would
take up too much memory per GrammarFst object. Instead we do it by giving a
special final-prob value to "special states" in the underlying FSTs that
GrammarFst stitches together. The ArcIterator code tests whether the
final-cost has this special value (4096.0) and if it does, it knows that it's a
"special state" and looks it up in a hash; if not, it just looks up the start
of the array of arcs for this state in the underlying FST.
In order to avoid having any extra if-statements in the ArcIterator that would
have to be evaluated while we loop over arcs, we make sure that even "expanded
states" have vectors of arcs that use the underlying arc type (fst::StdArc)
with 32-bit state-ids. The "fst-instance" index of the destination FST is
stored separately in the ArcIterator, just as it is for normal states. This,
of course, requires that we must not have states with arcs leaving them
that transition to multiple FST instances. See the next section for how
we ensure this.
\section grammar_prepare Preparing FSTs for use in grammar decoding
The GrammarFst code has various requirements on the FSTs that it stitches together,
some of which were mentioned above. These requirements are designed to help
keep the GrammarFst code fast. The function fst::PrepareForGrammarFst (internally implemented
by class fst::GrammarFstPreparer) ensures that these preconditions are met. The user is required
to call this preparation code prior to instantiating the GrammarFst object, so the preparation is
considered part of the graph construction; this keeps the run-time code fast.
The standard graph-construction script utils/mkgraph.sh calls this automatically (via the binary
make-grammar-fst) if it detects that you are using this framework.
The tasks of fst::PrepareForGrammarFst include setting a final-cost of 4096.0 for
FST states that will end up being "special" states, and also making various small
changes to the HCLG.fst that ensure it has the properties needed by class fst::GrammarFst
(e.g. ensuring no state will have transitions to multiple FST instances). These
changes are mostly accomplished by inserting epsilon arcs; for details, see the
documentation of class fst::GrammarFstPreparer.
\section grammar_olabels Output labels in GrammarFsts
In the example scripts we provided, because we only wanted "real words" to
appear on the output side of HCLG.fst, we ensured that no special symbols of
the form \#nontermXXX on the output side of G.fst. However, the
graph compilation framework does allow you to include those symbols if you
want. These might be useful in certain application scenarios, where you want
to know that a particular span of words was decoded as part of a sub-grammar.
The only thing you have to be careful of is that the program
lattice-align-words (and the code underlying it) will not work if you have
words that have an empty pronunciation. That can be an issue if you need to find the
exact time-alignment of words for some reason. In those cases you should use
the alternative program lattice-align-words-lexicon (which reads a file
lexicon.int giving the pronunciation of words in your lexicon), which should
work even in this case. The prepare_lang.sh script already puts empty
pronunciation entries for symbols of the form \#nontermXXX
in lexicon.int, so lattice-align-words-lexicon method of word alignment
should "just work" if you made the lang and graph directories using the
provided scripts.
*/
}