Qual é a intuição por trás do SVD?

50

Eu li sobre decomposição de valor singular (SVD). Em quase todos os livros didáticos, é mencionado que ela fatoriza a matriz em três matrizes com determinada especificação.

Mas qual é a intuição por trás da divisão da matriz dessa forma? O PCA e outros algoritmos para redução de dimensionalidade são intuitivos no sentido de que o algoritmo possui uma boa propriedade de visualização, mas com SVD não é o caso.

SHASHANK GUPTA
fonte
4
Você pode querer começar com a intuição da decomposição de autovalor-autovetor, pois o SVD é uma extensão para todos os tipos de matrizes, em vez de apenas quadradas.
JohnK
Há muitas notas na internet e respostas aqui no CV sobre SVD e seu funcionamento.
Vladislavs Dovgalecs 15/10
2
O SVD pode ser pensado como um algoritmo de compressão / aprendizado. É um descompressor linear de compressor. Uma matriz M pode ser representada pela multiplicação de SVD. S é o compressor V determina quanto erro você gostaria de ter (compressão com perda) e D é o descompressor. Se você mantiver todos os valores diagonais de V, terá um compressor sem perdas. Se você começar a jogar fora pequenos valores singulares (zerando-os), não poderá reconstruir a matriz inicial exatamente, mas ainda estará próximo. Aqui o termo fechar é medido com a norma de Frobenius.
Cagdas Ozgenc 15/10/2015
2
@ Cartas, se você fizer isso, defina cuidadosamente o que você está usando "S" "V" e "D" como matematicamente. Eu nunca vi as iniciais sobrecarregadas na própria notação antes (que tem os valores singulares, por exemplo?). Parece ser uma fonte provável de confusão,
Glen_b
3
Você sabe estimar o PCA com SVD? Se sim, você pode explicar por que sente que algo está faltando na sua compreensão do SVD? Veja isto
Aksakal

Respostas:

63

Escreva o SVD da matriz (real, n × p ) como X = U D V T onde U é n × p , D é diagonal p × p e V T é p × p . Em termos das colunas das matrizes U e V , podemos escrever X = p i = 1 d i u i v T iXn×p

X=UDVT
Un×pDp×pVTp×pUVX=i=1pdiuiviT. Isso mostra escrito como uma soma de p matrizes de classificação 1. Como é uma matriz de classificação 1? Vamos ver: ( 1 2 3 ) ( 4 5 6 ) = ( 4 5 6 8 10 12 12 15 18 ) As linhas são proporcionais e as colunas são proporcionais.Xp
(123)(456)=(45681012121518)

Pense agora em como contendo os valores em escala de cinza de uma imagem em preto e branco, cada entrada na matriz representando um pixel. Por exemplo, a seguinte imagem de um babuíno:X

imagem de um babuíno

Em seguida, leia esta imagem no R e obtenha a parte da matriz da estrutura resultante, talvez usando a biblioteca pixmap.


Se você deseja um guia passo a passo de como reproduzir os resultados, pode encontrar o código aqui .


Calcule o SVD:

baboon.svd  <-  svd(bab) # May take some time

512×512512512120

baboon.1  <-  sweep(baboon.svd$u[,1,drop=FALSE],2,baboon.svd$d[1],"*") %*%
                   t(baboon.svd$v[,1,drop=FALSE])

baboon.20 <-  sweep(baboon.svd$u[,1:20,drop=FALSE],2,baboon.svd$d[1:20],"*") %*%
                   t(baboon.svd$v[,1:20,drop=FALSE])

resultando nas duas imagens a seguir:

classificação um e classificação 20 reconstrução da imagem babuíno

À esquerda, podemos ver facilmente as listras verticais / horizontais na imagem de classificação 1.

20

imagem de resíduos da reconstrução de babuínos no ranking 20

O que é bastante interessante: vemos as partes da imagem original que são difíceis de representar como superposição de linhas verticais / horizontais, principalmente pêlos do nariz na diagonal e alguma textura e os olhos!

kjetil b halvorsen
fonte
11
Eu acho que você quis dizer reconstrução de baixo escalão, não de baixo alcance. Deixa pra lá. Esta é uma ilustração muito boa (+1). É por isso que é um descompressor de compressor linear. A imagem é aproximada com linhas. Se você realmente executar um codificador automático semelhante com uma rede neural com funções de ativação linear, verá que ele também permite linhas com qualquer inclinação, não apenas as linhas verticais e horizontais, o que o torna um pouco mais poderoso que o SVD.
Cagdas Ozgenc 28/10/2015
X=UΣVn×pXUn×nΣn×pVp×p
11
Veja math.stackexchange.com/questions/92171/... para alguns outros exemplos
b Kjetil Halvorsen
@ kjetil-b-halvorsen Estou interessado em saber como a descrição mudaria se eu tivesse usado o PCA para recusar o aplicativo. Eu gostaria que você pudesse responder minha pergunta aqui stats.stackexchange.com/questions/412123/…
Dushyant Kumar
@CowboyTrader observação interessante. Minha compreensão do aprendizado de máquina / rede neural é bastante limitada. Portanto, não entendo que, se alguém tem uma única imagem barulhenta e mais nada para treinar, como a rede neural funcionaria?
Dushyant Kumar
4

Am×nmnvA

(1)v1=argmaxvRnAv2subject to v2=1.
v1A
v2=argmaxvRnAv2subject to v1,v=0,v2=1.
v1,,vnRnRnA

Seja (então quantifica a potência explosiva de na direção ). Suponha que os vetores unitários sejam definidos de forma que As equações (2) podem ser expressas de forma concisa usando a notação da matriz como onde é a matriz cuja coluna é , é a matriz cuja a coluna é eσi=Avi2σiAviui

(2)Avi=σiuifor i=1,,n.
(3)AV=UΣ,
Vn×niviUm×niuiΣé o matriz diagonal cuja th entrada diagonal é . A matriz é ortogonal, então podemos multiplicar os dois lados de (3) por para obter Pode parecer que agora derivamos o SVD de com quase zero esforço. Até agora, nenhuma das etapas foi difícil. No entanto, falta uma parte crucial da imagem - ainda não sabemos que é ortogonal.n×niσiVVT
A=UΣVT.
AU

Aqui está o fato crucial, a peça que faltava: acontece que é ortogonal a : Eu afirmo que se isso não fosse verdade, então não seria o ideal para o problema (1). De fato, se (4) não fosse satisfeito, seria possível melhorar perturbando-o um pouco na direção .Av1Av2

(4)Av1,Av2=0.
v1 v1v2

Suponha (por uma contradição) que (4) não seja satisfeito. Se estiver ligeiramente perturbado na direção ortogonal , a norma de não será alterada (ou, pelo menos, a alteração na norma de será desprezível). Quando eu ando na superfície da terra, minha distância do centro da terra não muda. No entanto, quando é perturbado na direção , o vetor é perturbado na direção não ortogonal e, portanto, a alteração na norma de não é desprezível . A norma dev1v2v1v1v1v2Av1Av2Av1Av1pode ser aumentado em uma quantidade não desprezível. Isso significa que não é ideal para o problema (1), que é uma contradição. Adoro esse argumento porque: 1) a intuição é muito clara; 2) a intuição pode ser convertida diretamente em uma prova rigorosa.v1

Um argumento semelhante mostra que é ortogonal a e e assim por diante. Os vetores são ortogonais aos pares. Isso significa que os vetores unitários podem ser escolhidos para serem ortogonais em pares, o que significa que a matriz acima é uma matriz ortogonal. Isso completa nossa descoberta do SVD.Av3Av1Av2Av1,,Avnu1,,unU


Para converter o argumento intuitivo acima em uma prova rigorosa, devemos confrontar o fato de que se é perturbado na direção , o vetor perturbado não é verdadeiramente um vetor unitário. (Sua norma é .) Para obter uma prova rigorosa, defina O vetor é realmente um vetor de unidade. Mas, como você pode mostrar facilmente, se (4) não for satisfeito, então, para valores suficientemente pequenos de , temos (assumindo que o sinal dev1v2

v~1=v1+ϵv2
1+ϵ2
v¯1(ϵ)=1ϵ2v1+ϵv2.
v¯1(ϵ)ϵ
f(ϵ)=Av¯1(ϵ)22>Av122
ϵé escolhido corretamente). Para mostrar isso, basta verificar se . Isso significa que não é ideal para o problema (1), que é uma contradição.f(0)0v1

(A propósito, eu recomendo a leitura da explicação de Qiaochu Yuan sobre o SVD aqui . Em particular, dê uma olhada no "Lema principal nº 1", que é o que discutimos acima. Como diz Qiaochu, o principal lema nº 1 é "o coração técnico de decomposição de valor singular ".)

littleO
fonte
0

Cara, tire uma hora do seu dia e assista a esta palestra: https://www.youtube.com/watch?v=EokL7E6o1AE

Esse cara é super direto, é importante não pular nada, porque tudo acaba junto no final. Mesmo que pareça um pouco lento no começo, ele está tentando identificar um ponto crítico, o que faz!

Vou resumir para você, em vez de apenas fornecer as três matrizes que todo mundo faz (porque isso estava me confundindo quando li outras descrições). De onde vêm essas matrizes e por que as configuramos assim? A palestra acertou em cheio! Toda matriz (sempre na história da eternidade) pode ser construída a partir de uma matriz base com as mesmas dimensões, depois girá-la e esticá-la (esse é o teorema fundamental da álgebra linear). Cada uma dessas três matrizes que as pessoas jogam representa uma matriz inicial (U), uma matriz de escala (sigma) e uma matriz de rotação (V).

A matriz de escala mostra quais vetores de rotação estão dominando, esses são chamados de valores singulares. A decomposição está resolvendo para U, sigma e V.

Tim Johnsen
fonte