Archives

Depuis sa création en 2007, le Groupe de travail a organisé des exposés ponctuels et des journées d'exposés. Seules les journées sont archivées ci-dessous.

 

Journées d’avril 2023 : Dynamique, Probabilités, Entropie, Mots, Stat à Amiens,

organisation locale Frédéric Paccaut

 Emmanuel Fricain, Université de Lille

Cyclicité pour le shift dans des espaces de Hilbert de fonctions analytiques

Mélodie Andrieu, Université du Littoral

Complexités des mots engendrés par un billard dans un hypercube

Pascal Vanier, Université de Caen

Croissance et complexité calculatoire dans les sous-shifts

 Michel Broniatowski, UPMC, et Wolfgang Stummer, Firedrich Alexander University Erlangen

Minimisation de certaines distances par simulation

Romain Azaïs, INRIA Lyon

Enumération de motifs dans des données arborescentes : sous-arbres et au-delà

Clément Lefèvre, Université d'Amiens

Sur la conjecture d’hyperbolicité des fractions rationnelles sur la sphère de Riemann

 

Journées de novembre 2022 à Caen

Cédric Lecouvey, Université de Tours,

Quelques interactions entre la théorie des représentations et l'étude de marches aléatoires dans des réseaux ou des alcôves

De nombreux exemples de marches aléatoires conditionnées à rester dans un cône sont contrôlés par des structures algébriques issues de la théorie des représentations et de la combinatoire des systèmes de racines. Le but de léxposé sera de proposer une introduction à cette classe de problèmes et de montrer comment la notion de graphe multiplicatif y joue un rôle central en lien avec des problèmes géométriques de grande complexité.

Martin Pépin, Université Sorbonne Paris-Nord,

Énumération et génération aléatoire des graphes dirigés ordonnés sans cycles et liens avec les DAGs étiquetés.

Les graphes dirigés sans cycles (ou DAGs pour “Directed Acyclic Graphs” en anglais) sont des graphes dirigés dans lesquels il n'y a aucun chemin d'arêtes d'un sommet vers lui même. Il s'agit d'une structure de données omniprésente en informatique dont le problème du comptage par nombre de sommets a été résolu par Robinson dans les années 1970. Afin de contrôler la densité de ces graphes, il est utile de fixer aussi leur d'arêtes. Cependant, l'approche Robinson (étendue par Gessel dans les années 1990) amène à des formules de récurrence faisant apparaître le principe d'inclusion-exclusion, qui se prête mal à la génération aléatoire (efficace) par les méthodes classiques. Dans cet exposé je présenterai deux contributions. D'abord nous étudierons une nouvelle classe de DAGs (les DOAGs), enrichie avec un ordre sur les arêtes sortantes de chaque sommet, offrant un nouvel outil de modélisation. Pour cette classe nous obtenons une décomposition récursive amenant à des algorithmes de génération aléatoire efficaces ainsi qu'un équivalent asymptotique dans le cas dense. Ensuite je montrerai comment l'approche utilisée pour cette nouvelle classe peut-être utilisée dans le cadres des DAGs classiques pour obtenir de nouvelles relations de récurrences, cette fois sans inclusion-exclusion. Une conséquence de ce résultat est l'obtention d'un algorithme de génération aléatoire efficace à nombre de sommets et arêtes fixés pour les DAGs.

Lala Maghnia Moali, Université de Caen,

Monotonie et comparabilité du réseau de files d’attente [M2/G2/1 --> ./G/1/1] avec priorité relative

La difficulté d’étudier les propriétés des flux inter-stations rend l’obtention de résultats de performance explicites, pour la plupart des réseaux de files d’attente, une tâche quasiment impossible. Pour palier ces difficultés, plusieurs chercheurs ont développé des approches de substitution d’un réseau compliqué par un autre plus simple qui lui soit le plus proche possible et pour lequel des résultats analytiques existent. Les méthodes de bornes stochastiques s’appliquent aux chaînes de Markov multidimensionnelles, et permettent ainsi d’apporter des solutions intéressantes pour l’évaluation des performances des systèmes complexes. Dans ce travail, nous nous sommes focalisés sur l’application des méthodes de comparaison stochastique pour l’étude des propriétés de monotonie et de comparabilité d’un réseau de files d’attente avec priorité relative. Nous avons dérivé différentes inégalités stochastiques par rapport aux ordres stochastique et convexe, qui assurent la monotonie de l’opérateur de transition associé à la chaîne de Markov induite. Les inégalités stochastiques obtenues fournissent des bornes simples pour la distribution stationnaire des chaînes de Markov induites liées au modèle d’attente étudié.

Amor Keziou, Université de Reims

Vraisemblance empirique robuste

Nous proposons une version robuste de la méthode de vraisemblance empirique, dans des modèles semi-paramétriques, par minimisation de la divergence de Kullback-Leibler entre la mesure empirique et des ensembles de lois de probabilités vérifiant des contraintes définies par des fonctions d’orthogonalité tronquées.

Théo Grente, France Energies Marines, LMNO Université de Caen

Grammaires conjonctives, automates cellulaires et logique

Les grammaires conjonctives sont une extension des grammaires algébriques avec une opération de conjonction. Leur pouvoir expressif (même sur un alphabet unaire) est largement inconnu. Le but de cet exposé est de prouver l'inclusion des langages conjonctifs dans une des classes de complexité des automates cellulaires (AC), un modèle de calcul parallèle et local. En effet, lorsqu'on restreint le temps, léspace ou même la communication, les AC peuvent agir comme des reconnaisseurs de langages définissant des classes de complexité. La preuve présentée dans cet exposé utilise une méthode de programmation qui repose sur des caractérisations exactes des classes de complexité intéressantes de l'AC par des sous-logiques ESO (logique existentielle du second ordre) avec des formules de Horn comme partie du premier ordre. En utilisant cette méthode, il suffit de définir des grammaires conjonctives dans notre logique pour obtenir naturellement un résultat d'inclusion.

 

Journées de mai 2022 à Caen

Pierre Calka, Université de Rouen

Fractales aléatoires générées par des suites de pavages réguliers du plan

On considère un pavage régulier du plan (carré, triangulaire, hexagonal) et on construit une suite croissante d'ensembles aléatoires obtenus par réunion de tuiles d'homothétiques de ce pavage. On montre que cette suite converge vers un ensemble aléatoire compact dont on calcule explicitement les dimensions de boîte et de Hausdorff. On verra que la méthode s'appuie sur un codage de la construction itérative par un processus de branchement multi-types. Collaboration avec Yann Demichel, Université Paris Nanterre.

Brigitte Vallée, GREYC Université de Caen

Construction explicite de sources d’entropie nulle : changement d’échelle et insertion de délais.

La plupart des sources qui apparaissent de manière naturelle en théorie de l’information ont une entropie positive. Elles sont bien étudiées. Nous cherchons ici à construire de manière explicite des sources naturelles d’entropie nulle, via un changement d’échelle, ou l’insertion de délais. Ces deux processus (changement d’échelle, insertion de délais) sont d’ailleurs essentiellement les mêmes : ils ne modifient pas les intervalles fondamentaux de la source, mais seulement la « profondeur » à laquelle ces intervalles fondamentaux sont utilisés, ou la « vitesse » à laquelle on les subdivise. Nous commençons avec une source d’entropie positive, bien connue, et utilisons une classe naturelle de changements d’échelle, de croissance sous-linéaire. Les sources obtenues héritent ainsi de beaucoup de propriétés de la source de départ —au changement d’échelle près— et peuvent être finement analysées. Nous nous concentrons sur deux questions importantes: nous exhibons des lois asymptotiquement normales à la Shannon-MacMillan-Breiman, et nous analysons la profondeur moyenne des tries construits sur ces sources. Dans chacun des deux cas, nous obtenons une classe de comportements précis, paramétrée par le changement d’échelle utilisé. Nous utilisons des méthodes de combinatoire analytique, qui font jouer un rôle important aux séries génératrices des sources.

Collaboration avec Ali Akhavi GREYC, Frédéric Paccaut Université de Picardie.

Philippe Regnault, Université de Reims

Existence d'un taux d'entropie non trivial : la bonne fonctionnelle d'entropie pour le bon processus (et réciproquement).

Dans cet exposé, on s'intéresse à un critère de pertinence pour qu'une fonctionnelle déntropie soit une mesure d'information adaptée à un processus stochastique : l'existence d'un taux déntropie non trivial (différent de 0 ou de l'infini). L'existence d'un tel taux est, par définition, caractérisée par le fait que la suite des entropies marginales du processus croisse (asymptotiquement) linéairement avec le nombre de coordonnées ; propriété que l'on dénommera linéarité de la fonctionnelle pour ce processus.

Dans un premier temps, en se basant sur des résultats antérieurs de Girardin, Lhote et Regnault, on établit qu'il existe trois familles de fonctionnelles linéaires pour les processus vérifiant la propriété dite de quasi-puissance: l'entropie de Shannon, les entropies de Rényi et les entropies « log-Taneja ». Dans un second temps, on propose une méthode de construction de processus simples tels qu'une fonctionnelle déntropie donnée soit linéaire pour ces processus. Collaboration avec Valérie Girardin

Julien Clément, GREYC Université de Caen

Analyse en moyenne des tries

Le trie est une structure de donnés de type dictionnaire qui permet de représenter efficacement un ensemble de mots pour les opérations usuelles (insérer ou insérer un mot, tester si un mot est présent). Dans cet exposé je présenterai l'analyse en moyenne de paramètre de tries dans un cadre probabiliste particulier relativement simple : les mots sont produits indépendamment par une source dynamique déntropie de Shannon positive. Les méthodes sont principalement celles de la combinatoire analytique et font intervenir des séries génératrices reliées à la source et au paramètre étudié.

Cet exposé plutôt introductif se base sur d'anciens travaux en collaboration avec Philippe Flajolet et Brigitte Vallée.

Mathieu Dien, GREYC Université de Caen

Comptage des extensions linéaires et calcul du volume de polytopes convexes

Dans cet exposé, nous présenterons le problème du calcul déxtensions linéaires d'un ordre partiel et son lien avec le problème du calcul de volume de polytopes convexes particuliers. Nous présenterons rapidement des applications en lien avec ce problème, puis des algorithmes plus ou moins efficaces pour le résoudre. Nous conclurons sur plusieurs pistes de généralisations de ces résultats.

 

Journées de novembre 2021 à Caen

Pablo Rotondo, Université Gustave Eiffel Champs-sur-Marne

Entropie renormalisée : partitions balancées et changement de base

Dans le cas de deux sources de deux sources déntropie positive, Dajani et Fieldsteel ont démontré en 2001 que la quantité de symboles d'une source S2 qui sont produits par chaque symbole d'une source S1 est essentiellement le quotient h(S1) / h(S2) des entropies respectives. Plus précisément, si, grâce à n symboles de S1 sur léntrée, on peut produire m symboles dans la source S2 , alors le quotient m/n tend vers h(S1)/h(S2) lorsque n tend vers l'infini. Nous obtenons un cadre plus général qui s'applique aussi aux sources déntropie nulle. Notre généralisation du théorème de Dajani-Fieldsteel fait intervenir une fonction f dite de poids ou entropie renormalisée, qui joue un rôle analogue à léntropie. Quand cette fonction de poids f existe (presque partout ou en mesure), disons f1 pour S1 et f2 pour S2, nous montrons que la limite qui intervient dans le théorème de Dajani-Fieldsteel est lim f2(m)/f1(n) = 1. Quand l'entropie h est positive, la fonction de poids f est tout simplement linéaire f(t) = h·t. Pour certains cas d’entropie nulle, et en particulier pour plusieurs sources importantes de théorie des nombres, nous démontrons que la fonction de poids existe toujours et est sous-linéaire. Collaboration avec Valérie Berthé, Eda Cesaratto et Martín D. Safe.

Blanche Saint Béat, Laboratoire d'écologie Pélagique (PDG-ODE-DYNECO-PELAGOS) Ifremer Brest

Estimation des flux du réseau trophiques par par modélisation inverse (LIM) : choix d’une fonction objective.

En écologie marine, les propriétés des réseaux trophiques révèlent le fonctionnement des écosystèmes. Ces propriétés nécessitent un réseau quantifié. Alors que les mesures de flux in situ sont souvent parcellaires, la quantification des flux devient un problème sous-déterminé pour lequel il existe une infinité de solutions qui s’ajustent au jeu de données in situ. Une manière rigoureuse de résoudre un tel problème est la MODELISATION LINEAIRE INVERSE (LIM). La version la plus récente du LIM permet de déterminer un set de solution pour chaque flux grâce à un algorithme d’échantillonnage aléatoire. La description de l’incertitude associée à chaque flux permet de développer des tests statistiques indispensables dans un contexte de comparaison d’écosystèmes ou d’analyse d’impact d’une perturbation. Cependant, pour certaines analyses plus précises une seule solution par flux est nécessaire. Une question se pose alors : comment choisir une seule solution parmi toutes celles proposées ? Déterminées selon des critères mathématiques ou écologiques, différentes fonctions objectives, permettant la sélection d’une seule valeur pour chaque flux, ont été testées. Par une stratégie de dégradation de modèles LIM très bien documentés et la réestimation des flux des réseaux trophiques associés, 10 fonctions objectives ont été testées. Si certaines fonctions écologiques donnent de bons résultats, la fonction de la moyenne apparait comme celle qui estime le mieux les flux du réseau trophique quelle que soit la quantité d’information intégrée au modèle LIM. La reprise récente de cette étude, avec une approche mathématique, a mis à jour de nouvelles conclusions, qui vous seront présentées par Valérie Girardin.

Valérie Girardin, LMNO Université de Caen

Quelques questions sur l'utilisation de la théorie de l'information en analyse inverse de réseaux trophiques par des méthodes MCMC

L'algorithme LIM-MCMC de Van Den Meersche (2009) est couramment utilisé par les écologues pour décrire le polygone multidimensionnel déterminé par les contraintes linéaires biologiques sur un écosystème marin. Saint Béat et al. (2013) ouvre la voie sur une méthodologie nouvelle permettant de déterminer une solution particulière à partir de l'ensemble des solutions ainsi simulées, par optimisation de fonctions de coût. Dans son stage, Yann Burkhardt a envisagé différentes fonctions provenant de la théorie de l'information, en les comparant de manière statistique sur un modèle synthétique qui supporte une dégradation systématique. Des questions sur la méthode LIM-MCMC en comparaison de méthodes algorithmiques plus récentes utilisées dans d'autres domaines sont apparues en cours d'étude. D'après le rapport de stage de magistère de Yann Burkhardt, Université Paris-Saclay Orsay

Justine Lequesne, Centre François Baclesse Caen

Construction d’un score de toxicités cumulées pour modéliser l’évolution de la qualité de vie pendant un traitement : application sur des données de patientes traitées pour un cancer de l’ovaire.

Avec les progrès récents en matière de recherche médicale, la survie des personnes atteintes de cancer s’est nettement améliorée depuis ces dernières décennies, au prix de fortes contraintes pour le patient. Maintenir une bonne qualité de vie chez ces patients est devenue une préoccupation centrale dans leur prise en charge.

Dans cet exposé, nous analyserons les scores de toxicités des patientes de l’essai clinique AURELIA, traitées pour un cancer de l’ovaire. Les scores de toxicité seront calculés à partir de l’ensemble des événements indésirables, de ceux reliés au traitement ou seulement de ceux de grade élevé. L’association entre chaque score de toxicité et la qualité de vie sera évaluée par des modèles mixtes ajustés sur plusieurs facteurs d’intérêt (traitement, age, etc.). Les paramètres de régression standardisés associés à chaque score seront ensuite comparés dans le but d’identifier le score de toxicité qui prédit au mieux l’évolution de la qualité de vie. Collaboration avec Sophie Lefèvre-Arbogast, Elodie Coquan et Florence Joly

Jean-Guy Caputo, Laboratoire de Mathématiques INSA Rouen

Analyse de réseaux trophiques: une approche par l'optimisation

Nous introduisons une méthodologie pour étudier les possibles flux de matière dans un écosystème défini par des observations de biomasses et des contraintes biologiques réalistes. Les flux appartiennent à un polygone dans un espace multidimensionel ce qui rend une exploration statistique difficile en pratique ; nous proposons alors de résoudre un problème d'optimisation convexe. Sept critères basés sur des index écologiques ont été choisis comme fonctions de coût convexes. Les résultats numériques montrent que la méthode est rapide et peut être utilisée pour de grands systèmes. Les solutions de flux minimal sont ensuite analysées par la décomposition chemins-cycles. Leur consistance est aussi vérifiée en introduisant un système différentiel vérifié par les biomasses sur lequel on examine la stabilité du point fixe. La méthode est illustrée sur un modèle réduit d'écosystème et appliquée à des systèmes réalistes. Collaboration avec Valérie Girardin, Arnaud Knippel, Hieu Nguyen,Nathalie Niquil et Quentin Noguès.

Nathalie Niquil et Quentin Noguès, BOREA Université de Caen

Quelques exemples d'applications du LIM MCMC à l'analyse des impacts humains sur le fonctionnement des écosystèmes marins.

Qu’est ce qu’un écosystème marin en « bon état écologique » ? Cette question est devenue capitale pour les états de l’Union Européenne lorsque cette notion de « bon état écologique » des réseaux trophiques est entrée dans le droit de l’UE par la Directive Cadre Stratégie pour le Milieu Marin (en 2008 à l’UE et 2010 dans le droit français). Nous proposons d’utiliser les indices ENA (Ecological Network Analysis), calculés à partir du LIM-MCMC, pour décrire le changement d’état du réseau trophique avant et après des impacts, observés ou simulés. Nous développerons en particulier ici le cas du futur parc éolien de Courseulles-sur-mer dont nous avons décrit l’effet prévisible sur le fonctionnement de l’écosystème en étudiant son cumul avec les effets du changement climatique sur la répartition des espèces qui suivent vers le Nord leur optimum de température et de salinité. Les résultats démontrent la capacité des indices ENA à décrire et comprendre les effets cumulés à l'échelle de l'écosystème. En utilisant une approche d'analyse de sensibilité, notre étude montre que les indices ENA pourraient être des outils utiles pour aider les gestionnaires dans leurs décisions : par exemple, sur l’intérêt écologique d’ouvrir ou fermer la zone à la pêche entre les mats d’éoliennes.

Christine Kéribin, Université Paris-Saclay Orsay

Classification non supervisée sous contrainte de mémoire de très grands jeux de données déséquilibrés à partir de comptages marginaux

En classification non supervisée de grands volumes de données, il est intéressant de pouvoir détecter de petites classes qui peuvent avoir une grande valeur. Nous nous plaçons dans un cadre où la taille mémoire est limitée et le jeu de données ne peut être chargé en mémoire. Il est alors courant de recourir au sous-échantillonnage, mais sa capacité à détecter les petites classes est limitée. Considérant la classification non supervisée par modèle de mélange gaussien, nous proposons une approche de réduction de taille par comptages marginaux. Nous en établissons les propriétés théoriques, définissons un algorithme d’estimation et illustrons sa plus-value par rapport au sous-échantillonnage pour la détection de petits clusters. Collaboration avec Filippo Antonazzo et Christophe Biernacki.

 

Journées de novembre 2019 à Caen

Jean Paul Allouche, CNRS, UPMC

Un bref survol sur les automates cellulaires et une «application» aux équations de réaction-diffusion

Plusieurs communautés, qui ne se parlent pas toujours entre elles, s'intéressent aux différentes notions d'automates ; en se limitant aux automates abstraits, il y a essentiellement deux grandes catégories, les automates finis et les automates cellulaires. Dans cette dernière catégorie ont été surtout étudiés les automates cellulaires à une dimension et les dessins obtenus en regardant leur évolution temporelle (il est de bon ton de citer Wolfram). Si on se permet de quitter la dimension 1, on trouve des tentatives de modélisation d'équations aux dérivées partielles : nous citerons un exemple avec un travail avec Christine Reder lié à une réaction chimique oscillante (Belouzov-Zhabotinsky-Zaïkine), et donc aux équations de réaction-diffusion.

Maël le Treust (ETIS UMR 8051, Université Paris Seine, Université Cergy-Pontoise, ENSEA, CNRS)

Communication stratégique et persuasion

Quelle information doit-on partager avec un destinataire ayant un objectif différent? Le problème de la «communication stratégique», à l'origine issue de la littérature économique, se pose aujourd'hui pour les réseaux de communication décentralisés. Les utilisateurs et/ou les appareils sont considérés comme des joueurs qui choisissent de manière autonome des stratégies de transmission afin d'optimiser leur propre objectif. Désormais, chaque symbole révèle une information qui induit une action, qui donne un paiement. A l'inverse du paradigme classique de la communication, le schéma de codage doit tenir compte de la signification de chaque symbole. L'objectif n'est plus d'assurer la fiabilité de la transmission, mais de contrôler les croyances postérieures du décodeur afin d’influencer son action. Nous proposons une approche unifiée qui généralise les résultats de classiques de la théorie de l'information et les résultats des jeux de persuasion. Nous caractérisons la communication stratégique optimale à l'aide de la concavification d'une utilité évaluée sur l’espace des croyances postérieures, sous une contrainte d’entropie moyenne.(avec Tristan Tomala, HEC Paris, GREGHEC UMR 2959)

Loïck Lhote (GREYC ENSICAEN)

Calcul d'entropies généralisées pour le système dynamique des fractions continues

Nous nous intéressons au calcul de constantes qui sont liées au système dynamique des fractions continues. Dans un article de 2004, nous avons proposé un algorithme de complexité polynomiale pour calculer l'entropie de Shannon (qui admet une forme explicite), la constante de Hensley (qui intervient dans la variance du nombre d'étapes de l'algorithme d'Euclide) ou encore la dimension de Hausdorff de certains ensembles.

Dans cet exposé, nous montrerons comment étendre ces calculs aux entropies généralisées comme celles de Rényi, Tsallis ou Sharma-Mittal. L'algorithme se base sur une méthode utilisée par Flajolet, Daudet et Vallée pour calculer certaines constantes liées aux réseaux euclidiens.

Rita Giuliano (Dipartimento di Matematica, Universita' di Pisa)

Entropie et dimension de Rényi dans un cadre général

A partir des notions d'entropie de Shannon et de alpha-entropie de Rényi, la notion de alpha-dimension d'une variable aléatoire est d'habitude introduite en supposant que le paramètre est un nombre entier tendant vers l'infini. Afin d'utiliser cette notion dans le cadre des ensembles de Cantor généralisés, il faut supposer que le paramètre est un nombre réel (tendant encore vers l'infini). Cela amène des problèmes de définition que nous allons discuter dans le présent exposé. En outre, nous étendons un lemme de Wu et Verdu, concernant le cas entier pour l'entropie de Shannon, au cas des non entiers et aux alpha-entropies de Rényi.

Justine Lequesne (Centre de Lutte Contre le Cancer, Henri Becquerel Rouen et François Baclesse Caen)

Méthodologie statistique des essais cliniques en cancérologie : utiliser des outils innovants sans compromettre la faisabilité de l'étude ou l'interprétation des résultats.

 

Journées de mai 2019 à Calais,

organisation locale Dominique Schneider

Valérie Girardin Université de Caen, et Philippe Regnault Université de Reims

Taux d'entropies généralisées.

Dominique Schneider, Université du Littoral

Vitesse presque-sûre dans le théorème ergodique.

Pierre Calka, Université de Rouen

Enveloppes convexes de points aléatoires perturbés.

Nikolitsa Chatzigiannakidou, Université du Littoral

Disjoint universality for subsequences of the orbit of the real Taylor shift.

Sabine Evrard, Université d'Amiens

Polynômes à valeurs entières.

 

Journées de décembre 2018 à Caen

Christine Kéribin, LMO, Université Paris-Sud Orsay

Etude de critères de sélection pour définir la complexité d’un modèle de co-clustering

La classification croisée (co-clustering) est une méthode d’apprentissage non supervisée définissant une partition simultanée des lignes et des colonnes d’une matrice sous forme d’un quadrillage de blocs. Parmi les approches probabilistes pour traiter le co-clustering, le modèle des blocs latents (LBM) est un modèle de mélange complexe, la structure des blocs sous-jacente impliquant une dépendance forte des observations. Des travaux récents ont montré la consistance et la normalité asymptotique des estimateurs variationnel et du maximum de vraisemblance du LBM lorsque le nombre de blocs est connu. Nous étudions deux critères pour sélectionner le nombre de blocs d’un LBM quand celui-ci est inconnu. Le critère BIC (Bayesian Information Criteria, Schwarz 1978) est traditionnellement utilisé pour sélectionner l’ordre d’un modèle de mélange. L’approche ICL (Integraded Completed Likelihood, Biernacki 2000) met l’accent sur la robustesse de la classification. La différence entre ces deux critères peut être assimilée à un terme d’entropie. Dans le LBM, le critère ICL a une expression exacte à distance finie et est facilement calculable, alors que BIC souffre d’une double approximation. Nous étudions la consistance de ces critères, et conjecturons en particulier celle du critère ICL pour le LBM, fait remarquable puisque ce n’est pas le cas pour les modèles de mélange simple.

Steeve Zozor CNRS, GIPSA-Lab, DIS Grenoble

Sur le codage quantique sans pertes avec pénalisation exponentielle

Nous étudions le problème du codage source quantique sans perte en nous appuyons pour cela sur un schéma d'encodage satisfaisant à une version quantique de l’inégalité de Kraft-McMillan. Dans le cadre standard l'objectif est de minimiser la moyenne (de type arithmétique) des longueurs des mots code quantiques, conduisant, contrairement au cas classique, à l'encodage non pas des symboles quantiques formant la source, mais les états propres de l'opérateur densité la caractérisant (les valeurs propres formant les probabilités associées). Nous nous intéressons ici à la la minimisation d'une moyenne de type exponentielle afin de pénaliser les mots code de “grande longueur”. Nous montrons que, à l'image du cas classique, la longueur moyenne exponentielle du code optimum est liée à la version quantique de l’entropie de Rényi de la source, le cas von Neumann (équivalent quantique de Shannon) étant le cas particulier correspondant à la pénalisation linéaire. La longueur moyenne usuelle est, elle, reliée à la fois à l'entropie de Rényi et de von Neumann de la source.

Gaëtan Richard, GREYC, Université de Caen Normandie

Complexité de Kolmogorov : une introduction dans le cadre des systèmes dynamiques

Dans cet exposé, nous présenterons les notions de complexité de Kolmogorov et leur liens avec l’aléatoire. Nous porterons attention aux questions soulevées (et aux réponses apportées) par les définitions et tout particulièrement vis-à-vis de l’entropie. Nous regarderons également plusieurs utilisations de cette complexité dans le cadre des systèmes dynamiques.

Charles Tillier Télécom ParisTech, Université Paris Nanterre,

Méthodes statistiques pour le comportement extrême de chaînes de Markov.

Dans cet exposé, je vais présenter des méthodes statistiques qui sont particulièrement adaptées à l'étude du comportement extrémal de chaînes de Markov. En effet, les chaînes de Markov de type Harris peuvent être décomposées en cycles de régénération indépendants, ces cycles étant définis par des instants de régénération où la chaîne oublie son passé. De fait, on peut découper le chemin des observations en blocs de régénération et examiner les extrema du processus comme si ces blocs étaient (approximativement) indépendants et identiquement distribués. Je me concentrerai sur léstimation de l'indice extrémal et l'indice de queue du processus et j'illustrerai ces méthodes sur deux exemples provenant de la finance et de l'assurance. Enfin, pour mettre en avant le potentiel de ces techniques, je présenterai une application sur données réelles, le CAC 40. Travail commun avec Patrice Bertail (Université Paris Nanterre) et Stéphan Clémencon (Télécom ParisTech).

Matthieu Dien, GREYC Université de Caen Normandie

Génération aléatoire de structures discrètes par la méthode de Boltzmann

Nous commencerons par définir des outils de bases de la combinatoire énumérative, les séries génératrices. Puis nous introduirons la méthode symbolique permettant de passer d'une description (une spécification) d'une famille de structures discrètes à une équation fonctionnelle vérifiée par sa série génératrice. Nous utiliserons alors ce même principe pour décrire une méthode systématique permettant de construire des générateurs aléatoires pour toutes structures spécifiables (et bien fondées). Si le temps nous le permet, nous présenterons une extension de ces résultats aux structures croissantes.

Ali Mohammad-Djafari CNRS, L2S, CentraleSupélec, UPSa, ISCT

Traitement des signaux et des images comme problème inverse : de la régularisation à l'inférence bayésienne

En traitement du signal classique, on regarde le signal ou l'image et on l'analyse: débruitage, augmentation de la résolution, segmentation, détection de contours, etc., souvent sans un critère précis. Une approche plus récente consiste à modéliser le signal observé (image floue et bruitée) comme la sortie d'un système dont l'entrée est le signal désiré (image nette et sans bruit). La fonction de transfert de ce système reliant la sortie à l'entrée est le modèle direct et l'estimation de léntrée à partir des données observées est un problème inverse. Deux classes de méthodes existent: régularisation et l'inférence bayésienne. Dans l'approche de régularisation, on définit la solution comme l'optimiseur d'un critère en deux parties: un terme d'adéquation des données au modèle et un terme de régularisation. En fonction des choix pour ces deux termes, il y a un grand nombre d'algorithmes d'optimisation. Bien que ces méthodes aient eu du succès, il reste trois limitations: choix des critères, poids relatif des deux termes (paramètre de régularisation) et quantification de l'incertitude de la solution obtenue.

L'approche inférence bayésienne apporte des solutions pour ces limitations en modélisant les erreurs (le terme de vraisemblance), en proposant des modèles probabilistes appropriés (a priori). Et finalement, en fournissant la loi a posteriori de tous les inconnues, à partir de laquelle on peut, soit opter pour un estimateur ponctuel (mode ou espérance) ou explorer lénsemble des solutions les plus probables. Cet exposé se focalise plus sur l'inférence bayésienne.

 

Journée de juillet 2018 à Saint Martin d'Hères,

organisation locale Steeve Zozor

Philippe Regnault (Univ. de Reims Champagne-Ardenne)

Taux d'entropie généralisés de chaînes de Markov ergodiques

Saloua Chlaili (GIPSA-Lab)

Sur les liens entre th »orie de l'information et th »orie de l'estimation dans le cas de double inadéquation du modèle

Simon Barthelmé (GIPSA-Lab, Grenoble)

Polynômes symétriques et entropie

Max Hongler (Labo. de Proc. Microtech., EPFL, Lausanne)

Entropie relative et rendement énergétique des moteurs Browniens

Steeve Zozor (GIPSA-Lab)

Sur le codage quantique sans pertes avec pénalisation exponentielle

 

Journées de janvier 2018 à Caen

Dominique Schneider Université du Littoral

Statistique du premier chiffre pour certaines suites de réels

Etant donnée une suite (u_n) de réels postifs, notons M(u_n)) sa suite des mantisses en base 10. Nous étudions le comportement asymptotique de cette dernière. Nous donnons, notamment, des conditions afin de montrer que la suite M(u_n)) converge au sens de la densité naturelle vers la loi de Benford (appelé phénomène du premier chiffre). Nous discuterons aussi le cas de la convergence au sens de la densité logarithmique. Nous étudierons aussi le cas où la suite (u_n) est générée par les trajectoires d'un processus aléatoire. Nous donnerons des majorants des vitesses de convergence dans les différentes situations citées. Enfin nous tenterons déxpliquer pourquoi beaucoup de données de la vie réelle semblent plus ou moins suivre le phénomène du premier chiffre.

Brigitte Vallée Université de Caen Normandie

Dichotomic Search and Basis Changing

Sorting and searching algorithms are based on comparisons between keys, and each comparison between keys is usually given a unitary cost. The analysis of most of classical algorithms (QuickSort, QuickSelect, etc ....) is well-known in this case. Usually, the keys are viewed as real numbers; we now revisit these algorithms, that now deal with words which encode reals instead of reals themselves. In this case, comparisons are performed between the encoding words and the cost of such a comparison (in number of symbols) depends on the coincidence of words (the length of their longest common prefix). We have already performed this fine analysis, for many classical sorting and searching algorithms. The present talk is focused on Dichotomic Search. The classical Dicho algorithm deals with a sorted sequence X=(x_i), i in N, of keys (with N= 2^L) and an input key x. It determines the interval [x_i, x_{i+1}] the key x belongs to. The design of the algorithm is more transparent if one associates to the sequence X its binary tree T of depth L. Then, for each input x, Dicho finds a path in the tree T and performs comparisons between x and the keys that are on this path. This is why the Dicho algorithm always performs L comparisons. We revisit the Dicho Algorithm: we consider a dynamical system D, and we deal with the encoding of reals in base D: each real number x is encoded via its expansion D(x) in the system D}. Moreover, the binary tree T associated with the dichotomic process can be viewed as generated by a binary dynamical system B. Now, the Dicho Algorithm deals with two systems: the encoding system D and the dichotomic system B. Given the encoding D(x) of the input, and the encoding D(x_i) of the nodes of the dichotomic tree, it finds, via comparisons between the input D(x) and the encoded nodes D(x_i), a path in the tree. This also determines the beginning of the word B(x) which encodes x via the (dichotomic) system B}. The algorithm Dicho is thus also viewed as an algorithm for changing basis. We study the fine complexity (in number of symbols) of the Dicho Algorithm, when it deals with random encodings in base D, and uses a dichotomic system B. In particular, we compare it to the lower bound for Changing Basis, that comes from information theory and involves the ratio between the entropies of the two sources.

Etienne Grandjean Université de Caen Normandie

Calculabilité et complexité: un point de vue historique et personnel

En 1928, Hilbert a posé la question de l’existence d’un algorithme qui déterminerait si un énoncé logique/mathématique quelconque est valide (Entscheidungsproblem). A la suite des travaux de Gödel, Turing et Church ont démontré en 1936 qu’un tel algorithme n’existe pas. La théorie de la calculabilité, née sur ces bases, puis la théorie de la complexité, initiée dans les années 60, se sont donné comme objet d’étude l’existence ou la non existence d’algorithmes - ou d’algorithmes efficaces - pour résoudre les problèmes. Dans cet exposé, je présenterai un point de vue personnel à partir de quelques résultats qui illustrent un « état des lieux » de ces questions. Je mettrai l’accent sur des aspects qu’on peut juger surprenants : le fait que nombre de problèmes « naturels » dits « difficiles » sont prouvés de complexité exactement équivalente ; la difficulté qu’on a à prouver des bornes inférieures de complexité pour un grand nombre de problème « naturels » alors qu’on sait démontrer quelques résultats de hiérarchie très fins ; certaines dichotomies de complexité prouvées, etc.

Pierre Calka Université de Rouen

Cas d'inhomogénéité dans les mosaïques de Poisson-Voronoi

En probabilités géométriques, on étudie des figures géométriques générées aléatoirement. Dans cet exposé, on se concentre sur le modèle classique de la mosaïque de Poisson-Voronoi qui est une partition de léspace engendrée par un ensemble de points aléatoires appelés germes, chaque germe donnant naissance à une zone polyédrique de l'espace appelée cellule. Lorsque l'ensemble des germes a de bonnes propriétés d'homogénéité comme c'est le cas pour un ensemble invariant par translation dans léspace euclidien, la théorie générale des processus ponctuels donne la possibilité de calculer les moyennes de certaines caractéristiques géométriques des cellules. Ce nést plus le cas lorsqu'il y a inhomogénéité de la répartition des germes. On s'intéressera à deux problèmes différents : d'une part, un ensemble de germes dans le plan dont la répartition connaît un "trou", c'est-à-dire un ensemble convexe compact vide ou que l'on force à être contenu dans une cellule et d'autre part, un ensemble de germes sur une variété riemannienne de courbure non constante. Dans les deux situations, on calculera des moyennes de caractéristiques géométriques (nombre de sommets d'une cellule notamment) dans un cadre asymptotique.

Nicolas Chenavier Université du Littoral

Stretch factor dans une triangulation de Delaunay

Considérons un processus ponctuel de Poisson (X_n) d'intensité n dans le plan et deux points (déterministes) p et q du plan. Le processus ponctuel X:=X_n U {p,q}, génère un graphe DT(X) dit de Delaunay. Ce graphe définit une triangulation du plan telle qu'aucun point de X n'est à l'intérieur du disque circonscrit des triangles de DT(X). Dans cet exposé, on s'intéresse à la longueur du chemin le plus court reliant les points p et q, le long des arêtes de DT(X), lorsque l'intensité n du processus (X_n) tend vers l'infini.

 

Journée de novembre 2017 à Nanterre,

organisation locale Patrice Bertail

Christian Léonard (Université Paris-Nanterre)

Convergence du transport entropique vers le transport optimal déterministe

Valérie Girardin (Université de Caen)

Taux d'entropie généralisée

Emmanuelle Gauthérat (Université de Reims)

Phi-divergence empirique pour des fonctionnelles Hadamard différentiables

El Mehdi Issouani (Université Paris-Nanterre)

Maximum d'entropie pour la traduction ou la réduction de texte

 

Journées de mai 2017 à Reims,

organisation locale Philippe Regnault

Aldric Degorre IRIF, Paris 7

Entropie des langages temporisés réguliers

Frédéric Paccaut (LAMFA, Amiens)

g-mesures et mesures de Gibbs : quelles différences ?

Brigitte Vallée et Dimitri Darthenay GREYC, Université de Caen

Analyse fine de la Sélection Dichotomique

Charles Tillier Modal'X, Paris 10

Etude du comportement extrémal de processus stochastiques en théorie du risque

Amor Keziou LMR, Université de Reims

Séparation aveugle de sources dépendantes

 

Journée de janvier 2017 à Caen en commun avec le séminaire Algo du GREYC et le séminaire Analyse et Physique Mathématique du LMNO

Nicolas Basset Université libre de Bruxelles

Mesures d'entropie maximale pour les réseaux d'automates

Il est en général impossible d'énumérer exhaustivement les mots d'une taille fixée « n » d'un automate fini car leur nombre croit exponentiellement par rapport à n. Par contre, il est bien connu comment avoir accès en temps polynomial à un mot typique de longueur n, c'est à dire qu'on peut simuler la mesure de probabilité qui donne la même chance à chaque mot de longueur n d'être tiré au sort. Cette mesure uniforme est celle déntropie maximale au sens de Shannon. Pour les mots de longueur infini (et sous hypothèse de forte connexité de l'automate), la mesure déntropie maximale décrite par Shannon (et connue sous le nom de mesure de Parry) peut se calculer en temps polynomial par rapport à la taille de l'automate. Nous considérons les familles d'automates synchronisés sur les lettres communes et entrelacés sinon, qui sont un formalisme élégant et très utile pour modéliser les systèmes concurrents. Pour de tels modèles, il est indispensable d'adopter des méthodes compositionnelles qui combinent des calculs effectués sur les automates composants la famille sans jamais construire l'automate produit de taille prohibitive (exponentielle en le nombre d'automates composants la famille). Nous présentons des méthodes compositionnelles de calcul de mesures déntropie maximale pour les mots finis (mesure uniforme) ou infinis (mesure de Parry). Nous proposons aussi des méthodes compositionnelles pour les mesures de Boltzmann. Les générateurs aléatoires associés à ces mesures ont été très étudiés récemment du fait de leur capacité à générer aléatoirement et de manière très efficace des objets combinatoires de grande taille.

Eugène Asarin IRIF, Université Paris-Diderot

Langages temporisés et leur taille (fonctions génératrices et entropie)

Les automates temporisés et leurs langages introduits au début des années 1990 par Alur et Dill sont largement utilisés pour modéliser des systèmes temps-réel et leurs comportements. Ils sont également des objets mathématiques intéressants. Un mot temporisé est une séquence des lettres (événements) et des nombres réels (intervalles de temps entre ces événements), par exemple 2.53a1.72b3a4.5a. Un langage temporisé est un ensemble de tels mots. On va s’intéresser à la taille (volume) d’un tel langage temporisé. Ceci peut être vu comme une nouvelle classe de problèmes combinatoires, mais cette question est aussi liée à une nouvelle approche à la transmission d’information et à la génération aléatoire. L’information la plus complète sur la taille du langage est contenue dans une fonction génératrice, mais existent des caractéristiques plus grossières, telles que l'entropie. Dans l’exposé je présenterai les langages et automates temporisés et puis caractériserai leurs fonctions génératrices et entropie comme propriétés spectrales d'un opérateur intégral. Et sur des nombreuses exemples je montrerai comment on peut calculer des jolies formules pour les fonctions génératrices pour certaines classes d’automates temporisés. (travaux communs avec N.Basset, D.Perrin et A. Degorre)

Claude Longuemare Université de Caen

Chaleur, désordre et entropie

Le but de cet exposé sera de survoler les questions qui ont conduit historiquement à élaborer la notion déntropie en physique. Il sera nécessaire de revenir sur les cycles thermodynamiques et l'inégalité fondatrice de Clausius . Grâce à Boltzmann nous ferons le lien avec la notion de désordre énergétique en donnant un sens microscopique et statistique à la distinction chaleur/travail. Nous terminerons cet exposé par une « évocation » de l'équation de Boltzmann, de son théorème H et le retour du temps qui passe.

Ali Akhavi GREYC, UNICAEN

 Le problème du tri généralisé, un point de vue symbolique à propos des algorithmes réversibles

Nous présentons un cadre pour associer de manière originale et naturelle, un algorithme à un ensemble de règles de réécriture. Ici un algorithme est identifié avec l'ensemble de ses traces d'exécution. Les systèmes de réécriture sont définis sur les séquences de transformations élémentaires et sont tels que leurs formes normales sont exactement les traces d'exécution. Les algorithmes que nous considérons sont ceux qui cherchent à résoudre une classe de problèmes que nous introduisons sous le nom des problèmes de tri généralisé. Il s'agit de la recherche d'une séquence génératrice particulière pour une algèbre présentée. Sous des hypothèses raisonnables, nous montrons que les traces d'exécution de ces algorithmes sont des diagrammes (i.e., graphes orientés et arc-colorés) couvrants des diagrammes de Cayley du groupe des automorphismes de l'algèbre présentée associé à l'algorithme (et donc des systèmes de réécriture). En utilisant le formalisme des ASM introduit par Gurevich, nous montrons que tout algorithme qui est réversible (i.e., qui ne perd pas d'information durant une exécution) et qui s'arrête toujours, résout un problème de tri généralisé. Notre approche permet de relier dans les cas très simples une borne inférieure de complexité au diamètre d'un graphe de Cayley.

Philippe Regnault, Université de Reims Champagne Ardennes

Taux d'entropie renormalisés d'une chaîne de Markov : forme explicite et interprétation dynamique.

Usuellement, en théorie de l'information, le taux déntropie d'un processus stochastique est défini comme la limite de l'entropie marginale du processus normalisée par unité de temps. Il a été établi récemment (Ciuperca, Girardin, Lhote 2011, Girardin, Lhote 2015) que cette limite est dégénérée (valant 0 ou l'infini) pour la plupart des entropies usuelles, à l'exception des entropies de Shannon et de Rényi, mais qu'une renormalisation adaptée permet de définir des taux d'entropie -- dits renormalisés -- pour une large famille d'entropies et de processus. Le taux d'entropie d'une chaîne de Markov ergodique associée à l'entropie de Shannon possède une expression explicite, fonction de la matrice de transition de la chaîne et de sa loi stationnaire. Sous des conditions simples sur la matrice de transition de la chaîne, on obtient ici des expressions explicites pour les taux d'entropie renormalisés. Ces expressions apparaissent comme des extensions directes du cas classique de Shannon et possèdent une interprétation dynamique similaire, faisant intervenir la notion de loi quasi-stationnaire.

Journées d'avril 2016 à Caen, en commun avec le séminaire Algo du GREYC

Thierry Lecroq LITIS,  Université de Rouen

Répétitions abéliennes dans les mots sturmiens

Dans cet exposé nous étudions les répétitions abéliennes dans les mots sturmiens. Nous exploitons une bijection entre les facteurs des mots sturmiens et des intervalles du segment unitaire qui permet d'étudier les périodes des répétitions abéliennes en utilisant des résultats classiques de la théorie des nombres. Si k_m est léxposant maximal d'un répétition abélienne de période m, nous montrons que la limite supérieure k_m/m est supérieure ou égale à racine de 5 pour tout mot sturmien et quélle est égale à racine de 5 dans le cas du mot infini de Fibonacci. Nous montrons de plus que le plus long préfixe du mot infini de Fibonacci qui est une répétition abélienne de période F_j, j > 1, a pour longueur F_j(F_{j+1} + F_{j-1} + 1) - 2 si j est pair et F_j(F_{j+1} + F_{j-1}) - 2 si j est impair. Cela nous permet de donner une formule exacte pour la pluspetite période abélienne d'un mot fini de Fibonacci. Travail en commun avec Gabriele Fici, Alessio Langiu, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki et Elise Prieur-Gaston

Pierre Calka (LMRS Université de Rouen) 
Probabilités géométriques et géométrie algorithmique : étude asymptotique dénveloppes convexes et autres exemples

Cet exposé vise à présenter des résultats de probabilités géométriques portant sur des structures qui apparaissent naturellement en géométrie algorithmique (polyèdres, graphes géométriques, triangulations...). On s'intéressera plus particulièrement au cas des enveloppes convexes de grands nuages de points aléatoires et on montrera comment obtenir des moyennes et variances limites de leurs caractéristiques géométriques telles que le nombre de points extrémaux ou de faces de dimension fixée, le volume, etc. Par ailleurs, on établira des théorèmes limites et on exhibera dans certains cas léxistence de formes limites. En fonction du temps, on pourra aussi aborder d'autres exemples de structures géométriques telles que les cellules de Voronoi. Les résultats présentés sont utiles dans le cadre de l'analyse de complexité en moyenne en géométrie algorithmique. 

Valérie Girardin (LMNO Université de Caen Normandie) 
Taux d'entropie renormalisés. Application aux chaînes de Markov.

Nous étudions le problème de définition, calcul et estimation de taux déntropie et de divergence généralisées pour des processus stochastiques à temps discret et à nombre d'états dénombrable. Les fonctionnelles considérées incluent la plupart de celles rencontrées dans la littérature, dont les entropies et divergences associées de Shannon, Rényi, Tsallis, Kullback-Leibler, Sharma-Mittal, etc. Usuellement, en théorie des processus, le taux est défini par moyenne sur le nombre d'unités de temps. Lorsque cette normalisation n'est pas adaptée au comportement asymptotique du processus, les taux induits sont triviaux. Nous montrons alors qu'une renormalisation adéquate permet d'obtenir des taux significatifs, étendant ainsi le champ de leurs nombreuses applications à une large classe de processus et de fonctionnelles. Des formules de taux explicites sont obtenues dès que le processus vérifie une hypothèse de régularité bien connue en théorie des systèmes dynamiques, la propriété de quasi-puissance. Pour les chaînes de Markov finies ou dénombrables, la propriété est vérifiée sous des conditions simples sur la matrice de transition de la chaîne. Le taux peut alors s'exprimer de différentes manières, à partir de la matrice de transition perturbée par le paramètre adéquat. (Travaux communs avec Gabriela Ciuperca, Loick Lhote et Philippe Regnault) 

Julien Clément CNRS GREYC Caen

Trier des clés: une analyse en moyenne du nombre de comparaisons de symboles.

On aborde classiquement l'analyse en moyenne d'algorithmes en s'intéressant à la complexité mesurée en nombre de comparaisons. Implicitement, On a alors des résultats de complexité du type: l'algorithme Quicksort est en O(n log n), le tri Insertion en O(n^2), ou encore le tri Radix en O(n log n). Ces affirmations se basent sur des hypothèses spécifiques - que les comparaisons entre les données (ou clés), pour les deux premiers, et les comparaisons entre symboles pour le troisième ont un coût unitaire et elles ont le mérite évident de présenter un tableau facile à assimiler de la complexité des algorithmes de tri. Cependant, ces hypothèses simplificatrices sont de fait discutables: elles ne permettent pas de comparer précisément les avantages et inconvénients d'algorithmes reposant sur des principes différents (i.e., ceux qui comparent les clés et ceux qui utilisent une représentation sous forme de suite de symboles) d'une manière qui soit totalement satisfaisante à la fois du point de vue de la théorie de l'information et du point de vue algorithmique. En effet, d'abord le calcul nést pas vu à son niveau le plus fondamental, cést-à-dire, par la manipulation de symboles élémentaires tels que le bit, l'octet, le caractère ou le mot-machine. De plus les analyses simplifiées ne sont pas toujours informatives dans beaucoup d'applications (bases de données ou traitement de la langue naturelle), où l'information est de nature hautement 'non atomique' , au sens quélle ne se réduit pas à un seul mot-machine. J'expose une méthode pour analyser en moyenne plusieurs algorithmes de tri et de sélection, pour le nombre de comparaisons de symboles. Les clés à traiter sont vues comme des séquences de symboles produites par un modèle de source général. Pour des sources particulières (comme les sources sans mémoire) on accède à une analyse en moyenne fine (avec le calcul de constantes explicites). Les méthodes et outils sont ceux de la combinatoire analytique. Collaboration avec Brigitte Vallée, Thu Hien Nguyen-Thi (initiée avec Philippe Flajolet).

Vincent Brault, Université de Grenoble

L'algorithme Largest Gaps, un algorithme théorique pour le modèle des blocs latents

Quels mots apparaissent plus dans les oeuvres de Charles Baudelaire que dans celles de Victor Hugo ? Les films de science-fiction sont-ils plus proches des films romantiques que ceux d'action ? Utilise-t-on la même partie du cerveau pour apprendre une langue étrangère et les tables de multiplication ? Les armoiries de la ville de Marseille ressemblent-elles plus à celles de Paris qu'à celles de Lyon ? Quels sont les gènes qui réagissent de la même façon suivant différents stress ? Les chiens ont-ils plus de points communs avec les chats qu'avec les loups ? Les politiciens sont-ils tous semblables ? Comment se forment les groupes sur les réseaux sociaux ? Ces quelques questions montrent l'étendue du champ d'applications du modèle des blocs latents. Le principe est de mettre en relation des objets (par exemple des livres, des films...) et des caractéristiques (le nombre de mots, le public...) puis de chercher une structure jointe pour obtenir des groupes. Dans cet exposé, nous étudierons l'adaptation de l'algorithme Largest Gaps utilisé par Channarond et al. (2012) dans le cadre des modèles de graphes aléatoires (cas où les lignes et les colonnes représentent les mêmes individus). Nous montrerons en particulier que cet algorithme renvoie des estimateurs du nombre de classes, des labels et des paramètres qui sont consistants sous certaines conditions. Puis, nous expliquerons en quoi ces résultats apportent un regard nouveau sur la façon de quantifier la difficulté d'une matrice et sur les problèmes d'asymptotique mais aussi les limites de son utilisation en pratique. Enfin, nous étudierons l'algorithme Largest Gaps sur des données simulées et réelles.

Rachid Senoussi INRA Avignon

Inférence statistique autour des facteurs climatiques et biologiques dans la dispersion spatiale et temporelle des thrips dans une serre de rosiers.

Dans la démarche d'une protection raisonnée en agriculture, il est important de comprendre  "statistiquement" le comportement dynamique et spatial des bio-agresseurs.  Dans le cadre précis du système rosiers/thrips en milieu confiné un modèle stochastique (et statistique) est construit pour estimer/quantifier et tester l'influence relative des facteurs environnementaux sur les différents stades de développement des thrips. Le but est de déterminer les meilleures "plages" spatiales et climatiques favorables à leur développement ou à leur agrégation afin d'affiner au mieux  les zones susceptibles de traitements. Travail collaboratif de Senoussi R., Fatnassi H., Pizzol J., Desneux N., Boulard T.  (Inra PACA). 

Philippe Regnault Université Reims-Champagne-Ardennes, Reims

Tests d'indépendance basés sur les informations mutuelles associées aux phi-divergences. 

Dans cet exposé, nous définissons des tests d'indépendance par seuillage d'informations mutuelles généralisées, dans un contexte semi-paramétrique. Précisément, l'information mutuelle associée à une phi-divergence est estimée en mettant à profit la représentation duale de la divergence. Les propriétés asymptotiques des estimateurs sont établies, incluant la consistance, la loi asymptotique et un principe de grandes déviations. Les tests d'indépendance basés sur ces estimateurs sont comparés en termes défficacité asymptotique (au sens de Bahadur). 

Soutenance de thèse de Justine Lequesne

Tests statistiques basés sur la théorie de l'information. Applications en biologie et en démographie.

 

Journées de novembre 2014 à Caen à Caen commune avec le séminaire Analyse et Physique Mathématique du LMNO

Victor Konev U. Tomsk

Quick Detection of Parameter Changes in Autoregressive Processes

By using sequential estimation theory, the talk provides a general approach to the problem of quick detection of abrupt changes of the parameters in stochasic discrete time systems specified by autoregressive processes. There is a large literature on detection algorithms in such systems but relatively little work on the statistical properties of the detection procedures beyond very simple models. The distributions of noises in the process are assumed to be unknown. In this case it seems natural to proceed in the construction of the decision rule from the least squares functional of residuals whose increments exhibit changes in the behaviour after the disruption.The key idea is to apply sequential estimates for accumulating information on the disruption in the system. The procedure enables one to control the probabilities of false alarms and false tranquility. The optimization problem of procedure parameters is considered.

Max Olivier Hongler Ecole Polytechnique Federale de Lausanne

Titmouse versus Robins' Behavioral Model for Innovation Propagation

Inspired by the observation that non-territorial songbirds (titmouses) propagate innovation (i.e., how to drill a hole in the cover of a milk bottle) more efficiently than territorial fellows (robins), we propose a stylized mathematical model of knowledge propagation founded on an analytically solvable multi-agent system. Individual agent dynamical state is modeled via a scalar variable which aggregates the agent's time-dependent state of knowledge. Agent's information is enhanced via imitation process, the efficiency of which is tuned by the number of leading fellows (i.e., those with higher state of knowledge) that each agent finds in a neighboring imitation range. Territorial agents (the robins) deploy comparatively small imitation range, which leads to an evanescent diffusive propagation wave of knowledge. This vanishing propagation contrasts with the non-territorial fellows (the titmouses), which implement significantly longer imitation ranges. From these long range interactions, one observes the self-emergence of a stable, constant velocity, collective propagating wave of knowledge. These drastically different dynamic behaviors suggest the existence of a critical imitation range where a behavioral phase transition occurs.

Christophe Vignat Université Paris-Sud Orsay et Tulane University

Ordonnancement d’opérateurs non-commutatifs et fonctions spéciales

Étant donnés deux opérateurs non-commutatifs p et q, il est facile de montrer que tout mot équilibré en p et q s’écrit comme un polynôme du mot élémentaire pq+qp. Dans un article de 1988, Bender et Dunne ont caractérisé les polynômes associés a certaines combinaisons linéaires - appelées ordonnancements - de mots équilibrés, tels que les ordonnancements symétriques, de Born-Jordan et de Weyl. Ils ont ensuite posé la question de la généralisation de cette approche a un ordonnancement arbitraire, et de la caractérisation des polynômes associés. Je montrerai la solution générale a ce problème, laquelle fait intervenir des familles classiques de polynômes telles que les polynômes continus de Hahn les polynômes de Pochhammer.

suivis d'une discussion autour des travaux récents sur la "maxentisation" menés au sein du GT EMS par Valerie Girardin et Justine Lequesne LMNO UCBN, Jean Francois Bercher ESIEE Marne la Vallée, Philippe Regnault Université de Reims Champagne Ardennes, Steeve Zozor GIPSA-LAB Grenoble.

 

Journées de mai 2014 à l'ESIEE Paris, Noisy le Grand,

organisation locale Jean-François Bercher

Exposés de Steeve Zozor GIPSA-LAB Grenoble et Michèle Basseville IRISA CNRS Rennes

Soutenance de thèse de Michèle El Gheche

Proximal methods for convex minimization of Phi-divergences. Application to computer vision

 

Journée de mars 2014 à Caen

Renaud Leplaideur, université de Brest

A propos de la convergence vers les états fondamentaux à température zéro.

En formalisme thermodynamique, une mesure d'équilibre maximise l'énergie libre pour un potentiel donné.

Lorsque la fonction potentiel est Hölder, la fonction pression qui associe à beta le maximum des énergies libres pour beta est analytique. Elle admet une asymptote en l'infini de pente donnée par le maximum de l'intégrale du potentiel par rapport à la mesure. Le problème de la convergence à température zéro consiste à étudier ce qui se passe pour la mesure d'équilibre dépendant de beta lorsque beta tend vers l'infini. On montre que tout point d'accumulation doit nécessairement être une mesure qui maximise l'intégrale pour le potentiel considéré mais aussi qui a une entropie maximale parmi ces mesures. Toutefois, cette condition n'est pas suffisante.

Philippe Regnault, université de Reims

Estimation par maximum de Lq-vraisemblance, test paramétrique par rapport de Lq-vraisemblance et information de Fisher généralisée.

Journée de mars 2013 à l'ESIEE Paris, Noisy le Grand,

organisation locale Jean-François Bercher

Jean Francois Bercher, ISIEE

Sur une version multidimensionnelle d'une borne de Cramér-Rao généralisée, les relations d'incertitude associées et certaines propriétés de l'information de Fisher

Patrice Bertail, Université de Nanterre

Minimisation de l'énergie empirique pour des parametres Hadamard différentiables

 

Journée de mai 2012 à Caen

Patrice Bertail, Université de Nanterre

Fonction de répartition empirique et distance de Hellinger.

Justine Lequesne, Université de Caen

Divergence de Kullback-Leibler et tests d'entropie.

Valérie Girardin, Université de Caen

Sur la fonction Lambda et la renormalisation de taux d'entropie.

Journée d'avril 2012 à l'ESIEE Paris, Noisy le Grand,

organisation locale Jean-François Bercher

Philippe Regnault, Université de Caen

Sur la géometrie riemanienne, la distance entre les spheres d'entropie et les applications en statistique.

Loick Lhote, ENSICAEN

Sur la fonction Lambda et la renormalisation de taux d'entropie.

Discussion autour de travaux récents sur la "maxentisation" menés au sein du GT EMS

Journées de novembre 2011 à Caen

Brigitte Vallée GREYC Université de Caen

Sources générales, arbres, discipline et entropie

En algorithmique, on manipule très souvent des mots, et on cherche à construire des structures de données (souvent des arbres) qui permettent de les manipuler efficacement. Et si on veut faire de l’algorithmique ”réaliste”, il faut considérer que les mots sont produits par une source ”générale” et expliquer en quoi les propriétés probabilistes de la source se répercutent sur la forme des arbres, notamment leur ”longueur de cheminement”. J’expliquerai informellement les principales étapes de la recherche de notre équipe dans ce domaine: (a) Donner un sens à ce qu’on appelle une source générale, opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques. (b) Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet. (c) Exhiber une propriété importante de la source, appelée ”discipline”, et, dans le cas des sources dynamiques, donner des conditions suffisantes qui entraînent la discipline. (d) Montrer que, pour une source disciplinée, la longueur moyenne de cheminement des arbres fait intervenir l’entropie de la source.

Raimondo Manca Université La Sapienza Roma

Choose among homogeneous and parametric or non-parametric non-homogeneous semi-Markov models

The choice of the model to be applied to study the dynamic evolution of a complex phenomenon by means of a semi-Markov process is not simple. Many conditions will influence this choice. We will show how to select among the different possibilities that the semi-Markov processes offer. Furthermore we will explain the reasons why some model should be applied to study better than the other models the evolution of the observed phenomenon. Different examples will be presented.

Vlad barbu Université de Rouen

Modèles cachés de type semi-markovien

Dans cet exposé, nous nous intéressons aux modèles cachés de type semimarkovien, aux questions d’estimation associées et aux possibles domaines d’application. D’abord, nous présentons un système canonique pour lequel les processus markoviens ou semi-markoviens cachés sont des outils adéquats de modélisation. Nous introduisons également les notations et les définitions correspondantes. Ensuite nous nous intéressons à l’estimation d’un tel modèle. Nous présentons des résultats sur la convergence et la normalité asymptotique des estimateurs du maximum de vraisemblance obtenus pour les caractéristiques du modèle (noyau semi-markovien, loi conditionnelle, etc.). D’un point de vue pratique, l’obtention des estimateurs est réalisée via un algorithme de type EM que nous présentons brièvement. L’intérêt de notre approche réside, d’une part, dans la richesse de modélisation de ces processus et, d’autre part, dans la généralisation apportée par le fait qu’on s’affranchit partiellement de l’hypothèse de Markov, trop contraignante pour un certain nombre d’applications.

Jan Bulla Université de Caen

Clustering de données longitudinales par un modèle de Hurdle dynamique semi-markovien

The models presented deal with the analysis of a longitudinal dataset of buying behavior, i.e., we record a set of customer informations over several time periods. Such a data structure shows a number of characteristics which need to be described as the dependence of dependent variables on covariates, serial dependence and heterogeneity among the customers. Several model specifications have been proposed to model correlation in a longitudinal setting; see e.g. Molenberghs et al. (2010). In our empirical study, customers may be subject to several factors affecting their buying behavior, such as advertisements or promotional offers. Over time, the influence of these factors on the costumer’s buying behavior may vary in an unknown (unobserved) way. In this setting, the hurdle-Poisson Hidden Markov Model (Alf´o and Maruotti, 2010), a dynamic extension of the classical hurdle model (Mullahy, 1986), can be applied. We analyze the performance of this model and show how to extend the latent process from a Markov to a semi-Markov chain using a computationally convenient and easily deductible approach inspired by Durbin et al. (1998) and Langrock & Zucchini (2011). As a by-product of the model estimation algorithm, it is possible to classify customers into several relationship states.

Collaboration avec Antonello Maruotti

Jean-François Bercher ISIEE, Marne la Vallée

Sur un chemin défini par une distribution escort généralisée

Dans cette présentation, j’introduirai un problème de transition entre deux états caractérisés par leurs densités de probabilité. Pour un certain modèle de cette transition, on trouvera que la densité d’équilibre est définie par une distribution compagne (dite ”escort distribution”). On montrera que la divergence de Rényi intervient alors comme sous produit de la construction. Cette distribution compagne définit une courbe reliant les deux états. Le long de cette courbe, la divergence de Jeffreys, comme la divergence thermodynamique (définie comme un flux d’information de Fisher), s’exprime aisément en fonction de la divergence de Rényi. Lorsque l’état final est ajustable, il s’ensuit qu’une approche raisonnable pour choisir cet état est la minimisation de la divergence de Rényi. Dans le cas où cet état doit vérifier certaines contraintes de moments, on verra que la densité correspondante se met sous la forme d’une gaussienne généralisée.

Guglielmo D’Amico, Università di Chieti-Pescara G. D’Annunzio, Italy

Mesure d'inégalités de revenus dynamique : illustration sur quelques pays européens

In this presentation, we propose a stochastic model that makes dynamic the classical inequality indices usually applied in a static framework. We will expose the general theory, and then apply the model to data from different European countries. In particular Eurostat data for Germany, Greece and Italy will be considered. For each country, we stratify the population by age in five groups: age 0-17, 18-24, 25-49, 50-64 and over 64, in the way adopted by Eurostat. Within each group, in each country, we evaluate the Dynamic Theil’s Entropy that allows us to recover the total inequality in the country. The forecasted inequalities are compared. The obtained results suggest that the adoption of a dynamic model plays a fundamental role in the programming of economic policies geared to the containment of economic inequality. Finally, we will give some conclusions and further research suggestions.

Soutenance de thèse de Philippe Regnault, Université de Caen

Différents problèmes liés à l'estimation de l'entropie de Shannon d'une loi, d'un processus de Markov.