A Reinforcement Learning-Informed Pattern Mining Framework for Multivariate Time Series Classification

1 Introduction

Multivariate time series (MTS) are sequences of events acquired longitudinally, where each event is constituted by observations recorded over multiple attributes. For example, the vital signs and lab results in electronic health records (EHRs) can be formulated as MTS, since they are measured over time and multiple measurements can be obtained simultaneously (e.g., temperature and blood pressure). MTS are widely used in motion recognition [Rakthanmanon and Keogh, 2013], human activity recognition [Minnen et al., 2006], and healthcare [Kang and Choi, 2014]. Comprehensive analyses of MTS can provide insights and facilitate decision-making in various domains and applications [Senin and Malinchik, 2013], and MTS classification is one of the fundamental problems of MTS analyses and has received significant attention [Li et al., 2021]. In general, previous work on MTS classification can be roughly divided into the more recent, highly effective neural network (NN)- based methods, and the classic, often interpretable pattern-based methods.

Various NN-based approaches have been proposed to directly learn low-dimensional representations from MTS through various NN or deep NNs, including the state-of-theart ROCKET [Dempster et al., 2020], TapNet [Zhang et al., 2020], and MLSTM-FCN [Karim et al., 2019]. For example, ROCKET uses a large number of random convolution kernels to transform time series and uses the transformed representations to train a linear classifier. Despite their effectiveness, due to the 'black-box' nature of neural network models, the learned representations are often hard to interpret.

The pattern-based methods, on the other hand, generate discrete representations or time-series shapelet as patterns that capture both intra- and inter-sample structures of MTS (e.g., ShapeNet [Li et al., 2021], WEASEL+MUSE [Sch¨afer and Leser, 2018]). These methods decompose each original attribute into a bag of substructures using sliding windows, then transform the substructures into features to be used as inputs for classifiers. Since the patterns are still operating on the original attribute space, they are often highly interpretable. Specifically, discriminative patterns are those that can distinguishMST among different classes [Senin andMalinchik, 2013] and they are typically useful for classification tasks. As frontier work, WEASEL+MUSE [Sch¨afer and Leser, 2018] applies symbolic Fourier approximation to discretize MTS and uses χ2 -test to determine discriminative patterns.

In addition to the fact that pattern-based methods often produce interpretable patterns which may not be helpful for classification, they also have three major limitations: (i) Generalizability - to determine discriminative patterns, pattern-based methods typically use carefully designed architectures, often in combination with domain knowledge over specific types of data [Gao et al., 2021]. (ii) Scalability - they tend to generate a great amount of pattern candidates and require complicated feature filtering modules. This could lead to inefficient training and undesirable model performance as discussed in [Zhang et al., 2020]. (iii) Reliability - existing patternbased methods employ distance-based metrics, i.e. dynamic time warping (DTW) [Shokoohi-Yekta et al., 2015] and symbolic Fourier approximation [Sch¨afer and Leser, 2018] to discretize and segment MTS,. Yet, these are not considered to be very reliable [Hallac et al., 2017].

We propose a Reinforcement Learning (RL) informed PAttern Mining (RLPAM) framework to identify interpretable yet important patterns for MTS classification.

RLPAM combines Deep RL (DRL) and Toeplitz inverse covariance-based clustering (TICC) to address limitations and shortcomings of existing pattern-based approaches while preserving their original interpretability. DRL have shown great success in improving prediction performance [Gao et al., 2022b; Zoph and Le, 2017], which do not necessarily rely on domain knowledge. By considering the graphical connectivity structure of both the temporal and the crossattribute dependencies among events, it has been shown that TICC produces more reliable results in MTS segmentation than distance-based metrics, as well as discovering pattern interpretations in various applications such as driving patterns in traffic [Hallac et al., 2017; Yang et al., 2021].

We compare RLPAM with other the-state-of-the-art NNbased and pattern-based methods on 30 benchmark datasets as shown in Table 1 as well as real-world large-scale EHRs for a challenging task: sepsis shock early prediction. RLPAM outperforms all other methods on 14 out of 30 datasets as well as on the EHRs. We also show that by selecting patterns based on RL, not only can the performance of classification be improved, but they can also be used to draw insights into quantitative and qualitative relationships between MTS and labels through a case study using the task of septic shock progression. To summarize, our work has at least two main contributions: 1) To the best of our knowledge, RLPAM is the first MTS classification method to adapt RL to identify discriminative patterns, making the framework scalable, generalizable, and reliable; 2) We have conducted a comprehensive comparison of various state-of-the-art NN-based and patternbased methods across 30 UEA Archive datasets (Table 1).

2 RelatedWork

Table 1 summarizes the performance of some recently proposed MTS classification models comparing with their respective baselines over the UEA datasets. These methods in general can be categorized into pattern-based and NN-based.

Pattern-based methods generally extract bag-of-patterns (BOP) (e.g., WEASEL+MUSE [Sch¨afer and Leser, 2018]) or shapelet-patterns (e.g., ShapeNet [Li et al., 2021]) from time series and then feed these patterns into a classifier. Specifically, BOP breaks up time series into windows and represents them as discrete features via a histogram of feature counts. For instance, one of the state-of-the-art BOP models, WEASEL+MUSE [Sch¨afer and Leser, 2018], uses symbolic Fourier approximation and statistical methods to generate discrete-valued patterns for classification. It outperforms classic baselines (e.g., DTW) on 13 out of 20 UEA datasets. Shapelets are time series subsequences that can best represent samples across different classes [Ye and Keogh, 2009].

lection and classifier training. (c) Policy (Actor) πθ of Figure 1b.

Figure 1: Overview of the RLPAM framework.

ShapeNet [Li et al., 2021] embeds shapelets into a unified space and characterizes MTS by evaluating pre-defined distance metrics calculated from selected shapelets as inputs to the classification model. It outperforms baselines including WEASEL+MUSE on 14 out of 30 UEA datasets.

NN-based methods [Karimet al., 2019; Zhang et al., 2020] have been proposed to improve the MTS classification performance recently. For instance, MLSTM-FCN [Karim et al., 2019] is a deep learning framework that generates latent patterns with a squeeze-and-excitation block, and it outperforms WEASEL+MUSE on 14 out of 20 UEA datasets. TapNet [Zhang et al., 2020] proposes an attentional prototype network to learn the latent features extracted fromMTS, and it outperforms both benchmark and recent baselines (e.g., MLSTM-FCN) on 14 out of 30 UEA datasets. ROCKET [Dempster et al., 2020] is neural-network based model that transforms time series using random convolutional kernels to train linear classifiers. It is recognized as a strong method evaluated on 26 UEA datasets in recent work [Ruiz et al., 2021]. Although these NN-based approaches can be trained end-to-end, they provide little interpretability.

3 RLPAM

The overview of our RLPAM framework is illustrated in Figure 1. It first encodes MTS into univariate cluster sequences (UCS), then learns multi-pattern time series (MPTS) using pattern candidates extracted from UCS, from which discriminative patterns are identified by a RL module, in concurrent with training of the classification model. We are releasing the source code of our implementation and it can be accessed at https://github.com/fay067/RLPAM.

3.1 ProblemFormulation

Multivariate time series can be represented as X = {X1, ...,XN}, where N is the total number of samples. Each sample Xi consists of a sequence of events: Xi = (xi,1, ..., xi,ti ) where each xi,j is an event representing the observations at time step j and ti is the horizon which can vary across different samples. Specifically, xi,j ∈ RD and D is the number of attributes recorded; thus, we have Xi ∈ Rti×D . Our goal is to train a classification model f : Xi → yi which assigns each sample Xi to its corresponding class yi ∈ P = {1, ..., P}.

3.2 LearningMulti-pattern Time Series

Encoding UCS from MTS. We first convert each MTS sample Xi into a univariate cluster sequence (UCS), which is a vector characterizing the dependencies across attributes in the original MTS. It consists of the following two steps: Events Clustering: Events from all samples are stacked to form a multivariate sequence X = (x1,1, ..., x1,t1 , ..., xN,1, ..., xN,tN ) with length T = ∑Ni=1 ti. Then we group the events xi,j ∈ X into C clusters, where each xi,j is assigned with one from the set of clusters K = {K1, . . . , KC}. The distance-based metrics used in classic clustering methods, such as K-Means [Lloyd, 1982], are shown to be not fully reliable for pattern mining purposes [Keogh and Lin, 2005; Hallac et al., 2017]. As a result, we choose to formulate the objective as defined in the Toeplitz inverse covariancebased clustering (TICC) problem [Hallac et al., 2017], since it can be solved through a model-based manner by considering the graphical connectivity structure of both the temporal and the cross-attribute dependencies among events. UCS Formulation: After mapping each event into a cluster, a vector K = (K1,1, . . . ,K1,t1 , . . . ,KN,1, . . . ,KN,tN ) can be defined such that each element Ki,j ∈ K is mapped from the corresponding event xi,j ∈ X. Then we group together the Ki,j's that are mapped from the same sample as Ui = (Ki,1, . . . , Ki,ti ) to constitute the UCS for sample Xi.

Extracting MPTS from UCS. From the pattern information encoded in UCS, we further extract multi-pattern time series (MPTS) to represent the time series samples. It consists of the following two steps: Initializing Pattern Candidates: For the set of UCS, Up p ∈ P, which mapped from samples {Xi|yi = p} associated with a class p, we extract consecutive subsequences with a minimum length of 2, as pattern candidates unique to class p. Consequently, the overall set of pattern candidates for all the classes, L = {l1, . . . , lL}, can be obtained by extracting subsequences from all Up and taking a union of their outputs; here, L is the size of such pattern candidates set. Encoding Multi-Pattern Time Series: Given a sample Xi with length ti, its MPTS over L pattern candidates is written as Mi = (Mi,1, ...,Mi,L)⊤ ∈ {0, 1}ti×L, where Mi,l ∈ {0, 1}ti . The elements of Mi,l are determined by the time stamps the l-th pattern candidate appears (denoted as 1) or is absent (denoted as 0) in its corresponding UCS Ui. Note that such MPTS encapsulate the dependencies underlying sequential patterns across timestamps and samples, and they could be used as the inputs to a classification model.

3.3 RL for Pattern Selection and Classification

Considering the fact that the number of MPTS pattern candidates {l1, . . . , lL} are usually large, it is highly desired to filter out the noisy patterns to classify based on critical ones. Though some linear models, e.g., LASSO, may be capable of selecting patterns based off fromMPTS, they cannot capture the temporal correlations existed in MTS [Tan et al., 2016]. In this work, we introduce RL to simplify the MPTS Mi's by identifying the discriminative patterns, which can best distinguish each sample among the classes, by interacting with the RL environment while training the classifier f. Equipped with RL, our method can not only improve the performance of f, but also highlight interpretability of the patterns.

There exists at least two challenges for RL to solve the problem we consider. (a) Large discrete search space. The number of pattern candidates could result in exponentially growing search space since it has size 2L. (b) Sampleagnostic discriminative pattern selection. Usually the classification model is trained using mini-batches which are randomly sampled from the training dataset [Ruder, 2016]. However, we expect the selected discriminative patterns to distinguish each sample among all the others that are not associated with the same class, even if they are not presented in the current training batch. As a result, we expect the RL to select a set of patterns that are consistently discriminative among all the samples, instead of finding patterns that can only distinguish samples within each specific input batch.

Modeling with RL

General RL trains an agent to learn optimal strategies by interacting with environments and maximizing cumulative rewards. Such environments can be formalized as Markov decision processes (MDPs). Specifically, each time after the agent performs an action a = π(s) at state s following its policy π, the environment responds with the next state s′ with the reward signal r. The goal is to find a policy π that maximizes the expected cumulative return the agent could obtain, as G(π) = Eρ [ ∑ητ=0 γ iR(sτ , aτ )]; here, η is the horizon of the environment, ρ = {(s0, a0), . . . , (sη, aη)|aτ = π(sτ )} is the trajectory given π, and γ ∈ [0, 1) is the discount factor.

The modeling of MPTS pattern selection and training an LSTM [Hochreiter and Schmidhuber, 1997] classifier based on RL is illustrated in Figure 1b. Each element of M = (S, A, P, R, γ) in this RL environment is detailed as follows:

State Space S: The states are characterized by s = (M, h), where M ∈ {0, 1}Ttrain×L is the batch of MPTS mapped from corresponding training samples selected in the current iteration, Ttrain = ∑Ntrain i=1 ti, h ∈ RNtrain×nlstm are the encodings (or the hidden states) generated by the LSTM, Ntrain is the batch size and nlstm is the number of hidden units of the LSTM.

Action Space A: The action space defines the mechanism of selecting discriminative patterns from all the L patterns residing within the input batch M. We define actions as vectors with length L as a ∈ {0, 1}L. Each dimension l ∈ [1,L] is filled with either 1 (or 0) corresponding to if the l-th pattern in M is considered as a discriminative pattern (or not).

Given that there exists one-to-one mapping between each Xi and Mi following from Section 3.2, we can rewrite the classification model's input in terms of MPTS under the batch training setting to simplify mathematical notations. Specifically, from now on we consider the classification model f takes as input batch M⊙ a and maps them to predictions ˆy, where M⊙a means all the elements in the l-th column of M

are multiplied with the l-th element in a for all l ∈ [1, L].

Transitions P: The transition dynamics determine how to transit from a current state s = (M, h) to the next state s′ = (M′ , h′ ) given an action a to the environment. In our case, M → M′ is determined by how training batches are formulated by sampling from the dataset in each iteration. Similarly, h → h′ represents the change of LSTM hidden states by switching from the old input M⊙a to the new input M′ ⊙a′ . Consequently, by putting together all the transitions above, we define s → s′ .

Reward Function R: After the agent takes an action a at state s, the reward r = R(s, a) is returned by the environment, thus the policy π can then be updated following this information. We define the reward function as R(s, a) =

-J(ˆy, y), which is the negative of a commonly used loss function such as cross-entropy.

Actor-Critic DRL. Although some existing RL methods can resolve the challenge (a), e.g., [Dulac-Arnold et al., 2015], they may not be capable of addressing the challenge (b), which is specific to the pattern selection problem considered in this work. Here, we choose to adapt from an actorcritic deep RL method, i.e., deep deterministic policy gradient (DDPG) [Lillicrap et al., 2016], for two reasons. First, it was originally designed for continuous action spaces which intrinsically has large spaces; Second, the policy π can be updated using past experience, which is more sampling efficient. In DDPG, an actor πθ : S → A is used to represent the policy to be updated iteratively. It is parametrized by a multi-layer perceptron (MLP) [Anzai, 2012] θ. The actor πθ is jointly trained with the critic Qξ : S × A → R, parametrized by another MLP ξ, to maximize the approximated expected return Gβ(πθ) = Es∼ρβ [Qξ(s, πθ(s))].

Our Neural Architecture and Actor-Critic Updates

We first design the neural architecture for actor πθ to account for the discrete action space a ∈ {0, 1}L, by using Sigmoid output activations and thresholding. The architecture is illustrated by a flowchart in Figure 1c. Specifically, to better represent the states s = (M, h) as matrices in batch settings, we define ˜s = ( ˜M, h) where ˜M is obtained by first padding all the sequences Mi ∈ M to become the same length and then concatenating all the elements in each padded sequence into a vector; thus, the first dimension of ˜Mbecomes Ntrain, which is consistent with h ∈ RNtrain×nlstm . 1 Then, the architecture follows regular MLP up until when logits are generated, which are with dimension RNtrain×L. In what follows, the logits first pass through a Sigmoid layer and are then averaged over all the samples in batch, where we denote the output from here as µθ(s) ∈ RL. At last, the action is generated following πθ(s) = 1(µθ(s) ≥ 0.5), where 1(·) is the indicator function and πθ(s) ∈ RL.

Due to the averaging layer, the same action is taken for all the inputs in the batch, i.e., the same patterns are selected over all the input samples (Xi's) that are mapped to the MPTS batch M. The purpose of using such an averaging layer is to reduce the conditional dependencies between a and s as pointed out in the challenge (b). Since each batch is formed by randomly sampling from the training data, by enforcing such constraints we expect the policy would focus on the patterns that are helpful to distinguish different classes.

1 Note that ˜s and s can be used interchangeably.

Note that the updates of policy πθ do not rely on domain knowledge of the datasets, which shows generalizability of the framework. The use of deep classification models and deep RL makes the proposed method scalable. In event clustering, the objective does not include the distance-based metrics that are shown to be not fully reliable. Moreover, the selected discriminative patterns could be interpretable, which will be illustrated in Section 4.5.

4 Experiments

In this section, we introduce the datasets and baselines used for evaluations, followed by results and a case study illustrating the interpretability of derived patterns.

4.1 Datasets

We first evaluate our model on 30 datasets from UEA MTS classification archive [Bagnall et al., 2018], which consists of data collected from various domains, including human activities recognition, ECG/EEG signals, motion classification, etc. The sample sizes of the datasets range from 27 to 50,000. The lengths of time series range from 8 to 17,901. We follow the same train/test split ratio as provided by the dataset authors.

Furthermore, we evaluate our model's performance on 24-hour early predictions of septic shock using MIMIC-III [Johnson et al., 2016] which contains real-world electronic healthcare records obtained from intensive care unit patients. We pre-process and label sepsis patients following [Gao et al., 2022a]. In total 772 (containing 386 positive and 386 negative) sepsis patients are obtained. The lengths of time series range from 1 to 923. We adopt 5-fold cross validation to evaluate the performance on this dataset.

4.2 EvaluationMetrics

For each dataset, we report the classification accuracy, average rank and number of wins/ties on the testing set. We compute mean per class error (MPCE), which is the average error of each class for all the datasets, following the process described in [Karim et al., 2019]. We also conduct the Friedman test and Wilcoxon signed-rank test following the process described in [Demˇsar, 2006] with Holm's α (5%) [Holm, 1979]. The Friedman test is a non-parametric statistical test to justify the significance of performance differences across all the methods. The Wilcoxon signed-rank test is a non-parametric statistical test based on the hypothesis that the rank medians between our method and any baselines are the same.

4.3 Baselines

We compare RLPAM with (i) directly using UCSs as inputs to train LSTM, which is denoted as UCS in Table 2. This serves as an ablation baseline which helps analyze the advantages of mining discriminative patterns from them, as proposed in RLPAM. (ii) Seven state-of-the-art methods: WEASEL+MUSE, ShapeNet, MLSTM-FCN, TapNet, and ROCKET as reviewed in Section 2, as well as MrSEQL [Le Nguyen et al., 2019] and MiniRocket [Dempster et al., 2021], which are originally

- Accuracy results are sorted by deviations between RLPAM and the best performing baselines. The classification accuracy of the baselines on the UEA archive datasets are obtained from their original papers, except ROCKET which is run using the code open-sourced by [Ruiz et al., 2021].

Figure 2: Performance Comparison on MIMIC-III dataset. ShapeNet cannot be implemented due to the high missing rate in clinical data which make shapelet based methods hard to converge.

proposed towards TS classification but can be directly applied to MTS classification. (iii) Three MTS classification benchmarks [Shokoohi-Yekta et al., 2015; Bagnall et al., 2018]: EDI is one nearest neighbor classifier based on Euclidean distance. DTWI is dimension-independent DTW. DTWD is dimension-dependent DTW.

4.4 Classification Results

The overall classification accuracy results for the UEA datasets are presented in Table 2. The result "N/A" indicates the corresponding methods are not reported in [Bagnall et al., 2018] or incapable of producing the results. Overall, RLPAM achieves the best average accuracy rank across all the compared methods. Specifically, RLPAM attains the average rank of 2.900, which is higher than all the baselines. RLPAM results in 14 wins/ties while the best performing state-of-theart gets 8 wins/ties. In terms of MPCE, RLPAM achieves the least average error per class across all datasets. In Friedman test, our statistical significance is p <= 0.001. It confirms the statistical significance of the performance difference among all 12 methods. The Wilcoxon signed-rank test is performed between RLPAM and all baselines, which shows that overall performance of RLPAM over the 30 UEA datasets outperforms baselines with statistical significance at the level of p < 0.05, except ROCKET and MiniRocket. Interestingly, on datasets where UCS performs reasonably well but not as good as the state-of-the-arts, RLPAM can improve its performance and even outperforms state-of-the-arts. On datasets where UCS performs poorly, RLPAM can significantly improve its performance but may not beat the state-of-the-arts. The observations above demonstrate the importance of generating pattern-based representations, as proposed in RLPAM, for MTS classification. Moreover, RLPAM performs better in most datasets that contain a limited number of training samples, such as StandWalkJump (SWJ) and AtrialFibrillation (AF) which contain only 12 and 15 training samples respectively. The reason could be that these datasets intrinsically contain high-qualitative representative and discriminative patterns which are captured by RLPAM.

We further investigate how RLPAM performs against the state-of-the-art MTS classification methods on a real-world healthcare problem, i.e., 24-hour early septic shock prediction. For this task we use the data extracted fromMIMIC-III, along with the open-sourced code attached to each method in its original paper. Given that this is a binary classification task, we show both the average accuracy and AUC obtained

(c) Beginning/ending 4hrs' supports across two classes.

Figure 3: Analysis for the RLPAM informed patterns.

from 5-fold cross validation in Figure 2. It can be observed that RLPAM achieves the best performance in terms of both metrics, which significantly outperforms the other methods.

4.5 ACase Study on Interpretability

Six RLPAM patterns with the highest supports were selected here. Here the support is calculated by the portion of visits which contain the pattern among all visits. As shown in Figure 3a, three of them (i.e., N1, N2, N3) appear significantly more frequently in non-shock visits than in shock ones, while S1, S2, S3 appears significantly more in shock visits than non-shock ones. For each pattern l ∈ L and all MTS X = {X1, . . . ,XN}, we calculate the average value, κdl , of each attribute d ∈ [1, D] recorded in the part of X pertaining to Mi,l = 1, across all i ∈ [1,N] patients. In what follows, the deviations κdl - ¯κdl , from the population mean of each attribute ¯κdl = 1N ∑i 1 ti ∑t xi,t,d, are visualized in Figure 3b 2 . It can be observed that S1, S2, S3 in general result in negative deviations (shown in red), while most part of N1, N2, N3 are associated with positive deviations (shown in blue). According to the deviations, and referring to the septic shock diagnosis criteria provided by some expertized clinician, we find potential ways to interpret the patterns as shown in Table 3. The patterns informed by RLPAM are fine-grained and convey insights of septic shock progress.

2 All MTS X are min-max normalized before calculating deviations.

We further analyze the supports of patterns in the beginning 4 hours and the ending 4 hours across visits for non-shock and shock patients, which are shown in Figure 3c left and right side respectively. We find that patterns N1, N2, N3 appear consistently frequent across non-shock visits with similar supports between the beginning and the ending 4 hours. On the contrary, patterns S1, S2, S3 behave differently across shock visits: S1 is more than twice as frequent in the beginning 4 hours than in the ending 4 hours; S2 is consistently frequent in both the beginning and ending 4 hours; S3 only appears in the ending 4 hours. Interestingly, we also investigate all C = 6 cluster indices that constitute UCSs, and most of them have supports greater than 0.6 on both shock and non-shock classes. This indicates that it is hard to use cluster indices alone to differentiate classes, but the patterns recognized by RLPAM can provide insights into the relations between MTS and class labels.

5 Conclusion and Limitation

In this paper, we proposed a MTS classification framework called RLPAM. It first converted MTS into MPTS which contain information propagated from interpretable pattern candidates. Then, a deep RL module was devised to iteratively identify and refine the set of discriminative patterns in concurrent with training of a deep learning classifier. The design of the actor's neural architecture as well as the adapted actor-critic gradients updates were shown effective for maintaining the set of selected patterns in a sample-agnostic manner. We ran experiments on 30 UEA Archive datasets and the MIMIC-III dataset. The results showed that RLPAM outperforms state-of-the-art methods as well as the ablation baseline which directly using UCS as classification model inputs, illustrating the importance of identifying discriminative patterns. However, our performance was limited on datasets where UCS performs extremely poor; possibly due to the lack of graphical connectivity structure among temporal or crossattribute dependencies underlying the data, which makes the cluster indices generated by TICC not informative enough for downstream analyses. In the future, this could be resolved by designing event clustering method that could improve the expressiveness and representational power of its UCS outputs.

Acknowledgements

This research was supported by the NSF Grants: #2013502, #1726550, #1660878, #1651909, #1522107, #1837499, and #2112562, and by AFOSR FA9550-19-1-0169. Special thanks to John Hostetter (NCSU) for his insightful comments to help improve paper presentation.