18
$\begingroup$

Here is my old question

I would like to ask if someone knows the difference (if there is any difference) between Hidden Markov models (HMM) and Particle Filter (PF), and as a consequence Kalman Filter, or under which circumstances we use which algorithm. I’m a student and I have to do a project, but first I have to understand some things.

So, according to bibliography, both are State Space Models, including hidden (or latent or unobserved) states. According to Wikipedia (Hidden_Markov_model)in HMM, the state space of the hidden variables is discrete, while the observations themselves can either be discrete (typically generated from a categorical distribution) or continuous (typically from a Gaussian distribution). Hidden Markov models can also be generalized to allow continuous state spaces. Examples of such models are those where the Markov process over hidden variables is a linear dynamical system, with a linear relationship among related variables and where all hidden and observed variables follow a Gaussian distribution. In simple cases, such as the linear dynamical system just mentioned, exact inference is tractable (in this case, using the Kalman filter); however, in general, exact inference in HMMs with continuous latent variables is infeasible, and approximate methods must be used, such as the extended Kalman filter or the particle filter.

But for me this is a bit confusing… In simple words does this mean the follow (based also to more research that I have done):

  • In HMM, the state space can be either discrete or continuous. Also the observations themselves can be either discrete or continuous. Also HMM is a linear and Gaussian or non-Gaussian dynamical system.
  • In PF, the state space can be either discrete or continuous. Also the observations themselves can be either discrete or continuous. But PF is a non-linear (and non-Gaussian?) dynamical system (is that their difference?).
  • Kalman filter (also looks like the same to me like HMM) is being used when we have linear and Gaussian dynamical system.

Also how do I know which algorithm to choose, because to me all these seem the same... Also I found a paper (not in English) which says that PF although can have linear data (for example raw data from a sensor-kinect which recognizes a movement), the dynamical system can be non-linear. Can this happen? Is this correct? How?

For gesture recognition, researchers can use either HMM or PF, but they don’t explain why they select each algorithm… Does anyone know how I can be helped to distinguish these algorithms, to understand their differences and how to choose the best algorithm?

I’m sorry if my question is too big, or some parts are naive but I didn’t find somewhere a convincing and scientific answer. Thank you a lot in advance for your time!

Here is my NEW question (according to @conjugateprior's help)

So with further reading, I would like to update some of my parts of my previous comment, and to make sure that I understood a bit more what is going on.

  • Again in simple words, the umbrella is Dynamic Bayesian networks under which the models of HMM and State space are included (subclasses) (http://mlg.eng.cam.ac.uk/zoubin/papers/ijprai.pdf).
  • Furthermore, the initial difference between the 2 models is that, in HMM the hidden state variables are discrete, while the observations can either be discrete or continuous. In PF the hidden state variables are continuous (real-valued hidden state vector), and the observations have Gaussian distributions.
  • Also according to @conjugateprior each model has the 3 following tasks: filtering, smoothing and prediction. In filtering, the model HMM uses for discrete hidden state variables the method Forward algorithm, state space uses for continuous variables and linear dynamic system the Kalman Filter, etc.
  • However, HMM can also be generalized to allow continuous state spaces.
  • With these extensions of HMM, the 2 models seems to be conceptually identical (as it is also mentioned in Hidden Markov Model vs Markov Transition Model vs State-Space Model...?).

I think that I’m using a bit more accurate the terminology, but still everything is blurry to me. Can anyone explain to me what is the difference between HMM and State Space model?

Because I really cannot find an answer that can fit to my needs..

Thank you once more!

$\endgroup$
  • 1
    $\begingroup$ If your school's library has this book: crcpress.com/Time-Series-Modeling-Computation-and-Inference/… I would take a look at it. It does a good job of explaining all three topics which, I might mention, are three very distinct topics. $\endgroup$ – user95564 Nov 23 '15 at 11:40
  • $\begingroup$ I just checked that library doesn't have this book, unfortunately.. so if you could send me the parts that you believe that answer my question or help me to also distinct these topics it would be great! : ) $\endgroup$ – user5584748 Nov 23 '15 at 12:11
15
$\begingroup$

It will be helpful to distinguish the model from inference you want to make with it, because now standard terminology mixes the two.

The model is the part where you specify the nature of: the hidden space (discrete or continuous), the hidden state dynamics (linear or non-linear) the nature of the observations (typically conditionally multinomial or Normal), and the measurement model connecting the hidden state to the observations. HMMs and state space models are two such sets of model specifications.

For any such model there are three standard tasks: filtering, smoothing, and prediction. Any time series text (or indeed google) should give you an idea of what they are. Your question is about filtering, which is a way to get a) a posterior distribution over (or 'best' estimate of, for some sense of best, if you're not feeling Bayesian) the hidden state at $t$ given the complete set of of data up to and including time $t$, and relatedly b) the probability of the data under the model.

In situations where the state is continuous, the state dynamics and measurement linear and all noise is Normal, a Kalman Filter will do that job efficiently. Its analogue when the state is discrete is the Forward Algorithm. In the case where there is non-Normality and/or non-linearity, we fall back to approximate filters. There are deterministic approximations, e.g. an Extended or Unscented Kalman Filters, and there are stochastic approximations, the best known of which being the Particle Filter.

The general feeling seems to be that in the presence of unavoidable non-linearity in the state or measurement parts or non-Normality in the observations (the common problem situations), one tries to get away with the cheapest approximation possible. So, EKF then UKF then PF.

The literature on the Unscented Kalman filter usually has some comparisons of situations when it might work better than the traditional linearization of the Extended Kalman Filter.

The Particle Filter has almost complete generality - any non-linearity, any distributions - but it has in my experience required quite careful tuning and is generally much more unwieldy than the others. In many situations however, it's the only option.

As for further reading: I like ch.4-7 of Särkkä's Bayesian Filtering and Smoothing, though it's quite terse. The author makes has an online copy available for personal use. Otherwise, most state space time series books will cover this material. For Particle Filtering, there's a Doucet et al. volume on the topic, but I guess it's quite old now. Perhaps others will point out a newer reference.

$\endgroup$
  • $\begingroup$ First of all thank you very much for your answer. Please check that I edited the question above in order to be more coherent and accurate with the terminology. I also rephrase my whole question. $\endgroup$ – user5584748 Nov 24 '15 at 12:04
  • $\begingroup$ In your rewrite it's not quite true that "In PF the hidden state variables are continuous (real-valued hidden state vector), and the observations have Gaussian distributions." PF is a filter. The model for which it is a filter must have a continuous state space (with some Markovian structure or other) but is otherwise unconstrained: any distributions, any dynamics, and any measurement process. $\endgroup$ – conjugateprior Nov 25 '15 at 14:06
  • $\begingroup$ You could, for example, use a PF to filter an ordinary linear Gaussian state space model. It would work just fine. You just don't have to since the Kalman filter is exact. $\endgroup$ – conjugateprior Nov 25 '15 at 14:07
  • 4
    $\begingroup$ "What is the difference between HMM and State Space model?" Basically: By convention, HMMs have discrete state. Also by convention, 'state space models' denote things with continuous state. $\endgroup$ – conjugateprior Nov 25 '15 at 14:10
  • $\begingroup$ Thank you so much! So this difference is happened by convention (and according to bibliography). But in general, we can choose whichever model we want. Is that correct? The model that I'll choose depends on whether will I have better results? $\endgroup$ – user5584748 Nov 26 '15 at 7:29

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.