• View
• Edit
• History
• Print

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 eps² .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/ eps² 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/reconstruct.py

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

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

http://nlp.polytechnique.fr/word2vec#french

• Exercice:
  • Matrice A=

                [0.1,2,2.0,1,2]
                [0.2,3,3.0,1,1]
                [0.1,4,4.1,1,2]

Réduire à 2 lignes et 2 colonnes. Instruction Python:

A = np.array([ [0.1,2,2.0,1,2],[0.2,3,3.0,1,1],[0.1,4,4.1,1,2] ])