Catégorisation non supervisée et estimation de densité

La catégorisation non-supervisée est une tache d’apprentissage statistique très populaire massi- vement utilisée entre autres en traitement du signal, en reconnaissance de formes et en fouille de données. Elle consiste à regrouper en catégories un ensemble d’échantillons donnés en en- trée. L’objectif est d’assurer une cohérence intra-catégorie maximale tout en garantissant une séparation inter-catégorie optimale. Un modèle de catégorisation est généralement associé à une fonction de coût qui mesure la fidélité avec laquelle il rend compte de la densité de distribution des échantillons dans l’espace d’entrée. Celle-ci peut se contenter d’un critère de cohésion intra- catégorie (e.g., variance intra-catégorie) ou lui adjoindre un critère de séparation inter-catégories (catégorisation à vaste marge). Dans une première phase dite d’apprentissage ou d’entraînement, les paramètres du modèle sont estimés de sorte à minimiser la fonction de coût sur un ensemble d’échantillons d’entraî- nement. Une fois les paramètres optimaux obtenus avec suffisamment de précision, le modèle peut être utilisé dans une deuxième phase dite d’inférence pour déterminer la ou les catégories correspondant à un nouvel échantillon jusqu’ici non-présenté. Dans ce chapitre, nous nous intéressons au problème de catégorisation distribuée, qui étend la catégorisation classique centralisée au cas où l’ensemble d’échantillons d’entraînement est re- parti sur de multiples nœuds de calcul connectés en réseau. On souhaite alors obtenir un modèle optimal de l’ensemble des échantillons du réseau, pris comme un tout. Notons que dans ce cha- pitre nous considérons uniquement le cas où ce sont les échantillons qui sont distribués. Nous ne considérons pas le cas où les composantes de ces échantillons sont distribuées, cas qui corres- pond typiquement au scénario où tous les nœuds observent en simultané des grandeurs diverses émanant d’un même phénomène physique ou un champ de valeurs reparties géographiquement (e.g., météorologique, sismique, etc).

Ces deux algorithmes sont bâtis sur le protocole Gossip asynchrone AGAVG introduit dans le chapitre 1. Ils s’inspirent pour une large part de leurs homologues centralisés, largement utilisés depuis des décennies : K-means [165] et Expectation-Maximization (EM) [70]. Dans la section 1, nous introduisons formellement les problèmes de catégorisation et présen- tons une sélection des algorithmes centralisés les plus utilisés. Dans la section 2, nous exposons le problème de catégorisation distribuée, ainsi qu’un éventail d’algorithmes dédiés à cette tache. Les section 3 et 4 sont respectivement consacrées à la présentation des deux algorithmes que nous proposons, AGKM et AGEM. Leur analyse théorique est détaillée en section 5. Les résul- tats de leur étude expérimentale sont rapportés en section 6, avant de conclure ce chapitre en section 7. , ap- pelés prototypes (codeword en littérature anglophone), qui minimisent la distance Euclidienne moyenne entre tout échantillon d’entraînement et son prototype le plus proche. Cette fonc- tion coût est nommée Erreur Quadratique Moyenne (Mean Squared Error, MSE) et s’exprime comme suit :

Il existe de nombreuses variantes de K-means [23, 134]. Pour les problèmes de grande di- mensions, la distance Euclidienne offre généralement de mauvaises performances. Ceci est du au phénomène de concentration des distances qui accompagne l’augmentation de la dimension- nalité (malédiction de la dimensionnalité). En effet, dans les espaces de grande dimension, les distances entre échantillons tendent à se concentrer autour d’une même valeur. Cela conduit à la formation de hubs et de anti-hubs qui désignent respectivement les points qui deviennent plus proches voisins de quasiment tous les échantillons (hubs) et les points qui ne sont les plus proches voisins d’aucun échantillon (anti-hubs) [205]. L’apparition de ces points particuliers a des conséquences désastreuses sur les performances de catégorisation. Les métriques non- euclidiennes (normes `Au lieu d’appliquer l’étape 1 à l’ensemble des échantillons, on peut se restreindre à un sous-échantillon (aléatoire ou non) et utiliser un sous-échantillon différent à chaque itération. Le cas extrême, nommé quantification vectorielle stochastique (Stochastic Vector Quantization, SVQ), consiste à ne prendre qu’un seule échantillon aléatoire à chaque itération. Dans ce cas, la convergence n’est garantie que si l’on ajoute un terme d’inertie à l’étape de mise à jour du dictionnaire, sous la forme d’un pas d’apprentissage décroissant. Autrement, l’algorithme ne converge pas vers un minimum stable mais oscille autour d’un optimum local. SVQ peut être étendu au scenario où les échantillons ne sont pas disponibles en début d’algorithme mais sont capturés un par un pendant la phase d’apprentissage elle même. On parle alors de quantification « en ligne » (online).