Skip to main content

Apprentissage et calcul scientifique

Emmanuel Franck

Section 4.1 Réduction de dimension et ACP

L’objectif de cette section est d’introduire la notion de réduction de dimension en apprentissage non supervisé ainsi que la méthode la plus classique dans ce cadre: l’analyse en composante principale ainsi que son extension nonlinéaire.

Subsection 4.1.1 Principe de la réduction de dimension

La réduction de dimension est un problème d’apprentissage non supervisé qui cherche a trouver une représentation en dimension basse de données en grande dimension. Cela peut permettre de visualiser des données, de compresser des images ou d’utiliser des méthodes de régression qui ne marche pas en grande dimension. La réduction de dimension est basée sur l’hypothèse suivante:

Hypothèse de variété.

Soit des données \(x\in \mathbb{R}^n\) associé à une densité de probabilité \(p(x)\) l ’hypothèse de variété consiste à dire que
\begin{equation*} x = D(z) \end{equation*}
avec \(z\in \mathbb{R}^d\) avec \(d\lt \lt n\text{.}\) Cette hypothèse est équivalente à dire que nos données sont en pratique distribué sur une sous-variété \(\mathcal{M}\) de dimension \(d\text{.}\)
L’objectif de la réduction de dimension revient donc a déterminé \(D()\) et représentant en basse dimension \(z\text{.}\) On parle de réduction linéaire quand on suppose que les données sont distribuées sur un hyperplan de basse dimension. Cela équivaut à:
\begin{equation*} D(z)=x_{ref}+ \Phi z \end{equation*}

Subsection 4.1.2 ACP

L’Analyse en Composante principale est la méthode de référence pour la réduction de dimension linéaire. Il existe plusieurs façons de présenter cette approche. On va en donner une. On se donne des données \(\left\{x_1,...,x_n\right\}\) et on les suppose centrées:
\begin{equation*} \frac{1}{n}\sum_{i=1}^n x_i=0. \end{equation*}
Si ce n’est pas le cas on peut les centrer au préalable.

Définition 4.2. projecteur orthogonal.

On se donne un vecteur \(w\in \mathbb{R}^K\text{.}\) La projection orthogonale de \(x\in \mathbb{R}^n\) dans la direction \(w\) est donnée par la fonction \(f(x): \mathbb{R}^n\rightarrow \mathbb{R}^K\text{:}\)
\begin{equation*} f(x)=\frac{(x,w)}{\parallel w\parallel } \end{equation*}
On va maintenant introduire l’objectif de l’ACP.

Définition 4.3. Encodeur et décodeur linéaire.

Soit des données \(\left\{x_1,...,x_n\right\} \in \mathbb{R}^d\text{.}\) On appelle encodeur et décodeur linéaire les opérateurs linéaires \(\Phi_d\in\mathcal{M}_{d,K}(\mathbb{R})\) et\(\Phi_e\in\mathcal{M}_{K,d}(\mathbb{R})\) qui satisfont
\begin{equation*} \operatorname{min}_{\Phi_e,\Phi_d, \Phi_d^t \Phi_d =I_d} \mathcal{L}(\Phi_e,\phi_d) \end{equation*}
avec
\begin{equation*} \mathcal{L}(\Phi_e,\phi_d) =\sum_{i=1}^n\parallel x_i - \Phi_e z_i\parallel_2^2 \end{equation*}
avec \(z_i=\Phi_e x_i\) les quantités latentes.
Cela revient à compresser puis décompresser nos données avec une erreur minimale.

Preuve.

On commence par considérer les vecteurs propres un par un. Soit \(\phi_k\) un vecteur colonne de \(\Phi_d\) et \(z_i\in \mathbb{R}^d\) (de \(k\)eme composante \(z_i^k\))
\begin{equation*} \mathcal{L}(\phi,z) =\frac{1}{n}\sum_{i=1}^n\parallel x_i - \phi_k z_k^i \parallel_2^2=\sum_{i=1}^n\left( (x_i-\phi_k z_i^k)^t (x_i-\phi_k z_k^i) \right) \end{equation*}
\begin{equation*} \mathcal{L}(\phi,z) =\frac{1}{n}\sum_{i=1}^n\parallel x_i - \phi_k z_k^i\parallel_2^2=\sum_{i=1}^n\left( x_i^t x_i - (\phi_k z_k^i)^t x_i -x_i^t \phi_k z_k^i + (\phi_k z_k^i)^t \phi_k z_k^i\right) \end{equation*}
on utilise \(x_i^t \phi_k z_k^i =z_k^i(x_i,\phi_k)=z_k^i(\phi_k,x_i)=(\phi_k z_k^i)^t x_i\) et \((\phi_k z_i)^t \phi_k z_i= z_t (\phi_k)^t \phi_k z_i = \parallel z_i\parallel_2^2 \) en utilisant l’hypothèse d’orthonormalité (qui donne \((\phi_k)^t \phi_k=1\)). On obtient donc
\begin{equation*} \mathcal{L}(\phi,z) =\sum_{i=1}^n\parallel x_i - \phi_k z_k^i\parallel_2^2=\sum_{i=1}^n\left( x_i^t x_i - 2 z_i^k \phi_k^t x_i + (z_i^k)^2\right) \end{equation*}
Maintenant on va calculer le gradient par rapport à \(z_i^k\text{,}\) on obtient
\begin{equation*} \frac{\partial \mathcal{L}(\phi,z) }{\partial z_i^k} = 2(z_i^k -\phi_k^t x_i) \end{equation*}
En annulant le gradient on retrouve \((z_i^k -\phi_k^t x_i)=0\) ce qui nous définit l’encodeur comme le transposé du décodeur. Maintenant on va regarder la fonction de coût évaluée avec la valeur optimale des \(z_i^{k,*}\) ce qui revient à \(z_i =\phi_k^t x_i\text{.}\) En faisant cela on obtient
\begin{equation*} \mathcal{L}(\phi,z_i^{k,*}) = \mathcal{L}(\phi_k)=\sum_{i=1}^n\left( x_i^t x_i - z_i^{k,2}\right) \end{equation*}
Puisque \(x_i\) ne dépend pas \(\Phi_d\) alors minimiser la fonction précédente est équivalent à
\begin{equation*} \operatorname{min}_{\phi}\mathcal{L}(\phi)= \operatorname{min}_{\phi}\sum_{i=1}^n\left( - z_i^{k,2} \right) \end{equation*}
Puisqu’on a \(z_i^k =\phi_k^t x_i=\langle \phi_k, x_i \rangle\) on a
\begin{equation*} z_i^{k,2} =\phi_k^t x_i x_i^t \phi_k \end{equation*}
et donc la dernière minimisation est équivalent à
\begin{equation*} \operatorname{max}_{\phi_k, \phi_k^t \phi_k = 1} \sum_{i=1}^n \left(\phi_k^t (x_i x_i^t)\phi_k \right) \end{equation*}
Ensuite on utilise la définition de \(\Sigma\) pour conclure.

Preuve.

On va procéder par récurrence en construisant les vecteurs orthonormés \((\phi_1,...\phi_K)\) de \(\Phi_d\text{.}\)
  • Premier étape de la récurrence. Le vecteur \(\phi_1\) est solution de
    \begin{equation*} \underset{\phi_1}{\operatorname{max}}\phi_1^t \Sigma \phi_1 \end{equation*}
    avec comme contrainte \(\parallel \phi_1\parallel_2^2 =1\text{.}\) En utilisant la méthode des multiplicateurs de Lagrange, cela revient à résoudre
    \begin{equation*} \underset{\phi_1}{\operatorname{min}}\mathcal{L}_{mod}= \underset{\phi_1}{\operatorname{min}}\left(-\phi_1^t \Sigma \phi_1 +\lambda_1(\phi_1^t \phi_1 -1)\right) \end{equation*}
    Le gradient \(\mathcal{L}_{mod}\) est donné par
    \begin{equation*} \frac{\partial \mathcal{L}_{mod} }{\partial \phi_1}= -2\Sigma \phi_1 +2\lambda_1 \phi_1 \end{equation*}
    \begin{equation*} \frac{\partial \mathcal{L}_{mod} }{\partial \lambda_1}= (\phi_1^t \phi_1 -1) \end{equation*}
    En annulant les gradient on obtient:
    \begin{equation*} \begin{cases} 2\Sigma \phi_1 -2\lambda_1 \phi_1=0 \\ \phi_1^t \phi_1 =1 \end{cases}. \end{equation*}
    On a donc \(\Sigma \phi_1 =\lambda_1 \phi_1\text{.}\) On utilise ensuite \(\phi_1^t \phi_1 =1\) ce qui donne \(\phi_1^t\Sigma \phi_1 =\lambda_1 \text{.}\) On retrouve le problème qu’on souhaite maximiser. Il faut donc prendre \(\lambda_1\) maxmimal et donc il s’agira de la plus grande valeur propre de \(\Sigma\text{.}\)
  • K étape de la récurrence. Le vecteur \(\phi_k\) est solution de
    \begin{equation*} \underset{\phi_k}{\operatorname{max}} \phi_k^t \Sigma \phi_k \end{equation*}
    avec comme contrainte \(\parallel \phi_k\parallel_2^2 =1\) et \(\langle \phi_k,\phi_{k-1}\rangle=0\text{.}\) En utilisant la méthode des multiplicateurs de Lagrange cela revient à résoudre
    \begin{equation*} \underset{\phi_k}{\operatorname{min}} \mathcal{L}_{mod}= \underset{\phi_k}{\operatorname{min}} \left( -\phi_k^t \Sigma \phi_k +\lambda_k(\phi_k^t \phi_k -1)+\lambda_{k,k-1}(\phi_k^t \phi_{k-1} -0)\right) \end{equation*}
    Le gradient \(\mathcal{L}_{mod}\) est donné par
    \begin{equation*} \frac{\partial \mathcal{L}_{mod}}{\partial \phi_k}=2\Sigma \phi_k -2\lambda_k \phi_k-\lambda_{k,k-1}\phi_{k-1} \end{equation*}
    On calcul aussi les gradient par rapport aux multiplicateurs ce qui donne
    \begin{equation*} \frac{\partial \mathcal{L}_{mod}}{\partial \lambda_k}=(\phi_k^t \phi_k -1) \end{equation*}
    \begin{equation*} \frac{\partial \mathcal{L}_{mod}}{\partial \lambda_{k,k-1}}=\phi_k \phi_{k-1} \end{equation*}
    On obtient donc le problème:
    \begin{equation} 2\Sigma \phi_1 -2\lambda_k \phi_k -\lambda_{k,k-1}\phi_{k-1}=0 \tag{4.2} \end{equation}
    avec les contraintes \(\phi_k^t \phi_k =1\) et \(\phi_k^t \phi_{k-1}\text{.}\) On va multiplier la relation (4.2) par \(\phi_{k-1}^t\) ce qui donne
    \begin{equation*} 2\phi_{k-1}^t \Sigma \phi_k -2\lambda_k \phi_{k-1}^t\phi_k-\lambda_{k,k-1}\phi_{k-1}^t\phi_{k-1} =0 \end{equation*}
    \begin{equation*} 2(\phi_{k-1}, \Sigma \phi_k) -2\lambda_k (\phi_{k-1},\phi_k)-\lambda_{k,k-1} =0 \end{equation*}
    On utilise la symétrie de \(\Sigma\) pour obtenir
    \begin{equation*} 2(\Sigma \phi_{k-1}, \phi_k) -2\lambda_k (\phi_{k},\phi_{k-1})-\lambda_{k,k-1} =0 \end{equation*}
    On utilise l’orthogonalité \(\phi_k^t \phi_{k-1} =0\) et le fait que par récurrence on est \(\Sigma \phi_{k-1} =\lambda_{k-1} \phi_{k-1}\) pour obtenir
    \begin{equation*} 2(\lambda_{k_1} \phi_{k-1}, \phi_k) -\lambda_{k,k-1} =0 \end{equation*}
    On réutilise l’orthogonalité donc \(\lambda_{k,k-1} =0\text{.}\) On a donc
    \begin{equation*} \Sigma \phi_k =\lambda_k \phi_k \end{equation*}
    et la encore on mutliplie par \(\phi_k^t\) pour obtenir \(\phi_k^t\Sigma \phi_k =\lambda_k\) la quantité a maximiser ce qui nous dit que \(\lambda_{k}\) est la \(k\)ième plus grande valeur propre. Cela conclut la preuve.
Ce résultat nous donne donc comme encodeur les \(K\) premiers vecteurs propres de la matrice de covariance des données.
Figure 4.6. On donne un exemple d’ACP sur une image. En haut a gauche on a l’image de référence. En haut a droite on a l’image (en noir et blanc) ou on conserve les 50 directions principales. En bas on conserve 20 directions (gauche) ou 6 directions (droite).
Sur la figure Figure 4.6 on propose un exemple de compression par ACP ou l’on garde qu’un certains nombre de direction principales pour reconstruire une image.

Subsubsection 4.1.2.1 ACP probabiliste

La méthode probabiliste peut être aussi obtenue dans un cadre probabiliste. On va ici chercher a déterminer la loi de probabilité des données en supposant que ces données dépendent de variables latente en petit dimension. Si l’ont ne considère pas leq données centrée, l’analyse en composante principal peut s’écrire sous la forme suivante:
\begin{equation*} x_i = b + (\Phi,z_i) +\epsilon =b + \sum_{j=1}^m z_i^j \phi_j +\epsilon \end{equation*}
avec \(\epsilon\) un bruit Gaussien de variance \(\sigma^2\) et des quantités a déterminer: \(b\in \in\mathcal{M}_{d}(\mathbf{R})\) et \(\Phi\in\mathcal{M}_{d,K}(\mathbf{R})\text{.}\) On peut récrire ce problème sous la forme d’un modèle génératif à variable latente:
  • Une variable latente y de loi à priori:
    \begin{equation*} p(z) = \mathcal{N}(0,1) \end{equation*}
  • Une probabilité conditionnelle:
    \begin{equation*} p_{\theta}(x \mid z) = \mathcal{N}(b +(\omega,z),\sigma^2) \end{equation*}
La construction du modèle à variable latentes va consister ici à trouver \(b\in \mathbb{R}^d\text{,}\) \(\Phi \in \mathcal{M}_{d,K}( \mathbb{R})\) et si possible \(\sigma^2\) tel que les données puisssent être générées/expliquées par la loi de probabilité
\begin{equation*} p_{\theta}(x)= \int_y p(x, z )= \int_y p(x \mid z)p(z)=\mathcal{N}(b,\Phi\Phi^t+\sigma^2 I_d) \end{equation*}
que l’ont peut déterminer a partir de la loi à priori et la probabilité conditionnelle car il s’agit de loi Gaussienne. Puisqu’on cherche a ce que les données est été le probablement possible générée par \(p_{\theta}(x)\) le plus naturel est de maximiser la vraissamblance associée.
On écrit donc la log vraissensamblce associée à \(p(x)\). On obtient:
\begin{equation*} log \mathcal{L}(x_1,...x_n; b, \Phi)=\sum_{i=1}^n p(x_i) \end{equation*}
ce qui est égale à
\begin{equation} log \mathcal{L}(x_1,...x_n; b, \Phi)=- \frac{n}{2}\left(d \operatorname{ln}(2\pi) +\operatorname{ln}(C) -\frac{1}{2}\sum_{i=1}^n ((x_i-b),C^{-1}(x_i-b)) \right)\tag{4.3} \end{equation}
avec \(C=\Phi\Phi^t+\sigma^2 I_d\text{.}\) Cela revient à
\begin{equation*} log \mathcal{L}(x_1,...x_n; b, \Phi)=- \frac{n}{2}\left(d \operatorname{ln}(2\pi) +\operatorname{ln}(C) -\frac{1}{2} tr(C^{-1}S) \right) \end{equation*}
avec
\begin{equation*} \Sigma=\sum_{i=1}^n=(x_i-b)(x_i-b)^t=(X-Eb)(X-Eb)^t \in\mathcal{M}_{d,d}(\mathbb{R}) \end{equation*}
avec \(\Sigma\) matrice de covariance et \(E\) la matrice contenant que des 1.
Preuve.
On commence par regarder la dérivée par rapport à \(b\) et résoudre l’équation
\begin{equation*} \frac{\partial log \mathcal{L}(x_1,...x_n; b, \Phi)}{\partial b}=0. \end{equation*}
Il est assez immédiat de trouver que \(b= \bar{x}\text{.}\) Maintenant on considère la dérivation par \(\Phi\text{.}\) On a
\begin{equation*} \frac{\partial log \mathcal{L}(x_1,...x_n; b, \Phi)}{\partial \Phi}=0 \end{equation*}
On utilise un résultat de (e.g. see Krzanowski and Marriott 1994, p. 133) pour la différentiation de matrice. On obtient
\begin{equation*} \frac{\partial log \mathcal{L}(x_1,...x_n; b, \Phi)}{\partial \Phi} = n(C^{-1}\Sigma C^{-1}\Phi- C^{-1}\Phi) \end{equation*}
On voit donc que les points critiques sont solutions de
\begin{equation} \Sigma C^{-1}\Phi = \Phi\tag{4.4} \end{equation}
Maintnenant l’enjeu est de résoudre ce dernier système linéaire. Il y a 3 solutions possibles. D’abord le cas trivial \(\Phi=0\) qui correspond plutôt a un minimum de la log-vraissemblance qu’un maximum. Le second cas est \(C=\Sigma\text{.}\) Par définition de \(C\) (\(C=\Phi\Phi^t+\sigma^2 I_d\)) on obtient donc une caractérisation
\begin{equation*} \Phi\Phi^t = \Sigma-\sigma^2I_d \end{equation*}
On peut diagonaliser la matrice \(\Sigma-\sigma^2I_d\) ce que donne
\begin{equation*} \Sigma-\sigma^2I_d= \omega\omega^t=U (\Delta - \sigma^2 I_d) U^t \end{equation*}
et donc \(\Phi = U (\Lambda - \sigma^2 I_d)^{\frac{1}{2}} R\) avec \(R\) une matrice orthogonale. Maintenant il reste le dernier cas de figure qui ne correspond à aucun des cas précédent. Pour résoudre le problème on se donne une décomposition en valeur singuliaire de \(\Phi\text{:}\)
\begin{equation*} \Phi = U D V^t \end{equation*}
qu’on identifie à \(U_K\) et \(\Lambda_K\) dans le théorème. On a \(U\in \mathcal{M}_{d,K}(\mathbb{R})\) avec des colonnes orthogonales (donc \(U^t U=I_d\)), \(\Lambda\in \mathcal{M}_{K,K}(\mathbb{R})\) diagonale et \(V \in \mathcal{M}_{K,K}(\mathbb{R})\) orthogonale. Maintenant on va utiliser la formule de Sherman–Morrison–Woodbury qui dit que
\begin{equation*} (A+BEF)^{-1}=A^{-1}-A^{-1}B(E^{-1}-FA^{-1}B)^{-1}FA^{-1} \end{equation*}
On applique cela à notre matrice \(C\text{.}\) On utilise la SVD de \(\Phi\text{.}\) On rappelle
\begin{equation*} C^{-1}= (\sigma^2 I_d + \Phi\Phi^t)^{-1} =\frac{1}{\sigma^2} (I_d - \frac{1}{\sigma^2} \Phi \Phi^t) \end{equation*}
et on pose \(M=(\sigma^2 I_d + \Phi^t \Phi)\text{.}\) On utilise la formule de Sherman–Morrison–Woodbury qui dit que
\begin{equation*} (I_d-BF)^{-1}=I_d-B(I_d-FB)^{-1}F \end{equation*}
On montre que \(C^{-1}\Phi=\Phi M^{-1}\) (a démontrer). Ensuite on va développler \(\Phi M^{-1}\text{.}\) On a
\begin{align*} \theta M^{-1}\amp =U\Lambda V^t (\sigma^2 + V\Lambda^2V^t)^{-1}\\ \theta M^{-1}\amp =U \Lambda V^t (\sigma^2 V V^t+ V\Lambda^2V^t)^{-1}\\ \theta M^{-1}\amp =U \Lambda V^t (\sigma^2 V V^t+ V\Lambda^2V^t)^{-1}\\ \theta M^{-1}\amp =U\Lambda V^t ((\sigma^2 V+ V\Lambda^2)V^t)^{-1}\\ \theta M^{-1}\amp =U \Lambda V^t V^{-t}(\sigma^2 V+ V\Lambda^2)^{-1}\\ \theta M^{-1}\amp =U \Lambda (\sigma^2 V+ V\Lambda^2)^{-1}\\ \theta M^{-1}\amp =U\Lambda(V(\sigma^2+ \Lambda^2))^{-1}\\ \theta M^{-1}\amp =U\Lambda(\sigma^2+ \Lambda^2)^{-1}V^{-1}\\ \theta M^{-1}\amp =U\Lambda(\sigma^2+ \Lambda^2)^{-1}V^{t} \end{align*}
Maintenant on repart de (4.4) et on utilise les calculs précédents pour obtenir
\begin{equation*} \Sigma UL(\sigma^2+ \Lambda^2)^{-1}V^{t} = ULV^t \end{equation*}
On multiplie par \(V\) puis par \((\sigma^2+ L^2)\) ce qui donne
\begin{equation*} \Sigma UL=UL(\sigma^2+ \Lambda^2)= U(\sigma^2+ \Lambda^2)\Lambda \end{equation*}
On se place maintenant dans un cas ou une valeur propre \(\Lambda_{ii}\neq 0\text{.}\) Dans ce cas notre équation précédente implique:
\begin{equation*} \Sigma u_j = (\sigma^2+l_j^2)u_j, \quad \forall i \end{equation*}
On en déduit donc que chaque vecteur colonne de \(U\) est un vecteur propre de \(\Sigma\) associée à la valeur propre \(\lambda_j=\sigma^2+l_j^2\text{.}\) On a donc \(l_j=(\lambda_j-\sigma)^{\frac12}\)>. Pour \(l_j=0\) on a donc \(u_j\) qui peut être choisit arbitrairement. On a donc
\begin{equation*} \omega = UL V^t= U_K(\lambda_K-\sigma^2)^{\frac{1}{2}}R \end{equation*}
On ne détaillera pas la fin de la preuve sur l’estimation de \(\sigma^2\text{.}\) on peut la retrouver dans ( ref Tipping99probabilisticprincipal) .
Si on se place dans un capdre déterministe \(\sigma=0\) on projette les données en suivant la moyenne donc avec
\begin{equation*} \boxed{z = M_{pca}^{-1}\Phi_{pca}^t(x-\mathbf{x})} \end{equation*}
On va maintenant développer cet opérateur pour \(\sigma=0\text{.}\) On a donc \(\Phi_{pca} = U_M(\Lambda_K)^\frac{1}{2}R\) et \(M_{pca}=R^t \Lambda R\text{.}\) Ensuite on calcul
\begin{equation*} M_{pca}^{-1}\Phi_{pca}^t=(R^t \Lambda_k R)^{-1}R^t \Lambda_K^{\frac12}U_K^t= R^t \Lambda_K R R^t \Lambda_K^{\frac12}U_K^t = \Lambda_K^{-\frac12}U_K^t \end{equation*}
On en deduit le corrolaire suivant. On obtient le même résultat auqe précédemment a une mise à l’échelle près par la racine carrée des valeurs propres del la matrice de covariance.

Subsection 4.1.3 ACP à noyau

L’ACP est une méthode de réduction de dimension très efficace, mais elle est limitée à l’hypothèse que les données en basse dimension soient distribuées sur ou autour d’un hyperplan. Une première solution pour aller au-delà de cela est d’utiliser la méthode des noyaux. L’idée est la même qu’en régression on va envoyer les données dans un espace de redescription de façon à ce qu’il existe un décodeur linéaire pour compresser les données. On a donc des données \(\left\{x_1,...x_n\right\}\text{.}\) On se donne une fonction de redescription dépendante d’un noyau
\begin{equation*} \phi(x)=\sum_{j=1}^n \alpha_j k(x,x_j) \end{equation*}
On souhaite que les nouvelles données \(y_i=\phi(x_i)\) satisfont \(\frac{1}{n}\sum_{i=1}^n y_i=0\text{.}\) Pour cela on utilise une version centrée
\begin{equation*} \tilde{\phi}(x)=\phi(x)-\frac{1}{n}\sum_{i=1}^n\phi(x) \end{equation*}
On se donne maintenant la matrice de covariance associée aux données dans l’espace de redescription:
\begin{equation*} \Sigma = \sum_{i=1}^n\tilde{\phi}(x_i)\tilde{\phi}(x_i)^t \end{equation*}
Avant de continuer, on appelle puisque \(\phi\) est associé à un noyau reproduisant on a
\begin{equation*} k(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle_{H} =\phi(x_i)^t \phi(x_j) \end{equation*}
et on note \(K\) la matrice associée telle que \(K_{ij}=k(x_i,x_j)\text{.}\) Si on souhaite utiliser une fonction de redescription centrée. Dans ce cas il existe un noyau associé \(\tilde{k}\) et une matrice \(\tilde{K}\) associée aux données
\begin{equation*} \tilde{K} = K - 2\frac{1}{n}\mathbb{1}K +\frac{1}{n^2} \mathbb{1}K\mathbb{1} \end{equation*}
Maintenant on souhaite appliquer une ACP aux données dans l’espace de redescription. Pour cela on va calculer les vecteurs propres de \(\Sigma\) et les utiliser pour construire les représentants en basse dimension.

Preuve.

A faire en TD.

Définition 4.11. Plongement pour l’ACP a noyau.

Soit \((v_1,...v_K)\) les \(K\) vecteurs propres associés aux plus grandes valeurs propres de \(\Sigma\text{.}\) Pour obtenir les données en petite dimension on projette de façon orthogonale sur l’espace engendré par ses vecteurs. par conséquent la jème coordonnée du vecteur \(z\) est donné par:
\begin{equation} z_j=\frac{\langle \phi(x),v_j \rangle}{\parallel v_j\parallel}=\langle \phi(x),v_j \rangle =\sum_{i=1}^n a_{ji}\phi(x)^t\phi(x_i)=\sum_{i=1}^n a_{ji}k(x,x_j)\tag{4.5} \end{equation}
avec
\begin{equation*} K a_j =n \lambda_j a_j \end{equation*}
et \(K_{ij}=k(x_i,x_j)\)
C’est ce résultat qui nous donne le plongement en petite dimension pour nos données et pour de nouvelles données.
PrevTopNext