K-Nearest Neighbor Particle Filters for Dynamic Hybrid Bayesian Networks

In state estimation of dynamic systems, Kalman filters and HMM filters have been applied to linear-Gaussian models and models with finite state spaces. However, they do not work well in most practical problems with nonlinear and non-Gaussian models. Even when the state space is finite, the dynamic Bayesian networks describing the HMM model could be too complicated to manage. Sequential Monte Carlo methods, also known as particle filters (PFs), have been introduced to deal with these real-world problems. They allow us to treat any type of probability distribution, nonlinearity and nonstationarity although they usually suffer major drawbacks of sample degeneracy and inefficiency in high-dimensional cases. We show how we can exploit the structure of partially dynamic hybrid Bayesian networks (PD-HBN) to reduce ``sample depletion' and increase the efficiency of particle filtering by combining the well-known K-nearest neighbor (KNN) majority voting strategy and the concept of evolution algorithm. Essentially, the novel method resamples the dynamic variables and randomly combines them with the existing samples of static variables to produce new particles. As new observations become available, the algorithm allows the particles to incorporate the latest information so that the fittest particles associated with a proposed objective rule will be kept for resampling. We also conduct a theoretical analysis on the proposed KNN-PF algorithm, and demonstrate the accuracy of the performance prediction with extensive simulations. Performance analysis and numerical results show that this new approach has a superior estimation/classification performance compared to other related algorithms.