Skip to main content

Section 4.5 Méthodes "probabilistes"

On va finir par introduire une méthode de réduction probabiliste qui est à la fois différente de toutes les approches précédentes et en même temps proche dans la philosophie.

Subsection 4.5.1 Méthode SNE

L'idée de la méthode SNE (Stochastic Neighbor Embedding) est assez proche de la méthode LLE dans son premier objectif. En effet l'idée est toujours de définir un plongement qui préserve les voisinages. La différence principale vient dans la définition de cette notion de voisinage. Pour la méthode LLE, on définissait des moyennes locales qui reliait un point à ces voisins et on essayait de préserver ses moyennes locales. Ici on va définir une loi de probabilité des voisinages.

Définition 4.35.

Étant donné \(x_i\text{,}\) on définit la probabilité de choisir \(x_j\) comme voisin

\begin{equation*} \forall j \neq i,\ p_{j|i} = \frac{\exp\left(-\frac{||x_j - x_i||^2}{2\sigma_i^2}\right)}{\sum_{k\neq i} \exp\left(-\frac{||x_k - x_i||^2}{2\sigma_i^2}\right)}\qquad p_{i|i} = 0 \end{equation*}

on parle de similarité entre les données. On appelle \(P_i = (p_{j|i})_j\) - loi de probabilité de voisinage autour de \(x_i\)

On va maintenant définir la similarité sur les variables réduites et les lois de probabilités de voisinages. On obtient la définition de similarité sur les variables réduites \(z\text{:}\)

\begin{equation*} \forall j \neq i,\ z_{j|i} = \frac{\exp\left(-||z_j - z_i||^2\right)}{\sum_{k\neq i} \exp\left(-||z_k - z_i||^2\right)}\qquad z_{i|i} = 0 \end{equation*}

et \(Q_i = (q_{j|i})_j\) - loi de voisinage autour de \(z_i\text{.}\) Jusqu'à présent on a toujours construit les plongements en préservant certaines propriétés. Ic on va essayer de conserver les lois de voisinage à travers de plongement.

Objectif.

L'objectif est de minimiser l'écart entre les distributions de loi de voisinages dans l'espace complet et l'espace réduit:

\begin{equation} Z^* = \underset{Z}{\text{argmin}} \sum_i \text{KL}(P_i|Q_i) = \underset{Z}{\text{argmin}} \sum_i\sum_j p_{j|i} \log\left(\frac{p_{j|i}}{q_{j|i}}\right)\tag{4.14} \end{equation}
Pour cela on va calculer une méthode de gradient qui peut être calculer analytiquement.

On remarque que

\begin{equation*} \sum_i \text{KL}(P_i|Q_i)= \sum_{i\neq j} p_{j|i} \log p_{j|i} - \sum_{i\neq j} p_{j|i} \log q_{j|i} \end{equation*}
\begin{equation*} \partial_{z_k} \left( \sum_i \text{KL}(P_i|Q_i)\right) = - \sum_{i, j} p_{j|i} \frac{\partial \log q_{j|i}}{\partial z_k} = - \sum_{i, j} p_{j|i} \frac{\partial}{\partial z_k}(-||z_j - z_i||^2) \end{equation*}
\begin{equation*} + \sum_{i, j} p_{j|i} \frac{\partial}{\partial z_k}\log Z_i \end{equation*}

en notant \(Z_i = \sum_{\ell\neq i} \exp\left(-||z_i - z_\ell||^2\right)\text{.}\) On obtient donc:

\begin{align*} \frac{\partial C}{\partial z_k}(z) \amp= - 2 \sum_{j} p_{j|k} (z_j - z_k) + 2 \sum_{i} p_{k|i} (z_k - z_i) + \frac{\partial}{\partial z_k}\log Z_k + \sum_{i\neq k} \frac{\partial}{\partial z_k}\log Z_i \\ \amp= 2 \sum_{j} p_{j|k} (z_k - z_j) + 2 \sum_{i} p_{k|i} (z_k - z_i) - \sum_{\ell \neq k} 2 \exp\left(-||z_\ell - z_k||^2\right)\frac{(z_k - z_\ell)}{Z_k} - 2 \sum_{i\neq k} \exp\left(-||z_k - z_i||^2\right)\frac{(z_k - z_i)}{Z_i}\\ \amp = 2 \sum_{j} (p_{j|k} + p_{k|j}) (z_k - z_j) - 2 \sum_{\ell} q_{\ell|k} (z_k - z_\ell) - 2 \sum_{i\neq k} q_{k|i} (z_k - z_i)\\ \amp= 2 \sum_{j} (p_{j|k} - q_{j|k} + p_{k|j} - q_{k|j}) (z_j - z_k) \end{align*}

Avec ce calcul du gradient, on peut mettre en place un algorithme d'optimisation et calculer la solution.

Subsection 4.5.2 Variante t-SNE

Dans certains cas on veut absolument plonger les données en dimension ou 2 ou 3 afin de visualiser les données. Pour cela on utilise une variante de la méthode SNE qui s'appelle la méthode t-SNE. En effet en pratique la fonction de coût est pas facile a minimiser et les points en dimension 2 ou 3 ont tendance a ne pas assez s'écarter. On utilise pour cela deux ingrédients:

  • On symétrise les loi. par exemple \(p_{ij}=\frac12(p_{j|i}+p_{i|j})\)

  • Pour l'espace en basse dimension on utilise une loi de Student plutôt qu'une gaussienne:

    \begin{equation*} p_{ij} = \frac{p_{i|j}+p_{j|i}}{2},\qquad q_{ij} = \frac{(1+||z_i - z_i||^2)^{-1}}{\sum_{k\neq \ell}(1+||z_\ell - z_k||^2)^{-1}} \end{equation*}

Admis. Preuve similaire.