search

jrnold / ssmodels-in-stan

State space models (dynamic linear models, hidden Markov models) implemented in Stan.
https://jrnold.github.io/ssmodels-in-stan/
BSD 3-Clause "New" or "Revised" License
47 stars 16 forks source link

Issue with Algorithmic Speed #31

Open jsilve24 opened 7 years ago

jsilve24 commented 7 years ago

First off, thank you for all the hard work you have done in developing this package for R/stan. I am very excited to get to use it but I am having some trouble with computational speed. I wonder if I am doing something wrong?

Basically I am trying to develop a Multinomial-Logistic Normal Dynamic Linear Model. I have coded a basic local-level model in two ways: (1) Naively in Stan, without using any Kalman Filtering / smoothing (2) Using the StanStateSpace library you have developed.

My naive thought is that Kalman filter / smoothing should greatly improve efficiency as the closed-form updates reduce the burden on Stan's MCMC engine.

What I am finding is that both (1) and (2) handle a simulated 3-variate multinomial time-series (with 100 samples) just fine. That is both speed and accuracy are acceptable.

However, when I scale up to a 31-variate multinomial time-series with ~120 samples (and 4 missing samples), the sampler can't even make it to 10 warmup samples within 10 minutes.

I have included the following files to recreate my workflow.

I am not sure what is going on, whether it is inefficient filtering or whether the model is having trouble converging. Perhaps I am not using the code in the correct way?

Thank you very much for your advice! Justin Silverman

local_level.zip

jrnold commented 7 years ago

My guess would be that the problem is in the Kalman filter multivariate series it is multiplying the 31 dim matrices, and not accounting for the sparsity (are they all local level models?).

But I'm not really sure. The code on this repo isn't release ready, and there could be any number of issues with it. I've been working on other projects for a while, and need some time to turn back to it to do proper testing on it. I don't recommend using the code unless you are planning on digging into the source.

If you are able to figure it out, I'd be interested to know what was going on, but I don't have time to work on this project at the moment.

jsilve24 commented 7 years ago

I am interested in working on this. Do you have any ideas regarding how to handle sparsity in the filter? Yes they are all local level models.

On Mar 7, 2017, at 5:43 PM, Jeffrey Arnold notifications@github.com wrote:

My guess would be that the problem is in the Kalman filter multivariate series it is multiplying the 31 dim matrices, and not accounting for the sparsity (are they all local level models?).

But I'm not really sure. The code on this repo isn't release ready, and there could be any number of issues with it. I've been working on other projects for a while, and need some time to turn back to it to do proper testing on it. I don't recommend using the code unless you are planning on digging into the source.

If you are able to figure it out, I'd be interested to know what was going on, but I don't have time to work on this project at the moment.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/jrnold/ssmodels-in-stan/issues/31#issuecomment-284884885, or mute the thread https://github.com/notifications/unsubscribe-auth/AAbnRglCwbHGwX9GAf3H5BKmTeD5Jezbks5rjd2dgaJpZM4MWCMB.

jrnold commented 7 years ago

that's a good question. I'm not sure, I first wanted to make sure I got the Kalman filter code right in the general case, and then figure out how to speed up some special cases (local level, time invariant system matrices). This could include: (1) coding them as separate functions; (2) using sparse matrices for the system matrices (Ch 42 of the User's Guide); or (3) code generation. It's also quite possible that there's something wrong in the current code, or there's a matrix operation or two that's slowing down everything and could be adjusted. Or maybe there is no value added of using the Kalman filter with Stan ... and the autodiff is basically doing as well.

What may really the the solution is to implement in C++ where we can avoid building up the auto-diff structure while running the filter/smoother, and analytically calculate the derivatives.