Locality Sensitive Hashing

Locality-sensitive hashing
Partiție în bandă
Alegerea lui b & r
RezumatLSH

Locality-sensitive hashing

Obiectiv: Găsirea documentelor cu similaritate Jaccard de cel puțin t

Ideea generală a LSH este de a găsi un algoritm astfel încât, dacă introducem semnăturile a 2 documente, acesta să ne spună dacă aceste 2 documente formează sau nu o pereche candidată, adică dacă similaritatea lor este mai mare decât un prag t. Nu uitați că luăm similaritatea semnăturilor ca un proxy pentru similaritatea Jaccard între documentele originale.

În mod special pentru matricea de semnături min-hash:

Cercetați coloanele matricei de semnături M folosind mai multe funcții hash
Dacă 2 documente sunt încadrate în aceeași găleată pentru cel puțin una dintre funcțiile hash, putem considera cele 2 documente ca fiind o pereche candidată

Acum întrebarea este cum să creăm diferite funcții hash. Pentru aceasta, facem o partiție de bandă.

Partiție în bandă

Iată care este algoritmul:

Divizați matricea semnăturii în b benzi, fiecare bandă având r rânduri
Pentru fiecare bandă, se face hash-ul porțiunii sale din fiecare coloană într-un tabel hash cu k găleți
Perechile de coloane candidate sunt cele care fac hash-ul în aceeași găleată pentru cel puțin o bandă
Ajustați b și r pentru a prinde cele mai multe perechi similare, dar puține perechi care nu sunt similare

Există câteva considerații aici. În mod ideal, pentru fiecare bandă, dorim ca k să fie egal cu toate combinațiile posibile de valori pe care le poate lua o coloană în cadrul unei benzi. Acest lucru va fi echivalent cu potrivirea identității. Dar, în acest fel, k va fi un număr imens, ceea ce este imposibil de calculat. De exemplu: Dacă pentru o bandă avem 5 rânduri în ea. Acum, dacă elementele din semnătură sunt numere întregi de 32 de biți, atunci k în acest caz va fi (2³²)⁵ ~ 1,4615016e+48. Puteți vedea care este problema aici. În mod normal, k se ia în jur de 1 milion.

Ideea este că dacă 2 documente sunt similare atunci vor apărea ca pereche de candidați în cel puțin una dintre benzi.

Alegerea lui b & r

Dacă luăm b mare, adică un număr mai mare de funcții hash, atunci reducem r deoarece b*r este o constantă (numărul de rânduri din matricea semnăturilor). În mod intuitiv, aceasta înseamnă că creștem probabilitatea de a găsi o pereche de candidați. Acest caz este echivalent cu luarea unui t mic (prag de similaritate)

Să spunem că matricea de semnături are 100 de rânduri. Luați în considerare 2 cazuri:

b1 = 10 → r = 10

b2 = 20 → r = 5

În al 2-lea caz, există o șansă mai mare ca 2 documente să apară în aceeași găleată cel puțin o dată, deoarece au mai multe oportunități (20 față de 10) și se compară mai puține elemente ale semnăturii (5 față de 10).

Un b mai mare implică un prag de similaritate mai mic (mai multe falsuri pozitive) și un b mai mic implică un prag de similaritate mai mare (mai multe falsuri negative)

Să încercăm să înțelegem acest lucru printr-un exemplu.

Configurare:

100k documente stocate ca semnătură de lungime 100
Matrice de semnături: 100*100000
Compararea prin forță brută a semnăturilor va rezulta în 100C2 comparații = 5 miliarde (destul de mult!)
Să luăm b = 20 → r = 5

semnătatea pragului de similitudine (t) : 80%

Vrem ca 2 documente (D1 & D2) cu o similitudine de 80% să fie hașurate în același bucket pentru cel puțin una din cele 20 de benzi.

P(D1 & D2 identice într-o anumită bandă) = (0.8)⁵ = 0.328

P(D1 & D2 nu sunt similare în toate cele 20 de benzi) = (1-0.328)^20 = 0.00035

Aceasta înseamnă că în acest scenariu avem ~.035% șanse de fals negativ @ 80% documente similare.

De asemenea, dorim ca 2 documente (D3 & D4) cu 30% similaritate să nu fie hașurate în același bucket pentru niciuna dintre cele 20 de benzi (prag = 80%).

P(D3 & D4 identice într-o anumită bandă) = (0.3)⁵ = 0.00243

P(D3 & D4 sunt similare în cel puțin una dintre cele 20 de benzi) = 1 – (1-0.00243)^20 = 0.0474

Acest lucru înseamnă că în acest scenariu avem ~4.74% șanse de a avea un fals pozitiv @ 30% documente similare.

Așa că putem vedea că avem câteva false pozitive și câteva false negative. Aceste proporții vor varia în funcție de alegerea lui b și r.

Ce ne dorim aici este ceva de genul celor de mai jos. Dacă avem 2 documente care au o similaritate mai mare decât pragul, atunci probabilitatea ca ele să împartă aceeași găleată în cel puțin una dintre benzi ar trebui să fie 1, altfel 0.