Ricerca di similitudine, Parte 7 Composizioni LSH

Ricerca similitudine, Parte 7 LSH Composizioni

Immergiti nelle combinazioni di funzioni LSH per garantire una ricerca più affidabile

La ricerca di similarità è un problema in cui, dato un criterio di ricerca, l’obiettivo è trovare i documenti più simili ad esso tra tutti i documenti del database.

Introduzione

Nella scienza dei dati, la ricerca di similarità appare spesso nel dominio del NLP, nei motori di ricerca o nei sistemi di raccomandazione, dove è necessario recuperare i documenti o gli elementi più rilevanti per una determinata query. Esistono diverse modalità per migliorare le prestazioni di ricerca in grandi volumi di dati.

Nelle ultime due parti di questa serie di articoli, abbiamo approfondito LSH, un algoritmo che trasforma vettori di input in valori di hash a dimensioni inferiori, preservando informazioni sulla loro similarità. In particolare, abbiamo già analizzato due algoritmi adatti a diverse metriche di distanza:

• Come costruire un’app Streamlit multi-pagina interconnessa
• Ottimizzare le tue strategie con approcci oltre i test A/B
• 4 Modi Rivoluzionari per Migliorare il Tuo Team di Governance dei Dati

Ricerca di similarità, Parte 5: Locality Sensitive Hashing (LSH)

Esplora come le informazioni di similarità possano essere incorporate in una funzione di hash

towardsdatascience.com

L’algoritmo LSH classico costruisce firme che riflettono le informazioni sul coefficiente di Jaccard dei vettori.

Ricerca di similarità, Parte 6: Proiezioni casuali con LSH Forest

Comprendi come l’hashing dei dati e la riflessione della loro similarità mediante la costruzione di iperpiani casuali

towardsdatascience.com

Il metodo delle proiezioni casuali costruisce una foresta di iperpiani che preservano la similarità del coseno dei vettori.

In realtà, esistono algoritmi LSH per altre metriche di distanza. Anche se ogni metodo ha le sue parti uniche, ci sono molti concetti e formule comuni che compaiono in ognuno di essi. Per facilitare il processo di apprendimento dei nuovi metodi in futuro, ci concentreremo di più sulla teoria e forniremo diverse definizioni e teoremi essenziali che spesso appaiono nella letteratura avanzata su LSH. Alla fine dell’articolo, saremo in grado di costruire schemi LSH più complessi semplicemente combinando quelli di base come mattoncini LEGO.

Come bonus, alla fine daremo uno sguardo a come la distanza euclidea può essere incorporata in LSH.

Nota. Come prerequisito principale, si presume che tu sia già familiare con le parti 5 e 6 di questa serie di articoli. Se non lo sei, è altamente consigliato leggerle prima.

Nota. La distanza del coseno è definita formalmente nell’intervallo [0, 2]. Per semplicità, la mappiamo nell’intervallo [0, 1] in cui 0 e 1 indicano rispettivamente la similarità più bassa e più alta possibile.

Definizione formale di LSH

Dato una metrica di distanza d, H è chiamata una funzione LSH (d₁, d₂, p₁, p₂)-sensibile se per oggetti scelti casualmente x e y, si verificano le seguenti condizioni:

• Se d(x, y) ≤ d₁, allora p(H(x) = H(y)) ≥ p₁, cioè H(x) = H(y) con una probabilità almeno pari a p₁.
• Se d(x, y) ≥ d₂, allora p(H(x) = H(y)) ≤ p₂, cioè H(x) = H(y) con una probabilità al massimo pari a p₂.

Cerchiamo di capire cosa significano queste affermazioni. Quando due vettori sono simili, hanno una distanza ridotta tra di loro. Fondamentalmente, la prima affermazione assicura che la probabilità di hasharli nello stesso bucket sia superiore a una certa soglia. In questo modo, alcuni falsi negativi vengono eliminati: se la distanza tra due vettori è maggiore di d₁, allora la probabilità che vengano hashati nello stesso bucket è sempre inferiore a p₁. In modo inverso, la seconda affermazione controlla i falsi positivi: se due vettori non sono simili e la distanza tra di loro è maggiore di d₂, allora hanno una probabilità massima p₂ di apparire nello stesso bucket.

Dato l’affermazione sopra, di solito desideriamo che le seguenti affermazioni nel sistema siano soddisfatte:

• p₁ dovrebbe essere il più vicino possibile a 1 per ridurre il numero di falsi negativi.
• p₂ dovrebbe essere il più vicino possibile a 0 per ridurre il numero di falsi positivi.
• La differenza tra d₁ e d₂ dovrebbe essere il più bassa possibile per ridurre l’intervallo in cui non possono essere effettuate stime probabilistiche sui dati.

A volte l’affermazione sopra viene introdotta utilizzando il termine di similarità s invece di distanza d:

Dato una metrica di similarità s, H viene chiamato una funzione LSH (s₁, s₂, p₁, p₂)-sensibile se per oggetti scelti casualmente x e y, vengono soddisfatte le seguenti condizioni:

• Se s(x, y) ≥ s₁, allora p(H(x) = H(y)) ≥ p₁, cioè H(x) = H(y) con probabilità almeno p₁.
• Se s(x, y) ≤ s₂, allora p(H(x) = H(y)) ≤ p₂, cioè H(x) = H(y) con probabilità al massimo p₂.

Nota. In questo articolo, verranno utilizzate entrambe le notazioni (d₁, d₂, p₁, p₂) e (s₁, s₂, p₁, p₂). In base alle lettere utilizzate nelle notazioni nel testo, dovrebbe essere chiaro se si intende la distanza d o la similarità s. Per impostazione predefinita, viene utilizzata la notazione (d₁, d₂, p₁, p₂).

Esempio di LSH

Per rendere le cose più chiare, dimostriamo la seguente affermazione:

Se la metrica di distanza s è l’indice di Jaccard, allora H è una funzione LSH (0.6, 0.6, 0.4, 0.4)-sensibile. Fondamentalmente, devono essere dimostrate le affermazioni equivalenti:

• Se d(x, y) ≤ 0.6, allora p(H(x) = H(y)) ≥ 0.4
• Se d(x, y) ≥ 0.6, allora p(H(x) = H(y)) ≤ 0.4

Dalla quinta parte di questa serie di articoli, sappiamo che la probabilità di ottenere valori hash uguali per due vettori binari corrisponde alla similarità di Jaccard. Pertanto, se due vettori sono simili almeno al 40%, è garantito che la probabilità di ottenere valori hash uguali sia anche almeno del 40%. Nel frattempo, una similarità di Jaccard di almeno il 40% corrisponde a un indice di Jaccard al massimo del 60%. Di conseguenza, la prima affermazione è dimostrata. Riflessioni analoghe possono essere fatte per la seconda affermazione.

Questo esempio può essere generalizzato nel teorema:

Teorema. Se d è l’indice di Jaccard, allora H è una famiglia di funzioni LSH (d₁, d₂, 1 — d₁, 1 — d₂).

Allo stesso modo, basandosi sui risultati ottenuti dalla parte 6, è possibile dimostrare un altro teorema:

Teorema. Se s è la similarità del coseno (tra -1 e 1), allora H è una famiglia (s₁, s₂, 1 — arccos(s₁) / 180, 1 — arccos(d₂) / 180) di funzioni LSH.

Combina le funzioni LSH

Facciamo riferimento a concetti utili che abbiamo imparato nelle parti precedenti sugli LSH:

• Tornando alla parte 5 sul minhashing, ogni vettore è stato diviso in diverse bande, ognuna contenente un insieme di righe. Perché una coppia di vettori venga considerata candidata, deve esistere almeno una banda in cui tutte le righe dei vettori siano uguali.
• Riguardo alla parte 6 sulle proiezioni casuali, due vettori vengono considerati candidati solo se esiste almeno un albero in cui tutte le proiezioni casuali non separano i vettori iniziali.

Come possiamo notare, questi due approcci hanno un paradigma simile sotto il cofano. Entrambi considerano una coppia di vettori come candidati solo se almeno una volta su n configurazioni i vettori hanno gli stessi valori di hash tutte le k volte. Con la notazione dell’algebra booleana, si può scrivere così:

Basandosi su questo esempio, introduciamo gli operatori logici OR e AND che consentono di aggregare un insieme di funzioni di hash. Successivamente valuteremo come influiscono sulla probabilità di due vettori di essere candidati e sul tasso di falsi negativi e falsi positivi.

Operatore AND

Dato n funzioni LSH indipendenti H₁, H₂, … Hₙ, l’operatore AND considera due vettori come una coppia candidata solo se tutti i n valori di hash corrispondenti di entrambi i vettori sono uguali. Altrimenti, i vettori non vengono considerati come candidati.

Se i valori di hash di due vettori molto diversi vengono aggregati dall’operatore AND, la probabilità che siano candidati diminuisce all’aumentare del numero di funzioni di hash utilizzate. Di conseguenza, il numero di falsi positivi diminuisce.

Allo stesso tempo, due vettori simili possono casualmente risultare in una coppia di valori di hash diversi. A causa di ciò, tali vettori non saranno considerati simili dall’algoritmo. Questo aspetto comporta un tasso più elevato di falsi negativi.

Teorema. Considera r funzioni LSH indipendenti (s₁, s₂, p₁, p₂)-sensibili. Combinando queste r funzioni LSH con l’operatore AND si ottiene una nuova funzione LSH con i parametri come

È facile dimostrare questa affermazione utilizzando la formula di probabilità di diversi eventi indipendenti che moltiplica le probabilità di tutti gli eventi per stimare la probabilità che tutti gli eventi si verifichino.

Operatore OR

Dato n funzioni LSH indipendenti H₁, H₂, … Hₙ, l’operatore OR considera due vettori come una coppia candidata solo se almeno uno dei n valori di hash corrispondenti di entrambi i vettori è uguale. Altrimenti, i vettori non vengono considerati come candidati.

Inversamente all’operatore AND, l’operatore OR aumenta la probabilità che due vettori qualsiasi siano candidati. Per qualsiasi coppia di vettori, è sufficiente almeno una singola uguaglianza dei valori di hash corrispondenti. Per questo motivo, l’aggregazione OR riduce il numero di falsi negativi e aumenta i falsi positivi.

Teorema. Considera b funzioni LSH indipendenti (d₁, d₂, p₁, p₂)-family. Combinando queste b funzioni LSH con l’operatore AND si ottiene una nuova funzione LSH con i parametri come

Non dimostreremo questo teorema perché la formula di probabilità analoghe ottenuta e spiegata nella parte 5 di questa serie di articoli.

Composizione

Utilizzando le operazioni AND e OR, è possibile combinarle in vari modi per controllare meglio i tassi di falsi positivi e falsi negativi. Immaginiamo di avere r funzioni LSH utilizzate dal combinatore AND e b funzioni LSH utilizzate dal combinatore OR. È possibile costruire due diverse composizioni utilizzando questi combinatori di base:

Gli algoritmi descritti nei due articoli precedenti utilizzano la composizione AND-OR. Infatti, nulla ci impedisce di costruire composizioni più complesse basate sulle operazioni AND e OR.

Esempio di composizione

Studiamo un esempio per capire come le combinazioni di AND e OR possono migliorare significativamente le prestazioni. Supponiamo una combinazione OR-AND con parametri b = 4 e r = 8. Basandoci sulla formula corrispondente sopra, possiamo stimare come la probabilità iniziale che due vettori siano candidati si trasforma dopo la composizione:

Ad esempio, se per un certo valore di similarità tra due vettori, una singola funzione LSH li hasha nello stesso bucket nel 40% dei casi, allora dopo la composizione OR-AND saranno hashati nel 32,9% dei casi.

Per capire cosa c’è di così speciale nelle composizioni, consideriamo una funzione LSH (0,4, 1,7, 0,8, 0,2)-sensibile. Dopo la trasformazione OR-AND, la funzione LSH si trasforma nel formato (0,4, 1,7, 0,0148, 0,987)-sensibile.

In sostanza, se inizialmente due vettori erano molto simili e avevano una distanza inferiore a 0,4, allora sarebbero stati considerati candidati nell’80% dei casi. Tuttavia, con la composizione applicata, ora sono candidati nel 98,7% degli scenari, riducendo notevolmente gli errori di falsi negativi!

Analogamente, se due vettori sono molto diversi tra loro e hanno una distanza maggiore di 1,7, allora ora vengono considerati candidati solo nel 1,48% dei casi (rispetto al 20% prima). In questo modo, la frequenza degli errori di falsi positivi viene ridotta di 13,5 volte! Questo è un miglioramento enorme!

In generale, avendo una funzione LSH (d₁, d₂, p₁, p₂)-sensibile, è possibile trasformarla in un formato (d₁, d₂, p’₁, p’₂) dove p’₁ è vicino a 1 e p’₂ è vicino a 0. Avvicinarsi sempre di più a 1 e 0 di solito richiede l’uso di più composizioni.

LSH per altre metriche di distanza

Abbiamo già studiato a fondo gli schemi LSH utilizzati per preservare informazioni sull’indice di Jaccard e sulla distanza del coseno. La domanda naturale che sorge è se è possibile utilizzare LSH per altre metriche di distanza. Purtroppo, per la maggior parte delle metriche, non esiste un algoritmo LSH corrispondente.

Tuttavia, esiste uno schema LSH per la distanza euclidea, una delle metriche più comunemente utilizzate nell’apprendimento automatico. Poiché viene utilizzata frequentemente, studieremo come ottenere valori di hash per la distanza euclidea. Con le notazioni teoriche introdotte in precedenza, dimostreremo una proprietà LSH importante per questa metrica.

LSH per la distanza euclidea

Il meccanismo di hashing dei punti nello spazio euclideo include la loro proiezione su una linea casuale. L’algoritmo assume che

• Se due punti sono relativamente vicini tra loro, allora le loro proiezioni dovrebbero essere anche vicine.
• Se due punti sono lontani tra loro, allora le loro proiezioni dovrebbero essere anche lontane.

Per misurare quanto sono vicine due proiezioni, una linea può essere divisa in diversi segmenti uguali (bucket) di dimensione a ciascuno. Ogni segmento corrisponde a un certo valore hash. Se due punti si proiettano sullo stesso segmento di linea, allora hanno lo stesso valore hash. Altrimenti, i valori hash sono diversi.

Nonostante il metodo possa sembrare robusto a prima vista, può ancora proiettare punti che sono lontani tra loro nello stesso segmento. Ciò accade soprattutto quando una linea che collega due punti è quasi perpendicolare alla linea di proiezione iniziale.

Per ridurre il tasso di errore, è altamente consigliato utilizzare composizioni di linee di proiezione casuali, come discusso in precedenza.

È geometricamente possibile dimostrare che se a è la lunghezza di un singolo segmento di linea nello spazio euclideo, allora H è una funzione LSH (a / 2, 2a, ½, ⅓)-sensibile.

Conclusioni

In questo capitolo, abbiamo accumulato conoscenze sulla notazione generale LSH che ci ha aiutato a introdurre formalmente le operazioni di composizione, consentendoci di ridurre significativamente i tassi di errore. Vale la pena notare che LSH esiste solo per una piccola parte delle metriche di machine learning, ma almeno per quelle più popolari, come la distanza euclidea, la distanza coseno e l’indice di Jaccard. Quando si lavora con un’altra metrica per la misura della similarità tra vettori, è consigliabile scegliere un altro approccio di ricerca della similarità.

Per riferimento, le dimostrazioni formali delle affermazioni introdotte in questo articolo possono essere trovate in queste note.

Risorse

• Locality Sensitive Hashing | Appunti di lezione per l’analisi di Big Data | Nimrah Mustafa
• Distanza coseno | Wikipedia

Tutte le immagini, salvo diversa indicazione, sono dell’autore.