17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
Pré-imagem com mapas de difusão
Lúcia Maria dos Santos [email protected]
Ricardo [email protected]
Francisco Duarte Moura [email protected]
Instituto Politécnico, Universidade do Estado do Rio de Janeiro,
Caixa Postal 97282, 28601-970 Nova Friburgo, RJ, Brasil
Resumo. A aplicação de difusão, um dos métodos mais recentes de redução de dimensionalidade,
Coifman & et al. (2005), só pode ser calculada nas entradas, X i , de um conjunto de treinamento,
E = {X 1 , X 2 , . . . X n }. Esta é uma questão que não se coloca para o já tradicional PCA, análise
das componentes principais, onde não há dificuldade de calcular as projeções de novos pontos
fora do conjunto dado. Este já começa a ser um primeiro obstáculo na procura da pré-imagem
para aplicações de difusão. Por isso neste trabalho consideramos a questão da extensão, ou seja,
estendemos a aplicação de difusão a todo o espaço Rd , o qual contém o conjunto E de sinais
dados inicialmente, com a ajuda da já conhecida extensão de Nyström. Desta forma poderemos
abordar a questão da pré-imagem das caracterı́sticas (ou features) correspondentes a um sinal
qualquer do Rd que tenha sido difundido num espaço de mais baixa dimensão. Esta inversão ou
reconstrução do sinal, no caso do PCA, é mais simples quando se considera a opção natural,
linear, envolvendo as direções principais, sendo objeto de pesquisa recente no caso da aplicação
de difusão. No último experimento exposto neste trabalho utilizamos uma função custo baseada em
dados para encontrar a pré-imagem no caso da aplicação de difusão. Ao procurar tal pré-imagem
percebemos que poderı́amos também inverter o PCA de forma não linear, bastando para isso que
a inversão levasse em conta os dados experimentais. Achamos interessante então comparar tais
pré-imagens, sendo esperado que o PCA não funcionasse tão bem como os mapas de difusão, uma
vez que ele é originalmente um método linear.
Keywords: pré-imagem, extensão, mapas de difusão, análise das componentes principais.
1.
Introdução
A ideia da redução de dimensionalidade consiste em sair de um espaço de entrada com dados de alta dimensão e chegar num espaço reduzido com vetores de poucas componentes que
correspondam às caracterı́sticas essenciais de cada um dos respectivos dados de certa forma capazes de parametrizar os dados de entrada ou sinais do sistema fı́sico em estudo. Estes dados
rotulados na entrada fazem parte do conjunto de treinamento que será aqui representado por
E = {X 1 , X 2 , . . . X n }.
Existe atualmente na literatura uma grande variedade de métodos de redução de dimensionalidade. Neste trabalho citamos apenas o clássico e poderoso método linear conhecido como PCA
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
e o mais recente método, não linear, das aplicações ou mapas de difusão. O objetivo principal
deste trabalho é discutir uma forma de encontrar a pré-imagem para o caso dos mapas de difusão.
O método do PCA é citado nos experimentos pelo fato de ter se adaptado perfeitamente à função
custo que construı́mos baseada nos dados.
Em poucas palavras poderı́amos dizer que o problema da pré-imagem consiste em encontrar no espaço de entrada algum elemento do conjunto de treinamento que melhor aproxime uma
possı́vel ‘imagem inversa’ de um elemento no espaço reduzido. A pré-imagem exata geralmente
não existe ou não é única e por isso precisamos de uma solução aproximada, Mika & et al. (1998).
Nada impede que este problema da pré-imagem esteja também presente em casos onde não há
redução de dimensionalidade e nestes casos, que não serão aqui abordados, mesmo a solução
aproximada pode não ser tão fácil de se obter.
Uma das aplicações da pré-imagem consiste no chamado denoising, ou seja, retirada do ruı́do
de algum dos dados de entrada, podendo o ruı́do ser bastante complexo. Kwok & Tsang (2004)
apresentam um experimento onde conseguem tirar o ruı́do de um conjunto de dı́gitos manuscritos
(http://www.kernel-machines.org) usando pré-imagens baseadas em restrições de distâncias sem
precisar recorrer a otimizações não lineares como seria o caso originalmente proposto por Mika &
et al. (1998).
Conforme já mencionado, algumas vezes o problema da pré-imagem é associado ao problema
da extensão. Etyngier & Segonne & Keriven (2007) utilizaram a extensão clássica de Nyström
e triangulação de Delaunay para uma solução variacional do ruı́do na variedade dos dados. A
próxima seção trata da extensão de Nyström que será também utilizada neste trabalho com a finalidade de obtermos a pré-imagem procurada. Uma proposta para possı́vel inversão da aplicação de
difusão é apresentada na seção 3. Experimentos são apresentados na seção 4.
2.
Extensão de Nyström
Considere nosso conjunto de entradas do treinamento, E = {X 1 , X 2 , . . . , X n } em Rd , e o
conjunto das respectivas imagens dos dados, F = {Y 1 , Y 2 , . . . , Y n }, pela aplicação de difusão,
aqui representada por D, no conjunto Rn−1 .
Para estendermos a função D a outros vetores de Rd que não sejam entradas do conjunto
de treinamento, a fim de classificar novos sinais, utilizaremos a extensão de Nyström que será
representada por D̃, ver por exemplo Lafon & Lee (2006).
A aplicação de difusão (truncada em k termos) é definida apenas nos vértices de um grafo que
constitui o conjunto de treinamento,


λt1 v1 (j)


..
Dt (X j ) = 
(1)
 ,
.
t
λk vk (j)
onde vi (j) é a j-ésima componente do autovetor à direita de D−1 W , v i , associado ao autovalor λi ,
com i = 1, . . . , k, e k ≤ n − 1, enquanto t é o parâmetro considerado para o processo de Markov
associado à difusão, ver Pinto (2014). Neste texto W é a matriz de adjacência do grafo citado,
enquanto D é a matriz grau, ou seja, a matriz diagonal cujos elementos são a soma das linhas de
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
W. Assim,
D−1 W v i = λi v i ,
donde
vi=
1 −1
D Wv i ,
λi
ou ainda, em coordenadas,
n
n
1 X −1
1
1 X
−1
vi (j) = (D W v i )j =
(D W )jl vi (l) =
Wjl vi (l) .
λi
λi l=1
λi dj l=1
Mas Wjl = K(X j , X l ), onde K(X, Y ) = e−
mente, então,
kX−Y k2
ε
é o núcleo de difusão utilizado frequente-
n
1 X
vi (j) =
vi (l)K(X j , X l )
λi dj l=1
n
X
1
=
λi
Pn
−
m=1 e
kX j −X m k2
ε
vi (l)e−
kX j −X l k2
ε
,
(2)
l=1
P
P
kX j −X m k2
ε
uma vez que dj = nm=1 K(X j , X m ) = nm=1 e−
. Fixado i, observa-se que ao passo
que o lado esquerdo da equação(2) está definido para j ligado ao X j , o lado direito pode ser
definido para um X arbitrário. Isto é, podemos definir
v̄i : Rd −→ R
X
7→
P
kX−X l k2
1 nl=1 vi (l)e− ε
,
v̄i (X) =
λi Pn e− kX−Xε m k2
m=1
e neste caso, vi (j) é dado em função de v̄i ,
vi (j) = v̄i (X j ) ,
ou seja, podemos pensar em v̄i como uma extensão de v i para pontos que não sejam do grafo dos
dados originalmente observados.
Desta forma, podemos considerar a seguinte extensão da aplicação de difusão,
Rd × [0, +∞) −→ Rk

(X, t)
7→

λt1 v̄1 (X)


..
D̃t (X) = 
 ,
.
t
λk v̄k (X)
que coincide com Dt nos pontos do conjunto E = {X 1 , . . . , X n }. Esta é a extensão de Nyström,
Lafon & Lee (2006).
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
3.
Uma possı́vel inversa
Como D é injetora nas entradas do conjunto E de treinamento, Pinto (2014), então a imagem
inversa de cada elemento no conjunto F, é única. Para dados que estejam fora das entradas do
treinamento esta questão é bem mais complicada. O problema da pré-imagem de um elemento
qualquer de Rn−1 é um problema mal posto e em geral a pré-imagem de um único ponto, se
existir, será um conjunto de vetores no espaço de entrada, Arias & Randall & Sapiro (2007).
Para fugir deste inconveniente temos que buscar modificações adequadas e uma oportunidade é a
regularização do problema a partir da utilização do conjunto de sinais do treinamento.
Vamos inicialmente considerar um ponto b ∈ Rn−1 fixado. Buscamos a melhor aproximação
para uma possı́vel pré-imagem, x, deste ponto. Desejamos que este x esteja o mais próximo
possı́vel do nosso conjunto de dados de entrada, E, como uma forma de regularizar a inversão.
Obviamente, também buscamos que a imagem deste x pela extensão da aplicação de difusão seja
o próprio b ou o mais próximo disso. Para cada b fixado podemos representar estas exigências pela
função objetivo, f : Rd → R, a seguir:
f (x) = kD̃(x) − bk + γ min(kx − X k k).
(3)
k
Ou seja, dado um b ∈ Rn−1 , a sua pré-imagem, se existir, será o vetor x ∈ Rd que minimiza a
função f acima. O parâmetro γ foi utilizado para que seja possı́vel regular o nı́vel de influência
da segunda parcela de (3) em relação à primeira. Ao considerarmos γ < 1 estamos indicando que,
no algoritmo de minimização a ser utilizado, a primeira parcela contará mais do que a segunda.
O parâmetro γ é um parâmetro de regularização para este problema. É bom lembrar, como dito
anteriormente, que estas ideias podem também ser utilizadas, e as exploraremos nos experimentos,
para obter uma reconstrução não linear (inversão) do PCA.
Pensando agora num conjunto formado de vários b ∈ Rn−1 , se quisermos saber suas préimagens, podemos considerar a função anterior como dependente não apenas do x, mas também
do b. Assim podemos reescrever f como função de duas variáveis,
f : Rd × Rn−1 → R, definida por
f (x, b) = kD̃(x) − bk + γ min(kx − X k k).
k
(4)
Notamos que a função f como foi definida é sempre maior ou igual a zero. Avaliando-a em
(X i , D(X i )) e lembrando da seção anterior que a função extensão de Nyström interpola as entradas
do treinamento podemos substituir D̃(X i ) por D(X i ) em (4) e obtermos:
f (X i , D(X i )) = kD(X i ) − D(X i )k + γ min(kX i − X k k) = 0.
k
Logo o mı́nimo desta função é atingido em zero.
Gostarı́amos que pelo menos nas entradas do conjunto de treinamento a minimização desta
função, a qual produz a pré-imagem de um ponto fixado b ∈ Rn−1 , fosse a função inversa da
aplicação de difusão. Para que isso seja realmente verdade é preciso que façamos b = D(X i ) em
(4) e seja a única solução da minimização de f, ou seja, gostarı́amos de verificar que
f (X i , D(X i )) = 0
(5)
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
e
f (X j , D(X i )) > 0, ∀j 6= i.
(6)
Vamos desenvolver estes cálculos,
f (X j , D(X i )) = kD̃(X j ) − D(X i )k + γ min(kX j − X k k).
(7)
Podemos substituir D̃(X j ) por D(X j ) em (7). Como X j é entrada do treinamento vemos que a
segunda parcela no lado direito da Equação (7) atingirá seu mı́nimo zero e portanto
f (X j , D(X i )) = kD(X j ) − D(X i )k.
(8)
Como D é injetora nas entradas do treinamento, Pinto (2014), a equação (8) será nula exclusivamente quando i = j, como querı́amos demonstrar.
Resumindo tudo que foi dito, a proposta é considerar uma função G definida a partir da
minimização da função f apresentada anteriormente, G : Rn−1 → Rd , tal que
G(b) = arg min f (x, b).
(9)
x
Em geral G(b) pode ser um conjunto de Rd uma vez que f (·, b) pode ter vários pontos de mı́nimo.
Desta forma a proposta da inversa G é razoável uma vez que se comporta como inversa pelo menos
nas entradas do conjunto de treinamento.
4.
Experimentos
A tı́tulo de ilustração da questão da pré-imagem para denoising foi construı́do o seguinte experimento. Um banco de dados sintético foi constituı́do de 360 rotações de uma mesma vogal,
A, sendo cada imagem formada de 50 × 50 pı́xeis. Foi considerado o exemplar referente à vogal
rotacionada de 10o aqui representado por X 10 correspondente à décima coluna da matriz dos dados
10
originais. Um ruı́do foi adicionado a X 10 em forma de variação da iluminação, Xruido
= 0, 5X 10 ,
ou seja, a vogal escurecida pelo fator 0, 5 foi usada como elemento diferente de todas as entradas
do conjunto de treinamento e foram calculadas suas features em R3 pelo truncamento (para R3 ) da
extensão da aplicação de difusão. Este ponto estendido corresponde ao b da seção anterior e o objetivo é encontrar a sua pré-imagem. Para esta extensão os parâmetros utilizados foram ε = r2 , t = 2
e α = 1, onde r é o diâmetro do conjunto dos dados, ε é o tamanho da vizinhança considerada
no núcleo de difusão (ver Equação 2), t é o parâmetro de Markov e α é uma normalização escolhida para a aplicação de difusão, Coifman & Lafon (2006). Para obter esta pré-imagem fizemos
uma minimização da função f dada pela equação (3) com γ = 0, 2 com ajuda do algoritmo simulated anneling. Obtivemos uma imagem da letra A rotacionada também de 10o porém com a
iluminação muito mais próxima de X 10 , vogal original, do que da imagem escurecida, mostrando
10
que a imagem escurecida Xruido
foi efetivamente projetada no espaço das 360 vogais originais.
A Figura 1(a) representa a pré-imagem da extensão da vogal escurecida a ser comparada com
a Figura 1(b) da vogal que deu origem àquela com ruı́do (escurecimento) e a Figura 1(c) da vogal
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
(a) Pré-imagem
(b) Vogal original
(c) Vogal escurecida
Figura 1: As figuras acima são para efeito de comparação. A vogal está rotacionada de 10o e o fator de
iluminação utilizado no item (c) foi de 0, 5. A pré-imagem ficou mais perto da vogal original do que da
escurecida mostrando que esta pré-imagem da aplicação de difusão tem capacidade de retirar o ruı́do por
fator de iluminação da imagem, denoising.
com ruı́do, ou seja, da vogal escurecida. Neste exemplo o fator de iluminação, utilizado como
ruı́do, que provocaria uma dificuldade maior de identificação da vogal original foi praticamente
eliminado com a utilização da pré-imagem da aplicação de difusão. Visualmente a pré-imagem
ficou mais perto da letra original (modelo) do que da letra escurecida. As normas das diferenças
entre elas confirmam esta impressão. A norma da diferença da pré-imagem para a vogal original
foi de 0, 4281 enquanto para a vogal escurecida que deu origem a pré-imagem foi de 1, 8400.
Pré-imagem para a hélice
Ainda com o objetivo de explorar melhor a ideia da pré-imagem de um dado (ou reconstrução
de um sinal) pela aplicação de difusão construı́mos o seguinte experimento. Consideramos uma
hélice de três voltas com o parâmetro angular variando de zero a 6π, formada por 189 pontos em
R3 . O parâmetro ε = 0, 1r2 foi utilizado para o núcleo da difusão, lembrando que r é a maior
distância entre os dados de entrada.
O exemplar considerado dentre os pontos da hélice para o nosso experimento é aqui representado por X 85 , correspondente à 85a coluna da matriz dos dados. Aqui consideramos um ruı́do nas
três componentes de X 85 com auxı́lio do comando rand do Matlab e vamos representar este novo
85
ponto de R3 como Xruido
. Calculamos a extensão deste ponto para R1 e a chamamos de b para
ser coerente com as notações da seção anterior. Para esta extensão os parâmetros utilizados foram
ε = r2 , t = 1 e α = 1. O objetivo é encontrar a pré-imagem de b. Novamente foi utilizado o simulated anneling para uma minimização da função dada pela equação (3) desta vez com γ = 0, 8.
A condição inicial escolhida para o simulated annealing foi o centróide do conjunto formado pelo
ponto X 85 e seus pontos vizinhos anterior e posterior.
Obtivemos como mı́nimo de f na equação (3) o ponto (−0.5193, 0.8555, 8.4000) de R3 que
85
é mais próximo do ponto X 85 da hélice do que do Xruido
. A norma desta diferença entre este
85
85
ponto de mı́nimo e o ponto X foi de 8, 9785e − 04 enquanto para o Xruido
foi de 9, 3923e − 04.
Foi também verificado que de todos os 189 pontos da hélice considerada o mais próximo da pré-
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
85
imagem da extensão de Xruido
foi exatamente o ponto X 85 . Analogamente ao caso da letra A do
experimento anterior concluı́mos que a imagem ruidosa foi projetada no mesmo espaço dos 189
pontos da hélice original.
Tendo em vista este resultado para um ponto da hélice individualmente resolvemos explorar
mais este tópico aplicando raciocı́nio análogo para vários pontos e comparando os resultados das
aplicações de difusão com os resultados do PCA. Vale ressaltar que aqui utilizamos a função
objetivo dada pela equação (3) para ambos os métodos em lugar de considerarmos a reconstrução
clássica do PCA.
Desta vez, para o conjunto de treinamento consideramos apenas 38 pontos da hélice anterior
obtendo desta forma uma nuvem de pontos mais esparsa. No entanto, foram adicionados ruı́dos
aleatórios através do randn do Matlab a todos os 189 pontos da hélice original. Estes pontos ruidosos foram levados ao espaço de chegada da difusão (ou do PCA) por uma extensão (ou projeção),
respectivamente. Buscamos a pré-imagem destes pontos aplicando a técnica do simulated annealing à função objetivo dada pela equação (3) com as devidas adaptações para o caso do PCA. O
parâmetro γ = 0.09 foi utilizado em ambos os casos. Além disso para o método das aplicações de
difusão utilizamos ε = 0, 001r2 , t = 50 e α = 1.
A Figura 2 apresenta este experimento com pequeno trecho ampliado onde, em azul, estão os
pontos da hélice ideal, os pontos ruidosos estão em vermelho e as pré-imagens em verde para o
caso do PCA. A Figura 3 faz o mesmo para o caso das aplicações de difusão. Uma observação
visual nos leva a crer que as pré-imagens se aproximam mais da curva original, ideal, no caso
das aplicações de difusão. Para confirmar esta percepção, de volta ao espaço original da hélice,
fizemos a diferença entre os pontos ideais da mesma e os pontos encontrados como pré-imagem.
Consideramos o erro representado pela norma desta diferença para cada um dos 189 pontos da
hélice ideal e plotamos num mesmo gráfico o erro para as duas técnicas consideradas. A Figura 4
mostra esta comparação.
Este gráfico confirma que a técnica das aplicações de difusão com a função custo considerada
na Equação 3 é mais eficiente que o PCA quando utilizamos a pré-imagem para a retirada de ruı́dos
(denoising). A mediana dos erros para o caso da difusão foi de 0, 0501, enquanto para o PCA ficou
em 0, 1063.
5.
Conclusão
Este trabalho quis discutir a questão da pré-imagem para o caso especı́fico dos mapas de
difusão, um método não linear, mais recente de redução de dimensionalidade. A primeira dificuldade encontrada diz respeito a extensão de pontos do espaço de alta dimensão que não sejam
parte integrante dos dados originais da pesquisa. Com a finalidade de encarar este problema uma
adaptação da extensão de Nyström para este caso especı́fico da difusão foi utilizada. Criamos uma
função custo (ver Equação 3) que nos permitiu encontrar a pré-imagem que melhor se ajustasse ao
conjunto de treinamento dado e a extensão utilizada.
Um experimento geométrico com uma hélice ideal onde alguns pontos foram acrescidos de
ruı́do foi apresentado como forma de visualizar a questão da pré-imagem. O parâmetro ε no
denominador do núcleo gaussiano para a difusão foi escolhido como 0, 1% da máxima distância
euclidiana entre os dados do experimento e o parâmetro de Markov foi t = 50. Com o parâmetro
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
Hélice ideal
Pontos com ruídos
Pré-imagens
Figura 2: Hélice ideal(em azul) com alguns de seus pontos modificados por pequenos ruı́dos aleatórios
(em vermelho) e as pré-imagens correspondentes (em verde) para o caso do PCA. Um pequeno trecho foi
ampliado para melhor visualização.
Hélice ideal
Pontos com ruídos
Pré-imagens
Figura 3: Hélice com pequeno trecho ampliado onde conseguimos ver seus pontos ruidosos (em vermelho)
e as pré-imagens correspondentes (em verde) para o caso das aplicações de difusão.
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
Figura 4: Esta figura apresenta os erros gerados pela aplicação de difusão (em azul) e pelo PCA (em verde)
no que diz respeito a reconstrução para o experimento da hélice.
regularizador γ = 0, 09 da função custo para a pré-imagem rodamos o algoritmo com ajuda do
simulated annealing tanto para os mapas de difusão quanto para o PCA com as devidas adaptações.
Notamos que as pré-imagens ficaram mais próximas da hélice ideal para o primeiro, como era de
se esperar já que este último é originalmente um método linear.
Referências
Arias, P. & Randall, G. & Sapiro, G., 2007. Connecting the out-of-sample and pre-image problems in kernel methods. In Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE
Conference on, pp.1-8, 2007.
Pinto, L. M. dos S., 2014. Mapeamento de difusão para reconhecimento e reconstrução de sinais.
Instituto politécnico IPRJ/ Universidade do Estado do Rio de Janeiro UERJ - PhD Thesis, 2014.
Etyngier, P. & Segonne, F. & Keriven, R., 2007. Shape priors using manifold learning techniques.
Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on. In IEEE, pp.1-8,
2007.
Kwok, JT-Y & Tsang, IW-H, 2004. The pre-image problem in kernel methods. In IEEE, volume 15(6), pp.1517-1525, 2004.
Mika, S. & Schölkopf, B. & Smola, A. J. & Müller, Klaus-Robert & Scholz, M. & Rätsch, G.,
1998. Kernel PCA and De-Noising in Feature Spaces. In NIPS, volume 11, pp.536-542, 1998.
Coifman, R.R. & Lafon, S. & Lee, A. B. & Maggioni, M. & Nadler, B. & Warner, F. & Zucker,
S.W., 2005. Geometric diffusions as a tool for harmonic analysis and structure definition of
17o Encontro Nacional de Modelagem Computacional
5o Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis,Rio de Janeiro, RJ, Brasil. 15-17 out. 2014.
data: Diffusion maps In Proceedings of the National Academy of Sciences of the United States
of America, volume 102-21, pp.7426, 2005. National Acad Sciences.
Coifman, R.R. & Lafon, S., 2006. Diffusion maps In Applied and computational harmonic analysis, volume 21-1, pp.5-30, 2006. Elsevier.
Lafon, S. & Lee, A. B., 2006. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization In IEEE Transactions
on Pattern Analysis and Machine Intelligence, volume 28-9, pp.1393-1403, 2006.
Pre-image with diffusion maps
The diffusion map, one of the most recent method for dimensionality reduction, Coifman & et
al. (2005), may only be calculated in the inputs, X i , in a set of training, E = {X 1 , X 2 , . . . X n }.
This is an issue that does not arise for the now traditional PCA, principal component analysis,
where there is no difficulty in calculating the projections of new points outside the given set. This
gets to be a first hurdle to find the pre-image for diffusion maps. That is why in this work we
consider the issue of the extension, ie extend the diffusion map to the whole space Rd , which
contains E, set of first data signals, with the help of already known Nyström extension. Thus we
can address the issue of pre-image of the characteristics (or features) corresponding to a any signal
of Rd that has been widespread in the space of lower dimension. This reversal or reconstruction
of a signal, in the case of PCA, is simpler when considering the linear natural option involving
the main directions, but it is a subject of recent research in the case of diffusion map. In the
last experiment exposed in this work we use a cost function based on data to find the pre-image
in the case of application of diffusion. When looking for such pre-image we realized we could
also reverse the PCA non-linearly by simply taking into account the experimental data. We find it
interesting then to compare these pre-images, and it is expected that the PCA did not work as well
as maps of diffusion, since it is originally a linear method.
Keywords: pre-image, extension, diffusion maps, principal component analysis