t-SNE versus MDS

21

Ultimamente, tenho lido algumas perguntas sobre t-SNE ( Incorporação estocástica de vizinhos t-distribuídos ) e também visitou algumas perguntas sobre MDS ( Multidimensional Scaling ).

Eles costumam ser usados ​​de forma análoga; portanto, parecia uma boa idéia fazer essa pergunta, pois há muitas perguntas sobre as duas separadamente (ou comparadas ao PCA ) aqui.


Em suma, o que diferencia t-SNE e MDS? por exemplo. Quais são as sutilezas da hierarquia de dados que eles exploram, diferentes suposições etc.

Taxa de convergência? E quanto ao uso de kernels, ambos cumprem?

Firebug
fonte

Respostas:

19

O PCA seleciona dimensões influentes por análise própria dos próprios pontos de dados N, enquanto o MDS seleciona dimensões influentes por análise própria dos pontos de dados de uma matriz de distância pareada. Isso tem o efeito de destacar os desvios da uniformidade na distribuição. Considerando a matriz de distância como análoga a um tensor de tensão, o MDS pode ser considerado um algoritmo de layout "direcionado à força", cuja complexidade de execução é onde . O ( d N a ) 3 < a 4N2O(dNuma)3<uma4

O t-SNE, por outro lado, usa uma aproximação de campo para executar uma forma um pouco diferente de layout direcionado à força, normalmente via Barnes-Hut, que reduz a complexidade baseada no gradiente para , mas as propriedades de convergência são menos conhecidas para esse método de aproximação estocástica iterativa (tanto quanto eu sei) e, para os tempos de execução observados típicos são geralmente mais do que outros métodos de redução de dimensão. Os resultados geralmente são mais interpretáveis ​​visualmente do que a análise autônoma ingênua e, dependendo da distribuição, geralmente mais intuitivos que os resultados do MDS, que tendem a preservar a estrutura global à custa da estrutura local retida pelo t-SNE.O ( d N log ( N ) ) 2 d 4O(dN2)O(dNregistro(N))2d4

O MDS já é uma simplificação do PCA do kernel e deve ser extensível com kernels alternativos, enquanto o t-SNE do kernel é descrito no trabalho de Gilbrecht, Hammer, Schulz, Mokbel, Lueks et al. Eu não estou praticamente familiarizado com isso, mas talvez outro entrevistado possa estar.

Costumo escolher entre MDS e t-SNE com base em objetivos contextuais. Qualquer que seja a elucidação da estrutura que me interessa destacar, qualquer estrutura que possua maior poder explicativo, é o algoritmo que eu uso. Isso pode ser considerado uma armadilha, pois é uma forma de grau de liberdade do pesquisador. Mas a liberdade usada com sabedoria não é uma coisa tão ruim.

aminorex
fonte
Muito interessante! Posso pedir um esclarecimento sobre a interpretação do MDS como um algoritmo de layout "direcionado à força" e como é diferente, nesse sentido, do t-SNE?
Garini 18/03