Apakah ada versi t-SNE untuk streaming data?

19

Pemahaman saya tentang t-SNE dan pendekatan Barnes-Hut adalah bahwa semua titik data diperlukan sehingga semua interaksi gaya dapat dihitung pada waktu yang sama dan setiap titik dapat disesuaikan dalam peta 2d (atau dimensi yang lebih rendah).

Apakah ada versi t-sne yang secara efisien dapat menangani data streaming? Jadi jika pengamatan saya tiba satu per satu, itu akan menemukan lokasi terbaik di peta 2d untuk menempatkan pengamatan baru, atau terus memperbarui semua titik pada peta 2d untuk memperhitungkan pengamatan baru.

Apakah ini masuk akal atau tidak bertentangan dengan pengaturan t-sne.

Ger
sumber
Perkiraan Barnes-Hut membuat t-SNE sangat dapat diskalakan (setidaknya, Anda dapat menggunakannya dengan 100.000 baris, saya mencobanya). Anda dapat memanggilnya dari R: cran.r-project.org/web/packages/Rtsne/index.html
RUser4512
Hai, terima kasih! Saya senang memilih jawaban Anda jika Anda memasukkannya di bagian jawaban ini.
Tom
3
Lihat di sini untuk versi parametrik yang diimplementasikan dengan neural ntwork. lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
eyaler

Jawaban:

15

Saya memiliki pertanyaan yang persis sama dan mempostingnya di video YouTube dari kuliah CS231n yang diberikan oleh Andrej Karpathy beberapa minggu yang lalu. Berikut adalah pertanyaan yang saya posting diikuti oleh tanggapan Andrej:

https://www.youtube.com/watch?v=ta5fdaqDT3M&lc=z12ji3arguzwgxdm422gxnf54xaluzhcx

Q:

Apakah t-SNE membutuhkan seluruh kumpulan gambar (atau lebih umum, data) untuk membuat ruang fitur berdimensi rendah? Dengan PCA Anda dapat membuat ruang fitur dimensi rendah pada kumpulan data dan kemudian memproyeksikan titik data baru ke ruang yang sama tanpa harus "melatih ulang". Apakah itu berlaku untuk t-SNE?

Saya bertanya karena saya perhatikan bahwa scikit-learn memiliki t-SNE sebagai bagian dari kelas berjenisnya, tetapi modul itu tidak memiliki metode transformasi () seperti halnya PCA. Jadi, setidaknya, di sklearn, sepertinya ini tidak mungkin.

Pertanyaan saya sampai di sini. Bagaimana Anda menerapkan t-SNE dalam situasi streaming atau online di mana Anda ingin terus memperbarui visualisasi dengan gambar baru? Agaknya, orang tidak ingin menerapkan algoritma pada seluruh kumpulan untuk setiap gambar baru.

SEBUAH:

+ Evan Zamir ya ini dimungkinkan dengan t-SNE, tapi mungkin tidak didukung di luar kotak dengan implementasi t-SNE biasa. Biasanya lokasi masing-masing titik adalah parameter dalam optimasi, tetapi Anda juga dapat membuat pemetaan dari high-D -> low-D (mis. Neural net) dan backprop melalui lokasi. Kemudian Anda berakhir dengan fungsi embedding dan dapat memproyeksikan poin baru. Jadi tidak ada yang mencegah hal ini pada prinsipnya, tetapi beberapa implementasi mungkin tidak mendukungnya karena ini adalah kasus penggunaan yang kurang sering.

thecity2
sumber
11

Saat berhadapan dengan data streaming, Anda mungkin tidak ingin / perlu menyematkan semua poin dalam sejarah dalam satu peta t-SNE. Sebagai alternatif, Anda dapat melakukan penyematan online dengan mengikuti langkah-langkah sederhana ini:

  1. pilih jendela waktu durasi T, cukup lama sehingga setiap pola yang diinginkan muncul setidaknya beberapa kali dalam durasi jendela.

  2. gulir jendela saat data mengalir, dengan langkah-waktu dt jauh lebih kecil dari T. Untuk setiap posisi jendela, hitung t-SNE penyisipan titik data di jendela waktu.

  3. benih setiap embedding dengan hasil yang sebelumnya. Dalam t-SNE, kita perlu memilih koordinat awal dari titik data dalam ruang dimensi rendah. Dalam kasus kami, karena kami memilih dt jauh lebih kecil dari T, dua pernikahan berturut-turut berbagi sebagian besar poin data mereka. Untuk semua titik data yang dibagikan, cocok dengan koordinat awal mereka di embedding saat ini dengan koordinat akhir mereka di embedding sebelumnya . Langkah ini akan memastikan bahwa pola serupa memiliki representasi yang konsisten di seluruh embeddings yang berurutan. (dalam implementasi sklearn dengan python, parameter seed adalah "init". Secara default, implementasi sklearn menetapkan posisi awal titik secara acak)

Catatan 1: Penting bahwa pola-pola yang menarik muncul setidaknya sekali dalam jendela waktu tertentu, sehingga memori representasi tidak hilang ketika jendela meluncur melalui dataset. Memang, t-SNE biasanya tidak konvergen ke solusi unik tetapi hanya ke minimum lokal, jadi jika memori hilang, pola yang sama mungkin diwakili dengan cara yang sangat berbeda dalam dua contoh embedding.

Catatan 2: Metode ini sangat relevan ketika berhadapan dengan deret waktu non-stasioner, di mana orang ingin melacak pola yang berevolusi perlahan-lahan sepanjang waktu. Memang, setiap penyisipan di sini disoroti secara khusus ke jendela waktu kecil di mana ia dihitung, memastikan bahwa ia menangkap struktur lokal sementara dengan cara terbaik (berlawanan dengan penyematan penuh seluruh dataset non-stasioner).

Catatan 3: Dalam metode ini, embedding berturut-turut tidak dapat diparalelkan, karena seseorang membutuhkan hasil dari embedding sebelumnya untuk menabur yang berikutnya. Namun, karena seed (yaitu koordinat awal dari poin) dipilih dengan baik untuk sebagian besar poin (semua poin yang dibagi antara embeddings berturut-turut), embedding biasanya menyatu sangat cepat, dalam beberapa iterasi saja.

Untuk contoh penerapan metode ini ke deret waktu non-stasioner, lihat artikel ini ( ICLR 2016, Mempelajari representasi stabil dalam dunia yang berubah dengan t-SNE online: bukti konsep dalam burung penyanyi ), di mana ia berhasil diterapkan untuk melacak munculnya suku kata di seluruh pengembangan di burung penyanyi.

Stéphane Deny
sumber
2
Selamat datang di komunitas. Plagiarisme diri tidak keren. Saya merujuk ke posting pertama Anda di sini . Tentu, kami dapat menggunakan alasan yang sama untuk beberapa jawaban, berpotensi menyalin-menempelkan satu atau dua frasa atau hanya menautkan ke jawaban sebelumnya secara langsung. Meskipun demikian, jangan menurunkan posting Anda menjadi salinan kata demi kata dari jawaban sebelumnya dengan kalimat pertama yang diubah. Ini menurunkan kualitas konten CV dan menunjukkan sportivitas skolastik yang buruk oleh Anda.
usεr11852 mengatakan Reinstate Monic
5
@ usεr11852 Masalah telah dibuat karena utas lainnya adalah duplikat dari yang ini. Karena itu saya telah menutup yang lain, menggabungkannya dengan yang ini, dan menghapus jawaban yang tidak perlu. Secara umum, Stéphane, setiap kali Anda merasa terinspirasi untuk mengirim balasan yang persis sama dalam dua utas, harap tandai salah satunya sebagai duplikat sehingga kami dapat menggabungkannya.
whuber
2
@ usεr11852 OK, maaf untuk jawaban rangkap, saya kontributor baru jadi saya belum tahu praktik terbaik.
Stéphane Deny
1
@whuber Terima kasih telah menggabungkan pertanyaan dan atas kepala!
Stéphane Deny
1
Anda tampaknya kehilangan 2 upvotes sebagai hasilnya. Sangat disayangkan. +1 :) Selamat datang di CV.
Amoeba berkata Reinstate Monica
7

Ada varian yang baru-baru ini diterbitkan, disebut A-tSNE, yang mendukung secara dinamis menambahkan data baru dan memurnikan cluster baik berdasarkan bidang minat atau dengan input pengguna. Makalah yang ditautkan di bawah ini memiliki beberapa contoh bagus tentang ini:

Kutipan: arXiv: 1512.01655

TSNE Diperkirakan dan Dapat Digunakan Pengguna untuk Progressive Visual Analytics Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova

Ringkasan:

Progressive Visual Analytics bertujuan untuk meningkatkan interaktivitas dalam teknik analitik yang ada dengan cara visualisasi serta interaksi dengan hasil antara. Salah satu metode utama untuk analisis data adalah reduksi dimensi, misalnya, untuk menghasilkan embeddings 2D yang dapat divisualisasikan dan dianalisis secara efisien. t-Distributed Stochastic Neighbor Embedding (tSNE) adalah teknik yang cocok untuk visualisasi beberapa data dimensi tinggi. tSNE dapat membuat hasil antara yang berarti tetapi mengalami inisialisasi lambat yang membatasi penerapannya dalam Progressive Visual Analytics. Kami memperkenalkan pendekatan tSNE yang dapat dikendalikan (A-tSNE), yang berdagang dengan kecepatan dan akurasi, untuk memungkinkan eksplorasi data interaktif. Kami menawarkan teknik visualisasi real-time, termasuk solusi berbasis kepadatan dan Lensa Ajaib untuk memeriksa tingkat perkiraan. Dengan umpan balik ini, pengguna dapat memutuskan perbaikan lokal dan mengarahkan tingkat perkiraan selama analisis. Kami mendemonstrasikan teknik kami dengan beberapa dataset, dalam skenario penelitian dunia nyata dan untuk analisis real-time stream dimensi tinggi untuk menggambarkan efektivitasnya untuk analisis data interaktif.

cvlad
sumber
Selamat datang di situs ini. Kami mencoba membangun repositori permanen untuk informasi statistik berkualitas tinggi dalam bentuk pertanyaan & jawaban. Jadi, kami waspada terhadap jawaban tautan saja, karena tautannya. Bisakah Anda memposting kutipan lengkap & ringkasan informasi di tautan, kalau-kalau mati?
gung - Reinstate Monica
6

Perkiraan Barnes-Hut membuat t-SNE sangat dapat diskalakan (setidaknya, Anda dapat menggunakannya dengan 100.000 baris, saya mencobanya). Anda dapat memanggilnya dari R: Rtsne

O(nlog(n))O(n2)

RUser4512
sumber
1
Saya menggunakannya dengan 250.000 baris 1K padat - sebenarnya cukup bagus, tapi itu terikat oleh memori.
Vladimir Chupakhin
2

Perkiraan Barnes-Hut sekarang menjadi metode default di scikit-learn pada versi 0.17.0:

Secara default, algoritma perhitungan gradien menggunakan pendekatan Barnes-Hut yang berjalan dalam waktu O (NlogN). metode = 'tepat' akan berjalan pada algoritma yang lebih lambat, tetapi tepat, dalam waktu O (N ^ 2). Algoritma yang tepat harus digunakan ketika kesalahan tetangga terdekat harus lebih baik dari 3%. Namun, metode yang tepat tidak dapat skala ke jutaan contoh. Baru di versi 0.17: Perkiraan metode optimasi melalui Barnes-Hut.

thecity2
sumber
Ini tidak menjawab pertanyaan. BH, meski lebih cepat, tidak mendukung streaming. Mungkin Anda memaksudkan ini sebagai komentar atas jawaban ini .
merv