Filtres à particules: comment rééchantillonner?

Je comprends le principe de base d'un filtre à particules et j'ai essayé de l'implémenter. Cependant, je me suis accroché à la partie de rééchantillonnage.

Théoriquement parlant, c'est assez simple: à partir de l'ancien ensemble de particules (et pondéré), dessinez un nouvel ensemble de particules avec remplacement. Ce faisant, privilégiez les particules de poids élevé. Les particules de poids élevé sont attirées plus souvent et les particules de faible poids moins souvent. Peut-être une seule fois ou pas du tout. Après le rééchantillonnage, tous les poids reçoivent le même poids.

Ma première idée sur la façon de mettre en œuvre cela était essentiellement la suivante:

1. Normaliser les poids
2. Multipliez chaque poids par le nombre total de particules
3. Arrondissez ces pondérations à l'entier le plus proche (par exemple avec int()en Python)

Maintenant, je devrais savoir à quelle fréquence dessiner chaque particule, mais en raison des erreurs d'arrondi, je finis par avoir moins de particules qu'avant l'étape de rééchantillonnage.

La question: comment «remplir» les particules manquantes afin d'obtenir le même nombre de particules qu'avant l'étape de rééchantillonnage? Ou, au cas où je ne serais pas complètement sur la bonne voie ici, comment puis-je rééchantillonner correctement?

Le problème que vous rencontrez est souvent appelé exemple d'appauvrissement. Nous pouvons voir pourquoi votre approche en souffre avec un exemple assez simple. Disons que vous avez 3 particules et que leur poids normalisé est 0,1, 0,1, 0,8. Ensuite, multiplier par chaque poids par les 3 donne 0,3, 0,3 et 2,4. L'arrondi donne alors 0, 0, 2. Cela signifie que vous ne choisiriez pas les deux premières particules et que la dernière serait choisie deux fois. Vous en êtes maintenant à deux particules. Je soupçonne que c'est ce que vous avez vu lorsque vous dites "en raison des erreurs d'arrondi, je finis par avoir moins de particules".

Une autre méthode de sélection serait la suivante.

1. Normaliser les poids.
2. Calculez un tableau de la somme cumulée des poids.
3. Générez aléatoirement un nombre et déterminez quelle plage dans ce tableau de poids cumulatif auquel le nombre appartient.
4. L'indice de cette plage correspondrait à la particule à créer.
5. Répétez jusqu'à ce que vous ayez le nombre d'échantillons souhaité.

Donc, en utilisant l'exemple ci-dessus, nous commencerions par les poids normalisés. Nous calculerions alors le tableau [0,1, 0,2, 1]. De là, nous calculons 3 nombres aléatoires, soit 0,15, 0,38 et 0,54. Cela nous obligerait à choisir la deuxième particule une fois et la troisième particule deux fois. Le fait est que cela donne aux petites particules une chance de se propager.

Une chose à noter est que, bien que cette méthode traite de l'appauvrissement, elle peut conduire à des solutions sous-optimales. Par exemple, il se peut qu'aucune des particules ne corresponde vraiment bien à votre emplacement donné (en supposant que vous l'utilisez pour la localisation). Les poids ne vous indiquent que les particules qui correspondent le mieux, pas la qualité de la correspondance. En tant que tel, lorsque vous effectuez des lectures supplémentaires et répétez le processus, vous pouvez constater que toutes vos particules se regroupent en un seul emplacement qui n'est pas l'emplacement correct. C'est généralement parce qu'il n'y avait pas de bonnes particules pour commencer.

Comme je suppose que vous l'avez découvert vous-même, la méthode de rééchantillonnage que vous proposez est légèrement défectueuse, car elle ne devrait pas modifier le nombre de particules (sauf si vous le souhaitez). Le principe est que le poids représente la probabilité relative par rapport aux autres particules. Dans l'étape de rééchantillonnage, vous dessinez à partir de l'ensemble de particules de telle sorte que pour chaque particule, le poids normalisé multiplié par le nombre de particules représente le nombre de fois où cette particule est dessinée en moyenne. En ce que votre idée est correcte. Ce n'est qu'en utilisant l'arrondi au lieu de l'échantillonnage que vous éliminerez toujours les particules dont la valeur attendue est inférieure à la moitié.

Il existe plusieurs façons d'effectuer correctement le rééchantillonnage. Il y a un bon article intitulé On resampling algorithms for particules filters , compare the different methods. Juste pour donner un bref aperçu:

• Rééchantillonnage multinomial: imaginez une bande de papier où chaque particule a une section, où la longueur est proportionnelle à son poids. Choisissez au hasard un emplacement sur la bande N fois et choisissez la particule associée à la section.

• Rééchantillonnage résiduel: cette approche tente de réduire la variance de l'échantillonnage, en allouant d'abord à chaque particule leur plancher entier de la valeur attendue, et en laissant le reste au rééchantillonnage multinomial. Par exemple, une particule avec une valeur attendue de 2,5 aura 2 copies dans l'ensemble rééchantillonné et une autre avec une valeur attendue de 0,5.

• Rééchantillonnage systématique: prenez une règle avec des marques régulièrement espacées, de sorte que N marques soient de la même longueur que votre bande de papier. Placez au hasard la règle à côté de votre bande. Prenez les particules aux marques.

• Rééchantillonnage stratifié: identique au rééchantillonnage systématique, sauf que les repères sur la règle ne sont pas placés uniformément, mais ajoutés en tant que N processus aléatoires d'échantillonnage à partir de l'intervalle 0..1 / N.

Donc pour répondre à votre question: ce que vous avez mis en place pourrait être étendu à une forme d'échantillonnage résiduel. Vous remplissez les emplacements manquants par échantillonnage basé sur une distribution multinoniale des rappels.

Pour un exemple de code python qui implémente correctement le rééchantillonnage, vous pourriez trouver ce projet github utile: https://github.com/mjl/particle_filter_demo

De plus, il est livré avec sa propre représentation visuelle du processus de rééchantillonnage, qui devrait vous aider à déboguer votre propre implémentation.

Dans cette visualisation, la tortue verte montre la position réelle, le gros point gris montre la position estimée et devient vert quand il converge. Le poids passe de probable (rouge) à peu probable (bleu).

une façon simple de le faire est numpy.random.choice (N, N, p = w, replace = True) où N est le non. de particules et w = poids normalisés.

J'utilise l'approche de @ narayan pour implémenter mon filtre à particules:

new_sample = numpy.random.choice(a=particles, size=number_of_particles, replace=True, p=importance_weights)

a est le vecteur de vos particules à échantillonner, la taille est le nombre de particules et p est le vecteur de leurs poids normalisés. replace = True gère l'échantillonnage bootstrap avec remplacement. La valeur de retour est un vecteur de nouveaux objets particules.