Sequential Density Ratio Estimation for Simultaneous Optimization of Speed and Accuracy
Authors: Akinori F Ebihara
Taiki Miyagawa
Kazuyuki Sakurai
Hitoshi Imaoka
Venue: ICLR 2021 Spotlight (2021)
Keywords: Sequential probability ratio test
Early classification
Density ratio estimation

Abstract: Classifying sequential data as early and as accurately as possible is a challenging yet critical problem, especially when a sampling cost is high. One algorithm that achieves this goal is the sequential probability ratio test (SPRT), which is known as Bayes-optimal: it can keep the expected number of data samples as small as possible, given the desired error upper-bound. However, the original SPRT makes two critical assumptions that limit its application in real-world scenarios: (i) samples are independently and identically distributed, and (ii) the likelihood of the data being derived from each class can be calculated precisely. Here, we propose the SPRT-TANDEM, a deep neural network-based SPRT algorithm that overcomes the above two obstacles. The SPRT-TANDEM sequentially estimates the log-likelihood ratio of two alternative hypotheses by leveraging a novel Loss function for Log-Likelihood Ratio estimation (LLLR) while allowing correlations up to $N (\in \mathbb{N})$  preceding samples. In tests on one original and two public video databases, Nosaic MNIST, UCF101, and SiW, the SPRT-TANDEM achieves statistically significantly better classification accuracy than other baseline classifiers, with a smaller number of data samples. The code and Nosaic MNIST are publicly available at https://github.com/TaikiMiyagawa/SPRT-TANDEM.

Published as a conference paper at ICLR 2021
SEQUENTIAL DENSITY RATIO ESTIMATION FOR SIMULTANEOUS OPTIMIZATION OF SPEED AND ACCURACY
Akinori F. Ebihara!
Taiki Miyagawa!
Kazuyuki Sakurai'
Hitoshi Imaoka'
NEC Corporation
PRIKNN Center for Advanced Intelligence Project (AIP)
aebihara@nec. com
ABSTRACT
Classifying sequential data as early and accurately as possible a challenging yet critical problem, especially when a sampling cost is high. One algorithm that achieves this goal is the sequential probability ratio test (SPRT), which is known as Bayes-optimal it can keep the expected number of data samples as small as possible, given the desired eтror upper-bound. However, the original SPRT makes two critical assumptions that limit its application in real-world scenarios: (i) samples are independently and identically distributed, and (ii) the likelihood of the data being derived from each class can be calculated precisely. Here, we propose the SPRT-TANDEM, a deep neural network-bart SPRT algorithm that overcomes the above two obstacles. The SPRT-TANDEM sequentially estimates the log- likelihood ratio of two alternative hypotheses by leveraging a novel Loss function for Log-Likelihood Ratio estimation (LLLR) while allowing correlations up N(E N) preceding samples. In tests on one original and two public video databases, Nosaic MNIST, UCF101, and SiW, the SPRT-TANDEM achieves statistically significantly better classification accuracy than other baseline classifiers, with a smaller number of data samples. The code and Nosaic MNIST are publicly available at httph::://// //ga::///ttttiii thub. com/ aa i Mi yawawa SPRT- TANDEM
INTRODUCTION
The sequential probability ratio test, or SPRT, was originally invented by Abraham Wald, and an equivalent approach was also independently developed and used by Alan Turing in the 1940s (Good) 1979, Simpson 2010: Wald 1945). SPRT calculates the log-likelihood ratio (LLR) two competing hypotheses and updates the LLR every time new sample is acquired until the LLR reaches one of the two thresholds for alternative hypotheses (Figure D.. Wald and his colleagues proved that when sequential data are sampled from independently and identically distributed (i.i.d.) data, SPRT can minimize the required number of samples to achieve the desired upper-bounds of false positive and false negative rates comparably the Neyman-Pearson
Pearson test, known as the most powerful likelihood test (Wald & Wolfowitz 1948) (see also Theorem (A.5) in Appendix Aj. Note that Wald used the i.i.d. assumption only for ensuring finite decision time (i.e., LLR reaches threshold within finite steps) and for facilitating LLR calculation: the non-i.i.d, property does not affect other aspects of the SPRT including the error upper bounds (Wald) 1947). More recently, Tartakovsky al. verified that the non-i.i.d. SPRT is optimal or at least asymptotically optimal as the sample size increases (Tartakovsky et al. 2014), opening the possibility of potential applications of the SPRT to non-i.i.d. data series.
About 70 years after Wald's invention, neuroscientists found that neurons the part the primate brain called the lateral intraparietal cortex (LIP) showed neural activities reminiscent of the SPRT (Kira et al. 2015); when a monkey sequentially collects random pieces of evidence to make a binary choice, LIP neurons show activities proportional to the LLR. Importantly, the time of the decision can be predicted from when the neural activity reaches a fixed threshold, the same as the SPRT's s decision rule. Thus, the SPRT, the optimal sequential decision strategy, re-discovered to be an

---

Published as a conference paper at ICLR 2021
Early decision
accepting the hypothesis H y
Threshold @1
Decision value: Log- likellhood ratio
Undecided
(2(1), x
y
1)
d log
0
(2(1), x
Late, "careful" decision accepting the hypothesis Ho
Threshold 0g
Time
Figure 1: Conceptual figure explaining the SPRT. The SPRT calculates the log-likelihood ratio (LLR) of two competing hypotheses and updates the LLR every time sample (x(*) at time is acquired, until the LLR reaches one of the two thresholds. For data that is casy be clusiilee,, the SPRT outputs an answer after taking lew samples, whereas for diflicult data. the SPRT takes in numerous sumples in order make "careful" decision. For formal definitions and the optimality early classification of time series, Appendix
algorithm explaining primate brains' computing strategy. remains an open question, however, what algorithm will be used in the brain when the sequential evidence is correlated, non-i.idd series.
The SPRT is now used for several engineering applications (Cabri et al. 2018 Chen et al. 2017] Kulldorff et al., 201T). However, its i.id. assumption is too crude for to be applied to other real-world scenarios, including time-series classification, where data are highly correlated, and key dynamic features for classification often extend across more than one data point, violating the i.i.d. assumption. Moreover, the LLR of alternative hypotheses needs to be calculated as precisely as possible, which is infeasible in many practical applications.
In this paper, we overcome the above difficulties by using an SPRT-based algorithm that Treats data series As an N-th orDEr Markov process (SPRT-TANDEM), aided by a sequential probability density ratio estimation based on deep neural networks. A novel Loss function for Log- Log-Likeeihood Ratio estimation (LLLR) efficiently estimates the density ratio that let the SPRT-TANDEM approach close to asymptotic Bayes-optimality (i.e., Appendix (A.4). In other words, LLLR optimizes classification speed and accuracy at the same time. The SPRT-TANDEM can classify non-i.i.d. data series with user-defined model complexity by changing Nee N). the order of approximation, to define the number of past samples on which the given sample depends. By dynamically changing the number maintain high classification accuracy
of samples used for classification, the SPRI-TANDEM while minimizing the sample size as much as possible. Moreover, the SPRT-TANDEM enables a user flexibly control the speed-accuracy tradeoff without additional training, making it applicable to various practical applications.
We test the SPRT-TANDEM publicly available UCF101 action recognition database (Soomro et al. 2012) and Spoofing in the Wild (SiW) database (Liu et al. 2018). Two-way analysis of variance (ANOVA, (Fisher 1925) ) followed by a Tukey-Kramer proposed SPRT-TANDEM provides statistically significantly higher accuracy than other fexed-length and variable-length classifiers at smaller number of data samples, making Wald's s SPRT applicable even to non-i.i.d. data series. Our contribution is fivefold:
database, Nosaic MNIST (NMNIST), in addition to the
colli-comparison test (Tukey 1949; Kramer 1956) shows that our
1. We invented a deep neural network- algorithm, SPRT-TANDEM, which enables Wald's SPRT on arbitrary sequential data without knowing the true LLR.
2. The SPRT-TANDEM extends the SPRT to non-i.i.d. data series without knowing the true LLR.
3. With novel loss, LLLR, the SPRT-TANDEM sequentially estimates LLR optimize speed and accuracy simultaneously.
4. The SPRT-TANDEM can control the accurayy tradeoff without additional training.
5. We introduce Nosaic MNIST, novel early-classffication database.
2 RELATED WORK
The SPRT-TANDEN has multiple interdisciplinary intersections with other fields of research: Wald's classical SPRT, probability density estimation, neurophysiological decision making, and time-series
2

---

Published as a conference paper at ICLR 2021
classification. The comprehensive review is left to Appendix B while in the following, introduce the SPRT. probability density estimation algorithms, and early classification of the time series.
Sequential Probability Ratio Test (SPRT). The SPRT. denoted by 8*, is defined as the tuple of a decision rule and a stopping rule (Tartakossky et al.) 2014 Wald 1947):
Definition 2.1. Sequential Probability Ratio Test (SPRT), Let X as the LLR at time I, and X as a sequential data (1.T") : -[x(0)) Y(z1- Given the absolute values of lower and upper decision threshold, ug 2 and 01 2 0, SPRT, 8*, is defined as
8 =(d'; :T),,
(1)
where the decision rule d' and stopping time T" are
if Ar 2 a1
d' (X 0 Xy- S -a0
(2)
inf [T 2 0fAT & (-ao. a1)}
(3)
We review the proof of optimality in Appendix A.4 while Figure I shows an intuitive explanation.
Probability density ratio estimation. Instead of estimating numerator and denominator of density ratio separately, the probability density ratio estimation algorithms estimate the ratio as whole, reducing the degree of freedom for more precise estimation (Sugiyama et al.) 2010 2012). Two of the probability density ratio estimation algorithms that closely related to our work are the
probabilistic classification (Bickel et al., 2007 Cheng & Chu 2004. Qin 1998) and density fitting
approach (Sugiyama et al. 2008 [suboo et al.) 2009) algorithms. As we show in Section and
Appendix E the SPRT-TANDEM sequentially estimates the LLR by combining the two algorithms.
Early classification of time series. To make decision time short possible, algorithms for early
classification of time series can handle variable length of data (Mori et al.] [2018] Mori et al. 2016
Xing al., 2009 2012) to minimize high sampling costs (e.g., medical diagnosties (Evans et al. 2015
Griffin & Moorman| 200T), or stock crisis identification (Ghalwash et al. (0144). Leveraging deep
neural networks is exception in the early classification of time series (Dennis et al. 2018 Suzuki
ct al. 2018). Long short-term memory (LSTM) variants LSTM-s/LSTM impose monotonicity on classitication score and inter-class margin, respectively, speed up action detection (Ma et al.) 2016).
Early and Adaptive Recurrent Label ESTimator (EARLIEST) combines reinforcement learning and recurrent neural network decide when classify and assign class label (Hartvigsen al. 2019
3 PROPOSED ALGORITHM: SPRT-TANDEM
In this section, we propose the TANDEM formula, which provides the N-th order approximation of the LLR with respect to posterior probabilities. The i..d. assumption of Wald's SPRT greatly simplifies the LLR calculation at the expense of the precise temporal relationship between data samples. On the other hand, incorporating a long correlation among multiple data may improve the LLR estimation; however, calculating too long correlation may potentially be detrimental in the following cases. First, a class signature significantly shorter than the correlation length in consideration, uninformative data samples included in calculating LLR,, resulting in late or wrong decision (Campos et af. 2018). Second, long correlations require calculating long-range of backpropagation, prone to vanishing gradient problem (Hochreiter al. (00I). Thus, we relax the i.i.d. assumption by keeping only up to the N-th order correlation to calculate the LLR.
The TANDEM formula. Here, we introduce the TANDEM formula, which computes the approxi- mated LLR, the decision value of the SPRT-TANDEM algorithm. The data series approximated as an N-th order Markov process. For the complete derivation of the Oth (i.i.d),, 1st, and N-th order TANDEM formula, see Appendix C Given maximum timestamp T' E N, let (1,2) and y be sequential data (1.7) == (xx()) )T= and a class label y E (1,0), respectively, where (9) e R and d E N. By using Bayes' rule with the N-th order Markov assumption, the joint LLR of data at
3

---

Published as a conference paper at ICLR 2021
timestamp t is written as follows:
p(x(1) x0(2) 111 y 11
log
p(x(1), xx() (1) 1 =0]
ply 1|r(5-N1 N) x (5))
ply 1| N)
x (5- 11
Σ log
Σ N=
log
p(y 0|z(6-NN) N), m.ng x x(())
ply - 0px(0-N), N¹ .rog x (8-1))
s=N+1
llog p(v =1 ply 0)
(4)
85 in Appendix for the full formula). Hereafter we use terms k-let or multiplet to indicate the posterior probabilities, p(y|= ...., ((k) plyl (11))) that consider correlation across & data points. The first two terms of the TANDEM formula (Equation 4., N 1- let and N-let, have the opposite signs working in "tandem" adjusting each other to compute the LLR. The third term is prior (bias) term. In the experiment, we assume flat prior or zero bias term, but a user may impose a non-flat prior to handling the biased distribution of a dataset. The TANDEM formula can be interpreted as a realization of the probability matching approach of the probability density estimation, under an N-th order Markov assumption of data series.
(see Equation 84 and
Neural network that calculates the SPRT-TANDEM formula. The SPRT-TANDEM is designed explicitly calculate the N-th order TANDEM formula realize sequential density ratio estimation, which is the critical difference between our SPRT-TANDEM network and other architecture based on convolutional neural networks (CNNs) and recurrent neural networks (RNN). Figure 2 illustraaees a conceptual diagram explaining a generalized neural network structure, in accordance with the 1st-order TANDEM formula for simplicity. The network consists of a feature extractor and a temporal integrator (highlighted by red and blue boxes, respectively). They are arbitrary networks that user can choose depending on classification problems or available computational resources. The feature extractor and temporal integrator are separately trained because we find that this achieves better performance than the end-to-end approach (also see Appendix D). The feature extractor outputs frame features (e.g., outputs from global average pooling layer), which are the input vectors of the temporal integrator. The output vectors from the temporal integrator are transformed with a fully-comnected layer into -oo-dimesiional logits, which are then input the softmax layer obtain posterior probabilities. They are used to compute the LLR to run the SPRT (Equation (2). Note that during the training phase of the feature extractor, the global average pooling layer is followed by fully-connected layer for binary classification.
How to choose the hy hyperaarameterr N? By tuning the hyperparameter N, a user can efficiently boost the model performance depending databases; in Section []] we change N to visualize the model performance as a function of N. Here, we provide two ways to choose N. One is to choose N based the specific time scale, concept introduced in Appendix [ where we describe in detail how to guess on the best N depending on databases. The other is to use a hyperparameter tuning algorithm, such Optuna, (Akiba al., 2019) choose N objectively. Optuna has multiple hyperparameter searching algorithms, the default of which is the Tree-structured Parzen Estimator (Bergstra al., 2011). Note that tuning N is not computationally expensive, because N only related to the temporal integrator, not the feature extractor. In fact, the temporal integrator's training speed is much faster than that of the feature extractor: mins/epoch vs. 10 hrs/epoch (N 49, NVIDIA RTX2080Ti, SiW database).
4 LLLR AND MULTIPLET CROSS-ENTRONE LOSS
Given a maximum timestamp T' E N and dataset size M E N, S: = {(x(1.7) } sequential dataset. Training our network to calculate the TANDEM formula involves the following loss functions in combination: (i) the Loss for Log Likelihood Ratio estimation (LLLR), LLLR, and (ii) multiplet cross-entropy loss, Lmultipler. The total loss, Liotal is defined as
j be
Tnotal ILLL + Tmulttiplt.
(5)
4

---

Published as a conference paper at ICLR 2021
d - log [Mz(0), ,.. ,.., .0,
A(x(1), , //////
Temporal integrator
Σ log ply 1/ 2 .00o
Miy 0/ (),bo1)))
Σ
aog
fiy 0/z6 11)
Bly 1/zlo 311
log
Ply 1
Ply
Intermediate value Network output
sm?
Decision value
Plyl=!"))
Alyl
My Ma (1/22t1),,,00 ((
6g
( )
(a B
Po
(2:1t-11)
cl2lt
Phery (- 20
Tape (x
Japp (1-
a
Time
Figure 2: Conceptual diagram neural network for the SPRT-TANDEM where the order appeoximation N The feature (red) extracts the feature vector for classifcaation and outpuls it the temgoral integrator (blue). Note that the temporal integrator memorizes up N preceding states in probability densities that are output from the temporal intogrator, We use highlight quantity estimated by neural network. Trainable weight parameters are shared across the boxes with same color figure.
TANDEM formula (Fquation (.. I.I. calculated using the estimated
4.1 Loss FOR LOG-LIKELLHOOD RATIO ESTIMATION (LLLR).
The SPRT is Bayes-optimal long the true LLR is available; however, the true LLR is often inaccessible under real-world scenarios. To empirically estimate the LLR with the TANDEM formula, propose the LLLR
1
T ΣΣ 1=1
M
p(a; ((1² (2)
, 24 . .... - ---==
LLLR
log
(6)
MT
(8) 10 0)
where a is the sigmoid function. We use ý to highlight probability density estimated by neural network. The LLLR minimizes the Kullback-Leible divergence (Kullback & Leibler 1951) between the estimated and the true densities, as we briefly discuss below. The full discussion is given in Appendix due page limit.
Density fitting. First, we introduce KLIEP (Kullback-Leiid Leibler Importance Estimation Procedure, Sugiyama al. (2008)), density fitting approach of the density ratio estimation (Sugyyama al. (2010). KLIEP is an optimization problem of the Kullback-Leible divergence between pl y = 1) and 7 (X)) ( X 0) with constraint conditions, where X and y are random variables corresponding
to x (1.() and yi. and f(X) = p(X 1)/p(Xly 0) is the estimated density ratio. Formally.
argmin (L 110==11)[[( ()(l((X))((XXXX)) 0))] = argmin [-
dxp(xlx= = log(F(X))) (7)
with the constraints f(X) and f [ddf(X)pp(X)))) = 0) The first constraint ensures the positivity of the estimated density f(x))((( = 0), while the second one is the normalization condition. Applying the empirical approximation, we obtain the final optimization problem:
argmin
Σ
log P(X(1100)
with F(X(L.0) 2 and Mo ieTo
A(X(1.0) =1 (8)
M1
where /, = (i E [M]] 1}. To = [M] 0}. Mi [/,] and Mo = VTol
Stabilization. The original KLIEP g however, is asymmetric with respect to p( = 1) and p(Xly 0). To recover the symmetry, add 1 Σien log(f(x((:))) to the objective and
impose additional constraint M, Eier, ((x() 1. Besides, the symmetrized objective
5

---

Published as a conference paper at ICLR 2021
still has unbounded gradients, which cause instability in the training. Therefore, normalize the LLRs with the sigmoid function, obtaining the LLLR (6). We can also show that the constraints are effectively satisfied due to the sigmoid funciton. See Appendix for the details.
In summary, we have shown that the LLLR minimizes the Kullback- Leibler divergence of the true and the estimated density and further stabilizes the training by restricting the value of L.R.. Here emphasize the contributions estimation and thus to perform the SPRT, the algorithm optimizing two objectives: stopping time and accuracy. In previous works (Mori et al. 2018 Hartvigsen et al. 2020), on the other hand, these two objectives are achieved with separate loss fub-functions.
the LLLR again. The LLLR enables us to conduct the stable LLR
Compared to KLIEP, the proposed LLLR statistically significantly boosts the performance of the SPRI-TANDEM (Appendix E44). Besides, experiment on multivariate Gaussian with simple toy-model also shows that the LLLR minimize errors between the estimated and the true density ratio (Appendix F)
4.2 MULTIPLET
LOSS.
To further facilitate training the neural network, we add binary cross-entropy losses, though the LLLR suffices to estimate LLR. We call them multiplet cross-entropy loss here, and defined as:
N+1
Imultiplet
Lk-let
(9)
where
T (-(N+--)
Li-let
M(T Σ
E
(-logplula
(t (t-k+1) a... (2)))
(10)
Minimizing the multiplet cross-entropy loss is equivalent to minimizing the Kullback-Leibler divergence of the estimated posterior k-let p():)= (t-(((++)))) (..,, and the true posterior p(y le (t-++1) ..... x ) (shown Appendix G which is a consistent objective with the LLLR and thus the multiplet loss accelerates the training. Note also that the multiplet loss optimizes all the
logits output from the temporal integrator, unlike the LLLR.
5 EXPERIMENTS AND RESULTS
In the following experiments, arithmetic mean of the true positive and true negative rates, and (ii) mean hitting time, the average number of data samples used for classification. Note that the balanced accuracy robust class imbalance (Luque et al. 2019), and is equal to accuracy on balanced datasets.
two quantities evaluation criteria: (i) balanced accuracy, the
Evaluated public databases NMNIST, UCF, and SiW. Training, validation, and test datasets split and fixed throughout the experiment. We selected three carly-classification models (LSTM-s (Ma et 2016), LSTM-m (Ma al.) (0016), and EARLIEST (Hartvigsen al. 2019h) and one lxed-length classifier (3DResNet (Hara et al.) 2017)), as baseline models. All the carly-classfficttion models share the same feature extractor that of the SPRT-TANDEM for fair comparison.
Hyperparameters of all the models are optimized with Optuna unless otherwise noted so that no models are disadvantaged by choice of hyperparameters. See Appendix for the search spaces and fixed final parameters. After fixing hyperparameters, experiments are repeated with different random seeds to obtain statistics. In each of the training runs, we evaluate the validation set after each training epoch and then save the weight parameters if the balanced accuracy the validation set updates the largest value. The last saved weights are used as the model that run. The model evaluation is performed the test dataset.
During the test stage the SPRT-TA SPRD-TANDEM, we used various values of the SPRT thresholds to obtain range of balanced accuracy-mest mean hitting time combinations to plot speed-accuragy tradeoff (SAT) curve. all the samples in a video are used up, the thresholds are collapsed to aj = ag = 0 to force decision.

---

Published as a conference paper at ICLR 2021
(81
NMNIST SAT curve
(b)
curve
(c)
SAT
57
98
TAADEN
onden
94
29.3
2nd
93
00
100
00.00
02.48
30
40
40.30
$9.7
20
30
60
40.00
Moan :iiin time (elfames)
Mean Nitting reframest
Mean hitting time (Ptrames)
1R trajectory, data: NMNIST, order: 10
(e)
NMNIST SAT curve
NMNIST SAT curve
20
92.0
tog-koethodd ralo
Balinged accurayy (5c
1.0
-3
99.4
99.3
-10
99.2
90
-20
10 Frame
30 Nitting (ifromes)
20
88
10
20
Nitting time (afromes)
Figure 3: Experimental results. (a-c) Speed-aceuracy tradcoff (SAT) curves three databases: NMNIST, UCF, SiW. Note that only representative results shown. Error bars show the standard etror the mean (SEM). (d) Example LLR trajectories calculated on the NMNIST database with the 10th-order SPRI-TANDEM, Red and blue trajectories represent odd and even digits. respectively. SAT curves the ablation comparing effect of the Lmultipie and the LELR. (f) SAT curves comparing the SPRT and Neyman-Peeae Pearson test (NPT) using the same Ist-order SPRIFTANDEM network trained on the NMNIST database.
To objectively compare all the models with various trial numbers, we conducted the two-way ANOVA followed by the Tukey-Kramer multi-comparison test compute statistical significance. For the details of the statistical test, see Appendix([ !]
We show our experimental results below. Due space limitations, only show representative
results. For the full details, see Appendix [ For our computing infrastructure, see Appendix K
Nosaic MNIST (Noise + mosaic MNIST) database. We introduce novel dataset, NMNIST, whose video is buried with noise at the first frame, and gradually denoised toward the last, 20th frame (see Appendix [ for example data). The motivation to create NMNIST instead of using a preexisting time-series database is as follows: for simple video databases such as Moving MNIST (MMNIST, (Srivastava et al., 2015)), each data sample contains too much information so that well-trained classifiers can correctly classify video only with one or two frames (see Appendix M for the results of the SPRT-TANDEM and LSTM-m on MMNIST).
We design a parity classification task, classifying 0 - 9 digits into odd even class. The training, validation, and test datasets contain 50,000, 10,000, and 10,000 videos with frames size 28 x 28 1 (gray scale). Each pixel value is divided by 127.5, before subtracted by 1. The feature extractor of the SPRT-TANDEM is ResNet- 10 (He et al. 2016a). with the final output reduced to 128 channels. The temporal integrator is a peephole-LSTM (Gers & Schmidhuber [0000] Hochreiter & Schmidhuberi 1997), with hidden layers of 128 units. The total numbers of trainable parameters on the feature extractor and temporal integrator are 6.9M and M. respectively. We train Oth, 1st, 2nd, 3rd, 4th, 5th, 10th, and 19th order SPRT-TANDEN networks. LSTM-s / LSTM-m and EARLIEST use peephole-LSTM and LSTM, respectively, both with hidden layers of 128 units. 3DResNet has 101 layers with 128 final output channels so that the total number of trainable parameters is in the same order (7.7M) as that of the SPRT-TANDEM.
Figure 3 and Table 1 shows representative results of the experiment. Figure 31 shows example LLR trajectories calculated with the 10th order SPRT-TANDEM. The SPRT-TANDEM outperforms other baseline algorithms by large margins at all mean hitting times. The best performing model is the 10th order TANDEM. which achieves statistically significantly higher balanced accuracy than the other algorithms (p-value < 0.001). Is the proposed algorithm's 's superiority because the SPRT- TANDEM successfully estimates the true LLR to approach asymptotic Bayes optimality? We discuss potential interpretations of the experimental results in the Appendix D
7

---

Published as a conference paper at ICLR 2021
Table I: Representative mean balanced accuracy (%) calculated on NMNIST. For the complete list including standard ertors, see Appendix
Mean hitting time
Model
3
4.37
10
15
19
19.66
#trials
Oth
92.43
97.47
98.85 08.82
99.03
99.20
99.37
99.50
99.50
99.50
99.50
100
SPRT-
1st
93.81
98.04
99.07
99.21
99.34
99.46
99.50
99.50
99,50
99.50
100
TANDEM
2nd
93.73
98.01
99.07
99.22
99.36
99.45
99.49
99.49
99.49
99.50
120
(propioed)
10th
93.77
98.02
99.09
99.23
99.37
99,47
99.51
99.51
99.51
99.51
139
19th (max)
94.25
98.26
99.12
99.23
99.37
99.46
99.50
99.50
99.50
99.50
100
L.TM-mm
88.74
93.89
96.15
97.62
98.35
99.19
99.42
99.48
1338
LSTM-s
89.01
94.13
96.47
97.91
98.43
99.28
99.45
99.52
120
EARLIEST
97.48
99.34
133
3DResNet
93.81
96.98
100
UCF101 action recognition database. To create a more challenging task, we selected two classes, handstand- pushsup and handstand walking from the 101 classes in the UCF database. At glimpse of one frame, the two classes are hard to distinguish. Thus, to correctly classify these classes, temporal information must be properly used. We resize each video's 's duration as multiples of 50 frames and sample every 50 frames with 25 frames of stride as one data. Training, validation, and test datasets contain 1026, 106, and 105 videos with frames of size 224 224 x 3, randomly cropped to 200 x 200 X 3 at training. The mean and variance of frame are normalized to zero and one, respectively. The feature extractor of the SPRT-TANDEM is ResNet-50 (He et al. 2016b), with the final output reduced to 64 channels. The temporal integrator is a peephole- LSTM, with hidden layers of 64 units. The total numbers of trainable parameters in the feature extractor and temporal integrator 26K and 33K, respectively. We train Oth, 1st, 2nd, 3rd, 5th, 10th, 19th, 24th, and 49th -9th-order SPRT-TANDEM. LSTM-s LSTM-m and EARLIEST use peephole-LSTM and LSTM, respectively, both with hidden layers of 64 units. 3DResNet has 50 layers with 64 final output channels so that the total number of trainable parameters (52K) is on the same order as that of the SPRT- TARTETANDE..
Figure p and Table 2 shows representative results of the experiment. The best performing model is the 10th order TANDEM, which achieves statistically significantly higher balanced accuracy than other models (p-value < 0.001). The superiority of the higher-order TANDEM indicates that a classifier needs to integrate longer temporal information in order to distinguish the two classes (also see Appendix D).
Table 2: Representative mean balanced accuracy (%) calculated on UCE: For the complete list including standard errors, see Appendix
Mean hitting time
Model
2.01
2.09
3
5
10
15
25
Atrials
Dth
92.92
92.94
93.00
93.38
94.06
200
SPRT-
1st
93.79
93.78
93.73
93.57
93.93
94.56
95.96
96.55
96.87
96.87
200
TANDEM
2nd
94.20
94.20
94.18
93.97
94.01
94.09
95.84
96.46
96.76
96.79
200
(proposed)
10th
94.37
94.37
94.31
94.29
94.77
95.10
96.18
96.85
97.12
97.25
256
49th (max)
94.52
94.51
94.52
94.40
94.36
94.51
96.20
97.03
96.96
96.72
200
LSTM-m
93.14
93.39
93.23
93,31
94.32
94.59
95.93
96.68
100
LSTM-s
90.87
92.36
92.82
93.17
93.75
94.23
95.93
96.45
101
EARLIEST
93,38
93,48
50
3DResNNe
64.42
90.08
100
Spoofing in the Wild (SiW) database. To test the SPRT-TANDEM in a more practical situation, we conducted experiments on the SiW database. We use sliding window of 50 frames-length and 25 frames-stride to sample data, which yields training, validation, and test datasets of 46,729, 4,968, and 43,878 videos of live or spoofing face. Each frame is resized 256 x 256 x pixels and randomly cropped to 244 x 244 x 3 at training. The mean and variance of a frame are normalized to zero and one, respectively. The feature extractor of the SPRT-TANDEN output reduced to 512 channels. The temporal integrator is a peephole-LSTy 512 units. The total number of trainable parameters in the feature extractor and temporal integrator is 3.7M and 2. MM, respectively. We train Oth, 1st, 2nd, 3rd, 5th, 10th, 19th, 24th, and 49th-order SPRT- TANDEM networks. LSTM-s LSTM-m and EARLIEST use peephole-LS' LSMM and LSTM, respectively, both with hidden layers of 512 units. 3DResNet has 101 layers with 512 final output channels so that the total number of trainable parameters (5.3M) is in the same order as that of the SPRT-TANDEM. Optuna is not applied due to the large database and network size.
ResNet- 152, with the final
with hidden layers of
8

---

Published as a conference paper at ICLR 2021
Figure 3 and Table 3 shows representative results of the experiment. The best performing model is the 10th order TANDEM, which achieves statistically significantly higher balanced accuracy than other models (p-value 0.001). The superiority of the lower-order TANDEM indicates that each video frame contains a high amount of information necessary for the classification, imposing less need collect large number of frames (also see Appendix D
Table Representative halanced accurncy (%) calculated on SIW. For the complete list including standard errors, Appendix
Mcan hitting time
Model
1.19
2
8.21
10
15
32,06
#trials
0th
99.78
99.82
99.9 85
99.87
99.87
99.87
99.87
99.87
99.87
99.87
100
SPRT-
99.81
99.84
99.86
99.89
112
TANDEM
2nd
99.82
99.86
99.88
99.89
99.89
99.89
99.90
99.90
99.90
99,90
110
(proposed)
10th
99.84
99.87
99.88
99.88
99.88
99.88
99.88
99.89
99.88
99.88
107
49th (max)
99.83
99.88
99.88
99.88
99.88
99.88
99.88
99.88
99,88
96.72
73
LSTM-m
99.77
99.80 99,80
99.80
99.83
99.85
99.88
63
LSTM-s EARLIEST
99.77
99.80
99.80
99.81
99.83
99.84
99.87
58
99.72
99.77
3DRecNet
98.82
98.97
98.56
Ablation study. To understand contributions of the LLLR and Lmuitipplr. to the SAT curve, we conduct an ablation study. The Ist-order SPRT-TANDEM is trained with LLLR only, mmuitiple only, and both LLLB and Lmultipler. The hyperparameters of the three models are independently optimized using Optuna (see Appendix Hp. The evaluated database and model are NMNIST and the Ist-order BER-TAANEMM, respectively. Figure shows the three SAT curves. The result shows that LLLB leads higher classification accuracy, whereas Tmuliiiplt enables faster classification. The best performance is obtained by using both LLLR and Lmuttiplet. We also confirmed this tendency with the 19th order SPRT-TANDEM, as shown Appendix N
SPRT Neyman-Pearson test. As discuss in Appendix A the Neyman-Person test is the optimal likelihood ratio test with a fixed number of samples. On the other hand, the SPRT takes flexible number of samples for earlier decisions. To experimentally test this prediction, we compare the SPRT-TANDEM and the corresponding Neyman-Pearson test. The Deeyann-Pearson test classifies the entire data into two classes at each number of frames, using the estimated LLRs with threshold O. Results support the theoretical prediction, as shown in Figure 3 the Neyman-Pearser test needs a larger number of samples than the SPRT-TANDEM.
CONCLUSION
We presented the SPRT-TANDEM, a novel algorithm making Wald's SPRT applicable to arbitrary data series without knowing the true L.R. Leveraging deep neural networks and the novel loss func- tion, LLLR, the SPRT-TANDEM minimizes the distance of the true LLR and the L.R sequentially estimated with the TANDEM formula, enabling simultancous optimization of speed and accuracy. Tested on the three publicly available databases, the SPRT-TANDEM achieves statistically signif- icantly higher accuracy over other existing algorithms with a smaller number of data points. The SPRT-TANDEN, enables a user to control the speed-accuras tradeoff without additional training, opening up various potential applications where either aechracy or high-speed required.
ACKNOWLEDGEMENTS
The authors thank anonymous reviewers for their careful reading improve the manuscript. We would also like to thank Hirofumi Nakayama and Yuka Fujii for insightful discussions. Special thanks Yuka for naming the proposed algorithm.
AUTHOR CONTRIBUTIONS
A.F.E. conceived the study. A.F.E. and T.M. constructed the theory, conducted the experiments, and wrote the paper. T. M. organized python codes to be ready for the release. K.S. and H.I. supervised the study.

---

Published as a conference paper at ICLR 2021
REFERENCES
T. Akiba, S. Sano, T. Yanase. T. Ohta, and M. Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '19, pp. (623-2631, New York, NY, USA, 2019. Association for Computing Machinery.
J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for hyper-parameter optimiza- tion. In J. TTylor,, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 24, pp. 2546-2554, Curran Asso- ciates, Inc., 2011. URL htttps://procettt 86e8f7al 3tw.b32cfd12555 7ww.112777722222 7b22 0TT.Ea1.55.7.12.66663666300-0000
neurips cc/ppaper/001/filee. .dd
S. Bickel, M. Brückner, and T. Scheffer. Discriminative learning for differing training and test distributions. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, pp. 81-88, New York, NY, USA, 2007. Association for Computing Machinery.
A. Cabri, G. Suchacka, S. Rovetta, and F. Masulli. Online web bot detection using sequential classification approach. In 2018 IEEE 20th International Conference on High Performance Computing and Communications: IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems (HPPCC/SurCCity/DSS) pp. 1536-1540, 2018.
V. Campos, B. Jou, X. G. Nieto, J. Torres, and S.-F. Chang. Skip mn: Learning to skip state updates in recurrent neural networks. In ICLR, 2018.
C. Chen, M. O. Gribble, J. Bartroff, S. M. Bay, and L. Goldstein. The Sequential Probability Ratio Test: An efficient alternative to exact binomial testing for Clean Water Act 303(d) evaluation. J. Environ. Manage., 192:89-93, May 2017.
K. Cheng and C. Chu. Semiparametric density estimation under two-sample density ratio model. Bernoulli, 10(4):583-604 08 2004.
D. K. Dennis, C. Pabbaraju, H. V. Simhadri, and P. Jain. Multiple instance learning for efficient sequential data classification resource-constraince devices. In Proceedings of the 32nd Interna- tional Conference on Neural Information Processing Systems, NIPS' 18, pp. 10976-10987, Red Hook, NY, USA, 2018. Curran Associates Inc.
R. S. Evans, K. G. Kuttler, K. J. Simpson, Howe, Crossno, K. Johnson, M. N. Schreiner, J. F. Lloyd, W. H. Tettelbach, R. K. Keddington, A. Tanner, C. Wilde, and T. P. Clemmer. Automated detection of physiologic deterioration hospitalized patients. J Am Med Inform Assoc, 22(2): 350-360, Mar 2015.
R. Fisher. Statistical methods for research workers. Edinburgh Oliver & Boyd, 1925.
A. Gers and J. Schmidhuber. Recurrent nets that time and count. Proceedings of the IFFE-INNS- ENNS International Joint Conference on Neural Networks. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millennium, 3:189-194 vol.3, 2000.
M. F. Ghalwash, V. Radosavljevic, and Z. Obradovic. Utilizing temporal patterns for estimating uncertainty in interpretable early decision making. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '44 pp. 402-411, New York, NY, USA, 2014. Association for Computing Machinery.
I. J. Good. Studies in the History of Probability and Statistics. XXXVII A. M. Turing's 's statistical work in World War II. Biometrika, 66(2):393 08 1979.
M. P. Griffin and J. Moorman. Toward the early diagnosis of neonatal sepsis and sepsis-like illness using novel heart rate analysis. Pediatrics, 107(1):97-104, Jan 2001.
K. Hara, H. Kataoka, and Y. Satoh. Learning spatio-temporal features with 3d residual networks for action recognition. 2017 IEEE International Conference on Computer Vision Workshops (ICCVW), pp. 316--3160, 2017.
10

---

Published as a conference paper at ICLR 2021
T. Hartvigsen, C. Sen, X. Kong, and E. Rundensteiner. Adaptive-halting policy network for early classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 19, pp. 101-110, New York, NY, USA, 2019. ACM.
T. Hartvigsen, C. Sen, X. Kong, and E. Rundensteiner. Recurrent halting chain for early multi-label classification. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp.
2020.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016a.
K. Hc, X. Zhang, Ren, and Sun. Identity mappings in deep residual networks. In Computer Vision ECCV 2016 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV, pp. 630-645, 2016b.
Hochreiter, Y. Bengio, P. Frasconi, and Schmidhuber. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies. In S. C. Kremer and J. F. Kolen (eds.), Field Guide to Dynamical Recurrent Neural Networks. IEEE Press, 2001.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Comput., ((8):7335-778) November 1997.
S. Kira, T. Yang, and M. N. Shadlen. A neural implementation of wald's sequential probability rato test. Neuron, 85(4))861-873 February 2015.
C. Y. Kramer. Extension of multiple range tests to group means with unequal numbers replications. Biometrics, 12(3)3307-310, 1956.
S. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Statist., 22(1):79-888 03 1951.
M. Kulldorff, R. L. Davis, M. Kolczakf, E. Lewis, T. Lieu, and R. Platt. maximized sequential probability ratio test for drug and vaccine safety surveillance. Sequential Analysis, 30(1):58-78, 2011.
Y. Liu, A. Jourabloo, and X. Liu. Learning deep models for face anti-spoofing: Binary or auxiliary supervision. In In Proceeding of IEEE Computer Vision and Pattern Recognition, Salt Lake City, UT, June 2018.
A. Luque, A. Carrasco, A. Martín, and A. de las Heras. The impact of class imbalance in classification performance metries based the binary confusion matrix. Pattern Recognition, 91:216 231, 2019.
S. Ma, L. Sigal, and Sclaroff. Learning activity progression Istms for activity detection and early detection. In 2016 IEEE Conference on Computer Vision and Patlern Recognition (CVPR), pp. 1942-1950, 2016.
U. Mori, A. Mendiburu, S. Dasgupta, and A. Lozano. Early classification of time series by simultaneously optimizing the accuracy and earliness. IEEE Transactions on Neural Networks and Learning Systems, 29( 29100:4569-44578 2018.
U. Mori, A. Mendiburu, F. J. Keogh, and J. A. Lozano. Reliable early classification of time series based on discriminating the classes over time. Data Mining and Knowledge Discovery, 31:233-263, 2016.
J. Qin. Inferences for case-control and semiparametric two-sample density ratio models. Biometrika, 85(3):619-630, 09 1998.
E. Simpson. Bayes at Bletchley Park. Significance, 7(2):76-80, June 2010.
K. Soomro, A. R. Zamir, and M. Shah. Ucf101: A dataset of 101 human actions classes from videos in the wild. CoRR, abs/1212.0402, 2012.
N. Srivastava, E. Mansimov, and R. Salakhudinov. Unsupervised learning video representations using LTMSs. In International conference on machine learning, pp. 843-852. PMLR, 2015.

---

Published as a conference paper at ICLR 2021
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation: A comprehensive review. RIMS Kokyuroku, pp. 10-31, 01 2010.
M. Sugiyama, T. Suzuki, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe. Direct impor- tance estimation for covariate shift adaptation. Annals of the Institute Statistical Mathematics, 60(4):699-746, 2008.
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012.
T. Suzuki, H. Kataoka, Y. Aoki, and Satoh. Anticipating traffic accidents with adaptive loss and large-scale incident db. 2018 IEEE/CVF Conference Computer Vision and Pottern Recognition, pp. 3521-3529, 2018.
A. Tartakovsky, 1. Nikiforov, and M. Basseville. Sequential Analysis: Hypothesis Testing and Changepoint Detection. Chapman & Hall/CRC, 1st edition, 2014.
Y. Tsuboi, Kashima, Hido, Bickel, and Sugiyama. Direct density ratio estimation for large-scale covariate shift adaptation. Journal of Information Processing,
2009. J. W. Tukey. Comparing individual means in the analysis of variance. Biometrics, 2:99-12 14, 1949.
A. Wald. Sequential tests of statistical hypotheses. Ann. Math. Statist., 16(2):117-186, 06 1945.
A. Wald and J. Wolfowitz. Optimum character of the sequential probability ratio test. Ann. Math. Statist., 19(3):326-339 09 1948.
A. Wald. Sequential Analysis. John Wiley and Sons, 1st edition, 1947.
Z. Xing, J. Pei, and P. S. Yu. Early prediction on time series; A nearest neighbor approach. In Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI'09, pp. 1297 1302, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc.
Z. Xing. Pei, and S. Yu. Early classification on time series, Knowledge and Information Systems, 31(1):105-127, April 2012.
12

---

Published as a conference paper at ICLR 2021
CONTENTS
Introduction
2
Related work
Proposed algorithm: SPRI-TANDEM
LLLR and multiplet cross-entropy loss
4.1
Loss for Log-L.keelhoood Ratio estimation (LLLR).
Multiplet cross-entropy loss,
Experiments and results
6
Conclusion
Theoretical aspects of the sequential probability ratio test
15
Preliminaries
15
A.2
Detinition and the tradeoff of false alarms and stopping time
................................
16
A.3
Peaason The Neyman- Pearson test and the SPRT
19
A.4
The Optimality of the SPRT
21
Supplementary review of the related work
23
Derivation of the TANDEM formula
25
Supplementary discussion
28
Loss for Log-Likelihood Ratio estimation (LLLR)
32
E.1
Density ratio estimation and KLIEP
32
The symmetrized KLIEP loss
33
The LLLR and density ratio estimation
34
Preparatory experiment testing the effectiveness of the LLLR
36
F
Probability density ratio estimation with the LLLR
38
Experimental settings
38
F22 Density estimation results
38
Multiplet cross-entropy loss
39
Hyperparameter optimization
40
H.1 Nosaic MNIST (NMNIST)
40
H22 UCFIOI
42
H.3 Siw
43
13

---

Published as a conference paper at ICLR 2021
Statistical test details
45
J Details of the experiments in Section S
47
Computing infrastructure
58
An example video of the Nosaic MNIST database.
59
M Supplementary experiment on Moving MNIST database
60
Supplementary ablation experiment
14

---

Published as a conference paper at ICLR 2021
APPENDIX
A THEORETICAL ASPECTS OF THE SEQUENTIAL PROBABILITY RATIO TEST
In this section, we review the mathematical background of the SPRT following the discussion in Tartakovsky al. (2014). First, we define the SPRT based the measure theory and introduce Stein's lemma, which assures the termination of the SPRT. To define the optimality of the SPRT, we introduce two performance metrics that measure the false alarm rate and the expected stopping time, and discuss their tradeoff - the SPRT solves it. Through this analysis, we utilize two important approximations, the asymptotic approximation, and the no-overshoot approximation, which play essential roles to simplify our analysis. The asymptotic approximation assumes the upper and lower thresholds are infinitely far away from the origin, being equivalent to making the most careful decision to reduce the error rate, at the expense of the stopping time. On the other hand, the no-ov no-overshoot approximation assumes that we can neglect the threshold overshoots of the likelihood ratio.
Next, we show the superiority of the SPRT to the Neyman-Pearson test, using a simple Gaussian model. The Neyman- Pearson test is known to be optimal in the two-hypothesis testing problem and is often compared with the SPRT. Finally, we introduce several types of optimal conditions of the SPRT.
A.1 PRELIMINARIES
Notations. Let (St, P) be a probability space; Q2 is a sample space, F C P is a sigma-algebra of f2 where PA denotes the power set of a set A, and P is a probability measure. Intuitively, Q represents the set of all the elementary events under consideration, e.g., Ω {all the possible elementary events such that "a human is walking through gate."), "j. F is defined as a set of the subsets of Ω2 and stands for all the possible combinations of the elementary events; e.g., F { ("Akinori is walking through the gate at the speed of 80 m/min." "Taiki is walking through the gate at the speed 77 m/min," " or "Nothing happened.") "} P: F + [0, 1] a probability measure, a function that is normalized and countably additive; i.c., P measures the probability that the event A E F occurs. A random variable X is defined as the measurable function from Ω to a measurable space, practically Rd (d E N); e.g., if w( !?) is "Taiki is walking through the gate with a big smile," 'hen X(w) may be 100 frames of the color images with 128x 128 pixels (d = 128 x 128 x 100), i.e., a video recorded with camera attached at the top of the gate. The probability that random variable X takes a set of values S E IRd is defined as P(X E S) == P( (S)). where X is the preimage of X. By definition of the measurable function, X (S) E F for all S E Rd Let (Filezo be filtration. By definition, (FFe)e2 is a non-decreasing sequence of sub-sigma-algebrnt for all and such that 0 < f. Each element of filtration can be interpreted the available information at a given point f. (2,F, (Fi)e2o. P) is called a filtered probability space.
of F.i.e, Fs F, CF
As in the main manuscript, let X == {x:1)] be a sequential data point sampled from the density p. where T E NU (oo). For each / E (T). (1) E Rd,,, where d, E N is the dimensionality I (x(()), where ʃ is the density of (:()),
[i=1
of the input data. In the i.i.d. case, ((X().)) For each time-series data (ITT), the associated label y takes the value or O; we focus the binary classification, or equivalently the two-hypothesis testing throughout this paper. When y is a class label, ((TT()))) ()) is the likelihood density function. Note that (1,7) with label y is sampled according to density p(x((17))))) ly).
Our goal is, given a sequence (1.2), to identify which one the two densities p1 or Po the sequence (1.77) is sampled from; formally, to test two hypotheses H1 : y 1 and Ho : =y=00 given X (1.T), The decision function or test of a stochastic process (1.T) is denoted by d(X(1.T) : We can identify this definition with, for each realization of ( d : Rd=xT + {1,0), i.e.. ( + y. where y E (1,0). Thus we write d instead of d(x((1T)) for simplicity. The stopping time of X(I.T) with respect to filtration (Fi) is defined
(1, 0).
== T(X(L.)) : R2o such that {w E R|](w) < {) E F,, Accordingly, for fixed T E {oo} and E [1, {d = means the of time-series data such that the decision function accepts the hypothesis H, with finite stopping time; more specifically, {d y} {w ()d(x = y T(x((.7) (w)) < oo).
The decision rule 8 is defined as the doublet (d, T). Let AT = A(X(1.T) = p(xa.)) y=l)) and
p(x 0=
15

---

Published as a conference paper at ICLR 2021
AT log Ar be the likelihood ratio and the log-likelihood ratio of x(I.). In the ii.d
AT T p(a(t) y=1)
[ 2(1), where p(X(,))))) = II p(x (y E {1,03) and
p(a(t) y=0)
Z = p(a(t) ly=1)
p(ati) (y=0)
A.2 DEFINITION AND THE TRADEOFF OF FALSE ALARMS AND STOPPING TIME
Let us overview the theoretical structure of the SPRT. In the following, we assume that the time-series data points are i.i.d. until otherwise stated.
Definition of the SPRT. The sequential probability ratio test (SPRT), denoted by d* defined as the doublet of the decision function and the stopping time.
Definition A.1. Sequential probability ratio test (SPRT)
Let ag - log Ao 2 0 and a1 log A1 2 be (the absolute values of) a lower and an upper threshold respectively.
8 ,"),
(11)
d' d'((i))))
1 if S -40
= [1 -11
if Ar- 2 a1
(12)
7- = 2 0/r & (-ao; 01)]
(13)
Note that d' and r" implicitly depend on a stochastic process (I.T), In general, a doublet of a terminal decision function and stopping time is called decision rule hypothesis test.
Termination. The i.i.T.SPPTT terminates with probability and all the moments of the stopping time are finite, provided that the two hypotheses are distinguishable:
Lemma A.1. Stein's 's lemma
Let F,,,F P) be probability space and (Y be a sequence of i..d. random variables under P. Define т == inf[T 2 1 y(t) & (-a0, a.)). If P(Y # 1, the stopping time T is exponentially bounded; ie., there exist constants C > O and 0 < < such that P(r > T) S Cp for all T 1. Thereefore, P(r < 00) and E, 7k oc for all k 0.
Two performance metrics. Considering the two-hypothesis testing, we employ two kinds of performance metrics to evaluate the efficiency of decision rules from complementary points of view: the false alarm rate and the stopping time. The first kind of metries the operation characteristic. denoted by ((5, y), and its related metrics. The operation characteristic is the probability of the decision being 0 when the true label is = y; formally.
Definition A.2. Operation characteristic
The operation characteristic is the probability of accepting the hypothesis Ho function of y::
3(ō.v) P(d= 0ly)
(14)
Using the operation characteristic, define four statistical measures based on the confusion matrix; namely, False Positive Rate (FPR), False Negative Rate (FNR), True Negative Rate (TNR), and True Positive Rate (TPR).
FPR: (5 = -65, P(d= = 1ly = 0)
(15)
FNR: an (0) 3(,, = P(d = 0ly 1)
(16)
TNR: ((6, 0) =1-00(8)
P(d 1
(17)
TPR: 1 - = = 1 1
0000 Pdy=0ly=
(18)
Note that balanced accuracy is denoted by (1+,)(6,0) 0) -3(6, 1))/2 according to this notation. The second kind of metrics is the mean hitting time, and defined as the expected stopping time of the decision rule:
16

---

Published as a conference paper at ICLR 2021
Definition A.3. Mean hitting time The mean hitting time is the expected number of time-series data points that are necessary for testing a hypothesis when the true parameter value is y: Eyy = Sa (-l() The mean hitting time is also referred as the expected sample size of the average sample number.
There is a tradeoff between the false alarm rate and the mean hitting time. For example, the quickness may be sacrificed, if we use decision rule ō that makes careful decisions, i.e., with the false alarm rate 1 - 3 0) less than some small constant, On the other hand, if we use ó that makes quick decisions, then ò may make careless decisions, i.e., raise lots of false alarms because the amount of evidences is insufficient. At the end of this section, we show that the SPRT is optimal in the sense of this tradeoff.
The tradcoff of false alarms and stopping times for both i.i.d. and non-i..d. We formulate the tradeoff of the false alarm rate and the stopping time. We can derive the fundamental relation of the threshold to the operation characteristic in both i.id. and non-i.i.d cases (Tartakovsky et al. (2014)):
{ af S e (1 a7) oz) ag S (1-aa)))))
(19)
where we defined a= the false alarm rate and the stopping time. For example, the thresholds ay (y {1,0)) increase, the false alarm rate and the false rejection rate decrease, as (19) suggests, but the stopping time is likely to be larger, because more observations are needed to accumulate log-likelihood ratios to hit the larger thresholds.
:= ayy55) ) (y E (1, These inequalities essentially represent the tradeoff of
The asymptotic approximation and the no-overshoot approximation. Equation 19 is an exam- ple of the tradeoff of the false alarm rate and the stopping time; further, we can derive another example in terms of the mean hitting time. Before that, we introduce two types of approximations that simplify our analysis.
The first one is the no-overshoot approximation. It assumes to ignore the threshold overshoots of the log-likelihood ratio at the decision time. This approximation ratio of single frame is sufficiently small compared to the gap of the thresholds, at least around the decision time. On the other hand, the second one is the asymptotic approximation, which assumes an: 01 - co, being equivalent sufficiently low false alarm rates and false rejection rates the expense of the stopping time. These approximations drastically facilitate the theoretical analysis; in fact, the no-overshoot approximation alters (19) as follows (see Tartakovsky al. (2014)):
valid when the log-likelihood
aj ~ e 40 (1 - -6);
a 2 a1 - (1-
(20)
which is equivalent to
e00
ai 1
aj e -
aj e00
(21)
1 - aj
0g R loog
a1 R log
(22)
1 ag
aj
E _1-1
01
(*(1)
(23)
0g
6-
co0
where (*()) 3(8" v) (y E 0)). Further assuming the asymptotic approximation. we obtain
aj ~ 01
aj
00
(24)
Therefore, as the threshold gap increases, the false alarm rate and the false rejection rate decrease exponentially, while the decision making becomes slow, as is shown in the following.
Mean hitting time without overshoots. Let I, := E,, u (y E (1,03) be the Kulbbeck-Leibler divergence of fa and fu- Iy is larger if the two densities are more distinguishable. Note that I, 2: 0 since (2(() 0) $ 1, and thus the mean hitting times of the SPRT without overshoots
17

---

Published as a conference paper at ICLR 2021
expressed
1
1-ai]
1 1 ai
00
E1
(1 ai) log(
aj
log(
(25)
Ti
Oi
0i
1
1 1 1
- aj
Eo[r"]
(1- ag) log(
ag
log(
(26)
To
ai
ag
In Tartakovsky al. 2014). Introducing the function
((2,)) y) = (1 - x) log( = - x log(
1 y
(27)
2
can simplify 25 26
E1 [1[T"] = (aai, añ)
(28)
1 Eo Bo[T"| (aa aj).
(29)
(5 26 shows the tradeoff as we mentioned above: the mean hitting time positive (negative) data diverges if we are set the false alarm (rejection) rate to be zero.
The tradeoff' with overshoots. Introducing the overshoots explicitly, we can obtain the equality, instead of the inequality such as (19), that connects the the error rates and the thresholds. We first define the overshoots of the thresholds ag and at the stopping time as
Ki (4o, a1) == A-- 01
m 2 2a) on(), -0o}-
(30)
Ko an) == (A,, + oo)
(31)
We further define the expectation of the exponentiated overshoots as
el (4g, a1) == E -i ((o.aa)) }7, 2 a1] (o a1) == iole- (000 PAp S -ool Then we can relate the thresholds to the error rates (without the no-overshoots approximation, Tartakovsky (1991)):
(32)
(33)
aj Cap, a1 "0 e1 (ag, an )eo(a,,,)))) a1) aj
Co(ag, 01)e - ei (ao, a1) (1)ev((0,01) (34)
001+a0 e1 (ag, a1 (r)eo(ao, a1)
e tap e1 (ag, a1)co(ao. 01)
To obtain more specific dependence on the thresholds ay (y (1,
adopt the asymptotic
approximation. Let To(an) and Ti (ai) ) be the one-sided stopping times, i.e., To(ao) == inf >
1|Ar < - and Ti (a1) == inf[T 1|Ar 2 a.). We then define the associated overshoots
Ra (a1) Ar. ai onfTi co).
(35)
Ro (ao) := (Dr, + as) (n oo}.
(36)
According to Lotov 1988), we can show that
00 Si
Spe S05 caotas Co50
of
(37)
cagto Çi
under the asymptotic approximation. Note that
Sy = lim Ruy] (y E (1,0))
(38)
have no dependence on the thresholds ay (y (1,0)) Therefore we have obtained more precise dependence of the error rates on the thresholds than (24):
Theorem A.1. The Asymptotic tradeoff with overshoots Assume that Ly < 00 oy (1.03).
Let by be given in 38 Then
0 Gi (1 o(1)),
of = Soe
-0 Goe
+ o(1)) (an, a 00).
(39)
18

---

Published as a conference paper at ICLR 2021
Mean hitting time with overshoots
A more general form of the mean hitting time is provided in Tartakovsky (1991). We can show that
(1 - oi) (a1 + [M( =
=T1) ==(xxal===TT)
aj ao + E, [NOlTT = [=ool===Tool) =Tul)
E1 r
(40)
I1
ab) (1-a5)
(ou + Bu "nooT = TT) ag [a + Eo EK/Ks Til)
Egr"
(41)
Lo
The mean hitting times (40 41 explicitly depend on the overshoots, compared with (25 26 Let
Xy : lim [ylRy] (y E {1,0))
(42)
act0000
be the limiting average overshoots in the one-sided tests. Note that Xy have no dependence dy (y E (1,0}). The asymptotic mean hitting times with overshoots are
1 1 = T. (01 +o1), Eor
(a0 + xo) +o(1) (age - O, 01 - 0) (43)
To
As expressed in Tartakovsky et al. (2014). Therefore, they have an asymptotically linear dependence on the thresholds.
A.3 THE NEYMAN-PEARSON TEST AND THE SPRT
So far, we have discussed the tradeoff of the false alarm rate and the mean hitting time and several properties of the operation characteristic and the mean hitting time. Next, we compare the SPRT with the (eyman--Parson test, which is well-know to be optimal in the classification of time-series with fixed sample lengths; in contrast, the SPRT is optimal in the early classification time-series with indefinite sample lengths,
show in the next section.
We show that the Neyman-Peanee Pearson test optimal in the two-hypothesis testing problem or the binary classification of time-series. Nevertheless, show that in the i..d. Gaussian model, the SPRT terminates earlier than the Neyman-Pearson test despite the same error rates.
Preliminaries. Before defining the Deyman-Pearson test, we specify what the "best" test should be. There are three criteria, namely the most powerful test, Bayes test, and minimax test. To explain them in detail, we have to define the size and the power of the test. The significance level, or simply the size of test d is defined as!
a = P(d 1ly = 0).
(44)
It is also known as the false positive rate, the false alarm rate, or the false acceptance rate of the test. On the other hand, the power of the test d is given by
1 B P(d 1ly = 1).
(45)
y is also called the true positive rate, the true acceptance rate. the recall, or the sensitivity. B is known as the false negative rate or the false rejection rate.
Now, we can define the three criteria mentioned above.
Definition A.4. Most powerful test
The most powerful test of significance level a(> 0) is defined as the test that for every other test d' of significance level o, the power of d is greater than or equal to that of d':
P(d 1ly = 1) 2 P(d' = =)
(46)
Definition A.5. Bayes test Let mo := P(y 0) and ग. P(y = 1) 1)= = 1 To be the prior probabilities of hypotheses Ho and H1, and a(d) be the average probability of error:
ā(d) Σ T:ar(d),
(47)
1=1.
Pdd 1/y 0) is short for P([w E ()((x0.)))))) 1718 and is equivalent P "x0.)))p(x(.77)) (d) = 1] (i.e., the probability of the decision being 1, where x0.T is sam- pled from the density p( (1.T) 1)).
19

---

Published as a conference paper at ICLR 2021
where (,(d) == Pdd & fly i) is the false negative rate of the class i E {1,0}, A Bayes test, denoted by d", for the priors defined as the test that minimizes the average probability of error:
d == argin
(48)
where the infinum is taken over all sxed-sample size decision rules.
Definition A.6. Minimax test
Let Ormase (d) be the maximum error probability:
O'max (d) max {a:(d)}
(49)
:E(1,0}
A minimax test, denoted by d is defined as the test that minimizes the maximum error probability:
a'max (anx(dd)) inf (amax (d))
(50)
where the infimum is taken all fixed-sample- tests.
Note that a saeed--aple-szee decision rule or non-sequential rule is the decision rule with fixed stopping time T = N with probability one.
Definition and the optimality of the Neyman-Pearson test. Based on the above notions, we state the definition and the optimality of the Neyman-Pearson Pearson test. We the most powerful test for the two-hypothesis testing problem the Neyman-Pearee Pearson test; the theorem below also the definition of the PeymannPearson test.
Theorem A.2. Neyman-Pearson lemma Consider the two-hypothesis testing problem, i.e., the problem of testing two hypotheses Ho P P= Po and H1 PI, where Po and P1 are two probability distributions with densities pa and pı with respect to some probubility measure. The most powerful test is given by
=(0 =
(((()))) h(a)
NP (X
(51)
otherwise,
(((x0) where A(X(111)) = X is the likelihood ratio and the threshold h((a) is defined as
= Eg NP (X a ao(d>P) (= (X(L)) = =
(52)
to ensure for the false positive rate to be the user-defined value <<>> 0).
NP is referred to as the Neyman-Pearson test and also optimal with respect to the Bayes and minimax criteria:
Theorem A.3. Neyman-Pearson test is Bayes optimal Consider the two-hypothesis testing problem.
Given a prior distribution (i E (1,0)) the Bayes test d3, which minimizes the average error probability a(d) = (d) + miai (d), given by
d ( = {o (IFA(X(LTT)) 2 To/T))
(53)
(otherwise).
That is, the Bayesian test is given by the Veyman-Pearson test with the threshold To/T
Theorem A.4. Neyman-Pearson test is minimax optimal Consider the two-hypothesis testing prob- lem. the minimax test M, which minimizes the maximal error probability ( = max {d;(d))
eE(1,0)
is the Neyman-Pearson test with the threshold such that oeg (d =xx1dd )).
The proofs given in Borovkov (1998) and Lehmann & Romano 2006
20

---

Published as a conference paper at ICLR 2021
The SPRT is more efficient. We have shown that the Seyman-Pearson test is optimal in the two- hypothesis testing problem, in the sense that the Secmann-Pearsee test is the most powerful, Bayes, and minimax test; nevertheless, test even when these two show the same error rate.
show that the SPRT terminates faster than the Neyman-Pearson
Consider the two-hypothesis testing problem for the i.i.d. Gaussian model:
H; : y = yi (d E (1,0)) x(0) = y y g(t)
(t 2 1,y
(54)
e NO od) (o 2 0),
where (0,
(0, o²) denotes the Gaussian distribution with mean 0 and variance a², The Neyman-Pearson test has the form
dP P (x(1))(ao,ai))) =f
(if Ap(rrom)) 2 h(ag, a1)) (otherwise).
(55)
The sequence length = n(ag, a1) and the threshold h = f((ao, 01) are defined so as for the false positie rate and the false negative rate to equal to ag and a respectively; i.e.
P(A, 2 hly yo) 00,
(56)
P(A, < hly = y1) = aq
(57)
We can solve them for the i.i.d. Gaussian model (Tartakovsky al. (2014). To see the efficiency of the SPRT to the Sayman--Person test, we define
E E yy = yol
Eo(ag: a1) =
(58)
n( 01)
& E, 0n) = |F[T * by = yn] n(ag, a1)
(59)
Assuming the overshoots are negligible, we obtain the following asymptotic efficiency (Tartakovsky et al. (2014)):
1 Ey 01) a2)= (y E (1,0)).
lim max m am } -
(60)
In other words, under the no-overshoot and the asymptotic assumptions, the SPRT terminates four times earlier than the Neyman- Pearson test in expectation, despite the same false positive and negative
rates.
A.4 THE OPTIMALITY OF THE SPRT
Optimality in i.i.d. cases. The theorem below shows that the SPRT minimizes the expected hitting times in the class of decision rules that have bounded false positive and negative rates. Consider the two-hypothesis testing problem. We define the class of decision rules
C'ao, a1) = {8 s.t. P(d = 1|Ho) < oo, P(d 01) < a H[]]Ho]| < co, E[T[/1 < oc}. (61)
Then the optimality theorem states:
Theorem A.5. LLD. Optimality (Tartakovsky et al. (2014) Let the time-series data points (1), t = 1,2, be i.i.d. with density fo under Ho and with density under H1. where fo # fr. Let 0g > 0 and ai > 0 be fixed constants such that on + an < 1. If the thresholds -a, and 01 satisfies
ag (ao, a1) on and a (ao, a1) on, then the SPRT 8* (d' ,T") satisfies
inf (d((.r)
B|r|Ho] B[7*|Ho] and
inf (d(o))))C((n)
Blr|Hi] B(T (62)
A similar optimality holds for continuous-time processes (Irle & Schmitz (1984). Therefore the SPRT terminates at the earliest stopping time in expectation any other decision rules achieving the same less errrr rates the SPRT is optimal.
Theorem A.5 tells us that given defr-ed thresholds, the SPRT attains the optimal mean hitting time. Also, remember that the thresholds determine the error rates (e.g.. Equation (24). Therefore, the SPRT can minimize the required number of samples and achieve the desired upper-bounds of false positive and false negative rates.
21

---

Published as a conference paper at ICLR 2021
Asymptotic optimality in general non-iid. cases. In most of the discussion above, have assumed the time-series samples are i..d. For general non-i..d. distributions, we have the asymptotic optimality; i.e. the SPRT asymptotically minimizes the moments of the stopping time distribution (Tartakovsky et al. 2014)).
Before stating the theorem, first define a type of convergence of random variables.
Definition A.7. r-quick convergence Let (-(t) J:21 be a stochastic process. Let T((fa"))21)) be the last entry time of the stochastic process {a he2 in the region (c, 20) -t), ie.
h22
Te(fx(0)) h211) = sup s.t. |x:00 > c).
sup = 0.
(63)
121
Then, we say that the stochastic process (x(1) h22 converges to zero r-quickly, or
(1
ququcklyy, 0,
(64)
for some > O, if
[[(TT((( 122 o0 for every 0.
(65)
r-quick convergence ensures that the last entry time in the large-deviation region (T((f=()))2))
finite almost surely. The asymptotic optimality theorem is:
Theorem A.6. Non-ii.d. asymptotic optimality If there exist positive constants Lo and Iı and an increasing non-negative function (t) such that
d
Pi quicklyickyy In and
Xt
Po-r-quiclly -To
(66)
(1)
10000
(())
where Xa is defined in section A.1 then
oc (i for any finite and a1.
(67)
Moreover, if the thresholds ag and a₁ are chosen to satisfy 19.. ao + log(1/ai). and 01 +
log(1/aç) (a, - so), then all 0 m <.
inf 6EC(ap,an)
[B|r" vil} - 1y = v1l - 0
(68)
inf SEC(op.01)
[Bir = yol} - [E[([T]]")) = yol -
(69)
as max(ag, a1] > with log / log 1ogai| - where E oc)
22

---

Published as a conference paper at ICLR 2021
B SUPPLEMENTARY REVIEW OF THE RELATED WORK
Primate's 's decision making and parietal cortical neurons. The process of decision making in- volves multiple steps, such as evidence accumulation, reward prediction, risk evaluation, and action selection. We give brief overview regarding mainly to neural activities of primate parietal lobe and their relationship to the evidence accumulation, instead of providing a comprehensive review of the decision making literature. Interested readers may refer to review articles, such as Doya (2008):
Gallivan et al. (2018); Gold & Shadlen (2007).
In order to study neural correlates of decision making, Roitman & Shadlen (2002) used a random dot motion (RDM) task on non-human primates. They found that the neurons in the cortical area lateral intraparietal cortex, or LIP, gradually accumulated sensory evidence represented as increasing firing rate, toward one of the two thresholds corresponding to the two-alternative choices. Moreover, while a steeper increase of firing rates leads to an early decision of the animal, the final firing rates at the decision time is almost constant regardless of reaction time. Thus, at least in population-level LIP neurons are representing information very similar to that of the LLR in the SPRT algorithm (It is under active discussion whether the ramping activity is seen only in averaged population firing rate or both in population and single neuron level. See Latimer et al.] (2015); [Shadlen et al. (2016)) But also see Okazawa al. (2021) for recent finding that evidence accumulation is represented in high-dimensional manifold of neural population. In any case, LIP neurons seem to represent accumulated evidence as their activity patterns.
To test whether the ramping activity is explained by Wald's SPRT, Kira et al. (2015) used visual stimuli associated with reward likelihood: each stimulus indicates the answer of the binary choice task with a certain probability (e.g., if stimulus ''' is presented, choice I is the correct answer with 30% probability). ). LIP neurons' activities in response to these randomly presented stimuli are proportional to LLR calculated from the associated likelihood of the stimuli, letting authors concluded that the activity of LIP neurons are best explained by SPRT than other alternative models. It remains unclear, however, what algorithm is used in the brain when stimuli are not randomly presented but temporary dependent.
More complex decision making involving risk evaluation such "delayed, large reward V.S. imme- diate, small reward" is thought to be guided by other regions including orbitofrontal cortex, dorsal striatum dorsal prefrontal cortex (McClure et al. (2004); Rudebeek et al. (2006); Tanaka et al. (2004)).
Application SPRT. Ever since Wald's formulation, the sequential hypothesis testing was applied to study decision making and its reaction time (Stone (1960); Edwards (965): Ashby (1983), ). Several extensions more general problem settings were also proposed. In order to test more than two hypotheses, mqulti-hypothestt SPRT (MSPRT) was introduced (Armitage 1950); Baum & Veeravalli
(1994), ) and shown to be asymptotically optimal (Dragalin et al. (1999 2000); Veeravalli & Baum (9955) ). The SPRT was also generalized for non-i.i.d. data (Lai theoretically shown to be asymptotically optimal, given the known LLR (Dragalin et al. (1999]2000)
1981 Tartakovsky (tsssskyy((999)) (1999), and
Tartakovsky et al. (2014) provided a comprehensive review of these theoretical analyses, a part of whose reasoning we also follow to show optimality in Appendix The SPRT, and closely related, generalized LLR test, applied to solve several problems includes drug safety surveillance (Kulldorff jet al. (001)) exoplanet detection (Hu et al. (2019), and the LLR test out of weak classifiers (WaldBoost, Sochman & Matas (2005), to name a few. On an A/B test, Johari et al. (2017) tackled an important problem inflating error rates at the sequential hypothesis testing. Ju et al. (0019)
proposed inputed Girshick test to determine better variant.
Time-series classification. Here, we use the term "Time-series" interchangeably to mention both continuous data or discrete data such as video frames.
One of the traditional approaches to univariate or multivariate time series classification is distance- based methods, such as dynamic time warping (Bagnall (2014); Jeong et al. (2011) Kate (2015)) or k-nearest neighbors (Dau et al. (2018); Wei & Keogh)(2006); (2006); Yang & Shahabi (2007) ). More recently, Collective Of Transformation- baased based Ensembles (COTE) and its variant, COTE with Hierarchical
Vote system (HIVE-COTE) showed high classification performance at the expense of their high
computational cost (Bagnall et al. (2015): Lines et al. (2016)). Word Extraction for time series
23

---

Published as a conference paper at ICLR 2021
classification (WEASEL) and its variant, WEASEL MUSE take bag-of-pattens approach utilize carefully designed feature vectors (Schäfer & Leser (217)).
The advent of deep learning allows researchers to classify not only univariate/mmllivatittc data. but also large-size, video data using convolutional neural networks (Hara et al. (2017); Carrreira & Zisserman (017);; Karim al. (2018): Wang al. (2017)) Thanks to the increasing computation power and memory of modern processing units, each video data in a minibatch are designed to be sufficiently long in the time domain such that class signature can be contained. Video length of the training, validation, and test data are often assumed to be fixed; however, ensuring sufficient length for all data may compromise the classification speed (i.e., number of samples that used for classification). We extensively test this issue in Section 5
24

---

Published as a conference paper at ICLR 2021
C DERIVATION OF THE TANDEM FORMULA
The derivations of the important formulas in Section 3 are provided below.
The Oth order (i.i.d.) TANDEM formula. We use the following probability ratio to identify if the input sequence {x(*) J==1 derived from either hypothesis Hi 1 or Ho y 0.
p(= x (1) y 1) p(x(1), 1y
(70)
We can rewrite with the posterior. First, by repeatedly using the Bayes rule, we obtain
p(x(1), x(2) ...., x..,, ((t)ly)
=p(c 21 .... x 11 v)p(x(1' (t-1) x(1-2) 11)
-p(a!"/o(tt)) ,1 ,... x 1) (1)
p(xll-11) (((-)) x (1-3) (2), y))p(z(1-2) (l(-3) x (1)) ,))
= =p(x:0 1 (1) (1-1)) ,),,,,,1,3)) (1)) _()),))).))))))))))))) .y) . p...p(/ y) (71)
(1033)
We use this formula hereafter, Let us assume that the process {z 1 is conditionally-inddeenndennl and identically distributed (hereafter simply noted as i.i.d.), namely
((x(1), (2))
(1)) = II (g),
(72)
which yields the following LLR representation ("O-th order Markov process"): p(x10)2 x(1-2) (1)), .) p(z v))
(73)
Then
p(x(1) ,,!22 (,.,,)))))))
((2 (1)p((((-1))))))) plx 1z)p(a(1))))
II [(a(
)p(x
II
p(u)
Hence
((= x(2ه .... (10) 1y 1)
p(y 1|2()1)
ppyy ppy==0 0) t
(74)
(1z(1), x(अ) .... ( yyا 0)
ply 0|z(,)]
ply ply= = 1)
or
(1x 22(2) ..... 101 by =1) ((x(1), x((2 2(1) by 0)
plu 1|r((1) Σ log
Alog p(v 1) p(y = 0)
log
(75)
ply = 0 0,)()))
The Ist-order TANDEM formula. So far, we have utilized the i.i.d. assumption 73 or 72 let us derive the probability ratio of the first-order Markov process, which assumes
Now
(1) (1--)) (1-2) ae (1) v) pxx((() (1111)))
(76)
25

---

Published as a conference paper at ICLR 2021
Applying 776 to 71,, we obtain
p(x!1, xx(3) ...., 1y)
p(o!0) (x((=1) (o ,y) p(o0) ())(((()))) (w)
pl إاا w)س p p(zx1)11) (n)
p(ul x: )p( (5)) _1) p(ylz(()) pp(x(1))
p(-(5-1), y
p(y)
p(yloo()) - )p( (5), 11
ply (r (p(at1))((( )p(x!1)
II ==2
ply plyl [ )p 1))
p(v)
for 2 2. Hence
((x((1), (2)
y... (1) 1)
p(x(1), 1) (2) x21 0)
t pyy 1 (,,(e) (11-1111
Tpl 01))6-1))
ply = 0)
II
(78)
ply = (+))()) , x()-1))
p(y = 1 [x(
p(y = 1)
2=2
or
((((11) (2)) x( 11 1) p(x!11, (2)) ...y (1) |/ = 0)
log
ply 1 1|x(,0/ (((-1)) 1))
ply 1| p(y = 0|
p(y 11 ply = 0)
1)
Σ log
log
log
(79)
pyy = 0 0f2(1), x (((-1))
For t = 1 and
= 2, the natural extensions are
p(xx(1) by =1)
1)
log p(u 1|r(()) log ppy- 1) ply 0)
log
p(xx1)) by = 0)
p(y ()r(
(80)
((x(1), 22(2) by = 1) p(x(1), 2(2)|yy = 0)
p(y 1 1|r(11, xx(21)
p(y p(y=1) = 1)
log
= log
log
p(y = 0 (2) (())
p(y = 0)
The N-th order TANDEM formula. Finally we extend the 1st order TANDEM formula so that it can calculate the general N-th order log-likelihood ratio. The N-th order Markov process is defined as
p(x(1) (t-1) (t-2))
2) ,..,, x..,,(0), v) po0()1/((t1), 10 ,),))
(81)
Therefore, for t 2 N +
()x(1), (2)2) ...., x (1) ly)
=(x (0-11) (t-N) w))(() 2))(z((11))) (x (c- N11 8) ((2(2) ,1)p((())1)
II s=N+1
() (( (N- -..,,(()))) (1))g)
((y)x(()) x (p(2(())
Lll ((y) x(() (x(x (N) ..., (11)
II s=N+1
p(a(0-1) Ni,y)
p(y)
p()
pp
..... [(
p(y]x((), ..... x 11) (p(x(N)) ..... 2(1)
((y]z(o-1) xl0 (p(((0 --
x(o-
p(y)
s=N+1
(82)
Hence
(1) (2) ..., x11) 1)
p(x(1), .,., x11) 0) =
II p = (1) N))
"(y (--1) (
ply = 0)
ply = 1) (83)
++N+1 [u = (c) NJ)
p(y ([ x[,,
+2
26

---

Published as a conference paper at ICLR 2021
p(x(1) x(2) ...., x x11) / = 1)
log
p(x(1), x12) .... x16) |y 0)
ply 1 (6) ,00 (1)
ply 1| (|z( 1] x No)
Σ log
log
p(y 0 (+))
ply 0|z(5-1) .... x p(x~NN)) NY)
==N+1
N+
p(y 1)
ply 0) )
log
(84)
Fort t < N + 2, we obtain
p(z(1) (2) .... x0 = 1)
log
p(x(1, xx(2) ..., 1100y = 0)
ply 1|x(111 x012 _..., (())
ply 1) p(u = 0)
=log
log
(85)
p(y
0f,r(1), xx(2) ,.,,,(()))
27

---

Published as a conference paper at ICLR 2021
D SUPPLEMENTARY DISCUSSION
Why is the SPRI-TANDEM superior to other baselines? The potential drawbacks common to the LSTM-s/m and EARLIEST is that they incorporate long temporal correlation: may lead to (1) the class signature length problem and (2) vanishing gradient problem. as we described in Section 3. (1) If class signature significantly shorter than the correlation length in consideration, uninformative data samples are included in calculating the log-likelihood ratio, resulting in a late or wrong decision. (2) long correlations require calculating a long-range of backpropagation, prone to the vanishing gradient problem.
An LSTM-s/m-specific drawback is similar to that of Sryman-Pearsonn test, in the sense that fixes the number of samples before performance evaluations. On the other hand, the SPRT, and the SPRT-TANDEM, classify various lengths of samples: thus, the SPRT-TANDEM can achieve a smaller sampling number with high accuracy average. Another potential drawback of s/m is that their loss function explicitly imposes monotonicity to the scores. While the monotonicity is advantageous for quick decisions, it may sacrifice flexibility: the LSTM-s/m can hardly change its mind during a classification.
EARLIEST, the Siinforceeent-eeamiig based classifier, decides the various length of samples. A potential EARLIEST- -ppcccccccfficc drawback is that deep reinforcement learning is known to be unstable (Nikishin al. (0188: Kumar al.).
How optimal is the SPRI-TANDEM? In practice, it is difficult to strictly satisfy the necessary conditions for the SPRT's optimality (Theorem A.5 and A.6 because of experimental limitations.
One of our primary interests is to apply the SPRT, the provably optimal algorithm, to real-world datasets. A major concern about extending Wald's 's SPRT is that we need to know the true likelihood ratio a priori to implement the SPRT. Thus we propose the SPRT-TANDEM with the help of machine learning and density ratio estimation to remove the concern, if not completely. However, some technical limitations still exist. Let us introduce two properties of the SPRT that can prevent the SPRT-TANDEM from approaching exact optimality.
Firstly, the SPRT is assumed to terminate for all the LLR trajectories under consideration with probability one. The corresponding equation stating this assumption is Equation (6T) and (66) under the i..dd and non-i.idd condition, respectively. Given that this assumption (and the other minor technical conditions in Theorem and A.6 is satisfied, the more precisely estimate the LLRs, the more we approach the genuine SPRT implementation and thus its asymptotic Bayes optimality.
Secondly, the non-i.i.d. SPRT is asymptotically optimal when the maximum number of samples any.mptttiii allowed is not fixed (infinite horizon). On the other hand, our experiment truncates the SPRT (finite horizon) at the maximum timestamp, which depends on the datasets. Under the truncation, gradually collapsing thresholds are proven to give the optimal stopping (Tartakovsky et al. (2014)); however, the collapsing thresholds are obtained via backward induction (Bingham al. (2006)), which is possible only after observing the full sequence. Thus, under the truncation, finding the optimal solutions in a strict sense critically limits practical applicability.
The truncation is just an experimental requirement and is not an essential assumption for the SPRT- TANDEM. Under the infinite horizon settings, the LLRs assumed to increase or decrease toward the thresholds (Theorem A.6) in order to ensure the asymptotic optimality. However, we observed that the estimated LLRs tend to be asymptotically flat, especially when N is large (Figure 10 IT and
12 the estimated LLRs can violate the assumption of Theorem A.6
One potential reason for the flat LLRs is the TANDEM formula: the first and second term of the formula has different sign. Thus, the resulting likeliielihood ratio will be updated only when the difference between the two terms are non-zero. Because the first and second term depends on N + 1 and N inputs, respectively, it is expected that the contribution of one input becomes relatively small as N is enlarged. We are aware of this issue and already started working on it as future work.
Nevertheless, the flat LLRs at least do not spoil the practical efficiency of the TANDEM, as experiment shows. In fact, because we cannot know the true LLR of real- world datasets, is not easy to discuss whether the assumption of the increasing I.IRs is valid on the three databases (NMNIST,
28

---

Published as a conference paper at ICLR 2021
UCF, and SiW) we tested. Numerical simulation may be possible, but it is out of our scope because our primary interest is to implement a practically usable SPRT under real-world scenarios.
The best order N of the SPRT-TANDEM. The order N is a hyperparamer, as we mentioned in Section and thus needs to be tuned to attain the best performance. However, each dataset has its own temporal structure, and thus it is challenging to acquire the best order a priori. In the following, we provide rough estimation of the best order, which may give dramatic benefit to the users and may lead to exciting future works.
Let introduce concept, specific time scale, which is used in physies to analyze qualitative behavior of a physical system. Here, we define the specific time scale of physical system as a temporal interval in which the physical system develops dramatically. For example, suppose that physical system under consideration is small segment of spacetime in which an unstable particle, ortho-posse cuth--ossttooium (o-Ps), exists. In this case, a specific time scale can be defined as the lifetime of o-Ps, 0.14ps [Czarnecki] (1999)), because the o-Ps is likely to vanish in 0.14 x ((1) physical system has changed completely. Note that the definition of specific time scale is not unique for one physical system: it depends on the phenomena the researcher focuses on. Specific (time) scale are often found in fundamental equations that describes physical systems. In the example above, R in itself. Here (t) E R is the
the
the decay equation N (t) A exp(-t/rr has the lifetime expected number of o-Ps' at time E R. and A E R is a constant.
Let us borrow the concept of the specific time scale to estimate the best order of the SPRT-TANDEM, before training neural networks, though there is a gap in scale. In this case, we define the specific time scale of dataset the number of frames after which typical video in the dataset shows completely different scene. As is discussed below, we claim that the specific time scale of dataset is a good estimation of the best order of the SPRI-TANDEM, because the correlations shorter than the specific time scale are insufficient to distinguish each class, while the longer correlations may be contaminated with noise and keep redundant information.
First, we consider Nosaic MNSIT (NMNIST). The specific time scale of NMNIST can be defined as the half-life of the noise, i... the necessary temporal interval for half of the noise to disappear. It 10 frames by defimition of NMNIST, and approximately matches the best order of the SPRT-TANDEM: in Figure 3. our experiment shows that the 10th order SPRT-TANDEM (with 11 11-frames correlation) outperforms the other orders in the latter timestamps, though we did not perform experiments with all the possible orders. A potential underlying mechanism is: Too long correlations keep noisy information in earlier timestamps, causing degradation, while too short correlations do not fully utilize the past information.
Next, discuss the two classes in UCF101 action recognition database, handstand pushups and handstand walking, which are used in our experiment. A specific time scale is ~ 10 frames because of the following reasons. The first class, handstand pushups, has a specific time scale of one cycle of raising and lowering one's body ~ 50 frames (according to the shortest video in the class). The second class, handstand walking, has a specific time scale of one eycle of walking, i.e., two steps, ~ 10 frames (according to the longest video in the class). Therefore the specific time scale of UCF is ~ 10. the smaller one, since we can see whether there is a class signature in a video within at most ~ 10 frames. The specific time scale matches the best order of the SPRT-TANDEN, according to Figure 3
Finally, a specific time scale of SiW is ~ 1 frame, because single image suffices to distinguish a real person and spoofing image, because of the reflection of the display, texture of the photo, or the movement specific to a live persorf] The best order in Figure 3 is ~ 1, matching the specific time scale.
We make comments on two potential future works related to estimation of the best order of the SPRT-TANDEM. First, as our experiments include only short videos, it an interesting future work to estimate the best order of the SPRT-TANDEM in super-long video classification, where gradient vanishing becomes a problem and likelihood estimation becomes more challenging. Second, it is an
"hhis choice of words is, strictly speaking, not correct, hecause the noise decay in NMNIST linear; the definition half-life physics assumes the decay to be exponential. In fact, the feature extractor, which classified a single frame to two classes, showed fairly high accuracy in our experiment, without temporal information.
29

---

Published as a conference paper at ICLR 2021
exciting future work to analyse the relation of the specific time scale to the best order when there are multiple time scales. For example, recall the discussion of locality above in this Appendix D Applying the SPRI-TANDEM to dataset with distributed class signatures is challenging. Distributed class signatures may have two specific time scales: e.g., one is the mean length of the signatures, and the other is the mean interval between the signatures.
The best threshold X,- of the SPRT-TANDEM. In practice, user can change the thresholds after deploying the SPRT-TANDEM algorithm once and control the speed-accurace tradeoff. Computing the sered-accuracy-trate tradeoff curve is not expensive, and importantly computable without re-training. According to the seeeedd-cccrcc--rrradee
curve, a user can choose the desired accuracy and speed. Note that this flexible property is missing in most other deep neural networks: controlling speed usually means changing the network structures and training it all over again.
End-to-end v.s. separate training. The design of SPRT-TANDEM does not hamper an end-to-end training of neural networks; the feature extractor and temporal integrator can be readily connected for thorough backpropagation calculation. However, in Section 5 we trained the feature integrator and temporal integrator separately: after training the feature integrator, its trainable parameters are fixed to start training the temporal integrator. We decided to train the two networks separately because we found that it achieves better balanced accuracy and mean hitting time. Originally we trained the network using NMNIST database with an end-to-end manner, but the accuracy was far lower than the result reported Section [ We observed the same phenomenon when we trained the SPRT-TANDEM on our private video database containing 1- 1-channel infrared videos. These observations might indicate that while the separate training may lose necessary information for classification compared to the end-to-end approach, it helps the training of the temporal integrator by fixing information at each data point. It will be interesting to study this is a common problem in earlycllasifiiattion algorithms and find the right balance between the end-to-end and separate training to benefit both approaches.
Feedback to the field of neuroscience. Kira et al. (015)) experimentally showed that the SPRT could explain neural activities in the area LIP at the macaque parietal lobe. They randomly presented a sequence of visual objects with associated reward probability. A natural question arises from here: what if the presented sequence is not random, but time-dependent visual sequence? Will the neural activity be explained by our SPRT-TANDEM, or will the neurons utilize a completely different algorithm? Our research provides one driving hypothesis to lead the neuroscience community to deeper understanding of the brain's 's decision -aaiinn system.
Usage of statistical tests. As of writing this manuscript, not all of the computer science papers use statistical tests to evaluate their experiments. However, in order to provide an objective comparison across proposed and existing models, running multiple validation trials with random seeds followed by statistical test is helpful. Thus, the authors hope that our paper stimulates the field of computer science to utilize statistical tests more actively.
Ethical concern. The proposed method, SPRT-TANDEM. is a general algorithm applicable to a broad range of serial data, such as auditory signals or video frames. Thus, any ethical concerns entirely depend on the application and training database, not on our algorithm per se. For example, SPRT-TANDEM is applied to face spoofing detection, using faces of people of one particular racial or ethnic group as training data may lead to a bias toward or against people of other groups. However, this bias is concern in machine learning in general, not specific to the SPRT-TANDEM.
Is the SPRT-TANDEM "too local"" In our experiments in Section 5 the SPRT-TANDEN, with maximum correlation allowed (i.e., 19th, 49th, and 49th on NMNIST, UCF and SiW databases, respectively) does not necessarily reach the highest accuracy with a larger number of frames. Instead, depending on the database, the lower order of approximation, such as 10th order TANDEM, out- performs the other orders. In the SiW database, this observation is especially prominent: the model records the highest balanced accuracy is the 2nd order SPRT-TANDEM. While this may indicate our TANDEM formula with the "dropping correlation" strategy works well expected, remaining concern is the SPRT may integrate too local information. What if class signatures are far separated in time?
30

---

Published as a conference paper at ICLR 2021
In such case, the SPRT-TANDEM may fail integrate the distributed class signatures for correct classification. On the other hand, the SPRI-TANDEM, may be able to add the useful information of the class signatures to the LLR only when encountering the signatures (in other words, do not add non-zero values to the LLR without seeing class signatures). The SPRI-TANDEM may be able to skip unnecessary data points without modification, with modification similar to SkipRNN (Campos) et al. (2018), which actively achieve this goal: by learning unnecessary data point, the SkipRNN skips updating the internal state of RNN to attend just informative data. Similarly, we can modify the SPRI-TANDEM so that it learns to skip updating LLR upon encountering uninformative data. It will be exciting future work, and the authors looking forward to testing the SPRT-TANDEM on challenging database with distributed class signatures.
more challenging dataset: Nosaic MNIST-Harr (NMNIST-H). the main text, we see the accuracy of the SPRT-TANDEM saturates within few timestamps. Therefore, it is worth testing the models on a dataset that require more samples for reaching good performance. We create a more challenging dataset, Nosaic MNIST-Hard:: The MNIST handwritten digits are buried with heavier noise than the orifinal NMNIST (only 10 pixels/frame are revealed, while it is 40 pixels/frame for the original NMNIST). The resulting speed-accuracy tradeoff curves below show that the SPRT- TANDEM outperforms LSTM-s/m more than the error-bai range, even on the more challenging dataset requiring more timestamps to attain the accuracy saturation.
NMNIST-H SAT curve
10th TANDEM
95
19th TANDEM
LSTM-s
Balanced accuracy (%)
E
LSTM-m
90
85
80
75
70
10
20
Mean hitting time (#frames)
Figure 4: The spaed-accuracy tradeoff curve. Compare this with Figure in the main text. "10th TANDEM" means the 10-th order SPRT- TANDEM. TANDEM' means the models. The eruur bars are standard emorr of mean (SEM). The numbers of trials for statisties are 440, 240, 200, and 200 for 10th respectively.
SPRI-TANDEM. numbers trials hyperparameter tuning
TANDEM, 19th L.S.-s,
31

---

Published as a conference paper at ICLR 2021
E Loss FOR LOG-LIKELIHOOD RATIO ESTIMATION (LLLR)
In this section, we discuss a deep connection of the novel loss function, LLLR
LLLR
1 Σ iE4
|1 (log + M
Σ iclo
(log (XX.),
(86)
M
to density ratio estimation (Sugiyama et al. 2011 2010). Here, X; == {x E T and Us E (1.0) } (i E 7 == I U To. 7 N. dz E N) are a sequence of samples and a label, respectively. where 1, 11, and Lo are the index sets of the whole dataset, class 1, and class O, respectively. f(X,)
E I) is the likelihood ratio of X, The hatted notation (+) means that the quantity is an estimation with, e.g.. neural network the training dataset {(,,, 3))))) hez. Note that we do not necessarily have ((X p(X
to compute p( X,1y = 1) and p( X,ly = 0) separately to obtain the likelihood ratio f(X)) we can estimate directly, as is explained in the following subsections.
In the following, we first introduce KLJEP (Kullback-Leiblee Importance Estimation Procedure, Sugiyama et al. (2008)) which underlies the theoretical aspects of the LLLR, KLIEP was originally invented to estimate density ratio without directly estimating the densities. The idea is to minimize the Kullback-Leblerr divergence of the true density p(X ly 1) and the estimated density (X))((X))) = 0), where (X, y) is a sequential data-label pair defined on the same space as (X;, 3/4 's. Next, we introduce the symmetrized KLIEP, which cares about not only p(X ( = 1) and ((X) = 0), but p(X y = 0) and f- (Xly = 1) to remove the asymmetry inherent in the Kullback-Leilerr divergence. Finally, we show the equivalence of the symmetrized KLIEP to the LLLR; specifically, we show that the LLLR minimizes the Bellback--eiibler divergence of the true and the estimated density, and further stabilizes the training by restricting the value of likelihood ratio.
E.I DENSITY RATIO ESTIMATION AND KLIEP
In this section, we briefly review density ratio estimation and introduce KLIEP.
Density estimation is the construction of underlying probability densities based observed datasets. Taking their ratio, we can naively estimate the density ratio; however, division by an estimated quantity is likely enhance the estimation error (Sugiyama al. [2012 2010). Density ratio estimation has been developed to circumvent this problem. We can categorize the methods to the following four: probabilistic classification, moment matching, density ratio fitting, and density fitting.
Probabilistic classification. The idea of the probabilistic classification is that the posterior density XX is easier to estimate than the likelihood pXX] Y). Notice that
p(X ly -y-11 1) ply x p(y = 0) P(y 1|X) Mo
F(X) P(X by = 0) ply 0| ply
(87)
Ply = 0 M,
where M1 and Mg denote the number of the training data points with label and 0 respectively. Thus we can estimate the likelihood ratio from the estimated posterior ratio. The multiplet cross-entropy loss conducts the density ratio estimation in this way.
Moment matching. The moment matching approach aims to match the moments of p(Xly 1) and ((X))(XXy = 0), according to the fact that two distributions are identical and only if all moments agree with each other.
Density ratio fitting. Without knowing the true densities, we can directly minimize the difference between the true and estimated ratio as follows:
dx dXp(Xl== ()(()) -(x)))]
argmin
(88)
argmin
(Tp(Xly)0)F(( - 2 1xp(Xly==18
(89)
aargmnn
1 Me iET
Σ f(x,)²
2 Σ ((X)))
(90)
Mi ieh
32

---

Published as a conference paper at ICLR 2021
Here, we applied the empirical approximation. In addition, restrict the value of f(X): f(X) 2 0. Since (90) is not bounded below, we must add other terms or put more constraints, as is done in the original paper (Kanamori et al. (2009). This formulation of density ratio estimation is referred to as least-squares importance fitting (LSIF, Kanamori et al. 2009)).
Density fitting. Instead of the squared expectation, KLIEP minimizes the Kullback-Leible diver- gence:
argmin [KL(p(X|y 1 = 0))]
(91)
( ) 7(X)p(Xly== )
ar argmin
dXp(Xly 1) log(
(92)
argmin
- 1))o(((())))
(93)
We need to restrict f:
0 f() { XXF(X))(XXy==)
(94)
(95)
The first inequality ensures the positivity of the probability ratio, while the second equation is the normalization condition. Applying the empirical approximation, we obtain the final objective and the constraints:
argmin
Σ
log
(96)
M1 ich
F(X) 2 0
(97)
Σ f(x.)= =1
(98)
Mo
ieho
Several papers implement the algorithms mentioned above using deep neural networks. In Nam & Sugiyama 2015), LSIF is applied to outlier detection with the deep neural network implementation, whereas in Khan et al. (2019), KLIEP and its variant are applied to changepoint detection.
E.2 THE SYMMETRIZED KLIEP LOSS
As shown above, KLIEP minimizes the Kullback-Leibler divergence; however, its asymmetry can cause instability of the training, and thus we introduce the symmetrized KLIEP loss. A similar idea was proposed in Khan et al. (2019) independently of our analysis.
First, notice that
P(X yy 1) F(X)pl ( 0)
KL(p(Xly 1)llp -1)xX(n=1))(xXXXy=000 0)) = dxx(Xly> = 1) log(
(99)
dXp(x l)log(((X)) + const.
(100)
The constant term is independent of the weight parameters of the network and thus negligible the following discussion. Similarly,
(L =
=
ddxp(Xly = --
log(F(X)-") + const.
(101)
We need to restrict the value of f in order for p(Xly= = 1) and p( X = 0) to be probability densities:
{
O =0)
XxF(X 1
(102)
/
0) =
(103)
33

---

Published as a conference paper at ICLR 2021
and
0 S ((x) "(xlv 1)
(104)
= dxi(()) 1x
(105)
Therefore, define the symmetrized KLIEP loss
LKLIEP == / dd((-p(X)) f
= log f(X)) - /
d -
= 0) log f(X))
(106)
with the constraints (102 105
The estimated ratio function a IKLLI with the constraints
minimizes (L(p(X y F (X (((Xy 0)) + KL(p(Xlv D(x 1))). According
to the empirical approximation, they reduce to
1 Σ
LKLIEP ((X,)(()))))))))
log(f(X.)))
log(((X)))t))
(107)
M1 E
Mo
iET
P(X) 20
(108)
Σ F(Xi) =1
(109)
Mo ielo
f(X.) =
(110)
MI shh
E.3 THE LLLR AND DENSITY RATIO ESTIMATION Let us investigate the LLLR in connection with the symmetrized KLIEP loss.
Divergence terms. First, we focus on the divergence terms in 107
(f(()))))
(111)
M1 S
log (f(;))
(112)
Mo
sE
As shown above, decreasing and (112) of p(Xly = 1) and Fp(Xly 0) and that p(Xly 0) and f-1p(Xly = 1) respectively. The counterparts in the LLLR are
leads to minimizing the Kullback- divergence
LLLR
Σ
(log
log(f(Xt))
(113)
M
Mi
ieh
ich
+
Σ a (logF((x)) selo
Σ iETo
log log(f(X.)
(114)
Mo
because, on one hand, both terms (113 ensures the likelihood ratio to be large for class 1, and, on the other hand, both terms in (114) ensures f to be small for class O. Therefore, minimizing
LLLR is equivalent to decreasing both III and [112p and therefore to minimizing (108), i.c., the
Kullback-Leible divergences of the true and estimated densities.
Again, we emphasize that the LLLR is more stable, since LLLR is lower-bounder unlike the KLIEP loss.
Constraints. Next, we show that the L.LRR implicitly keeps i not too large nor too small; specifi- cally, with increasing R(X;)) = log F(X,)l, the gradient converges to zero before f((X;) enters the region, e.g., i((x:) Z 1. Therefore the gradient descent converges before A f(X;) becomes too large or small. show this, we first write the gradicnts explicitly:
V (wo(fog(((X.))) of o'llo f(X.)) Vw ((X,)
(115)
34

---

Published as a conference paper at ICLR 2021
where W is the weight and a is the sigmoid function. log ((X)), the factor
We see that with increasing R(X,)
o' (log F(X:))
(116)
converges to zero, because 116) ~ 0 for too large or small f(X;), e.g., for around R(X;) Z 1. Thus the gradient (15))
vanishes before f(X,) becomes too large or small, i.e. keeping i(X;) moderate.
In conclusion, the LLLR minimizes the difference between the true (p(X = 1) and p(X y 0)) and the estimated (f-1 (X =
and i( ((X)p(XXv = 0)) densities in the sense of the Kullback- Leibler divergence, including the effective constraints.
THE TRIVIAL SOLUTION IN EQUATION
115
We show that vanishing
V w log (Xx)
(117)
in 115 corresponds to a trivial solution; ; i.e. we show that 117 0 forces the bottleneck feature
vectors to be zero. Let us follow the notations in Table and Figure We particularly focus the last
components in the gradient V log F(X:), i.e. V w:loo log f(X;) (a E [dr.1]] and b E [dr.] = {0, 1)).
Specifically.
V Wil log
V ((( log log 1) V
"iin log (x 0)
Ogg
dog p(X'((Xly =
0gb (1)
log p( 0)
Σ
(118)
awill)
0gy (L)
aw
0gb (L)
==
Since Ö log /0g9 (L) = Syg - pgg where v.v' E {1,0) and wy. is the Kronecker delta, we see
Ölog ñ
(if y 1)
= (8y1 -py) - (8,0 pg) = {
(119)
Ögy (L)
(if 0)
Ögi (L)
0gu (L)
(L)
5:
118
w-()
1+
aw(l)
(-1) = 81of(l - for
(120)
ab
Thus 117
0 (va [d,,1l), which is trivial solution, because the bottleneck feature vector collapses to zero at convergence. Our experiments, however, show that model does not tend such trivial solution; otherwise, the SPRT-TANDEM cannot attain such a high performance.
118
fd f(l-1) -
(xx) = (1
( ) 22
Rdo=dd
(xx))) =(510 (0) (0)
Jál T (g
R 0,1, -)
(x,) = (F(())
.... f/ (1))r so
E =d,==
-d.
(xx)) = (011) ..... ( = - (x))
E R = 0, 1,,,,,...11 L-
E Rd 1xd1 = 0, 1, 2.... 1)
S (ax; M: training dataset
d,: input dimension
F; E Rd=; input vector
L: number of layers
t; E 2 oot label vector
σ: activation function
Table Notation. (0)) (an.) = az; input vector with dimension d, E N. ((0) (xr)) feature vector binary classification dimension d, jt (()) (me:) output softax function, and has dg since dimension di E N. W-O weight
problem paper. g (an, (an.)
feature vector before in the neural network, Figure visualizzs the network structure.
35

---

Published as a conference paper at ICLR 2021
f())
g
(xi)
f(1) (xi)
W(1)
(x))
(1+1) (xi)
p(++))
p(1-1)
(xi)
g (1)
(x:)
(L) (xi)
e (x 4i)
W
Soft-
Cross- entropy
Figure S: Visualization of the notation given in Table
+ We assume that the network has L cully-conneeted layers and activation
function with the final softmax with cross entropy loss.
E.4 PREPARATORY EXPERIMENT TESTING THE EFFECTIVENESS OF THE LLLR
To test if the proposed FLRR could effectively train a neural network, we ran two preliminary experi- ments before the main manuscript. First, we compared training the proposed network architecture Lmultipler. with and without LILR. Next, we compared training the network using Lmultiiplt with LIRR. and training with Lmattppet with the KLIEP loss, LKLIE,, whose numerator and denominator were carefully bounded so that the LKLIPP did not diverge.
(a)
(b)
3D face
2D face
Original video
Extracted
points
Figure 6: Depth-from-mottin datasct for the face 3D-ness detection task. Only three frames out ten frames are shown. Top and bottom faces are 3D and 2D faces, respectivoly. (a) Video of faces taken from various angles. (b) Facial feature points that are extracted with the leature extractor, Swy: (z (())
We tested the effectiveness of LLIR a 3D-ness detection task a depth-froom-mttion (DfM) dataser f] The DfM dataset was a small dataset containing 2320 and 2609 3D- and 2D- facial videos, respectively, each of which consisted of 10 frames. In each of the video, face was filmed from various angles (Figure 64), so that the dynamics of the facial features could be used to determine whether the face appearing in a video is flat, 2D face, or had 3D structure. The recording device was an iPhone7. Here, the feature extractor fuyz (f) was the LBP-AdaBoost algorithm (Viola & Jones (200T) combined with the supervised descent method (Xiong & De la Torre (2013)), which took the I-th frame of the given video as input Tit and output facial feature points (Figure (b)) The feature points were output vector of 152 lengths, consisted of vertical and horizontal pixel positions of 76 facial feature points. The temporal integrator (x)) is an LSTM, whose number of hidden units was the same that of feature points. The 1st-order SPRT-TANDER was evaluated on two hypotheses, = 1: 2D face, and y = 0: 3D face. We assumed a flat prior, ply 1) p(y = 0). The validation and test data were 10% of the entire data randomly selected at the beginning of training.
Forr the protection of personal information, this database cannot be made public.
36

---

Published as a conference paper at ICLR 2021
respectively. We conducted 10-fold cross- cross- validation test to evaluate the effect of LLLR-
260 (p
(=-(p-9.566
*(p=0.012)
0.08
0.07-
0.06
0.05
0.04-
0.03
0.02-
0.01
FLLR Lumnltight
LELIEP
frmiitigtes
Fmmillighe:
Figure 7: Statistical test of equal erorr rates (EERs) 10-fold cross-validation test. Two-way ANOVA conducted with loss factor (LeLR + Liuuligtet. LKLIEP + Luutiipee. and Lamiista)) and a epoch factor (21 100-th -100-th spoch). P-values with asterisks are statistically signilicant:
and three asterisks show 0.05, 0.01, and < 0.001, respectively. Error burs show the standard erroes of the mean (SFM).
We compared the classification performance of the SPRI-TANDEN network using both LLLR and Lmultiplet. and using Lmuitiplet only. We also compare LLLR Lmultipler and LKLIEP + Lmultiplet. To use LKLIP without making a loss diverge, we set the upper and lower bound of the numerator and denominator of 10 and 10-5, respectively. Out of 100 training epochs, the results of the last 80 epochs were used to calculate test equal error rates (EERs). Two-way ANOVA with factors "loss type" if the difference loss function caused statistically significantly
and "epoch" were conducted different EERs. We included the epoch as factor in order to see if the value of EER reached plateau in the last 80 epochs (i.e., statistically NOT significant). As we expected, EER values across training epochs were not significantly different (p = 0.17). On the other hand, the loss type caused statistically significant differences between the loss groups (i.e., TILR + T-multippess IKLIPP Temultiplet and /mmlttppee- p < 0.001). Following Tukey-Krrmme multi-comparison test showed that training with LLlR loss statistically significantly reduced the EER, compared to both LKLEF (p 9.56 * 10 10-10) and the S11R-ablated loss (p 9.56 10 10). The result plotted in Figure
37

---

Published as a conference paper at ICLR 2021
F PROBABILITY DENSITY RATIO ESTIMATION WITH THE LLLR
Below we test whether the proposed L.LR can help neural network estimating the true probability density ratio. Providing the ground-truth probability density ratio was difficult in the three databases used in the main text, because it was prohibitive to find the true probability distribution out of the public databases containing real-world scenes. Thus, create a toy- soy-model estimating the probability density ratio of the two multivariate Gaussian distributions. Experimental results show that multi- layer perceptron (MLP) trained with the proposed LLLR achieves smaller estimation error than an MLP with crossentropy (CE)-loss.
F.1 EXPERIMENTAL SETTINGS
Following Sugiyama et al. 2008 Sugiyama et al. (2008). let Po (a) be the d'dimeensional Gaussian
density with mean (2, ...y 0) and covariance identity, and pi (r) be the d-dimensional Gaussian density with mean (0, 2, 0,, ...., 0) and covariance identity.
The task for the neural network is to estimate the density ratio:
PI (ata)
f(x,)
(121)
Here, x is sampled from one of the two Gaussian distributions, Po or P1, and is associated with class label = 0 or = 1. respectively. We compared the two loss functions, CE-loss and LLLR:
N
LLLR =
(log f:)
(122)
N
where a is the sigmoid function.
A simple Neural network consists of 3-layer fully-connected network with nonlinear activation (ReL.U) is used for estimating f(x).
Evaluation metric is normalized mean squared error (NMSE, Sugiyama et al. 2008
N
NMSE =
(123)
N
2=
2j=1
f
Σ) 1 Ti
F.2 DENSITY ESTIMATION RESULTS
To calculate statistics, the MLP was trained either with the LLLR or CE-loss, repeated 40 times with different random initial vairables. Figure shows the mean NMSE with the shading shows standard error of the mean. Although the training with LLLR does not decrease NMSE well at the first few thousands of trials, the NMSE reaches as low as 10-5 around 14000 iterations. contrast, the training with CE shows a steep decrease of NMSE in the first 2000 iterations, but saturates after that. Thus, the proposed L.LR not only facilitates the sequential binary hypothesis testing, but also facilitates the estimation of true density ratio.
38

---

Published as a conference paper at ICLR 2021
Cross-Entropy
LLLR
10"4
1
5000
10000
20000
25000
30000
Figure S: Normalized meun squared error (NMSE) iteration curve. multi layer perceptron is trained either cross eniropy loss (blue) or the (red). show standard mean (SEM).
G MULTIPLET CROSS-ENTRON ENTROPY LOSS
In this section, show that estimation of the true posterior realized by minimizing the multiplet cross-entropy loss defined in Section Jn the basis of the principle of maximum likelihood estimation.
First, let us consider the 1st order for simplicity. The multiplet cross-entropy loss ensures for the posterior ((yl=<()) estimated by the network to be close to the true posterior p(y] Consider the Kullback-Leiie Leibler divergence of p(ylx(t)) and p(y]x((t) for some z(() Rd (t N), where y E {0, 1}:
argmin
E
KL (II()ll))
(124)
(p((()
argmin
E
- log (()))((0))
(125)
$
(att) p)ppppp(p0........)
M
argmin
Σ log p(ul)()))))))
(126)
M
Thus, the last line shows the smaller singlet loss leads to the smaller Ballback-Leibbee divergence; in other words, we can estimate the true posterior density by minimizing the multiplet loss, which is necessary to run the SPRT algorithm.
Similarly, we adopt the doublet cross-entropy to estimate the true posterior (f)) ((+11)):
argmin P
E (ar()), (ett)))p((())) .0(+))
[KL(p(y)o() x (++1) 110(()) (1) ((+2)))
(127)
log ply 2 ((+)))]
argmin
(128)
The crucial difference from the singlet loss that the doublet loss involves the temporal correlation between (t)) and (f++)) being necessary to implement the SPRT-TANDEM. Similar statements hold for other orders.
39

---

Published as a conference paper at ICLR 2021
H HYPERPARAMETER OPTIMIZATION
We used Optuna, the optimization software, to determine hyperparameters. Hyperparameter search trials are followed by performance evaluation trials of the fixed hyperparameter configuration. The evaluation criteria used by Optuna to find the best parameter combination is balanced accuracy. For models that produce multiple balanced accuracies mean hitting time combinations, we use the average of balanced accuracy at every natural number of the mean hitting time (c.g., one frame, two frames).
H.1 NOSAIC MNIST (NMNIST)
SPRT-TANDEM: feature extractor. ResNet version with 110 layers and 128 final output chan- nels (total trainable parameters: 6.9M) is used. Hyperparameters are searched within the following space:
learning rale E (10-2,10** 1
optimizer E (Adam, Momentum, RMSprop) weight decay E (10 10- "10").
Where Adam, Momentum, and RMSprop based (Kingma & Ba (2014), Rumelhart et al. (1986), and Graves (2013)), respectively. Numbers of batch size and training epoch are fixed to 64 and 50, respectively. The best hyprraarreeter combination is summarized in Table
Table Hyperparamettrr luning result of the SPRT-TANDER feature extractor on NMNIST database.
Trial
Leaming
Optimizer
docay
Dropout
5
One search trial takes approximately 5 hours on our computing infrastructure (see Appendix K
SPRT-TANDEM:
temporal integrator. Peephole-LSTM with a hidden layer of size 128 (total trainable parameters: 0.1M) is used. Hyperparameters are searched within the following space:
learning rate E (10-² 1002,, 1100.110
batch E (256, 512, 1024)
optimizer E (Adam, Momentum, Adagrad, RMSprop}
weight decay E [10-3 10-1 10-5)
dropout. E (0.0.1,0.2,0.33 0.3, 0.3,0.,0.5
Where Adagrad is based on (Duchi et al. (20TT)). Number training epochs is fixed to 50. The number of search trials and resulting best hyperparameter combination summarized in Table 6
Table 6: Hyperparameter tuning result SPRI-TANDEM temporal integrator. on NMNIST databuse.
Trial
Learning
Batch
Optimizer
Weight
Drepout
186
-2
1024
10-5
1st
151
10
1024
RMSpeup
10-5
D
RMSpcop
3rd
140
10
1024
Adam
10
D
10-2
5th
140
10
1024
Adam
10-3
10th
142
10 -2
1021
Adum
10
1024
RMSpcop
10
One search trial takes approximately 3 hours computing infrastructure (see Appendix K
40

---

Published as a conference paper at ICLR 2021
LSTM-m / LSTM-s. Peephole-LSTY with hidden layer of size 128 (total trainable parameters: 0.1 is used. Hyperparaméters are searched within the following space:
learning rate E {10 100 1000,1000;
optimizer E {Adam, Momentum, Adagrad, RMSprop)
weight decay E (10 100 11-
dropout E 0.10 0.2, 0.4,0, lambda E {0.01, 0.1, 6, 10, 100}
where the lambda is specific parameter of LSTM-m LSTM-s. Batch size and number of training epochs are fixed to 1024 and 100, respectively. The number of search trials and resulting best hyperparameter combination summarized in Table 7
Table Hy perpaaraaeeerr uning
LSTM-m LSTM-s on NMNIST databuse.
Thial
Learning mite
Optimizer
Weight decay
Dropose
Lambde
LSTM-m 1.5TM-s
160
le-002 1e-003
Adum RMSprop
Je-001
0
le-00)
159
1e-004
le-002
One search trial takes approximately 3 hours on our computing infrastructure (see Appendix K
LSTM with a hidden layer of size 128 (total trainable parameters: 0. 1M) is used. Hyperparameters are searched within the following space:
EARLIEST.
learning rate E (10-* "000".00-2... 10 10
100000', 10
optimizer E (Adam, Momentum, Adagrad, RMSprop)
weight decay E (10 10 10
dropout E (0,0.1,0.2, 0.3, 0.5,
Batch size and number of training epochs are fixed to F and 2, respectively, The number of search trials and resulting best hyperparameter combination are summarized Table
Hyperparameter tuning
database,
Trial
Leurning
Optimizer
Weight
Dropout
EARLIEST (lamhda: Lerrddd:-e-0023)
161
15-003
Adam
1e-004
EARLIEST (Jamhda: 1e-003)
One search trial takes approximately 48 hours on computing infrastructure (see Appendix K
3DResNet. 3DResNet with 101 layers and 128 final output channels (total trainable parameters:
7.7M) is used. Hyperparameters are searched within the following space:
learning rate (10-3 10-4. 1,10"1,00"" 1,00-)
batch size E (100, 200, 500}
weight decay E {10-3 10 13-
(129)
Optimizer and number of training epochs are fixed Adam and 50, respectively. The number of search trials and resulting best hyperparameter combination are summarized in Table
Table
Hyperparameter tuning result of DDResNet NMNIST darabase,
Input frames
Inill
Leariing rate
Batch size
Weight decay
50
1c-003
100
1c-004
50
1c-083
200
1e-004
As of writing this manuscript, the original code of FARLIEST does allow batch size larger than 1.
41

---

Published as a conference paper at ICLR 2021
Ablation experiment. Peephole-LSTM with hidden layer of size 128 (total trainable parameters: O. 0.I is used. Hyperparameters are searched within the following space:
110", learning rate E (10-), 10 1000..00=. 10003
optimizer E (Adam, Momentum, Adagrad, RMSprop)
weight decay E (10-9, 10 10-*)
dropoul E (0.0.11,.2,0.3304..3
Batch size and number of training epochs are fixed 1024 and 100, respectively. The number of search trials and resulting best hyperparameter combination are summarized in Table I0
Table 10: Hyperparametrr tuming result the ablation experiment.
Trial
Leaming rate
Optimizer
Weight docay
Dregout
Multiplet only
19th
1st
156
le-003
Le-003
RMSpnop
Adam
le-005
1e-004
LLER
1st
141
003
RMSprop
Adam
1e-005
H.2 UCF101
SPRT-TANDEM: feature extractor. ResNet version 2 with 50 layers and 64 final output channels (total trainable parameters: 26K) is used. Hyperparameters are searched within the following space:
learning rate {100 ,10 .10-5, 1.100.100)
decay {10-3, 10 100 10 100").
(130)
Numbers of batch size, optimizer, and training epochs are fixed to 512, Adam, and 100, respectively. The best hyperparameter combination is summarized in Table
Table 1I: Hyperparameter tunnning result of the SPRT-TANDEM feature extmetor on UCF datahuse.
Trial
Learning
Weight decay
10-3
10-5
Peephole-LSTN, with hidden layer of size 64 (total trainable parameters: 33K) is used. Hyperparameters are searched within the following space:
SPRT-TANDEM:
temporal integrator.
learning rate {10-*, 10 100 110=)
batch size {57, 114, 171, 171,
optimizer E (Adam, RMSprop) dropout E (0.1, 0.2, 0.3,
Numbers of weight decay and training epochs are fixed to 10 and 100, respectively. The number of search trials and the best hyperparameter combination are summarized in Table
Table Hyperparmmeter tuning result SPRT-TANDEM temporal integrator on database.
Trial
Batch
Optimizer
Dropout
Oth
100
1c-004
114
RMSprop
0.2
RMSprop
1e-004
RMSprop
100
1e-104
57
RMSprop
0.3
100
le-004
114
RMSprop
le-004
RMSprop
RMSprop
24th
100
1e-044
171
RMSprop
49th
100
1o404
342
RMSprop
42

---

Published as a conference paper at ICLR 2021
LSTM-m LSTM-s. Peephole-LSTM, with hidden layer of size 64 (total trainable parameters: 33K) is used. Hyperparameters searched within the following space:
learning rate {10"*, .000",,0,, 100".1007,
batch size E (57, 114, 114,,77,,42)
optimizer E (Adam, Momentum, Adagrad, RMSprop)
weight decay E {10- 10"* 100").
dropout E [0.1, 0.2,0,0.333
lambda E (0.01, 0.1, 1, 10, 100)
The number of training epochs is fixed to 100. The number of search trials and resulting best hyperparameter combination are summarized in Table 13
Hyperparameter tuning
Trial
Batch size
Leuriing rale
Optimizer
Weight
Dropout
Lambdu
LSIM-n
100
171
1e-005 003
Adam Adam
Te-003
100
LSTM
100
EARLIEST. LSTM with hidden layer of size 64 (total trainable parameters: 33K) is used. Hyperparameters are searched within the following space:
learning rate {100*, 100 10 2,03 ",0"",1011"""" 10-0;
optimizer E [Adam, Momentum, Adagrad, RMSprop]
weight decay E (10-3 100 10-
dropout E (0,0.1,0.2, 0.3,0,,,4
Batch size and number of training epochs are fixed to 1 and 30, respectively. The number of search trials and resulting best hyperparameter combination are summarized Table T4
Table 14: Hyperparameter combination of the EARLIEST on UCF databese.
Trial
Learning rate
Optimizer
Weight dacay
Dropour
BARLIEST (emmbaa: 1c-001)
1e-005 le 004
Adam Adam
1e:005 Le 004
EARLIEST (lambda:ee 005)
50
0.3
3DResNet. 3DResNet with 50 layers and 64 final output channels (total trainable parameters: 52K) used. Hyperparameters are searched within the following space:
learning rate E {10-3 10 1000001,,00 1000
weight decay E (10-3, 10 1011101.000 10--.10-5) 10-
(131)
Batch size, optimizer and number of training epochs are fixed 19, Adam, and 50, respectively. The number of search trials and resulting best hyperparameter combination are summarized in Table T5
Table 15: Hyperparameter tuning result the 3DResNet on NMNIST databuse.
Input
Trial
caminng
Ratch
Weight decay
50
Ie-004
100
le-005
30
le-004
H.3 SIW
The large database and network size prevent us to run multiple parameter search trials on SiW database. Thus, manually selected hyperparameters follows.
43

---

Published as a conference paper at ICLR 2021
SPRT-TANDEM: feature extractor. ResNet version 2 with 152 layers and 512 final output chan- nels (total trainable parameters: 3.7M) is used. Table shows the fixed parameter combination.
16: Hyperperameter tuning result the SPRI-TANDEM fearure extractor on
Butch size
Learning
Optimizer
Weight decay
83
1e-004
Adam
Ie-004
SPRI-TANDEM:
temporal integrator. Peephole-LSTM with a hidden layer of size 512s (total trainable parameters: MM) is used. TTble|I7 shows the fixed parameter combination.
Table 17: Hyperparameter tuning result of the SPRI-TANDEM temporal integratorabase.
Epoch
Batch size
Leumingg rale
Optimizer
Weight devay
Drepout
1e-004
Adam
1e-004
LSTM-m -STM-s. Peephole-LSTM with hidden layer of size 512s (total trainable parameters: 2. IM) is used. Table 18 shows the fixed parameter combination.
Table 18: Hyperparameter tuning result of the LSTM-m LSTM-s, on SIW database.
Epoch
Banch
Optimizer
Weight
Dropout
Lambda
50
83
1e-003
Adam
Te-003
100
EARLIEST. LSTM with hidden layer of size 512s (total trainable parameters: 2.1M) is used. Table 19
shows the fixed parameter combination.
Table 19: Hyporparameter combination of the EARLIEST on UCF databese.
Epoch
Leaminng rate
Optimizer
Weight decay
Dropout
3DResNet. 3DResNet with 101 layers and 512 final output channels (total trainable parameters:
5.3M) used. Table 20 shows fixed parameter combination.
20: Hyperparameter combination the 3DReNNet,
Input frumes
Epoch
Learning
Butch
Optimizer
Weight
5
30
1c-004
Adam
1e-004
1c-004
44

---

Published as a conference paper at ICLR 2021
I STATISTICAL TEST DETAILS
The models compared in the experiment have various numbers of trials due to the difference in training time; some models were prohibitively expensive for multiple runs (for example, 3DResNet takes 20 hrs/epoch on SiW database with NVIDIA RTX2080TI.) In order to have an objective comparison of these models, we conducted statistical tests, Two-way ANOVAfollowed by Tukey- Kramer comparcom test. In the tests, small numbers of trials lead to reduced test statisties, making it difficult to claim significance, because the test statistic of Tukey-Krama method is proportional to 1/ ((1 + 1/m)), where and are trial numbers of two models to be compared. Nevertheless, the SPRT-TANDEN, is statistically significantly better than other baselines. One intuitive interpretation of this result is that "the SPRT-TANDER achieved accuracy high enough so that only few trials of baselines were needed to claim the significance." " These statistical tests are standard practice in some research fields such biological science, in which variable trial numbers are inevitable in experiments.
All the statistical tests are executed with customized MATLAB (017)) script. Here, the factors for ANOVA are (1) the model factor contains four members: the SPRT-TANDEM with the best performing order the given database, LSTM-m, EARLIEST, and 3DResNett, and (2) the phase factor contains two or three members: early phase and late phase (NMNIST, UCF), or early, mid, and the late phase (SiW). The early, mid, and late phases are defined based on the number of frames used for classification. The actual number of frames is chosen so that the compared models can use as similar data samples as possible and thus depends on the database. The SPRT-TANDEM, LSTM-m. M and Net can be compared with the same number of samples used. However, EARLIEST cannot flexibly change the average number of samples (i.e., mean hitting time); thus, we include the results of EARLIEST to groups with the closest number of data possible.
For NMNIST, five frames and ten frames are used to calculate the statistics of the early and late phases, respectively, except EARLIEST uses 4.37 and 19.66 frames on average in each phase. For UCF, 15 frames and 25 frames are used to calculate the statistics of the early and late phases, respectively, except EARLIEST uses 2.01 and 2.09 frames average in each phasd" For SiW, 5, 15, and 25 frames are used to calculate the early, mid, and late phases, respectively, except EARLIEST uses 1.19, 8.21, and 32.06 frames. The p-values are statistically significant: one, two and three asterisks show < 0.05, 0.01, and < 0.001, respectively.
summarized in the Tables 21 24 P-values with asterisks
Table 21: p-values from the two-way ANOVA conducted on the three public databases.
NMNIST
UCF
S:W
model
.x00.00
*0.000 ver 161-66--6
***0.00
phase
1972 84E-261
0.65
Table 22: p-values from the Tukey-Kramer Kramer multi- coltii-oomprison test conducted on NMNIST.
10th SPRT-TANDEM
LSTM-m m
EARLIEST
3DResNet
earyy
late
early
lase
early
lose
eazly
10flarder SPRT-TANDEM
Lite
***5.99E-08
1STM-m
curly
***5.90E-08
late
***6,01F-08
**45 00F-00
***5 99F-09
EARLIEST
early
laie
**55.99E-06
A4a 1,26E-07
***5.99E-06
4445,996-00
**45.990 5.5999-08
1.00
**45 1445,998-0S
1.00
6445 99E-999--
3DResNet
cuty
**
**15.998-08
**15.99g.00 08
**95 992-
0115.999:00
w*15 99.9999-0
lase
***5.99 08
..45.99 08
*.4.99C
*..5
*..5.99
***5,99
***5.99E
6 'Nte that we also conducted three- way ANOVA with model, phase, and database factors to achieve qualitatively the same result verifying superionity of the SPRT-TANDEM over other algorithms. OOn UCF, EARLIEST does not use large number of frames even when the hyperparameter lambda is set to small value.
45

---

Published as a conference paper at ICLR 2021
Table 23: p-values from the Tukey Kramer multi comparison tesi conducted on UCF.
10thwoeder SPRT-TANDEM
carly
late
carly
lale
early
Inie
early
SPRITANNDEM
lase
5*95.99 05
LSTM-n
eady
1,244-05
V915000--0
laze
wer) 24455524-05
EARLIEST
endy
x*.9.426-07
**15,095-08
0.24
***5,990-44 9009-0--
lnte
-3.490.03
**19,42E-07
x<36,778-08
0.24
eies 99E-48
3DResNet
curly
*** 5..5,90--08
**+5.995-06
6445,
5-95,905-08 9909000
**45 900--06
4415 99E-08
#**5 99E-08
5,99. 08
**95.99 08
**15. 99.9% 08
**85 08
***5.998
***5,999
**15,99
p-values Tukey- multi comparison conducted
2nd-order SPRT-TANDEM
I.STM-m
FARLIEST
3TResNet
early late
2nd-arder SANDEM
LSTM
6*76,56E-0
EARLIST
corly
***5 5.00999-08
***5.906
5.99995-08
9988-05
3DResNer
4**5 99E908
**45.995-08
a*a5
**45
***5,00F-08
9.F008
00F-00
99F-08 99F-09 95F-08
46

---

Published as a conference paper at ICLR 2021
J DETAILS OF THE EXPERIMENTS IN SECTION 5
Here we present the details of the experiments in Section models we use in the experiment. Figure I0 and 12 using NMNIST. UCF, and SiW database, respectively. Tables accuracy and standard error of the mean (SEM) at the corresponding number of frames that used for classification.
Figure shows the SAT curves all the show example LLR trajectories calculated
25 to 40 shows average balanced
(a)
(b)
NMNIST SAT curve
NMNIST SAT curve
100
99.52
Balanced azcuracy (95)
95
Balancri accuracy
99.51
90
85
190 edde TACEN
99.49
80
(7T
10
20
99.48
10
15
Mean hitting time (eframes)
Mean hitting time (#fframes)
(c)
(d)
UCF SAT curve
UCF SAT curve
97.4
Balanced accuracy (8))
Balanced acouracy
85
odder TWEDMM
97.0
Jeace MA.00
96.8
96.6
10
20
40
Mean hitting time (Nframes)
Mean hitting time (#frames)
(e)
SIW SAT curve
SiW SAT curve
99.900
99.8
Balnnced accuracy 961
99.895
99.6
99.4
Belo0 ancedd accuracy
99.890
99.2
99.885
99.0
99.880
90.8
98.6
99.875
98.4
99.870
10
20
30
40
50
30
40
Mean hitting time (#frames)
Mean hitting time (#fromes))
Figure 9: Speed neeed-aceunccy tradeoff (SAT) curves of all the models. The right three panels show magnified views of the left three panels. The magnified region is same region plotted insets in Figure 3h. Bb. and B (SEM), (a.b) NMNIST database. (c.d) UCF database. (c.1) SiW databuse.
bars show standard enor mean
47

---

Published as a conference paper at ICLR 2021
(a)
Example LLR trajectory, data: NMNIST, order:
Example trajectory,
400
Miteiloodddddoooooooooooo rakio
200
20
loglllloooo
-20
-200
-60
10 12 13 Frame
14
15
16
19
15 29
Frame
(c)
(d)
Example LLR trajectory, data: NMNIST, order: 2
Example LLR trajectory, data: NMNIST, order:
40
20
Log Wtwllilndddddddooo radlo
20
-20
-20
-40
16 17
29
10 Frame
12 13 14
16 29
(e)
Example LLR trajectory, data: NMNIST, order:
Example LLA trajectory, data: NMNIST, order:
20
Log-likelhood rill
10
-20
(g)
Example trajectory, data: NMNIST, 10
trajectory,
Logilkkelhhed ralo
Log-Ikelnood
-10
-10
Frame
Frame
Figure 10: Log-likelihood ratio (L.R) trajectories calculated on NMNIST database, Red and blue trajectories represent odd and even class, respoctively. Pancls (8-1) shows results 0th. 1st, 2nd, 3rd, 5th, 10th, 14th, 24th, and 49th-order SPRI-TANDEM, respectively.
48

---

Published as a conference paper at ICLR 2021
(a)
(b)
Example LLA trajectory, data:UCF, order:0
Example LLR trajectory, UCFa:UCF, order:1
Log likelhood rato
likkihoodd rato
Log
-100
-25
550
Frame
[c)
Example trajectory, order:2
Example LLR trajectory, UCF, order:
60
30
40
Log Wollhoo rato
20
20
10
-00
-10
-20
-30
50
Frome
Framm
(e)
Example LLR trajectory, UCta:UCF, order:5
Example LLR trajectory, data:UCF, arder:10
Log likelPood rabl
-5
-10
-10
-15
-15
-20
10
20
30
40
50
10
20
30
50
Frame
Frame
(g)
Example LLR trajectory, data:UCE, order:
Example LLR trajectory, data:UCF, orden:24
7.5
5.0
ratio
2.5
5.0
0.0
Iacihood
2.5
-2.5
-25
775
10
20
50
10
20
Example LLR trajectory, data:UCF, 49
Log rat0
1
Figure 11: log-likeibbood ratio (LLR) tngjectories caleulated UCF database. Red and blue trajectories represent handstand- pushhup and hundstand walking class, respectively. Punels (a-i) shows results of Oth. 1st, 2nd, 3rd, 5th, 10th, 14th, 24th, and 49th order SPRT. TANDEM, respectively.
49

---

Published as a conference paper at ICLR 2021
(a)
(b)
Example LLR trajectory, data:SiW, order:0
Example LLR trajectory, data:SIW, order:
150
Log-thellood nato
Log Selllihhodd rato
100
50
-200
-50
400
20
30
50
10
20
30
40
50
Frame
[c)
(d)
Example LLR trajectory, data:SiW, order:2
Example LLR trajectory, data:SIW, orden3
75
rato
50
Log ileihhood ratio
20
25
-2
-90
-40
-75
-60
(e)
Example LLR trajectory, data:SiW, order:
(0)
Example LLR trajectory, data:SiW, order:10
20
Sig-liclhhodddoooooo ratio
20
Log Log-lkellood ratlo
1.0
-10
10
20
30
40
50
10
20
30
Frame
(g)
Example LLR trajectory, data:SiW, order:14
(h)
Example LLR trajectory, data:SiW, order:24
Log likelhood rato
5
-5
-10
-15
10
20
30
40
Frame
0
Example LLR tralectory, data: SWW, order:49
10
Log Wllithodd
Figure Log sigelikelihood (LLR) trajectories calculated databuse, trajectories represent spool class, respec-
tively. Panels (a i) shows results of Oth, 1st, 2nd, 3rd, Sth, 10th, 14th, 24th, and o9the SPRT TANDEM, respectively.
50

---

Published as a conference paper at ICLR 2021
Table 25: Databuse: NMNIST, model: SPRE-IANDEM (1/2)
0th
Frame
Meem
SEM
Mean
SEM
Mean
SEM
Mean
SEM
2
92,4200
3.5055c-004
93,8009
189199-004
93-7317
L.861c-000
93.5697
2.2729c 004
3
97,4691
1 103055-004
98.0409
7.31 10c 005
95.0061
8,2347c 005
97.9155
9,5436e 005
4
98.8174
5.18805-4155
99.0338
4.9126e-44
99,052
5.3061c-005
3.47942-005
3.5587e-005
4,2677e-000
4,0801c.005
6 99,3700
3.8820 005
99,4601
3.1799c 005
99.1456
3.839 005
99,4633
3,4830e 005
7
99,4480
3 422222-0055
99.4866
3 2020355-005
99,4783
3,5115c-005
99,4946
3. 3.2541c-005
8
2.917e-0055
99,4928
3.0137c-0K4
99.4899
3.3744c
99.5041
3.1241e
4954
2.9611-0055
4044
10002200005
99.4917
3.25404-005
99:5071
3.1055-0005
10 90,5004
2.8100-0015
99,4253
2.9 2998
99.4926
3,243%e-005
99,5088
3.84435- 005
11 99,3007
2
99.4934
2.91562 001
99.4929
3,2486e 005
99,3099
3.00/ 005
12
2.80550015
99.4754
3.25704-005
2.97522-005
13
99,5007
2.8895--015
99.4954
291156--005
3:25700-000
2,96496-005
14
99 99,5007
2.8895 (US
99,4954
2.9156c 00D
99.4928
3.25 000
99.5107
2,9599c 005
15
5007
2.889%--0155
99.47/5
562-560005
99.4928
3,25700-005
92.1107
2. 2,9599--005
16
2.8855-0015
99.4954
99,5007
2.5895e0005
99.4928
3.2570e
18
99,5000 5007
2.8895-0015
99 39.4254
569155-005
99.4928
3,25700-005
99:5108
2,90125--005
19
99,30077
99.4924
2.9156e-005
99.4928
3.25 005
99,3108
2,90256--00 0005
Sta., Atriala
100
100
130
120
Table 26: Datahase: NMNIST, model: SPRT-TANDEM (2/2)
Frame
Mcon
SEM
Meun
SEM
Mean
SEM
Mean
SEM
93.5525
3.0087-0044
93.5443
3.5917--004
93.7672
1,7120-0004
97.9744
9.74342-015
97.9483
1.5584-004
98.0168
8.0557e-005
98. 28.2590
5.3897c-000
4 99,0578
7.7568-005
99.0647
6,0566-0055
99.08 0854
4,1829--05
99:1162
4, 4,0463e-005
16059-005
355355
10676-005
3713
4.0986e-005
3.7966--005
99952:0005
9944113
4.33670-005
99.4657
3.4016e-005
99,4645
3,5654c-005
7 4844
4 10200-005
99 4803
4.3 3188-005
90 4940
1.882e-009
99.40 49.4943
3. 3.33496-005 005
8
9934
4 43301--005
99.4804
1210990005
99.50-9
00668--005
90,4975
3. 3,3000-005
4. 116495405
99
4.13206-005
3.3061c-005
10 5002
066426-005
90 40.4064
4.1014c-005
99.5119
2.9025e-005
99.4976
3.3061e-005
11
90.5013
407596-0015
99.4769
330-000
99:5132
2.92600-005
99.4976
5. 1.3061c-005
12
99 5019
4.0572-0055
99.1970
4.0075e-005
99.5135
2.9101e-005
99 99:1977
3.31422-005
13
40805:0055
3.9700-0055
3.31420-005
14
40062:-005
400044-005
99.5143
2.9773-005
99.4977
3.3143c-005
15
99 5022
4 006626-005
99 4980
100044-006
99.5144
2.9610e0005
99.197 1971977
3.3142-005
16
99. 5022
4 05626-005
99 4980
000044-005
99:5144
2,9410-005
99.4977
3.31426-005
17
406626-055
2.9410-005
3.31420-005
18
99. 5022
4.0562e-005
99 4980
A0004c-005
99.5144
2.9400-005
99. 4977
3.3142-000
19
99,5022
4 06622-005
99 4080
400044-005
99:5144
2.9410-005
90.4977
3.31426-005
stal. Atriass
70
70
100
Table 27: Database: NMNIST, model: LSTM-m/s
LSTM-m
LSTM-s
Frime
Mean
SFM
77. 77.885
1.7212e-00
88: 7368
L.1766-003
39.0127
9.0176e-005
93 3943943
8.08862-08 001
94.1324
7,0497c-005
96. 1456
3.1075e- 0001
96.1685
6.6315e-005
4.1456x-004
98 3505
3.5489 004
93,4303
4.0016e 005
98.7261
2.81 001
95.8419
3.64366 005
99.0151
2. 2.48633-001
99.0461
4.2539e-005
99.1751
10
99 1911
188822- 001
99.2758
4.758le-000
II
99 2693
166399-004
99 3305
4.439%-005
99 3401
99-3907
3.842%c 005
14
99 3994
14535e-0004
99,4494
4.4525e-000
15
99 4207
L.63%: 001
99.1548
4,2956e 005
16
99 1009
1.278%-000 001
99.4169
3.1843e 005
99
1.2698c-044
3.8017e--00
18
99 1918
1.3414e 004
99.5131
3,9145e 005
19
99 A820
1.2662--00 001
90.5 99.5178
3,2780e 005
99.4963
1.2963c-004
3.2808e
SUE, Atrials
138
130
51

---

Published as a conference paper at ICLR 2021
Table 28: Dutabase: NMNIST, model: EARLIEST
Lamidaa 1o-2
Lambda: 1o-3
Mean hitting time
Mean
SEM
Meon biuing time
Mean
SEM
4.57
97. 48.30
1.7986e-004
19.06
99.3407
4.5111c 005
stat. Atrials
130
Table 29: Database: NMNIST, model: 3DResNet
5 frames
10 frames
Menn
SEM
Mean
SEM
93 3059
5.43400-000
96.983
6.9305--004
stat. Atrials
100
200
Table 30: Database: UCF, model: SPRT-TANDEM (1/2)
2nd
3rd
Frame
Mean
SEM
Mean
SEM
Meun
92.9177
1.4953--002
93,7855
8.08225-004
94.20136
9.6000e-004
94,4136
8:93676-004
94,4764
6.01 380-344-1334
3782
1.470e-0003
93.5709
0.0460-003
93.9745
133486-003
93.8827
1.307500003
94.5345
8.78046-004
94 0586
1.5222e-003
93.9336
1.2935e-003
94.0073
1. 1.3311c-003
93.7145
1 44426-003
94.3364
8.77776-0344
94 6577
L41995-003
94,5586
1,3820e-000 063
94.09909
I 1.5426-003
03.8582
1.4 147086-0013
94.5364
8.75588-0044
1.3200-001
1.2608-0033
94.3550
0300
94,2305
13177-003
8016
80733-0034
3464
1,2122-003
95.3909
1.1544--03
7477
15500-003
94.6282
1.3686-001
94. 8827
36000-0044
9526127
L.150e-000
95.6595
1.0512e000 003
95.2452
I 1,320e 003
95,0000
1 1.2496-003 003
95.2145
32800-004
8473
1.11 1150--003
95,8295
1,0307e-033
95 6018
1.2770-003
95. 25.2443
12262-0003
9544445
00755-0044
960418
11158c-003
95.9627
1.0613e-n03
8377
1.28430-033
05.4218
95.6064
11 18c-1035
1782
1.08 093
0909
1,0505e-003
9519918
13183-0033
95.5318
1. 1911660003
95. 8023
-206--003
12
96 7664
10701e-001
96. 2341
1.0541e-003
06. 1245
I 1.294--003
05.6382
1. 150760003
96.0900
58544-034
13
96 4968
1.0795--03
96.336 3362
1.0504e-003
96. 2764
133226-003
0. 6906
1. 16422-0033
96. 1882
0.51 132-1044
4626
1.0524e0003
033556-003
95
1,661 0003
96. 06.3305
38488-034
96 8373
10797o-003
1.0815e-063
06.4618
133376-003
95. 09.7886
1. 15976-003
96.4383
0.881-0004
16
9668868
1.0663e 003
96.6600 6600
1,0617e 003
96.5252
I 1,309e 003
95,8759
1. 1,1770e 003
96. 16.5003
9.0577e-00
17
96 9009
1.0670-003
7055
1,074 003
96.57 5714
-03776-00
95. 05.9677
1. e93
96. 5264
8.9523-0004
969100
10621e-001
7700
1.0667e-003
100096-003
183 18330-003
777766-0344
19
96 9050
1.000.- 003
8155
1.0478e 003
96.65 6500
1,2776e 003
96. 000000
1. 16694e-00 003
96,6064
8.85844-00 004
20
96 90.0
060
96 8609
1.0254e-00
96 6691
I 1.274
96. 1927
1. 1463e-003
96.6345
5. 514-40004
21
96 9095
0603--003
96 8700
1.0182--033
96. 6873
1.27336-03
96. 06.25118
1451
96. 6666
63499--004
96
8655
1,0313e
1.2740e
96.2845
1.1448-0000
96.6930
8.5138c- 004
23
96 9095
003
8700
1,0312-0003
96 7327
I 1.2076-0033
96.3077
1. 1.33 10000-003
96.7183
-8544-004
24
96,9095
1.6603 003
96.8655
1,039e 003
76.7
I 1.258e 003
96.3456
1.124le 00.
96. 96.7223
8.1269c 034
25
96 9095
10600x000
96 8655
1,0399 003
96. 7555
1,251ee-03 003
96.3759
1. 1.1000e 003
96. 96.7268
8-4295-000
9095
060
8655
10390-000
1.351e-003
96.3941
1.005-0003
96.
16999-0034
27
96.9095
1. 1.0600 003
96 8655
1,039% 1.099-0003 003
96.7645
1,2453e 003
96.4032
1.1102e 003
96.7455
8.2897 004
28
96 9095
10603e-00
96.865 8655
1.139k- 003
96. 7762
I 1.2466e 003
96.4077
1. 11902e000 003
75.5
8.2935e-00
29
96 9095
0603--003
96 8655
11999-003
96. 7K27
1.2476-003
96.4123
1 1100e-003
96. 7545
703
96,9095
1.0003
8635
1.39% 003
96.7673
12407e
96.4123
1.1
96.7545
5.255 004
96 96.9095
1. 000603-000
8655
1,099-0003 003
96. 7918
1,2424e 003
96.4168
1. 10003-0003
96.7591
0.3
32
96,9095
L.6633 003
96.865 8655
1,099 003
7918
1. 1.2424e 003
96.4168
1. 110033-000 0013
96.7591
8.3202c 034
96.9095
1.0600e 003
8655
1,09% 005
96. 7918
1.442e 003
96.4168
1. 11005 003
96.7591
8.3202e 004
96 9095
1.600x0000
8655
10000 003
96.7918
123
96.4168
10336-0003
96.7591
8.3202e-004
35
96.9095
1.0003 003
945 8655
1,005A- 000
76.8
1.2424c 003
96.4108
1. 11003e000 0003
96.7591
8.3202c 004
36
96,9095
1.6603 003
96.855 8655
1,139 003
96. 7918
1.242 003
96.4168
1 11000e 003
96.7591
8.3202e 034
37
96 9095
000
8655
1,9999 003
Sh. 7918
1.2424-0033
96.4168
1. 1033--003
96.7591
8.3202e-00 004
96,9095
1.000e
8635
10359 003
96.7918
L.424e
96.4168
1.0033 0013
96.2591
S.3202 034
96.9095
1.060e 003
8655
1,039 003
96. 7918
1,242 003
96,1168
1. 11000:0033
96.7591
8.3202e 004
40
96 9095
10603--001
96 8655
(019A- 003
96. 7918
I 1.2424-0033
96.4168
1 1000--003
96.7591
32302-0044
96,9095
1,0603 003
96.8655 8655
1,05% 003
7918
1.242
96.4163
1.1033e 001
96.7591
8.3022 034
9699
[.6003 000
8655
1,39% 003
96.7918
12122e
96.1168
1.1033e 001
96.7591
8.320 004
43
96.909
100615--000
8653
1. 003
76.7918
1, 1.2424c 003
96.4108
1. 1.0053e0003
96.7591
8.5202e-000 004
44
96,9095
L0603c 003
8655
1.139 003
96. 7918
1.2424e 003
96.4168
1. 1.1033e 0013
96.7591
8.3202e 004
96 9095
1.0603e-00 001
96.85 8655
1,399c 003
96.7918
1.242 003
96.4168
1. 1.1003e 003
96.7591
8.3202e 001
96,9095
1.0603e-000
8635
1.359 003
96.7918
1.2434c-003
96.4168
1.1053e-0013
96.7591
8.32026-004
47
96.9095
1.6000 003
96.8655
1,099 003
96.7918
1.2424c 003
96.4168
1. 1.1033e 003
96.7591
8.3202e 004
48
96.9098
1.0603e- 002
96 8655
1.039p 003
96. 96.7918
1.242 003
96.4168
1. 1.1003e-000 003
96.7591
8.3202e-00 004
9639095
L.0603c-400 003
8655
1.0399
96.7918
1.2424e
96.4168
1.1033e-003 0013
96.7391
8:3202e 0034
4166. Strials
200
300
200
200
200
52

---

Published as a conference paper at ICLR 2021
'Table 31: Database: UCE, model: SPRI-TANDEM (2/2)
49th
Frame
Meum
SEM
Mean
SEM
Mean
SEM
Mean
SEM
2
94,3093
7.0583c-004
94.3973
6.35922-004
94.4741
6.5887e-004
94.5164
5,4415c 004
3
94,2913
9.2496c-000 004
94.4836
7.6021c 001
94.6227
7.1819c 001
94,0027
5.6738e 004
4
94,7670
1.2222-0055
94.6000
8.4566e-004
94.7445
8.5464
94.3614
6,37655-004
1.2322-0005
94,7559
9.77622-004
101
943126
6
95, 95,455
1.2265e 003
95,0105
1,0293c 000
95.0127
1.01 000
91.0668
8,6725e 001
7
95. 7621
1. 1:1532-0055
95. 1614
10559-000
95. 1064
L05133-005
95 50111
9:33426-00 004
1.2003e-003
95.3300
10980e-
95.1927
1,0612
95,3632
1.1858:005
11000--005
95.4233
10592-000
95,2618
10 96.1547
1.1972--015
95.8186
L.1200-006
95.8045
9.8477-000
902027
1/1222-000 401
11 96.3664
1.1808e-003
96,0200
10886c 000
92.1218
9,5190 000
96.582
9,8495e 004
12
1.15550005
96.3145
968759
9.60A4-0004
13
96,0033
1.1441:-0055
96.4641
96.5506
9.68870-00
963922
9,2010c-004
14
96.7571
1.152900003
96. 96.9886
9.20344 004
96.6436
9,30MM 100
97,0911
8,5480e 004
15
9498
1156770005
9644045
2. 75759---04
9K-7279
8.722%
97,0350
R. 8.55856-00
16
111125-0011
96.2995
9K-7314
9900091
17
96,8565
10099::003
96.6732
9,299% MO
96.7668
8.5201c 100
963873
8.61776
18
96.8616
106542-0155
96.7214
0.3324-/04
96.7866
8.3516--00
965891
H, 8,44922-004
19
96,9304
1X2912-005
10144:0001
96.7586
96-7764
9.41470-00
96,7814
8. 8,1684c 000
7.9474-004
070177 070177
90960S
H. 5,300 004
10044-0004
21
97,0455
10045:0015
96-7244
96.229
7.8600-000
15900-00
22
974067
1 1004350015
96 96-3
9.1 111188000 00
90.8205
7,9470 400
97.1186 1
7,88150 000
23
97.0746
4 1004::0055
96 3455
94-8477
7.9763-009
969991
7. 7394056-004
24
9,55145004
96,3350
9.11510-004
8.069%
1.95916-004
97.1243
9 004
96-8077
95.8600
8.1 8.12%% 40
969391
7,81250
26
97.1385
9 65524-0044
96 3964
0.00 200
8.025X-004
950377 7
27
97.1740
9 000700000444
96 96,3944
9038555
8.325 400
8.104T6-004
28
8.3312
8.205
0004
20
97. 2024
9.5 9.577740004
22
26,441
96819 1
31
30
97 2386
97.2173
9. 56055-0044
9. 5507
96 2411
8623
96 7941
8.8176
8.65700-00 000
061150
8. 8.55776-004
8:6152a-00 400
32
96,9596
96.7986
8.794%
005000--004
93.2386
96-2595
9188--0
962999
34
97.2386
9 5507:0004
96 9598
R. 0188-000
96 7986
8.82000-004
967795
8. 80000--004
35
9772457
9 5259
96 9545
8 0598--00
8.7490 -00
967444
8. 8.93876-004
36
96
9.974--00
8.783
0,0508-0004
37
97.2457
5250:-004
96 9495
9724--00
90.06
9, 100
38
9772457
9.5 52559-20144
96 96-9555
X 97244774
8.7856--004
9.1 19119400004
39
9772457
9 0.555-0004
96 9495
8.9 97244-001
96 8636
8.783%- 001
961150 0
9,11936-004
40
9,11976-004
41
97.2457
9.559940044
96,9495
8.9724--044
96,7286
8.8208-0044
1.0941c-004
42
9772457
9 9.559--0044
96 9495
8 8.9724-0044
96. 7936
8.8293x0004
96.7155
9, 9,1751e-004
43
97.2457
9.5 0.525900044
96 9495
8.97242-0MM
9636
8.8293--09 404
96.7155
9,175
9,1751e-004
45
97.2457
0.5250=0004
96 9499
8.9724--004
7936
8.8792-0004
967155
46
97.2457
9.5 9.5259:-094
96 9495
8.9724--004
96.7936
8.82930-004
96.7155
9.1751c-004
47
97,2457
9 0.5259-004
96 9495
8.9724e-001
96. 7936
8.8292 001
96.7155
9,1751e-004
48
97,2457
0.5250-0044
8.9724--004
8.8292--004
9,1751c-004
97.2457
9.5 9.52596-004
96 9455
8.97240-004
96.7891
8.87856-004
96.2155
9.1751c-000
stat. Auials
228
200
200
200
53

---

Published as a conference paper at ICLR 2021
Table 32: Databuse: UCF, model: LSTM-mus
Frume
Mean
SEM
Mean
SEM
92.3218
3.4055e-005
$4.2160
1.1426e 002
93.1418
2,5895c 000
90.8731
4,195% 003
55.5545
2.8885-0006
3609
2.9801-0008
2212
207144-000
93.3100
1968 000
93.1665
2,2873e 003
95. 1673
9889--006
92.8992
2.1601e-003
93,0718
1.9655-44
L9121e
188686-003
937873
18754-0005
93.1998
LM342e-00
10
94.3245
18930c 000
93.7480
1.799cc 003
L6810--002
13
95 0064
L.8533-000 000
94.3366
L8006e 003
14
94 6818
96462-008
94.2475
1,7542
L6357e
L8724-000
17
94 3909
18218-000
94.5104
18
95. 3064
L.72542-00
943128
L62tMe 003
95-7255
66622-005
95,4770
95-7336
16175--000
95.74622
1.4674- 003
22
8508
6107--001
95.8596
1.4144-000
95,000
16703--00
L.4755--000
25
95 9273
16787-0001
95.02511
1.5155-000
26
95 9M00
1.23770-008
95 9466
1.4797 005
95-0536
9586
1-7077--00
29
95 9991
1.28 1.88000000
0550
1.9112--00 0008
30
96 0027
2433--00
6730
4466
1.2232-000
9640567
L.88177-000
31
96 0727
8089-2001
06 061468
34
96 1527
84990-001
91.4
1.607A--00 000
1991
1.7732-0011
96-2111
54800-000
37
96 3882
1.2635-00011
96.3762
96 1973
7.792--001
9633
1.355
1.880-001
69966--00
96 3727
6963--001
96.5410
1.3637-0003
42
96 4718
66155-011
96-5734
1,2837e-003
5873
70995-0001
6094
1.2952--001
96 6445
66142-001
96.5086
1.3716e-001
96. 7209
16844--00
96-5300
1,3668x
96
1.7179--00
1.4514e-003
49
96 6845
6888 1819--000
96.4545
1.5521e-003
50
96 6891
70006-0001
96-51449
1.5340-0003
100
Table Database: UCE model: EARLIEST
I Lamiddo: 16-3
Lambda: 1e-5
Mesa
SEM
Mena hitting
SEM
2,0710
93, 4600
1.23976-003
2.0924
93,4800
8,5977e-004
Strinss
130
Table Database: model: 3DResNet
15 frames
25 framos
Mean
SEM
64.4188
6.79055-000
SKL0827
4.9385c-003
stat. Atrials
49
100
54

---

Published as a conference paper at ICLR 2021
Table 35: Databuse: SiW, model: SPRI-TANDEM (1/2)
3rd
Fram
Mean
SEM
Mesn
SEM
Mean
SEM
Meum
SEM
Mexn
SEM
99,8243
6.3459p0000 00G
99,8461
1.2108e 005
99,862
9.1650e 006
99,8677
7.4006e-000
99.8647
1.1755c-025
99.3182
8,7040e 006
99,8604
1,3893e 005
99,8781
8.4124e 006
99,8846
9.1821e 006
99,5752
1.0975c 005
99.8396
1,2285c4000
99.8671
1.5950e-000
99,8864
8.05
99.8904
7.53896-006
107707--035
993365
003
1.5600-
7.2057c.006
99,8917
6.7430e
99-8880 8
1-02-42--00 0035
99,3695
1.082le 003
99.8797
1.6822 005
99, 99,8933
7,0790 006
99,8920
6.5525e 006
99,8355
9,0529 006
993710
L,6623
1,5900 025
99,8939
7 7.35456-006
99,8925
6. 6.5969e-006
99,8888
0.22900--000
99,8722
1,1225c 003
99,8841
1.585cc
99,8940
7.2435g
99,8930
6.5214e-000
99,8888
000
928734
109900-005
8847
0.5685-005
7.027660066
59 8935
6.515860006
99. 19,8800
19036-006
10
993874
L,1475e-005
9988599
1.5007e-000
99,8947
7 7.89266 006
99 99.8955
6.5011e-0006
99 8892
8.94922-0066
11
99,8745
L1716e 005
99 8868
1,4293 005
99,8954
7 7,8938e 006
99,8939
6.4258e 006
99,8993
9.1568c 036
978745
1.170e-005
8880
005
740
99,
6.5122-0006
99.8893
9-1771
993745
L1710e-005
8886
005
7.050000066
99
6.4760e-1006
99,8894
1.148
14
99.8455
1,1710c 00S
3888
1,508e 000
99,9961
7,3445c 006
99, 99,8940
6.4613e-000 006
88.8394
9.1073c- 006
15
9747
L1710--005
8891
1.2824-000 005
99 8961
6.9314c-000
99. 8940
6.501600006
99. 5833
1.5933-006
9945745
L,7100-000
8962
6.9156e-006
99,
6.4201e0006
8894
99.8745
L1770e 005
1 005
6.9156e
99, 59.8
6.4501e
99,8894
9L0983c 036
18
974745
L1710e-005
8893
1.2955e-0005
99,8962
6.9155e-8806
99 8948940
6.4501e90066
99. 8894
19
993875
L17 00S
99 8892
1,324% 005
99 99,9912
6.9156e-006
99,8940
6.4201c0006
99, 8558554
9787
1.170-0005
06c-0006
99.
10155-106
998745
10700-005
8892
6.9156e-006
59
6.55356-0016
99.8894
10556-00G
22
99.875
1,1700-000 LOS
99.8991
1.5 S7B 00D
59,8961
7,010% 006
99 09.8940
6.5535e-006
99, 8998
9. 9.10035-0000
23
974745
1,17 1710-0055
8891
1,3844--055
99 8961
7 7.0166-0006
99. 8940
6. 6.55356-006
99. 5854
10055-0006
9745745
1.17
8891
7 7.01696-006
99.
6.55356-006
99,8894
1.105---00G
9938745
L1710e-005
59.88
005
99,8961
7 7.0169c-006
99 8940
6.5535e-006
99,8853
9109796-006
26
9747
L.7100-005
8891
09 09.8961
7 7.01696-006
99. .948940
6.55 6.5535c-906
99. 8873
02779-0006
27
99.875
L. 105
99 8991
1,3877 005
99 89.8
7 7.010%--006
99,8940
6. 6.55356-0006
99. 8992
990779--006
8745
11710-000
1.3972
7
09796-006
99 8777
1.1700-005
8891
0.3933-0055
2.01696-006
59. 8340
6.553560006
99. 99988833
02796-006
30
998775
L1710c-005
8998
1,39 29222e-100 005
59, 8961
7. 7.0119%- 006
99, 8948
6.55 6.5535e-006
99. 889/
910779--006
9745
1.17 175
99 8891
1.39220- 005
99 8961
7 20169--006
99. 8940
6. 6.5535--006
99. 8893
0079
8745
I.1 11710-000
1.3922e-005
7 7.0149c-0066
99.
00799-106
993875
L1710e-005
8891
005
99,
7 7.0109c-066
59. 8940
6.5535e0006
99,8893
96799-0006
34
874745
L.710--005
99 8891
3933200005
8961
7. 7.0169--006
99 8948
6. 6.5535c-806
99 8893
0079--006
35
8748
L17 175
99 8891
1,99 39922- 005
190 8961
7 7.010--006
99.8940
6. 6.55356-0066
99. .873
8745
11710-000
7
09796-006
90 8745
1,17 705
8891
09333-0005
7 21669-0006
99. 8340
55335-006
8803
0079--006
38
99 8745
1,7 L1710--005
8891
1.39 29222-0005
99,8900 8961
7. 7.0169c-0066
99. 8948
6. 6.5535c-900
99 8873
907799--066
39
8745
I 105
99 8891
1,3922e 005
99 8961
7 7,016 60166-0066
99. .948940
6. 6.5535-0006
99. 8893
09799--00
8745
11710-000
1.3922--005
7. 201669-0006
00799-006
993775
L1710c-005
8891
1.39326-005
99,899 1961
7 2.01690-006
59. 09.8940
6.553560006
99,8893
907796-000
42
99 8745
L1710-0005
99 8891
1.3922e-005
99.899 8961
7 7.0166e-006
99 8948
6.5535e-006
99. 8893
90799--006
41
8745
L.1100-005
99.8891
1.59222-005
991 19.8
7 2.01496-006
99.8940
6. 6.5535-0006
99. 99.8
9.0999-9066
97.5745
L1710e-005
7.
6.5535e-006
006
90 8745
1,1710-005
8891
-95
09 8961
7 7.0606-006
99. 8940
6.5555-0006
8898891
900979--006
46
99 8745
L1710--005
8891
39322-0005
99.8961
7. 7.01690-006
99. 09489400
6.5535c-906
99 02.8893
900799-0036
47
99,8745
99.75
1,3220e 005
99,8961
7,0 66 006
99. 89.0
6. 6.5535e-006
99. 8893
9.0979e- 006
N.A.
7.01
6.55350-006
09796-006
N.A.
N.A.
N.A.
99.8961
7.0169e-006
59 39.8940
6.55356006
99.8893
907996-006
StAd. Ptrials
116
109
55

---

Published as a conference paper at ICLR 2021
Table 36: Database: SiW, model: SPRI-TANDEM (2/2)
Frame
Meam
SEM
Mean
SEM
Mean
SEM
Mean
SEM
2
99,5726
4.1014
99.8706
5e7355c-005
99.8149
8.6377e-006
99,8724
1,2239e 005
3
99.53
1 198933 005
99 5762
1.2680e 005
99.8781
3.4636c 006
99,8800
1.2553e 005
4
1.5748c-015
99.8772
1.29722-005
8.852
L19644-005
1.2902e-005
L.77170-005
9,4704c-008
1,1899
6
99 5527
1.31
99 5766
1.1587c 005
99.8789
9.96015 006
99,8790
1,1873e 005
7
99 8826
1.3214:-005
99.8769
L.25670-005
99.8791
L02263-005
998791
L11447e-005
1.3378c-005
99.5770
1.7585c 001
L1899e
99,8826
1.34895-015
3-2693
10018X0005
1.152960005
10
99 8826
1.35900-005
99 8766
1.7846c-005
9938993
L80293--000
99,8955
1.1611e000
11
99,5827
1.1508c 00S
99 99.5767
1.7933c 0LL
99,8793
L0553e 005
99,899
L.1370e 005
12
99.8768
L06665--055
L.165c-005
99
1.34836-005
9938768
L.1657c-005
14
99 99,5
1.2567: 0US
99 3768
18001c OLS
99,8944
L.1115c 000
99,8797
1.1590c 005
15
99 8938
1. 1.3633-0055
99.8769
1. 79941--055
99,8795
L,1157e-005
922799
L11776-0005
16
1.5546-0015
99
L1155c-000
1.1644
17
99,8333
1.2600-003 005
L11100
L.184cc
18
89.8
1.3756-005
99.8771
142--00
993796
L,1133e-005
99,8804
1.1772e-005
19
99,5540
1. 1
99
1.79 O015
99.8797
1.11fcc 00S
99,8805
L.1570e 002
99
8036--005
1.1265--005
L18500-005
21
99,8546
99.8771
L.1457c-05
1.18706-005
22
99 3800
1.41 7015
9978772
80022-000
99,8796
L,1500- 000
99 99,8606
1,20155 005
23
1 42676-0015
99,8772
8090--005
99,8796
1.1647e-005
90 2805
L.21476-005
24
9975775
L.1655e-005
99,8266
102
9777
185244-005
L.165S-000
1.20776-000
26
99.8
1. 14240-0015
99 99,8780
85012-0005
998798
1.16822-005
8907
1 1.2167C-000
27
99 8859
1 14228-0015
99.8783
85622-0055
99.8799
1.16% 005
99 XHUT
L.21676-005
28
1.1685-005
20
99,
4477:-005
99
87003-005
1.165%-0005
1,23805-005
30
99 3361
1. 44594-001
9938797
99,8808
1.2218e-005
99 8917
1,2156--0 005
31
99 5860
45250-005
99 3796
99993
99.8799
1.3023
99 2812
1,206-0005
32
1.3221c-005
1,1934--005
99 8959
166105-005
3758
09956-005
L.3433-000
1,19096-005
34
99 8858
14752-0015
90 8798
1.996 0963--005
881
1.35122-005
90.8821
1. 805
35
99. 8858
1 14743-0015
99 8799
19998--05
99.8813
1.3567e-005
90 99,8821
L,1915-0005
36
99
1.36300005
37
99
47749:0005
5302
8815
36676-005
1818800000
38
99 585H
1.4499-0015
99 3304
2 0023350005
9988816
1.36776-005
9928
8.1855--005
39
99 8858
1. 14732=0055
99 5505
2 2.0255-0005
8818
1.3695-005
99 8822
L1830-0005
40
1.3735--005
1,1710-000
41
99,889
146055-005
5303
L.37426-005
1,1633e-005
42
99 8856
146736-005
99 5303
2. 00044-005
8821
1.3765e-005
90 90.8825
1,1630--005
43
99.88 8856
1. 146736-005
99 5802
99862-005
99.8822
1.38522-005
90 8825
L16122-005
45
46255-005
99 5305
9928x-005
8888825
0.3976-005
1.1630-005
46
99 8856
1 46250-005
99 3301
99944-0005
99.88.2
1.3844-005
09.8825
1.16322-005
47
99 8856
1. 1625c-005
99 5505
9904e-005
99.8826
000
99 8825
L,1630-00 005
48
46255-005
1,1630-005
99,8856
1.6256-005
99 30.330
08992--0055
99.8876
30-00
99,8825
1,1633x-005
stat. Auials
56

---

Published as a conference paper at ICLR 2021
Table 37: Databuse: SIW, model: LSTM-m's
Frume
Mean
SEM
Mean
SEM
99 /207
7.6320e-005
99.6207
7.6520e-00
99. 7677
2.299cc 005
99.1677
2.2591c 005
1.27%--005
1.1275-005
99 5029
S.5725c 006
99,8029
8,5723c 006
99. 7969
2209
99,7969
1.209% 005
99.951
1.3207c-KKL
1.3277c
L19808-005
1.1980-000
99 S0E1
1.33970-005
99,8551
L.3557e-000
10
99 3057
1.46662 0LS
99,8057
L.668e 005
L6821c-005
L.133--005
13
99 3196
L8401c 0LD
993896
L8401c
14
99 8341
1.2274--005
998241
1.7274e-005
X264
17
99 8316
66679-000
993316
L.6675-005
18
99 8335
I. 60099 O01
99,3335
L609 005
8383
1.9336-005
99 3391
L.99 1914
9938391
L.7974e-00 000
22
99 3401
7900--005
9984
1,7900--000 005
2449
L8522e-
25
99 8474
1891
9974
18391e-005
26
99 3457
199416-0055
9934497
1.9941c-055
94100-005
1,9410-005
29
99 3550
9969--00S
993550
1.99
30
99 8562
9671e-005
8562
1.9671e-005
1.92522-005
8578
31
90 5600
85322-005
99 8600
L88522-005
34
99 5G27
2.01 20c-0005
99 8627
2.01206-008
2.2477-0005
2.24776-005
37
99 8663
2 212122-0055
8663
2.2142e-005
99 8675
19121e-005
8675
2.192
8679
99 5683
25692x-005
99 8683
2.059x-000
42
99 8902
2.1 11503-0005
99 8692
2.1 21503--005
1346e
8726
50-15500005
2.1915e-005
99 5748
11044-0055
9748
2.3104c-005
99 8754
2.1851e-005
99.8754
2.1851e-005
211800-0055
2.8200-005
2.1 19744-0005
2.1974e-005
49
99 8780
2.2132e-005
99.8780
2.2133x 005
50
99.8782
2.08006-005
99.8782
2,0800-005
stat. Atrials
63
58
Table Database:
EARLIEST
Lambdic 1e-3
Lambda: le-5
Lambda: 1e-10
Mese hitinn
bitting
Mean
SEM
Mcan hitting time
1.1924
99.7156
4.4309e-066 005
8,2087
99,7753
2.9947e-005
32,0530
99.6823
4.5917e-005
Abd. Strials
30
17
Table Datahase: model:
Frame
Mean
SEM
98.8100
1.67622-013
98.9740
0666--011
98.5560
1.1066--003
Table 40: Database: SIW, model: 3DResNer
Mean
SEM
Mean
SEM
Meun
SEM
98. 8160
1.6702e-000 003
98,9740
1000c 003
98.550 98,5500
1.1066e-0KE
57

---

Published as a conference paper at ICLR 2021
K COMPUTING INFRASTRUCTURE
All the experiments are conducted with custom python scripts running on NVIDIA GeForce RTX 2080 Ti, GTX 1080 Ti, GTX 1080 graphics card. Numpy (Harris al. (2020) and Scipy (Virtanen et al. )020 are used for mathematical computations. We use Tensorflow 2.0.0 (Abadi et al. (2015))
as machine learning framework except when running baseline algorithms that are implemented with PyTorch (Paszke et al. (2019))
58

---

Published as a conference paper at ICLR 2021
L AN EXAMPLE VIDEO OF THE NOSAIC MNIST DATABASE.
As we described in Section 5 the Nosaic (Noise mOSAIC) MNIST, NMNIST for short, contains videos with 20 frames of MNIST handwritten digits, buried with noise the first frame, gradually denoised toward the last frame. The first frame has all 255-valued pixels (white) except only 40 masks of pixels that are randomly selected to reveal the original image. Another forty pixels are randomly selected at each of the next timestamps, finally revealing the original image at the last, 20th frame. An example video is shown Figure
3
3
Figure 13: Nosaic MNIST (NMNIST) database consists videos of 20 frames, each of which has 28 x 1 pixels. The frames are buried with the first frame, grndually denoised toward the last frame. NMNIST provides typical task early classification time scrics.
59

---

Published as a conference paper at ICLR 2021
M SUPPLEMENTARY EXPERIMENT ON MOVING MNIST DATABASE
Prior to the experiment on Nosaic MNIST, we conducted a preliminary experiment on the Moving MNIST (MMNIST) database. 1st, 2nd, 3rd, and 5th-order SPRT-TANDEM were compared to the LSTM-m. Hyperparameters of each model were independently optimized with Optuna. The result plotted in Figure 14 showed that the balanced accuracy the SPRT-TANDEM, peaked and reached the plateau phase only after two or three frames. This indicated that each of the frames in MMNIST contained too much information so that a well-trained classifier could classify a video easily, Thus, although our SPRT-TANDEM outperformed LSTM-m with large margin, we decided to design the original database, Nosaic MNNIST (NMNIST) for the carly-classification task. NMNIST contains videos with noise-buried handwritten digits, gradually denoised towards the end of the videos, increasing mean hitting time compared to the MMNIST.
MMNIST SAT curve
98.5
Balanced accuracy (96
98.0
98.55
97.5
I
98.50
97.0
98.45
10
15
96.5
onder TANDEM
96.0
ender
95.5
10
20
Mean hitting time (#frames)
Figure 14: Speed-accuracy tradeoff (SAT) curves of the Moving MNIST database. Error bars show standard mean (SEM).
60

---

Published as a conference paper at ICLR 2021
N SUPPLEMENTARY ABLATION EXPERIMENT
In addition to the ablation experiment presented Figure 3 which is calculated with 1st-order SPRI-TANDEM, we also conduct an experiment with 19th-order SPRT-TANDEM. The result shown in Figure is qualitatively in line with Figure 3e: the Lmulttppet has an advantage at the early phase with few data samples, while the LLLR leads the higher final balanced accuracy at the late phase, and using both loss functions the best SAT curves can be obtained.
NMNIST SAT
99.6
TANDEM
99.5
Balanced accuracy
99.4
99.3
99.2
99.1
4
10
20
Mean hitting time (#frames)
Figure Speed accuracy tradeoff (SAT) curves experiment bars show the standard error of the mean (SEM).
SPRT-TANDEM NMNIST
61

---

Published as a conference paper at ICLR 2021
SUPPLEMENTARY REFERENCES
M. Abadi, A. Agarwal, Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, Goodfellow, A. Harp. G. Irving, M. Isard, Y. Jia, Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org
Armitage. Sequential analysis with more than two alternative hypotheses, and its relation to discriminant function analysis. Journal of the Royal Statistical Society, Series B (Methodological), 12(():137-144, 1950.
Ashby. A biased random walk model for two choice reaction times. Journal of Mathematical Psychology, 17:277-297,, 1983.
A. Bagnall, J. Lines, J. Hills, and A. Bostrom. Time-series classification with cote: The collective of transformation-bee based ensembles. IEEE Transactions on Knowledge and Data Engineering, 27(9): 2522-2535, 2015.
A. Bagnall. Time series classification with ensembles of elastic distance measures. Data Mining and Knowledge Discovery, 29, 06 2014.
C. W. Baum and V. V. Veeravalli. A sequential procedure for multihypothesis testing. IEEE Transactions on Information Theory, 40(6):1994-20)) 2007, Nov 1994.
N. H. Bingham, G. Peskir, N. H. Bingham, and G. Peskir. Optimal stopping and dynamic program- ming, 2006.
A. Borovkov. Muthematical Statistics. Gordon and Breach Science Publishers, 1998.
V. Campos, B. Jou, X. G. Nieto, J. Torres, and S.-F. Chang. Skip rnn: Learning to skip state updates in recurrent neural networks. In ICLR, 2018.
Carreira and A. Zisserman. Quo vadis, action recognition? a new model and the kinetics dataset. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 4724-4733, 2017.
A. Czarnecki. Positronium properties. arXiv preprint hep-ph/9911455 1999.
H. A. Dau, E. Keogh, K. Kamgar, C.-C. M. Yeh, Y. Zhu, S. Gharghabi, C. A. Ratanamahatana, Yanping, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. Batista. The ucr time series classification archive, October 2018.
K. Doya. Modulators of decision making. Nat. Neurosci. 1144)410-416, Apr 2008.
V. P. Dragalin, A. G. Tartakovsky, and V. V. Veeravalli. Multhhyothessis sequential probability ratio tests asymptotic optimality. IEEE Transactions on Information Theory, 45(7):244--2461, Nov 1999.
V. P. Dragalin, A. G. Tartakovsky, and V. V. Veeravalli. Multhhypothesis sequential probability ratio tests. accurate asymptotic expansions for the expected sample size. IEEE Transactions on Information Theory,
1383, July 2000.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2115 2011.
W. Edwards. Optimal strategies for seeking information: Models for statistics, choice reaction times, and human information processing. Journal of Mathematical Psychology, 2(2):312 - 329, 1965.
J. P. Gallivan, C. S. Chapman, D. M. Wolpert, and J. R. Flanagan. Decision-making in sensorimotor control. Nat. Rev. Neurosci, 19(9):51-533, 09 2018.
I. Gold and M. N. Shadlen. The neural basis of decision making, Annu. Rev. Neurosci,, 30:535-574, 2007.
62

---

Published as a conference paper at ICLR 2021
A. Graves. Generating sequences with recurrent neural networks, arXiv preprint arXiv:1308.088 2013.
K. Hara, H. Kataoka, and Y. Satoh. Learning spatio-temporal features with 3d residual networks for action recognition. 2017 IEEE International Conference Computer Vision Workshops (ICCVW), pp. 3154-3160, 2017.
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, Taylor, Berg, N. Smith, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. Del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-365 09 2020.
M. M. Hu, H. Sun, and N. J. Kasdin. Sequential generalized likelihood ratio test for planet detection with photon-counting mode. In S. B. Shaklan (ed.), Techniques and Instrumentation for Detection of Exoplanets IX, volume 11117, pp. 492 498. International Society for Optics and Photonics, SPIE, 2019.
A. Irle and N. Schmitz. On the optimality of the sprt for processes with continuous time parameter. Statistics: A Journal of Theoretical and Applied Statistics, 15(1):91-104, 1984.
Y.-S. Jeong, M. K. Jeong, and O. A. Omitaomu. Weighted dynamic time warping for time series classification. Pattern Recognition, 44(9):2231 - 2240, 201 Computer Analysis of Images and Patterns.
R. Johari, P. Koomen, L. Pekelis, and D. Walsh. Peeking a/b tests: Why it matters, and what do about it. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17 pp. 1517-1525, New York, NY. USA, 2017. Association for Computing Machinery.
N. Ju, D. HU, A. Henderson, and L. Hong. A sequential test for selecting the better variant: Online a/b testing, adaptive allocation, and continuous monitoring. In Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, WSDM '19 pp. 492-500, New York, NY, USA, 2019. Association for Computing Machinery.
Kanamori, Hido, and M. Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10(Jul::391-1445) 2009.
F. Karim, S. Majumdar, H. Darabi, and S. Chen. LSTM fully convolutional networks for time series classification. IEEE Access, 6: 6:1662-1669, 2018. ISSN 2169-3536. doi: 10.1109/ACCESSS2001 2779939.
R. Kate. Using dynamic time warping distances features for improved time series classification. Data Mining and Knowledge Discovery, 30, 05 2015.
H. Khan, L. Marcuse, and B. Yener. Deep density ratio estimation for change point detection. arXiv preprint arXiv:1909 19t.009999000..... 09876, 2019.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980. 2014.
S. Kira, T. Yang, and M. N. Shadlen. A neural implementation of wald's sequential probability rato test. Neuron, 85(4))861-8)) -73,, February 2015.
M. Kulldorff, L.. Davis, M. Kolezakt, Lewis, T. Lieu, and R. Platt. maximized sequential probability ratio test for drug and vaccine safety surveillance. Sequential Analysis, 30(1):58-78, 2011.
A. Kumar, A. Gupta, and S. Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 13.
T. L. Lai. Asymptotic optimality of invariant sequential probability ratio tests. Ann. Statist., 9(2): 318-333, 03 1981.
63

---

Published as a conference paper at ICLR 2021
K. W. Latimer, J. L. Yates, M. L. Meister, A. C. Huk, and J. W. Pillow. Single-trial spike trains in parietal cortex reveal discrete steps during decision becision-making. Science, 349(6244):184-8777 Jul 2015.
E. L. Lehmann and P. Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
J. Lines, S. Taylor, and A. Bagnall. Hive-cote: The hierarchical vote collective of transformation- based ensembles for time series classification. In 2016 IEEE 16th International Conference on
Data Mining (ICDM), pp. 1041-1046, 2016.
V. Lotov. Asymptotic expansions in sequential likelihood ratio test. Theory of Probability & Its Applications, 32(1):57-67, 1988.
MATLAB. version 9.3.0 (R20/7b). The Math Works Inc., Natick, Massachusetts, 2017.
S. M. McClure, D. I. Laibson, G. Loewenstein, and J. D. Cohen. Separate neural systems value immediate and delayed monetary rewards. Science, 306(5695):033-577,, Oct 2004.
H. Nam and M. Sugiyama. Direct density ratio estimation with convolutional neural networks with application in outlier detection. IEICE TRANSACTIONS on Information and Systems, 98(5): 1073-1079, 2015.
E. Nikishin, P. Izmailov, B. Athiwaratkun, D. Podoprikhin, T. Garipov, P. Shvechikov, D. Vetrov, and A. G. Wilson. Improving stability in deep reinforcement learning with weight averaging. In Uncertainty in artificial intelligence workshop on uncertainty in Deep learning, 2018.
G. Okazawa, C. F. Hatch, A. Mancoo, C. K. Machens, and R. Kiani. The geometry of the rep- resentation of decision variable and stimulus difficulty in the parietal cortex. bioRxiv, 2021.
doi: 2221/01/04/2021.002 01 04 425244
URL http:::/t///it wiibiioo orriiiivv.. org/ content/errt Publisher: Cold Spring Harbor Laboratory _eprint: 44..444....4.llllppppp
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
J. D. Roitman and M. N. Shadlen. Response of neurons in the lateral intraparietal area during combined visual discrimination reaction time task. J. Neurosci., 22(11))945,-448, Nov 2002.
P. H. Rudebeck, M. E. Walton, A. N. Smyth, D. M. Bannerman, and M. F. Rushworth. Separate neural pathways process different decision costs. Nat. Neurosci., 161:1166111168 Sep 2006.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back-propagating errors. Nature, 323:533-536, 1986.
P. Schäfer and U. Leser. Multivariate time series classification with weasel+ muse. arXiv preprint 17X1::7111.11444 2017.
M. N. Shadlen, R. Kiani, W. Newsome, J. Gold, D. M. Wolpert, A. Zylberberg. J. Ditterich, V. de Lafuente, T. Yang, and J. Roitman. Comment on "Single-trial spike trains in parietal cortex reveal discrete steps during decision-making" Science, (51 1406, Mar 2016.
J. Sochman and J. Matas. Waldboost learning for time constrained sequential detection. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '05), volume 2, pp. 150-156 vol. 2, June 2005.
M. Stone. Models for choice-reaction time. Psychometrika, 25(3);251-260 September 1960.
M. Sugiyama, T. Suzuki, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe. Direct impor- tance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics, 60(4):699-746, 2008
64

---

Published as a conference paper at ICLR 2021
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation: A comprehensive review (statistical experiment and its related topics). 2010.
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012.
C. Tanaka, K. Doya, G. Okada, K. Ueda, Y. Okamoto, and S. Yamawaki. Prediction of immediate and future rewards differentially recruits cortico-basal ganglia loops. Nat. Neurosci., 7(8):887-893, Aug 2004.
A. Tartakovsky, Sequential methods in the theory of information systems (in Russian). Radio i Svyaz', Moscow, 1991.
A. Tartakovsky. Asymptotically optimal sequential tests for nonhomogeneous processes. Sequential Analysis, 17, 04 1999.
A. Tartakovsky, I. Nikiforov, and M. Basseville. Sequential Analysis: Hypothesis Testing and Changepoint Detection. Chapman & Hall/CRC, 1st edition, 2014.
V. V. Veeravalli and C. W. Baum. Asymptotic efficiency of a sequential multihypothesis test. JEEE Transactions Information Theory, 41(6): 1997, Nov 1995.
Viola and M. Jones. Rapid object detection using boosted cascade of simple features. In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern pp. I-1, Dec 2001.
Recognition, CVPR 2001, volume
Virtanen, R. Gommers, T. Oliphant, M. Haberland, Reddy, D. Cournapeau, Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. Jarrod Millman, N. Mayorov, A. R. J. Nelson, Jones, Kern, E. Larson, C. Carey, i. Polat, Y. Feng. E. W. Moore, J. Vand erPlas, D. Laxalde. J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, Pedregosa, P. van Mulbregt, and Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:
261-272, 2020.
Z. Wang, W. Yan, and T. Oates, Time series classification from scratch with deep neural networks: A strong baseline. In 2017 International Joint Conference on Neural Networks (IJCN), pp.
1578-1585, 2017.
L. Wei and E. J. Keogh. Semi-supervised time series classification. In KDD '06, 2006.
X. Xiong and F. De la Torre. Supervised descent method and its applications to face alignment. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, pp. 532-539, June 2013.
K. Yang and C. Shahabi. An efficient nearest neighbor search for multivariate time series. Informa- fion and Computation, 205(1) (:655 98, 2007.
65


Reviews:
[{"review_id": "vgWfiNrpu3N", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors propose how to use the neural networks to estimate the posteriors for each label y for the log likelihood ratio (LLR) estimation. The LLR estimation is performed using the multivariate inputs from the windows of time series, and it is used for the SPRT criterion without conventional iid assumption. \n\nThe paper contains an interesting idea of using the neural networks for the prediction of likelihoods and accumulating the information for the conventional sequantial probability ratio test (SPRT), which is well known for explaining the speed-accuracy tradeoff for decision making. The experimental results using various datasets show the relevance of the algorithm in terms of improving the speed-accuaracy tradeoff. \n\nThe authors presented a reasonable combination of two different objective functions: LLLR and L_multiplet. Though the authors did not mention explicitly, one is the objective for LLR which is ill-posed because pairs of high-biased neural network outputs can result in a small LLR by preserving only the ratio of the outputs correct. The other is the posterior objective (L_multiplet) which will alleviate the ill-posedness of the first objective by making the outputs of neural networks as close as possible to the correct one though they do not use those posteriors once it can estimate the LLR correctly.\n\nMy question about this paper is the learning procedure. For LLLR training, there is no need for the sync of x^(t) for different ys. I don’t see the explanation about choosing the index t in LLLR.\n\nIn the paragraph below Eq. (6), I don't understand what it means by the KL divergence between two ratios.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Zcfreyn-Ub", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "[EDITED AFTER DISCUSSION: My concerns are largely addressed and the paper is now stronger. I very much hope to see it at the conference, and have updated my review and rating accordingly.]\n\nThe paper proposes a new algorithm for early classification of sequential data, exploiting approaches to density ratio estimation to enable applying a sequential probability ratio test-type algorithm on perceptually rich data with no explicit likelihood. The algorithm is trained using a novel density ratio estimation loss alongside more standard cross-entropy, and shows strong performance on a number of provided benchmarks, including on a new variant of sequential MNIST. The paper claims ability to control speed-accuracy tradeoff in early classification, and applying the Wald SPRT on arbitrary sequential data. \n\nI enjoyed reading this paper: it combines two ideas (sequential likelihood ratio testing and density ratio estimation) in a way that appears obvious after the fact, but as often with these sort of post-hoc obvious ideas, is novel to my knowledge, and elegant. Trying to get something like the SPRT working beyond pairs of simple hypotheses has been under investigation for over half a century, and this paper is a worthwhile attempt. The empirical results look pretty good as well. \n\nAt the same time, I think the paper does overstate the benefit of the theoretical connection to the classical SPRT and previous non-i.i.d. extensions, and doesn't engage sufficiently with the challenges of stopping rules. I discuss these issues in more detail next, and conclude with some minor points about presentation, background work, and analysis. \n\n# Connections to the classical SPRT # \nThe paper claims to extend Wald's SPRT to non-i.i.d. data, and in particular its optimality properties. This includes claims in section 1 (on approaching Bayes-optimality and extending the Wald SPRT to arbitrary sequential data), at the beginning of section 4 (on how the LLLR enables performing the SPRT, which is provably optimal), and in section 5 (on approaching if not reaching Bayes-optimality). As far as I can tell, the paper does not enable performing the Wald SPRT on arbitrary data, and does not provide a provably optimal sequential test. The claim that it approaches optimality in any formal sense is likewise not supported as far as I can tell. Broadly, a sequential test consists of an update rule and a decision rule -- for the SPRT the update rule and decision rule are both optimal. For most extensions (non-i.i.d., multi-hypothesis, deadlines, etc), the update still follows Bayes' rule, and the optimal decision rule can only be found numerically (if at all), so some heuristic is given. This heuristic is often a fixed threshold, with asymptotic optimality guarantees). SPRT-TANDEM seems to be in the family of such extensions: it still applies Bayes' rule sequentially, and the stopping is given based on a fixed threshold. Thus, its optimality is asymptotic at best, and stronger claims are not supported. Furthermore, the paper doesn't make it clear whether the standard conditions for asymptotic optimality apply to the SPRT-TANDEM either: in my rough understanding, the standard asymptotic result is as risk goes to 0 (or equivalently, the LLR goes to infinity, and the threshold goes to infinity). I'm not sure that we know the SPRT-TANDEM LLR to grow in this way, and empirically, it seems like the LLR saturates to some fixed value, especially with high-order N, which means high threshold values are not achievable and risk cannot go to 0. We should also expect the SPRT-TANDEM to depart further from optimality as the model approaches the end of the video (since the optimal thing to do there is to gradually collapse the decision boundary, as the appendix reminds us). I recommend moderating these claims regarding optimality, and / or strengthening the results if possible. \n\n# Stopping rules # \nThe paper does not provide guidance on stopping rules, which limits practical use, and does not report on the thresholds used to generate the speed-accuracy tradeoff figures. Presumably, the simplest thing is to set the threshold to the desired accuracy (which I think will do the right thing in the no-overshoot case?). Does this work for SPRT-TANDEM to achieve a given accuracy? If not, is there another heuristic that applies? I recommend addressing this question in more detail. Relatedly, the paper criticizes Mori et al. 2018 and Hartvigsen et al. 2020 for using a separate objective for determining stopping and accuracy, but in fact SPRT-TANDEM would likewise need some dynamic programming or RL solver to have an optimal stopping policy, similarly to that prior work. I recommend providing explicit guidance about stopping rules, and moderating the claims relative to prior work. Solving for an optimal stopping policy would also strengthen the paper. \n\n# Presentation issues #\nThe paper tries to cram a lot into the short ICLR format, supported by an extensive appendix. I appreciate the inclusion of classical SPRT results in the appendix, which may be unfamiliar to the ICLR audience. At the same time, the main text does not provide much intuition about the novel LLLR loss, which is given very little explanation considering it is presented as one of the paper's major contributions. The relationships and improvements relative to KLIEP are presented too tersely, and a reader not familiar with that precise method will not know what to make of them. The paper would do better to provide more exposition there, perhaps in favor of moving the results tables to the appendix (since they show the same information as figure 3 as far as I can tell).  \nIn addition, the SAT curves are too busy, small, and hard to read. For the main document, I would recommend increasing font and symbol sizes, and presenting fewer orders of SPRT-TANDEM models (e.g. just order-1 and best-order), and fewer hitting times per model (e.g. there is no need to present the accuracy at every one of the last 10 frames if the accuracies are all the same there). Finally, the LLR trajectory figures can use partial transparency to make the individual traces easier to see. \n\n# Additional/minor points #\n- **Background work**. I appreciated the fairly detailed review of past work related to the SPRT. A few notable missing pieces related to neuroscience are work predating Kira et al. 2015 in applying the SPRT to neural data (e.g. Gold & Shadlen 2002) and to human decision making more broadly (e.g. Stone, 1960; Edwards, 1965, Ashby 1983, and others). Missing work related to practical applications of the SPRT includes Johari et al. 2017, Ju et al. 2019, and others from the domain of internet experimentation. None of these are critical omissions, I only bring them up considering the already-broad review. \n- **Statistical analysis**.  Given that the paper has a clear hypothesis (that SPRT-TANDEM outperforms competitors), it seems more sensible to perform repeated measures regression with planned contrasts rather than post-hoc testing for significance. This is a minor issue. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "WH5NrrBA7Mt", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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\nThis work introduces SPRT-TANDEM an algorithm to train a sequential probability ratio test (SPRT) as a neural network. This network is then used to discriminate between two hypotheses as fast as possible (seeing the smallest number of observations in a sequence) while maintaining a certain level of accuracy. The main contribution of this work is to enable Wald's SPRT without actual knowledge of the ratio, learning a neural network to model it.   \n\n# Major comments\n## Pros:\nThe paper does a good job of introducing the problem statement, that is the \"fast\" classification of sequential data. The algorithm introduced is well motivated and bridges the gap between \"classic statistical\" methods and machine learning approaches for sample-efficient time series classification. The experimental, results though not outstanding, show that SPRT-TANDEM outperforms other deep learning methods.  These experiments are insightful by the fact that they compare the performance of the different methods for different mean hitting time. Overall the paper is pleasant to read and introduce a new method that could be helpful for some practitioners.\n\n## Cons:\n1) The related work is quite superficial (even taking into account app B). In particular, I would have liked a deeper comparison with LSTM-s/m and EARLIEST, discussing the drawback/advantages of these methods with respect to SPRT-TANDEM.\n2) In the proof of 4, just before eq 70 you say: \"Let us assume that the process {x(s)}ts=1 is i.i.d., namely -> eq 70\". This seems wrong to me. The assumption you're making there is that the process has independent component conditionally to the class y (e.g for t = 2, the Bayesian network: x_1 <- y -> x_2). This is still a reasonable hypothesis however this is not equivalent to simply assuming the process is iid (which then would mean for t = 2, the Bayesian network: x_1 -> y <- x_2 and would not make eq 70 correct).\n3) The three tasks on which you test the models seem to be quite well solved after a few samples on average for all models. I think it would be worth testing the models on tasks that require more samples for reaching good performance and maybe where the temporality required (hyperparameter N) is larger.\n4) It is not very clear to me what are the respective roles of LLLR and MCEL. I do not understand why both are useful, I would have thought that CE in itself would be sufficient. The ablation study you did is interesting but I would have liked to get further insights about what is happening there.\n5) I believe that testing your method on a toy problem for which the correct ratio is known would be insightful about the \"optimality\" of your method.\n\n# Minor comments\n- Page 2 \"As an .. orDEr\"\n- Loss written with capital everywhere.\n- How to choose N: You say that training the features extractor is faster than the integrator's however it is not clear to me how you can train these two parts independently from each other.\n- For comparison on NMNIST it could be interesting to see the performance of a simple classifier on the 19th image alone.\n- You're talking about Optuna for hyperparameter optimization, this is unknown to me. A word about how it is working could be nice.\n- Why are the number of trials different?\n- The purpose of SPRT-TANDEM is to be as fast as possible, it could be interesting to clearly state somewhere how comparable are the different methods in term of computing times even if they are very close to each other.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4SzzKydnzAe", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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:\nThis work describes a new algorithm, SPRT-TANDEM, for classifying sequential data as early as possible. It builds upon several previous works (SPRT, KLIEP, and deep neural networks) to propose a well-engineered and well-motivated solution for the considered problem.\n\nSTRENGTHS:\n- This work is exceptionally documented, on all accounts: related work is multidisciplinary, broad and thorough; all losses and algorithms are derived from first principles; experiments are varied and include every last details regarding their setups, evaluation metrics or outcomes.\n- Albeit only briefly mentioned in the main, the method has strong theoretical foundations, as documented in Appendix A. \n- Experiments show stronger benchmark results than the considered baselines (LSTM-m/s, EARLIEST and 3DResNet), on a quite diverse set of experiments (images, videos).\n- Although the classification of sequential data is not among the most popular topics, I believe this contribution to be significant for the field. \n\nWEAKNESSES:\n- I believe the 8-page limit of ICLR does make this work justice, given the extensive documentation that comes along in the supplementary materials. The short format of the main paper makes it difficult at places to fully follow or appreciate the contributions presented in this work. (Should this paper be rejected, I would recommend it to be submitted to JMLR, which format is certainly a better fit.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "0ah7qI9IRNz", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "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": "The paper proposes a novel SPRT-TANDEM algorithm minimizing the divergence between estimated and true Log-Likelihood Ratios of SPRT and making it thereby Bayes optimal for various real-world applications. The paper is very well written, clear and scientifically sound and provides  extensive contributions, e.g. a database in addition to the algorithm. Performance of the algorithm is demonstrated via three experiments.  \n\nPrevious research is given sufficient credit. The only thing I would still like to see more is the discussion at the conclusions. Why does this seemingly simple modification to the existing SPRT method provide so superior performance.\n\nThe appendices are referred a lot in the text but they are missing from the paper?\n\nA very minor comment: The following sentence is a bit vaguely written:\nLong short-term memory (LSTM)-s/LSTM-m impose monotonicity on classification ...\nI guess it should be : Long short-term memory (LSTM) variants LSTM-S and LSTM-M impose monotonicity on classification ...\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a density ratio estimation approach to make the early decision for sequential data. The main contribution of this paper is the mathematical soundness of the proposed algorithm and all reviewers are unanimously positive about this paper with pretty good scores (7, 8, 6, 9, 7). However, despite the good scores, the verbal comments by the reviewers are not very strong except for one reviewer (R2); the reviewer with the highest score (9) did not provide detailed information about his/her rating. Also, the evaluation of this work is relatively weak because synthetic or simple datasets were employed for the experiment and the baseline methods are too straightforward. Also, it is not clear how the proposed algorithm can handle the data with sparse observations (data with idle times in the middle). Moreover, it does not provide rigorous stopping criteria although the authors proposed a simple method to determine the threshold, which is contradictory to the main objective of the proposed algorithm---making early predictions on sequential data---because the method requires "plotting the speed-accuracy tradeoff curve on the test dataset." This response implies that it at least requires a withheld dataset. Although this issue can be regarded as a separate problem, the paper could have provided an ablation study with respect to the criteria.

Considering all these facts--high scores but relatively low supports and confidences, and practical limitations, I would recommend accepting this paper as a spotlight presentation.

Decision: Accept (Spotlight)