MO431A - Tarefa 2

Data limite: Entregue um pdf, via email ou impresso, até as 10h do 3/4

Pode ser feito individualmente ou em duplas.

Para este projeto você precisa ter o Python 3.X, numpy, matplotlib e sklearn. Provavelmente você deve também usar o jupyter como modo interativo já que ele imprime as imagens (veja abaixo) na pagina com a interação.

1 Leia o arquivo X.npy

npy é um formato do numpy para armazenar matrizes de forma mais compacta que usando, por exemplo, um .csv

o numpy.load lê arquivos npy

X é um arquivo de 3023 linhas e 1850 colunas. Mas cada linha é na verdade uma imagem em tons de cinza de 50 por 37 pixels de pessoas famosas

X.npy esta em [http://www.ic.unicamp.br/~wainer/cursos/1s2019/X.npy

2 Imprima a imagem da primeira pessoa.

a função imshow do subpacote pyplot do matplotlib imprime uma imagem. Mas cada linha da matriz X precisa ser transformada numa matriz 50x37 para que o imshow funcione (veja o reshape do numpy). Ha também a codificação de cores da imagem; como a imagem é em tons de cinza a codificação é a cm.gray

3 Faça a fatoração svd da matriz X.

A função é svd, do subpacote linalg do numpy faz a fatoração svd.

Lembre-se que há duas formulações para a fatoração SVD

A = U D V^T

onde A é m x n.

Na primeira formulação (do wikipedia por exemplo),

U é m x m
D é m x n
e V^T é n x n

Esta fatoração é obtida pelo svd quando o parâmetro full_matrices é True

A segunda formulação (usada neste post sobre redução de dimensionalidade

U é m x n
D é n x n
e V^T é n x n

que é obtida quando full_matrizes é False.

Gere as 2 fatorações svd e mostre que as matrizes são dos tamanhos corretos.

4 Verifique a 2a formulação

Verifique o maior valor em modulo da diferença

X - (U D V^T)

usando a 2a formulação. O maior valor em modulo é o maior erro da fatoração em relação a algum dado original. Compare esse valor do maior erro com o valor médio dos dados em X. Verifique que o erro é bem baixo.

Note que o svd do numpy não retorna D como uma matriz (n x n) mas sim como um vetor com os elementos da matriz diagonal.

5 Compute a matriz reduzida e a matriz reconstruída

Vamos usar a redução para 150 dimensões.

5.1 matriz reduzida

O objetivo da redução da dimensionalidade da matriz X (3023 x 1850) é obter uma matriz com menos colunas \(k < 1859\) que representa mais ou menos a mesma informação que X, mas com menos espaço de memória.

Neste exercício, vamos usar k=150, ou seja queremos projetar cada imagem (que esta num espaço de 1850 dimensões) no melhor subespaço de 150 dimensões (menos de 10%) que representa ainda dos dados. Ou de outra forma, encontrar o subespaço de 150 dimensões cujo erro (quadrado) entre o dado original e sua projeção nesse subespaço seja a menos possível.

A matriz reduzida de X se 150 dimensões será uma matriz de 3023 linhas (o mesmo numero de dados/imagens) mas de 150 colunas.

A formula para a matriz reduzida é:

XD = U_k D_k

onde

-U_k é a matriz U com apenas as primeiras k colunas -D_k é a matriz diagonal D com apenas as primeiras k linhas e colunas

5.2 matriz reconstruída

A matriz reconstruída é uma matriz no espaço original (de 1850 dimensões) onde em vez da posição original de cada ponto, a linha representa a posição (no espaço de 1850 dimensões) da projeção do ponto no subespaço de 150 dimensões.

A matriz reconstruída deve ter 1850 dimensões mas em vez da imagem original. temos a imagem quando projetada no subespaço de 150 dimensões da redução.

A formula para a matriz reconstruída XC é

XC = U_k D_k V^T_k

onde -V^T_k são as k primeiras linhas de V^T

Gere as matrizes reduzidas e reconstruídas com redução para 150 dimensões

6 Imprima a imagem reconstruída da 1a pessoa redução

Compare com a imagem original impressa acima

7 Use o TruncatedSVD do scikit-learn

O pacote scikit-learn, ou sklearn, para aprendizado de maquina, contém a função TruncatedSVD que ja faz o processo de reduzir a dimensionalidade dos dados usando SVD. Na verdade esta função é mais rápida que o processo feito acima, ja que ele não computa a fatoração SVD completa, mas usa algoritmos que só computam os k primeiros componentes do U do D e do V^T.

Obtenha a matriz reduzida e a matriz reconstruída dos dados usando o TruncatedSVD.

Imprima a imagem da 1a pessoa da matriz reconstruída

8 Imprima as imagens das eigenfaces

Embora a ideia de auto0vetores (eigenvectors) é definida para matrizes quadradas, há um correspondente de auto-vetores no SVD. As linhas da matriz V^T são algo como auto-vetores. Em particular as primeiras 150 linhas de V^T (o que chamamos de V^T_k) são as bases do espaço de 150 dimensões para os quais estamos projetando os dados.

Isto é, cada imagem reconstruída é uma combinação linear dessas bases.Essas bases são chamadas na literatura de eigenfaces.

Imprima a primeira, segunda, 50-ésima e 150-ésima base (eigenfaces).