# Bayesian online changepoint detection (marginal predictive distribution)

The authors start by writing the marginal predictive distribution: $$P(x_{t+1} | \textbf{x}_{1:t}) = \sum_{r_t} P(x_{t+1} | r_t, \textbf{x}_t^{(r)}) P(r_t | \textbf{x}_{1:t}) \qquad \qquad (1)$$ where

• $x_t$ is the observation at time $t$;
• $\textbf{x}_{1:t}$ denotes the set of observation until time $t$;
• $r_t \in \mathbb{N}$ is the current runlength (time since last changepoint, can be 0); and
• $\textbf{x}_t^{(r)}$ is the set of observations associated with run $r_t$.

Eq. 1 is formally correct (see the reply below by @JuhoKokkala), but my understanding is that if you want to actually make a prediction about $x_{t+1}$ you'd need to expand it as follows:

$$P(x_{t+1} | \textbf{x}_{1:t}) = \sum_{r_t, r_{t+1}} P(x_{t+1} | r_{t+1}, \textbf{x}_t^{(r)}) P(r_t | \textbf{x}_{1:t}) P(r_{t+1} | r_t) \qquad (1\text{b})$$

My reasoning is that there might well be a changepoint at (future) time $t+1$, but the posterior $P(r_t | \textbf{x}_{1:t})$ only covers until $t$.

The point is, the authors in the paper make us of Eq. 1 as is (see Eqs. 3 and 11 in the paper), and not 1b. So, they seemingly ignore the possibility of a changepoint at time $t+1$ when predicting $x_{t+1}$ from data available at time $t$. At the beginning of Section 2 they say en passant

We assume that we can compute the predictive distribution [for $x_{t+1}$] conditional on a given run length $r_t$.

which perhaps is where the trick is. But in general, this predictive distribution should look something like Eq. 1b; which is not what they do (Eq. 11).

So, I am not sure I understand what's going on. Perhaps there is something funny going on with the notation.

### Reference

• Adams, R. P., & MacKay, D. J. (2007). Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742.
• A potential explanation is that $r_t$ represents the run length at the end of time step $t$, which is after the changepoint at time $t$. With this, Eq. 1 makes sense. In fact, one initialization of the algorithm is by setting $P(r_0 =0) = 1$ which assumes that there is a changepoint right before the start at $t=1$. However, Fig 1 is wrong (or at least misleading) in that if there is a changepoint between $t =4$ and $t=5$, and between $t=10$ and $t=11$ as depicted in Fig 1a, then $r_4$ and $r_{10}$ should be 0 according to this notation, and not $r_5$ and $r_{11}$ as per Fig 1b. Sep 14 '16 at 4:52
• There is something strange going on in Eq. 3 as the middle factor in the summand in the last line is $P(x_t \mid r_{t-1}, x^{(r)}_t)$ while I thought $x^{(r)}_t$ contains $x_t$. I suspect the $t$ and $t-1$ have switched places as $P(x_t \mid r_t, x^{(r)}_{t-1})$ would make sense. In Eq. 11, the right hand side seems to depend on $x_t^{(r)}$ which does not appear on the left hand side at all, so either there is something wrong or I don't understand the notation at all. Sep 14 '16 at 17:50
• @JuhoKokkala: I am glad I am not the only one with that feeling... Sep 14 '16 at 17:59
• @lacerbi, I have another question about this paper, and think you might be able to answer it since you seem familiar with the work: stats.stackexchange.com/questions/419988.
– gwg
Jul 31 '19 at 14:19

Both (1) and (1b) are correct. The OP has it right that (in this model) there might be a changepoint at $t+1$, and $x_{t+1}$ depends on whether there is a changepoint. This does not imply any problems with (1) as the possible values of $r_{t+1}$ are fully "covered" by $P(x_{t+1} \mid r_t, x_{1:t})$. $P(x_{t+1} | r_t, x_{1:t})$ means the conditional distribution of $x_{t+1}$ conditional on $(r_t, x_{1:t})$. This conditional distribution averages over "everything else", including $r_{t+1}$, conditional on $(r_t, x_{1:t})$. Just like one could write, say, $P(x_{t+1000} | x_t)$, which would take into account all possible configurations of changepoints as well as values of $x_i$s occurring between $t$ and $t+1000$.

In the remainder, I first derive (1) and then (1b) based on (1).

### Derivation of (1)

For any random variables $A,B,C$, we have \begin{equation} P(A \mid B) = \sum_c P(A \mid B, C=c)\,P(C=c \mid B), \end{equation} as long as $C$ is discrete (otherwise the sum needs to be replaced by an integral). Applying this to $x_{t+1},x_{1:t},r_t$:

\begin{equation} P(x_{t+1} \mid x_{1:t}) = \sum_{r_t} P(x_{t+1} \mid r_t, x_{1:t})\,P(r_t \mid x_{1:t}), \end{equation} which holds no matter what the dependencies between $r_t$, $x_{1:t}$, $x_{t+1}$ are, that is, no model assumptions have yet been used. In the present model, $x_{t+1}$ given $r_t,x^{(r)}_t$ is assumed* to be conditionally independent of the values of $x$ from the runs before $x^{(r)}_t$. This implies $P(x_{t+1} \mid r_t, x_{1:t}) = P(x_{t+1} \mid r_t, x^{(r)}_t)$. Substituting this into the previous equation, we get

\begin{equation} P(x_{t+1} \mid x_{1:t}) = \sum_{r_t} P(x_{t+1} \mid r_t, x^{(r)}_t)\,P(r_t \mid x_{1:t}), \qquad \qquad \qquad (1) \end{equation} which is (1) in OP.

### Derivation of (1b)

Let us consider the decomposition of $P(x_{t+1} \mid r_t, x^{(r)}_t)$ over possible values of $r_{t+1}$: \begin{equation} P(x_{t+1} \mid r_t, x^{(r)}_t) = \sum_{r_{t+1}} P(x_{t+1} \mid r_{t+1}, r_t, x^{(r)}_t)P(r_{t+1} \mid r_t, x^{(r)}_t). \end{equation}

Since it is assumed* that whether a changepoint occurs at $t+1$ (between $x_t$ and $x_{t+1}$) does not depend on the history of $x$, we have $P(r_{t+1} \mid r_t, x^{(r)}_t) = P(r_{t+1} \mid r_t)$. Furthermore, since $r_{t+1}$ determines whether $x_{t+1}$ belongs into the same run as $x_t$, we have $P(x_{t+1} \mid r_{t+1}, r_t, x^{(r)}_t)=P(x_{t+1} \mid r_{t+1}, x^{(r)}_t)$. Substituting these two simplifications into the factorization above, we get \begin{equation} P(x_{t+1} \mid r_t, x^{(r)}_t) = \sum_{r_{t+1}} P(x_{t+1} \mid r_{t+1}, x^{(r)}_t)P(r_{t+1} \mid r_t). \end{equation} Substituting this into (1), we get \begin{equation} P(x_{t+1} \mid x_{1:t}) = \sum_{r_t} \left(\sum_{r_{t+1}} P(x_{t+1} \mid r_{t+1}, x^{(r)}_t)P(r_{t+1} \mid r_t)\right)\,P(r_t \mid x_{1:t}), \qquad (1b) \end{equation} which is OP's (1b).

### * Remark on the model's conditional independence assumptions

Based on quickly browsing the paper, I would personally like the conditional independence properties to be more explicitly stated somewhere, but I suppose that the intention is that $r$ is Markovian and the $x$:s associated to different runs are independent (given the runs).

• (+1) Thanks. Yep, of course, I understand that Eq. 1 is formally correct if one assumes implicit marginalization over $r_{t+1}$. The problem is that later on the authors make predictions (Eq. 11 in the paper, and implicitly in Eq. 3) and they are seemingly not marginalizing over $r_{t+1}$ when they take them. Sep 14 '16 at 17:09
• Oh. It seems then that I misunderstood the question - should I delete this? You may want to clarify the question, currently it sounds like (1) is somehow incorrect (instead of perhaps not useful) Sep 14 '16 at 17:47
• Please keep this answer, which is valuable. My mistake that I was't clear enough in my original post. I tried to clarify my question thanks to your comments, and in a way that still makes this answer meaningful. Sep 14 '16 at 18:10