$k$-means: Fighting against Degeneracy in Sequential Monte Carlo with an Application to Tracking
For regular particle filter algorithm or Sequential Monte Carlo (SMC) methods, the initial weights are traditionally dependent on the proposed distribution, the posterior distribution at the current timestamp in the sampled sequence, and the target is the posterior distribution of the previous timestamp. This is technically correct, but leads to algorithms which usually have practical issues with degeneracy, where all particles eventually collapse onto a single particle. In this paper, we propose and evaluate using $k$ means clustering to attack and even take advantage of this degeneracy. Specifically, we propose a Stochastic SMC algorithm which initializes the set of $k$ means, providing the initial centers chosen from the collapsed particles. To fight against degeneracy, we adjust the regular SMC weights, mediated by cluster proportions, and then correct them to retain the same expectation as before. We experimentally demonstrate that our approach has better performance than vanilla algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Twice Sequential Monte Carlo for Tree Search
Model-based reinforcement learning (RL) methods that leverage search are responsible for many milestone breakthroughs in RL. Sequential Monte Carlo (SMC) recently emerged as an alternative to the Monte Carlo Tree Search …
Reinforcement LearningFighting Sample Degeneracy and Impoverishment in Particle Filters: A Review of Intelligent Approaches
During the last two decades there has been a growing interest in Particle Filtering (PF). However, PF suffers from two long-standing problems that are referred to as sample degeneracy and impoverishment. We are investiga…
ClusteringDiscrete Diffusion Inference-Time Control with Nested Sequential Monte Carlo
We study inference-time control for text generation in discrete diffusion language models, where the goal is to steer sampling toward sequence-level rewards without retraining. Prior work in this domain has focused on pa…
Text GenerationDareFightingICE Competition: A Fighting Game Sound Design and AI Competition
This paper presents a new competition -- at the 2022 IEEE Conference on Games (CoG) -- called DareFightingICE Competition. The competition has two tracks: a sound design track and an AI track. The game platform for this …
Introduction to Behavior Algorithms for Fighting Games
The quality of opponent Artificial Intelligence (AI) in fighting videogames is crucial. Some other game genres can rely on their story or visuals, but fighting games are all about the adversarial experience. In this pape…