Differentiable Weighted Finite-State Transducers
Authors: Awni Hannun
Vineel Pratap
Jacob Kahn
Wei-Ning Hsu
Venue:  (2021)
Keywords: weighted automata
automatic differentiation
sequence models

Abstract: We introduce a framework for automatic differentiation with weighted finite-state transducers (WFSTs) allowing them to be used dynamically at training time. Through the separation of graphs from operations on graphs, this framework enables the exploration of new structured loss functions which in turn eases the encoding of prior knowledge into learning algorithms. We show how the framework can combine pruning and back-off in transition models with various sequence-level loss functions. We also show how to learn over the latent decomposition of phrases into word pieces. Finally, to demonstrate that WFSTs can be used in the interior of a deep neural network, we propose a convolutional WFST layer which maps lower-level representations to higher-level representations and can be used as a drop-in replacement for a traditional convolution. We validate these algorithms with experiments in handwriting recognition and speech recognition.

Under review as a conference paper at ICLR 2021
DIFFERENTIABLE WEIGHTED FINITE-STATE TRANSDUCERS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce framework for automatic differentiation with weighted finite-state transducers (WFSTs) allowing them to be used dynamically at training time. Through the separation of graphs from operations graphs, this framework en- ables the exploration of new structured loss functions which in turn eases the en- coding of prior knowledge into learning algorithms. We show how the framework can combine pruning and back-off in transition models with various sequence- level loss functions. We also show how learn over the latent decomposition of phrases into word pieces. Finally, to demonstrate that WFSTs can be used in the interior of deep neural network, we propose a convolutional WFST layer which maps lower-level representations to higher-level representations and can be used as a drop-in replacement for a traditional convolution. We validate these algorithms with experiments in handwriting recognition and speech recognition.
INTRODUCTION
Weighted finite-state transducers (WFSTs) are commonly used tool in speech and language pro- cessing (Knight& & May, 2009; Mohri et al. 2002). They are most frequently used to combine predictions from multiple already trained models. In speech recognition, for example, WFSTs are used combine constraints from an cooustic-to-poneeeee model, a lexicon mapping words to pro- nunciations, and a word-level language model. However, combining separately learned models using WFSTs only at inference time has several drawbacks, including the well-known problems of exposure bias (Ranzato et al. 2015) and label bias (Bottou) 1991] Lafferty et al.) (001).
Given that gradients may be computed for most WFST operations, using them only at the inference stage of a learning system is not hard limitation. We speculate that this limitation is primarily due to practical considerations. Historically, hardware has not been sufficiently performant make training with WFSTs tractable. Also, no implementation exists with the required operations which supports automatic differentiation in a high-level yet efficient manner.
We develop a framework for automatic differentiation through operations on WFSTs. We show the utility of this framework by leveraging it to design and experiment with existing and novel learning algorithms. Automata are a more convenient structure than tensors to encode prior knowledge into learning algorithm. However, not training with them limits the extent to which this prior knowledge can be incorporated in useful manner. A framework for differentiable WFSTss allows the model to jointly learn from training data as well as prior knowledge encoded in WFSTs. This enables the learning algorithm to incorporate such knowledge in the best possible way.
Use of WFSTs conveniently decomposes operations from data (i.e. graphs). For example, rather than hand-coding sequence-level loss functions such as Connectionist Temporal Classification (CTC) (Graves et 2006) or the Automatic Segmentation Criterion (ASG) (Collobert et al. 2016), may specify the assumptions of the criteria in graphs and compute the resulting loss with graph operations. This facilitates exploration in the space such structured loss functions.
We show the utility of the differentiable WFST framework by designing and testing several algo- rithms. For example, bi-gram transitions may be added to CTC with a transition WFST. We seale transitions to large token set sizes by encoding pruning and back-off in the transition graph.
Word pieces are commonly used as the output of speech recognition and machine translation mod- els (Chuu al. 2018 Sennrich al. 2016). The word piece decomposition for word is learned

---

Under review as a conference paper at ICLR 2021
from gtn import
def A5G salieeisiionn ons, transitiors target):
Compute constrained and normalization graphs:
intersect (intersect (target, transitions), emissicns)
4 intersect (transitions, emissions)
Forward both grapha:
A_score forward_aaore
7_score Torward_score
Compute loss: loss negate (suberact (A_acora, X_scorel]
Clear previous gradients:
amt ons sero_grad transit monssiiionn... sero_grad()
Compute gradients:
raccdarrdooo clasa, retain_graph-salle losa. (osa. emissions.gradie transitions.grad
Figure 1: An example using the Python front-end of gtn to compute the ASG loss function and gradients. The inputs to the ASG function are all gtn. Graph objects.
with a indeeendeenndnnt model. Instead, we use WFSTs to marginalize over the latent word piece decomposition training time. This lets the model learn decompositions salient the task hand.
Finally, we show that WFSTs may used as layers themselves intermixed with tensor-based based layers. We propose convolutional WFST layer which maps lower-level representations higher-level representations. The WEST convolution can be trained with the rest of the model and results in improved accuracy with fewer parameters and operations compared to traditional convolution.
In summary, our contributions are:
A framework for automatic differentiation with WFSTs. The framework supports both C++ and Python front-ends and is available at htttps://wwt anonymized. com
We show that the framework may be used express both existing sequence-level loss functions and to design novel sequence-level loss functions.
We propose a convolutional WFST layer which can used in the interior of a deep neural network to map lower-level representations to higher-level representations.
We demonstrate the effectiveness of using WFSTs in the manners described above with experiments in automatic speech and handwriting recognition.
2 RELATED WORK
wealth of prior work exists using weighted finite-state automata in speech recognition, natural language processing, optical character recognition, and other applications (Breuel) (0088) Knight & May] 2009 Mohri 1997 Mohri et al., 2008 Pereira et al. 1994). However, the use of WFSTs is limited mostly the inference stage of predictive system. For example, Kaldi, commonly used toolkit for automatic speech recognition, uses WFSTs extensively, but in most cases for inference or estimate the parameters of shallow models (Povey et al. [00IT). some cases, WFSTs are used statically to incorporate fixed lattices in discriminative sequence criteria (Kingsbury 2009
Kingshury et al., 2012) et al. 2013 Vesely al. 2013).
Implementations of sequence criteria in end-to-end style training are typically hand-crafted with careful consideration for speed (Amodei et al. 2016 Collobert et al. 2019 Povey et al. 2016). The use of hand-crafted implementations reduces flexibility which limits research. In some cases, such as the fully differentiable beam search of Collobert et al. (2019). achieving the necessary computational efficiency with a WFST-basee implementation may not yet be tractable. However, show that many common cases we can have the expressiveness afforded by the differentiable WFST framework without paying unacceptable penalty in execution time.
first step,
2

---

Under review as a conference paper at ICLR 2021
The ideas of learning with WFSTs (Eisner 2002) and automatic differentiation through operations 1997) are not new. However, no simple and efficient frameworks exist. Especially related to this work, and inspiring the name of our framework, are the graph transformer networks of [Bottou et al. 1997). Generalized graph transducers (Bottou et al., 1996) are more expressive than WFSTs, allowing arbitrary data as edge labels. When composing these graphs, one defines an edge matching function and a "transformer" to construct the resulting structure. While not this general, differentiable WFSTs nevertheless allow for vast design space of interesting algorithms, and perhaps make more pragmatic trade-off between flexibility and efficiency.
on graphs (Bottou et al.
Highly efficient libraries for operations on WFSTs exist, notably OpenFST and its predecessor FSM (Allauzen et al., [2077] MMhri et al.] 2000). We take inspiration from OpenFst in the inter- face and implementation of many our functions. However, the design implications of operating on WFST's with automatic differentiation are quite different than those of the use cases OpenFST has been optimized for. We also draw inspiration from libraries for automatic differentiation and
deep learning (Collobert et al. 2011 Paszke al. 2019 Pratap al. 2019 Tokui et al. 2015).
Some of the algorithms we propose, with the goal of demonstrating the utility of the differentiable WFST library, are inspired by prior work. Prior work has explored pruning the set of allowed
alignments with CTC, and in particular limiting the spacing between output tokens (Liu et al.) 2018). Learning n-gram word decompositions with both differentiable (Liu et al. 2017) and non- differentiable (Chan et al. 2017) loss functions has also been explored.
3 DIFFERENTIABLE WEIGHTED FINITE-STATE TRANSDUCERS
A weighted finite-state acceptor A 6-tuple consisting of an alphabet Σ. set of states Q. start states Q.. accepting states Q.. a transition function (q. p) which maps elements of Q x Σ to elements of Q. and a weight function w(g, p) which maps elements of Q x to IR weighted finite-state transducer T is a 7-tuple which augments an acceptor with an output alphabet A. The transition function x (4g p, r)) and weight function w(q. p, r) map elements of Q x Σ to elements of Q and I respectively. In other words, each edge of transducer connects two states and has an input label p. an output label r and a weight w E IR.
We denote input by p == [pi....., Pr] where each p. E E. An acceptor A accepts the input p if there exists a sequence of states 4++1 = x(q. P;) E Q such that q1 E Q, and 9r+1 E Qa. With a slight abuse of notation, we let p A denote that A accepts p. The score of p is given by s(p) E w(g, Let r = .rr,.....P7 rT] a path with r; E A. A transducer T transduces the input to the output r (i.e. rp,r) E '7) if there exists sequence of states gi+1 = x x Pi, ri) E Q such that Fi E Q. and @T+1 E Qa. The score of the pair (p.r) r) is given by s(p, r) - - w(g:, Pi, ri).
We restrict operations to the log and tropical semirings. In both cases the accumulation of weights along path is with addition. In the log semiring the accumulation over path scores is with log- sum-exp which we denote by logadd; s; = log e In the tropical semiring, the accumulation over path scores is with the max, max; s;. We allow e transitions in both acceptors and transducers. An c input (or output) on an edge means the edge can be traversed without consuming an input (or emitting an output). This allows inputs to map to outputs of differing length.
3.1 OPERATIONS
We briefly describe a subset of the most important operations implemented in our differentiable WFST framework. For a more detailed discussion of operations on WFSTs see e.g. Mohri (2009).
Intersection We denote by B Ad A₂ the intersection of two acceptors Ai and A2. The inter- sected graph B contains all paths which are accepted by both inputs. The score of any path in is the sum of the scores of the two corresponding paths in Aj and Ag.
Composition The same symbol denotes the composition of two transducers U = Ti o Tz. If transduces p to and To transduces to r then U/ transduces p to r. As in intersection, the score of the path in the composed graph is the sum of the path scores from the input graphs.
Forward and Viterbi Score The forward score of T is logadd s(p,r) r). Similarly, the Viterbi score of T is max r).
3

---

Under review as a conference paper at ICLR 2021
are/O
REAA
brabyi
(a) Token graph Ta
(b) Label graph y
(c) Alignment graph 7 y
ar-
bid
6
all
bidd
hr.4
by.4
oll
(d) Emissions graph &x
(e) Constrained graph A = T o oo
Figure 2: The graphs used to construct the ASG sequence criterion. The are label "p:r/w" denotes an input label p, output label and weight w. Graphs with just "p/w" are acceptors.
Viterbi Path The Viterbi path of is given by arg max sp,r).
The forward score, Viterbi score, and the Viterbi path for acceptor A are defined in the same way using just p. In a directed acyelic graph these operations can be computed time linear the size of the graph with the well-known forward and Viterbi algorithms (Juratsky 2000 Rabiner 1989).
We support standard rational operations including the union (A+ B), concatenation (ABB), and the Kleene closure (A4*) of WFSTs. To enable automatic differentiation through complete computations, we support slightly non-standard operations. We allow for the negation of all the ares weights in a graph and the addition subtraction of the are weights of two identically structured graphs.
3.2 AUTOMATIC DIFFERNNTITION
For sake of automatic differentiation, every operation in section accepts as inputs one or more graphs and returns graph as output. For example, the forward score returns "scalar" graph with a single are between a start state and accepting state, with the score as the are weight. The Viterbi path outputs the linear graph representing the best path p" with p as the arc labels. Jacobians of the output graph weights with respect to the weights of the input graphs may be computed for of the operations described so far. Hence, the chain rule may be used compute Jacobians or gradients of outputs with respect to the inputs of compositions of graph operations.
The WFST framework implements reverse-mode automatic differentiation following existing deep learning frameworks (Pratap et al., 2019; Paszke et al. 2019). Figure gives an example Python implementation which computes gradients for the ASG criterion. order to enable second-order differentiation, among other design considerations, the gradient with respect to a graph is also a graph. This adds little additional overhead as the two graphs share the underlying graph topology. The weights of the gradient graph are the gradients with respect to the weights of the graph.
LEARNING ALGORITHMS
Let X = [x ( 2T) E be sequence of observations and = [vi,..., wol E W label. A sequence-level objective for the (X, 3) pair can be specified with two weighted automata:
log X)= = Σ
logadd s(p) - Σ
logadd s(p).
(I)
PEAX.
PEZx
The target constrained graph, Ax.y, is constructed from the observation and target pair and the normalization graph, Zx, is constructed only from the observation. We require Ax,x C Zx.
The key ingredients to make equation operational are 1) the structure of A and and 2) the source of the weights. The graph structures can be specified through functions graphs. The initial are weights come from the data itself or arbitrary learning algorithms (deep networks, n-gram language models, etc.) capable of providing useful scores elements of X and W.

---

Under review as a conference paper at ICLR 2021
a/D
Rel
<bs00
chouD
<boil
<ho-t
dist
diss
(a) Blank token graph.
(b) Alignment graph (T }).
Figure 3: The primary difference between ASG and CTC is the inclusion of the blank token graph (a) which allows for optional transitions <b> and results in the CTC alignment graph (b).
ataria, a)
a/n(a, b, a)
h, a
butaa b)
a/ux(b,
clara, c)
c/3(a, b)
b/w(b, b)
b
b
b,h
chetth
alvic, a)
b/ur(b)
<lj(b)
clatscoo..e
chw(c)
charlc.))
(a) A bigram graph for the token set [a.b.c}.
(b) An example of back-off in trigram graph.
Figure 4: Transition graph examples. The n- g-gram score is w and the back-off weight.
The ASG (Collobert et al. 2016) and CTC (Graves et al. 2006) sequence criteria are commonly used in speech and handwriting recognition. See e.g. Hannun (2017) for background on the mechanics and motivation CTC. To demonstrate the utility of our framework, we show how to construct these criteria from operations simpler WFSTs following the formulation in equation [
The graphs A and Z used by the ASG loss function can be constructed from operations on simpler graphs. The ASG criterion assumes that emitting new token requires consuming the token least once, as in the graph, Ta of figure 2a The full token graph is the closure of the union of the individual token graphs. Assuming alphabet of (a, b, c} gives T = (Ta To + Te) Composing T with the label graph ) (fig. (2b) of "ab" results in the alignment graph (fig. [c).. The alignment graph specifies the allowed correspondences between arbitrary length paths and the desired label. Intersecting the alignment graph with the emissions graph εx (fig. [2d results in the constrained graph A (fig. 2ep. The are weights of &x depend X and can be the output of deep neural network. Here Z is simply the emissions graph. We may add bigram transitions by including bigram transition graph. B, as in figure 4a In summary, the graph operations are:
AASo E (Bo ((T1 + .... .......... +T)) ))) and ZASG E
The primary differences between ASG and CTC are the use of bigram transitions in the former and the inclusion of blank token in the latter. The blank token, <b>,, is represented by the graph in figure Ba Constructing CTC amounts including the blank token graph when constructing the full token graph T. The intersection T y then results in the CTC alignment graph (fig, (3b. Note, this version of CTC does not force transitions on <b> between repeats tokens. This requires remembering the previous state and hence is more involved (see Appendix A. for details).
benefit of constructing sequence-level criteria by composing operations on simpler graphs the access to large design space of loss functions with which we can encode useful priors. For exam- ple we could construct a "spike" CTC, a "duration- limitedd CTC, or an "equally spaced" CTC by substituting the appropriate token graphs into equation? (see Appendix A.2 for details).
4.1 TRANSITIONS
The ASG criterion was constructed with a bigram transition graph B. We can use B to add transitions to CTC with the same operations in equation 2 but with the addition of the blank token.
5

---

Under review as a conference paper at ICLR 2021
E:DO
th:h/0
0
(a)
he/O
USUBOES
th/0
e-i
3
the/0
(b)
Figure 5: An individual sub- word-to- to-grapheme transducer (a) for the token "th" used to con- struct lexicon L which used make the de- composition graph (b) for the label "the".
Figure 6: The convolutional transducer with a receptive field size of 3 and a stride of 2. Each output is the forward score of the composition of a kernel graph with a receptive field graph.
Dense n-gram graphs require O(C"-1) states and ((C") ares for C' tokens, computationally in- tractable n and C' grow. The dense graph also suffers from sample efficiency problems most transitions will not be observed the training set. We can alleviate these issues with pruning and back-off (Katz 1987) which can be encoded strates back-off for a trigram model. The trigram (a, b, a) exists so no back-off is needed. Neither the trigram (a, b, c) nor the bigram (b, c) exist, the model backs off to the O-gram state (c) and then transitions to the unigram state (c).
WFST (Mohri al.) 2008). Figure (4b) demon-
4.2 MARGINALIZED WORD PIECE DECOMPOSITIONS
Using word pieces has several benefits over grapheme outputs without the sample and computational efficiency issues, and lexical constraints of outputting words directly. However, the set of pieces and decomposition for word are learned in an unsupervised and task independent manner (Kudo) 2018 (Sennrich al. 2016). These are then fixed and used to train the task specific model. The word piece dccomposition for a given phrase is not important, serving only as a stepping stone to more accurate models. This assumption can be made explicit by marginalizing over the set of decompositions for a target label while training the task specific model. This allows the model to select the decomposition(s) which are most salient the task hand.
Implementing marginalization over word piece decompositions usually requires non non-trivial changes carefully optimized implementations of existing sequence criterion. In the differentiable WFST framework this can be implemented in a plug-and-play fashion by incorporating a single lexicon graph. The lexicon transducer which maps sequences of sub-word tokens to graphemes, is the closure of the union of the individual sub-word-to-grae to-rapht-gra graphs. A composition with the label graph, L y, gives the decomposition graph for the label y. Figure Showws an example for the label "the". The decomposition graph can be used in place of the label graph to construct any down stream sequence criterion. For example, the constrained graph of equation becomes:
A = & (B ((Ti + ... Tc)* (())))
where L (C1+ +... Lc)* and C' is the number of word piece tokens.
4.3 CONVOLUTIONAL. WFSTS
Thus far we have only discussed applications of WFSTs to combine the output of other models. Figure 6 demonstrates convolutional WFST layer which function an arbitrary layer in tensor-based architecture. Like a standard convolution, the WFST convolution is specified by a set of kernels, receptive field size and stride Each kernel, KG, is WFST. Let the hidden units in receptive field at position be given by H E _ddkk, The receptive field graph, R is a linear graph with k nodes and edges between consecutive nodes. The activations H yield the edge weights in the receptive field graph. The output of the i-th kernel applied to position t is logadd s(p),
H
(4)
PEK,oRH,aat

---

Under review as a conference paper at ICLR 2021
Table 1: comparison of dense transition graphs from O (no transitions) up to 2 (bi-grams). We report CER on the IAM validation set using letter tokens.
Table 2: comparison of bi-gram transition graphs with back-off and varying levels of pruning for let- ters and 1, 000 word pieces. We report CER on the IAM validation set and epoch time in seconds.
No blank
Forced blank
Optional blank
Letters
Word Pieces
Te n-gram
Pruning
CER
Time (s)
CER
Time (s)
0
18.2
8.9
6.4
None
6.4
544
N/A
17,939
1
17.7
8.5
6.3
0
6.8
249
22.2
683
2
9.4
6.7
6.4
10
6.5
202
19.8
204
the forward score of the receptive field graph composed with the kernel graph.
The structure and labels of the kernel WFSTs are problem specific. For example, the kernel trans- ducers can be structured to impose a desired correspondence. We construct kernels which transduce lower-level tokens such letters to higher level tokens like word pieces. Without any other con- straints, the interpretation of the input as letter scores and the output word piece scores is implicit in the structure of the graphs, and can be learned by the model up any indistinguishable permuta- tion. The kernel graphs themselves have edge weights which, since equation 4 differentiable, can be initialized randomly and learned along with the other parameters of the model.
5 EXPERIMENTS
We study several of the algorithms from section with experiments in offline handwriting recog- nition (HWR) and automatic speech recognition (ASR). For both applications, use a varia- tion of the time-depth separable (TDS) convolutional architecture (Hannun et al., 2019). more detailed description of the network architectures, optimization procedures and data processing is in Appendix B We report character error rate (CER) without the use of an external language model or lexical constraint. Code to reproduce
experiments is open-source and available at https: // /www.wa. anonymi zed. com All of the tensor based operations are on the GPU while the WFST operations are the CPU. The WFST operations executed in parallel over the examples in the batch.
Offline Handwriting Recognition To facilitate comparisons to prior academic studies, we test our approach on handwritten line recognition using the IAM database (Marti & Bunke] 2002). We use the standard training set and report results on the first validation set available with the data set distribution. The splits have changed from those used by prior work (Graves et al. 2008 Pham et al. 2014 Voigtlaender et al. 2016) which makes comparisons to such work less meaningful.
Automatic Speech Recognition Speech recognition experiments are performed the Lib- riSpeech (Panayotov et al. 2013) and Wall Street Journal (WSJ) (Paul & Baker 1992) corpora. For LibriSpeech, we train with the "train-clean-100 subset and report results on the clean validation set. For WSJ we train on the full corpus and report results on the "dev-93" validation set.
5.1 TRANSITIONS
Table I shows that including transitions can improve CER substantially, particularly when no blank token is used. We speculate that bigram transitions help in this case primarily because of the duration model they provide. As previously observed (Graves et al. 2006), with blank token, the emissions of non-blam blank outputs spike at a single frame, and no duration model is needed. In Table 2 we see that pruning with back-off results in discernible loss in accuracy while yielding substantial run-time run-time improvements. With 1000 word pieces, the epoch time using a graph with pruned bigrams is nearly orders of magnitude faster than that of the dense graph.
dense transition model

---

Under review as a conference paper at ICLR 2021
13
30
30
12
7.5
26
25
CER
16
15
200
500
1,000
1,500
200
500
1,000
1,500
200
500
1,000
1,500
16
24
Tokens
Tokens
Tooens
X X-suhsample
(a) WSJ
(b) LibriSpeech
(c) IAM
(d) IAM
Figure 7: Validation CER with (dashed) and without (solid) marginalization as a function of (a-c) the number of word pieces and (d) the overall sub-sample factor using 1000 word pieces.
know
Know
knows
Know
kuows
opporitin
pasn hinn
Arxe
hoxes
krow
krows
(a) Using word pieces (top) k, n, O, w and (bottom) know.
(b) Using word pieces (top) P. o, 8, i, t, ien and (bottom) position.
Figure 8: The Viterbi word piece decomposition with 1000 tokens for (a) "'now"" and (b) "posi- tion". The decompositions are computed on the training set images prior to cropping the words.
5.2 MARGINALIZED WORD PIECE DECOMPOSITIONS
We experiment with marginalization use the SentencePiece toolkit (Kudo & Richardson] 2018) to compute the token set from the training text. For all datasets, larger token set sizes result in worse CER, though the effect is mild on LibriSpeech and more pronounced on IAM. Appendix figure I suggests this is primarily due to the different dataset sizes. Figures 7 /b and 7c demonstrate that word piece marginalization recovers sets. We examine the Viterbi decomposition on the LibriSpeech training set. Appendix fshle that some cases the most frequently selected decomposition for word is more phonologically plausible than the SentencePiece decomposition.
word piece decompositions in both ASR and HWR. We
some of the accuracy lost when using larger token
For IAM, we find that the model favors decompositions using lower-level output tokens but does still rely on higher-level word pieces in many cases. We also explore the interaction between sub- sampling in the network and marginalization. One benefit of marginalization is the ability to dynam- ically choose the decomposition suitable to given frame rate as demonstrated by 7d We examine the Viterbi decomposition for a few examples from the training set in figure g We see that a sin- gle model dynamically switches between different decompositions depending the input. If the handwriting is tightly spaced, for example, a higher-level token is preferred.
5.3 CONVOLUTIONAL WESTS
We experiment with the convolutional WFST layer on the IAM data set. The kernels in the WFST layer transduce letters to 200 word pieces. We use CTC-style graph structure for the kernels and hence the input to the WFST has an additional dimension for the <b>> token. Figure | gives and example of kernel and receptive field WFST. We place the WFST convolution in between the third and fourth TDS groups. The model is trained to predict 1000 word pieces at the output layer. We compare the WFST convolution with traditional convolution in the same position. Table strates that the WFST convolution outperforms the traditional convolution. The WFST convolution is also less expensive the number of parameters and the number of operations needed scale with the lengths of the word pieces in letters rather than the number of input channels.
CONCLUSION
We have shown that combining automatic differentiation with WFSTs is not only possible, but a promising route new learning algorithms and architectures. The design space of structured loss
8

---

Under review as a conference paper at ICLR 2021
Table 3: A comparison of the convolutional WFST layer to a traditional convolution. We report the CER on the IAM validation set and compare the two layers in number of param- eters and number of operations. Both con- volutional layers have a kernel width l: 5, stride of 4, G 80 input channels, and Co 200 output channels.
<to-20
haz0
doai
<l
Libo
(a) Kernel WFST
2l-
20033
dool
Convolution
CER
Params
Ops
(b) Receptive field WFST (A= 4)
WFST
19.5
2,048
O(kwcs) Okkacao)
Traditional
20.7
79,000
Figure 9: Graphs for the convolutional WFST.
functions that may be encoded and efficiently implemented through the use of differentiable WFSTs is vast. We have only begun to explore it.
We many other related and exciting paths for future work in automatic differentiation with WF- STs. First, we aim to continue to bridge the gap between static computations with WFSTs while performing inference and dynamic computations with WFSTs during model training. This will re- quire further optimizations and potentially approximations when integrating higher level lexical and language modeling constraints. Second, the of WFSTs substitute for rensor-based layers in a deep architecture is intriguing. This may be more effective than traditional layers in impos- ing prior knowledge on the relationship between higher-level and lower-level representations or in discovering useful representations from data.
REFERENCES
Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri. Openfst: A general and efficient weighted finite-state transducer library. In International Conference on Implementation and Application of Automata, pp. 11-23. Springer, 2007.
Dario Amodei, Sundaram Ananthanarayanan. Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, al. Deep speech 2: End-to- end speech recognition in english and mandarin. In International conference on machine learning, pp. 173-182, 2016.
Léon Bottou. Une Approche théorique de l'Apprentissage Connexionniste: Applications la Re- connaissance de la Parole. PhD thesis, Université de Paris XI, 1991.
Léon Bottou, Yoshua Bengio, and Yann LeCun. Document analysis with transducers, July 1996.
Léon Bottou, Yann Le Cun, and Yoshua Bengio. Global training of document processing systems using graph transformer networks. In Proceedings of Computer Vision and Pattern Recogni- tion (CVPR), pp.
Puerto-Rico, 1997. IEFE. URI. htth:h/pp/lo... http://lo...otoo.ooo bottob..troo..........o
papers/bottou
Thomas M Breuel. The OCRopus open source OCR system. In Document recognition and retrieval XV, volume 6815, pp. 68150F. International Society for Optics and Photonics, 2008.
William Chan, Yu Zhang, Quoc Le, and Navdeep Jaitly. Latent sequence decompositions. In Inter- national Conference on Learning Representations (ICLR), 2017.
Chung-Cheng Chiu, Tara N Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Zhifeng Chen, Anjuli Kannan, Ron Weiss, Kanishka Rao, Ekaterina Gonina, et al. State-of-the-art speech recognition with sequence-to-ssquueee models. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4774-4778. IEEE, 2018.
Ronan Collobert, Koray Kavukcuoglu, and Clément Farabet. Torch7: A matlab-like environment for machine learning. In Bigleamn, NIPS workshop, number CONF, 2011.

---

Under review as a conference paper at ICLR 2021
Ronan Collobert, Christian Puhrsch, and Gabriel Synnaeve. Wav2letter: end-to-end convnet- based speech recognition system. arXiv preprint arXiv:1609.03193, 2016.
Ronan Collobert, Awni Hannun, and Gabriel Synnaeve. A fully differentiable beam search decoder. In ICML, 2019.
Jason Eisner. Parameter estimation for probabilistic finite-state transducers. In Proceedings of the 40th Anmual Meeting of the Association for Computational Linguistics, pp. 1-8, 2002.
Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber. Connectionist tem- poral classification: labelling unsegmented sequence data with recurrent neural networks. In Pro- ceedings of the 23rd international conference on Machine learning, pp. 369-376. ACM, 2006.
Alex Graves, Mareus Liwicki, Santiago Fernández, Roman Bertolami, Horst Bunke, and Jürgen Schmidhuber. A novel connectionist system for unconstrained handwriting recognition. IEEE transactions on pattern analysis and machine intelligence, 31 31(5):855-88) 868, 2008.
Awni Hannun. Sequence modeling with ctc. Distill, 2017. https//diitill..pb//01//tt
doi:
Awni Hannun, Ann Lee, Qiantong Xu, and Ronan Collobert. Sequence-to-sequene speech recog- nition with time- separable convolutions. Proc. Interspeech 2019, pp. 3785-3789, 2019.
Phillip Isola, Jun-Yan Yan Zhu, Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1134, 2017.
Dan Jurafsky. Speech language processing. Pearson Education India, 2000.
Slava Katz. Estimation of probabilities from sparse data for the language model component of speech recognizer. IEEE transactions acoustics, speech, and signal processing, 35(3):400- 401, 1987.
Brian Kingsbury. Lattice-based optimization of sequence classification criteria for neural-network acoustic modeling. In 2009 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 3761-3764 IEEE, 2009.
Brian Kingsbury, Tara N Sainath, and Hagen Soltau. Scalable minimum bayes risk training of deep neural network acoustic models using distributed hessian-free free optimization. In Thirteenth Annual Conference of the International Speech Communication Association, 2012.
Kevin Knight and Jonathan May. Applications of weighted automata in natural language processing. In Handbook of Weighted Automata, pp. 571-596. Springer, 2009.
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the 56th Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pp. 66-75, 2018.
Taku Kudo and John Richardson. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing: System Demonstrations, pp. 66-71, 2018.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Proba- bilistic models for segmenting and labeling sequence data. 2001.
Hairong Liu, Zhenyao Zhu, Xiangang Li, and Sanjeev Satheesh. Gram-cte: automatic unit selee- tion and target decomposition for sequence labelling. In Proceedings the 34th International Conference on Machine Learning- Volume 70, pp. 2188-2197, 29882219,,017, 2017.
Hu Liu. Sheng Jin, and Changshui Zhang. Connectionist temporal classification with maximum entropy regularization. In Advances in Neural Information Processing Systems, pp. 831-841, 2018.
U-V Marti and Horst Bunke. The iam databaae: an english sentence database for offline handwriting recognition. International Journal Document Analysis and Recognition, 5(1):39 46, 2002.
10

---

Under review as a conference paper at ICLR 2021
Mchryar Mohri. Finite-state transducers in language and speech processing, Computational linguis- tics, 23(2):269-311, 1997.
Mehryar Mohri. Weighted automata algorithms. Handbook of weighted automata, pp- 213-254. Springer, 2009.
Mehryar Mohri, Fernando Pereira, and Michael Riley. The design principles of a weighted finite- state transducer library. Theoretical Computer Science. 231(1): 2000.
Mehryar Mohri, Fernando Pereira, and Michael Riley. Weighted finite-state transducers in speech recognition. Computer Speech & Language, 16(1):69-88)) 2002.
Mehryar Mohri, Fernando Pereira, and Michael Riley. Speech recognition with weighted finite-state transducers. In Springer Handbook of Speech Processing, pp. 559-584. Springer, 2008
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. LibriSpeech: an ASR corpus based on public domain audio books. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2015.
Daniel S Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D Cubuk, and Quoc V Le. Specaugment: A simple data augmentation method for automatic speech recognition. Proc. Interspeech 2019, pp. 2613-2617, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, pp- 2019.
Douglas B Paul and Janet Baker. The design for the wall street journal-based esr corpus. In Speech and Natural Language: Proceedings of Workshop Held Harriman, New York, February 23- 26, 1992, 1992.
Fernando Pereira, Michael Riley, and Richard Sproat. Weighted rational transductions and their ap- plication to human language processing. In HUMAN LANGUAGE TECHNOLOGY: Proceedings of a Workshop held at Plainsboro, New Jersey, March 8-11, 1994, 1994.
Vu Pham, Théodore Bluche, Christopher Kermorvant, and Jérôme Louradour. Dropout improves recurrent neural networks for handwriting recognition. In 2014 14th international conference on frontiers in handwriting recognition, pp. 285-290. IEEE, 2014.
Daniel Povey, Arna Ghoshal, Gilles Boulianne, Lukas Burget, Ondrej Glembek, Nagendra Goel, Mirko Hannemann, Petr Motlicek, Yanmin Qian, Petr Schwarz, et al. The kaldi speech recognition toolkit. In IEEE 201 workshop on automatic speech recognition and understanding, number CONF. IEEE Signal Processing Society, 2011.
Daniel Povey, Vijayaditya Peddinti, Daniel Galvez, Pegah Ghahremani, Vimal Manohar, Xingyu Na, Yiming Wang. and Sanjeev Khudanpur. Purely sequence-traiee trained neural networks for asr based on lattice-free mmi. 2016.
Vineel Pratap, Awni Hannun, Qiantong Xu, Jeff Cai, Jacob Kahn, Gabriel Synnaeve, Vitaliy Liptchinsky, and Ronan Collobert. Wav2letter++:: fast open-source speech recognition sys- tem. In ICASSP 2019-2019 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp.
IEEE, 2019.
Lawrence Rabiner. tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-28 1989.
Mare' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. Sequence level train- ing with recurrent neural networks. arXiv preprint a51 1.0632, 2015.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics ( (olume 1: Long Papers). pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v L/P16- 1162. URL https: www. aclweb. lorg/antho laaoooooyyy/pp ogy/p16-111

---

The blank token in CTC (<b>) also serves to disambiguate consecutive repeat tokens in the output from single token corresponding framework requires keeping track of the previously generated token and only allowing transitions on Under review as a conference paper at ICLR 2021
a:a
<hoop/0
<townii
2
choverll
(a) Spike CTC.
(h) Duration-limited CTC.
(c) Equally spaced CTC.
Figure 10: A few individual token graphs used to construct variants of, for example, CTC. The individual token graphs are combined to create the overall token graph T (Ti +...+... Tc)".
Hang Su, Gang Li, Dong Yu, and Frank Seide. Error back propagation for sequence training of context-dependent deep networks for conversational speech transcription. In 2013 IEEE Interna- tional Conference on Acousties, Speech and Signal Processing, pp. 6664-6668 IEEE, 2013.
Seiya Tokui, Kenta Oono, and Shohei Hido. Chainer: a next-generation open source framework for
deep learning. 2015.
Karel Vesely, Arnb Ghoshal, Lukás Burget, and Daniel Povey. Sequence-dissrimmnattv training of deep neural networks. 2013.
Paul Voigtlaender, Patrick Doetsch, and Hermann Ney. Handwriting recognition with large mul- tidimensional long short-term memory recurrent neural networks. In 2016 15th International Conference on Frontiers in Handwriting Recognition (ICFHR), pp. 228-233. IEEE, 2016.
A ALGORITHMS
A.1 REPEAT TOKENS IN CTC
input frames. Enforcing this construction in the WFST
new token or on <b>, Let Ti...., . To be the individual token graphs, including the blank token graph as in figure 3al The full token graph to disallow repeat consecutive transitions is given by
Σ
Σ TET j=ij
(5)
In practice, constructing the graph with equation will result in more states and arcs than are needed. Instead, we construct the graph directly. However, we note that these operations may be used along with removal and state minimization to keep the resulting token graph T small.
A.2 PRIORS WITH CTC
The individual token graphs in CTC do not assume much about the duration or spacing of the tokens at the input level. The graph in figure 2a states only that non-blank tokens must align to at least one frame. The graph in figure 3a states that the <b> token optional.
The differentiable WFST framework simplifies the construction of variations of these token-level graphs with potentially useful alternative assumptions. For example, we can construct a "spike" CTC which only allows single repetition of a non-blank label by using the graph in figure 10a Similarly, a "duration-limited" CTC could use a token graph as in figure 10b] In this case, the duration of token is limited to be between one and two input frames. We could specify a range of allowed distances between non-blank tokens using the blank token graph in figure 10c These may all be mixed and matched a per-token basis.
B EXPERIMENTAL SETUP
In both handwriting recognition and speech recognition experiments, variation of the time- depth separable (TDS) convolutional architecture (Hannun et al., 2019). The code and settings needed reproduce experiments available at athttps:/ www.. anonymi zed. com
12

---

Under review as a conference paper at ICLR 2021
Table 4: A comparison of the most frequent decomposition to the SentencePiece decomposition for a given word. The words were selected by first computing the Viterbi decomposition for each example in the LibriSpeech training set. We then chose words for which the most frequently selected decomposition was different from the SentencePiece decomposition. The counts are the occurrences of each decomposition the Viterbi paths on the training set. In some cases the most frequent decomposition appears to be more phonologically plausible than the SentencePiece decomposition.
Most common Decomposition
SentencePiece
Word
Count
Decomposition
Count
able
a, ble
121
able
88
wind
w, in, d
90
wi, n,
72
single _s, ng, le
65
_ s, ing, le
40
move _o, ve
54
_mov,
47
ring ri, ng
48
_ ing
23
B. HANDWRITING RECOGNITION
For experiments in HWR, we propose a variant of the TDS model which preserves the 2D structure in the image. The 2D TDS block first applies a 3D convolution with kernel size x k₁ x kw on a 4- dimensional input of size cx d h x where and are the separated channel and depth dimensions and w and are the height and width of the image respectively. Following the 3D convolution, is a 1 x 1 convolution with d input and output channels. We apply dropout, the ReLU non-linen non-linearity and residual connections as the original TDS architecture. In place of layer normalization, we use 2D instance normalization (Isola al. 2017) with learned affine transformation.
Unless otherwise noted, we use 4 groups of three TDS blocks each. In hetween each TDS block apply standard 2D convolution and optionally sub-sample the image in the height and width dimensions. For letter-based experiments we sub-sample the height by 2 and the width by 2 only after the first two groups. For word piece experiments we sub-sample both the height and width by a factor of 2 after every group for an overall sub-sampling factor of 16x in each dimension. We use a uniform kernel size of and 64 in between each TDS group.
We start the number of channels (c x d) 8 and increase 16, 32
For optimization we use a simple stochastic gradient descent with an initial learning rate of 10-1 which is reduced every 100 epochs by factor of 2. All models are trained for 400 epochs and we save the model which achieves the best results on the validation set during training. We use a mini-batch size of 32 with distributed data parallel training.
Bounding boxes for the line-level segmentation for each page are provided along with the ground truth texts. We perform no other data pre-processing other than simple normalization, remov- ing the global pixel mean and standard deviation from each image. We use three forms of data augmentation- random resize and crop, random rotation, and random color change.
B.2 SPEECH RECOGNITION
For experiments in speech recognition, we use a ID TDS architecture with 3 groups each containing TDS blocks. In between each group we sub-sample the input in the time-dimension by a factor of 2 for an overall sub-sampling factor of 8. The TDS blocks all use kernel width of 5. The first group has channels, and we double the number of channels in between each group.
For optimization we use stochastic gradient descent. Initial learning rates are tuned for each model type in the range 10-2 to 1. The learning rate is reduced every 100 epochs by a factor of 2. All models are trained for 400 epochs and we save the model which achieves the best results on the validation set during training. We use a mini-batch size of 16 with distributed data parallel training.
For features, we use 80 log-mel-scale filter banks on windows of 20 milliseconds every 10 mil- liseconds. We normalize individual examples by removing the mean and dividing by the standard deviation. We apply SpecAugment for regularization following the "LD" policy but without time- warping (Park et al. 2019).
13

---

Under review as a conference paper at ICLR 2021
644
DWSJ
LibriSppeec
DIAM
600
Number of word pieces
521
400
382
337
247
200
178
154
85
57
31
36
C. 50
50 < S 100
100 < S 200
200 < S 500
500 <
Figure 11: The number of word pieces with occurrences e in the given range. For each dataset we use 1,000 word piece tokens and count the number occurrences the training text using the decomposition for each word provided by SentencePiece. The WSJ training text contains 639k words, the LibriSpeech training text has 990K words and the IAM training text has only 54K words.
14


Reviews:
[{"review_id": "YoJJ5jbi48W", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a paper describing a software package for common calculations on WFSTs (like forward score or best path score), in a way that they are differentiable w.r.t. the arc weights.\n\nIt also contains several examples of WFSTs and WFSAs specifically for speech recognition or handwriting recognition, like for the CTC or ASG topology.\n\nThe scientific novelty in the paper is very limited. The scientific new contribution is a convolutional WFST layer.\n\nRandom notes and questions:\n\n- The K2 project (https://github.com/k2-fsa/k2) is a very popular attempt in this space which seems to have very similar goals. Specifically it has efficient implementations to calculate the best path score or forward score and is differentiable w.r.t. the arc weights. What are the differences?\n- The PyChain project (https://arxiv.org/abs/2005.09824, https://github.com/YiwenShaoStephen/pychain) also seems very related. The FSA structure is created by Kaldi, exported as OpenFST, and then imported as via OpenFST bindings in PyChain. PyChain then has an efficient GPU-based implementation of the forward-backward algorithm which gets any such FSA. The arc weights are dynamically filled in via posteriors from a NN, and the fwd-bwd score can then be used as the gradient. This is slightly less generic, as the arc weights are assumed to be coming from posteriors. But despite that, what are the differences?\n- The RETURNN project (https://github.com/rwth-i6/returnn) also has a similar generic implementation, which gets in any generic FSA, and then calculates the Viterbi path/score or forward-backward (Baum Welch algorithm), and the arc weights are given by NN posteriors. This was presented in the paper [\"CTC in the Context of Generalized Full-Sum HMM Training\"](https://www-i6.informatik.rwth-aachen.de/publications/download/1035/ZeyerAlbertBeckEugenSchl%FCterRalfNeyHermann--CTCintheContextofGeneralizedFull-SumHMMTraining--2017.pdf). This is a fast batched GPU implementation.\n- It is stated that Kaldi mostly uses WFSTs for inference. This is wrong. Esp in the case of LF-MMI training, it uses WFSTs in training.\n- Details about how the fwd-bwd computation (or other computations) are done are missing. E.g. is this implemented in CUDA and runs on GPU? How exactly? At least some details about this should be given.\n- The WFST arcs (from,to edges), arc weights, list of final states is all in GPU memory? Does it (including the algos like fwd-bwd) support batching, i.e. having multiple WFSTs in one batch? This is specifically important for efficient training.\n- How fast is it? E.g compared to the existing implementation above, or other existing implementations for CTC.\n- Is the WFST always represented statically, or does it support dynamic composition, which would be done on-the-fly when traversing the graph (like WFST decoders in speech recognition usually do it)? If it is always static, it might become very big, e.g. when combined with a 5gram LM or so, and then might not fit into memory. How is this solved?\n- In e.g. TensorFlow, you can easily explicitly calculate the forward scores in a while loop by explicitly iterating through allowed transitions. You don't need to formulate it as a WFST. This would also be fully differentiable, also supports full GPU-based calculation, and is very straight-forward. What is the advantage of the WFST formulation? The explicit calculation can be even more flexible, like only calculate arc weights which are really needed (e.g. in beam search).\n- The motivation for the convolutional transducer is not exactly clear.\n- The exact calculation/definition of the convolutional transducer is not clear. What exactly is the structure of the WFST, and how are the arc weights defined?\n- It is stated that IAM CER can not be compared to the literature because a different validation set is used. Why? Why not use the right validation set such that it can be compared? The CER also looks quite high, but maybe the validation set is much harder? Or the model is very weak compared to current state-of-the-art?\n- The IAM CER in Table 3 is esp very high, much higher than in Table 1 or 2. Why is that?\n- Speech recognition experiments are performed, but no word-error-rate (WER) is reported at all, which is the standard measure for speech recognition. Why? It looks like it deliberately is not supposed to be compared to other results from the literature?\n\n\nPros:\n\n- The software package and capabilities sound very promising.\n\nCons:\n\n- It misses several very related works (as outlined above).\n- Some important details about the implementation are missing (as outlined above).\n- The motivation (and exact definition) of the convolutional WFST are unclear.\n- The experimental section is very short, lacks in depth, and misses comparisons to the literature.\n\nSummary:\n\nOverall, the software looks interesting. However, the scientific novelty is limited, and also the experimental section has several problems. Maybe ICLR is not the right conference for this paper? Or otherwise the scientific contributions and experimental section should be improved. E.g. more tasks and experiments should be done where it is useful to have such a generic differentiable WFST software, which is currently hard to implement otherwise. And the experiments should have fair comparisons to the literature. In general, there are also several problems in the related work section.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KiBIiGinhL", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Overall comments\n\nThis is a well-written paper describing the incorporation of WFSTs into an \"auto-diff\" framework for Deep Learning. The central point is that by providing partial derivatives, in addition to the standard forward scores, to the major WFST operations, one can embed those WFST operations into a gradient-based deep learning framework as just another differentiable module. Given the continued demonstrated utility of WFSTs in the speech and natural language community, many researchers will welcome the motivation. The paper details how some specific WFST models can help implement models such as CTC or ASG, presents a less-clear application to convolutional models, and presents results evaluating the use of differentiable WFSTs for tasks in ASR and handwriting recognition.\n\nThe paper is a good read, but the central contribution isn't really detailed. A good overview of WFSTs and their utility is given, but that is somewhat orthogonal to the central contribution of \"we made an auto-diff version of these tools\". Section 3 gives a more or less standard outline of the WFST framework, but only in Section 3.2 is auto-differentiation discussed, and it's a very bare-bones description, along the lines of, \"we did it.\" The use of a gradient graph representing gradients/jacobians as WFST weights makes sense, but the specifics of implementing this for different WFST operations aren't really discussed. The reader doesn't have a sense of the implementation issues, or of any compute/memory issues involved. There is no sense of how efficiently the operations will run on GPUs. Since e.g. OpenFST operations such as ShortestDistance() and Divide() can be used to compute arc posteriors for ASR lattices in the context of MMI or sMBR for ASR sequence training, and since partial derivatives of the MMI/sMBR sequence level loss functions correspond to accumulated lattice arc posteriors, the reader who is knowledgeable about work in that area may wonder if the work detailed here also used WFST operations to define the derivatives themselves, or if a more direct/efficient implementation was used.\n\nThough the application to CTC and ASG is very clear, the convolutional WFST is much less clear to me. If a kernel is a WFST, what is the sequence model? I.e. in Eq (4) , what are the sequences p? I think sections 4.3 and 5.3 should expand on the convolutional models used, and detail both the standard convolutional model and the WFST model used. I think the paper assumes the reader is familiar with the TDS / convnet seq2seq models previously proposed, but I for one am not.\n\nMore specific comments:\n\n### References/background:\n\nThis well-known work by Jason Eisner is in my mind closely related to the ideas in this paper: \n\nhttps://www.aclweb.org/anthology/P02-1001.pdf.\n\n\"For example, Kaldi, a commonly used\ntoolkit for automatic speech recognition, uses WFSTs extensively, but in most cases for inference or\nto estimate the parameters of shallow models (Povey et al., 2011). In some cases, WFSTs are used\nstatically to incorporate fixed lattices in discriminative sequence criteria (Vesely et al., 2013). \"\n\nAll state-of-the-art hybrid ASR systems use some form of sequence training based on ASR lattices and criteria such as MMI or sMBR. Just a few references (in addition to the Vesely reference):\n\nhttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4960445\nhttps://www.isca-speech.org/archive/archive_papers/interspeech_2012/i12_0010.pdf\nhttps://ieeexplore.ieee.org/document/6638951\nhttps://www.isca-speech.org/archive/archive_papers/interspeech_2014/i14_1224.pdf\n\n\"Implementations of sequence criteria in end-to-end style training are typically hand-crafted with\ncareful consideration for speed (Amodei et al., 2016; Collobert et al., 2019; Povey et al., 2016).\"\n\nThough that is true for new models such as ASG and Lattice-Free MMI, for LAS and RNN-T, the models are locally normalized and fully conditioned on past history, so the baseline can be thought of as already sequence-trained (there is no need for a normalizing global score), which simplifies things. But by the same token, those models being fully conditioned on the past symbol history don't in fact allow the use of lattices (without limited history approximations) for criteria such as WMBR, so typical approaches use N-best lists. I'll leave it up to the authors how, or if, they want to acknowledge this point in their draft, it's really just a comment -- just to say that for some in the \"end-to-end\" world, WFSTs are less relevant than to others, depending on the nature of their models. Some references along those lines:\n\nhttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8461809 (MBR of LAS models)\nhttps://arxiv.org/pdf/1911.12487.pdf (MBR of RNN-T models)\n\n### Other comments\n\n\"Graphs\": this is never actually defined afaict. Is it synonymous to \"WFST\"?\n\n\"Forward and Viterbi Score The forward score of T is logadd(p,r)∈A s(p, r). Similarly, the Viterbi\nscore of T is max(p,r)∈T s(p, r).\"\n\nWhy is the Forward score defined over an Acceptor, while the Viterbi score is defined over a Transducer?\n\nSection (4) Eq. (1): just an FYI, a lot of readers in the ASR community would recognize A and Z as \"numerator\" and \"denominator\" for lattice-based sequence training, see e.g. https://www.isca-speech.org/archive/archive_papers/icslp_1996/i96_0018.pdf.\n\n\"The primary difference between ASG and CTC is the inclusion of the blank token graph\": isn't the primary difference (in addition to the one cited), the use in ASG of a normalizing score, while in CTC the outputs are all locally normalized? (There is no normalizing score in CTC , at least not in the same sense as there is in ASG).\n\nSection 5.3, \"TDS\" is mentioned with no reference and no explanation of what it is an abbreviation for, and no summary of what it is.\n\n\"The kernel transducers can be structured to impose a desired correspondence. For example, we\nconstruct kernels which map lower-level tokens such as letters to higher level tokens like word\npieces. Without any other constraints, the interpretation of the input as letter scores and the output\nas word piece scores is implicit in the structure of the graphs, and can be learned by the model up\nto any indistinguishable permutation\"\n\nThis relates to my points at the start -- this description is much too compact, I really have to strain to imagine the specifics of what the authors are talking about here. Also, what is the standard (non-convolutional) model here?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CDeGCVgEh_H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n \nThe authors introduce a  library for differential weighted finite-state transducers. WFST are commonly used in speech or handwriting recognition systems but are generally not trained jointly with the deep neural networks components such as ConvNN. This is not due to theoretical limitation of WFST but rather to a lack of available implementation and the need of important computational power to train them. The authors show that this new library can be used to encode the ASG criterion, by combining the emission graph (coming from a NN for example), the token graph (base recognition units) and the label graph (the sequence annotation) on one hand and the emission graph and a language model graph on the other hand. The authors show how word pieces decomposition can be learnt through marginalisation. Finally, convolution Wfst are rapidly presented. Preliminary experiments are reported on wSj data base for speech recognition and IAM database for handwriting recognition.\n\n\n##########################################################################\n\nReasons for score: \n \n \n I am very pleased to see an implementation of the GTN approach which has been proposed more than 20 years ago. WFST approaches have been shown to be more effective (and more elegant) than ad-hoc implementation for both speech and handwriting recognition. If efficient, this library will certainly have a major impact on future ASR and HTR systems. However, implementation details are not given or explained and experiments are still preliminary. Despite its importance and impact, this work seems to be in a too early stage to be accepted to ICLR this year.\n\n\n\n##########################################################################Pros: \n\nPros:\n\n* first implementation of a differentiable WFST library\n* experiments both on ASR and HTR with interesting results for learning WFST parameters\n* a new convolutional WFST is introduced\n\n\n##########################################################################\n\nCons: \n\n* we dont' know to what extent the operations on WFST needed to build a real ASR/HTR application  are available (determinisation, minimization,  weight pushing, etc)\n* ASR/HTR systems are not compared to state of the art, to measure the remaining progress to reach SOTA.\n* As said by the authors, include WFST in a differentiable stack of layers needs a lot of computation. Is it trackable for large scale systems ? Table 2 gives epoch times for 1000 word pieces (which is small) and for bigrams only. Is it on TPU or CPU ?\n* the section 4 on learning algorithms is not very generic as only an implementation of ASG is first presented then a comparison to CTC.\n* section 4.3 on conv. WFST is too short to be really understand the proposed model. Maybe this part should be dropped to leave more room to basic algorithms presentation.\n \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6fzq56cCKSJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents how weighted finite-state transducers (WFST) and a few common operations performed on them can be integrated in a differentiable model, and therefore contribute to the training of complete systems. The authors propose a few case studies, mainly in language applications, where the WFSTs are used to compute a sequence-level loss function, to keep ambiguity and let the model decide word-peices decomposition, or gracefully replace convolution layers. The code associated with the presented methods will be available.\n\nThe benefits brought by the availability of WFST-based differentiable operation in deep learning libraries are clear and very relevant. As the authors mention, it would unlock a wealth of possibilities in the design of loss functions and other operations in language-related applications (but not only) and allow to more easily create end-to-end systems. \n\nHowever, the idea in itself is not entirely novel. As mentioned in the related work section, this idea has been extensively explored in the past, and a good example of this are the graph transformer networks (GTNs). The corresponding paper(s) cover the same kind of operations described here if not more, and it is not clear how this paper brings more on that topic, other than putting them in the context of loss functions used today. The differentiability of the selected operations in the selected semiring is pretty straight-forward and already implemented in some frameworks for special cases. As rightfully mentioned by the authors, Kaldi implements sequence-discriminative loss functions, either lattice-based or lattice-free, based on WFSTs and on GPU. PyChain implements it too, and I believe Google mentioned at several occasions that their implementation of the CTC loss was based on WFSTs.\n\nThe novelty therefore does not lie so much in the differentiability of WFSTs nor in their integration into the training procedure as in the implementation of an efficient way to integrate them in a generic fashion for GPU training. The paper should focus more on that aspect, which would indeed be very interesting for the community, reviving the very interesting and not-so-much exploited GTN idea. \n\nRegarding the applications of the method to speech and handwriting recognition and word-piece selection, they are quite relevant for the scope of this paper. Although the level of details on CTC and ASG for example would be sufficient for application-specific conferences, I feel like a reminder of how and why these loss functions are computed would be nice for ICLR since not all readers may be familiar with these losses. \n\nRegarding the implementation, which to me is the main contribution of this paper, I would expect more details about runtime and efficiency compared to other implementation of CTC and ASG for example, which by the way would not be too hard to modify to include the proposed variations (even though it would be reimplementing them for each new case, when the proposed method would be generic, which is indeed a very nice thing to have!). It would also be interesting to see more the impact of the graph size and structure, understand more how the epsilon transitions are handled and the derivative computed.\n\nRegarding the experiments, a comparison with the state-of-the-art would be interesting. I understand that the page limit is tight and does not allow to present the models in details, but the reference to the paper presenting TDS in the main text at least might help the reader understand better section 5.3, which is difficult to follow when one is not familiar with that architecture.\n\nOverall, the paper is well-written, easy to read when one is familiar with the presented loss functions. The idea is attractive and the implementation would be very beneficial for the community. However, the novelty of the idea itself is very limited and the improvement over the GTN idea is not clearly stated. The contribution is in my opinion more related to an efficient implementation, but that part is not really described here and lacks an empirical study of its performance. Although I'd be happy to use the implementation provided by the authors and understand the huge benefit of its availability, I do not see this paper above acceptance threshold for ICLR.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a framework for automatic differentiation with weighted finite-state transducers (WFSTs), which would allow user-specified graphs in structured output prediction tasks and easy plug-and-play of graphs through the composition operation (demonstrated with variants of CTC). The authors demonstrated their framework on the OCR and ASR domains, which are important application scenarios. All reviewers agree the work is useful and can potentially be significant. However, the reviewers think the paper needs more discussions of similar/parallel work and the key differences from them, and clear description of the novelty in terms of either machine learning insights or algorithmic implementations.  We understand that this may be an implementation-heavy work, but the level of details provided in the current version does not convince the reviewers that the proposed approach is already efficient and can scale up. This could be shown by fair comparison with existing approaches (e.g., hard-coded error back-propagation implementation with a fixed graph) in runtime and accuracy. 
Decision: Reject