Detecting and Adapting to Irregular Distribution Shifts in Bayesian Online Learning
Authors: Aodong Li
Alex James Boyd
Padhraic Smyth
Stephan Mandt
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian online learning
change detection
non-stationary continual learning

Abstract: We consider the problem of online learning in the presence of distribution shifts that occur at an unknown rate and of unknown intensity. We derive a new Bayesian online inference approach to simultaneously infer these distribution shifts and adapt the model to the detected changes by integrating ideas from change point detection, switching dynamical systems, and Bayesian online learning. Using a binary ‘change variable,’ we construct an informative prior such that--if a change is detected--the model partially erases the information of past model updates by tempering to facilitate adaptation to the new data distribution. Furthermore, the approach uses beam search to track multiple change-point hypotheses and selects the most probable one in hindsight. Our proposed method is model-agnostic, applicable in both supervised and unsupervised learning settings, suitable for an environment of concept drifts or covariate drifts, and yields improvements over state-of-the-art Bayesian online learning approaches.

Detecting and Adapting to Irregular Distribution Shifts in Bayesian Online Learning
Aodong Li' Alex Boyd² Padhraic Smyth Stephan Mandt
'Department of Computer Science DDeparteent of Statistics
University of California, Irvine
faodongl1, alexjb, mandt handt)@uci..cm smyth@ics edu
Abstract
We consider the problem of online learning in the presence of distribution shifts that occur at an unknown rate and of unknown intensity. We derive a new Bayesian online inference approach to simultaneously infer these distribution shifts and adapt the model to the detected changes by integrating ideas from change point detection, switching dynamical systems, and Bayesian online learning. Using a binary "change variable," we construct an informative prior such that-if a change is detected-the model partially erases the information of past model updates by tempering to facilitate adaptation to the new data distribution. Furthermore, the approach uses beam search to track multiple change-poine hypotheses and selects the most probable one in hindsight. Our proposed method is model-agnostic, applicable both supervised and unsupervised learning settings, suitable for an environment of concept drifts covariate drifts, and yields improvements over state-of-te state-of-the-are art Bayesian online learning approaches.
Introduction
Deployed machine learning systems are often faced with the problem of distribution shift, where the new data that the model processes is systematically different from the data the system was trained on (Zech al. 2018 Ovadia et al. 2019). Furthermore, shift can happen anytime after deployment, unbeknownst to the users, with dramatic consequences for systems such as self-driving cars, robots, and financial trading algorithms, among many other examples.
Updating a deployed model on new, representative data can help mitigate these issues and improve general performance in cases. This task is commonly referred learning. Such online learning algorithms face a tradeoff between remembering and adapting. If they adapt too fast, their performance will suffer since adaptation usually implies that the model loses memory of previously encountered training data (which may still be relevant to future predictions). On the other hand, if a model remembers too much, typically has problems adapting new data distributions due to its finite capacity.
online incremental
The tradeoff between adapting and remembering can be elegantly formalized in Bayesian online learning framework, where a prior distribution is used to keep track of previously learned parameter estimates and their confidences. For instance, variational continual learning (VCL) (Nguyen et al.) 2018 is a popular framework that uses a model's previous posterior distribution as the prior for new data. However, the assumption of such continual learning setups is usually that the data distribution is stationary and not subject to change, in which case adaptation is not an issue.
This paper proposes
Bayesian online learning framework suitable for non-stationary data distributions. It is based on two assumptions: (i) distribution shifts occur irregularly and must be inferred from the data, and (ii) the model requires not only good mechanism to aggregate data but
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

also the ability to partially forget information that has become obsolete. To solve both problems, we still use Bayesian framework for online learning (i.e., letting previous posterior distribution inform the next prior); however, before combining the previously learned posterior with new data evidence, we introduce an intermediate step. This step allows the model to either broaden the previous posterior's s variance to reduce the model's confidence, thus providing more "room" for new information, or remain in the same state (i.c., retain the unchanged, last posterior as the new prior).
We propose a mechanism for enabling this decision by introducing a discrete "change variable" that indicates the model's best estimate of whether the data in the new batch is compatible with the previous data distribution or not; the outcome then informs the Bayesian prior at the next time step. We further augment the scheme by performing beam search on the change variable. This way, we are integrating change detection and Bayesian online learning into common framework.
We test our framework on variety of real-world datasets that show concept drift, including baskethall player trajectories, malware characteristics, sensor data, and electricity prices. We also study sequential versions of SVHN and CIFAR-I0 with covariate drift, where we simulate the shifts in terms of image rotations. Finally, we study word embedding dynamics in an unsupervised learning approach. Our approach leads to a more compact and interpretable latent structure and significantly improved performance in the supervised experiments. Furthermore, it is highly scalable; we demonstrate it on models with hundreds of thousands of parameters and tens of thousands of feature dimensions.
Our paper is structured as follows: we review related work in Section 2 introduce our methods in report our experiments in Section and draw conclusions in Section
Section 3
2
Related Work
Our paper connects to Bayesian online learning, change detection, and switching dynamical systems.
Bayesian Online and Continual Learning There is a rich existing literature on Bayesian and continual learning. The main challenge in streaming setups is to reduce the impact of old data on the model which can be done by exponentially decaying old samples (Honkela and Valpolal 2003] Sato, 2001] Grappel et al., [010] or re- re-weighting them [McInerney et 2015 Theis and Hoffman 2015). An alternative approach is to adapt the model posterior between time steps, such as tempering it at a constant rate to accommodate new information [Kulhavý and Zarrop 1993, Kurle et al. 2020] In contrast, continual learning typically assumes a stationary data distribution and simply uses the old posterior as the new prior. A scalable such scheme based on variational inference was proposed
by Nguyen et al. 2018) which was extended by several authors [Farquhar and Gal 2018 Schwarz ct al. 2018 A related concept is clastic weight consolidation (Kirkpatrick et al. 2017]. where new model parameters are regularized towards old parameter values.
All of these approaches need to make assumptions on the expected frequency and strengh of change which are hard-coded in the model parameters (e.g., exponential decay rates, re-whigtting terms, prior strengths, or temperature choices). Our approach, in contrast, detects change based on a discrete variable and makes no assumption about its frequency. Other approaches assume situations where data arrive in irregular time intervals, but are still concerned with static data distributions (Titsias)
ct al. 2019 Lee et al. 2020 Rao et al. 2019].
Change Point Models There is also a rich history of models for change detection. A popular class of change point models includes "product partition models" [Barry and Hartigan| [992] which assume independence of the data distribution across segments. In this regime, Fearnhead [2005] proposed change detection in the context of regression and generalized it to online inference [Feanhhead and Liu 2007]; ; Adams and MacKay | described a Bayesian online change point detection scheme (BOCD) based on conditional conjugacy assumptions for dieeennnnio sequences. Other work generalized change detection algorithms multivariate time series [Xuan and Murphy| 2007 Xie
et al. 2012] and non non-conjugate Bayesian inference (Saatçi et al. 2010 Knoblauch and Damoulas
2018 Turner et al. 2013 Knoblauch et al. 22118).
Our approach relies on jointly inferring changes in the data distribution while carrying out Bayesian parameter updates for adaptation. To this end, we detect change in the high- nigh-dimensional space of

---

model (e.g., neural network) parameters, as opposed to directly in the data space. Furthermore, detected change only partially resets the model parameters, as opposed to triggering complete reset.
Titsias et al. [2020) proposed change detection to detect distribution shifts in sequences based on low-dimensional summary statistics such loss function; however, the proposed framework does not use an informative prior but requires complete retraining.
Switching Linear Dynamical Systems Since our approach integrates a discrete change variable, it is also loosely connected to the topic of switching linear dynamical systems. [inderman et al. 2017 considered recurrent switching linear dynamical systems, relying on Bayesian conjugacy and closed-form message passing updates. BBecker-Ehmck et al. (2019) proposed a variational Bayes
filtering framework for switching linear dynamical systems. Murphy [2012] and [Barber] [2012] developed an inference method using a Gaussian sum filter. Instead, we focus on inferring the full history of discrete latent variable values instead of just the most recent one.
Bracegirdle and Barber [201T] introduce resef variable that sets the continuous latent variable to an unconditional prior. It is similar to our work, but relies using low-dimensional, tractable models. Our tempering prior can be seen as a partial reset, augmented with beam search. We also extend the scope of switching dynamical systems by integrating them into supervised learning framework.
3 Methods
Section 3.1 introduces the setup and the novel model structure under consideration. introduces an exact inference scheme based on beam search. Finally, we introduce the variational inferncee extension for intractable likelihood models in Section 3.3
Overview
Section 3.2
3.1 Problem Assumptions and Structure
We consider a stream of data that arrives in batches x; at discrete times For supervised setups, we consider pairs of features and targets (x,, Yr), where the task is to model pxy, An example model could be a Bayesian neural network, and the parameters z could be the network weights. For notational simplicity
focus the unsupervised case, where the task is to model p(xx) using model p(x, 2 with parameters 2, that we would like to tune to each new batch! We then measure the prediction error either on one-step-ahead samples or using held-out test set.
Furthermore, we assume that while the x, are i.i.d. within batches, they are not necessarily i.i.d. across batches as they come from time-varying distribution (x,) (or Pe(x,, yr) in the supervised cases) which is subject to distribution shifts. We do not assume whether these distribution shifts occur instantaneously gradually. The challenge is to optimally adapt the parameters to each new batch while borrowing statistical strength from previous batches.
As follows, we will construct a Bayesian online learning scheme that accounts for changes in the data distribution. For every new batch of data, our scheme tests whether the new batch is compatible with the old data distribution, or more plausible under the assumption of a change. To this end, we employ a binary "change variable" 8t, with 8, = for no detected change and 8; = 1 for a detected change. Our model's joint distribution factorizes as follows:
p(XI.T, ZieT S1:)) II
(1)
We assumed a factorized Bernoulli prior Ile p(s)) over the change variable: an assumption that will simplify the inference, but which can be relaxed. As a result, our model is fully-factorized over time, however, the model can still capture temporal dependencies through the informative prior p(ze|se: T)). Temporal information enters this prior through certain sufficient statistics т, that depend on properties of the previous time-step's ' approximate posterior.
In more detail, Т: is a functional on the previous time step's approximate posterior, Te 814-1] Throughout this paper, will use specific form of TG, namely
In extreme case, it is possible for batch to include only single data point. In supervised setups, we consider a conditional model p(y, mn xx) with features x; and targets yt- P Subscripts 1 1:t- indicates the integers from 1 to t inclusively.
3

---

b1) Posterior at t-]
x2) Price
a3) Posterior at
b1) Variational Groedy Search (VGS)
b2) Variational Beam Starch (VBS)
Ate-t Ror-t)
Mlal m0 Mabi m.
Figure I: a) A single inference step for the latent mean in a ID linear Gaussian model. Starting from the previous posterior (al), we consider both its broadened and un-broadened version (a2). Then the model absorbs the observation and updates the priors (a3), b) Sparse inference via greedy search (b1) and variational beam search (b2). b) Solid lines indicate fitted mean f4 over time steps t with boxes representing lo error bars. See more information about the pictured "shy" variant in Supplement
capturing the previous posterior's mean and variance More formally,
Te ( Σ } (Mean,
Based on this choice, define the conditional prior as follows:
p(z T.) [N(ze; Ht-1: Et-1)
for 8t
(3)
(Mzz 14-1: 1 1-11 for 8t
Above, 0 < 3 < is a hyperparameter referred to as inverse temperature If no change is detected (i.e., 8, 0), our prior becomes Gaussian distribution centered around the previous posterior's mean and variance. In particular, if the previous posterior was already Gaussian, it becomes the new prior. In contrast, if a change was detected, the broadened posterior becomes the new prior.
5
For as long as no changes are detected (8; 0), the procedure results a simple Bayesian online learning procedure, where the posterior uncertainty shrinks with every new observation. In contrast, a change detected (s; = 1), an overconfident prior would be harmful for learning as the model needs adapt the data distribution. We therefore weaken the prior through tempering. Given temperature B, we raise the previous posterior's s Gaussian approximation to the power B, renormalize it, and then use it prior for the current time step.
The process of tempering the Gaussian posterior approximation can be understood as removing equal amounts of information in any direction in the latent space. To this, let z be multivariate Gaussian with covariance Σ and u be a unit direction vector. Then tempering removes an equal amount of information regardless of u, Hu 2 (2 Σu) log 3, erasing learned information to free-up model capacity to adjust to the new data distribution. See Supplement for more details.
Connection to Sequence Modeling Our model assumptions have resemblance to time series modeling: if we replaced т, with 2;-1, we would condition on previous latent states rather than posterior summary statistics. In contrast, our model still factorizes over time and therefore makes weaker assumptions on temporal continuity. Rather than imposing temporal continuity on a data instance level, we instead assume temporal continuity at distribution level.
Connection Changepoint Modeling. We also share similar assumptions with the changepoint literature (Barry and Hartigan 1992). However, in most cases, these models don't assume an informative prior, effectively not taking into account any sufficient statisties T This forces these models to re-learn model parameters from scratch after a detected change, whereas our approach allows for some transfer of information before and after the distribution shift.
3.2 Exact Inference
Before presenting a scalable variational inference scheme in our model, we describe an exact inference scheme when everything is tractable, i.e., the special case of linear Gaussian models.
'In later sections, will Gaussian approximation the posterior, but here it is enough to assume that these quantities are computable.
In general it only requires @ > 0 to be inverse temperature. We further assume / < in this paper as this value interval broadens and weakens the previous posterior. See the following paragraphs.

---

According to our assumptions, the distribution shifts occur at discrete times and are unobserved. Therefore, we have to infer them from the observed data and adapt the model accordingly. Recall the distribution shift is represented by the binary latent variable St at time step 1. Inferring the posterior over 8, at will thus notify us how likely the change happens under the model assumption. As follows, we show the posterior of 8t is simple in tractable model and bears similarity with a likelihood ratio test. Suppose we moved from time step t - to step t and observed new data x Denote the history decisions and observations by ( 11:t- ))) which enters through T,. Then by Bayes rule, the exact posterior over 8t is again a Bernoulli, p( |s1:-1,, X1:t) = Bern sz; m), with parameter
- m =0 (log p(x, 8 - 0, 01 X1 )p(p)) 00) = - 1og p(x, 0: = 1, $1:1-1. (1:t-) + Eo
p(xe 81 = 0, 81:--1, 11 XI:--)
(4) Above, a is the sigmoid function, and Eo = log p(st = 1) log p(st = 0) are the log-odds of the prior p(s,) and serves bias term. p(x,|$1:4 x1=-1) evidence. Overall, m specifies the probability of 8 = given X1 and 81:t-1-
p(x, (z, ) Tz) is the model
Eq. 4 has simple interpretation as a likelihood ratio test: a change is more or less likely depending on whether or not the observations x, are better explained under the assumption of detected change.
We have described the detection procedure thus far, now we turn to the adaptation procedure. To adjust the model parameters Z the new data given a change or not, we combine the likelihood of X4 with the conditional prior (Eq. 3}. This corresponds to the posterior of Ze. p(z, X14, $1:{) =
p(x, (n (s)T.) obtained by Bayes rule. The adaptation procedure is illustrated in Fig. 1 (a), where pla, X1st-) we show how a new observation modifies the conditional prior of model parameters.
As a result of Eq. we obtain the marginal distribution of 2₁ at time L. as a binary mixture with mixture weights p( = 1/81:-1,, x1:+) m and p(st = -1/81 x1:e) 1 m: p(z, (1: mp = $14-1. x1x)) + (1 (1- m) Ze St = 0, -14-1, X1:).
Exponential Branching We note that while we had originally started with a posterior p(z.-1 11 at the previous time, our inference scheme resulted in p(z Xia) being mixture of two components it branches over two possible states When iterate, encounter an exponential branching of possibilities, or hypotheses over possible sequences of regime shifts $1.6- To still carry out the filtering scheme efficiently, we need a truncation scheme, e.g., approximate the bimodal marginal distribution by a unimodal one. As follows, we will discuss two methods methods-greedy greedy search and beam search to achieve this goal.
Greedy Search In the simplest "greedy" setup. we train the model in an online fashion by iterating over time steps For each we update a truncated distribution via the following three steps:
1. Compute the conditional prior p(zu|14; T.) the likelihood p(x; (z:) upon observing data X,-
(Eq. 3 based on p(z--1 X1:t11 81:--1) and evaluate
2. Infer whether a change happens or not using the posterior over St (Eq. and adapt the model parameters z, for each case.
3. Select st E {0. 1} that has larger posterior probability p(s.|s1.c1,,11 X1+) and its corresponding model hypothesis pzz, x1:)) (i.e., make a "hard" decision over s, with threshold of f).
The above filtering algorithm iteratively updates the posterior distribution over 2, each time it observes new data x,. In the version of greedy search discussed above, the approach decides immediately, i.e., before observing subsequent data points, whether change in z, has occurred or not in step 3. (Please note the decision is irrelevant to history, as opposed to the beam search described below.) We illustrate greedy search illustrated in Fig. (b1) where VGS the variational inference counterpart.
Beam Search A greedy search is prone to missing change points in data sets with low signal/noise ratio per time step because cannot accumulate evidence for change point over a series of time steps. The most obvious improvement over greedy search that has the ability to accumulate evidence for a change point is beam search. Rather than deciding greedily whether a change occurred or not at each time step, beam search considers both cases in parallel as it delays the decision of which
Seee also Fig. I Supplement C
5

---

one is more likely (see Fig. | (b2) and Fig. F (left) for illustration). The algorithm keeps track of fixed number K > 1 of possible hypotheses of change points. For each hypothesis, iteratively updates the posterior distribution as a greedy search. At time step I, every potential continuation of the K sequences is considered with 8t E {0. 1}, thus doubling the number of histories of which the algorithm has to track. To keep the computational requirements bounded, beam search thus discards half of the sequences based on an exploration-exploittiie trade-off.
Beam search simultaneously tracks multiple hypotheses necessitating the differentiation between them. In greedy search, we can distinguish hypotheses based on the most recent sy value since only two hypotheses are considered at each step. However, beam search considers at most 2K hypotheses each step, which exceeds the capacity of a single st. We thus resort to the decision history $1:--1 1 to further tell hypotheses apart. The weight p( x1:)) of each hypothesis can be computed recursively:
p(81a(x1aa)
x p(s,, 81 X1: (
x p(s X1: (
(5)
where the added information (1 X x at step is the posterior of 8 (Eq. 4 This suggests the "correction in hindsight" nature of beam search: re-ranking the sequence $1:t as a whole at time t indicates the ability to correct decisions before time t.
Another ingredient is set B,, which contains the K most probable "histories" $1æt at time f. From time 1 to f, we evaluate the continuation of each hypothesis 51:t-1 E B,-1 the first two steps of greedy search, leading to 2K hypotheses. We then compute the weight of each hypothesis using Eq. 5 Finally, select top K hypotheses into B. and re-normalize the weights of hypotheses in B,,
This concludes the recursion from time - 1 to t. With p(ze|$1d. $1:2. X14) and p($1: (1a)), we can achieve any marginal distribution of 2,, such as p(z, (x..) E.... p(z] $1:1 X1.1 )p (11:) X1:)).
Beam Search Diversification Empirically, we find that the naive beam search procedure does not realize its full potential. As commonly encountered in beam search, histories over change points are largely shared among all members of the beam. To encourage diverse beams, constructed the following simple scheme. While transitioning from time 8-1 to f, every hypothesis splits into two scenarios, one with s O and one with s = resulting in 2K temporary hypotheses. If two resulting hypotheses only differ in their most recent 8 valuu, we say that they come from the same "family." Each member among the 2K hypotheses is ranked according to its posterior probability p( ( in (5 In a first step, we discard the bottom 1/ 1/3 of the 2K hypotheses, leaving 4/3K hypotheses (we always take integer multiples of 3 for K). To truncate the beam size from 4/3K down to K, we rank the remaining hypotheses according to their posterior probability and pick the top K ones while also ensuring that we pick a member from every remaining family. The diversification scheme ensures that underperforming families can survive, leading to a more diverse set of hypotheses. We found this beam diversification scheme to work robustly across a variety of experiments.
3.3 Variational Inference
In most practical applications, the evidence term is not available in closed-form, leaving Eq. intractable evaluate. However, we can follow structured variational inference approach [Wain. wright and Jordan| 2008 Hoffman and Blei 2013, Zhang et al.] 2018), defining a joint varia- [ 8 1:2 [g(z; 11.),, approximate p(z,, St $1.0-1. x
tional distribution o [z, 8e p( xI (P(2))(( x. This procedure completes the detection and adaptation altogether.
One may wonder how the exact inference schemes for 8; and 2; are modified in the structured varia- tional inference scenario. In Supplement/A AA we derive the solution for g(ze, se181=-1). Surprisingly we have the following closed-form update equation for q(a, (51.-1) that bears strong similarities to [q.4 The new scheme simply replaces the intractable evidence term with a lower bound proxy- optimized conditional evidence lower bound L(q*[s1a) (CELBO, defined later), giving the update
q (x.(81=11) = Bern(s;;)) m =
1x - C(4" 8: 0, 812-1) 1) + Eo)
(6)
Above, we introduced parameter 7 2 (not to be confused with (9) to optionally downweigh the data evidence relative to the prior (see Experiments Section

---

two hypotheses the
b)
Google boola
UN debotm
besena Drogpsie 15-
Li Smer (war)
Daaest Droppriee
2g
Desous Drogecte
biler
pda dess
X
xxx
Duerage Ouagg
20 time step
VSS Pey.
Duc 2 Canka
Figure 2: a) Inferring the mean (black line) of a time-varying data distribution (black samples) with VBS. The initially unlikely hypothesis begins dominating over the other step 23. b) Baskethall player tracking: ablation study over (3 for VBS while fixing other parameters. We used greedy search (K=1) and run the model under different 3 values. Increasing / leads more sensitivity to changes in data, leading to more detected changepoints. c) Document dating error as a function of model sparsity, measured in average words update per year. As semantic changes get successively sparsified by varying Eo (Eq. 6). VBS maintains a better document dating performance compared to baselines.
Now we define the CELBO. To approximate pize|S1:: X1:t) by variational distribution ((z)) we minimize the KL divergence between (z:() and p Zz $111, X1:t), leading to
q' (Zels1a) = arg max [(g)s1a),
C(g]s1a) == E, 1lg z.)] (L(q
Q denotes the variational family (i.e., factorized normal distributions), and we term L(g s1..) CELBO.
The greedy search and beam search schemes also apply to variational inference. We name them variational greedy search (VGS, VBS (K=1)) and variational beam search (VBS) (Fig. [ (b)).
Algorithm Complexity VBS's computational time and space complexity scale linearly with the beam size K. As such, its computational cost is only about 2K times larger than greedy search" Furthermore, our algorithm's 's complexity is ((1) in the sequence length t. It is not necessary to store sequences $1r they are just symbols distinguish hypotheses. The only exception this scaling would be an application asking for the most likely changepoint sequence in hindsight. In this case, the changepoint sequence (but not the associated model parameters) would need to be stored, incurring a cost of storing exactly K x T binary variables. This storage is, however, not necessary when the focus is only on adapting distribution shifts.
Experiments
Overview The objective of our experiments is show that, compared other methods, variational beam search (1) better reacts to different distribution shifts, e.g., concept drifts and covariate drifts, while (2) revealing interpretable and temporally sparse latent structure. We experiment on artificial data to demonstrate the "correct in hindsight" nature of VBS (Section 4.1). evaluate online linear regression on three datasets with concept shifts (Section 4.3). visualize the detected change points on basketball player movements, demonstrate the robustness of the hyperparameter /3 (Section 4.3). study Bayesian deep learning approaches on sequences of transformed images with covariate shifts (Section 4.4). and study the dynamics of word embeddings on historical text corpora (Section 4.5) Unstated experimental details are in Supplement G
4.1 An Illustrative Example
We first aim to dynamically demonstrate the "correction in hindsight" nature of VBS based on simple setup involving artificial data. To this end, we formulated a problem of tracking the shifting mean of data samples. This shifting mean is a piecewise-constant step function involving two steps (seen as in black in Fig. 2 (a)), and we simulated noisy data points centered around the mean. We then used VBS with beam size K = 2 to fit the same latent mean model that generated the data, The color indicates the ranking among both hypotheses at each moment in time (blue as "more likely"
"This also applies to the baselines "Bayesian Forgetting" (BF) and Variational Continual Learning" (VCL) introduced in Section 4.2
7

---

vs. orange as "less likely"), While hypothesis 1 assumes a single distribution shift (initially blue), hypothesis 2 (initially orange) assumes two shifts. We see that hypothesis 1 initially more likely. but gets over-ruled by the better hypothesis 2 later (note the color swap at step 23).
4.2 Baselines
In our supervised experiments (Section 4.3 and Section 4.4). we compared VBS against adaptive methods, Bayesian online learning baselines, and independent batch learning baselines | Among the adaptive methods, we formulated supervised learning version of Bayesian online change-
point detection (BOCD) [Adams and MacKay 2007] 9 We also implemented Bayesian forgetting
(BF) [Kurle et al., 2020 with convolutional neural networks for proper comparisons. Bayesian online
learning baselines include variational continual learning (VCL) [Nguyen et al. 2018] and Laplace propagation (LP) [Smola et al., 2003 Nguyen et al. 2018). Finally, we also adopt a trivial baseline of learning independent regressors/classiieet on each batch in both a Bayesian and non-Bayesian fashion. For VBS and BOCD we always report the most dominant hypothesis. In unsupervised learning experiments, we compared against the online version of word2vec [Mikolov et al., 2013) with a diffusion prior, dynamic word embeddings Baaller and Mandt 2017].
4.3 Bayesian Linear Regression Experiments
As a simple first version of VBS, we tested an online linear regression setup for which the posterior can be computed analytically. The analytical solution removes the approximation error of the variational inference procedure as well as optimization-related artifacts since closed-form updates are available. Detailed derivations are in Supplement)
Real Datasets with Concept Shifts. We investigated three real-world datasets with concept shifts:
Malware This dataset is a collection of 100K malignous and benign computer programs. collected over 44 months [Huynh et al., 2017]. Each program has 482 counting features and a real-valued probability p E (0, 1] of being malware. We linearly predicted the log-odds.
SensorDrift A collection of chemical sensor readings (Vergara et al. 2012). We predicted the concentration level of gas acetaldehyde, whose 2,926 samples and 128 features span 36 months.
Elec2 The dataset contains the electricity price over three years of two Australian states (Harries) and Wales| 1999]. While the original problem formulation used a majority vote to generate 0-1 binary labels on whether the price increases not, we averaged the votes out into real-valued probabilities and predicted the log-odds instead. We had 45,263 samples and 14 features.
At each step, only one data sample is revealed the regressor. We evaluated all methods with one-step-ahead absolute erro [T0] and computed the mean cumulative absolute error (MCAH) at every step. In Table I we didn't 't report the variance of MCAEs since there is no stochastic optimization noise. Table shows that VBS has the best average of MCAES among all methods. We also reported the running performance in Supplement G.2] where other experimental details are available as well.
Basketball Player Tracking. We explored a collection of basketball player movement trajecto- ries Each trajectory has wide variations in player velocities. We treated the trajectories time series and used a Bayesian transition matrix to predict the next position X,+1 based on the current position Xz. This matrix is learned and adapted on the fly for each trajectory.
We first investigated the effect of the temperature parameter 3 in our approach. To this end, we example trajectory. We used VBS (K=1, greedy search)
visualized the detected change points and compared different values of 3 in Fig. (b). The figure shows that the larger 3, the more change
As a reminder, a "batch" at discrete time is the dataset available for learning; on the other hand, a "mini-bater batch" is small set of data used for computing gradients for stochastic gradient- based optimization.
"1) Although BOCD is mostly applied its underlying model's adaptation to change points are seldom investigated. 2) When the model is non-conjugate, such as Bayesian neural networks, we approximate the log evidence log p(ylæ) by the evidence lower bound. We measured the error the probability space for classification problems (Malware and Elec2) and the error in the data space for regressioo problems (SensorDrift).
unsupervised learning, its application in supervised learning and
https: / // /gi trub wwtp/////////////o/ooeooo 2aa./////AAAaAAaeee-ea Player- Movement
8

---

Table 1: Evaluation of Different Datasets
100
"simulation"
1960 mathomaticall preg deductive
MODELS
CIFAR-10
SVHN
MALWARD SENSOEDRERTT BLEC2
NRAPLAYER
mecning
0.5
(ACCURACV)
(MCAE 10
(LoGLiKE 10"")]
combination on neceptiee
Cimianir to
VRS (K-6)*
69.24.0.9
89.6:0.5
11.61
29.49:13.12
an
VBS (K-3)*
68.92:0.9
89.1
11.65
10.71
29.2242.63
1940
1980
VBS (K-1)"
68:24:0.8
88.9200.5
11.65
10.36
7.27
29.25
"atom"
2011 neutron stomic
ROCD (K-6)f
65.6-201.8
08.2
12.93
24.34
12.49
22.96:77.42
BOCD (K=3)1
67.11:0.8
88 k::0.5
12:74
24.31
12.49
20.9347.88
thermonudled
BF
69.8110.8
8..9
11.71
11,40
13.37
24.17:1..29
1945
VCL.1
66.7.10:8
88.7
13.27
24,90
16.59
2,48
inexhaustible
ceneanms change 2017)
LP
62.6::1.0
82.8:10.9
13:27
24,90
3.45:25.53
0.0
intrinsic
IR 63.72005
05.
16.6
27.71
12.48
-44.87:116 88
IB' (DAYES)
64.51:0.3
87.8:10.1
16.6
27.71
12.48
-44.87:116.88
Figure 3: Sparse word meaning changes in "simulation" and "atom".
PROPOSED, 3 [ADAMS AND MACKAY. 2007],
[KURLE ML., 2020]
[NOUYEX ET AL., 2018).
[SMOLA ET Al., 2003]. INDEPENDENT BATCH
points are detected; the smaller 3, the detected change points get sparser, i.e., 8 determines the model's sensitivity to changes. This observation confirms the assumption that 3 controls the assumed strength of distribution shifts.
In addition, the result also implies the robustness of poorly selected Bs. When facing an abrupt change in the trajectory, the regressor has two adapt options based on different As make a single strong adaptation or make a sequence of weak adaptations in either case, the model ends up adapting itself to the new trajectory. In other words, people can choose different 3 for specific environment, with a trade-off between adaptation speed and the erased amount of information.
Finally, regarding the quantitative results, evaluated all methods with the time-averaged predictive log-lik le-likkelioood on a reserved test set in Table Our proposed methods yield better performance than the baselines. In Supplement| F we provide more results of change point detection.
4.4 Bayesian Deep Learning Experiments
Our larger-scale experiments involve Bayesian convolutional neural networks trained on sequential batches for image classification using CIFAR-10 (Krizhessky et al. 2009] and SVHN (Netzer et al., 2011]. Every few batches, we manually introduce covariate shifts through transforming all images globally by combining rotations, shifts, and scalings. Each transformation is generated from a fixed, predefined distribution (see Supplement G.3). The experiment involved 100 batches in sequence, where each batch contained third of the transformed datasets. We set the temperature ==2/3 and set the CELBO temperature T = =20, 000 (in () for all supervised experiments.
Table shows the performances of all considered methods and both data sets, averaged across all of the 100 batches. Within their confidence bounds, VBS and BF have comparable performances and outperform the other baselines. We conjecture that the strong performance of BF can be attributed to the fact that our imposed changes are still relatively evenly spaced and regular. The benefit of beam search in VBS is evident, with larger beam sizes consistently performing better.
4.5 Unsupervised Experiments
Our final experiment focused on unsupervised learning. We intended demonstrate that VBS helps uncover interpretable latent structure in high-dimensional time series by detecting change points. We also showed that the detected change points help reduce the storage size and maintain salient features.
Towards this end, we analyzed the semantic changes of individual words over time in an unsupervised setup. We used Dynamic Word Embeddings (DWE) [Bamler and Mandi 2017 as our base model. The model is an online version of Word2Vec [Mikolov et al. [013]. Word2 Vec projects a vocabulary into embedding space and measures word similarities by cosine distance in that space. DWE further imposes a time-series prior on the embeddings and tracks them over time. For our proposed approach, we augmented DWE with VBS, allowing us detect the changes of words meaning.
We analyzed three large time-stamped text corpora, all of which are available online. Our first dataset is the Google Books corpus [Michel et al. 2011 n-grams form. We focused on 1900 to 2000

---

with sub-sampled 250M to 300M tokens per year. Second, we used the Congressional Records dataset [Gentzkow et al. 2018 which has 13M to 52M tokens per two-year period from 1875 to 2011. 1. Third, we used the UN General Dehates corpus (Jankin Mikhaylov et al. 2017]. which has about 250k to 450k tokens per year from 1970 to 2018.
Our first experiments demonstrate VBS provides more interpretable step-wise word meaning shifts than the continuous shifts (DWE). Due to page limits, in Fig. 3 we selected two example words and their three nearest neighbors in the embedding space at different years. The evolving nearest neighbors reflect a semantic change of the words. We plotted the most likely hypothesis of VBS in blue and the continuous pathh baseline (DWE) in grey. While people can roughly tell the change points from the continuous path, the changes are surrounded by noisy perturbations and sometimes submerged within the noise. VBS, on the other hand, makes clear decisions and outputs explicit change points. As a result, VBS discovers that the word "atom" changes its meaning from "element" to "nuclear" in 1945-the year when two nuclear bombs were detonated; word "simulation" changes its dominant context from "deception" to "programming" with the advent of computers in the 1950s. Besides interpretable changes points, VBS provides multiple plausible hypotheses (Supplement (.4).
Our second experiments exemplify the usefulness of the detected sparse change points, which lead to sparse segments of embeddings. The usefulness comes in two folds: 1) while alleviating the burden of the disk storage by storing one value for each segment, 2) the sparsity preserves the salient features of the original model. To illustrate these two aspects. we design a document dating task that exploits the probabilistic interpretation of word embeddings. The idea to assign a test document to the year whose embeddings provide the highest likelihood. In Figure 2 (c), we measure the model sparsity on the x-axis with the average updated embeddings per step (The maximum is 10000, which the vocabulary size). The feature preservation ability is measured by document dating accuracy on the y-axis. We adjust the prior log-odds Eo (Eq. (6) to have successive models with different change point sparsity and then measure the dating accuracy. We also designed an oracle baseline named "binning" (grey, Supplement G.4). For VBS, we show the dominant hypothesis (blue) as well as the subleading hypotheses (orange). The most likely hypothesis of VBS outperforms the baseline, leading to higher document dating precision at much smaller disk storage.
Discussion
Beyond Gaussian Posterior Approximations. While the Gaussian approximation is simple and is widely used (and broadly effective) in practice in Bayesian inference [c.g.. Murphy (2012), Pp.649- 662], our formulation does not rule out the extensions to exponential families. T. in Eq. 2 could be generalized by reading off sufficient statistics of the previous approximate posterior. To this end, we need a sufficient statistic that is associated with some measure of entropy or variance that broaden after each detected change. For example, the Gamma distribution can broaden its scale, and for the categorical distribution, we can increase its entropy/temperatuee More intricate (e.g. multimodal) possible alternatives for posterior approximation are also possible, for example, Gaussian mixtures.
6 Conclusions
We introduced variational beam search: an approximate inference algorithm for Bayesian online learning on non-stationary data with irregular changes. Our approach mediates the tradeoff between a model's ability to memorize past data while still being able to adapt to change. is based on a Bayesian treatment of a given model's parameters and aimed at tuning them towards the most recent data batch while exploiting prior knowledge from previous batches. To this end, we introduced a sequence of discrete change variables whose value controlled the way we regularized the model. For no detected change, we regularized the new learning task towards the previously learned solution; for detected change, we broadened the prior to give room for new data evidence. This procedure is combined with beam search over the discrete change variables. In different experiments, we showed that our proposed model (1) achieved lower error in supervised setups, and (2) revealed more interpretable and compressible latent structure in unsupervised experiments.
Broader Impacts. As with many machine learning algorithms, there is a danger that more automa- tion could potentially result in unemployment. Yet, more autonomous adaptation to changes will enhance the safety and robustness of deployed machine learning systems, such self-driving cars.
10

---

Acknowledgements
We gratefully acknowledge extensive contributions from Rohert Bamler (previously UCI, now the University of Tübingen), which were indispensable to this work.
This material is based upon work supported by the National Science Foundation under the CAREER award 2047418 and grant numbers 1633631, 1928718, 2003237, and 2007719 19; by the National Science Foundation Graduate Research Fellowship under grant number DGE- 1839285; by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001 120C0021; by Intel grant; and by grants from Qualcomm. Any opinion, findings, and conclusions or recommendations expressed this material are those of the authors and do not necessarily reflect the views of the National Science Foundation, revenues potentially related to this work include: research funding from NSF, NIH, NIST, PCORI, and SAP; fellowship funding from HPI; consulting income from Amazon.com.
do they reflect the views of DARPA. Additional
References
John R Zech. Marcus A Badgeley, Manway Liu, Anthony B Costa, Joseph J Titano, and Eric Karl Oermann. Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: A cross-sectional study. PLOS medicine, 15(1 ()11))eel 1006683, 2018.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. In Advances in Neural Information Processing Systems, 2019.
Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning.
In International Conference on Learning Representations, 2018.
Antti Honkela and Harri Valpola. On-line variational bayesian learning. In 4th International Symposium on Independent Component Analysis and Blind Signal Separation, 2003.
Masa-Aki Sato. Online model selection based on the variational bayes. Neural computation, 13(7):
1649-1681, 2001.
Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian tlikkthhooggh rate prediction for sponsored search advertising in microsoft's 's bing search engine. In ICML, 2010.
James McInerney, Rajesh Ranganath, and David Blei. The population posterior and bayesian modeling on streams. Advances in neural information processing systems, 28: 1 153-1161, 2015.
Lucas Theis and Matt Hoffman. A trust-region method for stochastic variational inference with applications to streaming data. In International Conference on Machine Learning, pages 2503- 2511. PMLR, 2015.
R Kulhavý and Martin B Zarrop. On general concept of forgetting. International Journal of Control, 98(4))905-922, 1993.
Richard Kurle, Botond Cseke, Alexej Klushyn, Patrick van der Smagt, and Stephan Günnemann. Con- tinual learning with bayesian neural networks for non-stationary data. In International Conference on Learning Representations, 2020.
Sebastian Farquhar and Yarin Gal. A unifying bayesian view of continual learning. Third workshop on Bayesian Deep Learning (NeurIPS 2018), 2018
Jonathan Schwarz, Daniel Altman, Andrew Dudzik, Oriol Vinyals, Yee Whye Teh, and Razvan Pascanu. Towards natural benchmark for continual learning. In NeurIPS Workshop Continual Learning, 2018.
James Kirkpatriek, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Bann Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3526, 2017.
11

---

Michalis K Titsias. Jonathan Schwarz, Alexander G de G Matthews, Razvan Pascanu, and Yee Whye Teh. Functional regularisation for continual learning with gaussian processes. In International Conference on Learning Representations, 2019.
Soochan Lee, Junsoo Ha, Dongsu Zhang, and Gunhee Kim. A neural dirichlet process mixture model for task-free continual learning. In International Conference on Learning Representations, 2020,
Dushyant Rao, Francesco Visin, Andrei Rusu, Razvan Pascanu, Yee Whye Tch, and Raia Hadsell. Continual unsupervised representation learning. In Advances in Neural Information Processing Systems, pages 7647-7657, 2019.
Daniel Barry and John A Hartigan. Product partition models for change point problems. The Annals of Statistics, pages 260-279, 1992.
Paul Fearnhead. Exact bayesian curve fitting and signal segmentation. IEEE Transactions on Signal Processing, (3(6):216021166) 2005.
Paul Fearnhead and Zhen Liu. Online inference for multiple changepoint problems. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 69(4):589-605, 2007.
Ryan Prescott Adams and David JC MacKay. Bayesian online changepoint detection. arXiv preprint arXiv:0710.374 2007.
Xiang Xuan and Kevin Murphy. Modeling changing dependency structure in multivariate time series. In Proceedings of the 24th international conference on Machine learning, pages 1055-1062, 2007.
Yao Xie, Jiaji Huang, and Rebecca Willett. Change-point detection for high-dimensiona time series with missing data. IEEE Journal of Selected Topics in Signal Processing, 7(1):12-27, 2012.
Yunus Saatçi, Ryan D Turner, and Carl Edward Rasmussen. Gaussian process change point models. In ICML, 2010.
Jeremias Knoblauch and Theodoros Damoulas. Spatio-temporal bayesian on-line changepoint detection with model selection. In International Conference on Machine Learning, pages 2718- 2727. PMLR, 2018.
Ryan Turner, Steven Bottone, and Clay Stanek. Online variational approximations to non-exponential family change point models; With application to radar tracking. In Proceedings of the 26th International Conference on Neural Information Processing Systems-Volue Volume 1, pages 306-314, 2013.
Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas. Doubly robust bayesian inference for non-stationary streaming data with 8-divergences. volume 31, 2018.
Michalis K Titsias, Jakub Sygnowski, and Yutian Chen. Sequential changepoint detection in neural networks with checkpoints. arXiv preprint arXiv:2010.03053, 2020.
Scott Linderman, Matthew Johnson, Andrew Miller, Ryan Adams, David Blei, and Liam Paninski. Bayesian learning and inference in recurrent switching linear dynamical systems. In Artificial Intelligence and Statistics, pages 914-922, 2017.
Philip Becker-Ehmek, Jan Peters, and Patrick Van Der Smagt. Switching linear dynamics for variational bayes filtering. In International Conference on Machine Learning, pages 553-562, 2019.
Kevin P Murphy, Machine learning: probabillistic perspective. MIT press, 2012.
David Barber. Bayesian reasoning and machine learning. Cambridge University Press, 2012.
Chris Bracegirdle and David Barber. Switch-reset models: Exact and approximate inference. In Proceedings The Fourteenth International Conference on Artificial Intelligence and Statistics, pages 190-198, 2011.
Martin Wainwright and Michael Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008
12

---

Matthew D Hoffman and David M Blei. Structured stochastic variational inference. In Artificial Intelligence and Statisties, 2015.
Cheng Zhang, Judith Bütepage, Hedvig Kjellström, and Stephan Mandt. Advances in variational
inference. IEEE transactions puttern analysis and machine intelligence, (1(8))2008-2022 2018.
Alexander Smola, Vishy Vishwanathan, and Eleazar Eskin. Laplace propagation. In NIPS, pages 441-448, 2003.
Tomas Mikolov, Πya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111-3119, 2013.
Robert Bamler and Stephan Mandt. Dynamic word embeddings. Proceedings of the 34th International Conference Machine Learning-Volume 70, pages 380-389. JMLR. org, 2017.
Ngoc Anh Huynh, Wee Keong Ng, and Kanishka Ariyapala. A new adaptive learning algorithm and its application to online malware detection. In International Conference on Discovery Science, pages 18-32. Springer. 2017.
Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical, 166:320-329, 2012.
Michael Harries and New South Wales. Splice-2 comparative evaluation: Electricity pricing. 1999.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Cean-Baptiste Michel, Yuan Kui Shen, Aviva Presser Aiden, Adrian Veres, Matthew K Gray, Joseph P Pickett, Dale Hoiberg, Dan Clancy, Peter Norvig, Jon Orwant, et al. Quantitative analysis of culture using millions of digitized books. science, 33 (61144)) 2011.
Matthew Gentzkow, JM Shapiro, and Matt Taddy. Congressional record for the 43rd- 14th congresses: Parsed speeches and phrase counts. In URL: https://data. stanford. edu/congress text, 2018.
Slava Jankin Mikhaylov, Alexander Baturo, and Niheer Dasandi. United Nations General Debate Corpus, 2017. URL htt.::ttt////oo org/10. 10. 7010////OTO//
13


Reviews:
[{"review_id": "sNhtqi9Sjze", "reviewer": "Reviewer_cuE8", "summary": "The paper focuses on distribution shift, i.e. the distribution that generates the data changes with time, something that can cause problems to static models since now the train and test distributions are not the same. The authors take an online Bayesian perspective and try to detect a changes in the distribution based on the data points that are received in each iteration. They also perform extensive experiments in different domains.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I liked the paper, it provided an interesting perspective in distribution shift detection which has become a core problem to study recently in machine learning literature. The presentation of the paper is clear, I liked that the authors started by presenting the exact inference, before the introduction of variational inference, it helped understand the main idea although some parts of the paper were still technical and hard to follow in detail. The experiments were also very thorough and in several different datasets. One question I have for the experimental part, is how does the VBS approach compare with just using static models. In the case of CIFAR for example there is a large performance gap between the best performance that a neural network can achieve for normal CIFAR and the accuracy that VBS obtains for the modified dataset used here. I am wondering how well does a static model trained on CIFAR performs for the modified dataset and how does it compare to VBS. I am also not sure that I understand what the \"trivial baseline\" of independent batches is. Does it mean that you use the data points from this batch to learn a model? How does this work for CIFAR when you have only 100 samples per batch? (I probably misunderstood that but I would appreciate the clarification)\n\nTypos:\n- l320: MNIST or SVHN: should it be CIFAR?\n- l347: whilee", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "JzVTY7L2nI5", "reviewer": "Reviewer_kxgB", "summary": "This submission relates a method for adapting to distribution shifts online in a Bayesian fashion. A distribution shift is represented as a binary latent variable indicating that a shift has, or has not occurred. If a shift is inferred to have occurred, then the variance of the posterior is increased before the next step of the Bayesian recursion, weakening the influence of previous observations. Computational constraints associated with maintaining many possible hypotheses of the incidence of distribution shifts are remedied by the use of beam search. \n\nThis paper is timely and well-written. The topic of online adaptation to distribution shift is very relevant to the NeurIPS community, and the submission has developed through several rounds of peer review into a mature contribution to the literature. There are some substantial limitations that would be important to address in future work, but I am happy to recommend acceptance and willing to defend my evaluation.\n\nUPDATE 08/17/2021\nThe author response has addressed all my concerns. In particular it is very good to know that the full changepoint history need not be maintained, and that the method will automatically adapt, in a sense, to a poor choice of \\beta. I think this is a very good paper, and have increased my score to 8.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The approach as described is very thoroughly developed. As noted in the submission meta-data, this is the third round of peer review that this work has received, and I believe it represents a worthy contribution in its current state. There are a couple relevant references that have been omitted, but overall the literature review is adequate. I find the experiment evaluation sufficient to verify the quality of the idea. \n\nThe asymptotic memory and compute complexity (particularly in terms of the time horizon) do not appear to be clearly stated, aside from a brief discussion of memory requirements in G.4.1.\nI understand that beam search remedies the combinatorial explosion of possible histories, but it does not address the fact that even a fixed set of K sequences must eventually grow to infinite length in the current formalism. Of course the histories could simply be truncated, but that approach introduces history length as another hyperparameter to tune. Is there a more principled way to address the scaling with the time horizon (see limitations for more discussion on the importance of this question)? \n\nThe way the method is introduced in terms of sufficient statistics creates the expectation that the method will be generally developed for any exponential conjugate prior. This extension would be worth considering for future work.\n\n---- References ----\n\n[1] Bui, T. D., Nguyen, C. V., and Turner, R. E. (2017). Streaming sparse Gaussian process approximations. In Advances in Neural Information Processing Systems 31, pages 3301–3309, Long Beach, California, USA. Curran Associates Inc.\n\n[2] Stanton, S., Maddox, W., Delbridge, I., & Wilson, A. G. (2021, March). Kernel Interpolation for Scalable Online Gaussian Processes. In International Conference on Artificial Intelligence and Statistics (pp. 3133-3141). PMLR.\n\n[3] Oord, A. V. D., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., ... & Kavukcuoglu, K. (2016). Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499.\n\n[4] Solin, A., Hensman, J., & Turner, R. E. (2018). Infinite-horizon Gaussian processes. arXiv preprint arXiv:1811.06588.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are some conceptual shortcomings of the method as proposed that prevent this good paper from being great. \n\nWhile the method is an online algorithm, it is not a streaming algorithm, and in practice streaming algorithms are necessary for deployment to most devices (for example, the sampling rate of a smartphone accelerometer is ~200 Hz [4]). The method is unlikely to be used in the (presumably low-latency) contexts of “... systems such as self-driving cars, robots, and financial trading algorithms…” until it is a streaming algorithm. In future work, it would be very intriguing to see if the method could be adapted to constant-time streaming sparse GPs, such as [1] or [2]. \n\nAlong similar lines, the need to tune the hyperparameters offline is also a pretty serious limitation. In particular I see no reason why the \\beta that worked well for one type of distribution shift would work well for another. The method could more plausibly be deployed if there was a sensible way to adapt the hyperparameters online.\n\nThe final limitation relates to the choice to model distribution shifts as binary changepoints. In particular, it would have been very interesting to see some experiments or discussion of the virtues of the changepoint detection class of methods vs. directly modeling possible shifts in the data generating process. As an example, in the rotated MNIST experiment, instead of modeling discrete (unknown) shifts, one could instead take the latent variable to be the average rotation (a continuous value). Obviously it would complicate the beam search process, but it would not be impossible, because one can always discretize a continuous signal (see e.g., the quantization scheme in [3]). I suspect that a well-specified hypothesis class of possible shifts would improve the speed of adaptation and allow for continuous shifts, which are an important case to consider (e.g. the relatively continuous shift in light intensity from day to night as a function of time).\n\nSince this work relates to a very general class of methods, I have no concerns about potential social impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns with this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "2vHvVnUWwVX", "reviewer": "Reviewer_GfAk", "summary": "In this paper, the authors propose a method to jointly model the data and also change points in the model parameters.\nThis is accomplished following a Bayesian approach, where the full vector of change point detections (as binary indicators) is part of the model, and it informs the marginal posterior.\nThe method is illustrated in an interesting mix of real and synthetic data.\n\nUPDATE: The authors' responses were succinct and useful. However, I still think that the paper relies on too many approximations/heuristics. The approach is sensible, and the paper could be impactful, but they don't constitute a Neurips-level contribution.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, the authors propose a method to jointly model the data and also change points in the model parameters.\nThis is accomplished following a Bayesian approach, where the full vector of change point detections (as binary indicators) is part of the model, and it informs the marginal posterior.\nThe method is illustrated in an interesting mix of real and synthetic data.\n\nOverall, this paper is well written and deals with an important problem. However, I have some important concerns:\n\n* The method looks highly impractical to me. A full vector of change points is being carried around, and so the dimensionality of the model explodes. There are some interesting heuristics proposed, but they are all approximate heuristics, and so it is unclear how all this works in practice.\ne.g., how to approximate a bimodal distribution with a unimodal one ? ( L182).\n\n* On a related note, I find the normality assumption in (2) and (3) to be severely restrictive. I understand that the Bayesian approach requires this kind of simplifications, but this assumption automatically precludes practical cases. with, say, categorical or sparse or missing data. \n\n* At several points the authors describe an \"exact inference\" scheme. I am not sure what exact inference means here, especially given the number of heuristic methods involved.\n\n* In L296, what does it mean to reproduce the targets with real-valued probabilities?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-rThZ0pA8p9", "reviewer": "Reviewer_qHGH", "summary": "This paper addresses the topic of changepoint detection in the event of distribution shift. A Bayesian model meant to detect such changes online, and able to discount historical information after a distributional shift, is formulated to express the problem. Algorithmic implementation is provided and evaluated across a number of data sets.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well organized and written: the problem is properly defined, assumptions are clearly stated, formalization rigorous; the reasoning steps in the development of the inference algorithm are also easy to follow. Experiments are extensive, and the sub-selection in the main paper suitably illustrative; some considerations on the compuational cost (as a function of the variational hyperparameters like beam size) against the SotA methods considered would have been interesting. Related works clearly relates the current work to the literature, although this reviewer is not able to judge independently how innovative the work is within the context of changepoint detection models.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Short and sufficient considerations on broader impact are offered at the end of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a Bayesian framework for detecting and adaptive to irregular distribution shifts. The reviewers generally appreciated the submission, and felt that the author response did a good job of addressing questions. While there were still some remaining questions about design decisions in the approach (see reviews), on the whole the paper represents a good contribution. Please carefully consider and incorporate reviewer comments in the final version.

Decision: Accept (Poster)