Haruskah reduksi dimensi untuk visualisasi dianggap sebagai masalah "tertutup", diselesaikan oleh t-SNE?

23

Saya telah membaca banyak tentang algoritma -sne untuk pengurangan dimensi. Saya sangat terkesan dengan kinerja pada dataset "klasik", seperti MNIST, di mana ia mencapai pemisahan digit yang jelas ( lihat artikel asli ):t

t-SNE MNIST

Saya juga menggunakannya untuk memvisualisasikan fitur yang dipelajari oleh jaringan saraf yang saya latih dan saya sangat senang dengan hasilnya.

Jadi, seperti yang saya pahami:

O ( n log n )t -sne memiliki hasil yang baik pada sebagian besar dataset, dan memiliki implementasi yang cukup efisien - dengan metode pendekatan Barnes-Hut. Lalu, dapatkah kita berpotensi mengatakan bahwa masalah "pengurangan dimensi", setidaknya untuk tujuan menciptakan visualisasi 2D / 3D yang baik, sekarang merupakan masalah "tertutup"?O(nlogn)

Saya sadar bahwa ini adalah pernyataan yang cukup berani. Saya tertarik untuk memahami apa "jebakan" potensial dari metode ini. Yaitu, adakah kasus yang kita tahu tidak berguna? Selain itu, apa masalah "terbuka" di bidang ini?

galoosh33
sumber

Jawaban:

16

Tentu saja tidak.

Saya setuju bahwa t-SNE adalah algoritma luar biasa yang bekerja sangat baik dan itu merupakan terobosan nyata pada saat itu. Namun:

  • itu memang memiliki kekurangan serius;
  • beberapa kekurangan harus dipecahkan;
  • sudah ada algoritma yang berkinerja lebih baik dalam beberapa kasus;
  • banyak properti t-SNE masih kurang dipahami.

Seseorang ditautkan ke akun yang sangat populer ini tentang beberapa kekurangan t-SNE: https://distill.pub/2016/misread-tsne/ (+1), tetapi hanya membahas dataset mainan yang sangat sederhana dan saya menemukan bahwa itu tidak sesuai. sangat baik untuk masalah yang dihadapi seseorang dalam praktik ketika bekerja dengan t-SNE dan algoritma terkait pada data dunia nyata. Sebagai contoh:

  1. t-SNE sering gagal mempertahankan struktur global dataset;
  2. t-SNE cenderung menderita "kepadatan" ketika tumbuh di atas ~ 100rb;N
  3. Runtime Barnes-Hut terlalu lambat untuk besar .N

Saya akan membahas secara singkat ketiganya di bawah ini.


  1. t-SNE sering gagal melestarikan struktur global dataset.

    Pertimbangkan dataset RNA-seq sel tunggal ini dari institut Allen (sel kortikal mouse): http://celltypes.brain-map.org/rnaseq/mouse . Ia memiliki ~ 23rb sel. Kami tahu apriori bahwa kumpulan data ini memiliki banyak struktur hierarkis yang berarti, dan ini dikonfirmasi oleh pengelompokan hierarki. Ada neuron dan sel non-saraf (glia, astrosit, dll.). Di antara neuron, ada neuron rangsang dan penghambatan - dua kelompok yang sangat berbeda. Di antara misalnya neuron penghambat, ada beberapa kelompok utama: Pvalb-expressing, SSt-expressing, VIP-expressing. Dalam salah satu dari kelompok-kelompok ini, tampaknya ada beberapa kelompok lebih lanjut. Ini tercermin dalam hierarki clustering tree. Tapi ini t-SNE, diambil dari tautan di atas:

    masukkan deskripsi gambar di sini

    Sel-sel non-saraf berwarna abu-abu / coklat / hitam. Neuron eksitasi berwarna biru / teal / hijau. Neuron penghambat berwarna oranye / merah / ungu. Seseorang ingin kelompok-kelompok besar ini tetap bersatu, tetapi ini tidak terjadi: begitu t-SNE memisahkan suatu kelompok menjadi beberapa kelompok, mereka akhirnya dapat diposisikan secara sewenang-wenang. Struktur hierarkis dari dataset hilang.

    Saya pikir ini harus menjadi masalah yang dapat dipecahkan, tetapi saya tidak mengetahui adanya perkembangan berprinsip yang baik, meskipun ada beberapa pekerjaan baru ke arah ini (termasuk saya sendiri).

  2. t-SNE cenderung menderita "kepadatan" ketika tumbuh di atas ~ 100rbN

    t-SNE bekerja sangat baik pada data MNIST. Tetapi pertimbangkan ini (diambil dari makalah ini ):

    masukkan deskripsi gambar di sini

    Dengan 1 juta poin data, semua kluster digumpalkan bersama-sama (alasan tepatnya untuk hal ini tidak terlalu jelas) dan satu-satunya cara yang diketahui untuk melawan keseimbangan adalah dengan beberapa peretasan kotor seperti ditunjukkan di atas. Saya tahu dari pengalaman bahwa ini terjadi dengan dataset besar yang sama juga.

    Orang bisa melihat ini dengan MNIST sendiri (N = 70k). Lihatlah:

    masukkan deskripsi gambar di sini

    Di sebelah kanan adalah t-SNE. Di sebelah kiri adalah UMAP , sebuah metode baru yang menarik di bawah pengembangan aktif, yang sangat mirip dengan yang berukuran besar . UMAP / largeVis menarik cluster jauh lebih jauh. Alasan pasti untuk ini adalah IMHO tidak jelas; Saya akan mengatakan masih banyak yang harus dipahami di sini, dan mungkin banyak yang harus diperbaiki.

  3. Runtime Barnes-Hut terlalu lambat untuk besarN

    Vanilla t-SNE tidak dapat digunakan untuk lebih dari ~ 10k. Solusi standar sampai saat ini adalah Barnes-Hut t-SNE, namun untuk lebih dekat ke ~ 1mln menjadi sangat lambat. Ini adalah salah satu nilai jual utama UMAP, tetapi sebenarnya makalah terbaru menyarankan FFT-accelerated t-SNE (FIt-SNE) yang bekerja jauh lebih cepat daripada Barnes-Hut t-SNE dan setidaknya secepat secepat UMAP. Saya merekomendasikan semua orang untuk menggunakan implementasi ini mulai sekarang.NNN

    masukkan deskripsi gambar di sini

    Jadi ini mungkin bukan masalah terbuka lagi, tapi dulu sampai baru-baru ini, dan saya kira ada ruang untuk perbaikan lebih lanjut dalam runtime. Jadi pekerjaan pasti bisa berlanjut ke arah ini.

amuba kata Reinstate Monica
sumber
7

Berikut adalah analisis yang sangat baik tentang bagaimana memvariasikan parameter ketika menjalankan t-SNE memengaruhi beberapa set data yang sangat sederhana: http://distill.pub/2016/misread-tsne/ . Secara umum, t-SNE tampaknya baik dalam mengenali struktur dimensi tinggi (termasuk hubungan yang lebih kompleks daripada cluster), meskipun hal ini tunduk pada penyetelan parameter, terutama nilai-nilai kebingungan.

liangjy
sumber
7

Saya masih ingin mendengar komentar lain tetapi saya akan memposting jawaban saya sendiri untuk saat ini, seperti yang saya lihat. Sementara saya mencari jawaban yang lebih "praktis", ada dua "kelemahan" teoretis untuk t-sne yang layak disebut; yang pertama kurang bermasalah, dan yang kedua harus dipertimbangkan:

  1. Fungsi biaya t-sne bukan cembung, jadi kami tidak dijamin untuk mencapai optimal global : Teknik pengurangan dimensi lainnya (Isomap, LLE) memiliki fungsi biaya cembung. Dalam t-sne ini tidak demikian, maka ada beberapa parameter optimasi yang perlu disetel secara efektif untuk mencapai solusi "baik". Namun, meskipun potensi jebakan teoretis, perlu disebutkan bahwa dalam praktiknya ini bukan kejatuhan, karena tampaknya bahkan "minimum lokal" dari algoritma t-sne lebih baik (menciptakan visualisasi yang lebih baik) kemudian minimum global dari metode lain .

  2. kutukan dimensi intrinstik : Satu hal penting yang perlu diingat ketika menggunakan t-sne adalah bahwa itu pada dasarnya adalah pembelajaran berjenisalgoritma. Pada dasarnya, ini berarti t-sne (dan metode lain semacam itu) dirancang untuk bekerja dalam situasi di mana dimensi tinggi asli hanya secara artifisial tinggi: ada dimensi intrinsik yang lebih rendah pada data. yaitu, data "duduk" pada manifold dimensi yang lebih rendah. Contoh yang baik untuk diingat adalah foto-foto berurutan dari orang yang sama: Walaupun saya mungkin mewakili setiap gambar dalam jumlah piksel (dimensi tinggi), dimensi intrinstik data sebenarnya dibatasi oleh transformasi fisik titik-titik (dalam kasus ini, rotasi 3D kepala). Dalam kasus seperti itu t-sne berfungsi dengan baik. Tetapi dalam kasus di mana dimensi intrinsiknya tinggi, atau titik data berada pada manifold yang sangat bervariasi, t-sne diharapkan berkinerja buruk, karena asumsi yang paling mendasar - linearitas lokal pada manifold - dilanggar.

Untuk pengguna praktis, saya pikir ini menyiratkan dua saran yang berguna untuk diingat:

  1. Sebelum melakukan pengurangan dimensionalitas untuk metode visualisasi, selalu coba cari tahu terlebih dahulu apakah sebenarnya ada dimensi intrinsik yang lebih rendah untuk data yang Anda hadapi.

  2. Jika Anda tidak yakin tentang 1 (dan juga secara umum), mungkin bermanfaat, seperti artikel asli menyarankan, untuk "melakukan t-sne pada representasi data yang diperoleh dari model yang mewakili berbagai data yang sangat beragam, secara efisien dalam angka dari lapisan nonlinear, seperti auto-encoder ". Jadi kombinasi auto-encoder + t-sne dapat menjadi solusi yang baik dalam kasus seperti itu.

galoosh33
sumber
Hai @ galoosh33! Saya bertanya-tanya apakah Anda sudah memiliki kesempatan untuk melihat jawaban saya. Apakah ini membantu? Saya tidak tahu apakah Anda masih tertarik dengan 1,5 tahun ini setelah mengajukan pertanyaan ini, jadi saya akan menghargai umpan balik ... Dalam jawaban yang Anda terima sendiri, Anda mengatakan bahwa Anda masih akan senang mendengar pemikiran lebih lanjut, tetapi ini juga merupakan beberapa waktu lalu :)
amoeba berkata Reinstate Monica
1
terima kasih atas jawaban Anda yang luar biasa @amoeba! Saya akan memeriksanya akhir pekan ini.
galoosh33