Apakah ada versi t-SNE untuk streaming data?

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.

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.

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.

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.

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(n\log(n))$$O(n^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.