Ouverture 1 :
Modèles de chaînes de Markov cachées pour l’analyse de traces sur Internet- Sandrine Vaton (IMT Atlantique)
Les modèles de Markov cachés (hidden Markov models, HMMs) sont des processus aléatoires ayant de nombreuses applications (traitement automatique du langage naturel, reconnaissance des formes, intelligence artificielle…). Les HMMs sont des versions « bruitées » de chaînes de Markov, dans lesquels l’observation dépend aléatoirement d’un état markovien qui n’est pas observé directement.
Dans le domaine de l’analyse de traces informatiques et réseaux, ces modèles sont parfois utilisés pour caractériser la charge de trafic (modèles On/Off, processus de Poisson modulés Markov…), en détection des intrusions ou encore en modélisation des performances de réseau (délais, pertes de paquets…).
Quand on utilise des modèles de Markov cachés différents problèmes se posent, en particulier l’inférence des états cachés et l’estimation des paramètres du modèle statistique au vu des données de mesure. Nous rappellerons comment ces problèmes d’apprentissage statistique sont classiquement résolus à l’aide des algorithmes de Viterbi, du Maximum A Posteriori, ou encore de l’algorithme Expectation Maximization (EM).
Cependant les modèles de Markov cachés standards ont un certain nombre de limitations, qui restreignent leur applicabilité à l’analyse automatisée de grandes quantités de données. Un des problèmes concerne l’ordre du modèle (nombre d’états cachés), qui est supposé connu, ce qui est rarement le cas en pratique. Un autre problème est relatif à la complexité des distributions des données réelles, qui n’est pas toujours bien reflétée par des lois d’émission paramétriques.
Nous passerons ensuite de l’inférence classique aux approches bayésiennes non paramétriques. Nous introduirons des approches plus récentes dans lesquelles le nombre d’états cachés est infini, et où les paramètres du modèle sont considérés comme des variables aléatoires avec un a priori de type processus de Dirichlet. Nous parlerons des modèles de mélange infinis (DP-MM, Dirichlet Process Mixture Model) puis des modèles de Markov cachés infinis (Hierarchical Dirichlet Process Hidden Markov Models, HDP-HMMs et sticky HDP-HMMs). Ces modèles seront présentés et nous traiterons de l’inférence bayésienne des états et des paramètres avec des approches d’échantillonnage stochastique de type Monte Carlo.
Nous appliquerons ces modèles à l’analyse de séries de délais (Round Trip Times, RTTs) sur le réseau de mesure RIPE Atlas. Nous analyserons la correspondance entre les états markoviens inférés avec cette approche de modélisation stochastique et les routes IP déduites de données traceroute. Nous montrerons enfin comment nous avons utilisé ces modèles statistiques pour optimiser le routage dans un réseau overlay avec une approche basée sur des processus de décision markoviens (MDP, Markov Decision Processes) en limitant très fortement le nombre de mesures nécessaires pour surveiller l’état du réseau.
Ouverture 2 :
Etudier un réseau en lien avec son environnement: l’approche automate cellulaire – Bernard Pottier (LabSTICC/CNRS) et Tuyen Phong Truong (Can Tho University)
L’observation des effets du changement climatique, la prédiction, et la prévision de risques sont à l’ordre du jour. Ces besoins nous viennent avec des défis nouveaux, qui sont les échelles, grandes ou très grandes, et la diversité des paramètres à observer dans les domaines physiques, naturels, biologiques, voire socio-économiques. Les réseaux sans fil, et les capteurs permettent d’établir des points de mesure sur l’environnement, et cela avec des portées bien adaptées.
Nous décrivons une approche d’outils de conception basés sur une modélisation cellulaire de l’environnement, qui permet de rationaliser la collecte, en regard des phénomènes à observer, et des difficultés que ces phénomènes, ou le terrain peuvent opposer. Le principe est d’utiliser un système de cadrage et de fragmentation géo-localisée des zones à observer. Cette fragmentation peut être l’objet de classification afin de séparer des zones de caractéristiques différentes, par exemple la complexité du terrain.
Les sous-systèmes obtenus sont transformés en simulateurs concurrents, par exemple pour les ruissellements d’orages, ou pour la propagation de signaux radio longue distance. Dans cette situation, nous pouvons apprécier la viabilité des points de mesure en regard des phénomènes à observer, et de la capacité à établir un réseau de collecte optimisé.
Nous présentons en deux temps :
- Les outils logiciels, avec une démonstration d’usage,
- Des algorithmes implantés dans les simulateurs, et notoirement les calculs de propagation, puis une expérimentation permettant la validation des résultats de simulation.
L’outillage utilisé est une machine Linux dotée d ‘un accélérateur graphique, et de cartes Arduino supportant un GPS et un émetteur récepteur LoRa.
