Operations on lattices

下面我们讨论了一些网格上的运算操作和它们对应的程序。

Pruning lattices

网格可以用一个设定的 pruning beam来剪枝。这会去掉和网格中最优路径的代价相差不够小的那部分 arcs和 states。对每个网格，lattice-prune首先根据设定的尺度缩放 acoustic weight，然后调用 OpenFst的Prune()函数，最后对 acoustic weight进行逆缩放。一个命令行示例：

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

注意：为了提高效率，剪枝运算是在 Lattice格式下完成的，但是会在写出时转换为 CompactLattice。

Computing the best path through a lattice

lattice-best-path计算通过网格的最优路径，并输出输入符号序列（alignment）和输出符号序列（transcription）。通常输入和输出都是 archive。一个命令行示例：

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

Computing the N-best hypotheses

lattice-nbest计算通过网格的 N-best路径（利用 OpenFst的ShortestPath()函数），输出是一个有特定结构的网格（a CompactLattice）。正如在 OpenFst的ShortestPath()的文档中说明的，开始状态会有（至多）n个 arcs，每一个都是一条单独路径的开始。但是这些路径可以共享后缀。一个命令行示例：

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

Language model rescoring

因为 LatticeWeight的“graph part”（第一部分）包含了语言模型得分和转换模型(transition-model)得分，所有的发音或静音概率，我们不能只用新的语言模型得分替换它，否则会丢失后两个。所以，我们要先减去旧的 LM概率再加上新的 LM概率。这两个阶段的核心操作是组合（还有一些权值的缩放，等等）。相应的命令行是：首先，一处旧的 LM概率

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

然后加上新的 LM概率

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

也有其他的方法可以做到这一点，见下面lattice-compose的文档。要解释程序 lattice-lmrescore做了些什么，我们先描述一个简化的版本。假设给定 LM-scale S和 LM G.fst。我们首先把 G.fst中的 costs都乘以 S。然后对每个网格，把它组合到 G的右边，进行 lattice-determinize（仅保留每个词序列的最优路径），然后写出。如果 S是正值，这没有问题，但如果 S是负值，这相当于对每个词序列取了 G的最差路径。为了解决这一问题，我们采用如下做法。对每个输入的网格，首先用 S的逆缩放网格的 graph (or LM) costs；然后组合到 G.fst的右边；执行 lattice-determinization，保留每个词序列的最优路径；然后用 S缩放网格的 graph/LM scores。这样 S为负值时也是对的。这个方法只有在输入网格的每个词序列都只有一条路径时（e.g. 它经过了 lattice determinization）才有效。我们假定所有由程序处理的网格都有这个特点（所以直接写 “raw” state-level网格不是一个好主意，除非你知道你要做什么）。

注意为了让组合生效，程序需要把 G.fst从 tropical semiring映射到 LatticeWeight semiring。这通过把 G.fst的权值赋给权重的第一部分（the "graph" part），然后权重的第二部分置零（在半环中，它是1）。在 C++层，这个映射通过 OpenFst的 MapFst完成，其中定义了一个 Mapper类来映射 StdArc到 LatticeArc，然后根据需求创建一个 MapFst类型的对象，完成 G.fst到 LatticeWeight的权重部分的转换。

Probability scaling

可以通过一个 2x2的矩阵来对网格权重的概率进行比例缩放。相应的命令行程序是lattice-scale。一个示例：

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

它实际上不会被经常使用，因为我们希望 archive中的 acoustic weights是没有经过缩放的；需要进行缩放的程序可以接受一个-acoustic-scale选项。这些程序会应用缩放，执行运算（比如 determinization or pruning），然后逆缩放。对大多数操作，我们不会缩放 LM概率；然而，它有时也会被用到，e.g. 在区分性训练(discriminative training)时同时调整 LM和 acoustic尺度可能是有好处的。lattice-scale程序接受-lm2acoustic-scale和-acoustic2lm-scale选项。例如，程序会把-lm2acoustic-scale乘以权重的 LM部分然后加到新权重的 acoustic部分。我们引入这些主要是考虑到完整性。

Lattice union

lattice-union计算两个网格的 union（和其他程序一样，程序遍历 archive中的网格集合）。主要设想的用途是在区分性训练中（特别是 MMI），为了保证分母网格中的 transcription是正确的。一个命令行示例是：

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

程序调用 OpenFst的Union()函数，进行 lattice-determinization来保证每个词序列仅有一条路径，然后写出。实际上 lattice union发挥作用的场景并不多（e.g. 在由不同特征或模型计算得到的网格上进行 union并没有什么意义）

Lattice composition

lattice-compose有多种工作模式。一种是组合网格。这是在转换器(transducer)形式下完成的，i.e.把网格看做 transition-ids到 words的一个转换器。这一般会在映射一个网格集合到输出（来获得词到词的转换器）后完成。典型的用法是：

lattice-project ark:1.lats ark:- | \ lattice-compose ark:- ark:2.lats ark:3.lats

现在，3.lats的路径会具有 1.lats和 2.lats中得分的和。你可以用lattice-interp（见下一节）来一步完成这一目的。

另一种模式是组合网格和一个固定的 FST。为了这个目的，FST被动态地转换为网格；FST的权重解释为网格权重的“graph part”。一个例子是，把网格转换成音素，再和字典组合转换回词，例如：

lattice-to-phone-lattice final.mdl ark:1.lats ark:- | \ lattice-compose ark:- Ldet.fst ark:words.lats

这是一个简化了的例子；你可以进一步处理，去除网格中原来的“graph scores”然后加上 grammar和 transition scores。同时，Ldet.fst是一个专门处理了的词典：带消歧符号的词典（但是没有 #0到 #0的环，来通过语言模型消歧符号），determinized and with the disambiguation symbols then removed.

上面的模式对语言模型重打分也很有用；然而它也有不同的版本，如下所示（这对把 LM得分加到网格里时很有用，假定我们已经移除了旧的 LM得分）：

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

这里，G.fst是在输入端包含特殊的“回退符号”(backoff symbol) #0的语法，13461是这个回退符的数字标号。这种组合形式把回退符看做一个失败的 transition（利用 OpenFst's PhiMatcher），当请求的标签不存在时被采用：所以 G.fst被看做一个回退语言模型。

Lattice interpolation

lattice-interp根据一个缩放参数，对两个网格做内插。例子：

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

意思是在 1.lats的得分上乘以0.4，在 2.lats上乘以0.6。它会维持第一个 archive中的对齐信息，如果有的话。如果两个网格没有共同路径，组合会为空，程序就不会输出任何网格，所以最后的 archive中可能有“gaps”。你需要建立某种机制来为这些 utterances构造输出，到解码脚本中（e.g. 见 egs/rm/s3/steps/decode_combine.sh）。这个程序的功能可被模拟为 lattice-scale,lattice-project,lattice-compose的组合。

Conversion of lattices to phones

lattice-to-phones-lattice在网格的输出端删除词标签，替换为音素标签。这些是通过输入的 transition-ids获得的。注意音素标签并不是和音素边界对齐的（FSTs 在输入和输出符号之间没有对齐的概念）。典型用法是：

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

Lattice projection

Projection 是把 FST转变为 acceptor的一个 FST操作，在输入和输出符号间进行拷贝，让它们一致。lattice-project默认是把词标签拷贝至输入端（这在做网格内插时很有用）。例子是：

lattice-project ark:1.lats ark:- | \ lattice-compose ark:- ark:2.lats ark:3.lats

Lattice equivalence testing

lattice-equivalent作为一个调试工具非常有用。它测试网格是否相等，如果是，返回状态0。它通过利用一个随机化的相等测试算法来完成。一个例子：

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

可选的参数包括 -num-paths（在随机化的测试算法中用到的路径数）和 -delta（在相等测试时允许的得分的差异值）。

Removing alignments from lattices

lattice-rmali从网格的输入端移除对齐信息（i.e. the transition-ids）。这在你不需要某种信息时很有用（e.g. LM重打分时你只需要网格），而且可以节省储存空间。例子：

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

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:

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

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.

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:

lattice-to-post --acoustic-scale=0.1 ark:1.lats ark:- | \ gmm-acc-stats 10.mdl "$feats" ark:- 1.acc

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:

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

or:

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

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.

Computing oracle WERs from lattices

lattice-oracle输入是两个 tables：第一个是网格，第二个是 transcriptions（C++ 用 vector<>表示），输出是网格的词序列；在日志中会打印出相应的 WERs。这是通过构建一个“edit-distance FST”，把它和由网格和参考得到的 unweighted acceptors组合起来，来完成的。

一个例子（这个脚本片段来自 s3系列）：

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

Adding transition probabilities to lattices

lattice-add-trans-probs把 transition概率加到网格的 costs中。这在做丢弃原始的 graph costs并从头重建的 lattice rescoring时很有用。一个典型用法：

lattice-add-trans-probs --transition-scale=1.0 --self-loop-scale=0.1 \ final.mdl ark:1.lats ark:2.lats

关于这些缩放参数的更多解释，见 Scaling of transition and acoustic probabilities。

Converting lattices to FSTs

lattice-to-fst将网格转换为 FSTs，和编译训练图(the training graphs)的代码用到的格式相同。得到的 FSTs就是 weighted word acceptors（尽管目前的程序中我们乘以了系数0，也就是没有 weights）。它们可以作为compile-train-graphs-fst的输入来生成只包含网格中存在的路径的解码图。它的主要用途是在不共享同一个树的模型间做 lattice rescoring。一个例子是：

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

Copying lattices

lattice-copy作用就是拷贝网格，这在你想看二进制 FST的文本形式时很有用。例如：

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