Computer
Vision
Transformação para o Espaço Latente
Paulo Sérgio Rodrigues
PEL205
Computer
Vision
Matriz Ortogonal
Definição1 : A matriz A  ai , j mn é ortogonal se AT A  1nn
onde  é chamadode autovetorde A
Definição2 : x  n é um autovetorde Ann se
   de modo que Ax  x
Computer
Vision
Norma p de um Vetor
Definição3 : a norma p de um vetorx  n é
x
p
 n
p
   xi 
 i 1

1
p
Por exemplo, a normas p usuais são:
n
 x 1   xi
i 1
 
 x2 x x
T
 x

1
2
 max xi
1i  n
Computer
Vision
Matriz Simétrica e Positiva Definida
T eorema1 (Decomposição Espectral): Seja i , ei 
os n paresde autovalores - autovetore
s da matriz
n
simétricaAnn , então: A    e e
i 1
T
i i i
Definição4 : Uma matrizAnn é positivadefinida se
xT Ax  0 para todo vetorx  0
Computer
Vision
Valor Singular
Definição 5 : Dado uma matriz Ann cujo rank é r,
T
entãoos autovalores de A A são :
1  2    r  r 1    n  0
onde i  i é chamadode " valorsingular"de A
onde i  1,2,, n
Computer
Vision
Espaço Semântico Latente
[Deewesteer, 1990] diz que:
“A indexação no espaço latente (LSI) tenta resolver
problemas de casamento lexicográfico usando índices conceituais
derivados estatisticamente ao invés de usar palavras diretamente”.
A LSI assume que existe alguma informação escondida (Estrutura
Latente das Palavras) que é parcialmente obscurecida devido a
variabilidade das escolhas das palavras”.
Computer
Vision
Espaço Semântico Latente
• Uma vez que tanto textos quanto imagens podem ser interpretadas
como espaços vetoriais, as idéias do LSI de que existe informação
escondida e essa informação é essencial para caracterização de
padrões, podem ser levadas para a interpretação de cenas
Por que trabalhar no espaço latente quando se procura padrões tanto
textuais quanto visuais?
Existe uma série de problemas em casamento de padrões que incluem
pelo menos ...
Computer
Vision
Sinônimos:
Espaço Semântico Latente
palavras diferentes com o mesmo significado
Exemplo: avaro-avarento, léxico-vocabulário,
falecer-morrer, etc.. Tais palavras possuem baixa
similaridade no espaço vetorial euclidiano.
Imagens diferentes podem ter o mesmo significado:
Computer
Vision
Espaço Semântico Latente
Polissemia:
Uma única palavra pode ter múltiplos significados
Dependendo do contexto, o que leva a uma precisão
pobre em casamento de padrões textuais.
Ex: vários significados do verbo ter
Computer
Vision
Espaço Semântico Latente
Polissemia: Uma única imagem, dependendo do contexto, pode ter vários
significados, o que pode levar a uma pobre precisão em
classificação.
Computer
Vision
Espaço Semântico Latente
Alta dimensionalidade:
Tanto o espaço vetorial dos textos, quanto das imagens, possuem
geralmente uma alta dimensionalidade, gerando dificuldades de
gerenciamento e escondendo informações latentes.
Computer
Vision
Decomposição do Valor Singular
T eorema2 : Dada uma matrizAmn , cujo rank é r ,
e m  n, existemduas matrizesortogonais
U mn  u1 , u2 ,, un  e Vnn  v1 , v2 ,, vn , então:
r
A  UV T   ui i viT
(1)
i 1
onde    1 ,  2 ,,  n  nn e  i são os valoressingulares
de A, chamamos(1) de Decomposição de A em seus valoressingulares
Computer
Vision
Decomposição do Valor Singular
T eorema3 (T eoremade Eckart- Young):
Seja a SVD de uma matrizA dada pelo T eorema3
com r  rank A  p  minm, n e definindo:
k
Ak  U k  kV   ui v
T
k
T
i i
i 1
Então, Ak é uma aproximação ótima de A considerando que:
min A  B
 A  Ak
F
min A  B 2  A  Ak
2
rank  B  k
rank ( B )  k
F

p
2

 i
i  k 1
  k 1
Computer
Vision
Decomposição do Valor Singular
Interpretação Visual do SVD
K
Amn
U mn
=
K
Snn
T
nn
V
K
Computer
Vision
Decomposição do Valor Singular
Conclusão 1: O teorema de de Eckart-Young, garante que
Ak, a matriz truncada de A, é a matriz de rank k mais
próxima de A de acordo com as normas de Forbenius e norma 2
Conclusão 2: A decomposição em valores singulares de um espaço
vetorial, pode separar informações latentes escondidas. Revelar
essas informações pode ser uma maneira de representar esse
espaço
Em sua essência semântica. Isso vale para textos, imagens, sons,
vídeos, etc..
Computer
Vision
Decomposição do Valor Singular
Exemplo numérico no Matlab
A  USV
A = 0.95
0.23
0.61
0.49
0.89
0.76
T
0.46
0.02
0.82
[U,S,V] = svd(A)
0.44
0.62
0.79
Computer
Vision
Decomposição do Valor Singular
Exemplo numérico no Matlab
A  USV
U = -0.55
-0.45
-0.70
S = 2.10
0
0
V = -0.50
-0.57
-0.40
-0.51
0.54
-0.84
0.11
0
0.67
0
0.58
-0.59
0.48
-0.28
T
-0.64
-0.31
0.70
0
0
0.39
Verifica-se que A = U*S*V’
0
0
0
-0.64
-0.13
0.73
0.21
0.05
-0.55
-0.28
0.78
Computer
Vision
Decomposição do Valor Singular
Exemplo com uma imagem
Imagem Original
Valores Singulares
Computer
Vision
Decomposição do Valor Singular
Exemplo com uma imagem
Imagem reconstruída com
apenas 10% dos Valores
Singulares
10% dos Valores Singulares
Computer
Vision
Referências Bibliográficasa de SVD e LSI
1. S. T. Dumais, G. W. Furnas, T. K. Landauer, and S. Deerwester (1988),
Using latent semantic analysis to improve information retrieval. In
Proceedings of CHI’88: Conference on Human Factors in Computing,
New York: ACM, 281-285.
2. S. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A.
Harshman (1990), Indexing by latent semantic analysis. Journal of the
Society for Information Science, 41(6), 391-407.
3. P. W. Foltz (1990), Using Latent Semantic Indexing for Information
Filtering. In R. B. Allen (Ed.) Proceedings of the Conference on Office
Information Systems, Cambridge, MA, 40-47.
4. J. S. Yu, Z. H. Jin, and Z. S. Wen (2003), Automatic Detection of
Collocation. Report at the seminar of Statistical Machine Learning,
Peking University, http://icl.pku.edu.cn/yujs