Ricerca di similarità, Parte 4 Hierarchical Navigable Small World (HNSW)

Hierarchical Navigable Small World (HNSW) for Similarity Search, Part 4.

Scopri come costruire grafi multi-strato efficienti per aumentare la velocità di ricerca in masse di dati

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

Introduzione

Nella scienza dei dati, la ricerca di similarità appare spesso nel dominio NLP, nei motori di ricerca o nei sistemi di raccomandazione in cui devono essere recuperati i documenti o gli elementi più rilevanti per un’interrogazione. Esiste una grande varietà di modi diversi per migliorare le prestazioni di ricerca in masse di dati.

Hierarchical Navigable Small World (HNSW) è un algoritmo all’avanguardia utilizzato per una ricerca approssimata dei vicini più vicini. Sotto il cofano, HNSW costruisce strutture di grafo ottimizzate, rendendolo molto diverso da altri approcci che sono stati discussi nelle parti precedenti di questa serie di articoli.

L’idea principale di HNSW è quella di costruire un tale grafo in cui un percorso tra qualsiasi coppia di vertici possa essere attraversato in un piccolo numero di passi.

Un’analoga ben nota sulla famosa regola dei sei gradi di separazione è legata a questo metodo:

Tutte le persone sono a sei o meno connessioni sociali l’una dall’altra.

Prima di procedere alle operazioni interne di HNSW, discutiamo prima di skip list e navigable small words, strutture di dati cruciali utilizzate all’interno dell’implementazione HNSW.

Skip list

La skip list è una struttura dati probabilistica che consente di inserire e cercare elementi all’interno di una lista ordinata per O(logn) in media. Una skip list è costruita da diversi livelli di liste collegate. Il livello più basso ha la lista collegata originale con tutti gli elementi al suo interno. Passando ai livelli superiori, il numero di elementi saltati aumenta, diminuendo così il numero di connessioni.

Trovare l'elemento 20 nella skip list

La procedura di ricerca per un certo valore inizia dal livello più alto e confronta il suo elemento successivo con il valore. Se il valore è minore o uguale all’elemento, quindi l’algoritmo procede al suo elemento successivo. In caso contrario, la procedura di ricerca scende al livello inferiore con più connessioni e ripete lo stesso processo. Alla fine, l’algoritmo scende al livello più basso e trova il nodo desiderato.

In base alle informazioni da Wikipedia, una skip list ha il parametro principale p che definisce la probabilità di un elemento che appare in diverse liste. Se un elemento appare nel livello i, la probabilità che appaia nel livello i + 1 è uguale a p (p di solito è impostato su 0,5 o 0,25). In media, ogni elemento è presentato in 1 / (1 – p) liste.

Come possiamo vedere, questo processo è molto più veloce della normale ricerca lineare nella lista collegata. Infatti, HNSW eredita la stessa idea ma invece di liste collegate, utilizza grafi.

Navigable small world è un grafo con complessità di ricerca polilogaritmica T = O(logᵏn) che utilizza il routing avido. Il routing si riferisce al processo di avviare il processo di ricerca da vertici a basso grado e terminare con vertici ad alto grado. Poiché i vertici a basso grado hanno pochissime connessioni, l’algoritmo può spostarsi rapidamente tra di essi per navigare efficientemente nella regione in cui è probabile che si trovi il vicino più vicino. Quindi l’algoritmo si ingrandisce gradualmente e passa a vertici ad alto grado per trovare il vicino più vicino tra i vertici in quella regione.

Il vertice viene talvolta anche indicato come un nodo.

Ricerca

In primo luogo, la ricerca viene effettuata scegliendo un punto di ingresso. Per determinare il prossimo vertice (o vertici) a cui l’algoritmo fa un passo, calcola le distanze dal vettore di interrogazione ai vicini del vertice corrente e si sposta verso il più vicino. Ad un certo punto, l’algoritmo termina la procedura di ricerca quando non riesce a trovare un nodo vicino che sia più vicino alla query rispetto al nodo corrente stesso. Questo nodo viene restituito come risposta all’interrogazione.

Processo di ricerca avida in un piccolo mondo navigabile. Il nodo A viene utilizzato come punto di ingresso. Ha due vicini B e D. Il nodo D è più vicino alla query di B. Di conseguenza, ci spostiamo su D. Il nodo D ha tre vicini C, E e F. E è il vicino più vicino alla query, quindi ci spostiamo su E. Infine, il processo di ricerca condurrà al nodo L. Poiché tutti i vicini di L si trovano più lontani dalla query rispetto a L stesso, interrompiamo l'algoritmo e restituiamo L come risposta alla query.

Questa strategia avida non garantisce di trovare il vicino più vicino esatto poiché il metodo utilizza solo informazioni locali al passo corrente per prendere decisioni. Uno dei problemi dell’algoritmo è la fermata anticipata. Si verifica soprattutto all’inizio della procedura di ricerca quando non ci sono nodi vicini migliori di quello corrente. Per la maggior parte, questo potrebbe accadere quando la regione di avvio ha troppi vertici a basso grado.

Fermata anticipata. Entrambi i vicini del nodo corrente sono più lontani dalla query. Pertanto, l'algoritmo restituisce il nodo corrente come risposta, anche se esistono nodi molto più vicini alla query.

La precisione della ricerca può essere migliorata utilizzando diversi punti di ingresso.

Costruzione

Il grafo NSW viene costruito mescolando i punti del dataset e inserendoli uno per volta nel grafo corrente. Quando viene inserito un nuovo nodo, viene poi collegato da bordi ai M vertici più vicini ad esso.

Inserimento sequenziale di nodi (da sinistra a destra) con M = 2. Ad ogni iterazione, un nuovo vertice viene aggiunto al grafo e collegato ai suoi M = 2 vicini più vicini. Le linee blu rappresentano i bordi connessi a un nodo appena inserito.

Nella maggior parte degli scenari, i bordi a lungo raggio saranno probabilmente creati nella fase iniziale della costruzione del grafo. Giocano un ruolo importante nella navigazione del grafo.

I collegamenti ai vicini più vicini degli elementi inseriti all’inizio della costruzione diventano in seguito ponti tra gli hub della rete che mantengono la connettività complessiva del grafo e consentono la scalabilità logaritmica del numero di hop durante il routing avido. — Yu. A. Malkov, D. A. Yashunin

Dall’esempio nella figura sopra, possiamo vedere l’importanza del bordo a lungo raggio AB che è stato aggiunto all’inizio. Immagina una query che richiede il percorso attraverso nodi relativamente distanti come A e I. Avere il bordo AB consente di farlo rapidamente navigando direttamente da un lato del grafo all’altro.

All’aumentare del numero di vertici nel grafo, aumenta la probabilità che le lunghezze dei bordi appena collegati a un nuovo nodo saranno più piccole.

HNSW

HNSW si basa sugli stessi principi delle skip list e del piccolo mondo navigabile. La sua struttura rappresenta un grafo a più strati con meno connessioni sui livelli superiori e regioni più dense sui livelli inferiori.

Ricerca

La ricerca inizia dal livello più alto e procede a un livello inferiore ogni volta che viene trovato localmente il vicino più vicino tra i nodi del livello. In definitiva, il vicino più vicino trovato sul livello più basso è la risposta alla query.

Ricerca in HNSW

Come per NSW, la qualità della ricerca di HNSW può essere migliorata utilizzando diversi punti di ingresso. Invece di trovare solo un vicino più vicino su ogni livello, vengono trovati i efSearch (un iperparametro) vicini più vicini al vettore di query e ciascuno di questi vicini viene utilizzato come punto di ingresso nel livello successivo.

Complessità

Gli autori dell’articolo originale sostengono che il numero di operazioni necessarie per trovare il vicino più vicino su qualsiasi livello sia limitato da una costante. Considerando che il numero di tutti i livelli in un grafo è logaritmico, si ottiene la complessità di ricerca totale che è O(logn).

Costruzione

Scelta del livello massimo

I nodi in HNSW vengono inseriti sequenzialmente uno per uno. Ogni nodo viene assegnato casualmente un intero l che indica il livello massimo in cui questo nodo può essere presente nel grafo. Ad esempio, se l = 1, il nodo può essere trovato solo sui livelli 0 e 1. Gli autori selezionano l casualmente per ogni nodo con una distribuzione di probabilità a decadimento esponenziale normalizzata dal moltiplicatore non nullo mL (mL = 0 porta a un unico livello in HNSW e complessità di ricerca non ottimizzata). Normalmente, la maggior parte dei valori di l dovrebbe essere uguale a 0, quindi la maggior parte dei nodi è presente solo sul livello più basso. I valori più grandi di mL aumentano la probabilità che un nodo appaia su livelli più alti.

Il numero di livelli l per ogni nodo è scelto casualmente con una distribuzione di probabilità a decadimento esponenziale.
Distribuzione del numero di livelli in base al fattore di normalizzazione mL. L'asse orizzontale rappresenta i valori della distribuzione uniforme (0, 1).

Per ottenere il massimo vantaggio di prestazioni dell’organizzazione controllabile, la sovrapposizione tra vicini su diversi livelli (cioè la percentuale di vicini degli elementi che appartengono anche ad altri livelli) deve essere ridotta. — Yu. A. Malkov, D. A. Yashunin.

Uno dei modi per ridurre la sovrapposizione è ridurre mL. Ma è importante tenere presente che la riduzione di mL porta anche in media a più attraversamenti durante una ricerca avida su ogni livello. Per questo è essenziale scegliere un valore di mL che bilanci sia la sovrapposizione che il numero di attraversamenti.

Gli autori dell’articolo propongono di scegliere il valore ottimale di mL che è uguale a 1 / ln(M). Questo valore corrisponde al parametro p = 1 / M della lista di salti che rappresenta una sovrapposizione media di un singolo elemento tra i livelli.

Inserimento

Dopo che un nodo è stato assegnato il valore l, ci sono due fasi del suo inserimento:

  1. L’algoritmo parte dal livello superiore e trova avidamente il nodo più vicino. Il nodo trovato viene quindi utilizzato come punto di ingresso per il livello successivo e il processo di ricerca continua. Una volta raggiunto il livello l, l’inserimento procede alla seconda fase.
  2. A partire dal livello l, l’algoritmo inserisce il nuovo nodo nel livello corrente. Poi agisce come prima al passo 1 ma invece di trovare solo un vicino più vicino, cerca avidamente efConstruction (un iperparametro) vicini più vicini. Poi vengono scelti M dei vicini efConstruction e vengono costruiti bordi dal nodo inserito a questi vicini. Dopo di che, l’algoritmo scende al livello successivo e ciascuno dei nodi efConstruction trovati agisce come punto di ingresso. L’algoritmo termina dopo che il nuovo nodo e i suoi bordi sono inseriti sul livello più basso 0.
Inserimento di un nodo (in blu) in HNSW. Il livello massimo per un nuovo nodo è stato scelto casualmente come l = 2. Pertanto, il nodo verrà inserito nei livelli 2, 1 e 0. Su ciascuno di questi livelli, il nodo verrà connesso ai suoi M = 2 vicini più vicini.

Scelta dei valori per i parametri di costruzione

Il paper originale fornisce diversi utili consigli su come scegliere gli iperparametri:

  • Secondo le simulazioni, i buoni valori per M si trovano tra 5 e 48. I valori più piccoli di M tendono a essere migliori per richiami più bassi o dati a bassa dimensionalità, mentre i valori più alti di M sono più adatti per richiami più alti o dati ad alta dimensionalità.
  • I valori più alti di efConstruction implicano una ricerca più profonda in quanto vengono esplorati più candidati. Tuttavia, richiede più calcoli. Gli autori raccomandano di scegliere un valore di efConstruction che produca un richiamo vicino a 0,95-1 durante l’addestramento.
  • Inoltre, c’è un altro importante parametro Mₘₐₓ – il numero massimo di archi che un vertice può avere. Oltre ad esso, esiste lo stesso parametro Mₘₐₓ₀ ma separatamente per il livello più basso. Si consiglia di scegliere un valore per Mₘₐₓ vicino a 2 * M. I valori superiori a 2 * M possono portare a una degradazione delle prestazioni e a un uso eccessivo di memoria. Allo stesso tempo, Mₘₐₓ = M produce prestazioni scarse a richiamo elevato.

Euristica di selezione dei candidati

Si è notato in precedenza che durante l’inserimento del nodo, M dei candidati di efConstruction vengono scelti per costruire archi con loro. Discutiamo possibili modi per scegliere questi M nodi.

L’approccio naïve prende i M candidati più vicini. Tuttavia, non è sempre la scelta ottimale. Di seguito è riportato un esempio che lo dimostra.

Immagina un grafo con la struttura riportata nella figura sottostante. Come puoi vedere, ci sono tre regioni, due delle quali non sono collegate tra loro (a sinistra e in alto). Di conseguenza, per andare, ad esempio, dal punto A al punto B, è necessario percorrere un percorso lungo attraverso un’altra regione. Sarebbe logico connettere in qualche modo queste due regioni per una migliore navigazione.

Il nodo X viene inserito nel grafico. L'obiettivo è quello di collegarlo in modo ottimale ad altri 2 punti M =.

Quindi viene inserito un nodo X nel grafico e deve essere collegato ad altri 2 vertici.

In questo caso, l’approccio naïve prende direttamente i 2 vicini più vicini (B e C) e collega X a loro. Anche se X è collegato ai suoi veri vicini più vicini, non risolve il problema. Vediamo ora l’approccio euristico inventato dagli autori.

L’euristica considera non solo le distanze più vicine tra i nodi, ma anche la connettività di diverse regioni sul grafico.

L’euristica sceglie il primo vicino più vicino (B nel nostro caso) e collega il nodo inserito (X) ad esso. Quindi l’algoritmo prende sequenzialmente un altro vicino più vicino in ordine di distanza (C) e costruisce un arco ad esso solo se la sua distanza dal nuovo nodo (X) è maggiore di qualsiasi distanza dal vicino a tutti i vertici già connessi (B) al nuovo nodo (X). Dopo di che, l’algoritmo procede al vicino più vicino successivo fino a quando non vengono costruiti M archi.

Tornando all’esempio, la procedura euristica è illustrata nella figura sottostante. L’euristica sceglie B come il vicino più vicino per X e costruisce l’arco BX. Quindi l’algoritmo sceglie C come il vicino più vicino successivo. Tuttavia, questa volta BC < CX. Ciò indica che l’aggiunta dell’arco CX al grafico non è ottimale poiché esiste già l’arco BX e i nodi B e C sono molto vicini l’uno all’altro. La stessa analogia prosegue con i nodi D ed E. Dopo di che, l’algoritmo esamina il nodo A. Questa volta soddisfa la condizione poiché AC > AX. Di conseguenza, il nuovo arco AX e entrambe le regioni iniziali diventano connesse tra di loro.

L'esempio a sinistra utilizza l'approccio ingenuo. L'esempio a destra utilizza l'euristica di selezione che porta alla connessione di due regioni iniziali disgiunte.

Complessità

Il processo di inserimento funziona in modo molto simile, rispetto alla procedura di ricerca, senza alcuna differenza significativa che potrebbe richiedere un numero non costante di operazioni. Pertanto, l’inserimento di un singolo vertice impone O(logn) di tempo. Per stimare la complessità totale, dovrebbe essere considerato il numero di tutti i nodi inseriti n in un determinato dataset. In definitiva, la costruzione di HNSW richiede O(n * logn) di tempo.

Combinare HNSW con altri metodi

HNSW può essere utilizzato insieme ad altri metodi di ricerca di similarità per fornire prestazioni migliori. Uno dei modi più popolari per farlo è di combinarlo con un indice di file invertito e una quantizzazione di prodotto (IndexIVFPQ) che sono stati descritti in altre parti di questa serie di articoli.

Ricerca di similarità, parte 3: combinare l’indice di file invertito e la quantizzazione del prodotto

Nelle prime due parti di questa serie abbiamo discusso due algoritmi fondamentali nella ricerca delle informazioni: invertiti…

Nisoo.com

In questo paradigma, HNSW svolge il ruolo di un quantizzatore grossolano per IndexIVFPQ, il che significa che sarà responsabile della ricerca della partizione di Voronoi più vicina, per cui lo scopo della ricerca può essere ridotto. Per farlo, un indice HNSW deve essere costruito su tutti i centroidi di Voronoi. Quando viene fornita una query, HNSW viene utilizzato per trovare il centroide di Voronoi più vicino (invece della ricerca forzata come era stata fatta in precedenza confrontando le distanze con ogni centroide). Dopo di che, il vettore di query viene quantizzato all’interno di una partizione di Voronoi rispettiva e le distanze vengono calcolate utilizzando i codici PQ.

Scegliere il centroide di Voronoi più vicino trovando il vicino più vicino in HNSW costruito in cima ai centroidi di Voronoi.

Quando si utilizza solo un indice di file invertito, è meglio impostare il numero di partizioni Voronoi non troppo grande (per esempio 256 o 1024) perché la ricerca forzata viene eseguita per trovare i centroidi più vicini. Scegliendo un piccolo numero di partizioni Voronoi, il numero di candidati all’interno di ciascuna partizione diventa relativamente grande. Pertanto, l’algoritmo identifica rapidamente il centroide più vicino per una query e la maggior parte del suo tempo di esecuzione è concentrata sulla ricerca del vicino più vicino all’interno di una partizione Voronoi.

Tuttavia, l’introduzione di HNSW nel flusso di lavoro richiede un adeguamento. Consideriamo di eseguire HNSW solo su un piccolo numero di centroidi (256 o 1024): HNSW non porterebbe alcun beneficio significativo perché, con un numero ridotto di vettori, HNSW esegue relativamente la stessa operazione in termini di tempo di esecuzione come l’ingenua ricerca forzata. Inoltre, HNSW richiederebbe più memoria per archiviare la struttura del grafo.

Pertanto, quando si uniscono HNSW e l’indice di file invertito, è consigliabile impostare il numero di centroidi Voronoi molto più grande del solito. In questo modo, il numero di candidati all’interno di ciascuna partizione Voronoi diventa molto più piccolo.

Questo cambio di paradigma porta alle seguenti impostazioni:

  • HNSW identifica rapidamente i centroidi di Voronoi più vicini in tempo logaritmico.
  • Dopo di che, viene eseguita una ricerca esaustiva all’interno delle rispettive partizioni Voronoi. Non dovrebbe essere un problema perché il numero di candidati potenziali è piccolo.

Implementazione di Faiss

Faiss (Facebook AI Search Similarity) è una libreria Python scritta in C++ utilizzata per la ricerca di similarità ottimizzata. Questa libreria presenta diversi tipi di indici che sono strutture dati utilizzate per archiviare efficientemente i dati e eseguire le query.

In base alle informazioni fornite nella documentazione di Faiss, vedremo come HNSW possa essere utilizzato e combinato con l’indice a file invertiti e quantizzazione del prodotto.

IndexHNSWFlat

FAISS ha una classe IndexHNSWFlat che implementa la struttura HNSW. Come al solito, il suffisso “Flat” indica che i vettori del dataset sono completamente memorizzati nell’indice. Il costruttore accetta 2 parametri:

  • d : dimensionalità dei dati.
  • M : il numero di archi che devono essere aggiunti ad ogni nuovo nodo durante l’inserimento.

Inoltre, tramite il campo hnsw, IndexHNSWFlat fornisce diversi attributi utili (che possono essere modificati) e metodi:

  • hnsw.efConstruction : numero di vicini più vicini da esplorare durante la costruzione.
  • hnsw.efSearch : numero di vicini più vicini da esplorare durante la ricerca.
  • hnsw.max_level : restituisce il livello massimo.
  • hnsw.entry_point : restituisce il punto di ingresso.
  • faiss.vector_to_array(index.hnsw.levels) : restituisce una lista dei livelli massimi per ogni vettore
  • hnsw.set_default_probas(M: int, level_mult: float) : consente di impostare rispettivamente i valori di M e mL. Per impostazione predefinita, level_mult è impostato su 1 / ln(M).
Implementazione di Faiss di IndexHNSWFlat

IndexHNSWFlat imposta i valori per Mₘₐₓ = M e Mₘₐₓ₀ = 2 * M.

IndexHNSWFlat + IndexIVFPQ

IndexHNSWFlat può essere combinato anche con altri indici. Uno degli esempi è IndexIVFPQ descritto nella parte precedente. La creazione di questo indice composito avviene in due fasi:

  1. IndexHNSWFlat viene inizializzato come quantizzatore grossolano.
  2. Il quantizzatore viene passato come parametro al costruttore di IndexIVFPQ.

L’addestramento e l’aggiunta possono essere effettuati utilizzando dati diversi o gli stessi.

Implementazione di FAISS di IndexHNSWFlat + IndexIVFPQ

Conclusioni

In questo articolo abbiamo studiato un algoritmo robusto che funziona particolarmente bene per i vettori di grandi dataset. Utilizzando rappresentazioni grafiche a più livelli e l’euristica di selezione dei candidati, la sua velocità di ricerca scala efficientemente mantenendo una decente accuratezza di predizione. È anche importante notare che HNSW può essere utilizzato in combinazione con altri algoritmi di ricerca di similarità, rendendolo molto flessibile.

Risorse

  • Sei gradi di separazione | Wikipedia
  • Skip List | Wikipedia
  • Cerca il vicino più vicino approssimato efficiente e robusto utilizzando grafi Hierarchical Navigable Small World. Yu. A. Malkov, D. A. Yashunin
  • Documentazione di Faiss
  • Repository di Faiss
  • Sommario degli indici di Faiss

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