Réduction de dimension

Réduction de dimension

La réduction de dimension joue un rôle important dans la résolution de problèmes de Machine Learning large échelle où les données d’entrées consistent en un très grand nombre d’échan tillons de très grande dimension. Dans la plupart des cas, la dimension intrinsèque des données est très faible comparée à leur dimension extrinsèque, (i.e., dimension de l’espace d’entrée). La réduction de dimension vise ainsi à projeter les échantillons d’entrée dans un espace de dimen sion plus petite de sorte à retenir optimalement l’information portée par les données originales.

L’objectif final est généralement que l’erreur induite sur les étages suivants de la chaîne de trai tement soit minimale, voire progresse (e.g, classification, régression, reconstruction, etc). La plupart des méthodes de réduction de dimension classiques on été formulées pour des en vironnements centralisés, où toutes les données sont disponible en un unique site et où la solution peut être calculée par une seule machine.

Les approches centralisées supposent en particulier que cette unique machine possède une mémoire suffisante pour stocker tous les résultats inter médiaires. Cependant, cette solution est irréaliste dans un grand nombre de cas d’application, où l’ensemble des échantillons d’entraînement forme une gigantesque matrice. Par exemple, dans les applications biomédicales, multimédia ou d’imagerie satellitaire, cette matrice peut occuper plusieurs Tera-octets.

Par ailleurs, les approches centralisées ne sont pas utilisables lorsque les échantillons proviennent par nature d’un processus distribué et sont donc par définition réparties sur plusieurs machines. Cela justifie par conséquent la conception d’algorithmes de réduction de dimension distribués, qui tiennent compte de cette répartition des données sur un réseau de multiples nœuds de calcul

En environnement distribué, deux scénarios typiques peuvent se présenter. Dans le premier, que nous appellerons « Échantillons Distribués » (ED), les échantillons sont dispersés sur les nœudsdecalcul et chaquenœudpossèdetoutesles entrées de chacun deses échantillons. C’est le scénario le plus courant. Dans le deuxième scénario, que nous nommerons « Coordonnées Distri buées » (CD), chaque nœud possède une partie des entrées de chaque échantillon.

Un échantillon donné n’est alors jamais observable dans sa totalité en un nœud donné, chacune de ses com posantes pouvant être hébergée par un nœud différent. Ce cas survient typiquement lorsque les échantillons sont des mesures successives de plusieurs grandeurs issues d’un même phénomène géographiquement diffus.

Dans ce chapitre, nous présentons l’algorithme AGPCA (Asynchronous Gossip Principal Components Analysis), qui calcule l’Analyse en Composantes Principales (Principal Compo nents Analysis, PCA) d’un jeu d’échantillon reparti sur un réseau de manière décentralisée et- 93 RÉDUCTION DE DIMENSION asynchrone. Nous montrons qu’AGPCA est adapté aux deux scénarios ED et CD. Sous cer taines conditions de rang, nous démontrons théoriquement et expérimentalement que la solution produite en chaque nœud est identique à celle produite par une PCA centralisée exécutée sur l’ensemble des données du réseau.

Le reste de ce chapitre est organisé comme suit : dans la section 1 nous présentons diverses approches pour la réduction de dimension en environnement centralisé, avant de nous concentrer sur l’Analyse en Composantes Principales. La section 2 recense différentes algorithmes de PCA distribuée. Dans la section 3, nous introduisons une approche naïve de la PCA décentralisée et asynchrone,

nommée « Late PCA ». Dans la section 4, nous détaillons l’algorithme AGPCA qui lève les limitations soulevées par Late PCA. Dans la section 5, nous montrons qu’AGPCA est également adapté au scenarios CD. 3.1 Réduction de dimension centralisée Étant donné une matrice d’échantillons X D n, la réduction de dimension consiste à produire des représentations Y q n de dimension q où q D, qui préservent au mieux certaines propriétés globales et/ou locales des données d’entrée.

En dépit de cet objectif général commun, chaque technique de réduction de dimension définit sa propre notion des « propriétés à préserver ». De ce fait, l’évaluation et la comparaison des performances des techniques de réduction de dimension prises isolément pose généralement des problèmes de pertinence des résultats quan titatifs. La notion même de performance appliquée aux méthodes de réduction de dimension est souvent ambiguë,

car les représentations réduites sont la plupart du temps des produits intermé diaires qui servent d’entrée à un prédicteur (classificateur, régresseur, etc). Dans ce cas, il est souvent plus pertinent d’évaluer les performances en sortie du prédicteur, pour lequel on pos sède une vérité de terrain (éventuellement incomplète). Par exemple, il est fréquent d’évaluer la réponse d’un classificateur basique (e.g., plus proche voisin)

sur un jeu de données labellisées pour attester de la pertinence des représentations réduites sur une tâche réelle. Une exception notable est la tâche de visualisation, qui exploite directement les représentations compressées, en cherchant à préserver les distances, les groupements ou d’autres propriétés locales aux don nées d’entrée. Notons toutefois qu’étant limitée à trois dimensions de sortie, la visualisation ne permet pas de caractériser les performances en grandes dimensions.

Parmi les propriétés les plus fréquemment considérées, on trouve la préservation des dis tances, des dissimilarités, des relations de voisinage, des groupements (maximisation de la sépa ration entre groupe et minimisation de la variance intra-groupe) ou de la densité de probabilité des données.

Chacun de ces critères apporte ses avantages et ses inconvénients, qui se traduisent par des succès sur certaines tâches et des échecs sur d’autres tâches. Ainsi, certaines méthodes très performantes sur des données synthétiques échouent totalement sur des données naturelles. Pour une étude comparative approfondie, le lecteur pourra se référer à [238