Outils logiciels pour les cours Paris II

Cours Paris II

edit SideBar

BD 7

Une image est un ensemble de pixels, par exemple 780 environ dans la base de données MNIST, et jusqu'à des millions pour des images de grande précision.

Supposons n images, vues comme une matrice (n,d) où d est la dimension de chaque image.

Une approche classique est de compresser l'image en .gif et .jpeg par exemple. Une autre approche est de réduire la dimension.

  • Problème général: on a n points v de dimension d. On souhaite remplacer ces points par des points v' de dimension k plus faible, sans trop d'erreurs.
    • Johnson-Lindenstrauss: si k > 4 eps2 .log n alors la distortion est au plus eps avec une projection aléatoire.
    • Une projection aléatoire est une matrice (d,k) où chaque valeur est tirée selon N(0,1)
    • On peut aussi choisir k=log n/ eps2 et tirer selon N(0,1/k)
  • PCA: Analyse en composantes principales.
    • on choisit les vecteurs propres correspondant aux plus grandes valeurs propres de la matrice de covariance A(i,j)
    • on obtient une matrice A' avec moins de colonnes
    • on reconstruit approximativement la matrice d'origine

http://mdr.free.fr/td/Ad.pdf

  • Gram's decomposition
    • on peut toujours trouver des vecteurs vi pour i=1...n tels que vi. vj= A(i,j)
    • Problème: trouver des vecteurs de petite dimension tels que vi. vj= A(i,j)
    • Word2vec

http://rare-technologies.com/word2vec-tutorial/

UP2