Hashing sensibil la localitate

Hash-ul sensibil la localitate ( LSH ) ^[1] ^[2] este o metodă de reducere a dimensionalității spațiului vectorial al unui set de date.

Motive

Cantitatea mare de date care urmează să fie procesate, în principal calculul distanței dintre obiectele ( elementele ) unui set de date , este o constrângere majoră la dezvoltarea de aplicații de sistem în timp real pentru a satisface întrebări precum similaritatea dintre (părți din ) imagini sau (extrase din) muzică.

Ideea principală este de a aplica o funcție pentru hash articolelor din intrare astfel încât să se ciocnească, cu probabilitate mare, articole similare în aceleași containere (cupă). Numărul de găleți este mult mai mic decât universul posibilelor elemente de intrare. Scopul este de a ajunge la un hashing pe două niveluri:

funcția LSH mapează un element $p$ ${\ displaystyle p}$ $p$ într-o găleată $g_{j}(p)$ ${\ displaystyle g_ {j} (p)}$ ${\ displaystyle g_ {j} (p)}$ ;
o funcție hash standard mapează conținutul acestor găleți într-un tabel hash de lungime M.

Dimensiunea maximă a cupei a doua tabelă hash va fi numită B.

Recrutări

Cu metoda LSH vrem să ne asigurăm că corelăm distanța a două puncte $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ probabilitatea coliziunii într-o găleată. Cu cât distanța dintre puncte este mai mare, cu atât probabilitatea lor de coliziune este mai mică.

Definiție

$D(.,.)$ ${\ displaystyle D (.,.)}$ ${\ displaystyle D (.,.)}$ este funcția de distanță între elementele unui set $S.$ ${\ displaystyle S}$ $S.$ ;
$B(p,r)$ ${\ displaystyle B (p, r)}$ ${\ displaystyle B (p, r)}$ indică, pentru fiecare punct $p\in S$ ${\ displaystyle p \ în S}$ $p \ în S$ , ansamblul elementelor din $S.$ ${\ displaystyle S}$ $S.$ care stau la distanță $r$ ${\ displaystyle r}$ $r$ din $p$ ${\ displaystyle p}$ $p$ .

Să luăm în considerare o funcție hash $h$ ${\ displaystyle h}$ $h$ aleasă aleatoriu din familia LSH de funcții hash disponibile ${\mathcal {H}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ mathcal H}$ . O familie LSH ${\mathcal {H}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ mathcal H}$ de funcții din set $S.$ ${\ displaystyle S}$ $S.$ la întreg $U$ ${\ displaystyle U}$ $U$ se spune $(r_{1},r_{2},p_{1},p_{2})$ ${\ displaystyle (r_ {1}, r_ {2}, p_ {1}, p_ {2})}$ ${\ displaystyle (r_ {1}, r_ {2}, p_ {1}, p_ {2})}$ -sensibil pentru $D(.,.)$ ${\ displaystyle D (.,.)}$ ${\ displaystyle D (.,.)}$ dacă pentru fiecare pereche de puncte $q$ ${\ displaystyle q}$ $q$ (care este reprezentarea interogării) e $p$ ${\ displaystyle p}$ $p$ (care este punctul care îndeplinește condițiile de mai jos) aparținând mulțimii $S.$ ${\ displaystyle S}$ $S.$ :

de sine $p\in B(q,r_{1})$ ${\ displaystyle p \ în B (q, r_ {1})}$ ${\ displaystyle p \ în B (q, r_ {1})}$ asa de $Pr_{\mathcal {H}}[h(q)=h(p)]\geq p_{1}$ ${\ displaystyle Pr _ {\ mathcal {H}} [h (q) = h (p)] \ geq p_ {1}}$ ${\ displaystyle Pr _ {\ mathcal {H}} [h (q) = h (p)] \ geq p_ {1}}$
de sine $p\notin B(q,r_{2})$ ${\ displaystyle p \ notin B (q, r_ {2})}$ ${\ displaystyle p \ notin B (q, r_ {2})}$ asa de $Pr_{\mathcal {H}}[h(q)=h(p)]\leq p_{2}$ ${\ displaystyle Pr _ {\ mathcal {H}} [h (q) = h (p)] \ leq p_ {2}}$ ${\ displaystyle Pr _ {\ mathcal {H}} [h (q) = h (p)] \ leq p_ {2}}$

Pentru ca familia LSH să fie utilă în scopurile pe care și le-a stabilit, trebuie îndeplinite cele două condiții:

$p_{1}>p_{2}$ ${\ displaystyle p_ {1}> p_ {2}}$ ${\ displaystyle p_ {1}> p_ {2}}$ ;
$r_{1}<r_{2}$ ${\ displaystyle r_ {1} <r_ {2}}$ ${\ displaystyle r_ {1} <r_ {2}}$ .

De obicei se ia în considerare $r_{2}=c\cdot r_{1}$ ${\ displaystyle r_ {2} = c \ cdot r_ {1}}$ ${\ displaystyle r_ {2} = c \ cdot r_ {1}}$ cu $c>1$ ${\ displaystyle c> 1}$ ${\ displaystyle c> 1}$ .

Interpretare grafică

Într-un spațiu bidimensional există două cercuri concentrice centrate pe reprezentarea interogării $q$ ${\ displaystyle q}$ $q$ . Amintindu-mi asta $B(q,r_{1})$ ${\ displaystyle B (q, r_ {1})}$ ${\ displaystyle B (q, r_ {1})}$ Și $B(q,r_{2})$ ${\ displaystyle B (q, r_ {2})}$ ${\ displaystyle B (q, r_ {2})}$ reprezintă subseturi ale setului de date $S.$ ${\ displaystyle S}$ $S.$ :

Cercul interior al razei $r_{1}$ ${\ displaystyle r_ {1}}$ $r_1$ conține punctele $p$ ${\ displaystyle p}$ $p$ a setului de date $B(q,r_{1})$ ${\ displaystyle B (q, r_ {1})}$ ${\ displaystyle B (q, r_ {1})}$ care au, după cum s-a descris anterior, o probabilitate mai mare decât pragul $p_{1}$ ${\ displaystyle p_ {1}}$ $p_ {1}$ să fie hash în aceeași găleată.

Cercul exterior al razei $r_{2}$ ${\ displaystyle r_ {2}}$ $r_2$ exclude puncte $p$ ${\ displaystyle p}$ $p$ a setului de date $B(q,r_{2})$ ${\ displaystyle B (q, r_ {2})}$ ${\ displaystyle B (q, r_ {2})}$ care au, după cum s-a descris anterior, o probabilitate mai mică decât pragul $p_{2}$ ${\ displaystyle p_ {2}}$ $p_ {2}$ să fie hash în aceeași găleată.

LSH și distribuții stabile

Funcția hash ^[3] $h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}$ ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}): {\ mathcal {R}} ^ {d} \ to {\ mathcal {N}}}$ ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}): {\ mathcal {R}} ^ {d} \ to {\ mathcal {N}}}$ mapează un vector cu d dimensiuni ${\boldsymbol {\upsilon }}$ ${\ displaystyle {\ boldsymbol {\ upsilon}}}$ ${\ displaystyle {\ boldsymbol {\ upsilon}}}$ într-un set de numere întregi. Fiecare funcție hash aparținând familiei este selectată prin alegerea aleatorie $\mathbf {a}$ ${\ displaystyle \ mathbf {a}}$ $\ mathbf {a}$ Și $b$ ${\ displaystyle b}$ $b$ unde este $\mathbf {a}$ ${\ displaystyle \ mathbf {a}}$ $\ mathbf {a}$ este un vector cu dimensiuni d ale cărui componente sunt alese independent de o distribuție stabilă e $b$ ${\ displaystyle b}$ $b$ este un număr real ales uniform în intervalul [0, r]. Reparați-vă $\mathbf {a} ,b$ ${\ displaystyle \ mathbf {a}, b}$ ${\ displaystyle \ mathbf {a}, b}$ funcția hash $h_{\mathbf {a} ,b}$ ${\ displaystyle h _ {\ mathbf {a}, b}}$ ${\ displaystyle h _ {\ mathbf {a}, b}}$ se calculează prin relație $h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor$ ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}) = \ left \ lfloor {\ frac {\ mathbf {a} \ cdot {\ boldsymbol {\ upsilon}} + b } {r}} \ right \ rfloor}$ ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}) = \ left \ lfloor {\ frac {\ mathbf {a} \ cdot {\ boldsymbol {\ upsilon}} + b } {r}} \ right \ rfloor}$ .

Căutați vecinii cei mai apropiați

Una dintre principalele aplicații ale LSH este de a oferi un algoritm eficient pentru cea mai apropiată problemă de căutare a vecinilor . Având în vedere orice familie LSH ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ algoritmul are doi parametri principali:

lațimea $k$ ${\ displaystyle k}$ $k$ ;
numărul de tabele hash $L$ ${\ displaystyle L}$ $L$ .

Să începem prin a defini o nouă familie ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ $\ mathcal G$ a funcțiilor hash $g$ ${\ displaystyle g}$ $g$ , unde fiecare funcție $g$ ${\ displaystyle g}$ $g$ se obține prin concatenare $k$ ${\ displaystyle k}$ $k$ funcții $h_{1},...,h_{k}$ ${\ displaystyle h_ {1}, ..., h_ {k}}$ ${\ displaystyle h_ {1}, ..., h_ {k}}$ din ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ , adică

$g(p)=[h_{1}(p),...,h_{k}(p)]$ ${\ displaystyle g (p) = [h_ {1} (p), ..., h_ {k} (p)]}$ ${\ displaystyle g (p) = [h_ {1} (p), ..., h_ {k} (p)]}$

Alegerea concatenării $k$ ${\ displaystyle k}$ $k$ funcții hash pentru a obține $g$ ${\ displaystyle g}$ $g$ se justifică prin faptul că vrem să amplificăm diferența dintre probabilitatea mare $p_{1}$ ${\ displaystyle p_ {1}}$ $p_ {1}$ și probabilitatea redusă $p_{2}$ ${\ displaystyle p_ {2}}$ $p_ {2}$ .

Cu alte cuvinte, o funcție hash $g$ ${\ displaystyle g}$ $g$ luată la întâmplare din ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ $\ mathcal G$ se obține prin concatenare $k$ ${\ displaystyle k}$ $k$ funcții hash luate la întâmplare de la ${\mathcal {H}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ mathcal H}$ .

Ulterior algoritmul se construiește $L$ ${\ displaystyle L}$ $L$ tabele hash, fiecare corespunzând unei funcții hash diferite $g$ ${\ displaystyle g}$ $g$ .

În faza de preprocesare facem un hash din toate $n$ ${\ displaystyle n}$ $n$ punctele setului de date $S.$ ${\ displaystyle S}$ $S.$ în fiecare dintre $L$ ${\ displaystyle L}$ $L$ mese de hash. Deoarece tabelele hash rezultate au numai $n$ ${\ displaystyle n}$ $n$ intrări diferite de zero, puteți reduce utilizarea memoriei pentru fiecare funcție hash la $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ folosind funcții hash standard.

Având în vedere întrebarea $q$ ${\ displaystyle q}$ $q$ (interogare) către sistemul astfel creat, algoritmul iterează peste $L$ ${\ displaystyle L}$ $L$ funcții hash $g$ ${\ displaystyle g}$ $g$ . Pentru fiecare $g$ ${\ displaystyle g}$ $g$ , recuperează punctele setate de date care au fost mapate din hash în același compartiment în care a fost mapat $q$ ${\ displaystyle q}$ $q$ . Procesul se termină atunci când se găsește un punct de distanță $c R.$ ${\ displaystyle cR}$ ${\ displaystyle cR}$ din $q$ ${\ displaystyle q}$ $q$ .

Notă

^ Gionis, A., Indyk, P. , Motwani, R. , Similarity Search in High Dimensions via Hashing ( ps ), în Proceedings of the 25th Very Large Database (VLDB) Conference , 1999.
^ Piotr Indyk , Rajeev Motwani , Vecinii cei mai apropiați aproximativi: spre îndepărtarea blestemului dimensiunii. ( ps ), în Proceedings of 30th Symposium on Theory of Computing , 1998.
^ Datar, M., Immorlica, N., Indyk, P. , Mirrokni, VS, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions ( ps ), în Proceedings of the Symposium on Computational Geometry , 2004.

Elemente conexe

[GIM1999-1] Gionis, A., Indyk, P. , Motwani, R. , Similarity Search in High Dimensions via Hashing ( ps ), în Proceedings of the 25th Very Large Database (VLDB) Conference , 1999.

[IndykMotwani98-2] Piotr Indyk , Rajeev Motwani , Vecinii cei mai apropiați aproximativi: spre îndepărtarea blestemului dimensiunii. ( ps ), în Proceedings of 30th Symposium on Theory of Computing , 1998.

[DIIM04-3] Datar, M., Immorlica, N., Indyk, P. , Mirrokni, VS, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions ( ps ), în Proceedings of the Symposium on Computational Geometry , 2004.

[1]

[2]

[3]