Expanding change point model in section 11.2 of the manual

[Marty]

Hi, 

Figure 11.1 (pg. 99) in the manual for v2.5 gives the code for a change point model where at time s the Poisson rate parameter changes from the "early rate" e to the "late rate" l . I’m wondering what the best way is to code an extension of this model to allow for multiple change points. For example, suppose that there is also a rate for a middle period m, which would entail two change points s1 and s2 separating the three periods e, m and l. I can't figure out a good way to expand the code given on pg. 99 to appropriately marginalize out both of the change points. Thanks in advance for any advice. 

[Bob Carpenter]

Where you have the single loop in s for the changepoint, you
need to instead keep pairs. Easiest way to do it would be
in a matrix:

matrix[T,T] lp;
lp <- rep_matrix(log_unif,T);
for (s1 in 1:T)
for (s2 in 1:T)
for (t in 1:T)
lp[s1,s2] <- lp[s1,s2]
+ poisson_log(D[t], if_else(t < s1,
e, if_else(t < s2, m, l)));

and then in the model needs to be changed to convert the
matrix lp to a vector so it can be passed to log_sum_exp:

increment_log_prob(log_sum_exp(to_vector(lp)));

The problem is that as there are more change points, the
computational complexity grows. You can see it intuitively
from the loops.

Suppose there are N items. With a single change point, you
need to consider all N positions. Each position requires
an amount N of work, so overall complexity is O(N^2).

With two change points you need to consider all (N choose 2)
change points. That's a quadratic number of pairs, each
requiring an amount N of work, so overall complexity is O(N^3).

- Bob

P.S. I'll add the discussion to the next manual. This is a case
where something like Metropolis or Gibbs has a big computational
advantage in terms of iteration time, but this method should produce
better mixing and also let you estimate all the tails that would never
be visited by Gibbs or Metropolis.

On Oct 25, 2014, at 12:18 AM, Marty <marty....@gmail.com> wrote:

> Hi,
>
>
>
> Figure 11.1 (pg. 99) in the manual for v2.5 gives the code for a change point model where at time s the Poisson rate parameter changes from the "early rate" e to the "late rate" l . I’m wondering what the best way is to code an extension of this model to allow for multiple change points. For example, suppose that there is also a rate for a middle period m, which would entail two change points s1 and s2 separating the three periods e, m and l. I can't figure out a good way to expand the code given on pg. 99 to appropriately marginalize out both of the change points. Thanks in advance for any advice.
>
>

> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Marty]

Thanks for the clear explanation, Bob. Much appreciated.