incorporação de vizinho estocástico distribuído em t - t-distributed stochastic neighbor embedding

A incorporação de vizinhos estocásticos com distribuição t ( t-SNE ) é um método estatístico para visualizar dados de alta dimensão, dando a cada ponto de dados uma localização em um mapa bidimensional ou tridimensional. É baseado no Stochastic Neighbour Embedding, originalmente desenvolvido por Sam Roweis e Geoffrey Hinton , onde Laurens van der Maaten propôs a variante t- distribuída . É uma técnica de redução de dimensionalidade não linear adequada para incorporar dados de alta dimensão para visualização em um espaço de baixa dimensão de duas ou três dimensões. Especificamente, ele modela cada objeto de alta dimensão por um ponto bidimensional ou tridimensional de tal forma que objetos semelhantes são modelados por pontos próximos e objetos diferentes são modelados por pontos distantes com alta probabilidade.

O algoritmo t-SNE compreende dois estágios principais. Em primeiro lugar, t-SNE constrói uma distribuição de probabilidade sobre pares de objetos de dimensões altas de tal forma que objetos semelhantes são atribuídos a uma probabilidade mais alta, enquanto pontos diferentes são atribuídos a uma probabilidade mais baixa. Em segundo lugar, t-SNE define uma distribuição de probabilidade semelhante sobre os pontos no mapa de baixa dimensão e minimiza a divergência de Kullback-Leibler (divergência KL) entre as duas distribuições com respeito às localizações dos pontos no mapa. Embora o algoritmo original use a distância euclidiana entre objetos como a base de sua métrica de similaridade, isso pode ser alterado conforme apropriado.

t-SNE tem sido usado para visualização em uma ampla gama de aplicações, incluindo genômica , pesquisa de segurança de computador , processamento de linguagem natural, análise de música , pesquisa de câncer , bioinformática , interpretação de domínio geológico e processamento de sinal biomédico.

Embora os gráficos t-SNE muitas vezes pareçam exibir clusters , os clusters visuais podem ser fortemente influenciados pela parametrização escolhida e, portanto, é necessário um bom entendimento dos parâmetros para t-SNE. Esses "clusters" podem aparecer até mesmo em dados não agrupados e, portanto, podem ser descobertas falsas. A exploração interativa pode, portanto, ser necessária para escolher os parâmetros e validar os resultados. Foi demonstrado que t-SNE é frequentemente capaz de recuperar clusters bem separados e, com escolhas de parâmetros especiais, aproxima-se de uma forma simples de clustering espectral .

Detalhes

Dado um conjunto de objetos de alta dimensão , t-SNE primeiro calcula as probabilidades que são proporcionais à similaridade dos objetos e , como segue. ${\ displaystyle N}$${\ displaystyle \ mathbf {x} _ {1}, \ dots, \ mathbf {x} _ {N}}$${\ displaystyle p_ {ij}}$${\ displaystyle \ mathbf {x} _ {i}}$${\ displaystyle \ mathbf {x} _ {j}}$

Para definir ${\ displaystyle i \ neq j}$

${\ displaystyle p_ {j \ mid i} = {\ frac {\ exp (- \ lVert \ mathbf {x} _ {i} - \ mathbf {x} _ {j} \ rVert ^ {2} / 2 \ sigma _ {i} ^ {2})} {\ sum _ {k \ neq i} \ exp (- \ lVert \ mathbf {x} _ {i} - \ mathbf {x} _ {k} \ rVert ^ {2 } / 2 \ sigma _ {i} ^ {2})}}}$

e definido . Observe isso para todos . ${\ displaystyle p_ {i \ mid i} = 0}$${\ displaystyle \ sum _ {j} p_ {j \ mid i} = 1}$${\ displaystyle i}$

Como Van der Maaten e Hinton explicaram: "A semelhança do ponto de dados com o ponto de dados é a probabilidade condicional , que escolheria como seu vizinho se os vizinhos fossem escolhidos em proporção à sua densidade de probabilidade sob um Gaussiano centrado em ." ${\ displaystyle x_ {j}}$${\ displaystyle x_ {i}}$${\ displaystyle p_ {j | i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {i}}$

Agora defina

${\ displaystyle p_ {ij} = {\ frac {p_ {j \ mid i} + p_ {i \ mid j}} {2N}}}$

e note que , , e . ${\ displaystyle p_ {ij} = p_ {ji}}$${\ displaystyle p_ {ii} = 0}$${\ displaystyle \ sum _ {i, j} p_ {ij} = 1}$

A largura de banda dos núcleos gaussianos é definida de tal forma que a perplexidade da distribuição condicional é igual a uma perplexidade predefinida usando o método da bissecção . Como resultado, a largura de banda é adaptada à densidade dos dados: valores menores de são usados ​​em partes mais densas do espaço de dados. ${\ displaystyle \ sigma _ {i}}$${\ displaystyle \ sigma _ {i}}$

Como o kernel gaussiano usa a distância euclidiana , ele é afetado pela maldição da dimensionalidade e, em dados de alta dimensão, quando as distâncias perdem a capacidade de discriminar, tornam-se muito semelhantes (assintoticamente, convergiriam para uma constante). Foi proposto ajustar as distâncias com uma transformação de potência, com base na dimensão intrínseca de cada ponto, para amenizar isso. ${\ displaystyle \ lVert x_ {i} -x_ {j} \ rVert}$${\ displaystyle p_ {ij}}$

t-SNE visa aprender um mapa -dimensional (com ) que reflete as semelhanças da melhor forma possível. Para tal, mede semelhanças entre dois pontos do mapa e , utilizando uma abordagem muito semelhante. Especificamente, para , definir como ${\ displaystyle d}$${\ displaystyle \ mathbf {y} _ {1}, \ dots, \ mathbf {y} _ {N}}$${\ displaystyle \ mathbf {y} _ {i} \ in \ mathbb {R} ^ {d}}$${\ displaystyle p_ {ij}}$${\ displaystyle q_ {ij}}$${\ displaystyle \ mathbf {y} _ {i}}$${\ displaystyle \ mathbf {y} _ {j}}$${\ displaystyle i \ neq j}$${\ displaystyle q_ {ij}}$

${\ displaystyle q_ {ij} = {\ frac {(1+ \ lVert \ mathbf {y} _ {i} - \ mathbf {y} _ {j} \ rVert ^ {2}) ^ {- 1}} { \ sum _ {k} \ sum _ {l \ neq k} (1+ \ lVert \ mathbf {y} _ {k} - \ mathbf {y} _ {l} \ rVert ^ {2}) ^ {- 1 }}}}$

e definido . Aqui, uma distribuição t de Student de cauda pesada (com um grau de liberdade, que é o mesmo que uma distribuição de Cauchy ) é usada para medir semelhanças entre pontos de baixa dimensão, a fim de permitir que objetos diferentes sejam modelados distantes no mapa . ${\ displaystyle q_ {ii} = 0}$

As localizações dos pontos no mapa são determinadas minimizando a divergência (não simétrica) de Kullback-Leibler da distribuição da distribuição , ou seja: ${\ displaystyle \ mathbf {y} _ {i}}$${\ displaystyle P}$${\ displaystyle Q}$

${\ displaystyle \ mathrm {KL} \ left (P \ parallel Q \ right) = \ sum _ {i \ neq j} p_ {ij} \ log {\ frac {p_ {ij}} {q_ {ij}}} }$

A minimização da divergência de Kullback-Leibler em relação aos pontos é realizada usando gradiente descendente . O resultado dessa otimização é um mapa que reflete as semelhanças entre as entradas de alta dimensão. ${\ displaystyle \ mathbf {y} _ {i}}$

Programas

• O pacote de R Rtsne implementos t-PND em R .
• ELKI contém tSNE, também com aproximação de Barnes-Hut
• Scikit-learn , um popular kit de ferramentas de aprendizado de máquina em python, implementa t-SNE com soluções exatas e a aproximação de Barnes-Hut.
• Tensorboard, o kit de visualização associado ao TensorFlow , também implementa t-SNE ( versão online )

Referências

links externos

• Visualizando dados usando t-SNE , Google Tech Talk sobre t-SNE
• Implementações do t-SNE em vários idiomas , uma coleção de links mantida por Laurens van der Maaten