Locality-sensitive hashing

A questa voce o sezione va aggiunto il template sinottico {{Algoritmo}}

Puoi aggiungere e riempire il template secondo le istruzioni e poi rimuovere questo avviso. Se non sei in grado di riempirlo in buona parte, non fare nulla; non inserire template vuoti.

Il locality-sensitive hashing (LSH)^[1][2] è un metodo per la riduzione della dimensionalità dello spazio vettoriale di un insieme di dati.

La grossa mole di dati da elaborare, principalmente il calcolo della distanza fra gli oggetti (item) di un insieme di dati, è un grosso vincolo allo sviluppo di applicazioni sistema real-time per soddisfare interrogazioni quali la similarità fra (parti di) immagini o (estratti di) brani musicali.

L'idea principale è applicare una funzione hash agli item in input in modo da far collidere, con alta probabilità, item simili negli stessi contenitori (bucket). Il numero di bucket è molto più ridotto dell'universo dei possibili item in input. L'obiettivo è di arrivare ad un hashing a due livelli:

• la funzione LSH mappa un item ${\displaystyle p}$ in un bucket ${\displaystyle g_{j}(p)}$;
• una funzione hash standard mappa il contenuto di questi bucket in una hash table di lunghezza ${\displaystyle M.}$

La dimensione massima del bucket della seconda hash table verrà chiamato ${\displaystyle B.}$

Con il metodo LSH si vuole fare in modo di correlare la distanza di due punti ${\displaystyle p}$ e ${\displaystyle q}$ alla probabilità di collisione in un bucket. Maggiore è la distanza fra i punti minore sarà la loro probabilità di collisione.

• ${\displaystyle D(\cdot ,\cdot )}$ è la funzione di distanza fra elementi di un insieme ${\displaystyle S}$;
• ${\displaystyle B(p,r)}$ indica, per ogni punto ${\displaystyle p\in S}$, l'insieme di elementi di ${\displaystyle S}$ che stanno all'interno della distanza ${\displaystyle r}$ da ${\displaystyle p}$.

Consideriamo una funzione hash ${\displaystyle h}$ scelta a caso dalla famiglia LSH di funzioni hash disponibili ${\displaystyle {\mathcal {H}}}$. Una famiglia LSH ${\displaystyle {\mathcal {H}}}$ di funzioni dall'insieme ${\displaystyle S}$ all'insieme ${\displaystyle U}$ è detta ${\displaystyle (r_{1},r_{2},p_{1},p_{2})}$-sensitive per ${\displaystyle D(\cdot ,\cdot )}$ se per ogni coppia di punti ${\displaystyle q}$ (che è la rappresentazione dell'interrogazione) e ${\displaystyle p}$ (che è il punto che soddisfa le condizioni sotto riportate) appartenenti all'insieme ${\displaystyle S}$:

• se ${\displaystyle p\in B(q,r_{1})}$ allora ${\displaystyle \mathrm {Pr} _{\mathcal {H}}[h(q)=h(p)]\geq p_{1};}$
• se ${\displaystyle p\notin B(q,r_{2})}$ allora ${\displaystyle \mathrm {Pr} _{\mathcal {H}}[h(q)=h(p)]\leq p_{2}.}$

Affinché la famiglia LSH sia utile per gli scopi che ci si è prefissi devono valere le due condizioni:

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

Di solito si considera ${\displaystyle r_{2}=cr_{1},}$ con ${\displaystyle c>1}$.

In uno spazio a due dimensioni si hanno due cerchi concentrici centrati sulla rappresentazione dell'interrogazione ${\displaystyle q}$. Ricordando che ${\displaystyle B(q,r_{1})}$ e ${\displaystyle B(q,r_{2})}$ rappresentano dei sottoinsiemi dell'insieme di dati ${\displaystyle S}$:

• Il cerchio più interno di raggio ${\displaystyle r_{1}}$ contiene i punti ${\displaystyle p}$ dell'insieme di dati ${\displaystyle B(q,r_{1})}$ che hanno, come precedentemente descritto, una probabilità maggiore della soglia ${\displaystyle p_{1}}$ di subire un hash nello stesso bucket.

• Il cerchio più esterno di raggio ${\displaystyle r_{2}}$ esclude i punti ${\displaystyle p}$ dell'insieme di dati ${\displaystyle B(q,r_{2})}$ che hanno, come precedentemente descritto, una probabilità minore della soglia ${\displaystyle p_{2}}$ di subire un hash nello stesso bucket.

La funzione hash^[3] ${\displaystyle h_{\mathbf {a} ,b}\colon \mathbb {R} ^{d}\to \mathbb {N} }$ manda un vettore di ${\displaystyle d}$ componenti reali ${\displaystyle \mathbf {v} }$ in un intero non negativo. Ogni funzione hash appartenente alla famiglia viene selezionata scegliendo in modo casuale ${\displaystyle \mathbf {a} }$ e ${\displaystyle b}$ dove ${\displaystyle \mathbf {a} }$ è un vettore di ${\displaystyle d}$ componenti reali i cui elementi sono scelti in maniera indipendente da una distribuzione stabile e ${\displaystyle b}$ è un numero reale scelto secondo una distribuzione continua uniforme nell'intervallo ${\displaystyle [0,r].}$ Fissati ${\displaystyle \mathbf {a} ,b}$ e la funzione hash ${\displaystyle h_{\mathbf {a} ,b}}$ si calcola attraverso la relazione ${\displaystyle h_{\mathbf {a} ,b}(\mathbf {v} )=\left\lfloor {\frac {\mathbf {a} \cdot \mathbf {v} +b}{r}}\right\rfloor ,}$ dove ${\displaystyle \mathbf {a} \cdot \mathbf {v} }$ indica il prodotto scalare euclideo tra ${\displaystyle \mathbf {a} }$ e ${\displaystyle \mathbf {v} }$ e ${\displaystyle \lfloor \cdot \rfloor }$ indica la funzione parte intera.

Una delle principali applicazioni di LSH è quella di fornire un algoritmo efficiente per il problema della ricerca del nearest neighbor. Data una qualsiasi famiglia LSH ${\displaystyle {\mathcal {F}}}$ l'algoritmo ha due parametri principali:

• la larghezza ${\displaystyle k}$;
• il numero di tabelle di hash ${\displaystyle L}$.

Cominciamo definendo una nuova famiglia ${\displaystyle {\mathcal {G}}}$ di funzioni hash ${\displaystyle g}$, in cui ogni funzione ${\displaystyle g}$ si ottiene concatenando ${\displaystyle k}$ funzioni ${\displaystyle h_{1},\ldots ,h_{k}}$ da ${\displaystyle {\mathcal {F}}}$, cioè

${\displaystyle g(p)={\big (}h_{1}(p),\ldots ,h_{k}(p){\big )}.}$

La scelta di concatenare ${\displaystyle k}$ funzioni hash per ottenere ${\displaystyle g}$ è giustificata dal fatto che si vuole amplificare la differenza tra la alta probabilità ${\displaystyle p_{1}}$ e la bassa probabilità ${\displaystyle p_{2}}$.

In altre parole, una funzione hash ${\displaystyle g}$ presa casualmente da ${\displaystyle {\mathcal {G}}}$ si ottiene concatenando ${\displaystyle k}$ funzioni hash prese casualmente da ${\displaystyle {\mathcal {H}}}$.

Successivamente l'algoritmo costruisce ${\displaystyle L}$ tabelle di hash, ognuna corrispondente a una diversa funzione hash ${\displaystyle g}$.

Nella fase di preprocessing si fa un hash di tutti gli ${\displaystyle n}$ punti dell'insieme di dati ${\displaystyle S}$ in ognuna delle ${\displaystyle L}$ tabelle di hash. Dato che le tabelle di hash risultanti hanno solo ${\displaystyle n}$ elementi diversi da zero, si può ridurre l'utilizzo di memoria per ogni funzione hash a ${\displaystyle O(n)}$ usando funzioni hash standard.

Considerando l'interrogazione ${\displaystyle q}$ al sistema così creato, l'algoritmo itera sulle ${\displaystyle L}$ funzioni hash ${\displaystyle g}$. Per ogni ${\displaystyle g}$, reperisce i punti dell'insieme di dati che sono stati mappati dall'hash nello stesso bucket in cui è stata mappata ${\displaystyle q}$. Il processo si conclude quando viene reperito un punto di distanza ${\displaystyle cR}$ da ${\displaystyle q}$.

• K-nearest neighbors