Information k-means, fragmentation and syntax analysis. A new approach to unsupervised machine learning - ENSAE Paris Accéder directement au contenu
Thèse Année : 2020

Information k-means, fragmentation and syntax analysis. A new approach to unsupervised machine learning

Information k-means, fragmentation et analyse syntaxique. Une nouvelle approche de l’apprentissage non supervisé

Résumé

Information k-means is a new mathematical framework that extends the classical k-means criterion, using the Kullback divergence as a distortion measure. The fragmentation criterion is an even broader extension where each signal is approximated by a combination of fragments instead of a single center. Using the fragmentation criterion as a distortion measure, we propose a new fragmentation algorithm for digital signals, conceived as a lossy data compression scheme. Our syntax analysis is based on two principles: factorization and relabeling of frequent patterns. It is an iterative scheme, decreasing at each step as much as possible the length of the representation of the training set. It produces for each signal a syntax tree, providing a multi-level classification of the signal components. We tested the method on grey level digital images, where it was possible to label successfully translated patterns and rotated patterns. This lets us hope that transformation invariant pattern recognition could be approached in a flexible way using a general purpose data compression criterion. From a mathematical point of view, we derived two kinds of generalization bounds. First we defined an implicit estimator based on an implicit statistical model, related to our lossy data compression scheme. We proved a lemma relating the data compression rate and the distortion level of the compression algorithm with the excess risk of the statistical estimator. This explains why our syntax trees may be meaningful. Second, combining PAC-Bayesian lemmas with the kernel trick, we proved non asymptotic dimension-free generalization bounds for the various information k-means and information fragmentation criteria we introduced. For instance, in the special case of the classical k-means criterion, we get a non asymptotic dimension free generalization bound of order O( k log(k) / n )^{1/4}) that gives the best sufficient consistency condition, namely that the excess risk goes to zero when (k log(k) / n) goes to zero. Using a new kind of PAC-Bayesian chaining, we also proved a bound of order O( log(n/k) sqrt{k log(k)/n} ).
Le critère de l'information k-means étend le critère des k-means en utilisant la divergence de Kullback comme fonction de perte. La fragmentation est une généralisation supplémentaire permettant l'approximation de chaque signal par une combinaison de fragments. Nous proposons un nouvel algorithme de fragmentation pour les signaux numériques se présentant comme un algorithme de compression avec perte. A l'issue de ce traitement, chaque signal est représenté par un ensemble aléatoires de labels, servant d'entrée à une procédure d'analyse syntaxique, conçue comme un algorithme de compression sans perte. Nous avons testé la méthode sur des images en niveaux de gris sur lesquelles il a été possible de détecter des configurations translatées ou transformées par une rotation. Ceci donne l'espoir d'apporter une réponse à la reconnaissance invariante par transformations fondée sur un critère de compression très général. D'un point de vue mathématique, nous avons prouvé deux types de bornes. Tout d'abord, nous avons relié notre algorithme de compression à un estimateur implicite d'un modèle statistique lui aussi implicite, à travers un lemme, prouvant que le taux de compression et le niveau de distorsion de l'un sont reliés à l'excès de risque de l'autre. Ce résultat contribue à expliquer la pertinence de nos arbres syntaxiques. Ensuite, nous établissons des bornes de généralisation non asymptotiques et indépendantes de la dimension pour les différents critères des k-means et critères de fragmentation que nous avons introduits. Nous utilisons pour cela des inégalités PAC-Bayésiennes appliquées dans des espaces de Hilbert à noyau reproduisant. Par exemple dans le cas des k-means classiques, nous obtenons une borne en O(k log(k) / n)^{1/4}) qui fournit la meilleure condition suffisante de consistance, à savoir que l'excès de risque tend vers zéro quand O(k log(k) / n) tend vers zéro. Grâce à une nouvelle méthode de chaînage PAC-Bayésien, nous prouvons aussi une borne en O(log(n/k) sqrt{k log(k)/n}).
Fichier principal
Vignette du fichier
80953_APPERT_2020_archivage.pdf (5.62 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)
Loading...

Dates et versions

tel-03015285 , version 1 (19-11-2020)

Identifiants

  • HAL Id : tel-03015285 , version 1

Citer

Gautier Appert. Information k-means, fragmentation and syntax analysis. A new approach to unsupervised machine learning. Machine Learning [stat.ML]. Institut Polytechnique de Paris, 2020. English. ⟨NNT : 2020IPPAG011⟩. ⟨tel-03015285⟩
598 Consultations
188 Téléchargements

Partager

Gmail Facebook X LinkedIn More