* [1] E. Abi Jaber, E. Miller, and H. Pham, Linear-Quadratic control for a class of stochastic Volterra equations: solvability and approximation, Ann. Appl. Probab., 31 (2021), 2244–2274.
  * [2] E. Abi Jaber, E. Miller, and H. Pham, Integral operator Riccati equations arising in stochastic Volterra control problems, SIAM J. Control Optim., 59 (2021), 1581–1603.
  * [3] N. Agram and B. Øksendal, Malliavin calculus and optimal control of stchastic Volterra equations, J. Optim. Theory Appl., 167 (2015), 1070–1094.
  * [4] B. D. O. Anderson and J. B. Moore, Linear Optimal Control, Prentice-Hall, Englewood Cliffs, New Jersey, 1971.
  * [5] M. Athens, Special issues on linear-quadratic-Gaussian problem, IEEE Trans. Auto. Control., 16 (1971), 527–869.
  * [6] A. Bensoussan, Estimation and control of dynamical systems, Heidelberg, Springer, 2018.
  * [7] S. Chen and J. Yong, A linear quadratic optimal control problem for stochastic Volterra integral equations, Control theory and related topics - in memory of professor Xunjing Li, Fudan university, China. 44–66.
  * [8] F. Comte and E. Renault, Long Memory in Continuous-time Stochastic Volatility Models, Math. Finance, 8 (1998), 291–323.
  * [9] O. El Euch and M. Rosenbaum, The characteristic function of rough Heston models, Math. Finance, 29 (2019), 3–38.
  * [10] O. El Euch and M. Rosenbaum, Perfect hedging in rough Heston models. Ann. Appl. Probab., 28 (2018), 3813–3856.
  * [11] J. Gatheral, T. Jaisson and M. Rosenbaum, Volatility is rough, Quant. Finance, 18 (2018), 933–949.
  * [12] Y. Hamaguchi, Extended backward stochastic Volterra integral equations and their applications to time-inconsistent stochastic recursive control problems, Math. Control Relat. Fields, 11 (2021), 433–478.
  * [13] C. Hernández and D. Possamai, Me, myself and I: a general theory of non-Markovian time-inconsistent stochastic control for sophisticated agents, preprint, arXiv:2002.12572, 2020.
  * [14] C. Hernández and D. Possamai, A unified approach to well-posedness of type-I backward stochastic Volterra integral equations, Electron. J. Probab., 26 (2021), 1–35.
  * [15] C. Hernández, On quadratic multidimensional type-I BSVIEs, infinite families of BSDEs and their applications, preprint, arXiv:2111.11131, 2021.
  * [16] Q. Lei and C. S. Pun, Nonlocal fully nonlinear parabolic differential equations arising in time-inconsistent problems, preprint, arXiv:2110.04237, 2021.
  * [17] X. Li and J. Yong, Optimal control theory for infinite dimensional systems, Birkhäuser, Boston, 1995.
  * [18] Q. Lü, Well-posedness of stochastic Riccati equations and closed-loop solvability for stochastic linear quadratic optimal control problems, J. Differential Equations, 267 (2019), 180-227.
  * [19] J. Ma, P. Protter and J. Yong, Solving forward-backward stochastic differential equations explicitly — a four step scheme, Probab. Theory Related Fields, 98 (1994), 339–359.
  * [20] J. Ma, Z. Wu, D. Zhang, and J. Zhang, On well-posedness of forward-backward SDEs — a unified approach, Ann. Appl. Probab., 25 (2015), 2168–2214.
  * [21] J. Ma and J. Yong, Forward-Backward Stochastic Differential Equations and Their Applications, Lecture Notes in Math., vol. 1702, Springer-Verlag, Berlin, 1999.
  * [22] J. Ruan, Numerical methods for high dimensional path dependent PDEs driven by stochastic Volterra integral equations, PhD Dissertation, Univ. Southern California, 2020.
  * [23] Y. Shi, T. Wang, and J. Yong, Optimal control problems of forward-backward stochastic Volterra integral equations, Math. Control Rel. Fields, 5 (2015), 613–649.
  * [24] J. Sun, X. Li, and J. Yong, Open-loop and closed-loop solvabilities for stochastic linear quadratic optimal control problems, SIAM J. Control Optim., 54 (2016), 2274–2308.
  * [25] J. Sun and J. Yong, Stochastic linear-quadratic optimal control theory: open-loop and closed-loop solutions, Springer Briefs in Mathematics, 2020.
  * [26] J. Sun and J. Yong, Stochastic linear-quadratic optimal control theory: differential games and mean-field problems, Springer Briefs in Mathematics, 2020.
  * [27] F. Viens and J. Zhang, A martingale approach for fractional Brownian motions and related path dependent PDEs, Ann. Appl. Probab., 29 (2019), 3489–3540.
  * [28] H. Wang and J. Yong, Time-inconsistent stochastic optimal control problems and backward stochastic volterra integral equations, ESAIM Control Optim. Calc. Var., 27 (2021), 22.
  * [29] H. Wang, J. Yong, and J. Zhang, Path dependent Feynman–Kac formula for forward backward stochastic Volterra integral equations, Ann. Inst. Henri Poincaré Probab. Stat., to appear; arXiv:2004.05825.
  * [30] T. Wang, Linear quadratic control problems of stochastic Volterra integral equations, ESAIM: Control Optim. Cal. Var., 24 (2018), 1849–1879.
  * [31] T. Wang, Necessary conditions of Pontraygin’s type for general controlled stochastic Volterra integral equations, ESAIM: Control Optim. Cal. Var., 26 (2020), 16.
  * [32] T. Wang and J. Yong, Backward stochastic Volterra integral equations—representation of adapted solutions, Stochastic Process. Appl., 129 (2019), 4926–4964.
  * [33] T. Wang and H. Zhang, Optimal control problems of forward-backward stochastic Volterra integral equations with closed control regions, SIAM J. Control Optim., 55 (2017), 2574–2602.
  * [34] J. Yong, Linear forward-backward stochastic differential equations with random coefficients, Probab. Theory Relat. Fields, 135 (2006), 53–83.
  * [35] J. Yong, Well-posedness and regularity of backward stochastic Volterra integral equations, Probab. Theory Related Fields, 142 (2008), 21–77.
  * [36] J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations, Springer-Verlag, New York, 1999.
  * [37] J. Zhang, Backward Stochastic Differential Equations: From Linear to Fully Nonlinear Theory, Springer, New York, 2017.


#  Stop&Hop: Early Classification of Irregular Time Series

Thomas Hartvigsen  Massachusetts Institute of Technology<EMAIL_ADDRESS>,
Walter Gerych  Worcester Polytechnic Institute<EMAIL_ADDRESS>,  Jidapa
Thadajarassiri  Worcester Polytechnic Institute<EMAIL_ADDRESS>,
Xiangnan Kong  Worcester Polytechnic Institute<EMAIL_ADDRESS>and  Elke
Rundensteiner  Worcester Polytechnic Institute<EMAIL_ADDRESS>
(2022)

###### Abstract.

Early classification algorithms help users react faster to their machine
learning model’s predictions. Early warning systems in hospitals, for example,
let clinicians improve their patients’ outcomes by accurately predicting
infections. While early classification systems are advancing rapidly, a major
gap remains: existing systems do not consider irregular time series, which
have uneven and often-long gaps between their observations. Such series are
notoriously pervasive in impactful domains like healthcare. We bridge this gap
and study early classification of irregular time series, a new setting for
early classifiers that opens doors to more real-world problems. Our solution,
Stop&Hop, uses a continuous-time recurrent network to model ongoing irregular
time series in real time, while an irregularity-aware halting policy, trained
with reinforcement learning, predicts when to stop and classify the streaming
series. By taking real-valued step sizes, the halting policy flexibly decides
exactly when to stop ongoing series in real time. This way, Stop&Hop
seamlessly integrates information contained in the timing of observations, a
new and vital source for early classification in this setting, with the time
series values to provide early classifications for irregular time series.
Using four synthetic and three real-world datasets, we demonstrate that
Stop&Hop consistently makes earlier and more-accurate predictions than state-
of-the-art alternatives adapted to this new problem. Our code is publicly
available at https://github.com/thartvigsen/StopAndHop.

Time Series, Irregularly-Sampled Time Series, Early Classification,
Reinforcement Learning, Recurrent Neural Network, Deep Learning

††journalyear: 2022††copyright: acmlicensed††conference: Proceedings of the
31st ACM International Conference on Information and Knowledge Management;
October 17–21, 2022; Atlanta, GA, USA††booktitle: Proceedings of the 31st ACM
International Conference on Information and Knowledge Management (CIKM ’22),
October 17–21, 2022, Atlanta, GA, USA††price: 15.00††doi:
10.1145/3511808.3557460††isbn: 978-1-4503-9236-5/22/10††ccs: Computing
methodologies Neural networks††ccs: Computing methodologies Supervised
learning by classification

##  1\. Introduction

Background. Early Classification algorithms classify time series before
observing every timestep (Xing et al., 2009). These powerful methods give
users enough time to react in time-sensitive domains. For example, early
warning systems help clinicians improve their patients’ outcomes (Yala et al.,
2022; Zhao et al., 2019). Still, the best time to classify depends on the task
and a given time series because signals are often sporadic. Too early and it
may be a false alarm, fatiguing the end-user (Graham and Cvach, 2010). Too
late and the user cannot react. An ideal classification is both early and
accurate, but these goals conflict: an early classification may ignore
relevant future data, as illustrated in Figure 1.

Figure 1. Early Classification of Irregular Time Series. Purple vertical
dashed lines indicate the prediction time, disregarding all future data. The
goal is to classify irregular series while using as little of the timeline as
possible.

State-of-the-art. Early classification of time series (ECTS) is advancing
quickly. Recent approaches overcome the poor scaling and false alarms inherent
to classic ECTS (Wu et al., 2021) via reinforcement learning, predicting
whether to Stop or Wait at every step of an ongoing series (Martinez et al.,
2019; Hartvigsen et al., 2019, 2020; Yala et al., 2022). This approach
counteracts overconfident classifiers, resulting in better predictions. In
addition, by using neural networks they classify multivariate time series
seamlessly, a setting known to challenge similarity search methods (Ghalwash
et al., 2013, 2014; He et al., 2015; Ye and Keogh, 2009; Xing et al., 2011).
However, the state-of-the-art methods, along with all prior ECTS algorithms,
disregard uneven gaps between observations.

Figure 2. Comparing our problem, early classification of irregular time series
(d) to other related problems. (a) Shows standard time series classification,
using all possible observations. (b) Shows standard early classification of
time series, requiring evenly-spaced observations. (c) Shows standard
irregular time series classification of irregular time series, using all
possible observations.

Knowledge Gap. Despite rapid improvements, there remain ample opportunities to
broaden the reach of early classifiers. In particular, existing early
classifiers require that their input time series have even spaces between
observations: they decide whether to stop early whenever any new observation
arrives. Meanwhile, irregular time series (ITS), which have uneven and often-
large gaps between observations, are ubiquitous in impactful domains like
healthcare (Lipton et al., 2016), climate science (Bahadori and Liu, 2012),
and astronomy (Richards et al., 2011). In a hospital, for example, clinicians
quantify their patient’s health over time by taking measurements (laboratory
tests, vital signs, microbiology tests, etc.). Such ITS are often multivariate
and irregular between variables: measuring one variable does not mean
measuring all.

To model ITS data effectively, we must acknowledge and leverage asynchronous
observations (Rubanova et al., 2019). Specifically, successful ITS classifiers
should consider patterns of irregularity; different classes often have unique
signatures in their observations’ timing (Lipton et al., 2016). For example,
diabetes-risk patients receive more blood sugar tests while in the hospital.
The early classification community has yet to consider this common, rich, and
general type of time series data.

Problem Definition. Our work is the first to consider early classification of
irregular time series, which is an open, impactful, and challenging real-world
problem. For a previously-unseen ITS $X$, we seek one small (early) real-
valued time $\tau$ at which the entire series $X$ may be classified accurately
without using any observations later than $\tau$. The goals of earliness and
accuracy naturally conflict because early predictions are usually made at the
expense of accuracy (fewer observations have been collected). This is a multi-
objective problem, which we compare to other settings in Figure 2. A key
application of this problem is in healthcare, where clinicians require early
and accurate predictions, yet use almost entirely with irregular time series
(Jane et al., 2016; Yala et al., 2022; Zhao et al., 2019; Alavi et al., 2022).

Challenges. Our problem is challenging for three main reasons:

  * •

Conflicting Objectives: Earliness and accuracy contradict each other, so a
balance must be struck, where the relative importance of each goal may change
depending on the task. This trade-off may also change for each instance.

  * •

Unknown Halting Times: The optimal halting time $\tau$ is unobserved and
unavailable for supervision or evaluation.

  * •

Irregular, multivariate observations: ITS are often sparse and multivariate.
This is notoriously challenging for most machine learning methods, which
typically require fixed-length and regularly spaced inputs. Signals for
earliness and accuracy can also be found in patterns of missingness.

Proposed Method. We overcome these challenges, proposing the first early
classifier for irregular time series, which we refer to as Stop&Hop in
reference to our key idea. Stop&Hop instantiates a general and modular
solution, integrating three essential components. First, a continuous-time
recurrent Prefix Encoder embeds ITS data up to a candidate halting time,
expanding on recent successes in representation learning for ITS. This handles
irregular, multivariate observations by producing dense vector representations
of ongoing time series. Then, a reinforcement learning-based Halting Policy
Network decides whether or not to Stop and predict or Wait for more data. If
it chooses to Wait, it predicts for how long and Hops forward in time before
reactivating. Thus we formulate the early classification problem as a
Partially-Observable Markov Decision Process with actions that operate on
varying time scales. This formulation lets us encourage early stopping, even
though the true halting times are unknown. The policy can thus adapt to
variations in the irregularity of each input instance, using the observations’
timing to inform the halting time. Once the Halting Policy Network stops, a
Prefix Classifier Network classifies the series. All components are trained
jointly so that the conflicting objectives, earliness and accuracy, are easily
balanced.

Advancing beyond prior methods, Stop&Hop
[baseline=(char.base)][shape=circle,draw,inner sep=0.7pt] (char) 1; accesses
more possible prediction times, and
[baseline=(char.base)][shape=circle,draw,inner sep=0.7pt] (char) 2; learns
directly from observation timing, a new source of information for early
classification systems. These improvements make a new state-of-the-art early
classifier.

Contributions. Our contributions are as follows:

  1. (1)

We define the open problem Early Classification of Irregular Time Series,
bridging a major gap between modern early classifiers and real time-sensitive
decision making.

  2. (2)

Our method, Stop&Hop, is the first solution to this problem, integrating a
continuous-time representation learner with two cooperative reinforcement
learning agents.

  3. (3)

We show that Stop&Hop classifies ITS earlier and more-accurately than state-
of-the-art alternatives. We also show that Stop&Hop learns to stop exactly
when signals arrive using four synthetic datasets, leading to the earliest-
possible classifications.

##  2\. Related Work

Early Classification of Time Series. Early Classification of Time Series
(ECTS) is a machine learning problem: correctly predict the label of a
streaming time series using as few observations as possible (Gupta et al.,
2020). Solutions choose one early timestep per time series at which the whole
instance is classified (without cheating and looking at future values).
Classifying sequences early is classically targeted at time series (He et al.,
2015; Xing et al., 2011; Xing et al., 2012; Ghalwash et al., 2014, 2013; Mori
et al., 2018; Schäfer and Leser, 2020). Most recent approaches (Hartvigsen et
al., 2020, 2019; Martinez et al., 2019; Dennis et al., 2018; Ebihara et al.,
2020) have turned to deep learning, extending beyond traditional methods for
univariate time series (Mori et al., 2017; Xing et al., 2012, 2009; Xing et
al., 2011), which scale poorly by exhaustively searching for discriminative
subsequences (He et al., 2015). The current best solution is to frame this
problem as a Partially-Observe Markov Decision Process, where at each
regularly-spaced timestep, a policy decides whether or not to stop and predict
the label. Some halt RNNs early (Hartvigsen et al., 2019, 2020) while others
use Deep Q-Networks (Martinez et al., 2019).

Figure 3. Stop&Hop Architecture. Given a timestamp $t^{\prime}$, an embedding
is computed for all values and irregularity prior to $t^{\prime}$. Then, a
classifier attempts to classify the series. The halting policy network then
uses this classification and the embedding to decide whether or not to stop
or, if not, how long to wait before repeating this process.

A major limitation of existing ECTS methods is their reliance on inputs being
regularly-spaced; they decide whether or not to halt at each possible
timestep. This does not account for missing values or gaps between
observations, features essential to classifying ITS (Che et al., 2018). In
ITS, the gaps between consecutive observations may even be large and
unpredictable, so waiting until the next value arrives has consequences.
Furthermore, many ITS are multivariate, and multiple variables are rarely
observed concurrently. This compounds issues with existing ECTS methods.
Further, the times at which observations arrive can itself provide valuable
knowledge for accuracy (Lipton et al., 2016) and earliness. A successful
solution to our problem should take advantage of this extra source of
information.

Learning from Irregular Time Series. Standard machine learning techniques
often fail for ITS as they assume fixed-length and regularly-spaced inputs
(Shukla and Marlin, 2020), which are especially rare in important medical
settings (Sun et al., 2020). To bridge this gap, myriad recent works learn
from ITS directly, developing models that take irregular series as inputs.
Some approaches augment RNNs by either including auxiliary information such as
a missingness-indicator (Lipton et al., 2016) or time-since-last-observation
(Che et al., 2018) as extra features to preserve properties found in the
irregularity. Others build more complex value estimators by either learning
generative models (Li and Marlin, 2020), using gaussian kernel adapters
(Shukla and Marlin, 2019; Li and Marlin, 2016), set functions (Horn et al.,
2020), or including decay mechanisms in Recurrent Neural Networks (RNN) to
encode information-loss when variables go unobserved over long periods of time
(Mozer et al., 2017; Che et al., 2018). Some recent works have begun
parameterizing ordinary differential equations to serve as time series models
(Kidger et al., 2020; Lechner and Hasani, 2020; Rubanova et al., 2019; Jia and
Benson, 2019), Some very recent models have also begun to integrate attention
mechanisms into this estimation process (Shukla and Marlin, 2021; Chen and
Chien, 2021; Tan et al., 2020).

However, ITS model considers when to return predictions to end users in the
ongoing timeline. A key constraint of the early classification of irregular
time series problem is that when classifying a series at a particular point in
its timeline, we cannot use any future values. This constraint hinders the use
of methods that use all observations during interpolation (Shukla and Marlin,
2019, 2021) or ODE models that encode sequences backwards (Rubanova et al.,
2019). Such methods are quickly becoming pervasive (Kidger et al., 2020),
though creating online models for ITS remains a burgeoning area (Morrill et
al., 2021; Cheng et al., 2020; Weerakody et al., 2021).

##  3\. Problem Formulation

Assume we are given a set of $N$ labeled irregular time series
$\mathcal{D}=\\{(X^{i},y^{i})\\}_{i=1}^{N}$. Each series $X$ is a collection
of one sequence of $T^{d}$ (timestep, value) pairs per variable $d$:
$X=\\{\\{(t^{d}_{j},v^{d}_{j})\\}_{j=1}^{T^{d}}\\}_{d=1}^{D}$ where each
sequence of timesteps is strictly increasing ($t^{d}_{1}<t^{d}_{2}<\dots
t^{d}_{T^{d}}$) and $v^{d}_{j}$ is the corresponding value of variable $d$ for
each timestep. $T^{d}$ denotes the number of observations for variable $d$.
$X$ is irregular in that typically $t_{i}^{j}\neq t_{i}^{k}$ and
$t_{i+1}^{j}-t_{i}^{j}\neq t_{i+2}^{j}-t_{i+1}^{j}$ for all $i$, $j$, and $k$.
Each label $y$ indicates to which of $C$ classes $X$ belongs. Our goal of
Early Classification of Irregular Time Series is to learn a function $f$ that
maps previously-unseen input time series to their accurate class labels $y$
based only on values observed prior to some early time $\tau$, which is an
unknown function of $X$. The smaller $\tau$ is, the better. However, fully
achieving both goals at the same time in practice is usually impossible since
early predictions are often made at the expense of accuracy as less of the
series has been observed. Thus we seek a tunable solution that balances
earliness and accuracy according to the task at hand.

##  4\. Method

We propose an intuitive first solution to the open Early Classification of
Irregular Time Series (ECITS) problem, which we name Stop&Hop and illustrate
in Figure 3. The ultimate goal of our proposed method is to predict the best
halting time $\tau$ for a given series so as to balance the cost of delaying a
prediction with the benefits of accuracy, according to the requirements of the
task at hand. Thus, one halting timestep $\tau$ is predicted per series $X$
along with a prediction $\hat{y}$ made using only observations made before
time $\tau$.

Since no ECITS solution exists, we first describe a general solution, which we
then instantiate as an architecture that builds on representation learning for
irregular time series and on deep reinforcement learning. A general solution
to ECITS iterates three steps: [baseline=(char.base)][shape=circle,draw,inner
sep=0.7pt] (char) 1; Predict a candidate halting time $t^{\prime}$ given only
variables recorded before $t^{\prime}$.
[baseline=(char.base)][shape=circle,draw,inner sep=0.7pt] (char) 2; Construct
a vector representation $h_{t}^{\prime}$ of the ongoing series $X$ that
captures patterns in both values and irregularity up to time $t^{\prime}$.
[baseline=(char.base)][shape=circle,draw,inner sep=0.7pt] (char) 3; Predict
whether or not to halt and classify $X$ at time $t^{\prime}$. If so, use
$h_{t^{\prime}}$ to classify $X$. If not, predict the next candidate halting
time $t^{\prime}$. Thus, a solution will march through the continuous timeline
with a step-size that is predicted by the model according to the observations
as they arrive. At each step, the model will decide whether or not to Stop and
return a classification.

Table 1. Basic Notation Notation |  Description
---|---
$D$ |  Variables per time series.
$\tau$ |  Predicted halting time.
$\hat{y}$ |  Predicted class label.
$t^{\prime}$ |  Candidate halting time.
$\pi_{\text{stop}}$ |  Stopping policy (chooses Stop or Wait).
$\pi_{\text{hop}}$ |  Hopping policy (chooses hop size).
$h_{t^{\prime}}$ |  Hidden state computed at time $t^{\prime}$.

Each component of this general solution solves one challenge of the ECITS
problem. First, learning when to try to stop is essential in the irregular
setting. This is in contrast to the standard ECTS setting where, with
knowledge that observations arrive on a fixed schedule, methods simply decide
whether or not to stop every time a new measurement arrives. Second, standard
supervised learning methods struggle to model ITS data as they are not fixed-
length. Learning dense representations of these data instead provides feature
vectors that are easy to learn from. Step three can then leverage the vast
success of deep learning to classify ongoing ITS.

This modular setup solves the ECITS problem and so we instantiate this idea
with solutions to each of the three sub-problems, integrating the two goals of
accuracy and earliness. First, a continuous-time recurrent network $R(\cdot)$
constructs a representation $h_{t^{\prime}}=R(X_{\leq{t^{\prime}}})$ where
$X_{\leq{t^{\prime}}}$ represents all observations made prior to a timestep
$t^{\prime}$. Next, a Halting Policy Network decides either to Stop, or Hop
forward in time to a new timestep $t^{\prime}\mathrel{{+}{=}}\Delta t$ where
$\Delta t$ is a real-valued Hop Size computed as a function of representation
$h_{t^{\prime}}$. This two-policy setup is novel for the ECTS literature.
Since incoming observations are irregular, our adaptive approach allows the
network to learn when to try and stop according to when observations arrive,
adding flexibility. During training, the halting policy is encouraged to
prefer both smaller (earlier) values $\hat{\tau}$ and accurate predictions.
Once the halting policy chooses to stop or the series ends, a classifier
network predicts the class label of $X$.

The rest of this section is organized as follows. We describe our
implementation of each component of Stop&Hop: Generating prefix embeddings
with a continuous-time RNN, a neural network for classifying prefix
embeddings, and deep reinforcement learning agents for halting early and
hopping effectively. Then, we describe how to train each component.

###  4.1. Embedding Irregular Time Series Prefixes

Stop&Hop learns to encode ongoing irregular time series via continuous time
representation learning, computing vector representations of a series $X$ at
real-valued timesteps. We refer to this as a Prefix Encoder, as it encodes the
prefixes of ongoing time series. There has been a recent surge in approaches
developed for representing ongoing ITS (Che et al., 2018; Rubanova et al.,
2019) and most use a recurrent component to encode the series at real-valued
timesteps in the continuous timeline:
$h_{t}^{\prime}=\mathcal{R}_{\theta}(X,t^{\prime})$, where $R(\cdot)$ is a
continuous-time recurrent neural network and $t^{\prime}$ is a real-valued
time. $h_{t}^{\prime}$ is thus a vector representing all dynamics of
observations in series $X$ prior to time $t^{\prime}$, including information
found in the irregularity of the values. The only constraint on architecture
design for $\mathcal{R}_{\theta}(\cdot)$ in the Early Classification setting
is that $h_{t}^{\prime}$ must only be computed with respect to values observed
earlier than $t^{\prime}$. This disables the use of methods that compute bi-
directional hidden states or use future values for imputation (Shukla and
Marlin, 2019). Further, we seek to model the irregularity itself, which can
inform both the classification accuracy and the earliness. Thus we compute
$h_{t^{\prime}}$ using the GRU-D (Che et al., 2018), denoted for variable step
sizes between embeddings. The hidden state and input values are decayed based
on the time since the last-observed value for each variable as follows:

(1) $\displaystyle\hat{x}^{d}_{t^{\prime}}$
$\displaystyle=m_{t^{\prime}}^{d}x_{t^{\prime}}^{d}\odot(1-m^{d}_{t^{\prime}})(\gamma_{x_{t^{\prime}}}^{d}x_{\text{prev}}^{d}+(1-\gamma_{x_{t^{\prime}}}^{d}\tilde{x}^{d}_{t^{\prime}}))$
(2) $\displaystyle\hat{h}_{t^{\prime}}$ $\displaystyle=\gamma_{h_{t}}\odot
h_{t^{\prime}}$ (3) $\displaystyle r_{t^{\prime}}$
$\displaystyle=\sigma(W_{r}\hat{x}_{t^{\prime}}+U_{r}\hat{h}_{t^{\prime}}+b_{r})$
(4) $\displaystyle z_{t^{\prime}}$
$\displaystyle=\sigma(W_{z}\hat{x}_{t^{\prime}}+U_{z}\hat{h}_{t^{\prime}}+b_{z})$
(5) $\displaystyle\tilde{h}_{t^{\prime}}$
$\displaystyle=\phi(W\hat{x}_{t^{\prime}}+U(r_{t^{\prime}}\odot\hat{h}_{t^{\prime}})+Vm_{t^{\prime}}+b)$
(6) $\displaystyle h_{t^{\prime}}$ $\displaystyle:=(1-z_{t^{\prime}})\odot
h_{t^{\prime}}+z_{t}\odot\tilde{h}_{t^{\prime}},$

where $\tilde{x}^{d}_{t^{\prime}}$ is the mean of all values of for the given
instance’s variable $d$ before time $t^{\prime}$, $m_{t^{\prime}}^{d}$ is a
binary value indicating whether or not any new observations have been made
since $t^{\prime}$, and $x_{\text{prev}}^{d}$ is the value of the most recent
observation of the $d$-th variable prior to time $t^{\prime}$. $\odot$ is the
hadamard product and $\gamma_{x_{t^{\prime}}}^{d}$ is a decay factor for
variable $d$ at time $t^{\prime}$ computed by a neural network:

$\gamma_{x_{t^{\prime}}}^{d}=e^{-\max(0,W_{\gamma}s_{t^{\prime}}^{d}+b_{\gamma})},$

where $s_{t^{\prime}}^{d}$ is the difference between $t^{\prime}$ and the time
of the last observation of variable $d$. The GRU-D is a natural choice for
this problem, as it computes hidden states at any real-valued times, based on
previous hidden states. By incorporating the mask $m$ and time since last
observation $x_{\text{prev}}$, the hidden state reflects input irregularity.
When decisions—like when to halt—are made based on the resultant hidden
states, they depend on the irregularity of the input series. Further, the
GRU-D is a unidirectional state space model, computing hidden states without
using future information. This is crucial, as early classifiers can only use
previous observations.

An encoding $h_{t^{\prime}}$ thus represents knowledge contained in the
transitions between the values over time and observation density. These hidden
states can therefore use patterns in values and observations to support both
earliness and accuracy. For instance, if observations are arriving rapidly,
more may arrive soon, so waiting to receive them will not incur much penalty
for waiting (Shukla and Marlin, 2019). On the other hand, if the hidden states
indicate low observation density, it may be better to cut our losses since
more observations may be far in the future. Alternatively, the time-since-
last-observation can itself be a valuable feature (Lipton et al., 2016), so
waiting to see if more observations arrive can itself be a reasonable policy
for accurate classification.

###  4.2. Classifying Prefixes

Given a prefix embedding $h_{t^{\prime}}$, we use a Prefix Classifier
$\mathcal{C}_{\theta}$ to predict the class label of the entire series $X$
based only on values observed up to time $t^{\prime}$. We use a standard fully
connected network that projects $h_{t^{\prime}}$ into a $C$-dimensional
probabilistic space via the softmax function, parameterizing the conditional
class probabilities. In our experiments, we use one hidden layer, but this
component can be scaled up depending on the task at hand. Once the Halting
Policy Network chooses to stop, the final prediction $\hat{y}$ for series $X$
is also generated by the Prefix Classifier.

###  4.3. Irregularity-Aware Halting Policy Network

Stop&Hop achieves early halting through an irregularity-aware Halting Policy
Network $\mathcal{H}_{\theta}$ that chooses whether to Stop or Wait at a given
time $t^{\prime}$ based on the history of an ongoing time series $X$. If it
chooses to Wait, it also predicts for how long in the form of a real-valued
step size, after which it will run again. Since there are rarely ground truth
optimal halting times for when Stop&Hop should stop, we follow the state-of-
the-art (Hartvigsen et al., 2019, 2020; Martinez et al., 2019) and formulate
this task as a Partially-Observable Markov Decision Process (POMDP): Given a
state $h_{t^{\prime}}$, select an action $a_{t^{\prime}}$ from the set {Stop,
Wait}. If $a_{t^{\prime}}=\\{\text{Stop}\\}$, then the class label for the
entire series is returned at time $t^{\prime}$. If
$a_{t^{\prime}}=\\{\text{Wait}\\}$, update $t^{\prime}:=t^{\prime}+\Delta t$,
where $\Delta t$ is a hop-size predicted based on $X_{\leq t^{\prime}}$, the
observations before time $t^{\prime}$. Overall, the earlier and more accurate
the predictions are for a series $X$, the higher the reward. If Stop&Hop stops
too early, it may not have observed enough data and will be less likely to be
accurate. Therefore, a good solution must carefully balance between stopping
and predicting the next halting time.

States. The Halting Policy Network’s first job is to compute a probability of
halting $p_{t^{\prime}}$ given the environment’s state at time $t^{\prime}$
which can then be used to take an action: Stop now, or Wait for more data to
be collected. While prior methods use only the prefix embedding
$h_{t^{\prime}}$ to represent the ongoing system’s current state (Hartvigsen
et al., 2019), we propose also predicting an intermediate classification
$y_{t^{\prime}}$ via the Prefix Classifier for each hidden state to gauge the
model’s current opinion of the classes. By feeding this information to the
Halting Policy Network, it can learn the relationship between the Prefix
Classifier’s confidence and the likely accuracy, which often depends on the
task. Additionally, we input $t^{\prime}$ as additional knowledge of a
prediction’s earliness.

Actions. The Halting Policy Network contains two prediction problems in
sequence. First, it decides whether to Stop and classify, or to Hop forward in
time and wait to classify. For the Stop decision, the model selects actions
from the set $\mathcal{A}_{\text{stop}}=\\{\text{Stop},\text{Hop}\\}$. We thus
parameterize a binomial distribution over the action set
$\mathcal{A}_{\text{stop}}$ by a stopping policy $\pi_{\text{stop}}$:

(7) $\displaystyle
p_{t^{\prime}}=\text{softmax}(W_{h}h_{t^{\prime}}+U_{h}\hat{y}_{t^{\prime}}+V_{h}t^{\prime}+b_{h}),$

where $W$, $U$, and $V$ are weight matrices and $b$ is a bias vector. Finally,
we use the probabilities $p_{t^{\prime}}$ to sample an action from a
multinomial distribution. If $a_{t^{\prime}}=\\{\text{Stop}\\}$, then the
corresponding class prediction $\hat{y}_{t^{\prime}}$ is returned at time
$t^{\prime}$ and we set $\tau$ is set to $t^{\prime}$.

If the model instead chooses to Hop, we run a hopping policy
$\pi_{\text{hop}}$, another small neural network, that predicts a positive
real-valued hop-size, which is added to $t^{\prime}$. To account for the
irregular nature of the input time series, we model the hop-time as a
continuous variable, samples of which we acquire by parameterizing a normal
distribution with a neural network. The hop policy $\pi_{\text{hop}}$ begins
by predicting the a mean value:

(8)
$\displaystyle\mu_{t^{\prime}}=\phi(Wh_{t^{\prime}}+U\hat{y}_{t^{\prime}}+Vt^{\prime}+b),$

where $\phi$ is the ReLU function (Hahnloser et al., 2000). We then sample a
hop-size $\Delta t$ from the normal distribution with mean $\mu_{t^{\prime}}$:
$\Delta t\sim\mathcal{N}(\mu_{t^{\prime}},\sigma)$. We leave the standard
deviation $\sigma$ as a hyperparameter, though in principle it can also be
learned by the model. To ensure $\Delta t\geq 0$, we take the absolute value
of $\Delta t$, which is a common approach in similar scenarios (Mnih et al.,
2014). To compute the new candidate halting time, we add the hop-size to the
current candidate halting time: $t^{\prime}\mathrel{{+}{=}}\Delta t$.

In practice, early in training the Halting Policy Network may tend to exploit
some actions by predicting too-high probabilities, relative to an optimal
policy. To encourage exploration early on in training, we employ a simple
$\epsilon$-greedy approach to action selection and exponentially decay the
values $\epsilon$ from 1 to 0 throughout training:

$\displaystyle a_{t^{\prime}}=\begin{cases}a_{t^{\prime}},&\text{with
probability}\ 1-\epsilon\\\ \text{random action,}&\text{with probability}\
\epsilon\end{cases}$

By exploring more, the model tries out different sequences of actions to cover
the space of possible episodes more effectively while early on in training. We
also increase the probability that the Halting Policy Network chooses to Wait
before the model has been thoroughly trained so that the prefix embeddings and
classifier also get to observe more of the sequences and increase their
performance. Otherwise, a model that learns to stop early very quickly will
never have seen the later portions of the training sequences. For all of our
experiments, we compute $\epsilon$ as $e^{-i}$ while reassigning
$i:=i+\frac{i*7}{E}$ for $E$ training epochs after initializing $i$ to 0.
During testing, we set $\epsilon=0$ to avoid exploration for testing series.

Rewards. The final component of the POMDP is the reward for reaching different
states. We encourage the halting policy network to cooperate with the prefix
embeddings and classifier by setting the reward $r_{t^{\prime}}=1$ when the
$\hat{y}$ is accurate and setting $r_{t^{\prime}}=-1$ otherwise. This way,
accurate classifications are encouraged. To encourage early classifications,
we penalize Wait probabilities, as discussed in the next section, which
describes how we jointly train all of Stop&Hop’s components.

###  4.4. Training

The prefix embedding network $\mathcal{R}_{\theta}$ and Classifier
$\mathcal{C}_{\theta}$ are fully-differentiable, so we train them together
using standard back propagation. We encourage them to predict $\hat{y}$ as
close to $y$ as possible by minimizing their cross entropy, where $y_{c}=1$ if
$y=c$ and is 0 otherwise in Equation 9. $\hat{y}_{c}$ is the predicted
probability of class $c$.

(9) $\mathcal{L}_{\text{acc}}=-\sum_{c=1}^{C}y_{c}\log(\hat{y}_{c})$

The Halting Policy Network, on the other hand, samples its actions and so its
training is more intensive, though we follow the standard policy gradient
method and use the REINFORCE algorithm (Williams, 1992) to estimate the
gradient with which we update the network’s parameters. To balance between
earliness and accuracy, the parameters of the Halting Policy Network are
updated with respect to two goals: Make $\tau$ small, and make $\hat{y}$
accurate. Following the state-of-the-art (Hartvigsen et al., 2019), we achieve
smooth optimization by rewarding accurate predictions and penalizing the
cumulative probability of Waiting over each episode. Thus the loss function
for optimizing the halting policy network is computed as:

$\displaystyle\mathcal{L}_{\text{early}}=$
$\displaystyle-\mathbb{E}\left[\sum_{t^{\prime}}\log\pi_{\text{stop}}(a_{t^{\prime}}|h_{t^{\prime}})\left[\sum_{j=t^{\prime}}(r_{t^{\prime}}-b_{t^{\prime}})\right]\right]$
$\displaystyle-\mathbb{E}\left[\sum_{t^{\prime}}\log\pi_{\text{hop}}(a_{t^{\prime}}|h_{t^{\prime}})\left[\sum_{j=t^{\prime}}(r_{t^{\prime}}-b_{t^{\prime}})\right]\right]$
$\displaystyle-\lambda\sum_{t^{\prime}}\log\pi_{\text{stop}}(a_{t^{\prime}}=\text{Stop}|h_{t^{\prime}}),$

where the scale of $\lambda$ determines the emphasis on earliness and
$\pi_{\text{stop}}$ and $\pi_{\text{hop}}$ are the probabilities predicted by
the stopping and hopping networks, respectively. If $\lambda$ is large, the
halting policy network will learn to maximize the probability of stopping
always whereas if $\lambda$ is small or zero, the model will solely maximize
accuracy. Interestingly, the most-accurate classification may not always be
achieved by observing the entire series, though this is rare in practice. For
example, early signals followed by irrelevant values make classification
challenging for memory-based models. Our approach deals with this case
naturally by learning not to make late predictions when they are less
accurate, regardless of any cost of delaying predictions. The final loss
$\mathcal{L}$ is thus

(10) $\mathcal{L}=\mathcal{L}_{\text{acc}}+\alpha\mathcal{L}_{\text{early}},$

and minimized via gradient descent. $\alpha$ scales the loss components.

##  5\. Experiments

###  5.1. Datasets

We evaluate Stop&Hop on four synthetic and three real-world datasets, which
are described as follows:

Synthetic datasets: Since the true halting times are not available for real
data, we develop four synthetic datasets with known halting times.
Intuitively, a good early classifier will stop as soon as a signal is
observed. To generate these data, we first uniformly sample $T-1$ timesteps
from the range $[0,1]$ for each of $N$ time series. We set $T=10$ and
$N=5000$. Then, from a chosen distribution of signal times, we sample one more
timestep per series at which the class signal occurs and add it to a series’
timesteps.

We experiment with four distributions of true signal times, each creating a
unique dataset: Uniform $\mathcal{U}(0,1)$, Early
$\mathcal{N}(\mu=0.25,\sigma=0.1)$, Late $\mathcal{N}(\mu=0.75,\sigma=0.1)$,
and BiModal where half the signals are from Early and the other half are from
Late. For each time series, one value is sampled from one of the
distributions—each distribution creates one dataset—which serves as the time
at which a signal arrives in the timeline. In all cases, we clamp this value
to be within range $[0,1]$. We generate two classes by giving $2500$ time
series a $1$ at their signal occurrence time, and $-1$ to the remaining $2500$
series in the dataset. thus we know precisely when the signals arrive for each
instance. Values for off-signal timesteps are set to 0 and are uniformly
sampled from the timeline.

ExtraSensory: We use the publicly-available ExtraSensory (Vaizman et al.,
2017) human activity recognition dataset, which contains smartphone sensor
data collected across one week while participants labeled which actions they
performed and when. These data were collected in the wild, so participants
were left to their own devices for the duration of the study with no
prescribed behavior. Using these data, we simulate a listening probe on a
smartphone’s accelerometer data, which consist of three variables
corresponding to the X, Y, and Z coordinates. A listening probe saves a
phone’s battery by collecting data only when certain measurements are taken,
naturally creating irregular time series. For this dataset, we measure the
norm of the 3-dimensional accelerometer data, only taking measurements
associated with changes in the norm over 0.001. Here we consider the popular
tasks of detecting Walking and Running, classifying whether or not a person
performs an activity within a window. Since activity records are often
incomparable between people, we use the records from the person who walked or
ran the most breaking their series into 100-minute long windows. This creates
two independent datasets, one per user, which is common for human activity
recognition. We balance each dataset, resulting in 2636 time series with an
average of 90 observation per series for Walking and 3000 time series with on
average 100 observations for Running. Deeper, extended discussion of this
dataset is available in a concurrent submission. In general, down-sampling
human activity recognition data is common in the irregular time series
literature (Shukla and Marlin, 2019; Rubanova et al., 2019), and simulating a
listening probe adds a key new ingredient: non-random down-sampling.

PhysioNet: The PhysioNet dataset (Silva et al., 2012) contains medical records
collecting from the first 48 hours after 4000 patients were admitted to an
intensive care unit and is publicly-available. There are 42 variables recorded
at irregular times for each patient along with one label indicating if they
perished. This is a common benchmark for multivariate irregular time series
classification (Che et al., 2018). On these data, we train our classifiers to
perform mortality prediction for previously-unseen patients. 13.8% of patients
have positive labels, so we use the Area Under the Receiver-Operator Curve
(AUC) as our primary metric on all three real-world datasets.

###  5.2. Compared Methods

We compare Stop&Hop to the two key alternatives. Each is a state-of-the-art
early classifier which we update to handle ITS.

  * •

E-GRU (Dennis et al., 2018). E-GRU thresholds a sequential classifier’s output
probability in real time. When the predicted probability $\hat{y}$ surpasses a
threshold $\alpha$, $\hat{y}$ is used to classify the series, ignoring all
future observations. A hidden state represents the streaming series and is
updated whenever a new observation arrives. Each time it is updated, the
hidden state is passed to a neural network that predicts $\hat{y}$.

  * •

EARLIEST (Hartvigsen et al., 2019). Similar to E-GRU, EARLIEST models ongoing
time series with an RNN. Whenever a new observation arrives, a new hidden
state is computed. Similar to Stop&Hop, a halting policy then decides whether
or not to stop and classify the series with a neural network. This baseline
also helps to ablate the Hopping Policy Network network, as it only chooses
between Stop and Wait, ignoring irregularity between observations.

In our synthetic experiments, we also compare Stop&Hop with a baseline: A GRU
is trained to classify irregular time series, then forced to stop at different
proportions of the timeline. This is the most basic early classifier as the
halting times are always the same, disregarding the input data. For all
methods, we use the GRU-D update equations (Che et al., 2018) described in
Section 4.1.

(a) PhysioNet

(b) ExtraSensory Running

(c) ExtraSensory Walking

Figure 4. Trade-off between earliness and accuracy on three real-world time-
sensitive datasets. For each dataset in (a)-(c), the black line (Stop&Hop)
outperforms the compared methods, as it is above them for most halting times.

###  5.3. Implementation Details

For our synthetic datasets and PhysioNet, we repeatedly split the data into
90% training and 10% testing subsets five times, and report the average
performance. We learn each model’s parameters on the training set, and report
all final evaluation metrics on the testing set. The ExtraSensory datasets, on
the other hand, contain instances taken from different windows along a single
timeline and so we select a timestep for each before which is the
training/validation data and after which is the testing to ensure the testing
set’s sanctity. For the synthetic SimpleSignal datasets, we use 10-dimensional
prefix embeddings, which we compute at intervals of 0.1. For ExtraSensory, we
use 50-dimensional prefix embeddings and for PhysioNet they are
20-dimensional.

(a) Effect of $\lambda$ on AUC

(b) Effect of $\lambda$ on Earliness

Figure 5. Hyperparameter tuning for $\lambda$, the emphasis on earliness, on
the ExtraSensory Running dataset. In (a), the AUC increases smoothly as
$\lambda$ decreases. Similarly, in (b) as $\lambda$ decreases, the resultant
halting time increases, successfully covering the whole space from 0.1 to 1.0.

(a) PhysioNet

(b) ExtraSensory Running

(c) ExtraSensory Walking

Figure 6. Effect of Hopping Policy’s standard deviation on the
earliness–accuracy trade-off curves. As the curves are similar to one another,
Stop&Hop is generally robust to selecting the standard deviation, though
tuning per dataset can still be valuable.

For each method, we use a batch size of 32 and grid search for a learning rate
(options: $\\{1e^{-2},1e^{-3},1e^{-4}\\}$) and weight decay for L2
regularization (options: $\\{1e^{-3},1e^{-4},1e^{-5}\\}$) using our validation
data. The validation data is a random 10% of the training dataset and we
repeat this random splitting five times. In our experiments, since we use a
GRU-D (Che et al., 2018) to compute prefix embeddings, its hidden state should
be updated in between hop sizes. For simplicity, we only update the embeddings
when real data are observed per the baselines, though Stop&Hop’s final Stop
time may be between observations. Each model was optimized using Adam (Kingma
and Ba, 2014) with learning rates and weight decays that maximize their
performance on the validation data. All training was done using Intel Xeon
Gold 6148 CPUs. For all experiments, we set the value $\alpha$ in Equation 10
to 1 as the loss terms are balanced. All of our code and data are publicly
available.111https://github.com/thartvigsen/StopAndHop

###  5.4. Results on real-world datasets

First, we demonstrate that Stop&Hop produces early and accurate
classifications using three real time-sensitive datasets, shown in Figure 4.
We use the trade-off curves between earliness and AUC to measure each method’s
performance, adjusting their parameters to achieve average halting times that
span the timeline. We first observe that Stop&Hop outperforms the comparisons:
the black line is consistently highest. This improvement indicates that
Stop&Hop stops earliest and makes the most-accurate classifications.

(a) Uniform true signal times

(b) Early true signal times

(c) Late true signal times

Figure 7. Earliness vs. Accuracy on three synthetic datasets—Uniform, Early,
and Late. The X axis denotes the average percent of the timeline used as
Stop&Hop predicts one halting point per time series. The high black line
indicates that Stop&Hop succeeds to stop and classify irregular time series at
effective times.

For the PhysioNet dataset, Stop&Hop maintains improvement across all average
halting times, converging with the comparisons once all time steps are
observed—as expected. Further, this AUC ($\sim$0.82) is nearly state-of-the-
art for this dataset (Shukla and Marlin, 2021). For the two ExtraSensory
datasets, Stop&Hop’s improvements seem to come earlier in the timeline; at
some point, AUC appears to saturate and Stop&Hop and EARLIEST accurately
classify all testing time series. As we will show on our synthetic results
(Figure 8(b)), this happens when a method predicts good halting points. We are
also unsurprised by this saturation in general: there will always be cases
where relevant windows of a time series are isolated (Zhu et al., 2021). For
these datasets, the optimal halting times are unknown, yet seem to be around
40 minutes for Walking and 60 minutes for Running on average. Discovering good
halting times retrospectively is an added benefit of a successful early
classifier; it can even recover reasonable halting times for individual
instances, depending on whether or not the classification was accurate. In
summary, Stop&Hop consistently outperforms the alternatives on these three
real-world datasets.

(a) Earliness vs. Accuracy

(b) Cumulative halting distribution

Figure 8. Results for BiModal dataset. In (a) Stop&Hop outperforms Preset
Halting. In (b), the solid and dashed lines match, indicating that Stop&Hop is
nearly optimal.

We also conduct a hyperparameter study for $\lambda$ for the Running dataset,
shown in Figure 5. Our results indicate that $\lambda$ has strong control over
the earliness–accuracy trade-off: As $\lambda$ increases, Halting Time and
Accuracy steadily decrease. Standard deviations are computed across five
replications of the same experiment with different seeds. Thus emphasizing
earliness or accuracy is intuitive.

To further ablate the impacts of hyperparemters on Stop&Hop’s success, we also
consider the standard deviation $\sigma$ of the hop policy $\pi_{\text{hop}}$,
which controls for how long to wait before trying to stop again. As $\sigma$
increases, so does the variance in chosen hop sizes. Interestingly, we find
that Stop&Hop’s performance is largely robust to changing $\sigma$, as shown
in Figure 6. Still, varying $\sigma$ seems to have some impact and we
recommend tuning it according to the task at hand. $\sigma$ also determines to
what degree $\pi_{\text{hop}}$ directly controls the sampled hop size. As
$\sigma$ grows, $\pi_{\text{hop}}$ has less direct control, which can improve
exploration and regularize the chosen actions.

###  5.5. Stop&Hop finds the true halting times

We next verify that Stop&Hop indeed finds the true halting times by using use
our four synthetic datasets where we know the halting times. Our results are
shown in Figures 7 and 8, where we compare Stop&Hop to a Preset Halting
baseline with the same prefix embedding approach as Stop&Hop to isolate the
effects of learning when to stop. The preset halting method stops at a set of
predetermined halting times. For example, a preset halting method that uses
50% of the timeline stops all instances at time 0.5.

Our experiments show that Stop&Hop clearly achieves higher accuracy while
using less of the timeline compared to preset halting times, as expected. This
is only possible if Stop&Hop appropriately halts when it sees a signal and
waits otherwise. As the four synthetic datasets have different halting
distributions, we see that Stop&Hop succeeds to wait longer when signals are
all later (Figure 7c) and stop earlier when signals are all earlier (Figure
7b). Note that for the Uniform dataset, Stop&Hop steadily increases to
Accuracy of 1.0 (indicating 100% accurate predictions), which makes sense
because the true signals are distributed uniformly across the timeline. For
the Early dataset, where signals happen early in the timeline, AUC saturates
early and Accuracy steeply increases early on. For Late, Accuracy increases
slowly early on and steeply later. In each case, the Preset Halting baseline’s
Accuracy changes exactly as expected.

For the BiModal dataset—highlighted in Figure 8—we first observe that Stop&Hop
again makes early and accurate predictions, even when signals are distributed
unevenly across the timeline. Its curve is characterized by a steep increase,
followed by a plateau, followed by a steep increase, and finally a plateau. We
expand this experiment and also show a snapshot of the halting distribution
from the BiModal dataset from Stop&Hop trained with $\lambda=3e^{-6}$ in
Figure 8(b). Each instance’s predicted halting time is plotted against the
proportion of the dataset with halting times earlier than a set of possible
halting times, showing the cumulative halting distribution. We color-code the
early and late signals and find that Stop&Hop matches the cumulative
frequencies of the halting timings almost perfectly. As our method captures
all positives exactly on time, matching the true cumulative functions without
supervision, we postulate that Stop&Hop can also learn other complex
functions. In contrast, the preset halting comparison’s halting distribution
is a step function: All instances halt at the same time. This is not flexible
enough to match the halting distributions of real datasets.

##  6\. Ethical Considerations

Our work facilitates decision making given partial temporal information. This
lack of knowledge can naturally lead to misclassifications, which are more or
less dangerous depending on the task. For example, incorrectly predicting
Cancer early may cause undue stress and financial burden to a patient. Still,
the cost of risking a false positive must be balanced with the cost of
delaying predictions, which itself may have negative impacts. Early
classifiers do not suffer from or introduce this trade-off, and instead
embrace reality—the trade-off is real in practice, regardless of the
algorithm. Standard classifiers, for instance, ignore prediction timing, so
they always pick one side of the trade-off. Algorithms like Stop&Hop crucially
allow end-users to balance their own risk aversion.

##  7\. Conclusion

Our work introduces the open Early Classification of Irregular Time Series
problem. This is an important, challenging, and interesting problem that has
yet to be considered by the early classification community. We provide a
general formulation for solving this problem, which we instantiate as a
modular framework that serves as an effective first solution, named Stop&Hop.
Stop&Hop is a novel reinforcement learning-based continuous-time recurrent
network that leverages irregularity in the inputs to inform classifications
that are both early and accurate. By using irregularity to inform when to
classify ongoing series, Stop&Hop advances beyond the state-of-the-art for
early classification. Our irregularity-aware halting policy network chooses
when to stop, which allows more-flexible halting policies than recent
alternatives and shortens the reinforcement learning trajectories, leading to
more stable training. We find that Stop&Hop indeed halts at the earliest-
possible times on all four synthetic data sets and consistently outperforms
alternatives on all three real datasets by making earlier and more-accurate
predictions.

With this work, we also advocate for broadening the evaluation of machine
predictions. Our community often evaluates machine learning models using
solely accuracy (or a similar measure). However, in time-sensitive domains,
accuracy is irrelevant if a model is used too late. We pose that earliness,
along with other highly-impactful directions, like fairness and
explainability, should also be considered when developing machine learning
systems.

##  8\. Acknowledgements

This research was supported in part by grants from U.S. Dept. of Education
P200A150306, NSF-IIS 1910880 and NSF-OAC 2103832. We are grateful to the WPI
DAISY lab for constructive feedback and support.

## References

  * (1)
  * Alavi et al. (2022) Arash Alavi, Gireesh K Bogu, Meng Wang, Ekanath Srihari Rangan, Andrew W Brooks, Qiwen Wang, Emily Higgs, Alessandra Celli, Tejaswini Mishra, Ahmed A Metwally, et al. 2022\.  Real-time alerting system for COVID-19 and other stress events using wearable data.  _Nature medicine_ 28, 1 (2022), 175–184.
  * Bahadori and Liu (2012) Mohammad Taha Bahadori and Yan Liu. 2012.  Granger causality analysis in irregular time series. In _SDM_. SIAM, 660–671.
  * Che et al. (2018) Zhengping Che, Sanjay Purushotham, Kyunghyun Cho, David Sontag, and Yan Liu. 2018.  Recurrent neural networks for multivariate time series with missing values.  _Scientific reports_ 8, 1 (2018), 6085.
  * Chen and Chien (2021) Yi‐Hsiang Chen and Jen‐Tzung Chien. 2021.  Continuous‐Time Attention for Sequential Learning. In _AAAI_.
  * Cheng et al. (2020) Li-Fang Cheng, Bianca Dumitrascu, Gregory Darnell, Corey Chivers, Michael Draugelis, Kai Li, and Barbara E Engelhardt. 2020\.  Sparse multi-output Gaussian processes for online medical time series prediction.  _BMC medical informatics and decision making_ 20, 1 (2020), 1–23.
  * Dennis et al. (2018) D. Dennis, C. Pabbaraju, H. Simhadri, and P. Jain. 2018\.  Multiple instance learning for efficient sequential data classification on resource-constrained devices. In _NeurIPS_. 10953–10964.
  * Ebihara et al. (2020) Akinori F Ebihara, Taiki Miyagawa, Kazuyuki Sakurai, and Hitoshi Imaoka. 2020.  Sequential Density Ratio Estimation for Simultaneous Optimization of Speed and Accuracy. In _ICLR_.
  * Ghalwash et al. (2013) M. Ghalwash, V. Radosavljevic, and Z. Obradovic. 2013\.  Extraction of interpretable multivariate patterns for early diagnostics. In _ICDM_. 201–210.
  * Ghalwash et al. (2014) M. Ghalwash, V. Radosavljevic, and Z. Obradovic. 2014\.  Utilizing temporal patterns for estimating uncertainty in interpretable early decision making. In _KDD_. 402–411.
  * Graham and Cvach (2010) Kelly Creighton Graham and Maria Cvach. 2010.  Monitor alarm fatigue: standardizing use of physiological monitors and decreasing nuisance alarms.  _American Journal of Critical Care_ 19, 1 (2010), 28–34.
  * Gupta et al. (2020) Ashish Gupta, Hari Prabhat Gupta, Bhaskar Biswas, and Tanima Dutta. 2020.  Approaches and applications of early classification of time series: A review.  _IEEE Transactions on Artificial Intelligence_ 1, 1 (2020), 47–61.
  * Hahnloser et al. (2000) Richard HR Hahnloser, Rahul Sarpeshkar, Misha A Mahowald, Rodney J Douglas, and H Sebastian Seung. 2000.  Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit.  _Nature_ 405, 6789 (2000), 947–951.
  * Hartvigsen et al. (2019) Thomas Hartvigsen, Cansu Sen, Xiangnan Kong, and Elke Rundensteiner. 2019.  Adaptive-Halting Policy Network for Early Classification. In _KDD_. 101–110.
  * Hartvigsen et al. (2020) Thomas Hartvigsen, Cansu Sen, Xiangnan Kong, and Elke Rundensteiner. 2020.  Recurrent Halting Chain for Early Multi-label Classification. In _KDD_.
  * He et al. (2015) G. He, Y. Duan, R. Peng, X. Jing, T. Qian, and L. Wang. 2015.  Early classification on multivariate time series.  _Neurocomputing_ 149 (2015), 777–787.
  * Horn et al. (2020) Max Horn, Michael Moor, Christian Bock, Bastian Rieck, and Karsten Borgwardt. 2020.  Set functions for time series. In _ICML_. PMLR, 4353–4363.
  * Jane et al. (2016) Nancy Yesudhas Jane, Khanna Harichandran Nehemiah, and Kannan Arputharaj. 2016.  A temporal mining framework for classifying un-evenly spaced clinical data.  _Applied clinical informatics_ 7, 01 (2016), 1–21.
  * Jia and Benson (2019) Junteng Jia and Austin R Benson. 2019.  Neural jump stochastic differential equations. In _NeurIPS_.
  * Kidger et al. (2020) Patrick Kidger, James Morrill, James Foster, and Terry Lyons. 2020.  Neural Controlled Differential Equations for Irregular Time Series. In _NeurIPS_.
  * Kingma and Ba (2014) Diederick Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  In _ICLR_.
  * Lechner and Hasani (2020) Mathias Lechner and Ramin Hasani. 2020.  Learning Long-Term Dependencies in Irregularly-Sampled Time Series. In _NeurIPS_.
  * Li and Marlin (2016) Steven Cheng-Xian Li and Benjamin M Marlin. 2016.  A scalable end-to-end Gaussian process adapter for irregularly sampled time series classification. In _NeurIPS_. 1804–1812.
  * Li and Marlin (2020) Steven Cheng-Xian Li and Benjamin M Marlin. 2020.  Learning from irregularly-sampled time series: a missing data perspective. In _ICML_.
  * Lipton et al. (2016) Zachary C Lipton, David Kale, and Randall Wetzel. 2016\.  Directly modeling missing data in sequences with rnns: Improved classification of clinical time series. In _Machine Learning for Healthcare_. 253–270.
  * Martinez et al. (2019) Coralie Martinez, Emmanuel Ramasso, Guillaume Perrin, and Michèle Rombaut. 2019.  Adaptive early classification of temporal sequences using deep reinforcement learning.  _Knowledge-Based Systems_ (2019).
  * Mnih et al. (2014) Volodymyr Mnih, Nicolas Heess, Alex Graves, et al. 2014\.  Recurrent models of visual attention. In _NeurIPS_. 2204–2212.
  * Mori et al. (2018) U. Mori, A. Mendiburu, S. Dasgupta, and J. Lozano. 2018\.  Early classification of time series by simultaneously optimizing the accuracy and earliness.  _IEEE transactions on neural networks and learning systems_ 29, 10 (2018), 4569 – 4578.
  * Mori et al. (2017) U. Mori, A. Mendiburu, E. Keogh, and J. Lozano. 2017\.  Reliable early classification of time series based on discriminating the classes over time.  _Data Mining and Knowledge Discovery_ 31, 1 (2017), 233–263.
  * Morrill et al. (2021) James Morrill, Patrick Kidger, Lingyi Yang, and Terry Lyons. 2021\.  Neural Controlled Differential Equations for Online Prediction Tasks.  _arXiv preprint arXiv:2106.11028_ (2021).
  * Mozer et al. (2017) Michael C Mozer, Denis Kazakov, and Robert V Lindsey. 2017\.  Discrete event, continuous time RNNs.  _arXiv preprint arXiv:1710.04110_ (2017).
  * Richards et al. (2011) Joseph W Richards, Dan L Starr, Nathaniel R Butler, Joshua S Bloom, John M Brewer, Arien Crellin-Quick, Justin Higgins, Rachel Kennedy, and Maxime Rischard. 2011\.  On machine-learned classification of variable stars with sparse and noisy time-series data.  _The Astrophysical Journal_ 733, 1 (2011), 10\.
  * Rubanova et al. (2019) Yulia Rubanova, Tian Qi Chen, and David K Duvenaud. 2019\.  Latent Ordinary Differential Equations for Irregularly-Sampled Time Series. In _NeurIPS_. 5321–5331.
  * Schäfer and Leser (2020) Patrick Schäfer and Ulf Leser. 2020.  TEASER: early and accurate time series classification.  _Data mining and knowledge discovery_ 34, 5 (2020), 1336–1362.
  * Shukla and Marlin (2019) Satya Narayan Shukla and Benjamin Marlin. 2019.  Interpolation-Prediction Networks for Irregularly Sampled Time Series. In _ICLR_.
  * Shukla and Marlin (2020) Satya Narayan Shukla and Benjamin M Marlin. 2020.  A survey on principles, models and methods for learning from irregularly sampled time series.  _arXiv preprint arXiv:2012.00168_ (2020).
  * Shukla and Marlin (2021) Satya Narayan Shukla and Benjamin M Marlin. 2021.  Multi-Time Attention Networks for Irregularly Sampled Time Series. In _ICLR_.
  * Silva et al. (2012) Ikaro Silva, George Moody, Daniel J Scott, Leo A Celi, and Roger G Mark. 2012.  Predicting in-hospital mortality of icu patients: The physionet/computing in cardiology challenge 2012. In _2012 Computing in Cardiology_. 245–248.
  * Sun et al. (2020) Chenxi Sun, Shenda Hong, Moxian Song, and Hongyan Li. 2020\.  A review of deep learning methods for irregularly sampled medical time series data.  _arXiv preprint arXiv:2010.12493_ (2020).
  * Tan et al. (2020) Qingxiong Tan, Mang Ye, Baoyao Yang, Siqi Liu, Andy Jinhua Ma, Terry Cheuk-Fung Yip, Grace Lai-Hung Wong, and PongChi Yuen. 2020\.  Data-GRU: Dual-attention time-aware gated recurrent unit for irregular multivariate time series. In _AAAI_ , Vol. 34. 930–937.
  * Vaizman et al. (2017) Y. Vaizman, K. Ellis, and G. Lanckriet. 2017.  Recognizing detailed human context in the wild from smartphones and smartwatches.  _IEEE Pervasive Computing_ 16, 4 (2017), 62–74.
  * Weerakody et al. (2021) Philip B Weerakody, Kok Wai Wong, Guanjin Wang, and Wendell Ela. 2021.  A review of irregular time series data handling with gated recurrent neural networks.  _Neurocomputing_ 441 (2021), 161–178.
  * Williams (1992) Ronald J Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8, 3-4 (1992), 229–256.
  * Wu et al. (2021) Renjie Wu, Audrey Der, and Eamonn J Keogh. 2021.  When is Early Classification of Time Series Meaningful?  _arXiv preprint arXiv:2102.11487_ (2021).
  * Xing et al. (2009) Z. Xing, J. Pei, and P. Yu. 2009.  Early Prediction on Time Series: A Nearest Neighbor Approach. In _IJCAI_. 1297–1302.
  * Xing et al. (2012) Z. Xing, J. Pei, and P. Yu. 2012.  Early classification on time series.  _Knowledge and Information Systems_ 31, 1 (2012), 105–127.
  * Xing et al. (2011) Z. Xing, J. Pei, P. Yu, and K. Wang. 2011\.  Extracting interpretable features for early classification on time series. In _SDM_. 247–258.
  * Yala et al. (2022) Adam Yala, Peter G Mikhael, Constance Lehman, Gigin Lin, Fredrik Strand, Yung-Liang Wan, Kevin Hughes, Siddharth Satuluru, Thomas Kim, Imon Banerjee, et al. 2022\.  Optimizing risk-based breast cancer screening policies with reinforcement learning.  _Nature Medicine_ (2022), 1–8.
  * Ye and Keogh (2009) Lexiang Ye and Eamonn Keogh. 2009.  Time series shapelets: a new primitive for data mining. In _KDD_. 947–956.
  * Zhao et al. (2019) Lei Zhao, Huiying Liang, Daming Yu, Xinming Wang, and Gansen Zhao. 2019.  Asynchronous multivariate time series early prediction for ICU transfer. In _Proceedings of the 2019 Int. Conference on Intelligent Medicine and Health_. 17–22.
  * Zhu et al. (2021) Yuansheng Zhu, Weishi Shi, Deep Shankar Pandey, Yang Liu, Xiaofan Que, Daniel E Krutz, and Qi Yu. 2021.  Uncertainty-Aware Multiple Instance Learning from Large-Scale Long Time Series Data. In _IEEE Big Data_. 1772–1778.