I was wondering if anyone has any good suggestions for solving the filtering problem when you have a hidden Markov model where the hidden chain x_k has a very large state space? By very large I mean that the exact solution (http://en.wikipedia.org/wiki/Forward_algorithm) becomes too computationally demanding.
My application is basically a discrete spatio-temporal model where for each time instance the transition probability is a Markov random field with nearest neighbour interaction.
hello, maybe this should shine some light
http://en.wikipedia.org/wiki/Particle_filter
Hi Tayelolu,
Thanks, I am aware of the particle filter which works in principle. However, it is known to perform quite poor for high dimensions.
Hello. You seem to have hit upon a hard problem. If you cannot aggregate the HMM to a smaller number of states or use a coarser discretisation, you may be able to factorise the optimisation computations. This can be done where there is no interaction between the optimisation variables in essentially the same way that leads to the Viterbi algorithm. Some of the references in the report below deal with this but not in the context of MRFs. If this is transformable to a standard HMM it may help.
PS I agree wih the comment about particle filters. They are not much use in high dimensional spaces from what I have seen.
Article A Survey of Hidden Markov Model Tracking with Emphasis on OTHR
Greeting from Newcastle!
I understand that the particle filter had been known to perform poorly in high dimension. However, I think we now have enough ingredient to enhance its capacity significantly.
Christian mentioned that his state space has a discrete nature, which is something I have not been working on. However, I presume that we can turn a discrete distribution into an equivalent stepwise density function to see if the continuous algorithms could be applied? If yes, then we continue as follows.
The traditional ingredients for particle filter has been important sampling and resampling (SIR) and possibly some ad hoc post-mixing strategy. Now if we add two new ingredients: slice sampling and simulated annealing in between then I think we have something far more robust than what we have seen before.
If you could point me to a concrete example, I would love to see if I can provide some simulation, assuming that we can convert the problem into one which has a continuous and well connected support set (multimodality is permissible)
The original question is about discrete state spaces with a very large number of states, not continuous spaces. Perhaps it would be better to start another thread that deals with the performance of particle filters in high dimensional continuous state spaces, as this thread relates to HMMs.
Hi everyone, back from Easter break. Thanks for all the answers, I'll review them more carefully and make a more detailed answer later.
To give some context to the problem I am trying to solve we have recently proposed a new particle filter/sequential Monte Carlo framework that does seem to work for quite a bit higher dimension than standard PFs. I have attached our arXived paper on the matter, the type of problems I am looking to find something to compare our method with is in Section 6.3. In this filtering problem we are looking at a structured state space where at each time step we would have to sum over 2^600 or 2^1056 different values using brute force.
- Badges
- Science topic
- Similar topics
- Medicine
- Physiology
- Biosignals
- Biomedical Signal Processing
- Statistical Learning