Explicação intuitiva de como o UMAP funciona, comparado ao t-SNE

18

Eu tenho um doutorado em biologia molecular. Meus estudos começaram recentemente a envolver análise de dados de alta dimensão. Tive a ideia de como o t-SNE funciona (graças a um vídeo do StatQuest no YouTube ), mas não consigo entender o UMAP (ouvi a palestra do criador do UMAP on-line, mas não achei fácil de entender). Voltei ao artigo original descrevendo-o, mas era muita matemática para mim.

Alguém pode lançar alguma luz sobre o assunto? Estou procurando ou uma explicação intuitiva, semelhante ao vídeo StatQuest vinculado acima.

Atakan
fonte
11
Estou procurando intuição em palavras, mas também algumas dicas simples sobre cálculos matemáticos (não sei se o último é possível). Gostaria de ver algo assim no UMAP: "StatQuest tSNE claramente explicado" youtube.com/watch?v=NEaUSP4YerM Quando digo que entendo como o tSNE funciona, estou me referindo à ampla abordagem de cálculo descrita no vídeo . É um pouco difícil para mim imaginar o exemplo no vídeo em um espaço dimensional mais alto, mas no geral posso ver como as distâncias são calculadas. Eu gostaria de ter uma compreensão semelhante sobre UMAP
Atakan

Respostas:

13

Você disse que seu entendimento do t-SNE é baseado em https://www.youtube.com/watch?v=NEaUSP4YerM e está procurando uma explicação do UMAP em um nível semelhante.

Eu assisti este vídeo e é bastante preciso no que diz (tenho alguns pequenos detalhes, mas no geral é bom). Engraçado o suficiente, ele quase se aplica ao UMAP exatamente como é. Aqui estão as coisas que não se aplicam:

  1. As semelhanças são calculadas a distâncias usando um kernel diferente; não é gaussiano, mas também decai exponencialmente e também possui largura adaptativa, como no t-SNE.
  2. As semelhanças não são normalizadas para somar 1, mas ainda acabam sendo normalizadas para somar um valor constante.
  3. As semelhanças são simétricas, mas não apenas pela média.
  4. O kernel de similaridade no espaço de incorporação não é exatamente o kernel de distribuição t, mas um kernel muito muito semelhante.

Eu acho que todas essas diferenças não são muito importantes nem muito conseqüentes. A parte realmente importante é a parte em que no vídeo o narrador diz (10m40s):

Queremos que esta linha se pareça com esta linha [...]

O vídeo não explica como o t-SNE quantifica se são semelhantes ou não e como é possível conseguir que elas se pareçam. Ambas as partes são diferentes no UMAP. Mas a declaração citada também pode ser aplicada ao UMAP.


Da maneira como o artigo UMAP é escrito, as semelhanças computacionais com o t-SNE não são muito aparentes. Role para baixo até o Apêndice C em https://arxiv.org/pdf/1802.03426.pdf e / ou veja aqui https://jlmelville.github.io/uwot/umap-for-tsne.html , se desejar ver uma comparação lado a lado dos cálculos listados acima e das funções de perda de t-SNE e UMAP.

ameba
fonte
Isso é muito útil, obrigado! Eu tenho uma pergunta sobre esse segmento específico do vídeo. Quando ele está mostrando o "mapa de calor não ordenado" à esquerda, os pontos de anotação (pontos de dados coloridos) estão em ordem e a intensidade da cor na interseção da linha-coluna não corresponde ao gráfico no lado direito. Isso é uma deturpação, certo? Eu espero que o gráfico à esquerda seja desordenado quando se trata de pontos de dados, que serão solicitados pelo UMAP. Estou no caminho errado aqui?
Atakan
@ Atakan Não tenho muita certeza do que você está dizendo. Não vejo deturpação. Estou olhando para o quadro de vídeo às 10:40. A matriz de similaridade esquerda é "uma bagunça". Os "pontos de anotação" à esquerda simplesmente marcam o cluster de cada ponto; imagine que os pontos sejam numerados de 1 a 12. As 12 linhas / colunas da matriz correspondem a esses pontos; as 4 primeiras linhas correspondem aos pontos "azuis", as 4 próximas correspondem aos pontos "vermelhos", etc. Como a incorporação unidimensional (na parte inferior do quadro) é "uma bagunça", as semelhanças na matriz também são "uma bagunça".
Ameba
8

A principal diferença entre t-SNE e UMAP é a interpretação da distância entre objetos ou "aglomerados". Uso as aspas, pois os dois algoritmos não se destinam ao cluster - eles são principalmente para visualização.

O t-SNE preserva a estrutura local nos dados.

O UMAP afirma preservar a estrutura local e a maior parte da estrutura global nos dados.

Isso significa que com t-SNE você não pode interpretar a distância entre os clusters A e B nas diferentes extremidades do gráfico. Você não pode inferir que esses clusters são mais diferentes do que A e C, onde C está mais próximo de A na plotagem. Mas no cluster A, você pode dizer que pontos próximos um do outro são objetos mais semelhantes do que pontos em extremidades diferentes da imagem do cluster.

Com o UMAP, você deve conseguir interpretar as distâncias entre / posições de pontos e clusters.

Ambos os algoritmos são altamente estocásticos e dependem muito da escolha de hiperparâmetros (t-SNE ainda mais que UMAP) e podem produzir resultados muito diferentes em execuções diferentes, portanto, seu gráfico pode ofuscar uma informação nos dados que uma execução subseqüente possa revelar.

O bom PCA antigo, por outro lado, é determinístico e facilmente compreensível com o conhecimento básico de álgebra linear (multiplicação de matrizes e problemas próprios), mas é apenas uma redução linear em contraste com as reduções não lineares de t-SNE e UMAP.

Edgar
fonte
10
Discordo totalmente desta avaliação: "t-SNE preserva a estrutura local e ignora a estrutura global. O UMAP reconhece a estrutura local e global". O UMAP opera no gráfico de vizinhos k-mais próximos (para um pequeno valor de k), exatamente como o t-SNE.
ameba
Na verdade, é o que afirmam os autores da UMAP, veja, por exemplo, aqui ou aqui . Você conhece uma comparação (teórica ou prática) que mostre que a afirmação deles não é verdadeira? Por favor compartilhe!
Edgar
6
Eu sei que eles dizem isso ...: - / Mas são eles que estão fazendo essa afirmação, então o ônus é deles para provar isso (não é para eu refutar). Eu não estava convencido pelo que vi até agora.
Ameba
2
verdade, ainda é meio que um novo método. esperamos que seja feita uma avaliação mais rigorosa do umap vs t-sne. Eu mudei minha resposta para refletir seu ponto de vista.
Edgar
4
Agora existe uma pré-impressão sobre esse mesmo tópico: O UMAP não preserva a estrutura global melhor que o t-SNE ao usar a mesma inicialização
krassowski