9
$\begingroup$

I am reading the Bayesian online changepoint detection paper by Adams and MacKay (link).

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lacerbi Sep 14 '16 at 4:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Juho Kokkala Sep 14 '16 at 17:50
  • $\begingroup$ @JuhoKokkala: I am glad I am not the only one with that feeling... $\endgroup$ – lacerbi Sep 14 '16 at 17:59
  • 1
    $\begingroup$ @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. $\endgroup$ – gwg Jul 31 at 14:19
5
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ (+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. $\endgroup$ – lacerbi Sep 14 '16 at 17:09
  • 1
    $\begingroup$ 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) $\endgroup$ – Juho Kokkala Sep 14 '16 at 17:47
  • $\begingroup$ 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. $\endgroup$ – lacerbi Sep 14 '16 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.