t-SNE: t-Distributed Stochastic Neighbor Embedding é uma técnica de redução de dimensionalidade que é particularmente bem adaptada para visualizar bancos de dados com muitas dimensões.

A técnica foi introduzida em 2008 por Laurens van der Maaten e Geoffrey Hinton, o segundo bem famoso por causa do seu trabalho com redes neurais. Hinton é um dos primeiros pesquisadores a treinar redes neurais de muitas camadas usando backpropagation.

O objetivo do t-SNE é a partir de um conjunto de pontos em um espaço multi-dimensional encontrar uma representação fiel desses pontos em um espaço de dimensão menor, geralmente um plano 2D. O algoritmo é não-linear e se adapta aos dados, realizando diferentes transformações em diferentes regiões do espaço multi-dimensional. O t-SNE é capaz de capturar muito da estrutura local do espaço multi-dimensional enquanto também revela a estrutura global do banco de dados como a presença de clusters.

Neste post vamos tentar definir matematicamente (não muito rigorosamente) o que é o t-SNE para depois mostrar algumas aplicações usando o R.

Definindo melhor matemáticamente

O t-SNE é baseado no SNE com duas principais diferenças:

  • usa uma função de custo simétrica que é mais fácil de otimizar
  • usa a distribuição t ao invés da distribuição Normal para calcular a similaridade entre os pontos no espaço de dimensão menor, o que também ajuda na otimização e no chamado crowding problem.

Em primeiro lugar, o t-SNE converte a matriz de distâncias euclidianas nos espaço de maior dimensão em probabilidades condicionais que representam similaridades. A similaridade entre dois pontos e é a probabilidade condicional de pegar como seu vizinho se os vizinhos fossem escolhidos em proporção à densidade de uma distribuição Normal com média em .

Para pontos próximos, é relativamente alta e para pontos distantes será muito pequena (para valores rasoáveis da variância da Normal escolhida).

Essa matriz não é simétrica e isso causa problemas, principalmente na presença de outliers. Para corrigir isso, o t-SNE simplesmente transforma a matriz de probabilidades condicionais em uma matriz de probabilidades conjuntas, definindo

Em seguida, considere a representação num espaço de menor dimensão de . Queremos que a matriz de similaridades entre e seja a mais parecida possível das smimilaridades entre e .

Agora as similaridades entre e são definidas pela probabilidade de ter como vizinho se os vizinhos fossem escolhidos proporcionalmente à densidade de uma distribuição t de Student com 1 grau de liberdade (equivalente a à distribuição Cauchy) com centro em .

O objetivo do t-SNE é que seja o mais parecido possível com . Para isso, ele define uma função de custo (no caso a divergência de Kullback-Leibler) e a minimiza usando o método do gradiente.

Para completar o problema, fica faltando apenas definir o valor de , variância da distribuição Normal utilizada para calcular as similaridades no espaço de maior dimensão. Essa variância é definida a partir de um hiper-parâmetro da técnica, chamado de perplexidade, que pode ser interpretado pela quantidade de vizinhos muito próximos que cada ponto tem. Esse parâmetro balanceia a atenção do modelo pelos aspectos locais da estrutura dos dados e pelos aspectos mais globais.

Claro que toda essa explciação foi feita por alguém que não entende tanto do assunto, para se aprofundar, vale a pena ler com calma o artigo original da técnica.

Aplicação

No R existem dois pacotes que podem ser usados para o t-SNE:

  • tsne: Em puro R, mais lento
  • Rtsne wrapper de um código em C++ (otimizado)
library(Rtsne)
library(ggplot2) 
iris_unicos <- unique(iris)
tsne <- Rtsne(as.matrix(iris_unicos[,1:4]), perplexity = 30) # Run TSNE
qplot(tsne$Y[,1], tsne$Y[,2], geom = "point", colour = iris_unicos$Species) # Plot the result

plot of chunk unnamed-chunk-1

Essa é uma aplicação bem simples. No próximo post irei aplicar o t-SNE em bancos de dados mais interessantes. Por enquanto, mostro aqui alguns exemplos de visualizações obtidas por outras pessoas.

Abaixo, a visualização do banco de dados MNIST

mnist

A técninca funcionou muito bem também no http://qwone.com/~jason/20Newsgroups/

20news

Referências

Quase tudo que eu escrevi aqui pode ser encontrado nos seguintes links:

Outros lugares com usos interessantes:

Inclusive, você pode fazer quantos você quiser usando o novo http://projector.tensorflow.org/.

Além de visualizações essa técnica tem sido bastante utilizada como feature engneering em copetições de machine learning. No Numerai, por exemplo, é responsável por melhorar bastante os resultados.