Introduction to Information Retrieval
Introduction to
Information Retrieval
CS276: Information Retrieval and Web Search
Christopher Manning and Prabhakar Raghavan
Lecture 13: Matrix Decompositions and Latent
Semantic Indexing (LSI)
Eduardo Augusto Silvestre
Introduction to Information Retrieval
Ch. 18
Aula de hoje
 Seção 18.1.1: desenvolve-se a noção de
matrix decomposition.
 Seção 18.2: usa uma forma especial de
decomposição de matriz para construir
um low-rank approximation.
 Seção 18.3: usa low-rank approximation e
a técnica de latent semantic index.
Introduction to Information Retrieval
Ch. 18
Aula de hoje
 Latent Semantic Index (LSI)
 Matriz termo-documento muito grande
 Podemos representar o espaço termodocumento por um espaço latente
dimensional mais baixo?
Introduction to Information Retrieval
Linear Algebra
Background
Sec. 18.1
Introduction to Information Retrieval
Autovalores & Autovetores
 Autovetores (p/ uma matriz quadrada S, mm)
Exemplo
(direita) autovetor
autovalores
 Quantos autovalores existem no máximo?
só tem uma solução não nula se
Essa é uma equação de m-ésima ordem em que λ
pode ter no máximo m soluções distintas (raízes do
polinômio característico) – pode ser complexo, mesmo S
como real.
Introduction to Information Retrieval
Sec. 18.1
Multiplicação de matriz vetor
30 0 0


S  0 20 0 Tem autovalores 30, 20, 1 com
correspondente autovetores


0
0
1


1
0
0
 
 
 
v3   0 
v1   0 
v2   1 
1
0
0
 
 
 
Cada autovetor, S age como um múltiplo da matriz
identidade: mas como um múltiplo diferente em cada
2
um.
 
4
Qualquer vetor (ex. x=
) pode ser visto como uma
6
 
combinação dos autovetores:
x = 2v1 + 4v2 + 6v3
Introduction to Information Retrieval
Sec. 18.1
Multiplicação matriz-vetor
 Assim uma multiplicação matrix-vetor tal como Sx (S,
x como no slide anterior) pode ser reescrita em
termos dos autovalores/vetores:
Sx  S(2v1  4v 2  6v 3)
Sx  2Sv1  4Sv2  6Sv 3 21v1  4 2v 2  6  3 v 3
Sx  60v1  80v 2  6v 3
 Pensando até mesmo em x como um vetor arbitrário,
a ação de S em x é determinada pelo
autovalores/autovetores.
Sec. 18.1
Introduction to Information Retrieval
Multiplicação matriz vetor
 Sugestão: o efeito de “pequenos” autovalores é
pequeno.
 Se ignormarmos o menor autovalor(1), então ao
invés de
60
 
80
 
6 
obteríamos
60
 
80
 
0 
 São vetores similares (na similaridade de cossenos,
 etc.)

Introduction to Information Retrieval
Sec. 18.1
Autovalores & Autovetores
Para matrizes simétricas, autovetores p/ autovalores
distintos são ortogonais
Sv{1,2}  {1,2}v{1,2} , e 1  2  v1  v2  0
Todos autovalores de uma matriz simétrica real
são reais.
P/ complexos, se S  I  0 e S  ST    
Todos autovalores de uma matriz positiva
semi-definida são não-negativos.
w  n , wT Sw  0, entãose Sv  v    0
Sec. 18.1
Introduction to Information Retrieval
Exemplo
 Seja
2 1
S

1 2
Real, simétrico.
1 
2  
S  I  


2  
 1
| S  I | (2   ) 2  1  0.
 Então
 Os autovalores são1 e 3 (não-negativo, real).
 Os autovetores são ortogonais(e reais):
 1 
 
  1
1
 
1
Conecte esses valores
e resolva para
autovetores.
Sec. 18.1
Introduction to Information Retrieval
Decomposição própria/diagonal
 Seja
uma matriz quadrada com m autovetores
linearmente independentes (uma matriz não-defeituosa)
 Teorama: Existe uma decomposição própria
diagonal
 (cf. teorma diagonalização matriz)
 Colunas de U são autovetores de S
 Diagonal elements de
are eigenvalues of
Único p/
autovalores
distintos
Sec. 18.1
Introduction to Information Retrieval
Decomposição diagonal: por que /
como



v
...
v
Seja U tendo os autovetores c/ colunas: U
n
1




Então, SU pode ser escrito









1






...

SU

S
v
...
v

v
...
v

v
...
v
1
n
1
1
n
n
1
n
















n









Assim SU=U, orU–1SU=
E S=UU–1.

Sec. 18.1
Introduction to Information Retrieval
Exemplo – decomposição diagonal
Recorde
21


S

;


1
,

3
.
1
2


12


1 
Os autovetores 
  1 
 
Invertendo, temos
1
e 
1
 
forma
1
/2 
1
/2


U


1
/
2
1
/
2



1
1
U
1
1

1
Relembre
UU–1 =1.
11
10
1
/
2
1
/
2






Então, S=UU–1 = 






1
1
0
3
1
/
21
/
2






Sec. 18.1
Introduction to Information Retrieval
Continuação exemplo
Vamos dividir U (e multiplicar U–1) por
2




1
0


1
/2
1
/2
1
/2

1
/2
Então, S= 





0
3

1
/2
1
/2
1
/2
1
/2






Q

Why? Stay tuned …
(Q-1= QT )
Introduction to Information Retrieval
Sec. 18.1
Decomposição própria simétrica
 Se
é uma matriz simétrica:
 Teorema: Existe uma (única) decomposição própria
T
S

Q

Q
 Onde Q é ortogonal:
 Q-1= QT
 Colunas de Q são autovetores normalizados
 Colunas são ortogonais
 (tudo é real)
Sec. 18.1
Introduction to Information Retrieval
Exercício
 Examine the symmetric eigen decomposition, if any,
for each of the following matrices:
 0 1
1 0


0 1
1 0


 1 2
2 3


 2 2
 2 4


Introduction to Information Retrieval
Time out!
 Eu vim para essa aula p/ aprender recuperação de
texto e mineração, não quero voltar ao passado da
álgebra linear outra vez …
 Mas se você quer desenterrar a álgebra linear, Strang’s
Applied Mathematics é um bom lugar para começar.
 O que essas matrizes tem haver com texto?
 Relembre: M  N matrizes termo-documento …
 Mas tudo daqui em diante precisa de matrizes
quadradas – então …
Sec. 18.2
Introduction to Information Retrieval
Decomposição Valor Singular (SVD)
P/ uma matriz A, M  N, do rank r existe uma
fatorização (Singular Value Decomposition = SVD)
como a seguir:
T
A

U

V
MM
MN
V é NN
As colunas de U são autovetores ortogonais de AAT.
As colunas de V são autovetores ortogonais de ATA.
Autovalores 1 … r de AAT são autovalores de ATA.
i  
i




diag
...
1
r


Valores
singulares
Introduction to Information Retrieval
Sec. 18.2
Decomposição do valor singular
 Ilustrações das dimensões do SVD e espalhamento
Introduction to Information Retrieval
Sec. 18.2
Exemplo SVD
Seja
1 1
A   0 1 
 1 0 
Assim M=3, N=2. Seu SVD é
0 2

/61
/3
1
0






1
/21
/2


1
/2

1
/61
/3
0
3




 
1
/2

1
/2






1
/
2
1
/
6

1
/
3
0
0
 


Tipicamente, os valores singulares são arranjados em
ordem decrescente.
Introduction to Information Retrieval
Sec. 18.3
Low-rank Approximation
 SVD pode ser usado para cacular low-rank
approximations ótimo.
 Problema aproximação: Encontrar Ak do ranking k tal
que
A

A

X
k
min
F
Frobenius norm
X
:
rank
(
X
)

k
Ak e X são ambas matrizes mn
Tipicamente, queremos k << r.
Sec. 18.3
Introduction to Information Retrieval
Low-rank Approximation
 Solução via SVD


T
A

U
di
(
,...,
,
0
ag
,...,
0
)
V
k
1k
Ajuste os menores valores singulares
r-k para zero
k
T
A


u
v
k 
i

1i i i
k
Notação coluna: soma do
rank de 1 “matrizes”
Introduction to Information Retrieval
Sec. 18.3
SVD Reduzido
 Se retermos somente k valores singulares e
alterarmos o resto para 0, então não precisamos das
partes da matriz em marrom
 EntãoΣ é k×k, U é M×k, VT é k×N, e Ak é M×N
 Chamado de SVD reduzido. É conveniente (spacesaving) , comum p/ aplicações computacionais
 Isso é o que Matlab nos dá
k
Sec. 18.3
Introduction to Information Retrieval
Erro aproximação
 Quão bom (ruim) é sua aproximação?
 Ela é a melhor possível, medida pela norma do erro
de Frobenius:
A

X

A

A


m
in
F
X
:
ra
(
X
)

k
nk
k

1
Fk
onde i é ordenado tal que i  i+1.
Sugira por que erro de Frobenius baixa quando k é
aumentado
Introduction to Information Retrieval
Sec. 18.3
SVD Low-rank approximation
 Enquanto a matriz termo-doc A pode ter M=50000,
N=10 million (e rank perto de 50000)
 Podemos construir uma aproximação A100 com rank
100.
 De todas as 100 matrizes, ela teria o menor erro
Frobenius.
 Ok…mas porque teríamos ??
 Reposta: Latent Semantic Indexing (Indexação
Semântica Latente)
C. Eckart, G. Young, The approximation of a matrix by another of lower rank.
Psychometrika, 1, 211-218, 1936.
Introduction to Information Retrieval
Latent Semantic
Indexing via SVD
Introduction to Information Retrieval
Sec. 18.4
O que é
 Da matriz termo-doc A, calculamos a
aproximação Ak.
 Existe uma linha p/ cada termo e uma
coluna p/ cada documento em Ak
 Assim documentos “vivem” em um espaço
de k << r dimensões
 Essas dimensões não são os eixos originais
 Mas por quê?
Introduction to Information Retrieval
Modelo espaço vetor: Prós
 Seleção Automática dos termos do índice
 Emparalhemanto parcial das consultas e
documentos (tratando o caso onde o documento não tem todos
os termos da consulta)
 Ranking de acordo com pontuação de similaridade
(tratando grandes conjuntos de resultados)
 Esquemas pesos para os termos (melhora a performance
na recuperação)
 Várias extensões
 Clustering de documentos
 Feedback relevância (modificando o vetor da consulta)
 Geometric foundation
Introduction to Information Retrieval
Problemas com Semântica Léxica
 Ambiguidade e associação na lgg natural
 Polissemia: Palavras frequentemente tem uma
grande número de signficados e diferentes tipos
de uso (mais severo em muitas coleções
heterogêneas).
 Esse modelo de espaço vetor não é capaz de
diferenciar entre diferentes signficados de uma
mesma palavras.
Introduction to Information Retrieval
Problemas com Semântica Léxica
 Sinônimos: Diferentes termos podem ter
signficados similares ou idênticos
(weaker: palavras indicando o mesmo
resultado).
 Associações entre palavras não são feitas
na representação espaço vetor.
Introduction to Information Retrieval
Polissemia e Contexto
 Similaridade de documentos no nível de uma palavra
única: polissemia e contexto
ring
jupiter
•••
…
planet
...
…
Signficado 1
space
voyager
saturn
...
Signficado 2
car
company
•••
Contribuição p/ similaridade,
Se usado o primeiro
signficado, mas não em
segundo
dodge
ford
Introduction to Information Retrieval
Sec. 18.4
Latent Semantic Indexing (LSI)
 Realiza uma low-rank approximation de documentterm matrix (rank típico 100-300)
 Idéia geral
 Mapeia documentos (e termos) p/ uma representação
low-dimensional.
 Projeta uma mapeamento tal que o espaço lowdimensional reflete associações semânticas (espaço
semântico latente).
 Calcula a similaridade de um documento baseado no
produto interno no seu espaço semântico latente
Introduction to Information Retrieval
Sec. 18.4
Objetivos de LSI
 Termos similares mapeados para lugares
similares no espaço low dimensional
 Redução do ruído pela redução da
dimensão
Sec. 18.4
Introduction to Information Retrieval
Análise da Semântica Latente
 Espaço semântico latente: exemplo de ilustração
courtesy of Susan Dumais
Introduction to Information Retrieval
Sec. 18.4
Realizando os mapas
 Cada linha e coluna de A gets mapped into the kdimensional LSI space, by the SVD.
 Reivindicação - isso não é só o mapeamento com a
melhor aproximação (erro Frobenius) para A, mas de
fato melhora a recuperação.
 Uma consulta q é também mapeada dentro desse
espaço, por
T

1
q
q
U

k
k
k
 Consulta em um vetor não esparso
Introduction to Information Retrieval
Sec. 18.4
Evidências empíricas
 Experimentos emTREC 1/2/3 – Dumais
 Lanczos SVD código (disponível em netlib) devido
à Berry usado nesses experimentos
 Executando vezes de ~ um dia em dezenas de
centenas de documentos [obstáculo para o uso]
 Dimensões – vários valores 250-350 relatados.
Reduzindo k melhora recall.
 (Abaixo de 200 relataram não satisfatórios)
 Geralmente espera o recall melhorar – e sobre
precision?
Sec. 18.4
Introduction to Information Retrieval
Evidência empírica
 Precisa ou acima da precisão média do TREC
 Top scorer em quase 20% dos tópicos TREC
 Um pouco melhor na média que espaços de
vetores
 Efeito da dimensionalidade:
Dimensões
250
300
346
Precisão
0.367
0.371
0.374
Introduction to Information Retrieval
Sec. 18.4
Modos de falha
 Frases negadas
 Tópicos doTREC as vezes negam certas
consultas/frases de termos – impedem a
conversão automática de tópicos para o espaço
semântica latente.
 Consultas booleanas
 Usualmente, texo livre/sintaxe do espaço vetor de
consultas LSI impedem (dizer) “Encontre qualquer
documento tendo satisfazer as seguintes 5
companias”
 Veja Dumais para mais.
Introduction to Information Retrieval
Sec. 18.4
Clustering?
 Falamos sobre docs, consultas, recuperação
e precisão aqui.
 O que isso tem haver com clustering?
 Intuição: Redução de dimensão através LSI
traz junto eixos “relacionados” no espaço
vetor.
Introduction to Information Retrieval
Intuição de blocos de matrizes
N documentos
Bloco1
Qual o rank dessa matriz ?
0’s
Bloco 2
M
termos
…
0’s
Bloco k
= blocos homogêneos não-nulos
Introduction to Information Retrieval
Intuição de blocos de matrizes
N documentos
Bloco 1
0’s
Bloco 2
M
termos
…
0’s
Bloco k
Vocabulário particionado em k tópicos (clusters);
cada documento discute em somente um tópico.
Introduction to Information Retrieval
Intuição de blocos de matrizes
N documentos
Bloco1
Qual a melhor aproximação
do rank-k p/ essa matriz?
0’s
Bloco 2
M
termos
…
0’s
Bloco k
= entradas não-nulas
Introduction to Information Retrieval
Intuição de blocos de matrizes
Provavelmente existe uma boa
aproximação do rank-k p/ essa matriz.
Arame
Pneu
V6
Bloco 1
Bloco 2
Poucas entradas não-zeros
…
Poucas entradas não-zeros
Carro
10
Automóvel 0 1
Bloco k
Introduction to Information Retrieval
Figura simplista
Tópico 1
Tópico 2
Tópico 3
Introduction to Information Retrieval
Algumas extrapolações
 A “dimensionalidade” de um corpus é o
número de tópicos distintos representados
nele.
 Mais extrapolações matemáticas:
 Se A tem um rank de aproximação k de
baixo erro Frobenius, então não existem
mais que k tópicos distintos no corpus.
Introduction to Information Retrieval
LSI tem outras aplicações
 Em muitos cenários no reconhecimento de padrões e
recuperação, temos uma matriz objeto característica.
 P/ tetxo, os termos são características e os documentos
são objetos.
 Podia ser opiniões e usuários …
 Essa matriz pode ser redundante em dimensionalidade.
 Pode trabalhar com low-rank approximation.
 Se estão faltando entradas (isto é, opiniões dos usuários),
pode recuperar se a dimensionalidade é baixa.
 Técnica analítica geralmente poderosa
 Princípio análogo aos métodos de clustering
Introduction to Information Retrieval
Resources
 IIR 18