danpovey
commented
3 years ago That's interesting, I was not aware of that paper.
I am not opposed to creating, in k2, more specialized FSTs, in the same way OpenFst has multiple FST types.
E.g. like we already have DenseFsaVec. There wouldn't be a common inheritance hierarchy at the C++ level,
because such things aren't quite so simple on GPUs. I'd be open to, eventually, creating some more commonalities
at the Python level though.
So, for instance, we could add a DenseNgramFsa type to k2, which would make it possible to implement LF-MMI with
higher-order n-grams than we currently have, without pruning.
(However, k2 does support beam-pruned intersection, which is already a pretty painless way to accelerate these things. We'd have to investigate whether the intersection speed is even a problem, once we implement LF-MMI with higher-order ngram phone models).
galv
Just a general comment. Keep in mind this may be a dead end.
In particular, I am referring to the fact that snowfall has MmiTrainingGraphCompiler, while k2 does not: https://github.com/k2-fsa/snowfall/blob/c5ffa3fbaa1bee29b930cc290fcb6a35cb652397/snowfall/training/mmi_graph.py#L44
I am looking at k2 from the point of view of performance. First of all, performance may not be the most important thing for k2, since objective functions usually do not take up most of the run time during training. So again, this may be a deadend.
If you take a look at the work here: https://www.isca-speech.org/archive/Interspeech_2017/pdfs/1557.PDF, they show that n-gram language WFSTs can be viewed as block-diagonal matrices. This is particularly beneficial for accelerators today because that means we can use already-efficient linear algebra routines to implement intersection. In particular, for CUDA, we can use block SpMM in cusparse. Effectively, this means that we can make the denominator computation of LF-MMI very fast. This is because we can turn an otherwise bandwidth-bound kernel into a computation-bound kernel.
By default, that will be on the probability semiring, which has numerical precision problems when you use an input sequence that is too long, but that that appears not to happen until you reach an input sequence length of 200 frames according to this work: http://bacchiani.net/resume/papers/ASRU2017.pdf (same authors as above). Given that people like to subsample 3x or 6x, this could actually mean you could train on 200 10ms 6 = 12 second input audio sequences. You can also consider using double precision tensor cores to increase the maximum input sequence.
Here's the problem with implementing these things today in k2: k2 must accept arbitrary WFSTs into its operations. In particular, snowfall appears to be the source of WFSTs today. At first, I thought that we could detect whether a particular WFST is an n-gram WFST, in which case we can relabel its vertices to make its adjacency matrix block diagonal and use the faster kernel. However, this is equivalent to the graph isomorphism problem, which has no polynomial time algorithm. So it seems clear that K2 must "own" graph construction in some cases. In addition, for the sake of unit testing, I would need to have the graph creation code in K2, rather than snowfall.
So ultimately I am wondering how much opposition there is to having code somewhat redundant to snowfall's MmiTrainingGraphCompiler (and friends) in k2 rather than snowfall.