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 \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 \R^N$ \end{tabular}}}
\put(85,-9)  {\framebox(45,32){\footnotesize \begin{tabular}{c}vecteur \\ $Y \in \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 \R^3 dans \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 \R^p. Soit W \in M_{p,d}\pa{\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 :

(1)#\begin{eqnarray*}
W^* &=& \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\R} \\ W'W = I_d \end{subarray} }
                                    { \arg \max } \; E\pa{W}
    =  \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\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 :

(2)#\begin{eqnarray*}
S =
\underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\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{\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 :

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

Soit X=\vecteur{X_1}{X_N} \in \pa{\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{\R}:math: telle qu :

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

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{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}

D’où :

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

Donc :

(4)#\begin{eqnarray*}
\underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\R} \\ W'W = I_d \end{subarray} } { \max }\; E\pa{W} =
        \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\R} \\ W'W = I_d \end{subarray} } { \max }\;
            \trace{ D_X P'WW'P }
= \underset{ \begin{subarray}{c} Y \in M_{p,d}\pa{\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{\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 :

\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.

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 :

(5)#