Kapan menggunakan lemma Johnson-Lindenstrauss di atas SVD?

Lemma Johnson-Lindenstrauss memungkinkan seseorang untuk mewakili titik-titik dalam ruang dimensi tinggi menjadi titik-titik dalam dimensi lebih rendah. Ketika menemukan ruang dimensi rendah yang paling cocok, teknik standar adalah menemukan dekomposisi nilai singular dan kemudian mengambil subruang yang dihasilkan oleh nilai singular terbesar. Kapan menarik menggunakan Johnson-Lindenstrauss di atas SVD?

machine-learning pengguna09128323
sumber

Jawaban:

Kedua pendekatan ini memberikan jaminan yang sangat berbeda.

JL Lemma pada dasarnya mengatakan "Anda memberi saya kesalahan yang Anda inginkan, dan saya akan memberi Anda ruang dimensi rendah yang menangkap jarak hingga kesalahan itu". Ini juga merupakan jaminan berpasangan terburuk : untuk setiap pasangan poin , dll

SVD pada dasarnya menjanjikan "Anda memberi tahu saya apa dimensi yang ingin Anda tinggali, dan saya akan memberi Anda embedding terbaik", di mana "terbaik" didefinisikan sebagai rata-rata : kesalahan total kemiripan sejati versus kemiripan yang diproyeksikan adalah minimum.

Jadi dari perspektif teoretis mereka memecahkan masalah yang sangat berbeda. Dalam praktiknya, yang mana yang Anda inginkan tergantung pada model Anda untuk masalah tersebut, parameter apa yang lebih penting (kesalahan atau dimensi), dan jenis jaminan apa yang Anda butuhkan.

Suresh Venkat
sumber

Bisakah seseorang memberi tahu saya bagaimana tepatnya

diperoleh dalam (1-eps) | uv | ^ 2 <= | f (u) -f (v) | ^ 2 <= (1 + eps) | uv | ^ 2 (dari en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma )?

f (\cdot)

$f(\cdot)$

T ....

Itu pertanyaan lain. Tetapi dalam (sangat) singkat, jika Anda mengambil matriks

dan mengisinya dengan entri yang diambil dari standar normal, maka

didefinisikan sebagai

A

$A$

f (x)

$f(x)$

A x

$Ax$

Suresh Venkat

Apakah ada skema JL untuk bidang terbatas juga di mana distorsi berada dalam metrik Hamming? Jika demikian, maka apa yang akan

berada di sini?

f

$f$

T ....

Anda tidak dapat melakukan pengurangan dimensionalitas ini secara efektif untuk metrik Hamming. Struktur

sangat berbeda. Dalam pengertian yang sangat mudah, mengakui pengurangan gaya JL terkait dengan hidup di ruang Hilbert.

ℓ_{1}

$\ell_1$

Suresh Venkat

SVD dan JL juga mengekstrapolasi ke poin masa depan juga berbeda.

Artinya, jika Anda menganggap data Anda berasal dari beberapa distribusi yang mendasarinya, pada prinsipnya SVD harus tetap "baik" untuk setiap poin di masa mendatang asalkan sampel tersebut diambil dari distribusi yang sama. Di sisi lain, dimensi target JL tergantung pada jumlah poin, yang berarti bahwa menerapkan transformasi JL ke poin tambahan dapat meningkatkan probabilitas kesalahan.

Ini menjadi relevan jika, misalnya, jika Anda menggunakan pengurangan dimensionalitas sebagai langkah preprocessing untuk beberapa algoritma lainnya. Batas SVD untuk data pelatihan mungkin berlaku pada data uji, tetapi JL tidak.

Frumple
sumber

Ini adalah poin yang sangat bagus.

Paul Siegel

Ini adalah kelanjutan dari jawaban Suresh - Saya mencari di Google sedikit setelah membaca jawabannya, dan muncul dengan pemahaman berikut. Saya awalnya akan memposting ini sebagai komentar untuk jawabannya, tetapi terus meningkat.

Tolong tunjukkan kesalahan dalam jawabannya, saya bukan ahli dalam bidang ini.

Dalam beberapa hal, JL dan SVD seperti apel dan jeruk.

1) Masalah yang mereka pecahkan benar-benar berbeda. Satu berkaitan dengan jarak berpasangan, yang lain dengan representasi terbaik. Satu kasus terburuk, yang lain adalah kasus rata-rata.

\begin{matrix} (1) & \arg min_{P} {sup_{u, v} (| 1 - \frac{| | P u - P v | |_{2}}{| | u - v | |_{2}} |)} \end{matrix}

$\arg\min\limits_{P} \left\{\sup\limits_{u,v} \left(\Biggl\lvert 1- \frac{||Pu-Pv||_2}{||u-v||_2} \Biggl\rvert \right) \right\} \tag{1}$

(Ini tidak tepat, saya akan berkomentar lebih lanjut tentang ini nanti)

$k$

\arg min_{P of dim k} {Avg (| | u - P u | |_{2})}

$\arg\min\limits_{P\text{ of dim k}} \left\{\text{Avg}\left(||u-Pu||_2\right)\right\}$

$\epsilon$

3) JL tidak konstruktif, SVD konstruktif - titik ini agak kabur, karena istilah konstruktif tidak didefinisikan secara tepat. Ada algoritma deterministik untuk menghitung SVD, tetapi algoritma untuk menemukan ruang JL adalah acak - lakukan proyeksi acak, jika Anda gagal, coba lagi.

$\epsilon$

(Lihat komentar untuk penjelasan mengenai bagian jawaban yang dicoret).

Sunting: @ john-myles-white telah menulis posting tentang JL untuk memverifikasi klaimnya, dan menunjukkan bagaimana proyeksi dapat dibangun: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- di-the-johnson-lindenstrauss-lemma /

elexhobby
sumber

Ada sejumlah kesalahan dalam jawaban Anda. (1) JL sangat konstruktif: ada semua jenis algoritme untuk membangun pemetaan (2) tidak mempertahankan perbedaan tetapi perbedaan relatif (rasio) (3) JL lemma telah diderandomisasi (4) JL berfungsi untuk setiap set vektor: konstruksi tidak tergantung pada input aktual. satu-satunya informasi yang dibutuhkan adalah jumlah vektor.

Suresh Venkat

Terima kasih Suresh. Saya telah memasukkan semua kecuali saran terakhir Anda. Silakan mengedit jawaban lebih lanjut. Pada poin terakhir, saya bingung. Anda mengatakan peta yang sama akan bekerja tidak peduli vektor apa yang saya berikan kepada Anda?

elexhobby

Itu poin yang agak halus. Setelah Anda memperbaiki kesalahan dan jumlah vektor, ada distribusi probabilitas tetap pada peta yang akan bekerja dengan probabilitas tinggi untuk setiap set vektor. Tentu saja tidak ada peta linear yang ditentukan secara deterministik yang memuaskan properti ini.

Sasho Nikolov

Layak untuk memeriksa implementasi scikit-learning

KLDavenport

0

$0$

1

$1$

1

$1$