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?
pca
linear-algebra
svd
eigenvalues
numerics
DongukJu
fonte
fonte
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! :-)eig
ousvd
na matriz de covariância, mas, tanto quanto eu sei, não há grande diferença entre usareig
ousvd
na 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).Respostas:
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 = √A A=UΣVT V ATA Σ σ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(11n−1ATA λi(1n−1ATA)
Considere qualquer matriz quadrada , e um vetor tal que . Entãoα ∈ R v B v = λ vB α∈R v Bv=λv
Vamos definir . O SVD de calculará a composição automática de para produzirSSTS=1S=1n−1ATA S STS=1(n−1)2ATAATA
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
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.
fonte
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:
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.
Saída:
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.
Saída:
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.
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:
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 λ^j ej=λ−λ^j
fonte
Para usuários de Python, gostaria de salientar que, para matrizes simétricas (como a matriz de covariância), é melhor usar a
numpy.linalg.eigh
função do que umanumpy.linalg.eig
função geral .eigh
é 9 a 10 vezes mais rápido queeig
no 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
eigh
vez desvd
. 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.fonte
eigh
vseig
: mail.scipy.org/pipermail/numpy-discussion/2006-March/…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 ≫ nm n m≫n
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:
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.
fonte