t-SNE versus MDS

21

Telah membaca beberapa pertanyaan tentang t-SNE ( t-Distributed Stochastic Neighbor Embedding ) belakangan ini, dan juga mengunjungi beberapa pertanyaan tentang MDS ( Multidimensional Scaling ).

Mereka sering digunakan secara analog, jadi sepertinya ide yang bagus membuat pertanyaan ini melihat ada banyak pertanyaan pada keduanya secara terpisah (atau dibandingkan dengan PCA ) di sini.


Singkatnya, apa yang membuat t-SNE dan MDS berbeda? misalnya. Keramahan apa dari hirarki data yang mereka jelajahi, asumsi berbeda, dll.

Tingkat konvergensi? Bagaimana dengan penggunaan kernel, apakah keduanya mematuhi?

Pembakar
sumber

Jawaban:

19

PCA menyeleksi berpengaruh dimensi dengan eigenanalysis dari titik data N sendiri, sementara MDS menyeleksi berpengaruh dimensi dengan eigenanalysis dari titik data dari matriks jarak berpasangan. Ini memiliki efek menyoroti penyimpangan dari keseragaman dalam distribusi. Mempertimbangkan matriks jarak sebagai analog dengan tensor tegangan, MDS dapat dianggap sebagai algoritma tata letak "gaya-diarahkan", kompleksitas eksekusi di antaranya adalah O ( d N a ) di mana 3 < a 4 . N2HAI(dNSebuah)3<Sebuah4

t-SNE, di sisi lain, menggunakan pendekatan lapangan untuk mengeksekusi bentuk yang agak berbeda dari tata letak gaya-diarahkan, biasanya melalui Barnes-Hut yang mengurangi kompleksitas berbasis gradien menjadi O ( d N log ( N ) ) , tetapi sifat konvergensi kurang dipahami dengan baik untuk metode pendekatan stokastik iteratif ini (sepengetahuan saya), dan untuk 2 d 4HAI(dN2)HAI(dNlog(N))2d4waktu berjalan yang diamati umumnya lebih lama dari metode pengurangan dimensi lainnya. Hasilnya seringkali lebih dapat ditafsirkan secara visual daripada analisis eigen naif, dan tergantung pada distribusinya, seringkali lebih intuitif daripada hasil MDS, yang cenderung melestarikan struktur global dengan mengorbankan struktur lokal yang dipertahankan oleh t-SNE.

MDS sudah merupakan penyederhanaan kernel PCA, dan harus dapat diperluas dengan kernel alternatif, sementara kernel t-SNE dijelaskan dalam pekerjaan oleh Gilbrecht, Hammer, Schulz, Mokbel, Lueks et al. Saya tidak terbiasa dengan hal itu, tetapi mungkin responden lain mungkin.

Saya cenderung memilih antara MDS dan t-SNE berdasarkan tujuan kontekstual. Mana pun yang menjelaskan struktur yang ingin saya sorot, struktur mana pun yang memiliki kekuatan penjelas yang lebih besar, itulah algoritma yang saya gunakan. Ini dapat dianggap jebakan, karena merupakan bentuk derajat kebebasan peneliti. Tetapi kebebasan yang digunakan dengan bijak bukanlah hal yang buruk.

aminorex
sumber
Sangat menarik! Bisakah saya meminta Anda klarifikasi tentang interpretasi MDS sebagai algoritma tata letak "diarahkan-paksa" dan bagaimana perbedaannya, dalam hal ini, dengan t-SNE?
Garini