// doc/lattices.dox

// Copyright 2009-2011 Microsoft Corporation

// 2013 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 lattices Lattices in Kaldi

\section lattices_intro Introduction

A lattice is a representation of the alternative word-sequences that are "sufficiently likely" for

a particular utterance. In order to understand lattices properly you have to understand decoding

graphs in the WFST framework (see \ref graph).

In this section we summarize the issues relating to Kaldi lattices, and in the rest of this page

we will explain them more precisely. The reader may also want to read the paper

<a href=https://sites.google.com/site/dpovey/2012_icassp_lattices.pdf?attredirects=0>

"Generating exact lattices in the WFST framework", D. Povey, M. Hannemann et. al, ICASSP 2012 (submitted)</a>,

which provides more context as to how our lattices relate to previously published algorithms.

This page gives more focus to the programming aspects.

There are two representations of lattices in Kaldi.

The first representation is the Lattice type. This is an FST whose weight type contains two

floating point weights (the graph cost and the acoustic cost), whose input

symbols are \ref transition_model_identifiers "transition-ids" (these are roughly like

context-dependent HMM states), and whose output symbols typically represent words (in general,

they represent whatever the output symbols on your decoding graph represented).

The second representation of lattices is the CompactLattice type. This contains essentially the same

information as Lattice, but in a different form: it is an acceptor (meaning the input and

output symbols are always identical), the input and output symbols represent words, and the

sequence of transition-ids is included as part of the weights (note that OpenFst has a very general

concept of weights; anything that satisfies the semiring axiom can be a weight).

The weight type in CompactLattice

contains a pair of floats and a sequence of integers (which represent transition-ids).

We'll describe the semiring later.

Since the Lattice and CompactLattice types both represent the same information, we have made

them equivalent for I/O purposes in the sense that the mechanisms that read Lattice will

also read CompactLattice, and vice versa. For instance, if you use the type

SequentialLatticeReader to read sets of lattices indexed by utterance-id, it will work

the same whether it was actually a Lattice or a CompactLattice in the archive.

However, we typically write lattices out as CompactLattice. Many programs read as Lattice

because

To convert between lattice types, there is a function ConvertLattice()

that you can use.

The weights in both the CompactLattice and Lattice types contain two floats, which

are interpreted as the graph cost and the acoustic cost respectively. The graph cost

is a sum of the LM cost, the (weighted) transition probabilities, and any pronunciation cost. Since

these are all mixed together, in order to do things like LM rescoring we typically first subtract

the "old" LM cost and then add in the "new" LM cost, to avoid touching the other parts

of the cost. If we call these two floating point values (a,b), the semiring in Lattice

is like the lexicographic semiring on (a+b, a-b) (see OpenFst documentation for explanation).

That is, when we "add" (in the semiring)

two of these pairs, we get the pair that has the lowest (graph + acoustic) cost; if they are the

same we break ties using the difference (graph - acoustic). This makes sense in terms of

"taking the best path". Actually, it only makes sense if the acoustic weights are appropriately

scaled. Our convention is to keep lattices externally (e.g. on disk) with the

acoustic costs unscaled, and to apply

the scale before any algorithm that compares the weights (and un-scale them again before

we write the lattices out).

The Lattice and CompactLattice types are used as data-structures to represent conventional lattices, and

also to represent N-best lists. The lattice generation algorithm we use has

quite precise properties. Let lattice-delta be a number (typically 10 or so).

Our lattice generation algorithm ensures (modulo beam pruning) that every

word-sequence whose best alignment has cost within lattice-delta of the best

path is present in the lattice, and has the best possible alignment and weight.

Also, each word-sequence must be present in the lattice only once. We achieve this by

first creating a state-level lattice and appropriately pruning it, and then

determinizing it using a special semiring (or if you like, you can view this as

a special determinization algorithm that handles non-functional FSTs by always

picking the most likely alternative path). We'll explain below below exactly

how this works.

We always ensure that for lattices that we write out to disk,

each word-sequence has only one path through the lattice. This is required for

certain algorithms (such as LM rescoring) to work properly. Being determinized

(on the word labels, in the CompactLattice format) is a sufficient condition for this.

We never attach symbol tables to FSTs in any Kaldi code. In order to view

archives containing lattices in their most natural form with actual words

in them, we use scripts to do the conversion (an example is in egs/rm/s1/steps/decode_tri1_latgen.sh).

\section lattices_lattice The Lattice type

The Lattice type is just an FST templated on a particular semiring.

In kaldi-lattice.h, we create a typedef:

\verbatim

typedef fst::VectorFst<LatticeArc> Lattice;

\endverbatim

where LatticeArc is the normal arc type templated on LatticeWeight:

\verbatim

typedef fst::ArcTpl<LatticeWeight> LatticeArc;

\endverbatim

LatticeWeight is again a typedef that instantiates the LatticeWeightTpl

template using BaseFloat as the floating point type.

\verbatim

typedef fst::LatticeWeightTpl<BaseFloat> LatticeWeight;

\endverbatim

The template LatticeWeightTpl is something that we define in the

fst namespace, in fstext/lattice-weight.h.

It has some similarities to the lexicographic semiring, i.e. it is similar to

the OpenFst type

\verbatim

LexicographicWeight<TropicalWeight, TropicalWeight>

\endverbatim

In both cases, addition (the semiring "plus" operation) is defined as taking

the max, but the "max" is differently defined. LexicographicWeight first compares

the first element and uses the second to break

ties. LatticeWeight first compares the sum; tie-breaking is then done using the

difference. So a LatticeWeight with (a,b) is equivalent to a LexigraphicWeight

with (a+b, a-b). The basic intuition behind LatticeWeight is to preserve the

semantics of taking the lowest-cost path (where the total cost is the graph plus

acoustic cost), while separately "remembering" what the acoustic and graph cost were.

In an ideal world, we might like to keep more information separate: for instance,

the LM cost versus the transition-model cost versus the pronunciation-probability

cost. But this is not practical because this information is all mixed together in

the decoding graph, and separating it out in the decoding graph would lead to a

significant expansion in decoding-graph size.

As mentioned previously, the input symbols in the Lattice represent transition-ids,

and the output symbols represent words (or whatever symbol was on the output

of your decoding graphs).

When designing Kaldi we considered using the LexicographicWeight type instead of

the LatticeWeight type, where the first element would be the (graph + acoustic)

cost and the second element would be, say, just the acoustic cost. We

ultimately decided against this because while it might be slightly more

efficient for some purposes, we felt it would be too confusing.

Many algorithms on lattices (for instance, taking the best path, or pruning) are

most efficient to do using the Lattice type rather than the CompactLattice type. The issue

is that with the CompactLattice type, the weights contain sequences of transition-ids,

and operations like taking the best path will multiply weights together which

corresponds to appending these sequences. For many algorithms, this would take time quadratic

in the length of the lattice in words. As mentioned above, you can read a Lattice

from an archive even if it contains a CompactLattice because the Holder type (LatticeHolder)

does automatic conversion. So the code:

\verbatim

SequentialLatticeReader lattice_reader(lats_rspecifier);

for (; !lattice_reader.Done(); lattice_reader.Next()) {

std::string key = lattice_reader.Key();

Lattice lat = lattice_reader.Value();

...

}

\endverbatim

would be valid even if the archive or script file specified in "lats_rspecifier"

contained the CompactLattice format-- which it normally would, because that is how

we normally write lattices. An example of lattice type conversion is:

\verbatim

Lattice lat;

// initialize lat.

CompactLattice compact_lat;

ConvertLattice(lat, &compact_lat);

\endverbatim

Conversion to the CompactLattice type involves a "factoring" operation, the function

fst::Factor() (defined by us in fstext/factor.h), that identifies chains of states

that can be combined into a single CompactLattice arc.

A typical example of appying an OpenFst algorithm to a lattice is as follows

(this code, modified from latbin/lattice-best-path.cc, finds the best path

through a lattice):

\verbatim

Lattice lat;

// initialize lat.

Lattice best_path;

fst::ShortestPath(lat, &best_path);

\endverbatim

\section lattices_compact Compact lattices (the CompactLattice type)

Similarly to the Lattice type, CompactLattice is a typedef to a typical OpenFst

template:

\verbatim

typedef fst::VectorFst<CompactLatticeArc> CompactLattice;

\endverbatim

The CompactLatticeArc type is a standard template for an Arc, templated on CompactLatticeWeight:

\verbatim

typedef fst::ArcTpl<CompactLatticeWeight> CompactLatticeArc;

\endverbatim

The CompactLatticeWeight type is a typedef as follows:

\verbatim

typedef fst::CompactLatticeWeightTpl<LatticeWeight, int32> CompactLatticeWeight;

\endverbatim

The template arguments are the underlying weight type (LatticeWeight), and an

integer type (int32) that is used to store the sequences of transition-ids.

Note that in Kaldi code (such as above), we tend to prefer to define concrete types,

for understandability, whereas the OpenFst style is to define templates, and when coding inside the

fst namespace we tend to follow this convention. Thus, we define a template in the

fst namespace and turn it into a fully-specified type (CompactLatticeWeight) in the

kaldi namespace.

The template arguments of CompactLatticeWeightTpl are an underlying weight (here,

LatticeWeight) and an integer type (here, int32). It contains two data members: a weight and

a sequence of integers:

\verbatim

template<class WeightType, class IntType>

class CompactLatticeWeightTpl {

...

private:

WeightType weight_;

vector<IntType> string_;

};

\endverbatim

These can be accessed using the member functions \ref fst::CompactLatticeWeightTpl::Weight() "Weight()"

and \ref fst::CompactLatticeWeightTpl::String() "String()". The semiring used by

\ref fst::CompactLatticeWeightTpl "CompactLatticeWeightTpl" does not correspond to any

semiring used in OpenFst, as far as we are aware. Multiplication corresponds to multiplying

the weights and appending the strings together. When adding two CompactLatticeWeights,

we first compare the weight component. If one of the weights is "more" than the other one, we take that weight

and its corresponding string. If not (i.e. if the two weights are the same), we use an ordering

on the strings to break ties. The ordering if we use is to take the shortest string if

they have different length, and otherwise use lexical order (we can't just use lexical order, or it

would violate one of the semiring axioms which is distributivity of multiplication over

addition).

Note that we talked above about one of the weights being "more" than the other one, and we

assumed that if neither is more than the other, then they are equal. This is only true if there

is a total order on the semiring, and this is a requirement on the weight component of

the template (this requirement is fulfilled for LatticeWeight and TropicalWeight).

The "OpenFst" way to access this ordering is using the template "NaturalLess", which given

a and b, looks for whether (a+b) is equal to a or to b. For efficiency reasons, we don't

do it this way: we assume that there is a Compare() function defined on the weight type

which returns -1, 0 or 1 depending on the comparison. We have such a function defined

for the LatticeWeightTpl template. To enable CompactLatticeWeightTpl

to be instantiated for TropicalWeight, which we do for testing purposes,

we define an appropriate Compare function for that weight type.

There is a reason why we define this perhaps rather strange looking semiring. It relates

to our idea of a lattice as containing the best path for any given word sequence.

Suppose we had an arbitrary lattice (e.g., it might be a raw state-level lattice) and

we represent it as a CompactLattice, which is an acceptor on word sequences with the

transition-id sequences as part of the weights. The semantics of WFSTs is that for

any (input-symbol-sequence, output-symbol-sequence) pair, the weight that the WFST

assigns is the sum of the weights of all paths that have that pair of symbol-sequences.

In the current case, we are dealing with an acceptor so there is really only symbol-sequence

(the word sequence). The point is that when we sum the (weight, string) pairs

in this semiring, we just get the single (weight, string) pair that

has the best "weight component", i.e. the lowest cost. If we were to remove

epsilons and determinize, in this semiring, we would get a lattice that only had a

single path for each word sequence, and that path would have the best possible

cost for that word sequence. This wouldn't be very efficient, so we actually use

a specialized determinization algorithm that removes epsilons and that is optimized for this case, but it

has the same effect as calling that the normal OpenFst RemoveEps() and Determinize() algorithms would.

\section lattices_generation Lattice generation

Command-line decoding programs that have 'latgen' in their names generate lattices.

Currently most of these use LatticeFasterDecoder. For purposes of exposition we will

focus instead on LatticeSimpleDecoder, whose operation is simpler.

This is defined in decoder/lattice-simple-decoder.h, and invoked by gmm-latgen-simple.cc.

As the name suggests, LatticeSimpleDecoder is a lattice-generating decoder that is modified from SimpleDecoder.

SimpleDecoder is a straightforwardly implemented Viterbi beam search algorithm with only a single

tunable parameter: the pruning beam (see \ref decoders_simple). LatticeSimpleDecoder has

one more important tunable parameter: the lattice beam (or lattice-delta), which should typically be

less than the pruning beam.

The basic picture is that LatticeSimpleDecoder first produces a state-level lattice, and prunes

it with the lattice-delta, and then at the end it runs a special determinization algorithm

that results in only keeping the best path for each word sequence.

In SimpleDecoder, there are reference-counted tracebacks. In LatticeSimpleDecoder,

a single traceback isn't enough because the lattice has a more complicated structure.

In fact, it turned out to be more convenient to store <EM> forward </EM> instead of

backward links. We need to do more than just do reference counting in order to

free un-needed links, because of the lattice-delta pruning; in fact there is no reference counting.

The final objective of the pruning algorithm is as follows (call this the

"naive" approach.

Firstly, suppose that for each

frame, for each state that was active on that frame we created a structure or token

of some kind, and for each arc out of it (to a state that was not pruned), we

create some kind of link record. Let's use the word "token" for the structure

that we create for a particular graph state at a particular frame, and "link" for

the forward link from one token to another token (note: these links can be within

a frame as well as across frames, due to epsilon arcs in the decoding graph).

The simplest possible version of the pruning algorithm is:

firstly, we decode up till the end of the file, keeping all the tokens and links

that were active during decoding.

When we have come to the end of the file we want to apply the lattice-delta beam,

such that any state or arc that is not on a path that is within lattice-delta

cost of the best path, will be pruned away. This is fairly easy to do: for example,

we could turn the state-level traceback into an FST and use OpenFst's \ref fst::Prune()

"Prune()" algorithm. Unfortunately this wouldn't be a very practical algorithm

because we would soon run out of memory: on each frame there are typically

many thousands of states active, and we can't afford to wait till the end of the

utterance to prune them.

Fortunately there is an efficient way to prune away these tokens without waiting

until the end of the utterance. Periodically (every 25 frames by default), we do

a backward sweep from the current frame to the beginning. In this backward

sweep, we work out a "delta" quantity for each token. The "delta" is the

difference between the cost of the best path and the cost of the best path the

token is on, and it can be computed in the backward sweep (the "forward"

information that we need it already inside the token, and is static). We can

define an analogous "delta" quantity for the forward links. Any time this

"delta" exceeds the "lattice-delta" beam, we prune away the associated token or

link. For the tokens at the currently active frame, we set the "delta" to zero;

we can prove that this is the right thing to do. That is, with this algorithm

we will only be pruning away things that we eventually would have pruned away anyway

using the "naive" algorithm.

It might seem on the face of it that our pruning algorithm would take time

quadratic in the length of the utterance (because each 25 frames we visit the whole

utterance up to the current point), but in fact it is more like linear,

because we can detect when all the "delta" values of tokens for a particular

frame have not changed, and we can stop going backward in time. We expect that

for very long utterances, we will normally prune backward for only a second or two.

Even if it were not for this feature, the algorithm would be dominated by a linear-time

component in practical cases, because the vast majority of tokens are deleted the

first time they are visited by the algorithm.

We note that there are a couple of complexities in our implementation of this. One

is that because we have forward links, while the pruning algorithm goes backward in

time, there is a danger of "dangling" forward links being created when we delete()

tokens, so we have to avoid delete()ing tokens until we have pruned the forward

links from the previous frame. The other issue is that we have to treat the

final frame specially, because we need to take into account the final

probabilities.

\subsection lattices_generation_raw Getting the raw lattice, and converting it into the final form.

When we have reached the end of the utterance, we produce the lattice in two phases.

The first phase is to create the

"raw lattice". This is a state-level FST that is pruned using the lattice-delta

but is not determinized, so it has many alternative paths corresponding to each

word sequence. Creation of the "raw lattice" is very trivial, and consists of

taking our token and link structures and translating them into OpenFst

structures. If we are asked for the best path (e.g. for getting the transcript),

we would just run OpenFst's ShortestPath algorithm on this raw lattice. If we

are asked for the lattice, there are two options.

The first option is: the

decoder supports outputting the raw state-level lattice directly (set --determinize-lattice=false);

this is mostly useful if you are going to do acoustic rescoring with a system built with the

same tree. Afterwards you would probably want to determinize the lattice using the

lattice-determinize program, before storing the lattices on disk for an extended time

(as the raw state-level lattices are quite large).

Let's assume instead that we're outputting

the determinized lattice (the second option). The determinized lattice is supposed to have only one

path through it for every word sequence that is allowed in the original raw

lattice. We can achieve this by creating a CompactLattice, removing epsilons and

determinizing, but this would be very inefficient. Instead, we run a special

determinization algorithm called \ref fst::DeterminizeLattice()

"DeterminizeLattice()". This algorithm does epsilon removal and

determinization together. In this respect it is similar to our algorithm \ref

fst::DeterminizeStar() "DeterminizeStar()", but the \ref

fst::DeterminizeLattice() "DeterminizeLattice()" algorithm uses data structures

that are specifically optimized for this case. The issue is the cost overhead of

appending long strings of input symbols together (the sequences of symbols are only about as long

as the maximum number of frames in a word, but this is quite long). That is, if represented in the

most naive way as vectors, adding a symbol to a list of N symbols and storing

the result separately take time O(N). Instead we use data structures that make

it take constant time. \ref fst::DeterminizeLattice()

"DeterminizeLattice()" takes as input the Lattice format, since this is the

most natural form for the input, and outputs in the CompactLattice format. However,

it should really be viewed as determinization of the CompactLattice format: that

is, it preserves equivalence only when viewing it as an operation on a CompactLattice.

\section lattices_archives Lattices in archives

We normally store lattices in archives. For general information about archives and

Kaldi I/O mechanisms, see \ref io. For a concrete example, a command line that

generates lattices might be as follows:

\verbatim

gmm-latgen-simple --beam=13.0 --acoustic-scale=0.0625 exp/tri/1.mdl \

exp/graph_tri/HCLG.fst ark:test_feats.ark "ark,t:|gzip -c > exp/lats_tri/1.lats.gz"

\endverbatim

After this, we could look at the lattice as follows:

\verbatim

gunzip -c exp/decode_tri2a_bg_latgen_eval92/7.lats.gz | \

utils/int2sym.pl -f 3 data/words.txt | head

444c0410

0 1 <s> 5.27832,0,

1 2 <UNK> 8.08116,1099.84,

1 3 A 12.8737,8342.93,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_17_17_17_3\

464_3596_3632_3_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_\

1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_12_18_17_17_18562_18561_18604_18\

603_18603_18618_604_603_603_638

1 4 IF 10.2262,8096.64,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_13708_137\

28_13806_12654_12670_12676_3_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1\

_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_1856\

2 5 NOT 12.4568,10548.7,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_17_20_26\

...

\endverbatim

It might seem slightly disconcerting that the label \<UNK\> appears on

a transition that has graph and acoustic scores but with no input labels

(these would appear after the final comma, if they

were present). It must be appreciated that graph and acoustic scores and input-label

sequences are only valid when summed (or appended) over entire paths through the

FST. There is no guarantee that they will be synchronized with respect to each other

or with respect to the word labels.

Lattices are normally stored in the CompactLattice format in the archive, and

as mentioned before, we use the convention that the acoustic weights in the

archive are unscaled, so for operations (such as pruning) that are sensitive

to the acoustic weight, the corresponding command-line programs would take

the --acoustic-scale option and would scale the acoustic weights prior to such

operations (and un-scale them afterwards).

\section lattices_operations Operations on lattices

Here we discuss some operations that can be done on lattices, and their corresponding

programs.

\subsection lattices_operations_pruning Pruning lattices

We can prune lattices using a specified pruning beam. This will remove arcs and states that

do not appear on a path that has a cost sufficiently close to the cost of the best path through the lattice.

For each lattice, the program lattice-prune first scales the acoustic weights using a specified acoustic

scale, then calls OpenFst's \ref fst::Prune() "Prune()" function, then reverses the

scaling of acoustic weights. An example command line is:

\verbatim

lattice-prune --acoustic-scale=0.1 --beam=5 ark:in.lats ark:out.lats

\endverbatim

Note: for efficiency, the pruning operation is done in the Lattice format, but we convert

to CompactLattice before writing the lattice out.

\subsection lattices_operations_best_path Computing the best path through a lattice

The program lattice-best-path computes the best path through a lattice, and outputs

the corresponding input-symbol sequence (alignment) and output-symbol sequence (transcription).

As usual, the input and outputs are in the form of archives. An example command line is:

\verbatim

lattice-best-path --acoustic-scale=0.1 ark:in.lats ark:out.tra ark:out.ali

\endverbatim

\subsection lattices_operations_nbest Computing the N-best hypotheses

The program lattice-nbest computes the N best paths through the lattice (using

OpenFst's \ref fst::ShortestPath() "ShortestPath()" function), and outputs

the result as a lattice (a CompactLattice), but with a special structure.

As documented for the \ref fst::ShortestPath() "ShortestPath()" function in

OpenFst, the start state will have (up to) n arcs out of it, each one to the

start of a separate path. Note that these paths may share suffixes.

An example command line is:

\verbatim

lattice-nbest --n=10 --acoustic-scale=0.1 ark:in.lats ark:out.nbest

\endverbatim

\subsection lattices_operations_lmrescore Language model rescoring

Because the "graph part" (the first component) of LatticeWeight contains the

language model score mixed together with the transition-model score and any

pronunciation or silence probabilities, we can't just replace it with

the new language model score or we would lose the transition probabilities

and pronunciation probabilities. Instead we have to first subtract the

"old" LM probabilities and then add in the new LM probabilities. The

central operation in both of these phases is composition (there is some

scaling of weights going on, also). The command line for doing this

is: first, to remove the old LM probabilities:

\verbatim

lattice-lmrescore --lm-scale=-1.0 ark:in.lats G_old.fst ark:nolm.lats

\endverbatim

and to add the new LM probabilities:

\verbatim

lattice-lmrescore --lm-scale=1.0 ark:nolm.lats G_new.fst ark:out.lats

\endverbatim

Note: the above examples are slightly simplified; actually you would have

to "project" the G.fst FST's on the output to remove disambiguation symbols

using `fstproject` with `--project_output=true`, see steps/lmrescore.sh for examples.

Also there are other ways to do this; see

the documentation for lattice-compose below.

What the program \ref lattice-lmrescore.cc "lattice-lmrescore" does is this...

actually, we will first first describe the simple version that is not exactly what

happens. Suppose that we are given an LM-scale S and a LM G.fst.

We first multiply all the costs in G.fst by S. Then for each lattice,

we compose it on the right with G, lattice-determinize it (to keep only the

best path through G for each word sequence) and write it out. This would

work fine for positive S, but for negative S it would be equivalent to taking

the <EM> worst </EM> path through G, for each word sequence. To fix this,

we instead do it as follows.

For each input lattice, we first

scale the lattice's graph (or LM) costs by the inverse of S; we then compose

on the right with G.fst; we run lattice-determinization (see above) on the resulting lattice

which retains only the best path through the lattice for each word sequence;

and we then scale the lattice's graph/LM scores by S. This does the right

thing for negative S. This whole approach only makes sense if the input

lattice has only a single path through it for each word sequence (e.g. if it

was lattice determinized). We assume that all lattices passed between programs

have this property (this is why it is not a good idea to write out "raw" state-level

lattices, unless you know what you are doing).

Note that in order for the composition to work, this program needs to map G.fst

from the tropical semiring into the LatticeWeight semiring. It does this by

putting the weights of G.fst into the first part of the weight (the "graph"

part), and leaving the second part of the weight zero (in the semiring, this is

1). At the C++ level, this mapping is done using the MapFst mechanism of

OpenFst, in which we define a Mapper class to map StdArc to LatticeArc, and then

create an object of type MapFst which is evaluated on demand and converts G.fst

to the LatticeWeight weight type.

\subsection lattices_operations_scale Probability scaling

It is possible to scale the probabilities on lattice weights using a general

2x2 matrix. The command-line program that does this is lattice-scale.

An example command line is:

\verbatim

lattice-scale --acoustic-scale=0.1 --lm-scale=0.8 ark:in.lats ark:out.lats

\endverbatim

This is actually not a frequently used program, because we expect that normally the

acoustic weights in archives should be unscaled; programs that need to apply an acoustic

scale generally accept an --acoustic-scale option. Such programs generally apply the scale,

do an operation (such as determinization or pruning) that is sensitive to it, and then apply

the inverse of the scale.

For most operations we do not

want to scale the LM probabilities; however, it might sometimes be useful to do so, e.g.

in discriminative training it might be useful to tune both the LM and acoustic scale.

The lattice-scale program accepts the options --lm2acoustic-scale

and --acoustic2lm-scale. For instance, the program would add --lm2acoustic-scale

times the original LM part of the weight to the acoustic part of the new weight. We include

this mostly for completeness.

\subsection lattices_union Lattice union

The program lattice-union computes the union of two lattices (as with other programs,

this program iterates over sets of lattices in archives). The main envisaged use of

this is in discriminative training (especially MMI), to ensure that the correct

transcription is present in the denominator lattice. An example command line is:

\verbatim

lattice-union ark:num_lats.ark ark:den_lats.ark ark:augmented_den_lats.ark

\endverbatim

This program calls OpenFst's Union() function, then lattice-determinizes to

ensure there is only one path for each word sequence, then write the lattice out.

There are actually not many situations where lattice union makes sense (e.g.

it does not make much sense to do the union over lattices computed with different

features or models).

\subsection lattices_operations_compose Lattice composition

The program lattice-compose works in several modes. One composes lattices

with other lattices. This is done in the transducer form, i.e. viewing

a lattice as a transducer from transition-ids to words. It would typically

be done after first projecting one of the sets of lattices on the output

(to get a word to word transducer). Typical usage might be:

\verbatim

lattice-project ark:1.lats ark:- | \

lattice-compose ark:- ark:2.lats ark:3.lats

\endverbatim

Now, 3.lats would have the sum of the scores in

1.lats and 2.lats, on its paths. You can accomplish the same thing in "one package"

by using the program lattice-interp (see next section).

Another mode is to compose a set of lattices with a fixed FST.

The FST is converted dynamically into a lattice for this purpose;

the FST weights are interpreted as the "graph part" of the lattice weights,

i.e. as the first part of the tuple. An example of the use of

this is to convert a lattice to phones, and then compose with

a lexicon to convert back to words, for example:

\verbatim

lattice-to-phone-lattice final.mdl ark:1.lats ark:- | \

lattice-compose ark:- Ldet.fst ark:words.lats

\endverbatim

This is a simplified example; you'd do further processing

to remove the original "graph scores" from the lattices and

add back in the grammar and transition scores. Also,

Ldet.fst is a specially processed version of the lexicon:

the lexicon with disambiguation symbols (but without the

loop that converts \#0 to \#0 to pass through the language

model disambiguation symbol), determinized and with the

disambiguation symbols then removed.

The mode described above can also be useful for language model

rescoring; however, it also comes in a different version,

illustrated below (this is useful for adding in LM scores to lattices, assuming

we had removed the old LM scores):

\verbatim

lattice-compose --phi-label=13461 ark:1.lats G.fst ark:2.lats

\endverbatim

Here, G.fst would be the grammar including the special "backoff symbol"

\#0 on the input side, and 13461 is the numeric label of the backoff symbol.

This form of composition treats the backoff symbol as a failure transition

(using OpenFst's PhiMatcher), which is only taken in case the

requested label did not exist: thus, we treat G.fst as a backoff

language model. This form of composition is more exact than

turning the \#0 into epsilon and compsoing normally, because it

prevents us taking backoff arcs when a non-backoff arc exists

(which amounts to a misinterpretation of the language model).

Actually, what the program lattice-compose has to do is a little more

complicated than just invoking Compose with OpenFst's PhiMatcher, because

of the way final-probabilities are treated. Because Compose doesn't use

the matcher when computing final probabilities, we can fail to take the

backoff arc when computing final probabilities. Therefore the

lattice-compose program has to modify the final probabilities

by "following through" the phi arcs, before calling the composition

algorithm. Note that this problem would not exist if we had the end-of-sentence

symbol as a label in G, but in some scripts we prefer to remove it.

Note also that "phi composition" would not work properly in general, if

the FST with phi's in it had epsilons on that same side. Thus, it makes

sense to remove epsilons from G first.

\subsection lattices_operations_interp Lattice interpolation

The program lattice-interp interpolates two sets of lattices together,

with a scaling factor. An example command line is:

\verbatim

lattice-interp --alpha=0.4 ark:1.lats ark:2.lats ark:3.lats

\endverbatim

which amounts to putting a weight of 0.4 on the scores of 1.lats and

of 0.6 on the scores of 2.lats. It keeps the alignments, if any, present

in the first archive. Note that this program will not output

any lattice if the composition is empty because the two lattices

had no paths in common, so the final archive may

have "gaps" in it. You have to build in some mechanism to produce

output for such utterances, into your decoding scripts (e.g.

see egs/rm/s3/steps/decode_combine.sh). The behavior of this

program can be simulated by combining the programs

lattice-scale, lattice-project and lattice-compose.

\subsection lattices_operations_phones Conversion of lattices to phones

The program lattice-to-phone-lattice removes the word labels from the

output side of a lattice and puts in their place phone labels. These

are worked out from the transition-ids on the input side. Note that the phone labels are

not exactly aligned with the phone boundaries (as a rule, FSTs have

no real concept of alignment between input and output symbols).

Typical usage is:

\verbatim

lattice-to-phones final.mdl ark:1.lats ark:phones.lats

\endverbatim

\subsection lattices_operations_project Lattice projection

Projection is an FST operation that turns an FST into an acceptor, either

by copying the output symbols to the input, or the input symbols to the output,

so they are both the same. The default for lattice-project is to copy the

word labels to the input side (this is useful when doing interpolation

of the scores of lattices). An example is:

\verbatim

lattice-project ark:1.lats ark:- | \

lattice-compose ark:- ark:2.lats ark:3.lats

\endverbatim

\subsection lattices_operations_equivalent Lattice equivalence testing

The program lattice-equivalent is mostly useful as a debugging tool. It

tests the equivalence of sets of lattices. It returns with exit status 0

only if all pairs of lattices in two supplied tables (e.g. archives) are

equivalent. It uses a randomized equivalence testing algorithm to do this.

A typical usage is:

\verbatim

lattice-equivalent ark:1.lats ark:2.lats || echo "Not equivalent!"

\endverbatim

Optional arguments include --num-paths (the number of paths used in the

randomized testing algorithm) and --delta, the score difference at which

scores are considered different for purposes of equivalence testing.

\subsection lattices_operations_rmali Removing alignments from lattices

The program lattice-rmali removes the alignment information (i.e. the

transition-ids) from the input side of the lattices. This is mainly useful

if you will not need that information (e.g. you only need the lattices for

language model rescoring), and you want to save disk space. An example is:

\verbatim

lattice-rmali ark:in.lats ark:word.lats

\endverbatim

\subsection lattices_operations_boost Error boosting in lattices

The program lattice-boost-ali is used in boosted MMI training. It reads in

a lattice and an alignment (both as tables, e.g. archives), and outputs the

lattices with the language model scores (i.e. the graph part of the scores)

boosted by the parameter b times the number of frame-level phone errors on that

path. Typical usage is:

\verbatim

lattice-boost-ali --silence-phones=1:2:3 --b=0.1 final.mdl ark:1.lats \

ark:1.ali ark:boosted.lats

\endverbatim

The silence phones are treated specially: wherever they appear in the lattices,

they are assigned zero error, i.e. they are not counted as errors

(this behavior can be controlled with the --max-silence option). Note that

this special treatment of silence has been adopted from MPE training where it

appeared to help; we have not investigated its exact effect on boosted MMI.

\subsection lattices_operations_post Computing posteriors from lattices

The program lattice-to-post computes, from a lattice, per-frame posterior

probabilities of the transition-ids in the lattice. This is done by a standard

forward-backward type of algorithm. Since, by convention, we store lattices

without any acoustic scaling, it will normally be necessary to supply an

acoustic scale to be used in the forward-backward algorithm. It also accepts

a language model scale, but the default (1.0) will often be most appropriate.

An example of

using this program is:

\verbatim

lattice-to-post --acoustic-scale=0.1 ark:1.lats ark:- | \

gmm-acc-stats 10.mdl "$feats" ark:- 1.acc

\endverbatim

\subsection lattices_operations_det Determinization of lattices

The program lattice-determinize implements lattice-determinization, which

essentially consists of keeping, for each word-sequence in the lattice, only

the best-scoring sequence of transition-ids. In general this process is

sensitive to the acoustic scale (because "best-scoring" depends on the scale),

but if the lattice has previously been determinized and then has only been processed

in a "word-level" way, i.e. each word-sequence still has only one transition-id

sequence, then the acoustic scale doesn't matter. The only time the acoustic

scale is likely to matter is if you generate state-level lattices, e.g. you

do lattice generation with --determinize-lattice=false.

This program has other options, that are mostly related to what to do if

determinization "blows up", i.e. exhausts memory, but in general you can just

leave these at their default values. These are mostly there because a previous

version of the determinization tended to exhaust memory.

You may want to set --prune=true if you want

to do pruning as part of the same program, but be careful that this only makes sense

if you have set the acoustic scale to an appropriate value; you might also want to

set the --beam option in that case.

A typical usage is:

\verbatim

lattice-determinize ark:1.lats ark:det.lats

\endverbatim

or:

\verbatim

lattice-determinize --acoustic-scale=0.08333 ark:state_level.lats ark:1.lats

\endverbatim

Note that lattices produced by lattice generation programs will be default already

be determinized, so it only makes sense to do determinization if you have just done

an operation like composition that makes lattices nondeterministic, or if you

have given --determinize-lattice=false to the lattice generation program to create

state-level lattices.

\subsection lattices_operations_oracle Computing oracle WERs from lattices

The program lattice-oracle takes two tables: the first of lattices, the second

of transcriptions (C++ representation: vector<int32>), and outputs the oracle

word-sequence of the lattices; it prints out the corresponding WERs in its

logging output. This is done by constructing an "edit-distance FST" and

composing this with unweighted acceptors constructed from the lattice and

from the reference.

An example (this script fragment assumes the newer, s3-style script) is:

\verbatim

cat $data/text | \

sed 's:<NOISE>::g' | sed 's:<SPOKEN_NOISE>::g' | \

scripts/sym2int.pl --ignore-first-field $lang/words.txt | \

lattice-oracle --word-symbol-table=$lang/words.txt \

"ark:gunzip -c $dir/lats.pruned.gz|" ark:- ark,t:$dir/oracle.tra \

2>$dir/oracle.log

\endverbatim

\subsection lattices_operations_tprob Adding transition probabilities to lattices

The program lattice-add-trans-probs adds in the (negated) transition probabilities to the

costs of a lattice. This is useful in forms of lattice rescoring where the original

"graph costs" are discarded and reconstructed from scratch. A typical usage is:

\verbatim

lattice-add-trans-probs --transition-scale=1.0 --self-loop-scale=0.1 \

final.mdl ark:1.lats ark:2.lats

\endverbatim

See \ref hmm_scale for more explanation about these scaling factors.

\subsection lattices_operations_to_fst Converting lattices to FSTs

The program lattice-to-fst converts an table of lattices into a table of

FSTs, in the same format used by the code that compiles the training

graphs. The resulting FSTs will be weighted word acceptors (although

in current use of this program we apply a scale of zero so there are

actually no weights). These may be used as input to the program

compile-train-graphs-fsts to produce decoding graphs that only include

the paths present in the lattice. The main use of this is to do

lattice rescoring across different models that don't share the same tree.

An example of usage is:

\verbatim

lattice-to-fst --lm-scale=0.0 --acoustic-scale=0.0 ark:1.lats ark:1.words

\endverbatim

\subsection lattices_operations_copy Copying lattices

The program lattice-copy simply copies a table (e.g. archive) of lattices.

This is mostly useful if you want to view binary FSTs in text form. For

example:

\verbatim

lattice-copy ark:1.lats ark,t:- | head -50

\endverbatim

\section lattice_nbest N-best lists and best paths

There are some situations (e.g. Viterbi training; rescoring with neural-net language

models) where we don't want the lattice structure and want either the best path

or the N best paths. Our format for N-best lists is the same as for lattices,

except for each utterance we have multiple FSTs (up to n, for some specified n).

Suppose the utterance id's are uttA, uttB, and so on. A normal Table of lattices

(e.g. an archive) will contain a lattice for uttA, one for uttB, and so on.

If we run the program

\verbatim

lattice-to-nbest --acoustic-scale=0.1 --n=10 ark:1.lats ark:1.nbest

\endverbatim

then the archive 1.nbest will contain lattices for uttA-1, uttA-2, ... uttA-2,

for uttB-1 ... uttB-10, and so on. Of course some of the utterances may not

have that many N-best entries if the lattice did not contain that many distinct

word sequences. The program lattice-to-nbest needs the acoustic scale as this

affects which paths would have the lowest score.

For some purposes it will still be inconvenient to deal with an FST and

we want an actual linear structure, e.g. just a sequence of words. For this,

we can use the following program:

\verbatim

nbest-to-linear ark:1.nbest ark:1.ali ark:1.words ark:1.lmscore ark:1.acscore

\endverbatim

This program reads in an archive of lattices, which must each be a linear FST,

and outputs 4 archives, corresponding to the input symbol sequences, the output

symbol sequences, and the acoustic and LM scores. The format (assuming

you write in text mode, e.g. with "ark,t:my_file") is as one would

expect, e.g.:

\verbatim

# head 1.words

utt-A-1 10243 432 436 10244

utt-A-2 7890 420 10244

...

\endverbatim

Remember that Kaldi always deals with integer id's; you can convert to words

using the symbol table and "utils/int2sym.pl -f 2-". The reverse transformation

can be accomplished with linear-to-nbest.

A program that might also be useful is lattice-to-1best, which is not the same

as lattice-to-nbest with --n=1, because it doesn't append "-1" to the utterance id.

You can pipe the output of this into nbest-to-linear if you want the word sequences

or something of that nature. The program lattice-best-path takes in a lattice

and outputs up to two archives, containing the word sequences and transition-id

sequences. This is there for historical reasons; the combination of lattice-to-1best

and nbest-to-linear is cleaner and more consistent with the overall framework.

\section lattices_times Times on lattices

If you want the time information of the lattices explicitly (rather than having

to count transition-ids), there is a function LatticeStateTimes (for Lattice),

and CompactLatticeStateTimes (for CompactLattice), which will give you the time

where each state is located (a number from 0 to the number of frames in the

file). Be careful that in general, the words are not synchronized with to the

transition-ids, meaning that the transition-ids on an arc won't necessarily all

belong to the word whose label is on that arc. This means that the times you

get from the lattice will (as far as the word labels are concerned) be inexact.

The same is also true of the weights; these are also not synchronized with

either the words or the transition-ids on a particular arc. If you want exact

times (e.g. for conversion to HTK lattices, or for sclite scoring), then you

should run the program lattice-align-words. This program only works if you

built your system with word-position-dependent phones, and it requires certain

command-line options to tell it which phones are in which position in the word.

See egs/wsj/s3/run.sh for an example (search for align). There is an

alternative program, lattice-align-words-lexicon, that you can use if your

system does not have word-position-dependent phones.

*/

}