18/09/2017
1
Single Value Decomposition
SVD
Lema. Toda matriz A, com n linhas e d colunas, admite uma fatoração A= UDVT= U é uma matriz com n linhas e r colunas (r rank de A) D é uma matriz diagonal r x r; V é uma matriz com d linhas e r colunas; U e V são ortonormais
SVD: Exemplo
SVD: Motivação
Lema. Toda matriz A, com n linhas e d colunas, admite uma fatoração A= UDVT
Aplicações
Enxergando A como uma matriz de dados (e.g. cada linha como um dado) temos aplicações em
– Compressão/ visualização
– Ranking
– Clustering
18/09/2017
2
SVD: Interpretação
SVD: Interpretação
• Garotos gostam de Sci-Fi • Meninas gostam de romance
SVD: Interpretação
Hipótese
• O rating de um usuário u para um filme f pode ser explicado pelo perfil de u (gosto em relação aos diferentes gêneros) e pelo pefil do filme f (aderência em relação aos diferentes gêneros)
• Generos não precisam ser conhecidos/escolhidos a priori
SVD: Interpretação
18/09/2017
3
SVD: Interpretação
Perfil de Joe em relação a Sci-Fi e Romance
Perfil de Star Wars em relação a Sci-Fi e romance
Peso do conceito Sci-Fi na interpretação
SVD: Interpretação
Exemplo com ratings mais misturados
SVD: Interpretação
Se A está contido em um subespaço de dimensão r então temos que
A= UDVT= .
• vi é a i-ésima direção ‘mais importante’ de A
• ui são os componentes dos pontos de A na direção vi
• i =D(i,i) é usado para dar um peso a direção vi
SVD: Interpretação
Se truncarmos a soma abaixo em k termos conseguimos aproximações/versões compactas da matriz de dados
18/09/2017
4
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 13
= x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02 -0.01
0.41 0.07 -0.03
0.55 0.09 -0.04
0.68 0.11 -0.05
0.15 -0.59 0.65
0.07 -0.73 -0.67
0.07 -0.29 0.32
12.4 0 0
0 9.5 0
0 0 1.3
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
0.40 -0.80 0.40 0.09 0.09
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 14
= x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02 -0.01
0.41 0.07 -0.03
0.55 0.09 -0.04
0.68 0.11 -0.05
0.15 -0.59 0.65
0.07 -0.73 -0.67
0.07 -0.29 0.32
12.4 0 0
0 9.5 0
0 0 1.3
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
0.40 -0.80 0.40 0.09 0.09
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 15
x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02 -0.01
0.41 0.07 -0.03
0.55 0.09 -0.04
0.68 0.11 -0.05
0.15 -0.59 0.65
0.07 -0.73 -0.67
0.07 -0.29 0.32
12.4 0 0
0 9.5 0
0 0 1.3
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
0.40 -0.80 0.40 0.09 0.09
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 16
x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02 -0.01
0.41 0.07 -0.03
0.55 0.09 -0.04
0.68 0.11 -0.05
0.15 -0.59 0.65
0.07 -0.73 -0.67
0.07 -0.29 0.32
12.4 0 0
0 9.5 0
0 0 1.3
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
0.40 -0.80 0.40 0.09 0.09
18/09/2017
5
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 17
x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02
0.41 0.07
0.55 0.09
0.68 0.11
0.15 -0.59
0.07 -0.73
0.07 -0.29
12.4 0
0 9.5
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
SVD: Redução de dimensionalidade
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,
http://www.mmds.org 18
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.92 0.95 0.92 0.01 0.01
2.91 3.01 2.91 -0.01 -0.01
3.90 4.04 3.90 0.01 0.01
4.82 5.00 4.82 0.03 0.03
0.70 0.53 0.70 4.11 4.11
-0.69 1.34 -0.69 4.78 4.78
0.32 0.23 0.32 2.01 2.01
SVD: Fundamentos
• Qual o conjunto de k direções que melhor ‘aproxima/representa’ um conjunto de n pontos em Rd ?
SVD: Fundamentos
• Qual o conjunto de k direções que melhor ‘aproxima/representa’ um conjunto de n pontos em Rd ?
• Qualidade da aproximação
– Soma do quadrado das distâncias dos pontos ao hiperplano gerado pelas direções (deve ser minimizada)
– Soma dos quadrados das projeções no subespaço gerado pelas direções (deve ser maximizada)
18/09/2017
6
• Com qual qualidade o vetor unitário v representa um ponto xi em Rd ?
• Maximizar o quadrado da norma da projeção é equivalente a minimizar o quadrado da distância perpendicular a v
SVD: Construção
|xi|=i2+i
2
Qual conjunto de k direções (vetores unitários) que melhor representa A?
SVD: Fundamentos
SVD: Fundamentos
Método guloso (todas as direções)
1. i1
2. Encontrar vetor unitário v1 tal que |Av1| é maximizado
3. Se i<d, seja vi+1 um vetor unitário ortogonal a v1,...,vi tal que |Avi+1| |Av| para todo v ortogonal a v1,...,vi.
a. Se |Avi+1 |>0, coloque vi+1 na coleção, incremente i e vá para o passo 3
4. Definir r como i
SVD: Fundamentos
Propriedade. Ao término do procedimento todos o n pontos da matriz A pertencem ao subespaço Vr gerado pelas direções v1,..., vr
Prova. Se um ponto a não pertence a Vr, a pode ser escrito como
a=va+v’,
onde va pertence a Vr e v’ é ortogonal a Vr.
Neste caso av’<> 0. Logo, teríamos |Av’|>0. Portanto, o algoritmo não teria parado
18/09/2017
7
SVD: Fundamentos
Método guloso (k primeiras direções fixas)
1. Encontrar vetor unitário v1 tal que |Av1| é maximizado
2. Enquanto i<k definir vi+1 como o vetor unitário ortogonal a v1,...,vi tal que |Avi+1 ||Av|
para todo v ortogonal a v1,...,vi.
Se |Avi+1 |>0, incremente i execute o Passo 2
Processo guloso leva a melhor representação?
SVD: Fundamentos
Definição. vi é o i-ésimo vetor singular a direita da matriz A
SVD: Fundamentos
Lema. Seja V um espaco de dimensão k e v1,..., vk uma base ortonomal para V. Além disso, seja W um espaço de dimensão k+1. Existe então, uma base ortonomal w1,..., wk+1 para W tal que wk+1 é ortogonal a V.
SVD: Fundamentos
18/09/2017
8
Prova. Seja pi a projeção de vi em W. Seja wk+1
um vetor em W ortogonal a p1 ,p2 ,...,pk. Note que wk+1 é ortogonal a vi, para i=1,..,k. Para ver isso note que vi=pi+p’i, onde p’i é ortogonal a W.
Podemos então obter uma base ortonormal w1,..., wk+1 para W.
SVD: Fundamentos
Teorema. Seja A uma matriz nxd com vetores singulares v1,..., vr . Para 1 k r, o espaço Vk gerado por v1,..., vk é o espaço k-dimensional que maximiza a soma dos quadrados das projeções dos n pontos (linhas de A)
SVD: Fundamentos
Teorema. Seja A uma matriz nxd com vetores singulares v1,..., vr . Para 1 k r, o espaço Vk gerado por v1,..., vk é o espaço k-dimensional que maximiza a soma dos quadrados das projeções dos n pontos (linhas de A)
Prova
• Para k=1, segue da definição do método.
• Passo de Indução: Se Vk é ótimo para dim k então Vk+1 é ótimo para dim k+1
SVD: Fundamentos
Prova (cont’d)
Seja W um subespaço ótimo de dim k+1 e seja w1,..., wk+1 uma base ortonormal para W, onde wk+1 é ortogonal a Vk
SVD: Fundamentos
18/09/2017
9
Prova (cont’d)
Por hipótese
|Aw1|2 +...+|Awk|2 |Av1|2 +...+|Avk|
2
Além disso, por construção
|Awk+1 |2 |Avk+1 |2
Somando as desigualdades provamos o resultado
SVD: Fundamentos
Observação. Avi é a lista dos comprimentos das projeções dos n pontos na direção vi
Definição . O i-ésimo valor singular da matriz A é i=|Avi|
SVD: Fundamentos
Exemplo
• Se v1 corresponde a Sci-Fi então – 1 =|Av1| é o peso de Sci-Fi
SVD: Fundamentos
v1 T 1
• 5 pontos em R5
• Os valores singulares da matriz acima são 17.92, 15.17, 3.56, 1.98, 0.35
SVD: Fundamentos
18/09/2017
10
• i pode ser vista como a componente de A na direção vi
SVD: Fundamentos
Propriedade. Seja ai a i-ésima linha da matriz A. Então
• A primeira igualdade abaixo decorre de que todo vetor ai pode ser escrito como uma combinação linear dos vetores ortonormais v1,...,vr
• A terceira e quarta igualdade seguem das definições
SVD: Fundamentos
• i dá uma idéia da variância capturada pela direção vi
• Os valores singulares da matriz acima são 17.92, 15.17,
3.56, 1.98, 0.35 • Os dois componentes principais já explicam cerca de
97% da variância: (17.922+15.172)/(17.922+15.172 +3.562+1.982+0.352)= (17.922+15.172)/564 =0.97
SVD: Fundamentos
• Os valores singulares são 12.4, 9.5 e 1.3.
• O primeiro valor corresponde a 62.5% da variância
• Os dois primeiros correspondem a 99.3% da variância
SVD: Fundamentos
43
= x x
1 1 1 0 0
3 3 3 0 0
4 4 4 0 0
5 5 5 0 0
0 2 0 4 4
0 0 0 5 5
0 1 0 2 2
0.13 0.02 -0.01
0.41 0.07 -0.03
0.55 0.09 -0.04
0.68 0.11 -0.05
0.15 -0.59 0.65
0.07 -0.73 -0.67
0.07 -0.29 0.32
12.4 0 0
0 9.5 0
0 0 1.3
0.56 0.59 0.56 0.09 0.09
0.12 -0.02 0.12 -0.69 -0.69
0.40 -0.80 0.40 0.09 0.09
18/09/2017
11
Definição. Seja ui= Avi / |Avi |. O conjunto de vetores u1,..., ur são os vetores singulares a esquerda da matriz A
SVD: Fundamentos
Exemplo
• Se v1 corresponde a Sci-Fi então – u1: aderência dos usuários em relação a Sci-Fi
SVD: Fundamentos
u1
v1 T
Lema. Os vetores u1,..., ur formam uma base ortonormal
SVD: Fundamentos
Teorema. A=UDVT
A: matriz de dados com n linhas e d colunas
U: matriz com n linhas e r colunas em que as colunas são os vetores singulares a esquerda,
D: matriz diagonal (rxr) formada pelos valores singulares
V: é a matriz com d linhas e r colunas em que as colunas são os vetores singulares a direita
SVD: Fundamentos
18/09/2017
12
Lema auxiliar. Se Av=Bv para todo vetor v então A=B
SVD: Fundamentos
Teorema. A=UDVT
Prova. Por causa do lema, basta mostrar que Av =(UDVT)v para todo vetor v. Caso 1) vj é uma direção principal. Segue que
A primeira igualdade segue da ortonomalidade dos vetores vj e a segunda da definição de uj
SVD: Fundamentos
Teorema. A=UDVT
Prova (cont’d). Caso 2) v’ é ortogonal a Vr , o subespaço gerado por v1 ,...,vr. Todo ai está em Vr Logo
A v’ = (UDVT) v’ = 0 Caso 3) v’ não é direção principal nem ortogonal a Vr . O resultado segue do fato que v’ pode ser escrito como combinação linear dos vetores em Vr somado a um vetor ortogonal a Vr .
SVD: Fundamentos Melhor aproximação de rank k
Seja
a aproximação para matriz A dada pelas k primeiras direções (vetores singulares) de A
18/09/2017
13
Melhor aproximação de rank k
Lema (3.5). As linhas de Ak são as projeções dos pontos (linhas de A) no subespaço Vk gerado pelas k direções principais v1,..,vk
Prova. Como os vi’s formam uma base ortonormal, a projeção do ponto a em Vk é dada por
Portanto, a projeção das linhas da matriz A é dada por
Melhor aproximação de rank k
Definição: Para uma matriz C a norma ||C |F é a raiz quadrada soma dos quadrados das entradas da matriz
• Se cada linha é vista como um ponto então
||C ||F 2 é a soma dos quadrados das distâncias
do ponto a origem
Melhor aproximação de rank k
Teorema. Para qualquer matriz B de rank no máximo k temos ||A-Ak ||F || A – B||F Prova (sketch) • Seja B uma matriz de rank no máximo k que minimiza
||A – B||F
• Seja V o subespaço gerado pelas linhas de B. Temos que cada linha de B é a projeção de A em V, caso contrário trocando as linhas de B pelas projeções das linhas de A em V diminuíriamos
||A – B||F.
Melhor aproximação de rank k
Teorema. Para qualquer matriz B de rank no máximo k temos ||A-Ak ||F || A – B|| F Prova (sketch) Segue do Teorema (análise do guloso) que ||Ak ||F ≥ ||B||F . Como
||A-Ak ||F + ||Ak||F = ||A|F e
||A-B||F + ||B|| F = ||A||F
temos que
||A-Ak ||F ||A – B||F
18/09/2017
14
Melhor aproximação de rank k
Interpretação/Consequência
• A matriz Ak provê a melhor representação possível em dimensão k dos n pontos em termos de erro quadrático.
• Se tentarmos representar os n pontos de A em um subespaço de dim k o erro quadrático será maior ou igual ao de Ak
Como calcular a decomposição SVD?
SVD: Método de potências
Seja B=ATA. Temos que
SVD: Método de potências
Seja B=ATA. É Possível mostrar que
Note que por construção 1 2 .... r > 0
Se 1 > 2
Portanto, podemos obter uma boa aproximação de v1 calculando Bk e normalizando sua primeira coluna.
SVD: Método de potências
18/09/2017
15
Complexidade
• Convergência do método depende de 1 - 2
• Método envolve multiplicação de matrizes, pode ser caro computacionalmente Exemplo
– Matriz A tem tamanho 108x108 com 109 entradas não nulas (esparsa)
– ATA tem tamanho 108x108 e não é esparsa. Inviável!
SVD: Método de potências
1. Seja (v1,v2 ,...,vd ) uma base ortonormal para Rd obtida estendendo a base v1,v2 ,...,vr
formada pelos vetores singulares. Além disso, seja x = c1v1 +c2v2 +.... +cd vd com c1 <>0
2. Se 1 > 2 então Bkx converge para 12k c1 v1
3. Como sabemos que v1 tem norma 1, podemos obter v1 normalizando 1
2k c1 v1
SVD: Método de potências II
1. Sejaa p e lo s veto res singu lares. Além d isso , seja x = c1v1 + c2v2 +... . + cd vd co m c1 <> 0
2 . Se 1 > 2 e ntão Bkx co nve rge para 12k c1 v1 3 . C o mo sab emos qu e v1 te m n orma 1, p odemo s ob ter v1 no rmal izan do 12k c1 v1
4. Para calcular Bkx fazemos Bx =AT(Ax) e Bkx =AT(ABk-1x)
5. Multiplicação entre matrizes são evitadas
– Apenas multiplicamos matrizes por vetores O(nd)
SVD: Método de potências II
Entrada: Matriz A de n linhas e d colunas Saída: vetor de dimensão d
1. Escolha um vetor aleatório x com norma 1 utilizando
uma distribuição gaussiana 2. Repita xoldx xAT(Ax) y x normalizado ; yold xold normalizado Até que |y-yold|< err 3. Devolva y
SVD: Método de potências II
18/09/2017
16
Propriedades do método
1. Se o maior valor singular for maior que o segundo maior singular de A então o método converge para v1
2. Se o maior valor singular for igual ao segundo maior valor singular o método converge para um vetor no espaço de gerado pelas direções principais associadas aos ‘maiores’ valores singulares (Teorema 3.11 e Lema 3.12 de FDS)
SVD: Método de potências II
1. Método apresentado apenas permite obter v1
2. Para obter vk+1 dado que já obtemos v1,v2,..., vk
utilizar o método anterior em A - Ak ,onde
SVD: Método de potências II
Fatos Importantes: Resumo
Lema. Toda matriz A, com n linhas e d colunas, admite uma fatoração A= UDVT= U é uma matriz com n linhas e r colunas (r rank de A) D é uma matriz diagonal r x r; V é uma matriz com d linhas e r colunas; U e V são ortonormais
Fatos Importantes: Resumo
• V é uma matriz com d linhas e r colunas;
– As colunas v1,…,vr de V são as direções principais da matriz A, vetores singulares a direita
– Para todo k, os vetores v1,…, vk definem um subespaço Vk de dimensão k tal que a projeção da matriz A neste subespaço é a maior possível dentre todos os subespaços de dimensão k
18/09/2017
17
Fatos Importantes: Resumo
• D é uma matriz diagonal r x r;
– O valor de D(i,i) é i=|Avi|
– i é o i-ésimo valor singular e pode ser interpretado como a importância da i-ésima direção principal
– A seguinte igualdade é importante
A 𝐹2 = 𝜎𝑖
2𝑟𝑖=
Fatos Importantes: Resumo
• U é uma matriz com n linhas e r colunas
– As colunas u1 ,..., ur de U são os vetores singulares a direita de A
– ui são as projeções das linhas de A na direnção vi
após uma normalização, ou seja, u = Avi / i
• A matriz é a projeção da matriz A no subespaço gerado por v1,…,vk.
• Para toda matriz B de rank k, |A-B|F ≥|A-Ak|F
– A k minimiza o erro quadrático dentre as matrizes de rank k
Fatos Importantes: Resumo Bibliografia
• Cap 3. Foundations of Data Science, Avrim Blum, John Hopcroft and Ravindran Kannan http://www.cs.cornell.edu/jeh/book.pdfs