Monographie

Belief Propagation: The algorithm's behaviour on ill-posed optimisation problems ; ABABOU, Rachel ; GIMEL'FARB, Georgy ; SLT SOURD, Benjamin

Type de contenu
  • Texte
Titre(s)
  • Belief Propagation: The algorithm's behaviour on ill-posed optimisation problems ; ABABOU, Rachel ; GIMEL'FARB, Georgy ; SLT SOURD, Benjamin
Autre(s) responsabilité(s)
Editeur, producteur
  • Ecoles Militaires de Saint-Cyr Coëtquidan
Description matérielle
  • 1 CD
Note sur le contenu
  • mémoire
Note de thèses et écrits académiques
  • Filière Scientifique - Option Mécanique Promotion Chef de bataillon Bulle Date de soutenance : 01/01/2013
Résumé ou extrait
  • PRESENTATION : De nombreux problèmes physiques peuvent se résoudre en recherchant l'argument minimum de fonctionnelles. A cet effet, de nombreux algorithmes de minimisation de fonctions ont été développés. Nous cherchons ici à améliorer l'un de ces algorithmes - l'algorithme de belief propagation (BP) - afin qu'il puisse s'appliquer à des problèmes qui ne sont pas bien posés au sens d'Hadamar. L'objectif est donc d'obtenir l'ensemble des solutions de tels problèmes. CONTRAINTES : Les principales contraintes ont été d'ordre technique. En effet, l'élaboration de cet algorithme a été faite en langage C++ qui était le langage utilisé dans le laboratoire et qui n'est pas forcement le plus adapté pour coder un programme mathématique (calcul matriciel non-optimisé). DEMARCHE : Dans un premier temps, il a fallu comprendre l'utilisation de cet algorithme de belief propagation dont les applications sont très variés et peuvent être sensiblement différentes (sum-product BP ou min-sum BP par exemple). Une fois le cadre théorique assimilé, la première étape fut d'appliquer l'algorithme sur un problème mal posé simple pour étudier le comportement de l'algorithme original et pouvoir l'adapter pour obtenir des résultats cohérents. RESULTATS OBTENUS : On remarque que deux problèmes cohabitent dans l'algorithme original pour pouvoir l'appliquer à de tels problèmes. Le premier est un problème de convergence de l'algorithme. Ensuite, nous avons rencontrer le problème suivant : nous obtenons les valeurs admissibles pour chaque argument de la fonction mais pas un ensemble de solutions globales. On a réussi à fixer le problème de divergence à l'aide de deux méthodes de normalisation différentes et nous avons obtenu un ensemble de solutions globales en utilisant cet algorithme. LIMITES : Bien que plus efficace que le test de chacun des antécédents possibles, cet algorithme reste perfectible dans le sens où il est encore nécessaire de tester les solutions ainsi trouvées dans le cas d'un graphe bouclé. CONCLUSION : La belief propagation est un algorithme relativement bien adapté à ce genre de problème. L'adaptation faite durant ce stage fonctionne sur des problèmes basiques. Cependant, il serait intéressant de le tester sur un problème plus complexe de type stereo vision .
Sujet(s)
Lien copié.
Build V.5.2.2 - 2ecb916194 (29/04/2026 07:35:08)