Por que Andrew Ng prefere usar SVD e não EIG da matriz de covariância para fazer PCA?

29

Estou estudando PCA no curso Coursera de Andrew Ng e outros materiais. Na primeira tarefa do curso de PNL de Stanford, cs224n , e no vídeo da aula de Andrew Ng , eles fazem decomposição de valor singular em vez de decomposição de vetor próprio da matriz de covariância, e Ng até diz que o SVD é numericamente mais estável do que a composição automática.

Pelo meu entendimento, para o PCA, devemos fazer SVD da matriz de (m,n)tamanho de dados , não da matriz de covariância de (n,n)tamanho. E decomposição de vetores próprios da matriz de covariância.

Por que eles fazem SVD de matriz de covariância, não matriz de dados?

DongukJu
fonte
8
Para a matriz semidefinida positiva simétrica quadrada (como a matriz de covariância), as decomposições de autovalor e valor singular são exatamente as mesmas.
Ameba diz Reinstate Monica
5
Quero dizer, eles são matematicamente iguais. Numericamente, eles podem realmente usar algoritmos diferentes e um pode ser mais estável que o outro (como diz Ng). Seria interessante saber mais sobre +1.
Ameba diz Reinstate Monica
4
Algumas informações sobre isso aqui: de.mathworks.com/matlabcentral/newsreader/view_thread/21268 . Mas observe que qualquer explicação sobre por que um algoritmo seria mais estável que outro será muito técnica.
Ameba diz Reinstate Monica
2
No Matlab, x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc;minha máquina gera 12s para eig () e 26s para svd (). Se for muito mais lento, deve ser pelo menos mais estável! :-)
ameba diz Reinstate Monica
4
Isso pode se basear em um entendimento incorreto: fazer um SVD da matriz de dados é mais estável do que usar eigou svdna matriz de covariância, mas, tanto quanto eu sei, não há grande diferença entre usar eigou svdna matriz de covariância - eles são ambos algoritmos estáveis ​​para trás. De qualquer forma, eu colocaria meu dinheiro em eig sendo mais estável, já que ele faz menos cálculos (assumindo que ambos sejam implementados com algoritmos de última geração).
Federico Poloni

Respostas:

17

a ameba já deu uma boa resposta nos comentários, mas se você quiser uma discussão formal, aqui vai.

A decomposição do valor singular de uma matriz é , onde as colunas de são autovetores de e as entradas diagonais de são as raízes quadradas de seus autovalores, ou seja, .Um = L Σ V T V A T A Σ σ i i = AA=UΣVTVATAΣσii=λi(ATA)

Como você sabe, os componentes principais são as projeções ortogonais de suas variáveis ​​no espaço dos vetores próprios da matriz de covariância empírica . A variação dos componentes é dada por seus valores próprios, .λi(11n1ATAλi(1n1ATA)

Considere qualquer matriz quadrada , e um vetor tal que . Entãoα R v B v = λ vBαRvBv=λv

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

Vamos definir . O SVD de calculará a composição automática de para produzirSSTS=1S=1n1ATASSTS=1(n1)2ATAATA

  1. os autovetores de , que por propriedade 1 são os deA T A(ATA)TATA=ATAATAATA
  2. as raízes quadradas dos valores próprios de , que pela propriedade 2, depois 1 e 2 novamente são .1(n1)2ATAATA1(n1)2λi(ATAATA)=1(n1)2λi2(ATA)=1n1λi(ATA)=λi(1n1ATA)

Voilà!

Em relação à estabilidade numérica, seria necessário descobrir quais são os alogritmos empregados. Se você quiser, acredito que estas são as rotinas LAPACK usadas pelo numpy:

Atualização: Na estabilidade, a implementação do SVD parece estar usando uma abordagem de dividir e conquistar, enquanto a composição do eigend usa um algoritmo QR simples. Não consigo acessar alguns documentos SIAM relevantes da minha instituição (culpas na pesquisa), mas encontrei algo que pode apoiar a avaliação de que a rotina SVD é mais estável.

Em

Nakatsukasa, Yuji e Nicholas J. Higham. "Algum algoritmo de divisão e conquista espectral estável e eficiente para a decomposição simétrica de autovalores e o SVD". Revista SIAM sobre Computação Científica 35.3 (2013): A1325-A1349.

eles comparam a estabilidade de vários algoritmos de autovalor e parece que a abordagem de dividir e conquistar (eles usam o mesmo que numpy em um dos experimentos!) é mais estável que o algoritmo QR. Isso, junto com alegações em outros lugares de que os métodos de D&C são realmente mais estáveis, suporta a escolha de Ng.

broncoAbierto
fonte
Os autovalores que obtive de svd na covariância e svd nos dados médios centrados não são os mesmos.
theGD
No entanto, as pontuações, que são X * V (onde V é obtido de [U, S, V] = svd (x) ou svd (covx)), são as mesmas.
theGD
11
@theGD Os autovalores de cov (X) e os valores singulares de (X) não são idênticos, consulte stats.stackexchange.com/questions/134282 .
Ameba diz Reinstate Monica
não há necessidade de se desesperar com a falta de acesso aos periódicos do SIAM: o artigo que você cita está aqui: opt.mist.iu-tokyo.ac.jp/~nakatsukasa/publishedpdf/pub13.pdf
Dima Pasechnik
2
@broncoAbierto the tech. O relatório está aqui: cpsc.yale.edu/sites/default/files/files/tr932.pdf (provavelmente não é possível encontrá-lo facilmente devido a um erro de digitação "Symetric" no título em cpsc.yale.edu/research/technical-reports / 1992-technical-reports :-))
Dima Pasechnik
12

O @amoeba teve excelentes respostas às perguntas da PCA, incluindo esta em relação ao SVD e à PCA. Respondendo à sua pergunta exata, farei três pontos:

  • matematicamente, não há diferença se você calcula o PCA diretamente na matriz de dados ou em sua matriz de covariância
  • a diferença se deve exclusivamente à precisão e complexidade numéricas. A aplicação de SVD diretamente à matriz de dados é numericamente mais estável do que à matriz de covariância
  • O SVD pode ser aplicado à matriz de covariância para executar PCA ou obter valores de eigen, na verdade, é o meu método favorito de resolver problemas de eigen

Acontece que o SVD é mais estável do que os procedimentos típicos de decomposição de autovalor, especialmente para aprendizado de máquina. No aprendizado de máquina, é fácil acabar com regressores altamente colineares. SVD funciona melhor nesses casos.

Aqui está o código Python para demonstrar o ponto. Criei uma matriz de dados altamente colinear, obtive sua matriz de covariância e tentei obter os valores próprios deste último. O SVD ainda está funcionando, enquanto a decomposição do eigen comum falha nesse caso.

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)

Saída:

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

Atualizar

Respondendo ao comentário de Federico Poloni, aqui está o código com testes de estabilidade de SVD vs Eig em 1000 amostras aleatórias da mesma matriz acima. Em muitos casos, Eig mostra 0 pequeno valor de eigen, o que levaria à singularidade da matriz, e o SVD não faz isso aqui. O SVD é cerca de duas vezes mais preciso em uma pequena determinação de valor próprio, que pode ou não ser importante, dependendo do seu problema.

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)

Saída:

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

Aqui codifique o código funciona. Em vez de gerar a matriz de covariância aleatória para testar as rotinas, estou gerando a matriz de dados aleatórios com duas variáveis: onde - variáveis ​​aleatórias uniformes independentes independentes. Portanto, a matriz de covariância é que - variâncias dos uniformes e coeficiente de correlação entre eles.

x1=ux2=u+εv
u,v
(σ12σ12+ερσ1σ2σ12+ερσ1σ2σ12+2ερσ1σ2+ε2σ22σ2)
σ12,σ22,ρ

Seu menor valor próprio: O valor próprio pequeno não pode ser calculado simplesmente conectando o na fórmula devido à precisão limitada; portanto, você precisa expandi-lo por Taylor:

λ=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

Eu corro simulações das realizações da matriz de dados, calculo os autovalores da matriz de covariância simulada e obtenho os erros .λ j e j = λ - λ jj=1,,mλ^jej=λλ^j

Aksakal
fonte
4
Sim, mas aqui OP é perguntando sobre SVD vs EIG aplicado tanto para a matriz de covariância.
Ameba diz Reinstate Monica
11
@amoeba, esclarei a relação de SVD e PCA
Aksakal
Esta é uma boa resposta. Gostaria de mencionar, no entanto, que o svd não pode detectar autovalores negativos quando houver algum e você deseja vê-los (se a matriz de covariância não for original, mas for, digamos, suavizada ou estimada de alguma forma ou inferida ou inferida ou resultar de exclusão pareada) de valores ausentes). Além disso, o eig on cov matrix permanece um pouco mais rápido que o svd nele.
ttnphns
@ttnphns, matriz definida positivo não é um problema, é claro
Aksakal
11
@FedericoPoloni, na FP aritmética e sem saber a resposta exata que eu discordo. Nesse caso, eu sei a resposta com precisão suficiente para esta tarefa. Em 2x2 você tem um ponto justo. Vou pensar em alguma coisa.
Aksakal
6

Para usuários de Python, gostaria de salientar que, para matrizes simétricas (como a matriz de covariância), é melhor usar a numpy.linalg.eighfunção do que uma numpy.linalg.eigfunção geral .

eighé 9 a 10 vezes mais rápido que eigno meu computador (independentemente do tamanho da matriz) e tem melhor precisão (com base no teste de precisão do @ Aksakal).

Não estou convencido com a demonstração do benefício da precisão da SVD com pequenos autovalores. @ O teste de Aksakal é de 1-2 ordens de magnitude mais sensíveis ao estado aleatório do que ao algoritmo (tente plotar todos os erros em vez de reduzi-los a um máximo absoluto). Isso significa que pequenos erros na matriz de covariância terão um efeito maior na precisão do que a escolha de um algoritmo de composição automática. Além disso, isso não está relacionado à questão principal, que é sobre o PCA. Os menores componentes são ignorados no PCA.

Um argumento semelhante pode ser feito sobre estabilidade numérica. Se eu tivesse que usar o método da matriz de covariância para PCA, eu o decomporia em eighvez de svd. Se falhar (o que ainda não foi demonstrado aqui), provavelmente vale a pena repensar o problema que você está tentando resolver antes de começar a procurar um algoritmo melhor.

Mosalx
fonte
+1. Algumas informações sobre eighvs eig: mail.scipy.org/pipermail/numpy-discussion/2006-March/…
amoeba diz Reinstate Monica
2

Para responder à última parte da sua pergunta, "Por que eles fazem SVD da matriz de covariância, não da matriz de dados?" Eu acredito que é por razões de desempenho e armazenamento. Normalmente, será um número muito grande e, mesmo que seja grande, esperamos que .n m nmnmn

Calcular a matriz de covariância e depois executar o SVD é muito mais rápido do que calcular o SVD na matriz de dados completa sob essas condições, para o mesmo resultado.

Mesmo para valores razoavelmente pequenos, os ganhos de desempenho são fatores de milhares (milissegundos vs segundos). Fiz alguns testes na minha máquina para comparar usando o Matlab: insira a descrição da imagem aqui

Isso é apenas tempo de CPU, mas as necessidades de armazenamento são igualmente importantes, se não mais. Se você tentar SVD em uma matriz de um milhão por mil no Matlab, ocorrerá um erro por padrão, porque precisa de um tamanho de matriz de trabalho de 7,4 TB.

Gruff
fonte
Isso não responde à pergunta que é sobre EIG da matriz cov vs. SVD da matriz de covariância .
ameba diz Restabelecer Monica
11
Sua pergunta no final, destacada em negrito, afirma: "Por que eles fazem SVD da matriz de covariância, não da matriz de dados?" que eu respondi.
Gruff
Vou editar a frase de abertura para deixar claro que estava respondendo a essa parte da pergunta do OP. Eu vejo como isso pode ser confuso. Obrigado.
Gruff
Se você tentar SVD em uma matriz de um milhão por mil no Matlab, ocorrerá um erro por padrão. Boa prática numérica é usar o SVD fino, nesses casos. Isso melhorará muito o tamanho e o desempenho do armazenamento.
Federico Poloni 15/10