Seminar: Analysis of Large-scale systems: Information Theory & combinatorial optimisation

Résumé :
Entre causalités microscopiques et phénomènes émergents, l’analyse des systèmes complexes ne peut véritablement se passer d’une approche multi-échelles. Nous abordons en particulier deux problèmes : celui de la représentation (multi-échelles) de données structurées et celui de la prédiction (multi-échelles) des systèmes dynamiques. Premièrement, nous proposons d’exploiter des mesures classiques développées en théorie de l’information pour évaluer la pertinence des niveaux de représentation/prédiction en termes d’information et de complexité(gain d’entropie, divergence de Kullback-Leibler, Information Bottleneck). Le problème de la représentation/prédiction optimale est donc formalisé sous la forme d’un problème d’optimisation combinatoire à deux objectifs, visant à extraire et agréger l’information disponible au niveau microscopique pour apporter des éléments d’analyse macroscopique. Deuxièmement, afin d’engendrer des représentations exploitables en pratiques par les experts, nous garantissons leur cohérence avec les connaissances a priori du système en contraignant l’espace de recherche du problème d’optimisation à partir des propriétés structurelles du système. Si le problème d’optimisation correspondant est NP-complet en général, nous proposons néanmoins des algorithmes polynomiaux dans le cas de structures particulières (hiérarchies, ensembles d’intervalles, produit cartésien des deux structures). Cette approche est notamment appliquée à l’agrégation spatio-temporelle de données médiatiques pour l’analyse multi-échelles des relations internationales, et à la prédiction des dynamiques multi-échelles dans un modèle classique de diffusion d’opinion (Voter Model).