Dynamic programming for multiple changepoints?

Modeling
1

I’ve been playing with the changepoint model from the user guide, and taking advantage of the clever dynamic programming speedup there (and blogged about here). What I can’t really claim, though, is that I quite understand exactly what’s going on.

Reproducing the code here:

transformed parameters {
vector[T+1] lp_e;
vector[T+1] lp_l;
vector[T] lp;

lp_e[1] <- 0;
lp_l[1] <- 0;
for (t in 1:T) {
    lp_e[t + 1] <- lp_e[t] + poisson_log(D[t], e);
    lp_l[t + 1] <- lp_l[t] + poisson_log(D[t], l);
}

lp <- rep_vector(log_unif + lp_l[T + 1], T) + head(lp_e, T) - head(lp_l, T);
}

My interest is in whether this can feasibly be generalised to multiple changepoints. I’ve spent an afternoon banging my head against it, but I clearly don’t understand the final summation step. Based on @Bob_Carpenter’s insight about the forward-backward algorithm I’ve gone down that particular rabbit-hole, but the logical leap to multiple changepoints is still beyond me.

Any pointers greatly appreciated!

1 Like
2

I had the same thought a while back but couldn’t work out how to do it. My gut feeling at the time is that it wasn’t possible because more than one point will break the symmetry but I don’t actually know; so I’m also pretty interested to see if there’s a general solution.

3

I’m currently trying to make the slow, easier to understand approach without dynamic programming work. Once I’ve got that working, I’m hoping things might seem a little clearer.

2 Likes