Bagaimana memahami Hashing Sensitifitas Lokalitas?

Saya perhatikan bahwa LSH tampaknya cara yang baik untuk menemukan barang serupa dengan properti berdimensi tinggi.

Setelah membaca makalah http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf , saya masih bingung dengan rumus-rumus itu.

Adakah yang tahu blog atau artikel yang menjelaskan cara mudah itu?

Tutorial terbaik yang saya lihat untuk LSH ada di buku: Mining of Massive Datasets. Periksa Bab 3 - Menemukan Barang Sejenis http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Saya juga merekomendasikan slide di bawah ini: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . Contoh dalam slide ini banyak membantu saya dalam memahami hashing untuk persamaan cosinus.

Saya meminjam dua slide dari Benjamin Van Durme & Ashwin Lall, ACL2010 dan mencoba menjelaskan intuisi Keluarga LSH untuk Cosine Distance sedikit.

• Pada gambar, ada dua lingkaran dengan warna merah dan kuning , mewakili dua titik data dua dimensi. Kami mencoba untuk menemukan kesamaan cosinus mereka menggunakan LSH.
• Garis abu-abu adalah beberapa pesawat yang dipilih secara acak.
• Bergantung pada apakah titik data terletak di atas atau di bawah garis abu-abu, kami menandai hubungan ini sebagai 0/1.
• Di sudut kiri atas, ada dua baris kotak putih / hitam, masing-masing mewakili tanda tangan dari dua titik data. Setiap kotak sesuai dengan bit 0 (putih) atau 1 (hitam).
• Jadi, sekali Anda memiliki kumpulan pesawat, Anda dapat menyandikan titik data dengan lokasi masing-masing ke pesawat. Bayangkan bahwa ketika kita memiliki lebih banyak pesawat di kolam, perbedaan sudut yang dikodekan dalam tanda tangan lebih dekat dengan perbedaan yang sebenarnya. Karena hanya pesawat yang berada di antara dua titik yang akan memberikan dua data nilai bit yang berbeda.

• Sekarang kita melihat tanda tangan dari dua titik data. Seperti dalam contoh, kami hanya menggunakan 6 bit (kotak) untuk mewakili setiap data. Ini adalah hash LSH untuk data asli yang kami miliki.
• Jarak hamming antara kedua nilai hash adalah 1, karena tanda tangan mereka hanya berbeda dengan 1 bit.
• Mempertimbangkan panjang tanda tangan, kita dapat menghitung kesamaan sudutnya seperti yang ditunjukkan pada grafik.

Saya punya beberapa kode sampel (hanya 50 baris) dengan python di sini yang menggunakan cosine similarity. https://gist.github.com/94a3d425009be0f94751

Tweet di ruang vektor bisa menjadi contoh bagus dari data dimensi tinggi.

Lihat posting blog saya tentang penerapan Hashing Sensitifitas Lokal ke tweet untuk menemukan yang serupa.

http://micvog.com/2013/09/08/storm-first-story-detection/

Dan karena satu gambar adalah seribu kata, periksa gambar di bawah ini:

http://micvog.files.wordpress.com/2013/08/lsh1.png

Semoga ini bisa membantu. @mvogiatzis

Inilah presentasi dari Stanford yang menjelaskannya. Itu membuat perbedaan besar bagi saya. Bagian dua lebih banyak tentang LSH, tetapi bagian satu juga membahasnya.

Gambar ikhtisar (Ada lebih banyak di slide):

Pencarian Tetangga Tetangga dalam Data Dimensi Tinggi - Bagian1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Pencarian Tetangga Dekat dalam Data Dimensi Tinggi - Bagian2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

• LSH adalah prosedur yang mengambil sebagai input sekumpulan dokumen / gambar / objek dan menghasilkan semacam Tabel Hash.
• Indeks tabel ini berisi dokumen-dokumen sedemikian rupa sehingga dokumen-dokumen yang berada pada indeks yang sama dianggap serupa dan indeks-indeks yang berbeda " berbeda ".
• Mana yang serupa tergantung pada sistem metrik dan juga pada kemiripan ambang s yang bertindak seperti parameter global LSH.
• Terserah Anda untuk menentukan apa ambang batas yang memadai s adalah untuk masalah Anda.

Penting untuk digarisbawahi bahwa langkah-langkah kesamaan yang berbeda memiliki implementasi LSH yang berbeda.

Di blog saya, saya mencoba menjelaskan secara menyeluruh LSH untuk kasus-kasus minHashing (ukuran kesamaan jaccard) dan simHashing (ukuran jarak cosinus). Saya harap Anda menemukannya bermanfaat: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Saya orang yang visual. Inilah yang bekerja untuk saya sebagai intuisi.

Katakanlah setiap hal yang ingin Anda cari kira-kira adalah benda-benda fisik seperti apel, kubus, kursi.

Intuisi saya untuk sebuah LSH adalah bahwa ia mirip dengan mengambil bayangan dari objek-objek ini. Seperti jika Anda mengambil bayangan kubus 3D, Anda mendapatkan 2D persegi seperti pada selembar kertas, atau bola 3D akan memberi Anda bayangan seperti lingkaran di selembar kertas.

Akhirnya, ada lebih dari tiga dimensi dalam masalah pencarian (di mana setiap kata dalam sebuah teks bisa menjadi satu dimensi) tetapi analogi bayangan masih sangat berguna bagi saya.

Sekarang kita dapat secara efisien membandingkan rangkaian bit dalam perangkat lunak. String bit panjang tetap agak, lebih atau kurang, seperti garis dalam dimensi tunggal.

Jadi dengan LSH, saya memproyeksikan bayangan objek pada akhirnya sebagai titik (0 atau 1) pada string garis / bit panjang tetap tunggal.

Trik keseluruhannya adalah untuk mengambil bayangan sehingga mereka masih masuk akal di dimensi yang lebih rendah misalnya mereka menyerupai objek asli dengan cara yang cukup baik yang dapat dikenali.

Gambar 2D kubus dalam perspektif memberitahu saya ini adalah kubus. Tapi saya tidak dapat dengan mudah membedakan kotak 2D dari bayangan kubus 3D tanpa perspektif: keduanya terlihat seperti kotak bagi saya.

Bagaimana saya mempresentasikan objek saya ke cahaya akan menentukan apakah saya mendapatkan bayangan yang dapat dikenali dengan baik atau tidak. Jadi saya menganggap LSH "baik" sebagai yang akan mengubah objek saya di depan cahaya sehingga bayangan mereka paling mudah dikenali sebagai mewakili objek saya.

Jadi untuk rekap: Saya memikirkan hal-hal untuk diindeks dengan LSH sebagai objek fisik seperti kubus, meja, atau kursi, dan saya memproyeksikan bayangan mereka dalam 2D ​​dan akhirnya sepanjang garis (sedikit string). Dan fungsi "baik" LSH "" adalah bagaimana saya menyajikan objek saya di depan cahaya untuk mendapatkan bentuk yang kira-kira dapat dibedakan di tanah datar 2D dan kemudian bit string saya.

Akhirnya ketika saya ingin mencari apakah suatu objek yang saya miliki mirip dengan beberapa objek yang saya indeks, saya mengambil bayangan dari objek "permintaan" ini menggunakan cara yang sama untuk menyajikan objek saya di depan cahaya (akhirnya berakhir dengan sedikit string juga). Dan sekarang saya dapat membandingkan seberapa mirip string bit itu dengan semua string bit lainnya yang diindeks yang merupakan proxy untuk mencari seluruh objek saya jika saya menemukan cara yang baik dan dapat dikenali untuk menyajikan objek saya ke cahaya saya.

Sebagai jawaban singkat, tldr :

Contoh hashing sensitif lokalitas bisa dengan pertama-tama mengatur pesawat secara acak (dengan rotasi dan offset) di ruang input Anda untuk hash, dan kemudian untuk menjatuhkan poin Anda ke hash di ruang tersebut, dan untuk setiap pesawat Anda mengukur jika titik tersebut adalah di atas atau di bawahnya (mis: 0 atau 1), dan jawabannya adalah hash. Jadi titik-titik yang serupa di ruang angkasa akan memiliki hash yang serupa jika diukur dengan jarak cosinus sebelum atau sesudah.

Anda dapat membaca contoh ini menggunakan scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer