Pourquoi Andrew Ng préfère-t-il utiliser SVD et non EIG de matrice de covariance pour faire PCA?

29

J'étudie PCA du cours Coursera d'Andrew Ng et d'autres matériaux. Dans le premier devoir de Stanford NLP cs224n , et dans la vidéo de conférence d'Andrew Ng , ils font une décomposition en valeurs singulières au lieu de la décomposition en vecteur propre de la matrice de covariance, et Ng dit même que la SVD est numériquement plus stable que la composition en eigendecomposition.

D'après ma compréhension, pour PCA, nous devrions faire SVD de la matrice de données de (m,n)taille, pas de la matrice de covariance de (n,n)taille. Et décomposition des vecteurs propres de la matrice de covariance.

Pourquoi font-ils SVD de matrice de covariance, pas de matrice de données?

DongukJu
la source
8
Pour une matrice semi-définie positive symétrique carrée (telle qu'une matrice de covariance), les décompositions de valeurs propres et de valeurs singulières sont exactement les mêmes.
amibe dit Réintégrer Monica
5
Je veux dire qu'ils sont mathématiquement les mêmes. Numériquement, ils pourraient en effet utiliser différents algorithmes et l'un pourrait être plus stable qu'un autre (comme le dit Ng). Ce serait intéressant d'en savoir plus sur +1.
amibe dit Réintégrer Monica
4
Quelques informations à ce sujet ici: de.mathworks.com/matlabcentral/newsreader/view_thread/21268 . Mais notez que toute explication sur la raison pour laquelle un algorithme serait plus stable qu'un autre va être très technique.
amibe dit Réintégrer Monica
2
Dans Matlab x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc;sur ma machine, les sorties 12s pour eig () et 26s pour svd (). Si c'est beaucoup plus lent, ça doit au moins être plus stable! :-)
amibe dit Réintégrer Monica
4
Cela pourrait être basé sur une compréhension incorrecte: faire une SVD de la matrice de données est plus stable que d'utiliser eigou svdsur la matrice de covariance, mais pour autant que je sache, il n'y a pas de grande différence entre utiliser eigou svdsur la matrice de covariance --- ils sont les deux algorithmes stables en arrière. Si quoi que ce soit, je mettrais mon argent sur eig étant plus stable, car il fait moins de calculs (en supposant que les deux sont implémentés avec des algorithmes de pointe).
Federico Poloni

Réponses:

17

amoeba a déjà donné une bonne réponse dans les commentaires, mais si vous voulez un argument formel, c'est parti.

La décomposition en valeurs singulières d'une matrice est A = U Σ V T , où les colonnes de V sont des vecteurs propres de A T A et les entrées diagonales de Σ sont les racines carrées de ses valeurs propres, c'est-à-dire σ i i = AA=UΣVTVATAΣ .σii=λi(ATA)

Comme vous le savez, les principales composantes sont les projections orthogonales de vos variables sur l'espace des vecteurs propres de la matrice de covariance empirique . La variance des composants est donnée par ses valeurs propres,λi(11n1ATA.λi(1n1ATA)

Considérons toute matrice carrée , α R et un vecteur v tel que B v = λ v . ensuiteBαRvBv=λv

  1. Bkv=λkv
  2. λ(αB)=αλ(B)

Définissons . La SVD deScalculera la composition propre deSTS=1S=1n1ATASpour donnerSTS=1(n1)2ATAATA

  1. les vecteurs propres de , qui par propriété 1 sont ceux de A T A(ATA)TATA=ATAATAATA
  2. les racines carrées des valeurs propres de , qui par propriété 2, puis 1, puis encore 2, sont1(n1)2ATAATA.1(n1)2λi(ATAATA)=1(n1)2λi2(ATA)=1n1λi(ATA)=λi(1n1ATA)

Voilà!

En ce qui concerne la stabilité numérique, il faudrait déterminer quels sont les alogrithmes employés. Si vous êtes à la hauteur, je pense que ce sont les routines LAPACK utilisées par numpy:

Mise à jour: Sur la stabilité, l'implémentation SVD semble utiliser une approche diviser pour mieux régner, tandis que la composition eigend utilise un algorithme QR simple. Je ne peux pas accéder à certains articles SIAM pertinents de mon établissement (blâmer les coupes dans la recherche) mais j'ai trouvé quelque chose qui pourrait soutenir l'évaluation que la routine SVD est plus stable.

Dans

Nakatsukasa, Yuji et Nicholas J. Higham. "Algorithmes de division et de conquête spectrale stables et efficaces pour la décomposition symétrique des valeurs propres et la SVD." SIAM Journal on Scientific Computing 35.3 (2013): A1325-A1349.

ils comparent la stabilité de divers algorithmes de valeurs propres, et il semble que l'approche diviser pour mieux régner (ils utilisent la même que numpy dans l'une des expériences!) soit plus stable que l'algorithme QR. Ceci, ainsi que les allégations ailleurs que les méthodes D&C sont en effet plus stables, soutient le choix de Ng.

broncoAbierto
la source
Les valeurs propres que j'ai obtenues à partir de svd sur la covariance et de svd sur les données moyennes centrées ne sont pas les mêmes.
theGD
Cependant, les scores, c'est-à-dire X * V (où V est obtenu à partir de [U, S, V] = svd (x) ou svd (covx)), sont les mêmes.
theGD
1
@theGD Les valeurs propres de cov (X) et les valeurs singulières de (X) ne sont pas identiques, voir stats.stackexchange.com/questions/134282 .
amibe dit Réintégrer Monica
pas besoin de désespérer par manque d'accès aux revues SIAM: l'article que vous citez est ici: opt.mist.iu-tokyo.ac.jp/~nakatsukasa/publishedpdf/pub13.pdf
Dima Pasechnik
2
@broncoAbierto la technologie. le rapport est ici: cpsc.yale.edu/sites/default/files/files/tr932.pdf (on ne peut probablement pas le trouver facilement en raison d'une faute de frappe "Symétrique" dans le titre sur cpsc.yale.edu/research/technical-reports / 1992-rapports-techniques :-))
Dima Pasechnik
12

@amoeba a eu d'excellentes réponses aux questions de l'ACP, y compris celle-ci sur la relation entre SVD et PCA. En réponse à votre question exacte, je ferai trois remarques:

  • mathématiquement, il n'y a pas de différence si vous calculez PCA directement sur la matrice de données ou sur sa matrice de covariance
  • la différence est purement due à la précision et à la complexité numériques. L'application de l'application de SVD directement à la matrice de données est numériquement plus stable qu'à la matrice de covariance
  • SVD peut être appliqué à la matrice de covariance pour effectuer l'ACP ou obtenir des valeurs propres, en fait, c'est ma méthode préférée pour résoudre les problèmes propres

Il s'avère que SVD est plus stable que les procédures de décomposition à valeurs propres typiques, en particulier, pour l'apprentissage automatique. Dans l'apprentissage automatique, il est facile de se retrouver avec des régresseurs hautement colinéaires. SVD fonctionne mieux dans ces cas.

Voici du code Python pour démontrer le point. J'ai créé une matrice de données hautement colinéaire, obtenu sa matrice de covariance et essayé d'obtenir les valeurs propres de cette dernière. SVD fonctionne toujours, alors que la décomposition propre ordinaire échoue dans ce cas.

import numpy as np
import math
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 1000
X = np.random.rand(T,2)
eps = 1e-11
X[:,1] = X[:,0] + eps*X[:,1]

C = np.cov(np.transpose(X))
print('Cov: ',C)

U, s, V = LA.svd(C)
print('SVDs: ',s)

w, v = LA.eig(C)
print('eigen vals: ',w)

Sortie:

Cov:  [[ 0.08311516  0.08311516]
 [ 0.08311516  0.08311516]]
SVDs:  [  1.66230312e-01   5.66687522e-18]
eigen vals:  [ 0.          0.16623031]

Mise à jour

En réponse au commentaire de Federico Poloni, voici le code avec les tests de stabilité de SVD vs Eig sur 1000 échantillons aléatoires de la même matrice ci-dessus. Dans de nombreux cas, Eig affiche 0 petite valeur propre, ce qui conduirait à la singularité de la matrice, et SVD ne le fait pas ici. La SVD est environ deux fois plus précise sur une petite détermination de valeur propre, qui peut être importante ou non en fonction de votre problème.

import numpy as np
import math
from scipy.linalg import toeplitz
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 100
p = 2
eps = 1e-8

m = 1000 # simulations
err = np.ones((m,2)) # accuracy of small eig value
for j in range(m):
    u = np.random.rand(T,p)
    X = np.ones(u.shape)
    X[:,0] = u[:,0]
    for i in range(1,p):
        X[:,i] = eps*u[:,i]+u[:,0]

    C = np.cov(np.transpose(X))

    U, s, V = LA.svd(C)

    w, v = LA.eig(C)

    # true eigen values
    te = eps**2/2 * np.var(u[:,1])*(1-np.corrcoef(u,rowvar=False)[0,1]**2)
    err[j,0] = s[p-1] - te
    err[j,1] = np.amin(w) - te


print('Cov: ',C)
print('SVDs: ',s)
print('eigen vals: ',w)
print('true small eigenvals: ',te)

acc = np.mean(np.abs(err),axis=0)    
print("small eigenval, accuracy SVD, Eig: ",acc[0]/te,acc[1]/te)

Sortie:

Cov:  [[ 0.09189421  0.09189421]
 [ 0.09189421  0.09189421]]
SVDs:  [ 0.18378843  0.        ]
eigen vals:  [  1.38777878e-17   1.83788428e-01]
true small eigenvals:  4.02633695086e-18
small eigenval, accuracy SVD, Eig:  2.43114702041 3.31970128319

Ici, le code fonctionne. Au lieu de générer la matrice de covariance aléatoire pour tester les routines, je génère la matrice de données aléatoire avec deux variables: u , v - variables aléatoires uniformes indépendantes. Ainsi, la matrice de covariance est ( σ 2 1 σ 2 1 + ε ρ σ 1 σ 2 σ 2 1 + ε ρ σ 1 σ 2 σ 2 1 + 2 ε ρ σ 1 σ 2 + ε 2 σ 2 2 σ 2 )

x1=ux2=u+εv
u,v
(σ12σ12+ερσ1σ2σ12+ερσ1σ2σ12+2ερσ1σ2+ε2σ22σ2)
- variances des uniformes et coefficients de corrélation entre eux.σ12,σ22,ρ

Sa plus petite valeur propre:

λ=12(σ22ε2σ24ε4+4σ23ρσ1ε3+8σ22ρ2σ12ε2+8σ2ρσ13ε+4σ14+2σ2ρσ1ε+2σ12)
ε
λσ22ε2(1ρ2)/2

j=1,,mλ^jej=λλ^j

Aksakal
la source
4
Oui, mais OP demande ici SVD vs EIG appliqué à la fois à la matrice de covariance.
amibe dit Réintégrer Monica
1
@amoeba, j'ai clarifié la relation entre SVD et PCA
Aksakal
C'est une bonne réponse. Je souhaite, cependant, mentionner que svd ne peut pas détecter les valeurs propres négatives quand il y en a et que vous voulez les voir (si la matrice de covariance n'est pas originale mais est, par exemple, lissée ou estimée d'une manière ou d'une autre ou déduite ou sort de la suppression par paire des valeurs manquantes). De plus, eig sur la matrice cov reste un peu plus rapide que svd dessus.
ttnphns
@ttnphns, la matrice définie non positive est un problème, bien sûr
Aksakal
1
@FedericoPoloni, sur l'arithmétique FP et ne connaissant pas la réponse exacte, je ne suis pas d'accord. Dans ce cas, je connais la réponse avec suffisamment de précision pour cette tâche. Sur 2x2, vous avez un bon point. Je vais penser à quelque chose.
Aksakal
6

Pour les utilisateurs de Python, je voudrais souligner que pour les matrices symétriques (comme la matrice de covariance), il est préférable d'utiliser une numpy.linalg.eighfonction plutôt qu'une numpy.linalg.eigfonction générale .

eighest 9 à 10 fois plus rapide que eigsur mon ordinateur (quelle que soit la taille de la matrice) et a une meilleure précision (basée sur le test de précision de @ Aksakal).

Je ne suis pas convaincu de la démonstration de l'avantage de la précision de la SVD avec de petites valeurs propres. Le test d'Aksakal est de 1 à 2 ordres de grandeur plus sensible à l'état aléatoire qu'à l'algorithme (essayez de tracer toutes les erreurs au lieu de les réduire à un maximum absolu). Cela signifie que de petites erreurs dans la matrice de covariance auront un plus grand effet sur la précision que le choix d'un algorithme de décomposition par eigend. En outre, cela n'est pas lié à la question principale, qui concerne l'APC. Les plus petits composants sont ignorés dans PCA.

Un argument similaire peut être avancé à propos de la stabilité numérique. Si je dois utiliser la méthode de la matrice de covariance pour l'ACP, je la décomposerais avec eighau lieu de svd. S'il échoue (ce qui n'a pas encore été démontré ici), il vaut probablement la peine de repenser le problème que vous essayez de résoudre avant de commencer à chercher un meilleur algorithme.

Mosalx
la source
+1. Quelques informations sur eighvs eig: mail.scipy.org/pipermail/numpy-discussion/2006-March/…
dit
2

mnmn

Calculer la matrice de covariance puis effectuer SVD sur cela est beaucoup plus rapide que de calculer SVD sur la matrice de données complète dans ces conditions, pour le même résultat.

Même pour des valeurs assez petites, les gains de performances sont des facteurs de milliers (millisecondes vs secondes). J'ai effectué quelques tests sur ma machine pour comparer avec Matlab: entrez la description de l'image ici

C'est juste du temps CPU, mais les besoins de stockage sont tout aussi, sinon plus, importants. Si vous tentez SVD sur une matrice d'un million sur mille dans Matlab, il générera une erreur par défaut, car il a besoin d'une taille de tableau de travail de 7,4 To.

Bourru
la source
Cela ne répond pas à la question qui concerne le GIE de la matrice cov par rapport à la SVD de la matrice de covariance .
amoeba dit Reinstate Monica
1
Sa question à la fin, mise en évidence en gras, déclare: "Pourquoi font-ils des SVD de matrice de covariance, pas de matrice de données?" auquel j'ai répondu.
Gruff
Je vais modifier la phrase d'ouverture pour qu'il soit clair que je répondais à cette partie de la question du PO. Je vois comment cela pourrait être déroutant. Merci.
Gruff
Si vous tentez une SVD sur une matrice d'un million sur mille dans Matlab, cela entraînera une erreur par défaut. Les bonnes pratiques numériques utilisent le SVD fin, dans ces cas. Cela améliorera considérablement la taille et les performances du stockage.
Federico Poloni