ROUGH DRAFT authorea.com/6828
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Projections aléatoires appliquées à la réduction de dimension

    Abstract

    Lorsque la trop grande dimension \(d\) des données empêchent la mise en oeuvre de méthodes de traitements classiques , même les méthodes de réduction de dimension les plus courantes, telles que l’analyse en composantes principales (PCA) sont inapplicables. Nous nous interessons ici à la projection des données suivant des matrices aléatoires. Nous vérifierons les performances que permettent les projections aléatoires et notamment leurs propriété de conservation des distances. Ce travail se base principalement sur l’article de Ella Bingham et Heikki Mannila (Bingham 2001).

    Approche théorique

    Analyse en composante principale

    L’analyse en composante principale est une méthode statistiquement optimale de reduction de dimension, consistant à maximiser la variation (quantifiée le plus souvent par la variance) des données dans le sous-espace image de la projection.

    En considérant des données sous la forme d’une matrice \(X\) de taille \( N \times d\), on cherche alors à obtenir \(E\) la matrice dont les colonnes sont les vecteurs propres de la matrice de covariance \(X^TX\). On a donc : \( X^TX = E\Lambda E^T \) avec \(\Lambda\) diagonale. La réduction de dimension s’effectue en conservant la projection sur sous-espace correspondant aux valeurs propres les plus grandes : \( X_{PCA} = X E_K^T \)

    Cette décomposition de la matrice de covariance (de taille \( d\times d\)) est coûteuse, et difficilement applicable en très grande dimension.

    Projection aléatoire

    Une alternative à l’approche précédente est de considérer une projection suivant des vecteurs aléatoires. Si \(R\) est une matrice de taille \(d\times k\) formée par k vecteurs unitaires, alors on peut construire une version réduite des données \(X\) en dimension \(k\) en calculant : \(X^{RP}_{N\times k} = X_{N\times d} R_{d\times k} \)

    La complexité de cette opération est en \(O(dkN)\). La simplicité de cette approche réside dans le fait qu’une matrice aléatoire gaussienne se revèle être proche de l’orthogonalité. Et l’intérêt de cette méthode est confirmée par le lemme de Johnson-Lindenstrauss, qui assure que les distances entre les points peuvent être quasiment conservées lors de la reduction de dimension, en remettant à l’echelle les données transformées avec un facteur bien choisi. En l’occurrence dans le cas qui nous intéresse ici, R peut être générée de manière à ce que ses termes suivent une loi gaussienne \(\mathcal{N}(0,\frac{1}{\sqrt{k}})\).

    Densité de la matrice de projection

    Pour rendre la projection un peu plus rapide encore, dans le cas de données de très grande dimension, il est envisageable de faire en sorte que la matrice \(R\) soit fortement creuse(Li 2006). Cette approche consiste à remplacer la variable aléatoire gaussienne par :

    \( r_{ij} = \left\{\begin{matrix} -\sqrt{\frac{s}{k}} & &1/2s\\ 0 &\textup{with probability} & 1-1/s\\ +\sqrt{\frac{s}{k}} & & -1/2s \end{matrix}\right \)

    La valeur recommandée par Ping Li et al. est \(s = d\), permettant d’obtenir une matrice \(R\) de densité \(1/d\).

    Nous allons vérifier ces résultats par des simulations sur des données images et textuelles.

    Application sur les images

    On considère des images de taille \(50 \times 50 \) (\(d = 2500\)). Pour les méthodes de réduction de dimension évoquées et des valeurs de \(k < 200\), on compare les distances euclidiennes entre les données transformées avec celles entre les images originales.

    \label{fig}Conservation de la distance euclidienne entre images après réduction de la dimension

    En pointillés sont représentés les bornes des intervalles de confiance à 95 %