Directeur de thèse : François CAYRE
École doctorale : Electronique, electrotechnique, automatique, traitement du signal (EEATS)
Spécialité : Signal, image, parole, télécoms
Structure de rattachement : Grenoble-INP
Établissement d'origine : INPG - ENSE3
Financement(s) : Contrat doctoral ; Sans financement
Date d'entrée en thèse : 01/10/2015
Date de soutenance : 25/10/2018
Composition du jury :
Jean-Marc GIRAULT
Maître de Conférences, Université François-Rabelais, Rapporteur
Thierry LECROCQ
Professeur, Université de Rouen-Normandie, Rapporteur
Steeve ZOZOR
Directeur de Recherche, CNRS, Examinateur
Pierre CHAINAIS
Professeur, Ecole centrale de Lille, Examinateur
Nicolas LE BIHAN
Directeur de Recherche, CNRS, Directeur de thèse
François CAYRE
Maître de Conférences, Grenoble INP, Co-directeur de thèse
Résumé : RÉSUME DE THÈSE
Les données sous forme de chaîne de symboles sont très variées
(ADN, texte, EEG quantifié,
) et ne sont pas toujours modélisables. Une
description universelle des chaînes de symboles indépendante des
probabilités est donc nécessaire. La complexité de Kolmogorov a été
introduite en 1960 pour répondre à cette problématique. Leconcept est
simple : une chaîne de symboles est complexe quand il n'en existe pas
une description courte. La complexité de Kolmogorov est le pendant
algorithmique de l'entropie de Shannon et permet de définir la théorie
algorithmique de l'information. Cependant, la complexité de Kolmogorov
n'est pas calculable en un temps fini ce qui la rend inutilisableen
pratique.
Les premiers à rendre opérationnelle la complexité de Kolmogorov
sont Lempel et Ziv en 1976 qui proposent de restreindre les opérations
de la description. Une autre approche est d'utiliser la taille dela
chaîne compressée par un compresseur sans perte. Cependant ces deux
estimateurs sont mal définis pour le cas conditionnel et le cas joint,
il est donc difficile d'étendre la complexité de Lempel-Ziv ou les
compresseurs à la théorie algorithmique de l'information.
Partant de ce constat, nous introduisons une nouvellemesure
d'information universelle basée sur la complexité de Lempel-Ziv appelée
SALZA. L'implémentation et la bonne définition de notremesure
permettent un calcul efficace des grandeurs de la théorie algorithmique
de l'information.
Les compresseurs sans perte usuels ont été utilisés par Cilibrasi
et Vitányi pour former une métrique universelle très populaire : la
distance de compression normalisée [NCD]. Dans le cadre de cette
application, nous proposons notre propre estimateur, la NSD, et montrons
qu'il s'agit d'une semi-distance universelle sur les chaînes de
symboles. L'application à de la classification hiérarchique montre que
la NSD surclasse la NCD en s'adaptant naturellement à davantage de
diversité des données et en définissant le conditionnementadapté grâce
à SALZA.
En utilisant les qualités de prédiction universelle de la
complexité de Lempel-Ziv, nous explorons ensuite les questions
d'inférence de causalité. Dans un premier temps, les conditions
algorithmiques de Markov sont rendues calculables grâce à SALZA. Puis en
définissant pour la première l'information dirigéealgorithmique, nous
proposons une interprétation algorithmique de la causalité de Granger
algorithmique. Nous montrons, sur des données synthétiques et réelles,
la pertinence de notre approche.