#  AdaRNN: Adaptive Learning and Forecasting for Time Series

Yuntao Du1, Jindong Wang2, Wenjie Feng3, Sinno Pan4, Tao Qin2, Renjun Xu5,
Chongjun Wang1 1Nanjing University, Nanjing, China 2Microsoft Research Asia,
Beijing, China3Institute of Data Science, National University of Singapore
4Nanyang Technological University 5Zhejiang University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2021)

###### Abstract.

Though time series forecasting has a wide range of real-world applications, it
is a very challenging task. This is because the statistical properties of a
time series can vary with time, causing the distribution to change temporally,
which is known as the distribution shift problem in the machine learning
community. By far, it still remains unexplored to model time series from the
distribution-shift perspective. In this paper, we formulate the Temporal
Covariate Shift (TCS) problem for the time series forecasting. We propose
Adaptive RNNs (AdaRNN) to tackle the TCS problem. AdaRNN is sequentially
composed of two modules. The first module is referred to as Temporal
Distribution Characterization, which aims to better characterize the
distribution information in a time series. The second module is termed as
Temporal Distribution Matching, which aims to reduce the distribution mismatch
in the time series to learn an RNN-based adaptive time series prediction
model. AdaRNN is a general framework with flexible distribution distances
integrated. Experiments on human activity recognition, air quality prediction,
household power consumption, and financial analysis show that AdaRNN
outperforms some state-of-the-art methods by $2.6\%$ in terms of accuracy on
classification tasks and by $9.0\%$ in terms of the mean squared error on
regression tasks. We also show that the temporal distribution matching module
can be extended to the Transformer architecture to further boost its
performance.

Time series, multi-task learning, transfer learning

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
30th ACM International Conference on Information and Knowledge Management;
November 1–5, 2021; Virtual Event, Australia.††booktitle: Proceedings of the
30th ACM Int’l Conf. on Information and Knowledge Management (CIKM ’21),
November 1–5, 2021, Virtual Event, Australia††price: 15.00††isbn:
978-1-4503-8446-9/21/11††doi: 10.1145/XXXXXX.XXXXXX††ccs: Computing
methodologies Transfer learning††ccs: Computing methodologies Artificial
intelligence

##  1\. Introduction

Time series (TS) data occur naturally in countless domains including financial
analysis (Zhu and Shasha, 2002), medical analysis (Matsubara et al., 2014),
weather condition prediction (Vincent and Thome, 2019), and renewable energy
production (Choi et al., 2016). Forecasting is one of the most sought-after
tasks on analyzing time series data (arguably the most difficult one as well)
due to its importance in industrial, society and scientific applications. For
instance, given the historical air quality data of a city for the last five
days, how to predict the air quality in the future more accurately?

In real applications, it is natural that the statistical properties of TS are
changing over time, i.e., the non-stationary TS. Over the years, various
research efforts have been made for building reliable and accurate models for
the non-stationary TS. Traditional approaches such as hidden Markov models
(HMMs) (Tuncel and Baydogan, 2018), dynamic Bayesian networks (Robinson et
al., 2010), Kalman filters (de Bézenac et al., 2020), and other statistical
models (e.g. ARIMA (Kalpakis et al., 2001)), have made great progress.
Recently, better performance is achieved by the recurrent neural networks
(RNNs) (Salinas et al., 2020; Vincent and Thome, 2019). RNNs make no
assumptions on the temporal structure and can find highly non-linear and
complex dependence relation in TS.

Figure 1. The _temporal covariate shift_ problem in non-stationary time
series. The raw time series data ($x$) is multivariate in reality. At time
intervals $A,B,C$ and the unseen test data, the distributions are different:
$P_{A}(x)\neq P_{B}(x)\neq P_{C}(x)\neq P_{Test}(x)$. With the distribution
changing over time, how to build an accurate and adaptive model?

The non-stationary property of time series implies the _data distribution
changes over time_. Given the example in Figure 1, data distributions $P(x)$
vary for different intervals $A$, $B$, and $C$ where $x,y$ are samples and
predictions respectively; Especially for the test data which is unseen during
training, its distribution is also different from the training data and makes
the prediction more exacerbated. The conditional distribution $P(y|x)$,
however, is usually considered to be unchanged for this scenario, which is
reasonable in many real applications. For instance, in stock prediction, it is
natural that the market is fluctuating which changes the financial factors
($P(x)$), while the economic laws remain unchanged ($P(y|x)$). It is an
inevitable result that the afore-mentioned methods have inferior performance
and poor generalization (Kuznetsov and Mohri, 2014) since the distribution
shift issue violates their basic I.I.D assumption.

Unfortunately, it remains unexplored to model the time series from the
distribution perspective. The main challenges of the problem lies in two
aspects. First, how to characterize the distribution in the data to maximally
harness the common knowledge in these varied distributions? Second, how to
invent an RNN-based distribution matching algorithm to maximally reduce their
distribution divergence while capturing the temporal dependency?

In this paper, we formally define the _Temporal Covariate Shift (TCS)_ in
Figure 1, which is a more practical and challenging setting to model time
series data. Based on our analysis on TCS, we propose AdaRNN, a novel
framework to learn an accurate and adaptive prediction model. AdaRNN is
composed of two modules. Firstly, to better characterize the distribution
information in TS, we propose a temporal distribution characterization (TDC)
algorithm to split the training data into $K$ most diverse periods that are
with large distribution gap inspired by the principle of maximum entropy.
After that, we propose a temporal distribution matching (TDM) algorithm to
dynamically reduce distribution divergence using a RNN-based model.
Experiments on activity recognition, air quality prediction, household power
consumption and stock price prediction show that our AdaRNN outperforms the
state-of-the-art baselines by $2.6\%$ in terms of an accuracy on
classification tasks and by $9.0\%$ in terms of RMSE on regression tasks.
AdaRNN is agnostic to both RNN structures (i.e., RNNs, LSTMs, and GRUs) and
distribution matching distances (e.g., cosine distance, MMD (Borgwardt et al.,
2006), or adversarial discrepancy (Ganin et al., 2016)). AdaRNN can also be
extended to the Transformer architecture to further boost its performance.

To sum up, our main contributions are as follows,

  * •

Novel problem: For the first time, we propose to model the time series from
the distribution perspective, then we postulate and formulate the Temporal
Covariate Shift (TCS) problem in non-stationary time series, which is more
realistic and challenging.

  * •

General framework: To solve TCS, we propose a general framework AdaRNN that
learns an accurate and adaptive model by proposing the temporal distribution
characterization and Temporal Distribution matching algorithms.

  * •

Effectiveness: We conduct extensive experiments on human activity recognition,
air quality prediction, household power consumption, and stock price
prediction datasets. Results show that AdaRNN outperforms the state-of-the-art
baselines on both classification and regression tasks.

##  2\. Related Work

###  2.1. Time series analysis

Traditional methods for time series classification or regression include
distance-based (Orsenigo and Vercellis, 2010; Górecki and Luczak, 2015),
feature-based (Schäfer, 2015), and ensemble methods (Lines and Bagnall, 2014).
The distance-based methods measure the distance and similarity of (segments
of) raw series data with some metric, like the Euclidean distance or Dynamic
time wrapping (DTW) (Keogh and Ratanamahatana, 2005). The feature-based
methods capture the global/local patterns in the time series rely on a set of
manually extracted or learned features. The ensemble methods combine multiple
weak classifiers to boost the performance of the models.

However, involving heavy crafting on data pre-processing and labor-intensive
feature engineering makes those methods struggling to cope with large-scale
data and the performance is also limited for more complex patterns. Recurrent
Neural Networks (RNNs), such as Gated Recurrent Unit (GRU) and Long Short Term
Memory (LSTM) have been popular due to their ability to extract high quality
features automatically and handle the long term dependencies. These deep
methods tackle TS classification or forecasting by leveraging attention
mechanisms (Lai et al., 2018; Qin et al., 2017) or tensor factorization (Sen
et al., 2019) for capturing shared information among series. Another trend is
to model uncertainty by combining deep learning and State space models
(Salinas et al., 2020). Furthermore, some methods (Salinas et al., 2020;
Vincent and Thome, 2019; Le Guen and Thome, 2020) adopt seq2seq models for
multi-step predictions. Unlike those methods based on statistical views, our
AdaRNN models TS from the perspective of the distributions. Recently, the
Transformers structure (Vaswani et al., 2017) is proposed for sequence
learning with the self-attention mechanism. The vanilla Transformer can be
easily modified for time series prediction, while it still fails for
distribution matching.

Time series segmentation and clustering are two similar topics to our temporal
distribution characterization. Time series segmentation (Liu et al., 2008;
Chung et al., 2004) aim to separate time series into several pieces that can
be used to discover the underlying patterns; it mainly uses change-point
detection algorithms, include sliding windows, bottom-up, and top-down
methods. The methods in segmentation almost don’t utilize the distribution
matching scheme and can’t adapt to our problem. Time-series clustering (Hallac
et al., 2017; Ristanoski et al., 2013), on the other hand, aims at finding
different groups consisting of similar (segments of) time series, which is
clearly different from our situation.

###  2.2. Distribution matching

When the training and test data are coming from different distributions, it is
common practice to adapt some domain adaptation (DA) algorithms to bridge
their distribution gap, such that domain-invariant representations can be
learned. DA often performs instance re-weighting or feature transfer to reduce
the distribution divergence in training and test data (Wang et al., 2020; Zhu
et al., 2020; Wang et al., 2018; Ganin et al., 2016; Tzeng et al., 2017).
Similar to DA in general methodology, domain generalization (DG) (Wang et al.,
2021) also learns a domain-invariant model on multiple source domains in the
hope that it can generalize well to the target domain (Balaji et al., 2018; Li
et al., 2018; Muandet et al., 2013). The only difference between DA and DG is
that DA assumes the test data is accessible while DG does not. It is clear
that our problem settings are different from DA and DG. Firstly, DA and DG
does not built for temporal distribution characterization since the domains
are given a prior in their problems. Secondly, most DA and DG methods are for
classification tasks using CNNs than RNNs. Thus, they might fail to capture
the long-range temporal dependency in time series. Several methods applied
pre-training to RNNs (Cui et al., 2019; Chen and Moschitti, 2019; Gupta et
al., 2018; Fawaz et al., 2018; Yang et al., 2017) which is similar to CNN-
based pre-training.

(a) Overview of AdaRNN

(b) Temporal distribution characterization (TDC)

(c) Temporal distribution matching (TDM)

Figure 2. The framework of AdaRNN.

##  3\. Problem Formulation

###### Problem 1 ($r$-step ahead prediction).

Given a time series of $n$ segments
$\mathcal{D}=\\{\mathbf{x}_{i},\mathbf{y}_{i}\\}_{i=1}^{n}$, where
$\mathbf{x}_{i}=\\{x_{i}^{1},\cdots,x_{i}^{m_{i}}\\}\in\mathbb{R}^{p\times
m_{i}}$ is a $p$-variate segment of length $m_{i}$111In general, $m_{i}$ may
be different for different time segments., and
$\mathbf{y}_{i}=(y_{i}^{1},\ldots,y_{i}^{c})\in\mathbb{R}^{c}$ is the
corresponding label.

Learn a precise prediction model
$\mathcal{M}:\mathbf{x}_{i}\rightarrow\mathbf{y}_{i}$ on the future
$r\in\mathbb{N}^{+}$ steps 222When $r=1$, it becomes the one-step prediction
problem. for segments $\\{\mathbf{x}_{j}\\}_{j=n+1}^{n+r}$ in the same time
series.

In most existing prediction approaches, all time series segments,
$\\{\mathbf{x}_{i}\\}_{i=1}^{n+r},$ are assumed to follow the same data
distribution; a prediction model learned from all labeled training segments
are supposed to perform well on the unlabeled testing segments. However, this
assumption is too strong to hold in many real-world applications. In this
work, we consider a more practical problem setting: the distributions of the
training segments and the test segments can be different, and the
distributions of the training segments can also be changed over time as shown
in Figure 1. In the following, we formally define our problem.

###### Definition 0 (Covariate Shift (Shimodaira, 2000)).

Given the training and the test data from two distributions
$P_{train}(\mathbf{x},y),P_{test}(\mathbf{x},y)$, covariate shift is referred
to the case that the marginal probability distributions are different, and the
conditional distributions are the same, i.e., $P_{train}(\mathbf{x})\neq
P_{test}(\mathbf{x})$, and $P_{train}(y|\mathbf{x})=P_{test}(y|\mathbf{x})$.

Note that the definition of covariate shift is for non-time series data. We
now extend its definition for time series data as follows, which is referred
to as _temporal covariate shift_ (TCS) in this work.

###### Definition 0 (Temporal Covariate Shift).

Given a time series data $\mathcal{D}$ with $n$ labeled segments. Suppose it
can be split into $K$ periods or intervals, i.e.,
$\mathcal{D}=\\{\mathcal{D}_{1},\cdots,\mathcal{D}_{K}\\}$, where
$\mathcal{D}_{k}=\\{\mathbf{x}_{i},\mathbf{y}_{i}\\}^{n_{k+1}}_{i=n_{k}+1}$,
$n_{1}=0$ and $n_{k+1}=n$. Temporal Covariate Shift (TCS) is referred to the
case that all the segments in the same period $i$ follow the same data
distribution $P_{\mathcal{D}_{i}}(\mathbf{x},y)$, while for different time
periods $1\leq i\neq j\leq K$, $P_{\mathcal{D}_{i}}(\mathbf{x})\neq
P_{\mathcal{D}_{j}}(\mathbf{x})$ and
$P_{\mathcal{D}_{i}}(y|\mathbf{x})=P_{\mathcal{D}_{j}}(y|\mathbf{x})$.

To learn a prediction model with good generalization performance under TCS, a
crucial research issue is to capture the _common knowledge_ shared among
different periods of $\mathcal{D}$ (Kuznetsov and Mohri, 2014). Take the stock
price prediction as an example. Though the financial factors ($P(x)$) vary
with the change of market (i.e., different distributions in different periods
of time), some common knowledge, e.g., the economic laws and patterns
($P(y|x)$) in different periods, can still be utilized to make precise
predictions over time.

However, the number of periods $K$ and the boundaries of each period under TCS
are usually unknown in practice. Therefore, before designing a model to
capture commonality among different periods in training, we need to first
discover the periods by comparing their underlying data distributions such
that segments in the same period follow the same data distributions. The
formal definition of the problem studied in this work is described as follows.

###### Problem 2 ($r$-step TS prediction under TCS).

Given a time series of $n$ segments with corresponding labels,
$\mathcal{D}=\\{\mathbf{x}_{i},\mathbf{y}_{i}\\}_{i=1}^{n}$, for training.
Suppose there exist an unknown number of $K$ underlying periods in the time
series, so that segments in the same period $i$ follow the same data
distribution $P_{\mathcal{D}_{i}}(\mathbf{x},y)$, while for different time
periods $1\leq i\neq j\leq K$, $P_{\mathcal{D}_{i}}(\mathbf{x})\neq
P_{\mathcal{D}_{j}}(\mathbf{x})$ and
$P_{\mathcal{D}_{i}}(y|\mathbf{x})=P_{\mathcal{D}_{j}}(y|\mathbf{x})$. Our
goal is to automatically discover the $K$ periods in the training time series
data, and learn a prediction model
$\mathcal{M}:\mathbf{x}_{i}\rightarrow\mathbf{y}_{i}$ by exploiting the
commonality among different time periods, such that it makes precise
predictions on the future $r$ segments,
$\mathcal{D}_{tst}=\\{\mathbf{x}_{j}\\}_{j=n+1}^{n+r}$. Here we assume that
the test segments are in the same time period,
$P_{\mathcal{D}_{tst}}(\mathbf{x})\neq P_{\mathcal{D}_{i}}(\mathbf{x})$ and
$P_{\mathcal{D}_{tst}}(y|\mathbf{x})=P_{\mathcal{D}_{i}}(y|\mathbf{x})$ for
any $1\leq i\leq K$.

Note that learning the periods underlying the training time series data is
challenging as both the number of periods and the corresponding boundaries are
unknown, and the search space is huge. Afterwards, with the identified
periods, the next challenge is how to learn a good generalizable prediction
model $\mathcal{M}$ to be used in the future periods. If the periods are not
discovered accurately, it may affect the generalization performance of the
final prediction model.

##  4\. Our proposed model: AdaRNN

In this section, we present our proposed framework, termed Adaptive RNNs
(AdaRNN), to solve the temporal covariate shift problem. Figure 2(a) depicts
the overview of AdaRNN. As we can see, it mainly consists of two novel
algorithms:

  * •

_Temporal Distribution Characterization (TDC):_ to characterize the
distribution information in TS;

  * •

_Temporal Distribution Matching (TDM):_ to match the distributions of the
discovered periods to build a time series prediction model $\mathcal{M}$.

Given the training data, AdaRNN first utilizes TDC to split it into the
periods which fully characterize its distribution information. It then applies
the TDM module to perform distribution matching among the periods to build a
generalized prediction model $\mathcal{M}$. The learned $\mathcal{M}$ is
finally used to make $r$-step predictions on new data.

The rationale behind AdaRNN is as follows. In TDC, the model $\mathcal{M}$ is
expected to work under the _worst_ distribution scenario where the
distribution gaps among the different periods are large, thus the optimal
split of periods can be determined by _maximizing their dissimilarity_. In
TDM, $\mathcal{M}$ utilizes the common knowledge of the learned time periods
by matching their distributions via RNNs with a regularization term to make
precise future predictions.

###  4.1. Temporal distribution characterization

Based on _the principle of maximum entropy_ (Jaynes, 1982), maximizing the
utilization of shared knowledge underlying a times series under temporal
covariate shift can be done by finding periods which are most dissimilar to
each other, which is also considered as the worst case of temporal covariate
shift since the cross-period distributions are the most diverse. Therefore, as
Figure 2(b) shows, TDC achieves this goal for splitting the TS by solving an
optimization problem whose objective can be formulated as:

(1) $\begin{split}\max_{0<K\leq
K_{0}}\,{\max_{n_{1},\cdots,n_{K}}\frac{1}{K}\sum_{1\leq i\neq j\leq
K}d(\mathcal{D}_{i},\mathcal{D}_{j})}\\\
\mathrm{s.t.}\,\,\forall\,i,\,\Delta_{1}<|\mathcal{D}_{i}|<\Delta_{2};\,\sum_{i}|\mathcal{D}_{i}|=n\end{split}$

where $d$ is a distance metric, $\Delta_{1}$ and $\Delta_{2}$ are predefined
parameters to avoid trivial solutions (e.g., very small values or very large
values may fail to capture the distribution information), and $K_{0}$ is the
hyperparameter to avoid over-splitting. The metric $d(\cdot,\cdot)$ in Eq. (1)
can be any distance function, e.g., Euclidean or Editing distance, or some
distribution-based distance / divergence, like MMD (Gretton et al., 2012) and
KL-divergence. We will introduce how to select $d(\cdot,\cdot)$ in Section
4.3.

The learning goal of the optimization problem (1) is to maximize the averaged
period-wise distribution distances by searching $K$ and the corresponding
periods so that the distributions of each period are as diverse as possible
and the learned prediction model has better a more generalization ability.

We explain in detail for the splitting scheme in (1) with the principle of
maximum entropy (ME). Why we need the most dissimilar periods instead of the
most similar ones? According to ME, when no prior assumptions are made on the
splitting of the time series data, it is reasonable that the distributions of
each period become as diverse as possible to maximize the entropy of the total
distributions. This allows more general and flexible modeling of the future
data. Therefore, since we have no prior information on the test data which is
unseen during training, it is more reasonable to train a model at the worst
case, which can be simulated using diverse period distributions. If the model
is able to learn from the worst case, it would have better generalization
ability on unseen test data. This assumption has also been validated in
theoretical analysis of time series models (Kuznetsov and Mohri, 2014;
Oreshkin et al., 2021) that diversity matters in TS modeling.

In general, the time series splitting optimization problem in (1) is
computationally intractable and may not have a closed-form solution. By
selecting a proper distance metric, however, the optimization problem (1) can
be solved with dynamic programming (DP) (Ross, 2014). In this work, by
considering the scalability and the efficiency issues on large-scale data, we
resort to a greedy algorithm to solve (1). Specifically, for efficient
computation and avoiding trivial solutions, we evenly split the time series
into $N=10$ parts, where each part is the minimal-unit period that cannot be
split anymore. We then randomly search the value of $K$ in $\\{2,3,5,7,10\\}$.
Given $K$, we choose each period of length $n_{j}$ based on a greedy strategy.
Denote the start and the end points of the time series by $A$ and $B$,
respectively. We first consider $K=2$ by choosing $1$ splitting point (denote
it as $C$) from the $9$ candidate splitting points via maximizing the
distribution distance $d(S_{AC},S_{CB})$. After $C$ is determined, we consider
$K=3$ and use the same strategy to select another point $D$. A similar
strategy is applied to different values of $K$. Our experiments show that this
algorithm can select the more appropriate periods than random splits. Also, it
shows that when $K$ is very large or very small, the final performance of the
prediction model becomes poor (Section 5.6.1).

###  4.2. Temporal distribution matching

Given the learned time periods, the TDM module is designed to learn the common
knowledge shared by different periods via matching their distributions. Thus,
the learned model $\mathcal{M}$ is expected to generalize well on unseen test
data compared with the methods which only rely on local or statistical
information.

The loss of TDM for prediction, $\mathcal{L}_{pred}$, can be formulated as:

(2)
$\mathcal{L}_{pred}(\theta)=\frac{1}{K}\sum_{j=1}^{K}\frac{1}{|\mathcal{D}_{j}|}\sum_{i=1}^{|\mathcal{D}_{j}|}\ell(\mathbf{y}_{i}^{j},\mathcal{M}(\mathbf{x}_{i}^{j};\theta)),$

where $(\mathbf{x}_{i}^{j},\mathbf{y}^{j}_{i})$ denotes the $i$-th labeled
segment from period $\mathcal{D}_{j}$, $\ell(\cdot,\cdot)$ is a loss function,
e.g., the MSE loss, and $\theta$ denotes the learnable model parameters.

However, minimizing (2) can only learn the predictive knowledge from each
period, which cannot reduce the distribution diversities among different
periods to harness the common knowledge. A naïve solution is to match the
distributions in each period-pair $\mathcal{D}_{i}$ and $\mathcal{D}_{j}$ by
adopting some popular distribution matching distance ($d(\cdot,\cdot)$) as the
regularizer. Following existing work on domain adaptation (Ganin et al., 2016;
Sun and Saenko, 2016) that distribution matching is usually performed on high-
level representations, we apply the distribution matching regularization term
on the final outputs of the cell of RNN models. Formally, we use
$\mathbf{H}=\\{\mathbf{h}^{t}\\}^{V}_{t=1}\in\mathbb{R}^{V\times q}$ to denote
the $V$ hidden states of an RNN with feature dimension $q$. Then, the period-
wise distribution matching on the final hidden states for a pair
$(\mathcal{D}_{i},\mathcal{D}_{j})$ can be represented as:

$\mathcal{L}_{dm}(\mathcal{D}_{i},\mathcal{D}_{j};\theta)=d(\mathbf{h}_{i}^{V},\mathbf{h}_{j}^{V};\theta).$

Unfortunately, the above regularization term fails to capture the _temporal
dependency_ of each hidden state in the RNN. As each hidden state only
contains _partial_ distribution information of an input sequence, _each_
hidden state of the RNN should be considered while constructing a distribution
matching regularizer as described in the following section.

####  4.2.1. Temporal distribution matching

As shown in Figure 2(c), we propose the _Temporal Distribution Matching (TDM)_
module to adaptively match the distributions between the RNN cells of two
periods while capturing the temporal dependencies. TDM introduces the
_importance vector_ $\bm{\alpha}\in\mathbb{R}^{V}$ to learn the relative
importance of $V$ hidden states inside the RNN, where all the hidden states
are weighted with a normalized $\bm{\alpha}$. Note that for each pair of
periods, there is an $\bm{\alpha}$, and we omit the subscript if there is no
confusion. In this way, we can _dynamically_ reduce the distribution
divergence of cross-periods.

Given a period-pair $(\mathcal{D}_{i},\mathcal{D}_{j})$, the loss of temporal
distribution matching is formulated as:

(3)
$\mathcal{L}_{tdm}(\mathcal{D}_{i},\mathcal{D}_{j};\theta)=\sum_{t=1}^{V}\alpha_{i,j}^{t}d(\mathbf{h}^{t}_{i},\mathbf{h}^{t}_{j};\theta),$

where $\alpha_{i,j}^{t}$ denotes the distribution importance between the
periods $\mathcal{D}_{i}$ and $\mathcal{D}_{j}$ at state $t$.

All the hidden states of the RNN can be easily computed by following the
standard RNN computation. Denote by $\delta(\cdot)$ the computation of a next
hidden state based on a previous state. The state computation can be
formulated as

(4) $\mathbf{h}_{i}^{t}=\delta(\mathbf{x}_{i}^{t},\mathbf{h}^{t-1}_{i}).$

By integrating (2) and (3), the final objective of temporal distribution
matching (one RNN layer) is:

(5)
$\mathcal{L}(\theta,\bm{\alpha})=\mathcal{L}_{pred}(\theta)+\lambda\frac{2}{K(K-1)}\sum_{i,j}^{i\neq
j}\mathcal{L}_{tdm}(\mathcal{D}_{i},\mathcal{D}_{j};\theta,\bm{\alpha}),$

where $\lambda$ is a trade-off hyper-parameter. Note that in the second term,
we compute the average of the distribution distances of all pairwise periods.
For computation, we take a mini-batch of $\mathcal{D}_{i}$ and
$\mathcal{D}_{j}$ to perform forward operation in RNN layers and concatenate
all hidden features. Then, we can perform TDM using (5).

####  4.2.2. Boosting-based importance evaluation

We propose a _Boosting-based importance evaluation_ algorithm to learn
$\bm{\alpha}$. Before that, we first perform pre-training on the network
parameter $\mathbf{\theta}$ using the fully-labeled data across all periods,
i.e., use (2). This is to learn better hidden state representations to
facilitate the learning of $\bm{\alpha}$. We denote the pre-trained parameter
as $\mathbf{\theta}_{0}$.

With $\mathbf{\theta}_{0}$, TDM uses a boosting-based (Schapire, 2003)
procedure to learn the hidden state importance. Initially, for each RNN layer,
all the weights are initialized as the same value in the same layer, i.e.,
$\bm{\alpha}_{i,j}=\\{1/V\\}^{V}$. We choose the cross-domain distribution
distance as the indicator of boosting. If the distribution distance of epoch
$n+1$ is larger than that of epoch $n$, we increase the value of
$\alpha_{i,j}^{t,(n+1)}$ to enlarge its effect for reducing the distribution
divergence. Otherwise, we keep it unchanged. The boosting is represented as:

(6) $\alpha_{i,j}^{t,(n+1)}=\left\\{\begin{aligned}
&\alpha_{i,j}^{t,(n)}\times
G(d^{t,(n)}_{i,j},d^{t,(n-1)}_{i,j})&&d^{t,(n)}_{i,j}\geq d^{t,(n-1)}_{i,j}\\\
&\alpha_{i,j}^{t,(n)}&&\text{otherwise}\\\ \end{aligned}\right.$

where

(7)
$G(d^{t,(n)}_{i,j},d^{t,(n-1)}_{i,j})=(1+\sigma(d^{t,(n)}_{i,j}-d^{t,(n-1)}_{i,j}))$

is the updating function computed by distribution matching loss at different
learning stages. And
$d^{t,(n)}_{i,j}=D(\mathbf{h}_{i}^{t},\mathbf{h}_{j}^{t};\alpha_{i,j}^{t,(n)})$
is the distribution distance at time step $t$ in epoch $n$. $\sigma(\cdot)$ is
the sigmoid function. It is easy to see that $G(\cdot,\cdot)>1$, ensuring the
increment of the importance. Similar to naive method, we normalize it as
$\alpha_{i,j}^{t,(n+1)}=\frac{\alpha_{i,j}^{t,(n+1)}}{\sum_{j=1}^{V}\alpha_{i,j}^{t,(n+1)}}$.
By (3) and (6), we can learn the value of $\bm{\alpha}$.

###### Remark 1.

The objective (3) is defined on one RNN layer, it can be easily implemented
for multiple layers to achieve multi-layer distribution matching. As for
inference, we simply use the optimal network parameter
$\mathbf{\theta}^{\ast}$. The computation of domain-wise distribution
distances can also be made efficient following existing work (Li et al.,
2018).

###### Remark 2.

In fact, there is also a naïve approach to acquire $\bm{\alpha}$ by using
another network with weight $\mathbf{W}_{i,j}\in\mathbb{R}^{2q\times V}$ that
takes $(\mathbf{H}_{i},\mathbf{H}_{j})$ as inputs and output $\bm{\alpha}$.
For instance, $\bm{\alpha}$ can be learned as
$\bm{\alpha}_{i,j}=g(\mathbf{W}_{i,j}\odot[\mathbf{H}_{i},\mathbf{H}_{j}]^{\top}$)
where $g$ is an activation and normalization function and $\odot$ is element-
wise production. After computing $\alpha_{i,j}$, we normalize it by a softmax
function. Unfortunately, this naïve approach does not work in reality for two
reasons. First, since $\bm{\alpha}_{i,j}$ and $\mathbf{\theta}$ are highly
correlated and at early training stage, the hidden state representations
learned by $\mathbf{\theta}$ are less meaningful, which will result in
insufficient learning of $\bm{\alpha}_{i,j}$. Second, it is expensive to learn
such $\mathbf{W}_{i,j}$ for each domain pair in RNN models.

Algorithm 1 AdaRNN

0: A time series dataset $\mathcal{D}$, $\lambda$, max iteration number $Iter$

1: Perform temporal distribution characterization by solving (1) to get $K$
periods $\\{\mathcal{D}_{i}\\}$’s.

2: End-to-end pre-training by minimizing (2) with $\lambda=0$

3: For iteration $i=1\text{ to }Iter$ :

4: Learn the value of $\bm{\alpha}$ and $\theta$ by solving (5) and using (6)

5: End For

6: return Optimal parameters $\mathbf{\theta}^{\ast},\bm{\alpha}^{\ast}$.

###  4.3. Computation of the distribution distance

AdaRNN is agnostic to RNN structures (vanilla RNNs, LSTMs, and GRUs) and the
distribution distances, i.e., the function $d(\cdot,\cdot)$. Technically,
$d(\cdot,\cdot)$ in TDC and TDM can be the same choice. We adopt several
popular distances: cosine distance, MMD (Gretton et al., 2012) and adversarial
distance (Ganin et al., 2016). Also note that the TDC and TDM are currently
two separate stages for controlling computation complexity. It shall be a
future work to end-to-end optimize these two stages. The complete process of
AdaRNN is presented in Algorithm 1. The detailed implementations of these
distances are presented in Appendix.

##  5\. Experiments

###  5.1. Setup

We mainly use GRUs (Gated Recurrent Units) (Chung et al., 2014) as the base
RNN cells for its high performance in real applications333It is natural to use
simple RNNs or LSTMs.. We test AdaRNN in four real-world datasets as
summarized in Table 1.

Table 1. Information of the datasets used in this paper.

Dataset | #Train | #Valid | #Test | dim. ($p$) | Task
---|---|---|---|---|---
UCI activity | 6,000 | 1,352 | 2,947 | 128 | Classification
Air quality | 29,232 | 2,904 | 2,832 | 6 | Regression
Electric power | 1,235,964 | 413,280 | 413,202 | 7 | Regression
Stock price | 778,200 | 271,690 | 504,870 | 360 | Regression

We compare AdaRNN with four categories of methods:

  * •

Traditional TS modeling methods, including ARIMA (Zhang, 2003), FBProphet
(Facebook, 2021), LightGBM, and GRU (Chung et al., 2014);

  * •

Latest TS models, including LSTNet (Lai et al., 2018) and STRIPE (Le Guen and
Thome, 2020)444STRIPE is an improved and stronger version of DILATE (Vincent
and Thome, 2019).;

  * •

Transformer (Vaswani et al., 2017) by removing its mask operation;

  * •

Variants of popular domain adaptation / generalization methods and we denote
them as “MMD-RNN” and “DANN-RNN”.

Note that the comparison is mainly for the final prediction performance using
temporal distribution matching after obtaining the time periods using TDC,
which the evaluation of TDC is in Section 5.6.1. Transformer (Vaswani et al.,
2017) was originally proposed for machine translation. Therefore, we alter it
by removing the masks for TS data by following implementation
555https://timeseriestransformer.readthedocs.io/en/latest/README.html. We use
$4$ encoder layers of Transformer with $8$ heads for self-attention tuned by
cross-validation to ensure that it achieves the best performance on the
datasets. Existing DA / DG methods cannot be directly applied to our problem,
since most of them are for CNN-based classification tasks. Therefore, we use
variants of them. Specifically, we use “MMD-RNN” to denote popular MMD-based
methods such as MEDA (Wang et al., 2018, 2020) and MMD-AAE (Li et al., 2018).
We use “DANN-RNN” to denote popular domain-adversarial training methods such
as RevGrad (Ganin et al., 2016) and DAAN (Yu et al., 2019). These two
distances are widely adopted in recent DA and DG literature. We change their
backbone network to be RNNs which are the same as other comparison methods and
then add the MMD or adversarial distances to the final output of the RNN
layers.

All methods use the same train-valid-test split and periods after TDC and the
final results are averaged on five random runs. Optimal hyperparameters are
tuned on the validation set. Note that to balance the efficiency and
performance in AdaRNN, we limit the range of $K$ in $\\{2,3,5,7,10\\}$ to
acquire the best splitting of periods. We set the pre-training epochs to be
$10$ in TDM. We use different distance function $d$ and the main results are
based on the MMD (Gretton et al., 2012). Other distances are discussed later.
Code of AdaRNN is at
https://github.com/jindongwang/transferlearning/tree/master/code/deep/adarnn.

###  5.2. Human activity recognition

The UCI smartphone activity (Almaslukh et al., 2017) is a time-series dataset
for classification task. It is collected by thirty volunteers wearing a
smartphone to record the accelerometer, gyroscope, and magnetometer signals
while performing six different activities (walking, upstairs, downstairs,
sitting, standing, and lying). We use $7,352$ instances for training and
$2,947$ instances as the test following (Almaslukh et al., 2017). It is clear
that training and testing sets have different distributions and TCS exists in
the training set due to different activities and users. We firstly clip the
data using sliding window with the size of 128. As there are 9 channels for
each instance, we regard it a sequence with length of 128 and feature of 9
dimension. For this task, we use accuracy (ACC), precision (P), recall (R),
F1, and area under curve (AUC) as the evaluation metrics.

The network is composed of two-layer GRUs with the hidden state dimension $32$
and a FC layer with output to be $r=6$. We optimize by Adam optimizer with the
learning rate of 0.005 with a batch size 64. We set $\lambda=0.1$. On this
dataset, we did not run the latest methods such as LSTNet and STRIPE as well
as FBProphet and ARIMA since they are built for regression tasks. Transformer
is not compared since we did not get good performance.

Table 2 shows the results on this classification task. It is obvious that
AdaRNN achieves the best performance on all evaluation metrics that
outperforms the adversarial-based DANN method by $\bm{2.56}\%$ in accuracy and
$\bm{3.07}\%$ in F1 score. This means that AdaRNN is effective in non-
stationary time series classification tasks.

Table 2. Results on UCI time series classification dataset.

Method | ACC | P | R | F1 | AUC
---|---|---|---|---|---
LightGBM | 84.11 | 83.73 | 83.63 | 84.91 | 90.23
GRU | 85.68 | 85.62 | 85.51 | 85.46 | 91.33
MMD-RNN | 86.39 | 86.80 | 86.26 | 86.38 | 91.77
DANN-RNN | 85.88 | 85.59 | 85.62 | 85.56 | 91.41
AdaRNN | 88.44 | 88.71 | 88.59 | 88.63 | 93.19

Table 3. Results on air quality prediction (left) and household electric power
consumption prediction (right).

| Dongsi | Tiantan | Nongzhanguan | Dingling | $\Delta(\%)$ | Electric Power
---|---|---|---|---|---|---
| RMSE | MAE | RMSE | MAE | RMSE | MAE | RMSE | MAE
FBProphet (Facebook, 2021) | 0.1866 | 0.1403 | 0.1434 | 0.1119 | 0.1551 | 0.1221 | 0.0932 | 0.0736 | - | 0.080
ARIMA | 0.1811 | 0.1356 | 0.1414 | 0.1082 | 0.1557 | 0.1156 | 0.0922 | 0.0709 | - | -
GRU | 0.0510 | 0.0380 | 0.0475 | 0.0348 | 0.0459 | 0.0330 | 0.0347 | 0.0244 | 0.00 | 0.093
MMD-RNN | 0.0360 | 0.0267 | 0.0183 | 0.0133 | 0.0267 | 0.0197 | 0.0288 | 0.0168 | -61.31 | 0.082
DANN-RNN | 0.0356 | 0.0255 | 0.0214 | 0.0157 | 0.0274 | 0.0203 | 0.0291 | 0.0211 | -59.97 | 0.080
LightGBM | 0.0587 | 0.0390 | 0.0412 | 0.0289 | 0.0436 | 0.0319 | 0.0322 | 0.0210 | -11.08 | 0.080
LSTNet (Lai et al., 2018) | 0.0544 | 0.0651 | 0.0519 | 0.0651 | 0.0548 | 0.0696 | 0.0599 | 0.0705 | - | 0.080
Transformer (Vaswani et al., 2017) | 0.0339 | 0.0220 | 0.0233 | 0.0164 | 0.0226 | 0.0181 | 0.0263 | 0.0163 | -61.20 | 0.079
STRIPE (Le Guen and Thome, 2020) | 0.0365 | 0.0216 | 0.0204 | 0.0148 | 0.0248 | 0.0154 | 0.0304 | 0.0139 | -64.60 | 0.086
AdaRNN | 0.0295 | 0.0185 | 0.0164 | 0.0112 | 0.0196 | 0.0122 | 0.0233 | 0.0150 | -73.57 | 0.077

(a) #Domain in TDC

(b) Different domain split

(c) Temporal distribution matching

(d) Effectiveness of $\alpha$

Figure 3. Ablation study. (a) Analysis of $K$ for temporal distribution
characterization. (b) Different domain split strategies. (c) Comparison of w.
or w./o. adaptive weights in distribution matching. (d) Effectiveness of
temporal distribution matching.

###  5.3. Air quality prediction

The air-quality dataset (Zhang et al., 2017) contains hourly air quality
information collected from 12 stations in Beijing from 03/2013 to 02/2017. We
randomly chose four stations (Dongsi, Tiantan, Nongzhanguan, and Dingling) and
select six features (PM2.5, PM10, S02, NO2, CO, and O3). Since there are some
missing data, we simply fill the empty slots using averaged values. Then, the
dataset is normalized before feeding into the network to scale all features
into the same range. This process is accomplished by max-min normalization and
ranges data between 0 and 1.

The network is composed of two-layer GRUs with the dimension of the hidden
state to be 64 and two bottleneck layers which contains two FC layers, and an
FC layer with output to be $r=1$. We set $\lambda=0.5$. We optimize all the
models by Adam optimizer with the learning rate of 0.005, we set the batch
size to be 36.

Table 3 presents the results where the last column “$\Delta(\%)$” denotes the
average increment over the baseline GRU. It can be seen that the proposed
method achieves the best results in all four stations. Our AdaRNN
significantly outperforms the strong baseline STRIPE (Le Guen and Thome, 2020)
by $\bm{8.97}\%$ in RMSE reduction.

###  5.4. Household electric power consumption

This dataset (Kaggle, 2021) contains 2,075,260 measurements gathered between
16/12/2006 and 26/11/2010 with a one-minute sampling rate. It contains several
attributes (global active power, global reactive power, voltage, global
intensity, and three substrings). We get 2,062,346 measurements for the whole
dataset after removing all the null data. We construct the train/valid/test
sets with a ratio of $6:2:2$, i.e., train on data from 16/12/2006 to
24/04/2009 and test on data from 25/02/2010 to 26/11/2010 and the rest is
valid set. We use the data of 5 consecutive days to predict the value of next
day.

The network is composed of two-layer GRUs with the dimension set to be 64 and
two bottleneck layers which contains two FC layers, and a FC layer with output
to be $r=1$. We set $\lambda=0.001$. We optimize all the models by Adam
optimizer with the learning rate of 0.0005 and batch size of 36.

The right part of Table 3 shows the RMSE of predicting the household power
consumption using different methods. Again, our AdaRNN achieves the best
performance.

###  5.5. Stock price prediction

We further evaluate the performance of AdaRNN on a large private finance
dataset where the task is to predict the stock price given the historical data
from 01/2007 to 12/2019. This dataset contains over 2.8M samples with 360
financial factors as the features. We use the data from 01/2017 to 12/2019 as
the test set, and the data from 01/2007 to 12/2014 as the training set with
the rest as the validation set. We use information coefficient (IC) and
information ratio (IR) as the evaluation metrics following existing work
(Kohara et al., 1997). The detailed description and computation of these
metrics are in appendix.

The network is composed of two-layer GRUs with the dimension of hidden state
to be 64 and two bottleneck layers which contains one FC layers, and a FC
layer with output to be $r=1$. We optimize all the models by Adam optimizer
with the learning rate of 0.0002, we set the batch size to be 800 and
$\lambda=0.5$.

Table 4 shows that our proposed AdaRNN outperforms other comparison methods in
all metrics. While achieving the best IC values, its RankIC can still be
higher than other methods. This means that AdaRNN is relatively steady in real
applications.

Table 4. Results on stock price prediction.

Method | IC | ICIR | RankIC | RankICIR | RawIC | RawICIR
---|---|---|---|---|---|---
LightGBM | 0.063 | 0.551 | 0.056 | 0.502 | 0.064 | 0.568
GRU | 0.106 | 0.965 | 0.098 | 0.925 | 0.109 | 0.986
MMD-RNN | 0.107 | 0.962 | 0.101 | 0.926 | 0.108 | 0.967
DANN-RNN | 0.106 | 0.964 | 0.103 | 0.924 | 0.107 | 0.966
Transformer (Vaswani et al., 2017) | 0.104 | 0.935 | 0.099 | 0.920 | 0.101 | 0.946
STRIPE (Le Guen and Thome, 2020) | 0.108 | 0.987 | 0.101 | 0.946 | 0.109 | 0.993
AdaRNN | 0.115 | 1.071 | 0.110 | 1.035 | 0.116 | 1.077

###  5.6. Ablation study

####  5.6.1. Temporal distribution characterization

To evaluate TDC, we design two experiments. Firstly, we compare the results of
$K=2,3,5,7,10$ to analyze the importance of $K$ in Figure 3(a). We see that
the performance is changing with the increment of $K$ and the best result is
achieved when $K=3,5$ for two stations on air quality prediction,
respectively. Then, when $K$ continues to increase, the performance drops. It
means that $K$ is important in characterizing the distribution information in
non-stationary TS.

Secondly, Figure 3(b) shows the comparison of domain split algorithms using
the same distribution matching method when $K=2$. Here, “Split 1” denotes a
random split and “Split 2” denotes the split where all periods are with
similar distributions (i.e., just the opposite of TDC). The “distance” denotes
the distribution distance. The results indicate that our TDC achieves the best
performance in RMSE with the largest distribution distance. The results of
other values of $K$ are also the same. Therefore, it is important that we
split the periods to the _worst_ case when the distributions are the most
diverse. Both experiments show that TDC could effectively characterize the
distribution information in time series. Evaluation of TDC using other
distances are in appendix.

(a) Different distribution distance

(b) Change of distance

(c) Multi-step prediction

(d) Convergence

(e) Training time

Figure 4. (a) Multi-step prediction of air quality. (b) TDM is agnostic to
distribution distances in different stations. (c) The change of distribution
distance. (d) Convergence analysis. (e) Training time.

####  5.6.2. Temporal distribution matching

We analyze the TDM module by evaluating the performance of pre-training and
the boosting-based method. We compare four variants of TDM: (1) naïve approach
(i.e., learning $\bm{\alpha}$ by a feed-forward layer as discussed in remark
2) w./o pre-training, (2) boosting w./o pre-training (3) pre-training + naïve,
(4) pre-training + boosting (Ours).

Figure 3(c) shows the performance on two stations. We observe that the pre-
training technique helps both naïve and boosting-based methods to get better
performance. More importantly, our boosting-based method can achieve the best
performance with pre-training. Compared with the STRIPE method from Table 3,
we see that almost all four variants of TDM can achieve better performance
than STRIPE. We also observe that by manually setting the same importance to
each hidden state, the results are not comparable. To summarize, it is
necessary to consider the importance of each hidden state when trying to build
an adaptive RNN model.

To evaluate the importance vector $\bm{\alpha}$, we compare the results of
with or without importance vector in Figure 3(d). The results indicate that by
taking the same distribution distance, our AdaRNN achieve the best results.
This demonstrates that the different distributions of each hidden state is
important to model in RNN-based time series modeling, to which our AdaRNN is
capable of dynamically evaluating their importance to achieve the best
performance.

###  5.7. Further analysis

####  5.7.1. Distribution distance

AdaRNN is agnostic to the distribution distance. Here we evaluate this
property by running TDM with four different kinds of distribution distances:
MMD (Borgwardt et al., 2006), CORAL (Sun and Saenko, 2016), Cosine, and
domain-adversarial distance (Ganin et al., 2016). Figure 4(a) presents the
results on three stations for air quality prediction. Combining the results
from Table 3, we observe that AdaRNN is robust to the choice of distribution
distance while achieving the best performance. Moreover, Figure 4(b) shows
that by adding the importance weights $\bm{\alpha}$, our AdaRNN achieves
lowest distribution distances compared to MMD and adversarial training.

####  5.7.2. Multi-step prediction

We analyze the performance of AdaRNN for multi-step ($r>1$) air quality
prediction and compare with STRIPE (Le Guen and Thome, 2020) by predicting air
quality index in next $6,12,18,24$ hours (the output sequence length is
$6,12,18,24$ accordingly). Figure 4(c) shows the results on one station. We
see that AdaRNN achieves the best performance for multi-step prediction. In
addition, as the prediction steps increase ($6\rightarrow 12\rightarrow
18\rightarrow 24$), the performances of all methods are becoming worse since
it is more difficult to model the longer sequences and also affected by the
cumulative errors.

####  5.7.3. Convergence and time complexity analysis

We analyze the convergence of AdaRNN by recording its training loss for
prediction and distribution matching in Figure 4(d). We see that AdaRNN can be
easily trained with quick convergence. On the other hand, AdaRNN is based on
RNNs which are autoregressive models. So it is reasonable that AdaRNN takes
more time for training than traditional RNNs. Figure 4(e) shows the training
time comparison between AdaRNN, GRU, and STRIPE (Le Guen and Thome, 2020). We
see that other than the best performance, the training time of AdaRNN is still
comparable to existing methods. The inference time of AdaRNN is the same as
existing RNN-based models since we only need to compute Eq. (2).

(a) MMD-RNN

(b) DANN-RNN

(c) AdaRNN

(d) Differences

Figure 5. Prediction vs. ground truth.

###  5.8. Case study: prediction vs. ground truth

Taking the station Dongsi as an example, we show the prediction vs. ground
truth values of different methods in Figure 5, where the red circles denote
the bad cases. We see that DANN and MMD achieve worse results than our AdaRNN
since they have relatively worse predictions in many points. Especially in
Figure 5(d), we show the absolute difference between the prediction of each
method and the ground-truth. We can clearly see that our AdaRNN outperforms
all methods with much less mistakes.

##  6\. Extensions

Apart from RNN-based models, in this section, we add the adaptive importance
weights to each hidden representations in the Transformer (Vaswani et al.,
2017) model, which is claimed more powerful than RNN-based models in the
latest studies. We add the importance weights $\bm{\alpha}$ to the
representations of each self-attention block and term this extension as
_AdaTransformer_. As shown in Table 5, this pilot study shows the power of the
AdaRNN in Transformers. We believe more improvements can be made in the
future.

Table 5. Results of vanilla and adaptive transformer Method | Station 1 | Station 2
---|---|---
Vanilla Transformer | 0.028 | 0.035
AdaTransformer | 0.025 | 0.030

##  7\. Conclusions and Future Work

This paper proposed to study the more realistic and challenging temporal
covariate shift (TCS) problem for non-stationary time series. We proposed the
AdaRNN framework to learn an adaptive RNN model for better generalization.
AdaRNN consists of two novel algorithms: temporal distribution
characterization to characterize the distribution information in TS and
temporal distribution matching to build the generalized RNN model by
distribution matching. Extensive experiments show its effectiveness in three
datasets.

In the future, we plan to extend this work from both algorithm and application
level. First, explore deeper extension of AdaRNN to Transformer for better
performance. Second, integrate the two stages of AdaRNN in an end-to-end
network for easier training.

##  Appendix A Distribution Distance

We adopt four widely used distribution distance functions following existing
work on DA/DG, i.e., cosine, MMD (Borgwardt et al., 2006), CORAL (Sun and
Saenko, 2016), and domain adversarial discrepancy (Ganin et al., 2016).

Cosine. Cosine distance is widely used in time series data (Wang and Oates,
2015; Lei et al., 2019) to measure the similarity between two distributions.
Given the data $\mathbf{h}_{s}$ and $\mathbf{h}_{t}$, cosine distance is
defined as:

(8)
$d_{cosine}(\mathbf{h}_{s},\mathbf{h}_{t})=1-\frac{\left<\mathbf{h}_{s},\mathbf{h}_{t}\right>}{||\mathbf{h}_{s}||\cdot||\mathbf{h}_{t}||}.$

Maximum Mean Discrepancy (MMD). The MMD (Gretton et al., 2012) is a non-
parametric distance between two probability distributions. MMD measures the
distance of the mean embeddings of the samples from two distributions in a
Reproducing Kernel Hilbert Space (RKHS). MMD can be empirically estimated by

(9) $\displaystyle d_{mmd}(\mathbf{h}_{s},\mathbf{h}_{t})$
$\displaystyle=\frac{1}{n_{s}^{2}}\sum_{i,j=1}^{n_{s}}k(h_{s_{i}},h_{s_{j}})+\frac{1}{n_{t}^{2}}\sum_{i,j=n_{s}+1}^{n_{s}+n_{t}}k(h_{s_{i}},h_{s_{j}})$
$\displaystyle-\frac{2}{n_{s}n_{t}}\sum_{j=n_{s}+1}^{n_{s}+n_{t}}k(h_{s_{i}},h_{s_{j}}),$

where $k(\cdot,\cdot)$ is the kernel function such as RBF kernel and linear
kernel, and $n_{s}=|h_{s}|,n_{t}=|h_{t}|$ are the number of the data from two
distributions, respectively.

Deep Correlation Alignment (CORAL). The CORAL distance (Sun and Saenko, 2016)
is defined as the distance of the second-order statistic (covariance) of the
samples from two distributions:

(10)
$d_{coral}(\mathbf{h}_{s},\mathbf{h}_{t})=\frac{1}{4q^{2}}||\mathbf{C}_{s}-\mathbf{C}_{t}||_{F}^{2},$

where $q$ is the dimension of the features, and $\mathbf{C}_{s}$ and
$\mathbf{C}_{t}$ are the covariance matrices of the two distributions,
respectively.

Domain Adversarial Discrepancy. The domain discrepancy can be parameterized as
a neural network and it is referred to as the domain adversarial discrepancy
(Ganin et al., 2016). An additional network named domain discriminator denoted
by $D$ is introduced. The domain adversarial objective is defined as:

(11) $\displaystyle
l_{adv}(\mathbf{h}_{s},\mathbf{h}_{t})=\mathbb{E}[\log[D(\mathbf{h}_{s})]]+\mathbb{E}[\log[1-D(\mathbf{h}_{t})]],$

where $\mathbb{E}$ denotes expectation. Hence, the adversarial discrepancy is

(12)
$d_{adv}(\mathbf{h}_{s},\mathbf{h}_{t})=-l_{adv}(\mathbf{h}_{s},\mathbf{h}_{t}).$

##  Appendix B Different distances in TDC

We analyze temporal distribution characterization (TDC) by using different
distance functions. We set $K=2$ for TDC and compare its performance with one
random domain split and the opposite domain split (i.e., with the smaller
distribution distance).

The results in Table 6 indicate that our TDC algorithm achieves the best
performance in RMSE and MAE with the largest distribution distance under most
distance functions. When using cosine distance, our split achieves the second
largest distribution distance but it gets the best performance in RMSE and
MAE. The results show that TDC could effectively characterize the distribution
information and is agnostic to distance functions.

Table 6. Results of different distances in TDC

Split | $|\mathcal{D}_{1}|/|\mathcal{D}_{2}|$ |  $d$(MMD) |  $d$(DTW) |  $d$(CORAL) |  $d$(Cosine) | RMSE | MAE
---|---|---|---|---|---|---|---
Split1 | 0.75/0.25 | 0.898 | 2.54 | 9.9999884E-1 | 0.9748 | 0.0233 | 0.0179
Split2 | 0.25/0.75 | 0.910 | 2.60 | 9.9999902E-1 | 0.9966 | 0.0239 | 0.0197
Ours | 0.66/0.33 | 0.932 | 2.79 | 9.9999919E-1 | 0.9861 | 0.0164 | 0.0112

##  Appendix C Stock price prediction: Metrics

The evaluation metrics for stock price prediction have been widely adopted in
previous work (Kohara et al., 1997). The information coefficient (IC)
describes the correlation between predicted and actual stock returns,
sometimes used to measure the contribution of a financial analyst. The IC can
range from $1.0$ to $-1.0$. An IC of $+1.0$ indicates a perfect linear
relationship between predicted and actual returns, while an IC of $0.0$
indicates no linear relationship. An IC of $-1.0$ indicates that the analyst
always fails at making a correct prediction. IC is defined as:

(13) $IC=corr(f_{t-1},r_{t}),$

where $f_{t-1}$ is the factor value of the stock in period $t-1$ and $r_{t}$
is the stock return rate of period $t$. $corr(\cdot,\cdot)$ is the correlation
functions. Besides, there are also some variants of IC, such as rankIC, which
is

(14) $rankIC=corr({order}_{t-1}^{f},{order}_{t}^{r}),$

where ${order}_{t-1}^{f}$ is the factor rank of each stock in period $t-1$ and
${order}_{t}^{r}$ is the ranking of each stock’s return rate in period $t$.

The information ratio (IR) of an actively managed portfolio is defined as the
portfolio’s mean return over a benchmark portfolio return divided by the
tracking error (standard deviation of the excess return), which is defined as

(15) $IR=IC\times\sqrt{BR},$

where BR is breadth or number of independent information sources.

We also call IR the ICIR. Based on IC and ICIR, we further use RankIC and
RankICIR to evaluate the robustness of models against permuations, and use
RawIC and RawICIR to denote the performance of unnormalized data. To sum up,
the higher they are, the better the model is.

## References

  * (1)
  * Almaslukh et al. (2017) Bandar Almaslukh, Jalal AlMuhtadi, and Abdelmonim Artoli. 2017\.  An effective deep autoencoder approach for online smartphone-based human activity recognition.  _Int. J. Comput. Sci. Netw. Secur_ 17, 4 (2017), 160–165.
  * Balaji et al. (2018) Yogesh Balaji, Swami Sankaranarayanan, and Rama Chellappa. 2018\.  Metareg: Towards domain generalization using meta-regularization. In _NeurIPS_. 998–1008.
  * Borgwardt et al. (2006) Karsten M Borgwardt, Arthur Gretton, Malte J Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex J Smola. 2006\.  Integrating structured biological data by kernel maximum mean discrepancy.  _Bioinformatics_ 22, 14 (2006), e49–e57.
  * Chen and Moschitti (2019) Lingzhen Chen and Alessandro Moschitti. 2019.  Transfer learning for sequence labeling using source model and target data. In _AAAI_ , Vol. 33. 6260–6267.
  * Choi et al. (2016) Edward Choi, Mohammad Taha Bahadori, Jimeng Sun, Joshua Kulas, Andy Schuetz, and Walter Stewart. 2016\.  Retain: An interpretable predictive model for healthcare using reverse time attention mechanism. In _NeurIPS_. 3504–3512.
  * Chung et al. (2004) Fu-Lai Chung, Tak-Chung Fu, Vincent Ng, and Robert WP Luk. 2004\.  An evolutionary approach to pattern-based time series segmentation.  _IEEE transactions on evolutionary computation_ 8, 5 (2004), 471–489.
  * Chung et al. (2014) Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. 2014.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  _arXiv preprint arXiv:1412.3555_ (2014).
  * Cui et al. (2019) Wanyun Cui, Guangyu Zheng, Zhiqiang Shen, S. Jiang, and Wei Wang. 2019.  Transfer Learning for Sequences via Learning to Collocate. In _ICLR_.
  * de Bézenac et al. (2020) Emmanuel de Bézenac, Syama Sundar Rangapuram, Konstantinos Benidis, Michael Bohlke-Schneider, Richard Kurle, Lorenzo Stella, Hilaf Hasson, Patrick Gallinari, and Tim Januschowski. 2020.  Normalizing Kalman Filters for Multivariate Time Series Analysis.  _NeurIPS_ 33 (2020).
  * Facebook (2021) Facebook. Accessed in Jan 2021\.  FBProphet.  https://facebook.github.io/prophet/.
  * Fawaz et al. (2018) Hassan Ismail Fawaz, G. Forestier, Jonathan Weber, L. Idoumghar, and Pierre-Alain Muller. 2018\.  Transfer learning for time series classification.  _Big Data_ (2018), 1367–1376.
  * Ganin et al. (2016) Yaroslav Ganin, E. Ustinova, Hana Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky. 2016\.  Domain-Adversarial Training of Neural Networks.  _JMLR_ 17 (2016), 59:1–59:35.
  * Górecki and Luczak (2015) Tomasz Górecki and Maciej Luczak. 2015.  Multivariate time series classification with parametric derivative dynamic time warping.  _Expert Syst. Appl._ 42 (2015), 2305–2312.
  * Gretton et al. (2012) A. Gretton, Bharath K. Sriperumbudur, D. Sejdinovic, Heiko Strathmann, S. Balakrishnan, M. Pontil, and K. Fukumizu. 2012.  Optimal kernel choice for large-scale two-sample tests. In _NeurIPS_.
  * Gupta et al. (2018) Priyanka Gupta, P. Malhotra, L. Vig, and G. Shroff. 2018\.  Transfer Learning for Clinical Time Series Analysis using Recurrent Neural Networks. In _ML for Medicine and Healthcare Workshop at KDD_.
  * Hallac et al. (2017) David Hallac, Sagar Vare, Stephen Boyd, and Jure Leskovec. 2017\.  Toeplitz inverse covariance-based clustering of multivariate time series data. In _SIGKDD_. 215–223.
  * Jaynes (1982) Edwin T Jaynes. 1982\.  On the rationale of maximum-entropy methods.  _Proc. IEEE_ 70, 9 (1982), 939–952.
  * Kaggle (2021) Kaggle. Accessed in Jan 2021\.  Household electric power consumption dataset.  https://www.kaggle.com/uciml/electric-power-consumption-data-set.
  * Kalpakis et al. (2001) Konstantinos Kalpakis, Dhiral Gada, and Vasundhara Puttagunta. 2001.  Distance measures for effective clustering of ARIMA time-series. In _ICDM_. IEEE, 273–280.
  * Keogh and Ratanamahatana (2005) Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005\.  Exact indexing of dynamic time warping.  _Knowl. Inf. Syst._ 7, 3 (2005), 358–386.
  * Kohara et al. (1997) Kazuhiro Kohara, Tsutomu Ishikawa, Yoshimi Fukuhara, and Yukihiro Nakamura. 1997.  Stock price prediction using prior knowledge and neural networks.  _Intell. Syst. Account. Finance Manag._ 6, 1 (1997), 11–22.
  * Kuznetsov and Mohri (2014) Vitaly Kuznetsov and Mehryar Mohri. 2014.  Generalization bounds for time series prediction with non-stationary processes. In _ALT_. Springer, 260–274.
  * Lai et al. (2018) Guokun Lai, Wei-Cheng Chang, Yiming Yang, and Hanxiao Liu. 2018\.  Modeling long-and short-term temporal patterns with deep neural networks. In _SIGIR_. 95–104.
  * Le Guen and Thome (2020) Vincent Le Guen and Nicolas Thome. 2020.  Probabilistic Time Series Forecasting with Structured Shape and Temporal Diversity.  In _Advances in Neural Information Processing Systems_.
  * Lei et al. (2019) Qi Lei, Jinfeng Yi, Roman Vaculín, Lingfei Wu, and Inderjit S. Dhillon. 2019.  Similarity Preserving Representation Learning for Time Series Clustering. In _IJCAI_.
  * Li et al. (2018) Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C Kot. 2018.  Domain generalization with adversarial feature learning. In _CVPR_. 5400–5409.
  * Lines and Bagnall (2014) J. Lines and Anthony J. Bagnall. 2014.  Time series classification with ensembles of elastic distance measures.  _Data Min. Knowl. Discov._ 29 (2014), 565–592.
  * Liu et al. (2008) Xiaoyan Liu, Zhenjiang Lin, and Huaiqing Wang. 2008\.  Novel online methods for time series segmentation.  _IEEE TKDE_ 20, 12 (2008), 1616–1626.
  * Matsubara et al. (2014) Yasuko Matsubara, Yasushi Sakurai, Willem G Van Panhuis, and Christos Faloutsos. 2014.  FUNNEL: automatic mining of spatially coevolving epidemics. In _KDD_. 105–114.
  * Muandet et al. (2013) Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. 2013\.  Domain generalization via invariant feature representation. In _ICML_. 10–18.
  * Oreshkin et al. (2021) Boris N Oreshkin, Dmitri Carpov, Nicolas Chapados, and Yoshua Bengio. 2021.  Meta-learning framework with applications to zero-shot time-series forecasting. In _AAAI_.
  * Orsenigo and Vercellis (2010) C. Orsenigo and C. Vercellis. 2010.  Combining discrete SVM and fixed cardinality warping distances for multivariate time series classification.  _Pattern Recognit._ 43 (2010), 3787–3794.
  * Qin et al. (2017) Yao Qin, Dongjin Song, Haifeng Chen, Wei Cheng, Guofei Jiang, and Garrison Cottrell. 2017\.  A dual-stage attention-based recurrent neural network for time series prediction. In _AAAI_.
  * Ristanoski et al. (2013) Goce Ristanoski, Wei Liu, and James Bailey. 2013.  Time series forecasting using distribution enhanced linear regression. In _PAKDD_. 484–495.
  * Robinson et al. (2010) Joshua W Robinson, Alexander J Hartemink, and Zoubin Ghahramani. 2010.  Learning Non-Stationary Dynamic Bayesian Networks.  _Journal of Machine Learning Research_ 11, 12 (2010).
  * Ross (2014) Sheldon M Ross. 2014\.  _Introduction to stochastic dynamic programming_.  Academic press.
  * Salinas et al. (2020) David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. 2020.  DeepAR: Probabilistic forecasting with autoregressive recurrent networks.  _Int. J. Forecast_ 36, 3 (2020), 1181–1191.
  * Schäfer (2015) P. Schäfer. 2015\.  Scalable time series classification.  _Data Min. Knowl. Discov._ 30 (2015), 1273–1298.
  * Schapire (2003) Robert E Schapire. 2003\.  The boosting approach to machine learning: An overview.  _Nonlinear estimation and classification_ (2003), 149–171.
  * Sen et al. (2019) Rajat Sen, Hsiang-Fu Yu, and Inderjit S Dhillon. 2019.  Think globally, act locally: A deep neural network approach to high-dimensional time series forecasting. In _NeurIPS_. 4837–4846.
  * Shimodaira (2000) Hidetoshi Shimodaira. 2000\.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of statistical planning and inference_ 90, 2 (2000), 227–244.
  * Sun and Saenko (2016) Baochen Sun and Kate Saenko. 2016.  Deep CORAL: Correlation Alignment for Deep Domain Adaptation. In _ECCV_.
  * Tuncel and Baydogan (2018) Kerem Sinan Tuncel and Mustafa Gokce Baydogan. 2018.  Autoregressive forests for multivariate time series modeling.  _Pattern recognition_ 73 (2018), 202–215.
  * Tzeng et al. (2017) E. Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. 2017\.  Adversarial Discriminative Domain Adaptation. In _CVPR_. 2962–2971.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _Advances in neural information processing systems_. 5998–6008.
  * Vincent and Thome (2019) LE Vincent and Nicolas Thome. 2019.  Shape and Time Distortion Loss for Training Deep Time Series Forecasting Models. In _NeurIPS_. 4189–4201.
  * Wang et al. (2020) Jindong Wang, Yiqiang Chen, Wenjie Feng, Han Yu, Meiyu Huang, and Qiang Yang. 2020\.  Transfer learning with dynamic distribution adaptation.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 11, 1 (2020), 1–25.
  * Wang et al. (2018) Jindong Wang, Wenjie Feng, Yiqiang Chen, Han Yu, Meiyu Huang, and Philip S Yu. 2018\.  Visual domain adaptation with manifold embedded distribution alignment. In _Proceedings of the 26th ACM international conference on Multimedia_. 402–410.
  * Wang et al. (2021) Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Wenjun Zeng, and Tao Qin. 2021\.  Generalizing to Unseen Domains: A Survey on Domain Generalization. In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Wang and Oates (2015) Zhiguang Wang and Tim Oates. 2015.  Imaging Time-Series to Improve Classification and Imputation. In _IJCAI_.
  * Yang et al. (2017) Z. Yang, R. Salakhutdinov, and William W. Cohen. 2017\.  Transfer Learning for Sequence Tagging with Hierarchical Recurrent Networks. In _ICLR_.
  * Yu et al. (2019) Chaohui Yu, Jindong Wang, Yiqiang Chen, and Meiyu Huang. 2019\.  Transfer learning with dynamic adversarial adaptation network. In _2019 IEEE International Conference on Data Mining (ICDM)_. IEEE, 778–786.
  * Zhang (2003) G Peter Zhang. 2003\.  Time series forecasting using a hybrid ARIMA and neural network model.  _Neurocomputing_ 50 (2003), 159–175.
  * Zhang et al. (2017) Shuyi Zhang, Bin Guo, Anlan Dong, Jing He, Ziping Xu, and Song Xi Chen. 2017\.  Cautionary tales on air-quality improvement in Beijing.  _Proc. Math. Phys. Eng. Sci._ 473, 2205 (2017), 20170457\.
  * Zhu and Shasha (2002) Yunyue Zhu and Dennis Shasha. 2002.  Statstream: Statistical monitoring of thousands of data streams in real time. In _VLDB_. Elsevier, 358–369.
  * Zhu et al. (2020) Yongchun Zhu, Fuzhen Zhuang, Jindong Wang, Guolin Ke, Jingwu Chen, Jiang Bian, Hui Xiong, and Qing He. 2020\.  Deep subdomain adaptation network for image classification.  _IEEE transactions on neural networks and learning systems_ 32, 4 (2020), 1713–1722.


We need to prove that there is $\bar{\tau}<\tau$ such that for every $\tau'\in D-\bar{\tau}$, $(\mu_\tau,q^*_{\bar{\tau}}) = (\mu_{\tau'},q_{\tau'})$. Assume for contradiction that there is a sequence $\langle \tau_i \ | \ i<\delta\rangle$ that is increasing, cofinal in $\tau$ such that $(\mu_{\tau_i},q_{\tau_i}) \neq (\mu_\tau,q^*_{\tau_i})$. We may assume without loss of generality that the sequence $\langle \mu_{\tau_i} \ | \ i<\delta\rangle$ is monotonic and all $q_{\tau_i}$'s have the same length, say $m$.

By the definition of $(\mu_{\tau_i},q_{\tau_i})$, each $q_{\tau_i}$ is a bottom part of $q^*_{\tau_i}$, say $q^*_{\tau_i}= q_{\tau_i}\cup s_{\tau_i}$ ($s_{\tau_i}$ may be empty). Set for some (equivalently for all sufficiently large) $i<\delta$, $q = \sigma_{\tau_i\tau}(q_{\tau_i})$, $s = \sigma_{\tau_i\tau}(s_{\tau_i})$, $r = r_\tau$, $\nu = \rm{sup}$$_{i<\delta} \mu_{\tau_i}$. Now $(\nu,q)$ is a divisor of $\N_\tau$ (see <cit.>). Since $\nu > \mu_\tau$ and $q$ is a bottom segment of $q_\tau$, $(\nu,q)$ cannot be a strong divisor of $\N_\tau$. Then a calculation as in <cit.> and similar to that of the proof of Lemma <ref> shows that for some $\iota<\delta$, $(\mu_{\tau_\iota},q_{\tau_\iota})$ is not a strong divisor of $\N_{\tau_\iota}$ (by showing that $p(\N'_{\tau_\iota})$ is a proper lengthening of $r'_{\tau_\iota}$). Contradiction.

Lemmata <ref>, <ref>, <ref> together complete the proof of Lemma <ref> in the case $\tau\in \S^1$.

§ PROOF OF THEOREM <REF>

The constructions done in the previous sections prove the $(4)\Rightarrow (1)$ direction of the theorem. The $(1)\Rightarrow (2)$ direction is trivial.  The $(2)\Rightarrow (3)$ direction follows verbatim from the proof of <cit.>. We now prove the remaining implication, whose proof is closely based on that of <cit.>.

Proof of $(3) \Rightarrow (4)$. Again, fix $(\P,\Sigma), \kappa$ as in the statement of Theorem <ref> and as before, we assume $\Sigma$ is coded by a Suslin co-Suslin set. We work in $\P$ for the rest of the argument. Assume the set

$A=\{\nu <\kappa^+ : E^\P_\nu \neq \emptyset\}$

is stationary in $\kappa^+$. We show that $\kappa$ is subcompact in $\P$.

Let $\tau=\kappa^+$, $\R = \P|\tau^+$, and $B$ be the least $<_\P$-set that witnesses the failure of subcompactness of $\kappa$. By a simple closure argument and the fact that $A$ is stationary, let $\nu < \tau$ be such that

\begin{equation}\label{eqn:01}
\nu\cap h^\omega_\R(\nu\cup \{\tau\}) = \nu \wedge E_\nu \neq \emptyset.
\end{equation}

Let $\tilde{\R}$ be the transitive collapse of $h^\omega_\R(\nu\cup \{\tau\})$ and $\sigma$ be the uncollapse map. We have:

* $\tilde{\R}$ is sound.

* $\kappa < \omega\rho^{\tilde{\R}}_\omega = \nu=(\kappa^+)^{\tilde{\R}} = \rm{crt}(\sigma)$.

* $\sigma$ is fully elementary.

Applying Theorem <ref> to $\sigma$, by <ref>, we easily see that clause $(b)$ must hold; that is $\tilde{\R}$ is a proper initial segment of Ult$(\R|\nu, E^\R_\nu)=\S'$. In fact, $\tilde{\R}$ is a proper initial segment of $\S = \S'|(\nu^+)^{\S'}$. We note that $\nu = (\kappa^+)^\S$.

We proceed to obtain a contradiction. First note that the failure of subcompactness of $\kappa$ can be expressed as a $\Sigma_1$-statement $\varphi(B, \tau)$ over $\R$. Since $\sigma$ is $\Sigma_1$ and $B$ is $<_\R$-minimal, we easily get that $B\in \rm{rng}(\sigma)$ and letting $B'=\sigma^{-1}(B)$, then $B'$ is the $<_{\tilde{\R}}$-least witness of failure of subcompactness of $\kappa$ in $\tilde{\R}$. So $B'$ is the $<_\S$-least such that $\varphi(B,\nu)$ holds in $\S$. So $B'$ is definable in $\S$ from $\nu$. Let $\pi$ be the $E^\R_\nu$ ultrapower map $\pi: \R|\xi\rightarrow \S$ (here $\xi$ is the $\R$-successor of the critical point of $E_\nu^\R$). Then $B'$ is in the range of $\pi$ (since the Jensen indexing scheme guarantees that $\nu$ is in the range of $\pi$), so let $\bar{B}=\pi^{-1}(B')$. We get then that $\sigma \circ \pi$ induces a map

$\psi: (H_\xi^\P,\bar{B})\rightarrow (H_\tau^\P,B)$.

This contradicts the assumption that $A$ witnesses the failure of subcompactness of $\kappa$.

§ STACKS OF LBR HOD MICE AND THREADABILITY

In this section, we adapt Jensen's definition of stacks (cf. <cit.>) to the context of lpm's and prove that the canonical $\square$-sequence built in a stack over some appropriately chosen lpm is not threadable. We work in $\sf{ZFC}$ throughout this section.

Let $\P$ be an lpm. We say that $\P$ is an lm if the following holds. For $n<\omega$, if

$\pi: \M\rightarrow \mathfrak{C}_n(\P)$

is $\Sigma^{(n)}_0$, $\M$ is countable, and $\mathfrak{C}_n(\P)$ is the $n$-th core of $\P$, then there is an $(n,\omega_1,\omega_1+1)$-strategy $\Sigma$ for $\M$ such that $(\M,\Sigma)$ is an lbr hod pair.

Suppose that there are no lpm's with a superstrong. Suppose $\P$ is an lm such that $o(\P)=\kappa$ is a regular, uncountable cardinal. Suppose $\M_0$ and $\M_1$ are sound lm's such that

* for $h\in\{0,1\}$, $\P\unlhd \M_h$ and $\rho_\omega(\M_h)=\kappa$;

* there is a transitive $M$ such that $\mathbb{R}\cup\rm{OR}\subseteq$$M$, $M\vDash \sf{AD}^+$ such that  whenever $h\in\{0,1\}$, $\pi: \N\rightarrow \M_h$ is elementary, there is a $\Sigma$ witnessing that $(\N,\Sigma)$ is an an lbr hod pair then $\Sigma\restriction\rm{HC}$ is coded by a Suslin co-Suslin in $M$.

Then either $\M_0\unlhd \M_1$ or $\M_1\unlhd \M_0$.

We remark that it is easy to see that the condensation lemma <ref> holds for lm's like $\M_0, \M_1$ (where these objects play the role of $\P$ in the statement of the lemma). We will say that $\M_0, \M_1$ are $M$-iterable.

Let $\theta$ be a regular cardinal much bigger than $\kappa$. Let $\pi: H\rightarrow H_\theta$ be (fully) elementary, range of $\pi$ contains everything relevant, and $H$ is countable. Let $(\bar{\kappa},\bar{\M_0},\bar{\M_1}) = \pi^{-1}(\kappa,\M_0,\M_1)$. So $\bar{\M_0}$ and $\bar{\M_1}$ are sound and project to $\bar{\kappa}$. Also, there are $\Sigma_0,\Sigma_1$ coded by Suslin co-Suslin sets in $M$ such that $(\bar{\M_0},\Sigma_0)$ and $(\bar{\M_1},\Sigma_1)$ are lbr hod pairs.

Now we apply Theorem <ref> to $\pi\restriction \bar{\M_0}$ and to $\pi\restriction\bar{\M_1}$. We easily rule out case (b) because $\bar{\M_0}$ and $\bar{\M_1}$ are sound. Case (c) is ruled out because of our smallness assumption. (d) is ruled out because $\bar{\kappa} < \kappa$. We get that case (a) of the theorem must hold. So $\bar{\M_0}\lhd \P$ and $\bar{\M_1}\lhd \P$. By elementarity, we get that either $\M_0\unlhd \M_1$ or $\M_1\unlhd \M_0$.

[Stacking mice]
Let $\P$ be an lm such that $o(\P) = \kappa$ is a regular, uncountable cardinal. Let $M$ be a transitive $\sf{AD}^+$ model containing $\mathbb{R}\cup\rm{OR}$. Let $\mathcal{S}_M$ be the unique lpm $\S$ such that $\M\unlhd \S$ if and only if there is some sound, $M$-iterable lm $\N\unlhd \S$ such that $\rho_\omega(\N)=\kappa$.

The proof of <cit.> gives the following (here, we use Theorem <ref> in the proof).

Let $\P, M, \S_M$ be defined as in Definition <ref>. Suppose that there are no lpm's with a superstrong. Suppose $\P\lhd \S_M$.[$\S_M$ may be equal to $\P$ in general (e.g. when $\powerset(\mathbb{R})\cap M$ is too simple).] Then for all $\M\unlhd \S_M$ with $\rho_\omega(\M)=\kappa$, there is some $\N\lhd \S$ with $\M\lhd \N$. In particular, $\S_M\vDash \sf{ZFC}^-$, $\kappa$ is the largest cardinal of $\S_M$, and $\S_M$ is an $M$-iterable lm.

Let $\P, M, \S_M$ be defined as in Definition <ref>. Suppose that there are no lpm's with a superstrong. Suppose $\P\lhd \S_M$. Let $\lambda =  o(\S_M)$. Suppose cof$(\lambda) > \omega$. Let $\vec{C} = \{C_\alpha : \alpha < \lambda\}$ be the $\square_\kappa$-sequence built over $\S_M$ (in the sense of the earlier sections). Then $\vec{C}$ is unthreadable.

Since $\S_M \vDash \sf{ZFC}^-$ (by Lemma <ref>), $\lambda$ is a limit ordinal. Since $\S_M\neq \P$, $\lambda > \kappa$. Let $D\subseteq \lambda$ be a thread through $\vec{C}$. By the construction of $\vec{C}$, the thread $D$ can be associated with the sequence $(\M_\alpha : \alpha\in lim(D))$ such that

* $\M_\alpha \unlhd \S_M$ is a sound, $M$-iterable lm such that $\rho_\omega(\M)=\kappa$;

* $\M_\alpha \vDash \alpha = \kappa^+$ but $L_1[\M_\alpha]\vDash |\alpha| = \kappa$;

* the direct limit $\M_\infty$ of the $\M_\alpha$'s (under the embeddings that occur in the construction of $\vec{C}$) exists. So $o(\M_\infty)\geq \lambda$, $\M_\infty$ is sound and $\rho_\omega(\M_\infty) = \kappa$.

Now, use the fact that cof$(\lambda)>\omega$, we easily get that

$\M_\infty$ is $M$-iterable.

This is because whenever $\pi:\M^*\rightarrow \M_\infty$ is elementary and $\M^*$ is countable, there is some $\alpha<\lambda$ and $\pi':\M^*\rightarrow \M_\alpha$. So $(\M^*,\Lambda)$ is an lbr hod pair for some $\Lambda$ coded by a Suslin co-Suslin set in $M$.

This means $\M_\infty\unlhd \S_M$. Contradiction.

We expect that Lemma <ref> can be used in various applications. For instance, in the core model induction applications, we can typically let $M$ be the “maximal model of $\sf{AD}^+$" and $\P$ be the result of some “hybrid $K^c$-construction" extending the direct limit of lbr hod pairs in $M$ (cf. [3]).

[1]
William J. Mitchell and John R. Steel.
Fine structure and iteration trees, volume 3 of Lecture
Notes in Logic.
Springer-Verlag, Berlin, 1994.

[2]
G. Sargsyan.
Hod Mice and the Mouse Set Conjecture, volume 236 of Memoirs of the American Mathematical Society.
American Mathematical Society, 2015.

[3]
Grigor Sargsyan and Nam Trang.
The largest Suslin axiom.
Submitted. Available at math.rutgers.edu/$\sim$gs481/lsa.pdf.

[4]
Ernest Schimmerling and John R. Steel.
Fine structure for tame inner models.
Journal of Symbolic Logic, 61(01):621–639, 1996.

[5]
Ernest Schimmerling and Martin Zeman.
Characterization of $\square_\kappa$ in core models.
Journal of Mathematical Logic, 4(01):1–72, 2004.

[6]
Ralf Schindler and Martin Zeman.
Fine structure.
In Handbook of set theory, pages 605–656. Springer, 2010.

[7]
Ralf-Dieter Schindler, John Steel, and Martin Zeman.
Deconstructing inner model theory.
The Journal of Symbolic Logic, 67(2):721–736, 2002.

[8]
F. Schlutzenberg and N. Trang.
Scales in hybrid mice over $\mathbb{R}$.
Submitted. Available at math.unt.edu/$\sim$ntrang.

[9]
Benjamin Siskind and John R. Steel.
Full normalization for mouse pairs.
arXiv preprint arXiv:2207.11065, 2022.

[10]
John R Steel.
Local hod computation.
Handwritten notes, available at

[11]
John R Steel.
$\mbox{HOD}^{L (\mathbb{R})}$ is a core model below $\theta$.
Bulletin of Symbolic Logic, 1(1):75–84, 1995.

[12]
John R. Steel.
Ordinal definability in models of determinacy.
In Alexander S. Kechris, Benedikt Löwe, and John
R. Steel, editors, Ordinal Definability and Recursion
Theory: The Cabal Seminar, Volume III. Cambridge University
Press, 2016.
Cambridge Books Online.

[13]
John R Steel.
A comparison process for mouse pairs, volume 51 of Lecture
Notes in Logic.
Cambridge University Press, 2022.

[14]
John R. Steel and W. Hugh Woodin.
HOD as a core model.
In Alexander S. Kechris, Benedikt Löwe, and John
R. Steel, editors, Ordinal Definability and Recursion
Theory: The Cabal Seminar, Volume III, pages 257–346.
Cambridge University Press, 2016.
Cambridge Books Online.

[15]
Nam Trang.
Hod in natural models of $\sf{AD}^+$.
Annals of Pure and Applied Logic, 165(10):1533–1556, 2014.

[16]
Martin Zeman.
Inner models and large cardinals, volume 5 of de Gruyter
Series in Logic and its Applications.
Walter de Gruyter & Co., Berlin, 2002.

From the beginning of the main condensation lemma proof:

Claim 0.  Suppose $\la (N,\Phi), (G,\Lambda), \sigma, \nu \ra$ is a tuple
satisfying (1)–(3) of Definition <ref>. Suppose $G$ is of
type 2. Let $k = \textrm{deg}(G)$, $D$ be the measure of Mitchell order 0 on
$\hat{\rho}^k(G)$ such that $G = \textrm{Ult}(C(G),D)$, and let $i_D$ be the
ultrapower map. Suppose $C(G)\lhd N$ and $\Phi_{C(G)} = \Phi^{\sigma\circ i_D}$.
$$(\Phi_{C(G)})_{\langle D,G\rangle} = \Lambda.$$

Proof. Consider the diagram in Figure <ref>, where we
let $H$ be Ult$(G,i_D(D))$ and $j$ be the corresponding ultrapower map, and $Y$
be the image of $H$ under the copy construction. We let $k:N\rightarrow Y$ be the ultrapower map by $\sigma(i_D(D))$.

Let $\Sigma = \Phi_{\langle k, Y \rangle}$. We have

\begin{align*}
(\Phi_{C(G)})_{\langle D,G \rangle} & = (\Sigma)^{\sigma\circ j} \\
& = \Sigma^{k\circ \sigma}\\
& = \Lambda \\
\end{align*}

The first equality follows from the definition of pullback strategies on stacks.
The second equality follows from commutativity, i.e. $\sigma\circ j = k\circ \sigma$.
The third equality follows from our assumption that $\Lambda = \Phi^\sigma$ and the definition of $\Sigma$.

$\hfill \square$

[node distance=3cm, auto]
(A) $C(G)$;
(B) [right of=A] $G$;
[->] (A) to node $i_D$ (B);
(C) [above of=A, node distance=1.5cm] $G$;
[->] (A) to node $i_D$(C);

(D) [right of=C]$H$;
[->] (C) to node $j$ (D);
[->] (B) to node $j$(D);

(E) [above of=C, node distance=1.5cm] $N$;
(F) [right of=E]$Y$;
[->] (E) to node $k$ (F);
[->] (D) to node $\sigma$ (F);
[->] (C) to node $\sigma$ (E);

Diagram illustrating that $(\Lambda_\xi)_{\langle E_\alpha,G \rangle} = \Lambda_\xi^\sigma$.