14 ms·
This uses dense (soft/weighted) transitions from any state to any state, and then some regularization to guide it to more sparse solutions. In practice, the nu
by albertzeyer 4y ago
This uses dense (soft/weighted) transitions from any state to any state, and then some regularization to guide it to more sparse solutions.
In practice, the number of states can be huge (thousands, maybe millions), so representing this as a dense matrix (a 1Mx1M matrix is way too big) is not going to work. It must be sparse, and in practice (all FST you usually deal with) it is. So it's very much a waste to represent it as a dense matrix.
That's why there are many specialized libraries to deal with FSTs. Also in combination with deep learning tools. See e.g. K2 (https://github.com/k2-fsa/k2 https://github.com/k2-fsa/k2).
- puttycat 4y agoIndeed this would need to predefine a maximum number of states. This work referenced also in the OP paper uses recurrent neural nets and a genetic algorithm to evolve the minimal number of states needed: https://arxiv.org/abs/2111.00600 https://arxiv.org/abs/2111.00600
- woodson 4y agoFB research has their own version of automatic differentiation of WFSTs: https://github.com/gtn-org/gtn https://github.com/gtn-org/gtn See also https://github.com/facebookresearch/gtn_applications https://github.com/facebookresearch/gtn_applications which contains examples of applications such as handwriting recognition and speech recognition.