Star Temporal Classification: Sequence Modeling with Partially Labeled Data
Authors: Vineel Pratap
Awni Hannun
Gabriel Synnaeve
Ronan Collobert
Venue: NeurIPS 2022 Accept (2022)

Abstract: We develop an algorithm which can learn from partially labeled and unsegmented sequential data. Most sequential loss functions, such as Connectionist Temporal Classification (CTC), break down when many labels are missing. We address this problem with Star Temporal Classification (STC) which uses a special star token to allow alignments which include all possible tokens whenever a token could be missing. We express STC as the composition of weighted finite-state transducers (WFSTs) and use GTN (a framework for automatic differentiation with WFSTs) to compute gradients. We perform extensive experiments on automatic speech recognition. These experiments show that STC can close the performance gap with supervised baseline to about 1% WER when up to 70% of the labels are missing. We also perform experiments in handwriting recognition to show that our method easily applies to other temporal classification tasks.

Star Temporal Classification: Sequence Modeling with Partially Labeled Data
Vineel Pratap Meta AI
Awni Hannun" Zoom AI
Gabriel Synnaeve Meta Al
Ronan Collobert" Meta AI
Abstract
We develop algorithm which can learn from partially labeled and unsegmented sequential data. Most sequential loss functions, such as Connectionist Temporal Classification (CTC), break down when many labels are missing. We address this problem with Star Temporal Classification (STC) which uses special star token allow alignments which include all possible tokens whenever token could be missing. We express STC as the composition of weighted finite-state transducers (WFSTs) and GTN framework for automatic differentiation with WFSTs) to compute gradients. We perform extensive experiments on automatic speech recognition. These experiments show that STC can close the performance gap with supervised baseline to about 1% WER when to 70% of the labels are missing. We also perform experiments in handwriting recognition to show that our method easily applies to other sequence classification tasks.
Introduction
Applications of machine learning in settings with little or no labeled data are growing rapidly. Much prior work in temporal classification focuses on semi-supervised or self-supervised learning [6] 37). Instead, we focus on weakly supervised learning, in which the learner receives incomplete labels for the examples in the data set. Examples include multi-instance learning [ 44 and partial-lahel learning [18, 19 225 In our case, we assume that each example in the training set is partially labeled, as in Figure I neither the number of missing words nor their positions in the label sequence are known in advance.
Input:
-0.--000) 10:0000000
Original Label: seen from an airplane the island looks like big spider
Partial Label: from airplane a spider
Figure An example of speech with a complete and partial label.
Partial labeling problem could arise in many practical scenarios. In semi-supervised learning or transfer learning of sequence labeling tasks, we can only consider high confidence tokens the label sequence and discard of the tokens. These labels with incomplete tokens be treated as partial labels. When transcribing dataset, we can randomly label parts of the dataset and use them as partial labels. much lower cost than transcribing the full dataset. We can also consider semi-aute aemi-automatic ways to label dataset. Restoring damaged texts 2 3 where some of the writing is illegible could be considered as a partial labeling problem. We also often face partial alignment problem [5] in practice
*Currently at Apple. Correspondence to Vineel Pratap (rineellppraaap@metaa com).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where beginning and ending tokens are missing. This is a sub- of the more general version of partial labeling problem that we solve in this work.
To solve this weak supervision problem we develop the Star Temporal Classification (STC) loss function. The STC algorithm explicitly accounts for the possibility of missing labels in the output sequence at any position, through a special star token. For the example of Figure [ the STC label sequence is from airplane
spider (where can be anything but the following label token). We show how to simply implement STC in the weighted finite-state transducer (WFST) framework. Moreover, through the use of automatic differentiation with WFSTs, gradients of the loss function with respect to the inputs are computed automatically, allowing STC to be used with standard neural network training pipelines.
the
For practical applications, a naive implementation of STC using WFSTs is intractably slow. We propose several optimizations to improve the efficiency of the STC loss. The star token we use results in much smaller graphs since it combines many arcs into one. The star token also enables us to substantially reduce the amount of memory transfers between the GPU, on which the network is computed, and the CPU, on which the STC algorithm is evaluated. These optimizations result in only minor increase in model training time when using the STC loss over a CTC baseline.
The STC loss can be applied to most sequence transduction tasks including speech recognition, hand- writing recognition, machine translation, and action recognition from videos. Here we demonstrate the effectiveness of STC on both automatic speech recognition and offline handwriting recognition. In speech recognition, with up to 70% of the labels missing, STC is able to achieve similar (about 1 1% WER difference) performance as supervised baseline. Similarly in handwriting recognition STC achieve low character error rates with up to 50% of the labels missing. In both cases STC yields dramatic gains over a baseline system which does not explicitly handle missing labels.
To summarize, the main contributions of this work are:
We introduce STC, a novel temporal classification algorithm which explicitly handles an arbitrary number of missing labels with an indeterminate location.
We simplify the implementation of STC by using WFSTs and automatic differentiation.
We describe key optimizations for STC enabling it to be used with minimal increase in training time.
We show in practical speech and handwriting recognition tasks that STC yields low word and character error rates with up to 70% of the labels missing.
2 Related Work
Many generalizations and variations of CTC have been proposed. Graph-based temporal classification (GTC) (32) generalizes CTC to allow for an n-bestt list of possible labels. (40) also extends CTC for using with for multiple labels. (23) propose selfless-CTC which disallows self-loops for non-blank output tokens. Unlike these alternatives, STC allows for an arbitrary number of missing tokens anywhere in the label for given example. A recent work, concurrent with this work, proposes wild card version of CTC [5. However, in that work the wild cards, or missing tokens, can only be at the beginning or end of the label.
Extended Connectionist Temporal Classification (ECTC) 17 was developed for weakly supervised video action labeling. However, the weak supervision in this case refers to the lack of segmentation, which is the common paradigm for CTC. The extensions to CTC are intended to handle the much higher ratio of input video frames to output action labels. [I]] develop sequence level loss function which can learn from noisy labels. They extend the auto segmentation criterion [7] to include a noise model which explicitly handles up to one missing label between tokens in the output. Unlike that work, STC extends the more commonly used CTC loss and allows for any number of missing tokens.
The idea of expressing CTC as the composition of WFSTs is well known 27 23 41
However,
recently developed Wast-based frameworks which support automatic differentiation the development of variations of the CTC loss much simpler.
13
19 make
WFST' have been modified by to take into account of noisy transcripts [6
by composing
the WFST graphs of word sequences. However, in this work the WFST composition is between
2

---

significantly larger WFST graphs (label sequence and neural network model output sequence). Also, the composition is performed during the training of the neural network which makes it more challenging engineering problem.
3 Method
3.1 Prohlem Description
We consider the problem of temporal classification [20], which predicts output sequence y (y,..... Bul E A [xU where A is a fixed alphabet of possible output tokens, from an unsegmented input sequence x = [x],... "ri.....2" 2T| E d where each x; is dddiimensionl feature vector. We also assume that the length of the output U is less than or equal to that of the input, T. A partially labeled output sequence of length Ü, such that (Ú' S U), is formed by removing zero or more elements from the true output sequence y. Given training set D & fx input sequences goal is learn temporal models which can predict true output sequences y". We consider this weakly supervised temporal classification problem the learning algorithm only has access to subset of the true output labels during training.
.....,,. NN consisting of [ Ør- and partially labeled output sequences y [i...... Mps our
3.2 Connectionist Temporal Classification (CTC)
Connectionist Temporal Classification (CTC) 13] is a widely used loss function for training sequence models where the alignment of input sequence with the target labels is not known in advance.
........ .r] and target sequence y [y1..... 30 ] E A where A finite alphabet of possible output tokens and U S T. The CTC loss uses a special blank token, (b), to represents frames which do not correspond to output token. An alignment between the input x and output in CTC is represented by a sequence length T; π [T1, T2 TT) where Te A U [blank]. The CTC collapse function B maps alignment an output, B(x)) = y. The function B removes all but one of any consecutively repeated tokens and then removes blank tokens e.g., (a, blank, blank, b, b, blank, a) (a, b, b, a). Given the input x, each output is independent of all other outputs, hence the probability of an alignment P(T[x)) is:
Consider input sequence
2r]
P(T(x) = II P(T
There can be many possible alignments æ for given x and y pair. The CTC loss computes the negative log probability of given x by marginalizing over all possible alignments:
Lore = log P(y = - -log
Σ
P(T(x).
(2)
T (y)
The sum over all alignments can be computed efficiently with dynamic programming as described by 13.
The CTC loss can be computed purely with WFST operations described in Figure The composition of the emission graph (Figure 2a which has are weights weights corresponding to log P( and the label graph (Figure 2b is shown in Figure 2c Each path from start final state in Figure 2c is valid CTC alignment. The negation of the forward score of the composed graph gives the CTC loss. These operations are differentiable and gradients can easily be propagated backward from the loss to neural network to train the model.
Constructing the CTC loss from simpler WFST graphs also simplifies the implementation of variations of CTC. For example, the variations 32 only require changes to the label graph Vete- However, when efficiency is primary concern, custom GPU kemness can be faster than generic implementation with WFSTs.
A brief introduction WFSTs can be found in the Appendix

---

.112
N113
0:0
4:17
6.2.1
06
00507
06506
0..
(a) Emission Graph Ex
(b) Label Graph Viece
Do 244
A-188
2-12
1/122
B-12
B-23
06140.6
e44553655
d-1.1
el-2.5
(c) Alignment Graph Acte Vate Ex
(d) Loss Graph Lete - Actel
Figure 2: The sequence of steps involved in computing CTC loss using WFSTs. The are label "p/w" a shorthand notation for "prplu". (a) the emissions graph constructed from the log probabilities over the alphabet A = {a, b, e, d) and blank symbol (b). The CTC label graph corresponding to the target sequence (a, b, e) is shown in (b). (c), we compose label graph with emission graph to get all valid paths which collapse to the target sequence. Finally, in (d) sum the probabilities of all of the valid paths (in log-space) and negate the result to yield the CTC loss.
3.3 Star Temporal Classification (STC)
The label graph of CTC, Lete (Figure 2b constructed from partial labels does not allow for the true target as possibility. The STC algorithm addresses this problem by allowing for zero or more tokens from the alphabet between any two tokens in the partial label. Like CTC, an alignment between the input x and output y in STC is represented by a sequence of length T; π = [T1, T.,..., TT] where Te AA U {blank) and is a partial label of B' (Tr). Unlike CTC, the STC collapse function B' (x) only removes blank tokens. In other words, we do not allow self-loops on non blank tokens in the STC label graph. This enables to token insertion penalty discussed in Section 3.3.1
a/wi
low2
(*)
lvw2
(*)a//6
d/w4
d/w4
Collapsing (+) token
(b) Collapsing (+) token w6 = logxumexpp(22,333..
w5 = 1ogsumexpww1,w22,ww
Figure 3: Example showing the collapsing of tokens in alphabet A {a, b, c, d} to star token, (+)
To make the computation of the STC loss efficient, STC uses a special star token, (*), which represents every token in the alphabet. It can be used to collapse the arcs between any two nodes the WFST graph as shown in Figure 3a We also define (+) {y y E A: y * /} which the relative complement of in A. We use the token, (+)\(, in the label graph of STC, Lates to avoid counting the same alignment multiple times as dicsussed Section The STC label graph, Late- for the partial label (a, b, c) is shown in Figure The graph allows any alignment with zero more tokens in between any two tokens of the given partial label sequence.
We also manually add the (+) and (x) \ tokens to the emission graph Ex with weights corresponding their log-pro probabiiiiitss for each timestep given by:
p(()|xx,t)
Σ P(yxx,t) = 1-P(((
yEA
(3)
p(())txxxt
Σ p(ylx,t).

---

c/0
(-1/0)
lef
(100
(b)0
(MMO
000
.40
(M
IV
Figure 4: STC Label Graph, Vste for the output sequence (a, b, c). In regex terms, this corresponds to "[=a|= a ['b] + b ['c]* (+), (b) refer to star, blank tokens and (*) { is the relative complement of in (+). X(s 0) corresponds to token insertion penalty which has a regularization effect. The are transitions marked in red show the changes from selflessCTTC label graph.
3.3.1 Token Insertion Penalty, À
We noticed that model training with STC does not work if we train directly with the STC label graph, when 10% of the labels missing. This is because the new paths introduced in STC from CTC (marked in red in F would allow the model to produce a lot of possible output sequences for any given example and can confuse the model, especially during the early stages of training, To circumvent this problem, we use parameter called token insertion penalty, À to add a penalty when using lot of new tokens. We define STC loss in the following way
STC Loss - log(p" Ppath, + p Ppath, + ... pp Ppothy)
where Ppath, is the probability of alignment path p E (0, 1] and k; is the number of additional star tokens for path i. This down weight paths which include many additional tokens. The token insertion penalty is in log-space and is defined À log(p).
We use a exponential decay scheme to gradually reduce the penalty as the model starts training.
Pt = Pmaz + (po PmmPPaa)eaa (eatee))p((//
(4)
A (n(pt)
where Po- Pmazz are hyperparameters and X, denotes the token insertion penalty used in STC for training step l. For choosing value of т, is useful think in terms of half-life /1/2 rln(2), which is the number of time steps taken for pt to reach (Po + pmaz)/2
3.3.2 On the importance of (+) token
The "(*)(t" token which matches any token except the token, t is useful not count the same alignment path multiple times while computing the STC loss. We illustrate it through the two possible STC label graphs from Figure 5 Consider that the partial label has just
word "the" and number of time steps, T= In Figure 5p, the aligmment path ("the", "the", "cat") is counted multiple times when
start token (*) directly 0-> 1 2 4 and 0 2 4 + 4. However, if we use (t) token as shown in Figure 5b we do not have this issue of accepting the path "the the cat" multiple times.
should also be noted that the "(*)\ token is only present after the token / but not before the token t in the label graph of STC from Figure 4 So, the label graph would still accept all possible labels sequences for the given partial label.
3.3.3 Implementation Details
With the recent advent of frameworks such GT) K2[19] which support autograd on WF- STs, we focus on the engineering details used by us to use these frameworks and train large-scale recognition systems below.
implement the STC criterion. Multiple We use the CPU-based WFST algorithms from GTN [S]
threads are used to compute STC loss in parallel for all of the examples in a batch. Since the neural network model is run on GPU, the emissions needed by STC must copied to the CPU, and the STC gradients must be copied back to GPU. To reduce the amount of data transfer between the CPU and the GPU, we transfer values corresponding only to the tokens present the partial labels and the star tokens. This works since the gradients corresponding to all other tokens zero.
5

---

Figure shows an overview of the STC training pipeline. The input sequence is typically passed through neural network on GPU produce a frame wise distribution (in log-space) over { The output number of frames depend on the size of the input sequence, as well as the amount of padding and the stride of the neural network model architecture. We then compute the ergpobbbbillity of star token, (*) and (+){E tokens Vt. E y using Equation 3 We construct the emission graph &x with weights as bog-probabilities and the label graph Late on CPU. Using the WFST operations shown in Figure 2 we compute STC Ioss and gradients of loss with respect to are weights (log probability output) of Ex. These gradients are copied back to GPU and the gradients of parameters in neural network are computed using backpropagation. Then the model can be trained using standard gradient descent methods.
Curput mondemmttio
(110.
(b10
11
Farmwos das buson In log-specal oour Auboi
chell
lod
1eliiu Sofeei lchol
Bb/v
(h1/0)
(119
Nousa Natwork
thei
8 graph
Compute STC
harkpopp
(b)
glvnn
Figure 5: Examples illustrate the importance of (+) token
Figure 6: The STC Training Pipeline
4 Experimental Setup
4.1 Automatic Speech Recognition (ASR)
We use LibriSpeech 33 dataset, containing 960 hours of training audio with paired transcriptions for speech recognition experiments. The standard LibriSpeech validation sets (dev-clean and dev-other) are used to tune all hyperparameters, as well as to select the best models. We report final word error rate (WER) performance on the test sets (test-clean and test-other).
We use the top 50K words (sorted by occurance frequency) from the official language model (LM) training data provided with LibriSpeech as the alphabet for training the models. These 50K words cover 99.04% of all the word occurances in the LM training data. The model architectures and the STC loss are implemented with the ASR application [35] of the flashligh(" machine-learninn framework and the C++ API of GTN.
4.1.1 Label Generation for Weakly Supervised Sctup
As LibriSpeech dataset consists of fully labeled data, we need to drop the labels manually to simulate the weakly supervised setup. We quantify this using a parameter p_drrp_ddppe p_drop E [0, 1], which denotes the probability of dropping word from the transcript label. It can be seen that higher value of _rop corresponds to higher number of missing words in the transcript and vice-versa. Figures 7h-b show the histogram of percentage of the labeled words present in each training sample in LibriSpeech for different values of p_dh drop which closely follows a normal distribution. Also, from the definition of p. proro it naturally follows that p_ p_drop 0 corresponds to supervised training setup while p_drop= = 1 corresponds to unsupervised training.
To make sure our method is robust to different types of partial labels, we also test our method on two other ways of generating the data:
1. Randomly split the training set into p parts and use different p p_drop for each split (Figure 7.) 2. Randomly split the set of all words in training vocab into p parts, use a different p p_drop for each split (Figure !)

---

25
50
75
100
25
50
100
25
50
75
100
25
50
75
100
% actuall words present
% of actual woods present
% of actual words present
%6 octuall words preseut
(a) P. P_drop 0.4
(b) p. p_dmp 0.7
(c) p_drop 0.1, 0.4, 0.7 for random splits of samples
(d) d_ppppp-- = 0.1, 0.1,0.4, 0.7 for random splits words
Figure Histograms of percentage of transcript words retained each training sample in LibriSpeech for different ways of generating weakly supervised data using p_ drop.
For all the new partially labeled datasets created, we prune samples which have empty transcriptions before using them for training.
4.1.2 Pseudo-labeling
To further achieve better word error rate (WER), we generate pseudo labels (PLs) on the training set using the word-based model trained with STC and use these PLs to train a letter-based model, via regular CTC approach. The PLs are generated using rescoring as described in Section B.1.2 on the training set using the hyperparameters optimized on validation set.
4.2 Handwriting Recognition (HWR)
Ouce aud- lur all
care olke of 357 Wilni
Prexideud
True Label: once- nnce--nd-forralllcsslooorrrfffff http://cciiiiioeooosiiioiioooooo
pDrop = 0.1 oow.adofollccchooffcccoioiiiiiia (Priiedn pDrop 0.3 once onc...ndffflaaaaloiiiiiiiooosss.
pDrop = 0.7 mc-llafl7mlioPreii
Figure 8: A training example from IAM along with weakly supervised labels generated for different p_drop values.
We test our approach on IAM Handwriting database (26,, which is a widely used benchmark for handwriting recognition. The dataset contains 78 different characters and a white-space symbol, |- We use Aachen data splits to divide the dataset into three subsets: 6,482 lines for training, 976 lines for validation and 2,915 lines for testing.
To create weakly supervised labels, we use the same methodology using p_ drop as described in However, we drop the labels at character-level instead of word-level. This is because it is efficient to express the STC label graph with "(+)" tokens when we use the same type of targets which are being dropped. In ASR, the targets are dropped at word level, hence we choose words and in HWR we use character targets. Figure 8 shows a training example from IAM along with weakly supervised labels generated for different p_ drop values. Additional implementation and training details (models, tokens, optimization, other hyperparameters and settings) for the ASR and HWR experiments are in the Appendix B
https::/www.open.t wwpenssr.org/55..

---

Table 1: WER comparison LibriSpeech test sets for various partial label generation settings. For each setting, we report the results for training with CTC (control experiment), STC on the partially labeled data and training with CTC using PLs generated from the trained STC model. Whenever possible, for each of these experiments, we report WER with a greedy decoding and no LM (top row), with 5-gram LM beam-search decoding (middle row) and with additional second-pass rescoring by Transformer LM (below row). We also include state-of-the-art results on LibriSpeech using wordpieces, letters and words output tokens in the top section of the table.
WEAK GEN. STRATRGY
MODEL STRIDE/
OUTPUT
TEST WER CLEAN/OTHER
PARAMETERS
TOKENS
CONFORMER
RNN-T
4/119M
IK WORD PIBCES
2.1/4.3
44
LSTM
1.9/3.9
TRANSFORMER
CTC
3/270M
LETTERS
WORD 5-GRAM
2.4/5.3
TR. RESCORING
2.1/4.5
SBQZSBQ
8/~ 300M
WORDS
WORD 4-GRAM
3.0/6.3
6.2/11.0
TRANSFORMER
CTC
3/270M
LETTERS
WORD S GRAM
4.9/8.8
RESCORING
4.1/9.0
P_DROP= 0.1
TRANSPORMER
STC
8/70M
WORDS
WORD S GRAAM TR. RESCORING
4.1/8.7
3.3/6.9
3.1/6.3
PSEUDO LABELING
CTC
3/270M
LETTERS
WORD S G-GRAM TR. RESCORING
2.9/5.6
2.7/5.2
TRANSFORMER
CTC
LETTERS
48.2/56.9
4,5/10.2
8/70M
WORDS
WORD
TR. RESCORING
3.6/7.7
3.3/6.6
PSEUDO LABELING
CTC
3/270M
LETTERS
WORD S-GRAM
3.1/5.9
TRANSFORMER
CTC
3/270M
LETTERS
100/100
6.9/15.1
P_DROP 0.7
TRANSFORMER
7.0/14.8
TR. RESCORING
5.1/11.1
PSEUDO LABELING
CTC
3/270M
LETTERS
WORD S-GRAM TR. RESCORING
3.5/7.0
3.1/6.2
TRANSFORMER
CTC
3/270M
LETTERS
58.6/63.9
SPLIT SAMPLES
4,9/11.1
INTO PARTS
TRANSFORMER
STC
8/70M
WORDS
WORD 5 GRAM TR. RESCORING
5.1/11.0
RANDOMEY:
3.7/8.2
ASSIGN P_ DROF= 0.1.0.4.0.7 FOR THE SPLITS
3.3/6.7
PSEUDO LABELING
CTC
3/270M
LETTERS
WORD S-GRAM
3.0/5.9
TR. RESCORING
2.8/5.4
TRAKSFORMER
CTC
3/270M
LETTERS
45,6/49.2
SPLIT INTO PARTS RANDOMLY;
5,8/13.0
TRANSFORMER
STC
8/70M
WORDS
WORD S-GRAM
6.6/12.2
ASSIGN P. DROP= 0.1.0.4.0.7 THE SPLITS
3.4/6.9
LABELING
3/270M
WORD
3.1/5.9
TR. RESCORING
2.9/5.6
5 Results
5.1
Automatic Speech Recognition
In Table [ we compare the WER performance of STC models for a fixed value of p_drop 0.1, 0.4, 0.7 and also when p_drop is dependent on the sample or the word. We also compare these results with the models trained directly with CTC on the partial labels. We can see that STC performs better than CTC in all the settings. We observe that performing beam search decoding

---

P_DROP
METROD
DEV CER
TEST CER
TRANSPORMER
4.7
21
CNN+CTC
43
LSTM W/ATTN
28
STC
CTC
1AM LibriSpecch
CNN CTC (OUR BASELINE)
3.7
5.4
CNN + CTC
5.4
7.7
0.1
CNN +
CNN + CTC
8.7
11.6
0.3
CNN + CTC
48.2
53.6
0.5
CNN STC
10.0
13.5
300
400
500
600
700
CNN
77.3
0.7
CNN STC
22.7
26.7
Epoch Time (in seconds)
Table 2: CER performance comparison of STC and CTC with greedy decoding on IAM dataset for different p_ pror values. A comparison with selected works using the "same" training set is shown at the top.
Figure 9: Epoch time performance of STC, CTC on LibriSpeech and IAM datasets for the models have used.
and an additional second-past rescoring with a Transformer LMM can reduce the WER of the models significantly.
also see that pseudo labeling the training set using STC model trained on partial labels and then training a letter-based CTC model can further improve WER performance. We can get competitive results compared with the fully supervised results.
5.2 Handwriting Recognition
In Table we compare the CER performance of CTC and STC for various values of p_ drop with greedy decoding. We can see that using STC clearly gives better performance over CTC trained models for p_drop= = 0.1, 0.3, 0.5, 0.7. The performance gap between the supervised baseline and models trained with partial labels using STC larger compared to ASR experiments. This because we did not use LM decoding pseudo-labeling steps which should help in reducing CER.
Hyperparameters used for token insertion penalty, À to train STC models for ASR, HWR experiments are in Appendix D
5.3 Runtime Performance STC
In Figure 9 we compare the epoch time of STC, CTC models LibriSpeech and IAM datasets. For a fair comparison, we use the same model that used to report STC results for each dataset. The experiments LibriSpeech, IAM are APIs of GTN respectively.
32, 8 Nvidia 32GB V100 GPUs and uses C++, Python
We were able to run epoch on LibriSpeech in about 300 seconds for the STC model and in about 250 seconds for the CTC model. Optimizing data transfer berween CPU and GPU by only moving the tokens which are present in the current training sample (Section 3.3.3) is a crucial step in achieving good performance. Without this optimization, would take about 5400 seconds per epoch on LibriSpeech the alphabet size, |A] of 50000 is very high.
For IAM experiments, did not perform the data transfer optimization for STC as |.|] is only 79. can be see that the epoch time of STC is about 25% more compared to CTC.
Conclusion
In variety of sequence labeling tasks (ASR, HWR), we show that STC enables training models with partially labeled data and can give strong performance. Weakly supervised data can be collected in semi-automatic ways and can alleviate labeling of full training data, thus reducing production costs.

---

We also show that using WFSTs with differentiable framework is flexible and powerful tool for researchers to solve a completely new set of problems, like the example we have shown in this paper. STC requires additional hyperparameter tuning and these vary by p_drop. The label graph can be easily modified to include the cases where the missing label's position or the number of missing tokens is known in advance. Also, STC can be specialized to allow a particular range of missing tokens (e.g. between 2 and 4 characters). A direct potential extension to study the application of STC to noisy labels.
References
[1] Jaume Amores. Multiple instance classification: Review, taxonomy and comparative study. Artif. Intell., 201:81-105, 2013.
[2] Yannis Assael, Thea Sommerschield, and Jonathan Prag. Restoring ancient text using deep learning: a case study on Greek epigraphy. In Empirical Methods in Natural Language Processing, pages 3369-6376 2019.
[3] Yannis Assael, Thea Sommerschield, Brendan Shillingford, Mahyar Bordbar, John Pavlopoulos, Marita Chatzipanagiotou, Ion Androutsopoulos, Jonathan Prag, and Nando de Freitas. Restoring and attrhutinng ancient texts using deep neural networks. Nature, 2022. doi: 10.103884411886-22--444444
[4] Peter Bell and Steve Renals. A system for automatic alignment of broadcast media captions using weighted inite-state transducers. pages 675-680, 12 2015. doi: 10.1 109//O//SSUU 7.14.44866..
[5] Xingyu Cai, Jiahong Yuan, Yuchen Bian, Guangxu Xun, Jiaji Huang, and Kenneth Church. W-CTC: connectionist temporal classification loss with wild cards. In International Conference on Learning Representations, 2022. URL /tttps:/ ew net do
[6] Olivier Chapelle, Bernhard Scholkopf. and Alexander Zien. Semi-supervised learning (chapelle, al., eds.; 2006)[hook reviews]. IEFE Transactions on Neural Networks, 20(3):542-542, 2009.
[7] Ronan Collobert, Christian Puhrsch, and Gabriel Synnaeve. Wav2letter: end-to-end convnet-based speech recognition system. arXiv preprint arXiv: arXiv:1609.088
2016.
[8] Ronan Collobert, Awni Hannun, and Gabriel Synnaeve. Word-level speech recognition with a letter to word encoder. In International Conference on Machine Learning, pages 2100- 20000 PMLR, 2020.
[9] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. J. Mach. Learn. Res., 12(mull); 1501-1536, jul 2011. ISSN 1532-4435.
[10] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121-2) 2011. URLhtttp Saimlr.org//apaae w1tperr//vvv/aa htcp///chhiii 11a. html
[11] Adrien Dufraux, Emmanuel Vincent, Awni Hammun, Armelle Brun, and Matthijs Douze. Lead2gold: Towards exploiting the full potential of noisy transcriptions for speech recognition. In 2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pages 78 85. IEEE, 2019.
[12] Angela Fan, Edouard Grave, and Armand Joulin. Reducing transformer depth on demand with structured dropout. In International Conference on Learning Representarions, 2019.
[13] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber. Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks. In Proceedings of the 23rd international conference Machine learning, pages 369-376, 2006.
[14] Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang. Zhengdong Zhang, Yonghui Wa, and Ruoming Pang. Conformer: Convolution-augmeene Transformer for Speech Recognition. In Proc. Interspeech 2020, pages 5036-5040, 2020. doi: 10.21457/Intesspeechh 2020-300 3015.
[15] Awni Hannun, Vineel Pratap, Jacob Kahn, and Wei-Ning Hsu. Differentiable weighted finite-state transducers. arXiv preprint arXiv:2010.01003, 2020.
[16] Timothy J. Hazen. Automatic alignment and error conrection of human generated transcripts for long speech recordings. In INTERSPEECH, 2006.
[17] De-An Huang, Li Fei-Fei, and Juan Carlos Niebles. Connectionist temporal modeling for weakly supervised action labeling. In European Conference Computer Vision, pages 137-153. Springer, 2016.
10

---

[18] Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In NIPS, 2002.
[19] k2-fsa. hatpss//ggttuub..cc/////t/a// com/k2-fsa/kktt 2021.
[20] Mohammed Waleed Kadous. Temporal classification: extending the classification paradigm to multivariate time scries. 2002.
[21] Lei Kang, Pau Riba, Marçal Rusiñol, Alicia Fornés, and Mauricio Villegas. Pay attention to what you read: Non-recurrent handwritten text-line recognition, 2020.
[22] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: vrXiv:1412.6988) 1412.6980, 2014.
[23] Aleksandr Laptev, Somshubra Majumdar, and Boris Ginshurg. CTC variations through new wfst topologies. arXiv preprint 10.0022 2021.
[24] Tatiana Likhomanenko, Qiantong Xu, Vineel Pratap, Paden Tomasello, Jacob Kahu, Gilad Avidov, Ronan Collobert, and Gabriel Synnaeve. Rethinking Evaluation in ASR: Are Our Models Robust Enough? In Proc. Interspeech 2021, pages 31 311-315, 2021. doi: 10.2 24144////eesspocccc2221111--1
[25] Liping Liu and Thomas Dietterich. Learnability of the superset label learning problem. In Eric P. Xing and Tony Jehara, editors, Proceedings of the s1 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1629-1637, Bejing, China, 22-24 Jun 2014. PMLR.
[26] U-V Marti and Horst Bunke. The iam-database: english sentence database for offline handwriting recognition. International Journal on Document Analysis and Recognition, 5(1):39-46, 2002.
[27] Yajie Miao, Mohammad Gowayyed, and Florian Metze. Eesen: End-to-end speech recognition using deep rnn models and wfst-hasedd decoding. In 2015 IEFE Workshop on Automatic Speech Recognition and Understanding (ASRU), pages 167-174. IEEF, 2015.
[28] Johannes Michael, Roger Labahn, Tobias Grüning, and Jochen Zöllner. Evaluating sequence-to-sequeen models for handwritten text recognition. In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 1286 1293. IEEE, 2019.
[29] Mehryar Mohri, Weighted automata algorithms. In Handbook of weighted automata, pages 213-254. Springer, 2009.
[30] Mehryar Mohri, Fernando Pereira, and Michael Riley. Speech recognition with weighted finite-state transducers. In Springer handbook of speech processing, pages 559-584. Springer, 2008
[31] Pedro Moreno and Christopher Alberti. A factor automaton approach for forced alignment of long speech recordings. pages 4869-4872, 04 2009, doi: 10.1 10111///ASSPP200999000000
[32] Niko Moritz, Takaaki Hori, and Jonathan Le Roux. Semi-supervised speech recognition via graph-baser based temporal classification. In ICASSP 202 2221 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1554866557 IEEF, 2021.
[33] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an ast corpus based public domain audio books. In 2015 JEEE international conference acoustics, speech and signal processing (ICASSP), pages 5206 5210. IEEE, 2015.
[34] Daniel Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekkn D. Cubuk, and Quoe V. Lec. Specaugment: simple data augmentation method for automatic speech recognition. Interspeech 2019, Sep 2019. doi: 10.21 20044///icerppcccch2001--9-1 2019-2680
URL http::/tt///tt //tt:://dx..u doi. //0g 21437 (0444//Innerppaa Interepeech
[35] Vincel Pratap, Awni Hannun, Qiantong Xu, Jeff Cai, Jacob Kahn, Gabriel Synnaeve, Vitaliy Liptchinsky, and Ronan Collobert. Wav2letter++: A fast open-source speech recognition system. ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2019, doi:
10. 10.1109/ccssp.20199 201.888335.......355....
URL httl./ttt://dx..cc doi. .ww.:ooii.ooogoooo 10. 1109 1109/ICASSP ICASSP 0001.86835335
[36] Vineel Pratap, Qiantong Xu, Tatiana Likhomanenko, Gabriel Synnaeve, and Ronan Collobert. Word order does not matter for speech recognition. arXiv preprint urXiv:2110.05994 2021.
[37] Gabriel Synnaeve, Qiantong Xu, Jacob Kahn, Tatiana Likhomanenko, Edouard Grave, Vineel Pratap, Anuroop Sriram, Vitaliy Liptchinsky, and Ronan Collobert. End-to-end asr: from supervised to semi- supervised learning with modern architectures, 2020.

---

[38] Ashish Vaswani, Noam Shazeer. Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances neural information processing systems, pages 5998-6008, 2017.
[39] Enrique Vidal, Franck Thollard, Colin De La Higuera, Francisco Casacuberta, and Rafacl C Carrasco. Prohabilistic sinite-state machines-part and ii IEEE transactions on pattern analysis and machine intelligence, 27(7). 2005.
[40] Curtis Wigington, Brian Price, and Scott Cohen. Multi-label connectionist temporal classification. In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 979-986. TEEF, 2019.
[41] Hongyu Xiang and Zhijian Ou, Crf-based single-stage acoustic modeling with ctc topology. In ICASSP 2019-2019 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 5676 5680. IEEE, 2019.
[42] Mohamed Yousef and Tom E. Bishop. Origaminet: Weakly-supervised. segmentation-fee one-step, full page textrecognition learning unfold. In The IEEE Conference Computer Vision and Puttern Recognition (CVPR), June 2020.
[43] Mohamed Yousef, Khaled F Hussain, and Usama S Mohammed. Accurate, data-efficient, unconstrained text recognition with convolutional neural networks. Pattern Recognition, 108:107482, 2020.
[44] Zhi-Hua Hua Zhou, Min-Ling Zhang. Sheng-Jun Jun Huang, and Yu- Yu-Feng Li. Multi-instance multi-label learning. Artificial Intelligence, 176(1):2291 1222222,,,, 2012.
Checklist
1. For all authors...
(a) Do main claims made the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs all thcoretical results? [N/A]
3. If you experiments..
(a) Did you include code, data, and instructions needed to reproduce main experimental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No]
(d) Did you include total amount of compute and the type resources used (e.g., type GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/relcusing new assets...
(a) your work uses existing assets, you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 'r us-
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "p-be0TxULR", "reviewer": "Reviewer_twp9", "summary": "The paper proposes Star Temporal Classification (STC) to solve the problem of missing labels for weakly supervised sequence labeling tasks (such as ASR, HWR). STC uses a special star token to allow alignments which include all possible tokens whenever a token could be missing. Technically, STC uses differentiable WFSTs to implement the loss function. Experiments are conducted for speech recognition over Librispeech and handwriting recognition over IAM, which demonstrate the effectiveness of STC.\n", "questions": "see above", "limitations": "see above", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-Strengths\n\nThe paper is generally well-written. The problem of missing labels is clearly formulated and solved in the framework of differentiable WFSTs. The techniques of introducing the star token and token insertion penalty are new. Moreover, the implementation of STC, especially to integrate CPU-based WFST algorithm and GPU-based neural network gradient calculation, is non-trivial, which requires engineering efforts. The experiments seem to be good.\n\n-Weaknesses\n\nConcerns about the experiments:\n\n1) The proposed method is designed to work for weakly supervised setup. But in practice, it is not known whether the labels are missing and the proportion of missing is also unknown. So the performance of applying STC in the fully-labeled setting is an important indicator. If such performance becomes worse due to the use of STC, then STC may not be practically useful.\n\n2) In real-world tasks, the labels are missing for many reasons. An important scenario is that the labels are not really missing, but are discarded after some filtering such as by confidence measures. This scenario is described in Line 21-23 in the Introduction, but not fully evaluated in the paper.\n\nThe proposed method is only experimented in the simple scenario, where some positions in the label sequence are really missing (not labeled). This is a simple scenario, which may not be so interesting in real-world tasks. The baseline of running CTC over the incomplete labels is too weak. \n\nI suggest that the authors can take experiments and show improvement in more realistic scenarios (e.g., semi-supervised learning or transfer learning), as described in the Introduction.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k8M7qpXHkay", "reviewer": "Reviewer_eojv", "summary": "This paper presents Star Temporal Classification (STC) an approach to train sequential models where there is an expectation that some labels are missing.  The key machinery to accomplish this is composition with a WFST constructed, and appropriately weighted to train with sequences of the (regular expression) form * A * B * C * rather than A B C.", "questions": "* The introduction and abstract experimental performance is described imprecisely. \"recover most of the performance\" \"low word error rates\".  It might be more impactful to be more exact in these descriptions -- how close to fully observed labeling exactly? what does \"low\" mean in these contexts.\n\n* STC is not evaluated with pDrop=0.0. This data point would provide confidence that this approach can be used without losing performance if labels are present (or if they are not).  Even the randomly split samples always assume at least 10% of labels are dropped.\n\n* What is the impact of modifying the collapse function to only remove blanks instead of also removing duplicates?\n\n* How is the token insertion penalty tuned? How big an impact does correctly setting this hyperparameter have?\n\n* What is the rationale for word based targets followed by letter based refinement?  The 1k word pieces seems to be a better target for librispeech asr, but this isn't used in any CTC or STC experiments. why not?\n\n* re baselines: Why not use a Conformer model in these experiments?  (the rationale for using CTC rather than RNNT is clear though.)\n\n* The best performing approach for STC requires a two-pass training routine using Word targets to recover missing labels and then Letter targets for final training. The word targets are described as an efficiency bottleneck in section 5.3 as well.  Why can't STC work on letter targets directly?  Is this because the sequence length is too long with letter targets?  Is there any benefit to this style training for the CTC baseline?  While the performance improvements are clear, this seems unrelated to the central STC idea.\n\n* A couple of possible typos in table 1.  The second to last line reports errors of \".1/5.9\".  The third row in the LM column includes \"2.5/5.9\"", "limitations": "* Without an evaluation at pDrop=0.0 it is hard to have confidence that this is a reliable drop-in replacement for CTC training.  If it's not this limits the impact of this work to only those instances where a user has a reasonable understanding that the available training data has been partially labeled.\n\n* STC requires additional hyperparameter tuning and these vary by pDrop.  ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n* STC is a clearly written extension to CTC, leveraging the ability to construct a decoding topology with a WFST.  \n* The basic approach taken opens itself up to modifications of the WFST beyond the STC formulation.\n* Demonstrates that STC can substantially improve performance on ASR and handwriting recognition, even with relatively high rates of label deletion.\n\nWeakness\n* The practical motivation is somewhat strained. While there are plenty of instances where labels may be missing (occlusion etc.), however, in most (many?) cases including those offered in the introduction the \"missing\" label's position is known.  For example for semi-supervised learning to mask low-confidence tokens, while the identity of the tokens may not be trusted, their position usually can.  Similarly in the handwriting recognition example, while there may be ambiguity in which characters are present, the number of characters is less confusable.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I14Og9e0BdK", "reviewer": "Reviewer_dZmF", "summary": "This paper proposes star temporal classification (STC), an extension of CTC particularly designed when only partial labeled supervision is available.", "questions": "I would like to hear authors opinion about my points in weakness.", "limitations": "I did not see any discussion on limitations.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Modeling when partial label is available is an interesting problem and can have several applications including the ones explained in introduction. A very relevant example can be recovering complete text for ancient literature when only partial text is recovered (references 2 and 3 of paper).\n\nWeakness:\n- One major issue with this paper is clarity of text and definitions. Examples:\n1. Use of 
 as star token: this symbol is widely used as start-of-sentence in the literature\n2. Equation 3, $P(
|x) = \\sum_{y\\in\\mathcal{A}} P(y|x)$, I think there should be some notion of time in this equation, otherwise I am not sure if rest of model makes sense. Second, if this is time dependent posterior, is it simply 1.0 - P(<b> | x, t)? \n3. text issues:page 5, \"is is useful think ...\"\n4. Many issues in Table1:\n4.a row starting with \"TRANSFORMER[36]\": there is some number under LM (2.5/5.9), what does this mean?\n4.b one to the last row, there is 0.1/5.9, does this model perform 0.1 on clean or is it a typo?\n5. The definition of the randomly split the words in bottom of page 6 is not clear to me.\n6. The notation pDrop, how about p_drop ?\n\n- Another major concern I have is the significance of modeling presented in this paper.\nI think the change is not very far from original CTC, it only changes state transition of CTC, this can be done for any other model, like RNNT. While important, I am not sure if it is significant.\n\n- Finally, there is a major concern about baseline comparisons:\n1. All the experiments presented are on simulated dataset created by authors, no previous numbers are reported on these partially labeled dataset. The main comparison is with fully labeled data. I don't think this sufficiently evaluate STC. Why not reporting some number on some other datasets, like the ones presented in reference 2 or 3.\n2. STC is not compared against other methods for recovering partially labeled data. For example one baseline can be creating pseudo label from CTC + LM for missing labeled and train with partial+pseudo labels. Maybe this will do as good as STC?\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept