L’algorithme de «propagation des croyances» peut-il décrire avec précision des systèmes complexes en réseau?

Dossier de recherche: L'algorithme de «propagation des croyances» peut-il décrire avec précision des systèmes complexes en réseau?

Prédictions théoriques comparées aux expériences – les nouvelles méthodes font des prédictions théoriques précises pour des réseaux réalistes. Crédit: Kirkley et al, Science Advances

Un algorithme de transmission de messages connu sous le nom de «propagation de croyances» peut être utilisé pour analyser de grands systèmes en les décomposant en plus petits morceaux et en s’assurant que toutes les solutions plus petites sont cohérentes les unes avec les autres. Pour modéliser la propagation de la maladie lorsque des personnes sont en contact étroit, par exemple, les chercheurs ont tendance à explorer le réseau de contacts des personnes infectées parce qu’il s’agit de grands systèmes.

En principe, calculer la façon dont une maladie se propage dans un vaste réseau de contacts est un défi difficile. Mais pour prédire ce qui arrivera à l’une de ces personnes, nous avons seulement besoin de savoir ce qui arrivera aux personnes avec lesquelles ils sont réellement en contact – pas à tout le monde au sein de leur réseau.

Pour expliquer ce qui arrive à ces contacts, il suffit de regarder leurs contacts et ainsi de suite. C’est la logique récursive de la propagation des croyances, et elle permet de réduire un calcul énorme et difficile à manier à une série de calculs beaucoup plus simples. Bien que cela sonne bien, dans la pratique, tout peut s’effondrer.

Dans un article publié dans Progrès scientifiques, Alec Kirkley, George Cantwell et Mark Newman, chercheurs de l’Université du Michigan et du Santa Fe Institute (SFI), rapportent un nouvel algorithme de propagation de croyances pour la solution de modèles probabilistes sur des réseaux contenant des boucles courtes.

«Supposons qu’Alice soit en contact étroit avec Bob, qui était en contact avec Charlotte. Pour savoir ce qui arrive à Alice, nous devons connaître Bob, puis Charlotte», explique Cantwell, physicien et boursier postdoctoral du programme SFI. « Mais supposons qu’il s’avère que Charlotte était déjà en contact avec Alice, maintenant nous nous sommes enfoncés dans une sorte de régression infinie. Pour prédire ce qui arrive à Alice, nous devons d’abord prédire ce qui arrive à Bob, puis à Charlotte, puis à Alice. de nouveau. »

Fait remarquable, l’algorithme de propagation des croyances peut encore être exécuté pour de telles questions apparemment auto-référentielles, et pas seulement pour prédire la propagation de la maladie. Malheureusement, les réponses qu’il fournit ne sont pas correctes et peuvent souvent être erronées dans une large mesure, en particulier pour les structures d’aspect réaliste.

«Dans notre travail, nous développons des méthodes pratiques pour corriger cette lacune», déclare Cantwell. « Par exemple, nous montrons comment la méthode peut être utilisée pour résoudre l’un des modèles canoniques de la littérature de physique, démontrant que nous pouvons calculer avec précision le comportement physique du système. À l’avenir, nous espérons que ce style d’analyse se révélera utile pour toutes sortes de modèles statistiques construits sur des structures complexes telles que les réseaux humains.  »


Pour trouver le bon modèle de réseau, comparez tous les historiques possibles


Plus d’information:
Alec Kirkley et coll. Propagation des croyances pour les réseaux à boucles, Progrès scientifiques (2021). DOI: 10.1126 / sciadv.abf1211

Fourni par Santa Fe Institute

Citation: L’algorithme de «propagation des croyances» peut-il décrire avec précision des systèmes complexes en réseau? (2021, 28 avril) récupéré le 28 avril 2021 sur https://techxplore.com/news/2021-04-belief-propagation-algorithm-accurately-complex.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.