Les filtres particulaires, également connus sous le nom de méthodes séquentielles de Monte-Carlo, sont un ensemble d'algorithmes utilisés pour trouver des solutions approximatives aux problèmes de filtrage pour des systèmes non linéaires à espace d'état. Ces techniques sont appliquées dans des domaines tels que le traitement du signal et l'inférence statistique bayésienne. Le problème du filtrage consiste à estimer les états internes d'un système dynamique lorsque seules des observations partielles sont disponibles et que des perturbations aléatoires affectent à la fois les capteurs et le système lui-même. L'objectif principal est de calculer la distribution a posteriori des états d'un processus de Markov, étant donné des observations bruitées et partielles.
Le terme « filtre particulaire » a été inventé pour la première fois en 1996 par Pierre Del Moral, en référence aux méthodes de particules en interaction de type champ moyen utilisées en mécanique des fluides depuis le début des années 1960. Le terme « Monte-Carlo séquentiel » a été inventé séparément par Jun S. Liu et Rong Chen en 1998. Le filtrage particulaire utilise un ensemble de particules, ou échantillons, pour représenter la distribution a posteriori d'un processus stochastique. Le modèle d'espace d'état peut être non linéaire, et l'état initial ainsi que les distributions de bruit peuvent prendre n'importe quelle forme. Cette approche fournit une méthodologie bien établie pour générer des échantillons à partir d'une distribution cible sans imposer de restrictions sur le modèle ou les distributions.
Méthodologie de base
Les filtres particulaires mettent à jour leur prédiction de manière approximative et statistique. Chaque particule porte un poids de vraisemblance représentant sa probabilité d'être tirée de la fonction de densité de probabilité sous-jacente de l'état du système. Un défi courant est l'effondrement des poids, où quelques particules dominent la distribution. Ce problème est atténué par une étape de rééchantillonnage qui remplace les particules à poids négligeables par de nouvelles particules proches de celles ayant des poids plus élevés, souvent déclenchée par des critères adaptatifs tels que la variance des poids ou l'entropie relative.
Contexte historique
Le fondement mathématique des filtres particulaires repose sur l'interprétation du filtrage comme des modèles de chemins de Feynman-Kac. Ces techniques ont été développées en chimie moléculaire et en physique computationnelle, avec des contributions précoces de Theodore E. Harris, Marshall N. Rosenbluth et Arianna W. Rosenbluth. En physique computationnelle, ces méthodes sont également utilisées dans le Monte-Carlo quantique, en particulier les méthodes de diffusion Monte-Carlo. Les méthodes de particules en interaction de type Feynman-Kac sont étroitement liées aux algorithmes génétiques utilisés en calcul évolutionnaire.
Motivation
Le problème du filtrage consiste à estimer les états internes d'un système dynamique lorsque les observations sont partielles et corrompues par le bruit, à la fois dans les capteurs et dans la dynamique du système. L'objectif est de calculer la distribution a posteriori de l'état étant donné les observations, ce qui nécessite une estimation bayésienne récursive. Pour les modèles linéaires et gaussiens, le filtre de Kalman fournit une solution exacte. Cependant, pour de nombreux systèmes réels, les modèles de dynamique et d'observation sont non linéaires ou non gaussiens.
En 1984, Mireille Chaleyat-Maurel et Dominique Michel ont prouvé que, sauf pour certaines classes spécifiques telles que les modèles linéaires-gaussiens ou certaines familles plus larges, la séquence des distributions a posteriori n'admet pas de récursion de dimension finie. Ce résultat implique que des solutions exactes sont généralement indisponibles et que des méthodes numériques approximatives sont nécessaires. Les approches traditionnelles, y compris les approximations par grille, le Monte-Carlo par chaîne de Markov, les filtres de Kalman étendus ou les modèles linéarisés, rencontrent souvent des difficultés avec les systèmes à grande échelle, les processus instables ou les dynamiques fortement non linéaires.
Algorithme et rééchantillonnage
Un filtre particulaire maintient un ensemble de particules, chacune représentant un état possible, avec un poids proportionnel à la vraisemblance de cet état étant donné les observations. L'algorithme procède de manière itérative : prédiction, où les particules évoluent selon la dynamique du système ; mise à jour, où les poids sont ajustés en fonction des nouvelles observations ; et rééchantillonnage, qui remplace les particules à faible poids par des copies de particules à poids élevé pour éviter l'effondrement des poids.
L'effondrement des poids se produit lorsque quelques particules accumulent la majeure partie de la masse de probabilité, conduisant à une représentation dégénérée. Pour atténuer ce problème, le rééchantillonnage est effectué lorsque la variance des poids ou l'entropie relative de la distribution des poids dépasse un seuil. Pendant le rééchantillonnage, les particules à poids négligeable sont écartées et de nouvelles particules sont générées autour de celles ayant des poids plus élevés. Cette étape introduit une certaine approximation mais est essentielle pour maintenir la diversité et la précision au fil du temps.
Fondements théoriques
D'un point de vue statistique, les filtres particulaires peuvent être interprétés comme des interprétations de particules en interaction de type champ moyen des mesures de probabilité de Feynman-Kac. Ces techniques sont originaires de la chimie moléculaire et de la physique. Les contributions précoces incluent les travaux de Theodore E. Harris et Herman Kahn en 1951, et les Rosenbluth en 1955, qui ont utilisé ces méthodes dans les simulations de Monte-Carlo quantique. En 1948, Enrico Fermi et Robert Richtmyer ont développé une interprétation de particules en interaction de type champ moyen pertinente pour ces méthodes. Des algorithmes de type génétique ont également été explorés par Alan Turing en 1950 et 1954, et par Nils Aall Barricelli à l'Institute for Advanced Study de Princeton au début des années 1950. La méthode « Poor Man's Monte Carlo » proposée par John Hammersley en 1954 contenait également des précurseurs des idées modernes de filtrage particulaire.
Applications
Les filtres particulaires sont largement utilisés dans des domaines tels que l'intelligence artificielle, le traitement du signal et l'inférence statistique bayésienne. Ils sont particulièrement adaptés à l'estimation d'états dans des modèles de Markov cachés où la dynamique sous-jacente et les distributions de bruit sont non gaussiennes. Les applications courantes incluent le suivi de cibles, la localisation de robots et l'analyse des risques financiers. Dans l'apprentissage automatique, les méthodes particulaires apparaissent dans l'analyse de données séquentielles et l'échantillonnage d'événements rares.
En physique computationnelle et en chimie moléculaire, ces techniques sont appliquées au Monte-Carlo quantique et à des problèmes connexes. En biologie, elles modélisent la dynamique des populations et l'évolution génétique. Les méthodes trouvent également des applications en phylogénie, en pharmacocinétique et en évaluation quantitative des risques.
Relations avec d'autres méthodes
Les filtres particulaires diffèrent des techniques traditionnelles comme le filtre de Kalman étendu, qui linéarise la dynamique non linéaire, ou le filtre de Kalman sans parfum, qui approxime les distributions via des points sigma. Alors que ces méthodes reposent sur des hypothèses gaussiennes, les filtres particulaires ne font pas de telles restrictions. Cependant, ils performent mal dans les systèmes à très haute dimension, où le nombre de particules nécessaires croît de manière exponentielle avec la dimension, un phénomène parfois appelé malédiction de la dimensionnalité. Des variantes telles que le filtre particulaire auxiliaire et le filtre particulaire de Rao-Blackwellisé ont été développées pour remédier à ces limitations dans des applications spécifiques.
Développements et limites
Les fondements théoriques des filtres particulaires remontent aux méthodes de particules en interaction de type champ moyen développées en physique et en chimie durant les années 1950, y compris les travaux précoces d'Alan Turing sur les machines d'apprentissage de type génétique et les contributions de Nils Aall Barricelli. La méthode « Poor Man's Monte Carlo » proposée par John Hammersley et ses collègues en 1954 contenait des éléments des filtres particulaires modernes. En physique computationnelle, le Monte-Carlo quantique et les méthodes de diffusion Monte-Carlo, développées à partir des travaux de 1948 d'Enrico Fermi et Robert Richtmyer, reposent également sur des approximations de particules en interaction de type Feynman-Kac.
Les chercheurs en calcul évolutionnaire, notamment John Holland au début des années 1970, ont développé des algorithmes génétiques similaires de manière indépendante comme outil heuristique. En statistique, le premier filtre particulaire formel a été introduit en 1993 par Neil Gordon, David Salmond et Adrian Smith, connu sous le nom de filtre bootstrap. Des améliorations significatives ont suivi, notamment le filtre particulaire auxiliaire par Michael Pitt et Neil Shephard en 1999, et le filtre particulaire de Rao-Blackwellisé, qui marginalise certaines sous-structures linéaires pour réduire la variance. Ces méthodes restent une pierre angulaire de l'inférence bayésienne séquentielle moderne.
Applications
La méthodologie trouve des applications dans de nombreux domaines. Dans le traitement du signal et de l'image, les filtres particulaires suivent des objets dans des séquences vidéo. En ingénierie et en robotique, ils soutiennent la localisation et la cartographie simultanées (SLAM) pour des systèmes comme les véhicules autonomes. En bioinformatique, ils sont appliqués à l'inférence phylogénétique et à l'analyse de l'expression génique. L'économie et la finance les utilisent pour l'estimation d'état dans des modèles de volatilité stochastique. L'évaluation quantitative des risques et l'échantillonnage d'événements rares bénéficient également de ces techniques. Bien que les problèmes à haute dimension restent difficiles, les filtres particulaires continuent d'être un outil flexible et largement utilisé pour l'estimation d'état non linéaire et non gaussienne.
Voir aussi
- apprentissage automatique pour un contexte plus large sur les algorithmes d'apprentissage
- intelligence artificielle pour les applications connexes
Références
Les sources primaires incluent les travaux de Pierre Del Moral sur les méthodes de particules en interaction de type champ moyen et les fondements mathématiques établis par Chaleyat-Maurel et Michel en 1984. Des enquêtes pratiques sont disponibles dans la littérature sur le calcul statistique.