Analyse en composantes principales (ACP) et Auto Encoders

Cet algorithme est proposé dans [Song1997]. Autrefois réseau diabolo, le terme auto-encoder est plus utilisé depuis l’avénement du deep learning. Il s’agit de compresser avec perte un ensemble de points. L”ACP est une forme de compression linéaire puisqu’on cherche à préserver l’information en projetant un nuage de points de façon à maximiser l’inertie du nuage. Les auto-encoders fonctionnent sur le même principe avec des modèles non linéaires.

subsection{Principe}

L’algorithme implémentant l’analyse en composantes principales est basé sur un réseau linéaire dit « diabolo », ce réseau possède une couche d’entrées à \(N\) entrées, une couche cachée et une couche de sortie à \(N\) sorties. L’objectif est d’apprendre la fonction identité sur l’espace \(\mathbb{R}^N\). Ce ne sont plus les sorties qui nous intéressent mais la couche cachée intermédiaire qui effectue une compression ou projection des vecteurs d’entrées puisque les entrées et les sorties du réseau auront pour but d’être identiques.

Figure F1 : Principe de la compression par un réseau diabolo

\begin{picture}(241,100)(0,-10) \put(1,1) {\framebox(40,22){\footnotesize \begin{tabular}{c}vecteur \\ $X \in \mathbb{R}^N$ \end{tabular}}} \put(85,-9) {\framebox(45,32){\footnotesize \begin{tabular}{c}vecteur \\ $Y \in \mathbb{R}^M$ \\ et $M < N$ \end{tabular}}} \put(200,1) {\framebox(40,22){\footnotesize \begin{tabular}{c}vecteur \\ $Z \approx X$ \end{tabular}}} \put(20,40) {\framebox(90,45){\footnotesize \begin{minipage}{30mm} première couche du réseau diabolo~: \textbf{projection (ou compression)} \end{minipage}}} \put(120,40) {\framebox(90,45){\footnotesize \begin{minipage}{30mm} seconde couche du réseau diabolo~: \textbf{reconstitution (ou décompression)} \end{minipage}}} \put(30,23) {\vector(1,1){17}} \put(130,23) {\vector(1,1){17}} \put(90,39) {\vector(1,-1){17}} \put(190,39) {\vector(1,-1){17}} \end{picture}

La figure suivante illustre un exemple de compression de vecteur de \(\mathbb{R}^3\) dans \(\mathbb{R}^2\).

Figure F2 : Réseau diabolo : réduction d’une dimension

\begin{picture}(130,75)(0,0) \put(20,10) {\circle{20}} \put(20,40) {\circle{20}} \put(20,70) {\circle{20}} \put(18,8) {\makebox(5,5){\footnotesize $x_1$}} \put(18,38) {\makebox(5,5){\footnotesize $x_2$}} \put(18,68) {\makebox(5,5){\footnotesize $x_3$}} \put(65,25) {\circle{20}} \put(65,55) {\circle{20}} \put(63,23) {\makebox(5,5){\footnotesize $z_{1,1}$}} \put(63,53) {\makebox(5,5){\footnotesize $z_{1,2}$}} \put(110,10) {\circle{20}} \put(110,40) {\circle{20}} \put(110,70) {\circle{20}} \put(108,8) {\makebox(5,5){\footnotesize $z_{2,1}$}} \put(108,38) {\makebox(5,5){\footnotesize $z_{2,2}$}} \put(108,68) {\makebox(5,5){\footnotesize $z_{2,3}$}} \drawline(30,10)(55,25) \drawline(30,40)(55,55) \drawline(30,10)(55,55) \drawline(30,70)(55,25) \drawline(30,70)(55,55) \drawline(30,40)(55,25) \drawline(75,25)(100,10) \drawline(75,25)(100,40) \drawline(75,25)(100,70) \drawline(75,55)(100,10) \drawline(75,55)(100,40) \drawline(75,55)(100,70) \end{picture}

Ce réseau possède 3 entrées et 3 sorties Minimiser l’erreur \(\sum_{k=1}^N E\left( X_{k},X_{k}\right)\) revient à compresser un vecteur de dimension 3 en un vecteur de dimension 2. Les coefficients de la première couche du réseau de neurones permettent de compresser les données. Les coefficients de la seconde couche permettent de les décompresser.

La compression et décompression ne sont pas inverses l’une de l’autre, à moins que l’erreur (1) soit nulle. La décompression s’effectue donc avec des pertes d’information. L’enjeu de l’ACP est de trouver un bon compromis entre le nombre de coefficients et la perte d’information tôlérée. Dans le cas de l’ACP, la compression est « linéaire », c’est une projection.

Problème de l’analyse en composantes principales

L’analyse en composantes principales ou ACP est définie de la manière suivante :

Problème P1 : analyse en composantes principales (ACP)

Soit \(\pa{X_i}_{1 \infegal i \infegal N}\) avec \(\forall i \in \ensemble{1}{N}, \; X_i \in \mathbb{R}^p\). Soit \(W \in M_{p,d}\pa{\mathbb{R}}\), \(W = \vecteur{C_1}{C_d}\) où les vecteurs \(\pa{C_i}\) sont les colonnes de \(W\) et \(d < p\). On suppose également que les \(\pa{C_i}\) forment une base othonormée. Par conséquent :

\[W'W = I_d\]

\(\pa{W'X_i}_{1 \infegal i \infegal N}\) est l’ensemble des vecteurs \(\pa{X_i}\) projetés sur le sous-espace vectoriel engendré par les vecteurs \(\pa{C_i}\). Réaliser une analyse en composantes principales, c’est trouver le meilleur plan de projection pour les vecteurs \(\pa{X_i}\), celui qui maximise l’inertie de ce nuage de points, c’est donc trouver \(W^*\) tel que :

\begin{eqnarray*} W^* &=& \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; E\pa{W} = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } \end{eqnarray*}

Le terme \(E\pa{W}\) est l’inertie du nuage de points \(\pa{X_i}\) projeté sur le sous-espace vectoriel défini par les vecteurs colonnes de la matrice \(W\).

Résolution d’une ACP avec un réseau de neurones diabolo

Un théorème est nécessaire avant de construire le réseau de neurones menant à la résolution du problème de l”ACP afin de passer d’une optimisation sous contrainte à une optimisation sans contrainte.

Théorème T1 : résolution de l’ACP

Les notations utilisées sont celles du problème de l”ACP. Dans ce cas :

\begin{eqnarray*} S = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } &=& \underset{ W \in M_{p,d}\pa{\mathbb{R}} } { \arg \min } \; \cro { \sum_{i=1}^{N} \norm{WW'X_i - X_i}^2 } \end{eqnarray*}

De plus \(S\) est l’espace vectoriel engendré par les \(d\) vecteurs propres de la matrice \(XX' = \sum_{i=1}^{N} X_i X_i'\) associées aux \(d\) valeurs propres de plus grand module.

Démonstration

Partie 1

L’objectif de cette partie est de chercher la valeur de :

\[\begin{split}\underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \max }\; E\pa{W}\end{split}\]

Soit \(X=\vecteur{X_1}{X_N} \in \pa{\mathbb{R}^p}^N\), alors :

\[E\pa{W} = \sum_{i=1}^{N} \norm{W'X_i}^2 = \trace{X'WW'X} = \trace{XX'WW'}\]

La matrice \(XX'\) est symétrique, elle est donc diagonalisable et il existe une matrice \(P \in M_p\pa{\mathbb{R}}:math:\) telle qu :

(3)\[\begin{split}\begin{array}{l} P'XX'P = D_X \text{ avec } D_X \text{ diagonale} \\ P'P = I_p \end{array}\end{split}\]

Soit \(P = \vecteur{P_1}{P_p}\) les vecteurs propres de la matrice \(XX'\) associés aux valeurs propres \(\vecteur{\lambda_1}{\lambda_p}\) telles que \(\abs{\lambda_1} \supegal ... \supegal \abs{\lambda_p}\). Pour mémoire, \(W = \vecteur{C_1}{C_d}\), et on a :

\[\begin{split}\begin{array}{l} \forall i \in \ensemble{1}{p}, \; XX'P_i = \lambda_i P_i \\ \forall i \in \ensemble{1}{d}, \; C_i = P_i \Longrightarrow XX'WW' = D_{X,d} = \pa{ \begin{array}{ccc} \lambda_1 & 0 & 0 \\ 0 & \ldots & 0 \\ 0 & 0 & \lambda_d \end{array} } \end{array}\end{split}\]

D’où :

\[E\pa{W} = \trace{ XX'WW' } = \trace{P D_X P' WW'} = \trace{ D_X P'WW'P }\]

Donc :

\begin{eqnarray*} \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \max }\; E\pa{W} = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \max }\; \trace{ D_X P'WW'P } = \underset{ \begin{subarray}{c} Y \in M_{p,d}\pa{\mathbb{R}} \\ Y'Y = I_d \end{subarray} } { \max }\; \trace{ D_X YY' } = \sum_{i=1}{d} \lambda_i \end{eqnarray*}

Partie 2

Soit \(Y \in \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \max }\; \trace{X'WW'X}\), \(Y = \vecteur{Y_1}{Y_d} = \pa{y_i^k}_{ \begin{subarray}{c} 1 \infegal i \infegal d \\ 1 \infegal k \infegal p \end{subarray} }\).

Chaque vecteur \(Y_i\) est écrit dans la base \(\vecteur{P_1}{P_p}\) définie en (3) :

\[\forall i \in \ensemble{1}{d}, \; Y_i = \sum_{k=1}^{p} y_i^k P_p\]

Comme \(Y'Y = I_d\), les vecteurs \(\vecteur{Y_1}{Y_d}\) sont orthogonaux deux à deux et normés, ils vérifient donc :

\[\begin{split}\left\{ \begin{array}{rl} \forall i \in \ensemble{1}{d}, & \sum_{k=1}^{p} \pa{y_i^k}^2 = 1 \\ \forall \pa{i,j} \in \ensemble{1}{d}^2, & \sum_{k=1}^{p} y_i^k y_j^k = 0 \end{array} \right.\end{split}\]

De plus :

\[XX'YY' = XX' \pa{ \sum_{i=1}^{d} Y_i Y_i'} = \sum_{i=1}^{d} XX' Y_i Y_i'\]

On en déduit que :

\begin{eqnarray*} \forall i \in \ensemble{1}{d}, \; XX' Y_i Y'_i &=& XX' \pa{ \sum_{k=1}^{p} y_i^k P_k }\pa{ \sum_{k=1}^{p} y_i^k P_k }' \\ &=& \pa{ \sum_{k=1}^{p} \lambda_k y_i^k P_k }\pa{ \sum_{k=1}^{p} y_i^k P_k }' \end{eqnarray*}

D’où :

\[\forall i \in \ensemble{1}{d}, \; \trace{ XX' Y_i Y'_i} = \sum_{k=1}^{p} \lambda_k \pa{y_i^k}^2\]

Et :

\begin{eqnarray*} \trace{ XX' YY'} &=& \sum_{i=1}^{d} \sum_{k=1}^{p} \lambda_k \pa{y_i^k}^2 \\ \trace{ XX' YY'} &=& \sum_{k=1}^{p} \lambda_k \pa {\sum_{i=1}^{d} \pa{y_i^k}^2} = \sum_{k=1}^{p} \; \lambda_k \end{eqnarray*}

Ceci permet d’affirmer que :

\begin{eqnarray*} Y \in \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \max }\; \trace{X'WW'X} \Longrightarrow vect \vecteur{Y_1}{Y_d} = vect \vecteur{P_1}{P_d} \end{eqnarray*}

Les équations (4) et (5) démontrent la seconde partie du théorème.

Partie 3

\begin{eqnarray*} \sum_{i=1}^n \left\| WW^{\prime}X_{i}-X_{i}\right\|^{2} &=& \sum_{i=1}^n \left\| \left( WW^{\prime} -I_{N}\right) X_{i}\right\| ^{2} \\ &=& tr\left( X^{\prime}\left( WW^{\prime }-I_{p}\right) ^{2}X\right) \\ &=& tr\left( XX^{\prime}\left( \left( WW^{\prime}\right) ^{2}-2WW^{\prime}+I_{p}\right) \right) \\ &=& tr\left( XX^{\prime}\left( WW^{\prime}WW^{\prime}-2WW^{\prime}+I_{p}\right) \right) \\ &=& tr\left( XX^{\prime}\left( -WW^{\prime} +I_{p}\right) \right) \\ &=& -tr\left( XX^{\prime}WW^{\prime}\right) +tr\left(XX^{\prime}\right) \end{eqnarray*}

D’où :

\begin{eqnarray*} \underset{ \begin{subarray} \, W \in M_{p,d} \pa{\mathbb{R}} \\ W'W=I_d \end{subarray}} { \; \max \; } \; \pa { \sum_{i=1}^{N} \norm{ W'X_i}^2 } = \underset{ \begin{subarray} \, W \in M_{p,d} \pa{\mathbb{R}} \\ W'W=I_d \end{subarray}} { \; \min \; } \; \pa { \sum_{i=1}^{N} \norm{ WW'X_i - X_i}^2 } \end{eqnarray*}

Partie 4

\(XX'\) est une matrice symétrique, elle est donc diagonalisable :

\[\exists P\in GL_N \pa{\mathbb{R}} \text{ telle que } P'XX'P=D_p \text{ où } D_p \text{ est diagonale}\]

On en déduit que :

\begin{eqnarray*} \sum_{i=1}^{N} \norm{ WW' X_i - X_i }^2 &=& \trace{ XX' \pa{ WW'-I_p }^{2} } \\ &=& \trace{ PP' XX' PP' \pa{ WW'-I_p }^{2} } \\ &=& \trace{ P D_p P' \pa{ WW'-I_p }^{2} } \\ &=& \trace{ D_p \pa{ P'WW'P-I_p }^{2} } \\ &=& \trace{ D_p \pa{ YY'-I_p }^{2} } \text{ avec } Y = P'W \end{eqnarray*}

D’où :

\begin{eqnarray*} \underset{Y}{\arg\min}\acc{ tr\left( D_{p}\left( YY^{\prime}-I_{p}\right) ^{2}\right)} = \left\{ Y\in M_{Nd}\left( \mathbb{R}\right) \left| YY^{\prime}=I_{d}\right. \right\} \end{eqnarray*}

Finalement, l’équation (7) permet de démontrer la première partie du théorème, à savoir (2) :

\begin{eqnarray*} S = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } &=& \underset{ W \in M_{p,d}\pa{\mathbb{R}} } { \arg \min } \; \cro { \sum_{i=1}^{N} \norm{WW'X_i - X_i}^2 } \end{eqnarray*}

Calcul de valeurs propres et de vecteurs propres

Le calcul des valeurs propres et des vecteurs propres d’une matrice fait intervenir un réseau diabolo composé d’une seule couche cachée et d’une couche de sortie avec des fonctions de transfert linéaires. On note sous forme de matrice \(\left( W\right)\) les coefficients de la seconde couche du réseau dont les biais sont nuls. On note \(d\) le nombre de neurones sur la couche cachée, et \(p\) le nombre d’entrées.

\[\forall i\in\left\{ 1,...,d\right\} ,\,y_{1,i}=\sum_{j=1}^p w_{ji}x_{j}\]

Soit \(X\in\mathbb{R}^{p}\) les entrées, \(Y=\left( y_{1,1},...,y_{1,d}\right) \in\mathbb{R}^{d}\), on obtient que : \(Y=W'X\).

Les poids de la seconde couche sont définis comme suit :

\[\forall\left( i,j\right) \in\left\{ 1,...,p\right\} \times\left\{ 1,...,d\right\} \,w_{2,j,i}=w_{1,i,j}\]

Par conséquent, le vecteur des sorties \(Z\in\mathbb{R}^{p}\) du réseau ainsi construit est \(Z=WW'X\). On veut minimiser l’erreur pour \(\left( X_{i}\right) _{1\leqslant i\leqslant N}\) :

\[E=\sum_{i=1}^N\left\| WW'X_{i}-X_{i}\right\| ^{2}\]

Il suffit d’apprendre le réseau de neurones pour obtenir :

\[W_{d}^{\ast}=\underset{W\in M_{pd}\left( \mathbb{R}\right) } {\arg\max }\,\sum_{i=1}^N\left\| WW'X_{i}-X_{i}\right\| ^{2}\]

D’après ce qui précède, l’espace engendré par les vecteurs colonnes de \(W\) est l’espace engendré par les \(k\) premiers vecteurs propres de la matrice \(XX^{\prime}=\left( X_{1},...,X_{P}\right) \left( X_{1},...,X_{P}\right) ^{\prime}\) associés aux \(k\) premières valeurs propres classées par ordre décroissant de module.

On en déduit que \(W_{1}^{\ast}\) est le vecteur propre de la matrice \(M\) associée à la valeur propre de plus grand module. \(W_{2}^{\ast}\) est l’espace engendré par les deux premiers vecteurs. Grâce à une orthonormalisation de Schmidt. On en déduit à partir de \(W_{1}^{\ast}\) et \(W_{2}^{\ast}\), les deux premiers vecteurs propres. Par récurrence, on trouve l’ensemble des vecteurs propres de la matrice \(XX^{\prime}\).

Définition D1 : orthonormalisation de Schmidt

L’orthonormalisation de Shmidt :

Soit \(\left( e_{i}\right) _{1\leqslant i\leqslant N}\) une base de \(\mathbb{R}^{p}\)

On définit la famille \(\left( \varepsilon_{i}\right) _{1\leqslant i\leqslant p}\) par :

\begin{eqnarray*} \varepsilon_{1} &=& \dfrac{e_{1}}{\left\| e_{1}\right\|}\\ \forall i \in \intervalle{1}{p}, \; \varepsilon_{i} &=& \dfrac{e_{i}-\overset{i-1}{\underset{j=1} {\sum}}<e_{i},\varepsilon_{j}>\varepsilon_{j}}{\left\| e_{i}-\overset {i-1}{\underset{j=1}{\sum}}<e_{i},\varepsilon_{j}>\varepsilon_{j}\right\| } \end{eqnarray*}

On vérifie que le dénominateur n’est jamais nul. \(e_{i}-\overset{i-1}{\underset{j=1}{\sum}}<e_{i},\varepsilon_{j}>\varepsilon_{j}\neq 0\) car \(\forall k\in\left\{ 1,...,N\right\} ,\; vect\left( e_{1},...,e_{k}\right) =vect\left( \varepsilon_{1} ,...,\varepsilon_{k}\right)\)

Propriété P1 : base orthonormée

La famille \(\left( \varepsilon_{i}\right) _{1\leqslant i\leqslant p}\) est une base orthonormée de \(\mathbb{R}^{p}\).

L’algorithme qui permet de déterminer les vecteurs propres de la matrice \(XX'\) définie par le théorème de l”ACP est le suivant :

Algorithme A1 : vecteurs propres

Les notations utilisées sont celles du théorème de l”ACP. On note \(V^*_d\) la matrice des \(d\) vecteurs propres de la matrice \(XX'\) associés aux \(d\) valeurs propres de plus grands module.

for \(d, p\)

Un réseau diabolo est construit avec les poids \(W_d \in M_{p,d}\pa{\mathbb{R}}\) puis appris.

Le résultat de cet apprentissage sont les poids \(W^*_d\).

if \(d > 1\)

L’orthonormalisation de Schmit permet de déduire \(V^*_d\) de \(V^*_{d-1}\) et \(W^*_d\).

else

\(V^*_d = W^*_d\)

Analyse en Composantes Principales (ACP)

L’analyse en composantes principales permet d’analyser une liste d’individus décrits par des variables. Comme exemple, il suffit de prendre les informations extraites du recensement de la population française qui permet de décrire chaque habitant par des variables telles que la catégorie socio-professionnelle, la salaire ou le niveau d’étude. Soit \(\left( X_{1},...,X_{N}\right)\) un ensemble de \(N\) individus décrits par \(p\) variables :

\[\forall i\in\left\{ 1,...,N\right\},\;X_{i}\in\mathbb{R}^{p}\]

L’ACP consiste à projeter ce nuage de point sur un plan qui conserve le maximum d’information. Par conséquent, il s’agit de résoudre le problème :

\[\begin{split}W^{\ast}=\underset{ \begin{subarray} \, W\in M_{p,d}\left( \mathbb{R}\right) \\ W^{\prime }W=I_{d} \end{subarray}}{\arg\min}% \left(\underset{i=1}{\overset{N}{\sum}}\left\| W'X_{i}\right\| ^{2}\right) \text{ avec }d<N\end{split}\]

Ce problème a été résolu dans les paragraphes Problème de l’analyse en composantes principales et Calcul de valeurs propres et de vecteurs propres, il suffit d’appliquer l’algorithme vecteurs propres.

Soit \(\left( X_{i}\right) _{1\leqslant i\leqslant N}\) avec \(\forall i\in\left\{ 1,...,N\right\} ,\,X_{i}\in\mathbb{R}^{p}\). Soit \(\pa{P_1,\dots,P_p}\) l’ensemble des vecteurs propres normés de la matrice \(XX'\) associés aux valeurs propres \(\pa{\lambda_1,\dots,\lambda_p}\) classées par ordre décroissant de modules. On définit \(\forall d \in \intervalle{1}{p}, \; W_d = \pa{P_1,\dots,P_d} \in M_{p,d}\). On définit alors l’inertie \(I_d\) du nuage de points projeté sur l’espace vectoriel défini par \(P_d\). On suppose que le nuage de points est centré, alors :

\[\forall d \in \intervalle{1}{p}, \; I_d = \sum_{k=1}^{N} \pa{P_d' X_k}^2 = tr \pa{X' P_d P_d' X} = tr \pa{XX' P_d P_d'} = \lambda_d\]

Comme \(\pa{P_1,\dots,P_p}\) est une base orthonormée de \(\mathbb{R}^p\), on en déduit que :

\[I = \sum_{k=1}^{P} X_k'X_k = \sum_{d=1}^{N} I_d = \sum_{d=1}^{p} \lambda_d\]

De manière empirique, on observe fréquemment que la courbe \(\pa{d,I_d}_{1 \infegal d \infegal p}\) montre un point d’inflexion (voir figure ci-dessous). Dans cet exemple, le point d’inflexion correspond à \(d=4\). En analyse des données, on considère empiriquement que seuls les quatres premières dimensions contiennent de l’information.

Figure F3 : Courbe d’inertie pour l’ACP

Courbe d’inertie : point d’inflexion pour \(d=4\), l’expérience montre que généralement, seules les projections sur un ou plusieurs des quatre premiers vecteurs propres reflètera l’information contenue par le nuage de points.