how the make HCL and G graphs

[jurcicek]

Hi!

thanks for sharing the code! I am wondering whether you could share how you make the HCL and G graphs. I guess the most important part is how you do determinization and when. I found that it affects the decoded results a lot. I made the on-the-fly composition working using your table compose; however, the RTF for the on-the-fly composition HCL and G vs. statistically composed HCLG is significantly worse on my graph, RTF of 0.48 vs RTF 0.28.

Here is how I prepare the HCL graph:

fstdeterminize ${lang}/L_disambig.fst | fstarcsort --sort_type=ilabel > ${dir}/det.L.fst

fstcomposecontext \
     --context-size=$N --central-position=$P \
     --read-disambig-syms=${lang}/phones/disambig.int \
     --write-disambig-syms=${lang}/disambig_ilabels_${N}_${P}.int \
     ${dir}/ilabels_${N}_${P} ${dir}/det.L.fst | fstarcsort > ${dir}/CL.fst

make-h-transducer \
     --disambig-syms-out=${dir}/h.disambig.int \
     --transition-scale=$tscale \
     ${dir}/ilabels_${N}_${P} \
     ${tree} \
     ${model} > ${dir}/Ha.fst

fstconvert \
    --fst_type=olabel_lookahead \
    --save_relabel_opairs=${dir}/cl.irelabel ${dir}/det.Ha.fst |
    fstarcsort --sort_type=olabel > ${dir}/la.Ha.fst
    
fstrelabel --relabel_ipairs=${dir}/cl.irelabel ${dir}/CL.fst | \
    fstarcsort --sort_type=ilabel | \
    fstcompose ${dir}/la.Ha.fst - > ${dir}/det.HaCL.fst

fstrmsymbols ${dir}/h.disambig.int ${dir}/det.HaCL.fst | \
    fstrmepslocal | \
    add-self-loops --self-loop-scale=$loopscale --reorder=true ${model} - | 
    fstarcsort --sort_type=olabel > ${dir}/HCL.fst

I am also wondering whether you tried to use LabelLookAheadMatcher instead of ArcLookAheadMatcher at

kaldi-decoders/bin/latgen-lazylm-faster-mapped.cc

Line 41 in af1efd2

typedef ArcLookAheadMatcher<SM> LA_SM;

I cannot make it work.

Thanks for any advice!

[jpuigcerver]

Hi,

Thanks for your interest. If you are able to compose HCLG statically, it is going to be faster than the dynamic composition, for sure. The latgen-lazylm-faster-mapped tool was created when composing it is unfeasible due to the huge graph that it would produce (think of very high order language models like 10-gram language models). If you are able to create HCLG statically, you should.

The accuracy results should be very similar, at least I always obtained the same results in my experiments when comparing the static HCLG vs. on-the-fly HCL and G composition, which this tool does.

You can check this script which creates the HCL and G transducers for a handwritten text recognition experiment:
https://github.com/jpuigcerver/Laia/blob/87ed2e7157879ede84012c5ba6fae12f8afb5f42/egs/iam/utils/build_word_fsts.sh

Your steps to create HCL seem correct. You follow some steps that I don't, but I guess that it is because you have to deal with triphones and other particularities of ASR.

I could never make LabelLookAheadMatcher work either, but that's probably because of my then-limited knowledge about Kaldi. At some point, I should try again to make it work, but it will take time.

[tbluche]

Hi there,
Nice work.. Joan, I should have talked to you a few weeks ago when I started implementing dynamic decoding for ASR.. I ended up doing pretty much what you had already done :p

You may relabel the whole HCL at the end of the graph creation

fstconvert --fst_type=olabel_lookahead --save_relabel_opairs=$graph_dir/g.irelabel $graph_dir/HCL.fst >$graph_dir/left.fst

Don't forget to relabel your G.fst before composing

fstrelabel --relabel_ipairs=$graph_dir/g.irelabel $graph_dir/G.fst | fstarcsort >$graph_dir/right.fst

And by the way, OpenFST should be able to choose the best filters depending of the properties of the FST (see the end of this file :

// Specializes for StdArc to allow weight and label pushing.
template <>
class DefaultLookAhead<StdArc, MATCH_OUTPUT> {
 public:
  using M = LookAheadMatcher<Fst<StdArc>>;
  using SF = AltSequenceComposeFilter<M>;
  using LF = LookAheadComposeFilter<SF, M>;
  using WF = PushWeightsComposeFilter<LF, M>;
  using ComposeFilter = PushLabelsComposeFilter<WF, M>;
  using FstMatcher = M;
};

So fstcompose left.fst right.fst will use those composition filters.

Regarding the RTF, I had some issues too, and profiling it showed that it was mainly due to the weight pushing, but also to some extent to the on-demand composition that cannot come for free.

[jurcicek]

Many thanks @jpuigcerver . Your response was very helpful. At the end, I managed to get LabelLookAheadMatcher to work. It is mostly based on the code and examples in opendcd, e.g. https://github.com/opendcd/opendcd/blob/master/script/makegraphotf.sh.

Here is how I build and prepare the HCL and G. In fact, my final solution is very similar to what was suggested by @tbluche.

#---------------

fstdeterminize ${lang}/L_disambig.fst | fstarcsort > ${dir}/det.L.fst

#---------------

fstcomposecontext \
    --context-size=$N --central-position=$P \
    --read-disambig-syms=${lang}/phones/disambig.int \
    --write-disambig-syms=${lang}/disambig_ilabels_${N}_${P}.int \
    ${dir}/ilabels_${N}_${P} ${dir}/det.L.fst | \
    fstarcsort > ${dir}/CL.fst

#---------------

make-h-transducer \
    --disambig-syms-out=${dir}/h.disambig.int \
    --transition-scale=$tscale \
    ${dir}/ilabels_${N}_${P} \
    ${tree} \
    ${model} > ${dir}/Ha.fst

cat ${dir}/Ha.fst > ${dir}/det.Ha.fst

#---------------

fstconvert \
     --fst_type=ilabel_lookahead \
     --save_relabel_ipairs=${dir}/h.orelabel ${dir}/CL.fst |
     fstarcsort --sort_type=ilabel > ${dir}/la.CL.fst
    
fstrelabel --relabel_opairs=${dir}/h.orelabel ${dir}/det.Ha.fst | \
     fstarcsort --sort_type=olabel | \
     fstcompose - ${dir}/la.CL.fst > ${dir}/det.HaCL.fst

#---------------

fstdeterminize ${dir}/det.HaCL.fst | \
    fstrmsymbols ${dir}/h.disambig.int | \
    fstrmepslocal | \
    fstpushspecial | \
    fstminimizeencoded | \
    add-self-loops --self-loop-scale=$loopscale --reorder=true ${model} - | 
    fstarcsort --sort_type=olabel |
    fstconvert --fst_type=const > ${dir}/HCL.fst

#-----------------------------

fstconvert --fst_type=olabel_lookahead --save_relabel_opairs=${dir}/g.irelabel ${dir}/HCL.fst > ${dir}/HCLr.fst
fstrelabel --relabel_ipairs=${dir}/g.irelabel ${lang}/G.fst | \
    fstarcsort | 
    fstconvert --fst_type=const > ${dir}/Gr.fst

fstcompose ${dir}/HCLr.fst ${dir}/Gr.fst | \
    fstconvert --fst_type=const > ${dir}/HCLrGr.fst

The composed HCLG for KALDI decoder is created as follows:

ComposeFst<StdArc>* OTFComposeFst(
    const StdFst &ifst1, const StdFst &ifst2,
    const CacheOptions& cache_opts = CacheOptions()) {

  typedef LookAheadMatcher< StdFst > M;
  typedef AltSequenceComposeFilter<M> SF;
  typedef LookAheadComposeFilter<SF, M>  LF;
  typedef PushWeightsComposeFilter<LF, M> WF;
  typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
  typedef M FstMatcher;
  
  ComposeFstOptions<StdArc, FstMatcher, ComposeFilter> opts(cache_opts);

  return new ComposeFst<StdArc>(ifst1, ifst2, opts);
}

My observation is that when I want the same WER then I must lower pruning for OTF composed HCL and G. This results in about 20 % increase in RTF. If I fix RTF then my WER is about 20 % relatively worse for OTF composed HCL and G. So, there is some cost of OTF composition though it is not that bad. It is usable.

Please note that preparation of the HCL and G is a bit different from the one in https://github.com/opendcd/opendcd/blob/master/script/makegraphotf.sh . For example, I could not determinize Ha.fst as it appeared to be non-functional. Also, the determinization of L is important, otherwise the final HCL graph will not be "small enough" and therefore the on the OTF composition that efficient.

[alongwithyou]

this is very good response!

[shakingWaves]

@jurcicek ,I have built the HaCL.fst. But ,the command "fstdeterminize --use-log=true HaCL.fst det.HaCL.fst" will be fail, because of the existence of loop, such as "self-loop". How can I solve it?

[daanzu]

I too get stuck with fstdeterminize ${dir}/det.HaCL.fst not terminating.

[jpuigcerver]

Hello all,

Make sure that you have replaced the epsilons in the input of your LM fst (G.fst) with a disambiguation symbol (i.e. #0), as well as to have produce a deterministic lexicon, also by introducing the appropriate disambiguation symbols.

Please, refer to Kaldi's documentation to understand how the WFST construction works: http://kaldi-asr.org/doc/graph.html

[shakingWaves]

@daanzu @jpuigcerver Unlike NFAs, which can always be determinized, not all WFST have
an equivalent deterministic WFST. Because, it does not meet the twins property of determinization. you all could refer to "An Approximate Determinization Algorithm for Weighted Finite-State Automata".

[daanzu]

Thanks for the info. I'm quite happy to have been able to get it to work if I skip the step to determinize HaCL.fst. Now I'm just curious how @jurcicek apparently was able to determinize HaCL.fst in Kaldi, but the nondeterminism isn't a showstopper for me. By the way, thanks for the interesting paper link, @shakingWaves.

[jpuigcerver]

@shakingWaves @daanzu It is true that, in general, not all WFST admit determinization.

However, if you are using traditional models for G (n-grams) and L, and you have introduced the appropriate disambiguation symbols, the resulting WFST does admit determinization (please, refer to Kaldi's documentation).

[daanzu]

I am using a simple non-ngram G, but that shouldn't be able to affect the determinization of HaCL.fst (there's no G there yet!). I think I'm using a traditional L and have introduced the appropriate disambiguation symbols (I'm following the recipe from @jurcicek). However, I've even tried a toy L (below), and its HaCL.fst also failed to determinize.

!SIL SIL
<UNK> SPN
ache EY K

Not a big deal, just curious.

[shakingWaves]

when I run the command "fstconvert --fst_type=olabel_lookahead --save_relabel_opairs=${dir}/g.irelabel ${dir}/HCL.fst > ${dir}/HCLr.fst", error "FATAL: IntervalReachVisitor: cyclic input" occurs. How can I solve it ?