Soutenance mémoire
Le sujet étudié dans cette thèse étant inspiré d’un problème pratique lié au trafic routier, nous allons en faire une brève description avant de l’abstraire comme un problème d’inférence dans la partie suivante. Les chapitres suivants de la thèse seront ensuite consacrés à l’étude de différents aspects de ce problème.
Le problème de régulation des réseaux de transport a vu son importance croître avec les phénomènes d’urbanisation et d’exode rural ; il reste critique malgré la mise en place progressive de politiques de transports publics. Un premier pas vers cette régulation consiste à être capable de fournir aux utilisateurs, et aux autorités, une information en temps réel sur l’état de congestion du réseau ainsi que sur son évolution. Plusieurs types d’informations caractérisent l’état de congestion d’un réseau. De manière non exhaustive, on peut citer la densité de véhicules, leur vitesse moyenne ou les temps de trajet sur les différents axes du réseau. On considérera dans ces travaux que c’est cette dernière information qui caractérise l’état du réseau ; c’est en général l’information qui intéresse le plus les utilisateurs de ce réseau.
La méthode classique pour recueillir des données de trafic routier est l’installation d’une boucle magnétique sous la chaussée d’un axe de circulation qui compte le nombre de véhicules y circulant par unité de temps. Il existe d’autres méthodes mais elles impliquent toutes l’installation de capteurs fixes dénombrant les véhicules circulant à un point du réseau. Dans le cas d’un réseau de transport urbain ou péri urbain, l’installation de ce type de capteurs sur l’ensemble des axes de circulation est techniquement et financièrement très difficile à mettre en œuvre du fait du nombre d’axes. Le coût d’installation d’une boucle magnétique est estimé à 12 500€, ceci ne tenant pas compte des frais de maintenance. En outre, une fois mis en place, un tel système n’offre aucune souplesse, les points de mesures étant figés.
L’émergence et la diffusion massive de systèmes de positionnement dans les véhicules remettent en cause cette approche classique de collecte de données. On propose ici d’étudier l’utilisation qui peut être faite de données provenant d’une flotte de véhicules utilisateurs du réseau. Ces véhicules fournissent, en temps réel, une information sur l’état du trafic rencontré. La nature des données est différente de celles obtenues par comptage. On passe en effet d’une vision eulérienne du trafic, où l’on observe le trafic à partir d’un point de mesure fixe, à une vision lagrangienne, où l’on suit les véhicules au cours du temps. Le point de vue lagrangien est plus adapté à la mesure de temps de trajet alors que le point de vue eulérien est plus adapté à la mesure de débit. Une collecte de données basée sur les véhicules et non plus sur l’infrastructure a déjà été mise en place sur la région de San Francisco dans le cadre du projet Mobile Millenium [75]. Les données collectées sont dans ce cas des traces GPS provenant de téléphones mobiles [45]. Notons cependant qu’obtenir des temps de trajet à partir de traces GPS nécessite de retrouver les chemins empruntés par les véhicules, ce qui peut être difficile, en particulier en zone urbaine où les axes peuvent être courts et proches les uns des autres (voir les travaux de Hunter et al. [49] à ce sujet).
Conditions suffisantes de convergence
L’algorithme BP, lorsqu’il converge, permet de trouver un minimum local d’une certaine « distance » aux vraies marginales comme on a vu dans la section 2.3 (proposition 2.1). Cependant, il existe des cas où l’algorithme ne converge pas, comme l’ont observé Murphy et al. [79]. Dans ces cas, BP ne nous fournit aucun résultat d’approximation des marginales ; en effet, à chaque itération l’énergie libre peut arbitrairement croître ou décroître. On comprend donc qu’à l’évidence, la convergence de l’algorithme BP est un aspect important de son étude.
Cas des graphes à un unique cycle. On sait que, par construction, l’algorithme BP converge en un nombre fini d’itérations lorsque le graphe de facteur est acyclique [53]. Le cas le plus simple à considérer est alors celui où le graphe contient un unique cycle. Ce cas a été étudié par Aji et al. [1] ainsi que par Weiss [102]. Les itérations de BP s’expriment alors comme des produits de matrices et il est possible de montrer que l’algorithme converge vers le vecteur de Perron de la matrice en question [102]. Les beliefs obtenus ne sont cependant pas les marginales exactes. De plus, par d’autres moyens, Watanabe et Fukumizu [101] ont montré l’unicité du point fixe de BP dans ce cas particulier.
Ce type de graphes, comportant un unique cycle, est assez courant dans le domaine des codes correcteurs d’erreurs ; ils sont associés aux codes dits « tailbiting » dont on peut trouver une description par Ma et Wolf [66].
Étude de BP en tant qu’itérations de Picard. L’approche classique pour exprimer des conditions suffisantes de convergence de l’algorithme BP consiste à étudier la suite des messages m(n) , définis par récurrence selon m(n+1) = Θ(m(n) ), à partir d’un ensemble de messages initiaux m(0).
Lien avec les mesures de Gibbs. Les premiers travaux faisant le lien entre l’étude des propriétés de BP et les mesures de Gibbs sont l’œuvre de Tatikonda et Jordan [91]. L’intérêt des mesures de Gibbs est de généraliser les distributions de Boltzmann à des graphes infinis. Pour plus de détails, on se référera à la description extensive qui en est faite par Georgii [38]. Le lien entre BP et ces mesures de Gibbs est obtenu en remarquant qu’à chaque itération BP résout, de manière exacte le problème de marginalisation sur un arbre dont la taille croît. Cet arbre a été en premier lieu introduit par Weiss et Freeman [105] sous le nom de d’arbre de calcul . Il s’agit en fait tout simplement d’un arbre infini conservant la connectivité locale du graphe originel. En terme topologique cet arbre de calcul est le revêtement universel, tel que décrit par Angluin [5], du graphe de facteurs G.
Proposition 2.3 (Tatikonda et Jordan [91]). Dès lors que l’on a unicité de la mesure de Gibbs définie sur l’arbre de calcul, l’algorithme BP converge presque sûrement vers un unique point fixe.
Types de convergence
Les variables naturelles pour exprimer les itérations de l’algorithme BP sont les messages, comme nous l’avons vu au chapitre précédent. Cependant, la valeur des messages en elle-même ne nous importe guère, c’est la valeur des beliefs qui nous intéresse. Nous allons ici préciser ce fait en décrivant deux types de convergences et leurs relations.
Dynamique des beliefs
A chaque étape de l’algorithme, en utilisant les équations (2.5) et (2.6), il est possible de calculer les beliefs courants b (n)i et b (n) a associés aux messages m(n) . La suite m(n) est dite « b-convergente » lorsque les suites b (n)i et b(n) a convergent. C’est ce type de convergence qui nous intéresse en pratique. Le terme « m convergence » fera référence à la convergence de la suite m(n) . Les beliefs s’exprimant comme des fonctions continues des messages (2.5)–(2.6), si la suite m(n) est m-convergente alors elle est évidemment b-convergente, la réciproque n’étant pas vraie en général.
Présentons tout d’abord un lemme qui sera central dans ce chapitre et qui précise le fait, énoncé par Mooij et Kappen [77], que de nombreux messages correspondent aux mêmes beliefs.
Le fait qu’un ensemble de messages correspondent aux mêmes beliefs permet de se rendre compte de l’utilité de la notion de b-convergence. En effet certains systèmes dynamiques peuvent converger vers des sous-espaces [43] ; la distinction entre b et m-convergence est donc bien réelle. Comme suggéré dans [77], il est naturel d’étudier le comportement de BP dans un espace quotient correspondant à cette invariance des beliefs. Introduisons d’abord une paramétrisation qui va faire apparaître cet espace quotient comme un simple espace vectoriel.
Normalisations homogènes positives
On introduit ici une famille de normalisations pour lesquelles les notions de m- et b-convergences sont équivalentes. L’intérêt des ces normalisations est avant tout de permettre l’étude de la convergence de BP en se focalisant uniquement sur la convergence des messages, plus naturelle à étudier. De plus, l’utilisation de ces normalisations permet numériquement de tester la convergence de BP sur les messages m directement.
Définition 3.1. Une normalisation Zai est dite positive homogène lorsqu’elle est de la forme Zai = Nai ◦ Θai, avec Nai : R q + Ô→ R+ une fonction positive homogène d’ordre 1 vérifiant
Nai(λma→i) = λNai(ma→i), ∀λ ≥ 0,
Nai(ma→i) = 0 ⇐⇒ ma→i = 0.
|
Table des matières
1 Introduction
1.1 Contexte de l’étude
1.2 Modélisation probabiliste
1.3 Champ markovien aléatoire
1.4 Structure du mémoire
1.A Éléments de théorie des graphes
2 Belief Propagation
2.1 Représentation par un graphe de facteurs
2.2 Définition de l’algorithme
2.3 L’approche variationnelle
2.3.1 Définition de la fonction objectif
2.3.2 L’approximation de Bethe
2.3.3 Minima de FBethe et points fixes de BP
2.3.4 Généralisations
2.4 BP comme re-paramétrisation de la distribution
2.5 Conditions suffisantes de convergence
2.6 Gaussian Belief Propagation
2.A Suites un+1 = f(un) : quelques notions
2.A.1 Points fixes et stabilité
2.A.2 Effets de mises à jour amorties
3 Normalisation et convergence de BP
3.1 Types de convergence
3.1.1 Dynamique des beliefs
3.1.2 Normalisations homogènes positives
3.2 Un algorithme BP sans normalisation ?
3.2.1 Point de vue variationnel
3.2.2 Point du vue itératif
3.2.3 Un schéma instable
3.2.4 Contraintes linéairement dépendantes
3.3 Une condition suffisante de stabilité
3.A Propriétés spectrales
3.B FBethe à partir des constantes de normalisation
4 BP avec observations incertaines
4.1 Contraintes fortes : mirror BP
4.1.1 Construction des règles de mises à jour
4.1.2 Convergence de l’algorithme
4.1.3 Expérimentations numériques
4.1.4 Comparaison avec « IPF-BP »
4.2 Une règle de mise à jour robuste
4.3 Minimisation d’une énergie libre moyenne
4.3.1 Cas d’une unique observation
4.3.2 Avec plusieurs observations
4.3.3 Comparaison avec mBP
5 Conclusion
Télécharger le rapport complet
