[Algoritmo] [PLN#2] PCA, SVD e Latent Semantic Analysis

Latent Semantic Analysis



O que é Latent Semantic Analisys (também conhecida como "Latent Semantic Indexing")?

Anteriormente foi citado em nossa série sobre Processamento de Linguagem Natural que um dos problemas recorrentes desta área é a falta de estrutura em textos escritos em linguagem natural. Uma das tentativas de criar uma base de dados passível de ser manipulada é a redução de um texto a um vetor de frequência de palavras. 

Sentença: Minha casa é amarela e fica entre uma casa vermelha e outra verde.
Vetor de palavras: [[Casa - Fr: 2], [minha - Fr:1]] ...

Podemos ainda dizer que as palavras que aparecem frequentemente em um texto podem ser mais significantes. Esta informação pode ser utilizada como base para construção de ferramentas como detectores de SPAM ou análise de sentimentos. 

Um dos problemas desta abordagem é a grande quantidade de sinônimos e polissemia em textos de linguagem natural. Na lingua inglesa encontramos palavras como:

"buy" e "purchase"
"big" e "large"
"quick" e "Speedy"

Exemplo de polissemia:

"man" - pode ser utilizado para se referir ao oposto de um animal, ou oposto a fêmea do homem (mulher), ou apenas com sentido casual "hey, man!".

"milk" - pode se referir ao liquido gerado por mamíferos " the cat is producing milk for its babies" ou também pode se referir a tirar vantagem de uma condição ou situação. "I'm going to milk it for all it's worth".


Então uma forma de resolver este problema é combinar palavras com um significado semelhante. Logo você poderá ver as palavras Desktop e PC juntas, pois seu significado é altamente relacionado.


O trabalho do algoritmo de Latent Semantic Analisys (LSA) é encontrar variáveis que possam representar um conjunto de palavras com o mesmo significado. Assim, seria possível que a dimensionalidade dos dados analisados seja bem menor que o original, possibilitando um processamento mais rápido dos dados. 

É importante notar que o LSA ajuda a resolver o problema dos sinônimos combinando variáveis correlatas, porém existe ainda o problema da polissemia no qual este algoritmo não trata.

PCA e SVD recap


LSA é basicamente a aplicação de SVD para uma matriz de termos. O PCA é uma versão mais simples do SVD.

SVD = singular value decomposition
PCA = principal components analysis

Vamos olhar primeiro para o PCA, entender o que este algoritmo faz  de uma forma geral. Seu objetivo é transformar todos vetores de entrada. O método consiste em uma multiplicação de matrizes, isto se torna perceptível quando multiplicamos um vetor por um outro vetor escalar em uma mesma direção, mas se você multiplicar um vetor por uma matriz você obterá um vetor em uma direção diferente. Assim, o PCA rotaciona a entrada inicial ou então podemos dizer que ela utiliza o mesmo vetor porém com um sistema de coordenadas rotacionado.

O PCA faz 3 tarefas:

1- Descorrelaciona todos os dados. Logo, os dados processados tem 0 correlações entre 2 entradas.

2 - Ordena cada nova dimensão em ordem decrescente pela quantidade de informação que ela carrega. 

3- Possibilita reduzir a dimensionalidade, sendo que se o conjunto inicial tem um vocabulário de 1000 palavras, poderíamos encontrar que quando juntamos as palavas pela quantidade de vezes que elas co-ocorrem em um documento o total de termos que são "Latentes" são apenas 100. Assim é possível cortar a alta dimensionalidade considerando que apenas uma baixa quantidade de termos contém os dados importantes. 

Entenda que reduzindo as informações, nem sempre você estará reduzindo a habilidade de predição. Uma perspectiva do PCA é que ele realiza a remoção de ruidos. Com o processamento de linguagem natural o vocabulário é bastante grande, e os ruídos são bastante comuns, então ao retirar o ruido é possível realizar melhor a generalização e uma forma nova de olhar os novos dados.

A ideia central por trás desta técnica é a matriz de covariância. As diagonais de uma matriz de covariância dizem que a variância de determinada dimensão. Fora das diagonais os são exibidas como duas dimensões diferentes estão correlacionadas.

Lembrando que para a maioria dos métodos estatísticos consideramos que uma maior variância é sinônimo de mais informação. Caso uma variável que contenha 0 informações e se pudermos prever que esta variável sempre será zero podemos eliminar este atributo.


A covariância é definida pelo seguinte algoritmo:

C(i,j) = E [X_ i - mu(i)) (X_ j - mu(j))]

Onde mu(i) é a média de X_i (iésima posição de X)

Se i = j  => exemplo de variância

Um exemplo de covariância

C(i,j) = sum [n=1..N] { X [n,i] - mu[i]) X[n,j] - mu[j])} / N


Uma forma mais conveniente desta equação é a notação de matriz - A matriz "X transpõe" X vezes dividido por "N". Note que dispensamos as médias desde que nós podemos centralizar os dados antes de realizar qualquer processamento.

C = X ^ T X / N

Podemos assumir que isso é correto desde que "X transposto" é D x N e "X" é N x D, então o resultado é D x D.

Agora temos D x D que é a matriz de covariância, agora devemos encontrar os valores e vetores gerados

Cq = lambda q

Colocamos estes valores em matrizes colocando os valores gerados na diagonal  da matriz chamada de "big lambda" quando nós empilhamos os vetores gerados em uma matriz chamada de "Q", como vimos anteriormente. Nós ordenamos os valores gerados e os vetores em ordem descendente.

Em forma de matriz temos o 

CQ = Q Lambda

Nós podemos provar que o Big Lambda é atualmente somente a covariância transformada em dados. Sendo que todas fora das diagonais são 0, sendo isto a matriz diagonal, isto significa que as médias transformadas é completamente desrelacionadas.

Desde que somos livres para ordenar esses valores em qualquer ordem que quisermos nós podemos assegurar que os maiores valores gerados vêm primeiro. Tendo em mente sempre que estes valores são variâncias transformadas em dados.


Single Value Decomposition

Agora que compreendemos que o PCA localiza correlações entre os inputs. Estamos preparados para compreender o funcionamento do SVD. 

O SVD apenas realiza dois PCAs ao mesmo tempo. Então os valores gerados de X X^T  são chamados de U. Logo após chamamos os valores gerados de X ^ T X, e chamamos de V.

Lembre-se que alinhamos estes vetores gerados para que eles correspondessem aos valores gerados em ordem descendente. No SVD, temos a raiz quadrada do valor gerado e colocamos uma matriz chamada S.

Realizando todo este processo podemos relacionar X, U, S, e V, da seguinte forma:

X = USV ^ T

É por este motivo que o método é chamado de "Singular Value Decomposition".


Usando LSA 

Para este exemplo iremos utilizar um dataset chamado book titles. 

import nltk
import numpy as np
import matplotlib.pyplot as plt
import from nltk.stem import WordNetLemmatizer
from sklearn.decomposition import Truncated SVD

wordnet_lemmatizer = WordnetLemmatizer()

titles = [ line.rstrip() for line in open ('all_book_titles.txt')]

Tudo isso é bastante similar ao que realizamos anteriormente. Posteriormente definimos o tokenizador.

def my_tokenizer(s):
s = s.lower() 
tokens = nltk.tokenize.word_tokenize(s)
into words (tokens)
tokens = [t for t in tokens if len(t) > 2 ] # remove palavras pequenas pois 
provavelmente não serão úteis
tokens = [t for t in tokens if t not in stopwords] # remove stopwords
tokens = t for t in tokens if not any (c.isdigit() for c in t)] # remove qualquer dígito

return tokens


Agora criaremos um mapa de indexação:

word_index_map = {}
current_index = 0 

all_tokens = []
all_titles  = []
index_word_map  = []
for title in titles:
try:
title  = title.encode('ascii', 'ignore') #exception se houver um caractér errado
exception if bad characters
all_titles.append(title)
tokens = my_tokenizer(title)
all_tokens.append(tokens)
for token in for tokens:
if token not in word_index_map:
word_index_map[token] = current_index
current_index += 1 
index_word_map.append(token)
except:
pass


Definimos algumas funções para tornar nossos tokens em um vetor:

x = np.zeros(len(word_index_map))
for t in tokens:
i = word_index_map[t]
x[i] = 1
return x

Note que neste exemplo não temos nenhum rótulo. O PCA e o SVD são algoritmos não supervisionados, ou seja, eles aprendem a partir da estrutura dos dados e não para realizar predições.

a seguir nós criamos a matriz de dados 

N = len(all_tokens)
D = len(word_index_map)
X = np.zeros((D, N)) # termos irão a partir das linhas, documentos a partir das colunas.
i = 0
for tokens in all_tokens:
x [:,i = tokens_to_vector(tokens)
i +=1

Note como nós divergimos da nossa matriz normal N x D e ao invés disso criamos D x N.

Finalmente, vamos usar o SVD para criar um scatterplot dos dados, ou seja reduzi-los a 2 dimensões e anotar cada ponto com sua palavra correspondente. 

svd = TruncatedSVD()
Z = svd.fir_transform(X)
plt.scatter(Z[:,0], [:,1])
for i in xrange (D):
plt.annotate( s= index_word_map[i], xy  = (z[i,0], Z[i,1]))
plt.show()



Este capítulo foi traduzido do livro "Natural Language Processing in Python". Ele está disponível para compra na Amazon por apenas $5,00 neste endereço.

[Algoritmo] [PLN#2] PCA, SVD e Latent Semantic Analysis [Algoritmo] [PLN#2] PCA, SVD e Latent Semantic Analysis Reviewed by Vinicius dos Santos on 12:58:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!