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?
pca
linear-algebra
svd
eigenvalues
numerics
DongukJu
la source
la source
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! :-)eig
ousvd
sur la matrice de covariance, mais pour autant que je sache, il n'y a pas de grande différence entre utilisereig
ousvd
sur 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).Réponses:
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 = √UNE A = UΣ VT V ATA Σ .σ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(11n−1ATA .λi(1n−1ATA)
Considérons toute matrice carrée , α ∈ R et un vecteur v tel que B v = λ v . ensuiteB α∈R v Bv=λv
Définissons . La SVD deScalculera la composition propre deSTS=1S=1n−1ATA S pour donnerSTS=1(n−1)2ATAATA
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
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.
la source
@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:
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.
Sortie:
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.
Sortie:
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: où 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 )
Sa plus petite valeur propre:
la source
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.eigh
fonction plutôt qu'unenumpy.linalg.eig
fonction générale .eigh
est 9 à 10 fois plus rapide queeig
sur 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
eigh
au lieu desvd
. 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.la source
eigh
vseig
: mail.scipy.org/pipermail/numpy-discussion/2006-March/…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:
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.
la source