Introduzione a HNSW Navigabile Small World Gerarchico

Introduzione

L’innovazione dell’IA sta avvenendo a ritmo frenetico. Una delle frontiere di questa innovazione sono i motori di ricerca vettoriali. Cosa sono questi motori di ricerca, vi chiederete? In parole semplici, aiutano ad addestrare modelli di linguaggio (LLM) per mezzo di grandi set di dati, selezionando ciò che è rilevante. Ora, esistono molti modi diversi in cui questo indicizzazione avviene nei database vettoriali. Tra di essi, il modello Small World Navigabile Gerarchicamente (HNSW) si distingue per essere performante e scalabile. Tutti i principali negozi di vettori forniscono HNSW come metodo di indicizzazione. È veloce, efficiente, robusto e affidabile. Quindi, in questo articolo, analizzeremo il funzionamento interno di HNSW e scopriremo cosa lo rende così veloce.

Obiettivi di Apprendimento

Capire cosa sono gli embedding e i database vettoriali.
Conoscere i diversi metodi di indicizzazione nei database vettoriali.
Imparare cos’è HNSW e come funziona.
Comprendere HNSWlib, un’implementazione HNSW che include solo l’intestazione del codice.

Questo articolo è stato pubblicato come parte del Data Science Blogathon.

Cosa sono gli Embedding?

Gli embedding sono rappresentazioni vettoriali dei dati (testo, immagini) in uno spazio vettoriale ad alta dimensionalità.

I dati semanticamente correlati saranno vicini nello spazio vettoriale, mentre i dati dissimili saranno lontani. In altre parole, gli embedding delle parole “Messi” e “calcio” saranno vicini nello spazio di embedding, mentre gli embedding delle parole “calcio” e “Joe Biden” saranno lontani nello spazio di embedding.

La lunghezza dei vettori può variare da alcune centinaia a migliaia o più. Ciò rende difficile memorizzarli, interrogarli e cercarli. Ma ogni applicazione basata su Retrieval Augmented Generation (RAG) richiede la ricerca e l’interrogazione ad alta velocità degli embedding dei dati. Ed è qui che entrano in gioco i database vettoriali.

Cosa sono i Database Vettoriali?

Così come i database tradizionali mirano a memorizzare dati strutturati e non strutturati, i database vettoriali memorizzano, cercano e interrogano gli embedding vettoriali ad alta dimensionalità. Forniscono interfacce user-friendly per interagire con gli embedding e i dati associati. I database vettoriali non sono fondamentalmente diversi dai database tradizionali. I database vettoriali utilizzano database tradizionali per memorizzare gli embedding serializzati. Ad esempio, Chroma utilizza SQLite come archiviazione in memoria e Pgvector utilizza il database Postgres per memorizzare gli embedding e i metadati associati. La cosa che differenzia un database tradizionale da un database vettoriale è l’algoritmo di indicizzazione sottostante.

Indicizzazione nei Database Vettoriali

L’indicizzazione si riferisce al processo di organizzazione di vettori ad alta dimensionalità in modo da consentire una query efficiente di vettori vicini.

Questa è la parte più cruciale nella costruzione di qualsiasi database vettoriale. Questi indici consentono una ricerca rapida ed efficiente di embedding ad alta dimensionalità. Esistono numerosi metodi di indicizzazione per creare indici vettoriali, come:

Algoritmo di ricerca lineare (Indicizzazione piatta): Questo è un algoritmo di ricerca lineare, il che significa che confronta il vettore di query con ogni altro vettore memorizzato nel database. Questo è il metodo più semplice ed è adatto a set di dati di piccole dimensioni.
Algoritmo basato sul clustering (IVF): L’Inverted File è una tecnica di indicizzazione basata sul clustering. Utilizza il clustering k-means per raggruppare tutti i vettori. Quando viene fornito un vettore di query, calcola la distanza tra il vettore di query e i centroidi di ciascun cluster. E inizia a cercare i vicini più vicini nel cluster con il centroide più vicino al vettore di query. Questo riduce significativamente il tempo di interrogazione.
Quantizzazione (Quantizzazione scalare e di prodotto): La tecnica di quantizzazione prevede di ridurre l’occupazione di memoria degli embedding di grandi dimensioni riducendone la precisione.
Basato su grafi (HNSW): Il metodo di indicizzazione più comune. Utilizza un’architettura gerarchica a grafo per indicizzare i vettori. Ed è quello che andremo a esplorare.

Comprensione di HNSW

I modelli di linguaggio di grandi dimensioni (LLM) stanno diventando sempre più popolari e molte organizzazioni vogliono implementarli nelle loro pile di prodotti. Tuttavia, ciò rappresenta una sfida: i LLM hanno una finestra di contesto limitata. Una finestra di contesto è il numero di token che un modello di intelligenza artificiale può elaborare. Ad esempio, il modello GPT 3.5 turbo ha una lunghezza di contesto di 4096. Ed è qui che i database di ricerca vettoriale si distinguono. Invece di inserire l’intero libro nel contesto del LLM, troviamo le parti più rilevanti e le forniamo al LLM per ottenere risultati precisi.

Ora, tra tutti i diversi modi di indicizzazione nei database vettoriali discussi sopra, HNSW è il più robusto e scalabile. Questo lo rende anche il metodo di indicizzazione più ampiamente utilizzato. HNSW è formato dalla combinazione di due algoritmi: skip list e navigable small world. Per capire HNSW, dobbiamo conoscere questi algoritmi. Quindi, immergiamoci.

Skip List

Come suggerisce il nome, la skip list si basa sulla struttura dati della lista collegata, o possiamo dire che è un’estensione della struttura dati della lista collegata. È stato inventato da David Pugh nel 1990 come alternativa più veloce alle liste collegate.

Perché abbiamo bisogno di una skip list? Una lista collegata ha una complessità temporale di ricerca O(n). Questo potrebbe non essere ideale per casi d’uso reali in cui la velocità di esecuzione è fondamentale. Quindi, potremmo aver bisogno di un algoritmo di lista collegata più efficiente.

Le skip list hanno una complessità temporale attesa di O(log n). Si comportano molto meglio nell’accesso casuale rispetto alle liste collegate. Poiché hanno una struttura a più livelli con più nodi in ogni livello, la complessità spaziale nel caso peggiore è O(n log n), dove n è il numero di nodi nel livello più basso.

Come funziona la skip list?

Una skip list mantiene un’architettura collegata a più livelli, dove il livello superiore ha i collegamenti più lunghi tra gli elementi. Questi diminuiscono in modo esponenziale man mano che ci spostiamo verso i livelli inferiori.

Nell’immagine sopra, il livello più basso è una lista collegata completa. Man mano che ci spostiamo verso l’alto, il numero di nodi si riduce della metà in ogni livello. La struttura è chiamata skip list, poiché i livelli superiori ti permettono di saltare i nodi durante il percorso.

Considera il seguente esempio.

Quando cerchiamo k:

se k = elemento target
se k ≥ spostati a destra
se k < spostati in basso

Partiamo dall’angolo in alto a sinistra e ci spostiamo verso destra finché non troviamo k o un numero inferiore a k. Ci spostiamo verso il livello inferiore e continuiamo il processo finché non raggiungiamo k. La complessità di ricerca è O(log n) in quanto saltiamo metà degli elementi ad ogni livello.

Anche se l’accesso casuale è più veloce, l’inserimento e la cancellazione sono più lenti in quanto aggiungono un sovraccarico aggiuntivo per l’aggiornamento e la cancellazione su più livelli.

Nell’inserimento, partiamo dalla lista inferiore e aggiungiamo il nodo nella posizione appropriata. Poiché le skip list mantengono una struttura gerarchica, dobbiamo determinare se il nodo appare a un livello superiore. Il processo è casuale, come un lancio di moneta. La probabilità che un nodo appaia nel livello superiore immediato è 0,5. In una skip list ideale, il numero di nodi nel livello 1 sarà ~n/2 e nel livello 2 ~n/4, dove n è il numero di nodi nel livello più basso o nella lista collegata completa.

Considera il seguente esempio.

Troviamo il posto ideale per l’inserimento e inseriamo il nodo al livello inferiore. Decidiamo poi se il nodo deve apparire nel livello superiore in base a un’uscita binaria casuale (testa o croce). In una skip list perfetta, otteniamo una distribuzione bilanciata di nodi in ogni livello.

La cancellazione avviene in modo simile. Trova il numero target e cancella il nodo. Se l’elemento è presente in un livello superiore, cancellalo e aggiorna la lista collegata.

Navigable Small World (NSW)

Navigable Small World è un algoritmo basato su grafo per trovare i vicini più vicini approssimati. I punti di dati in un grafo sono chiamati nodi. Ogni nodo è collegato a un insieme fisso di connessioni vicine l’una all’altra.

Questo è un algoritmo avido. Parte da un punto predefinito nel grafo e seleziona i nodi più vicini al nodo target. La distanza tra i nodi può essere misurata tramite similarità Euclidea o coseno. Questo processo viene ripetuto fino a raggiungere i vicini più vicini al nodo target.

L’algoritmo Navigable Small World è molto efficiente e facilmente utilizzabile. Funziona bene per dataset che vanno da alcune centinaia a migliaia. Successivamente, tende a comportarsi peggio. Soffre di terminazione anticipata quando non riesce a trovare un vicino migliore rispetto a quello attuale, poiché utilizza solo informazioni locali per trovare il vicino più vicino.

Durante l’inserimento, attraversiamo il grafo per trovare i vicini più vicini e li colleghiamo al nodo x.

Come nei database vettoriali, dobbiamo gestire diversi milioni di dati di embedding. Pertanto, abbiamo bisogno di un algoritmo migliore che si scali bene e offra una migliore ricercabilità. Sebbene NSW funzioni abbastanza bene per piccoli dataset, abbiamo bisogno di un algoritmo ancora migliore per gestire centinaia di milioni o miliardi di punti dati. Ecco dove entra in gioco HNSW.

Hierarchical Navigable Small World (HNSW)

HNSW estende NSW incorporando l’architettura gerarchica delle Skip Lists. Ciò ha eliminato il collo di bottiglia della scalabilità di NSW. Come le Skip Lists, HNSW crea la struttura a più livelli delle NSW invece delle liste collegate. Come le Skip Lists, il livello più alto avrà meno punti dati con le connessioni più lunghe. Il numero di elementi aumenta man mano che ci spostiamo nella gerarchia. Al livello più basso, abbiamo tutti i punti dati. Come le skip list, la probabilità dell’esistenza di un elemento diminuisce esponenzialmente man mano che ci spostiamo verso l’alto nella gerarchia.

Ma come facciamo a cercare in HNSW?

Ricerca in HNSW

Ricordiamo ora sia la skip list che NSW. Nella skip list, partiamo dal livello più alto, e in NSW, partiamo da un punto predefinito. In HNSW, partiamo da un punto predefinito al livello più alto della gerarchia e attraversiamo avidamente il grafo per trovare l’elemento più vicino al punto di dati obiettivo in quel livello. Una volta raggiunto il nodo più vicino, scendiamo al livello inferiore e ripetiamo il processo fino a quando non vengono trovati i “K” vicini più prossimi al nodo obiettivo. Vedi l’immagine sottostante.

Inserimento e Cancellazione in HNSW

L’inserimento in HNSW segue lo stesso principio delle skip list. Attraversiamo i livelli, trovando i vicini più prossimi all’elemento. Quindi, scendiamo e ripetiamo lo stesso processo fino a quando non troviamo tutti i vicini più prossimi al livello inferiore.

Il compito successivo è determinare i collegamenti bidirezionali all’elemento inserito. Di solito viene determinato da un parametro predefinito m. Colleghiamo i m vicini più prossimi al nodo inserito. Questo è uno dei modi per determinare i collegamenti a un nodo inserito. Altre euristiche possono essere utilizzate. Ad esempio, anziché connettersi solo ai nodi vicini più prossimi della stessa regione, connettiamo anche il nodo inserito al nodo più vicino della regione più vicina per formare un grafo meglio connesso.

Come per le skip list, la probabilità che un nodo compaia nei livelli superiori viene decisa casualmente. La funzione per questo è floor(-ln(rand(0, 1))), dove rand(0, 1) è un numero casuale campionato da una distribuzione uniforme tra (0, 1].

La cancellazione segue un approccio simile. Iniziamo con il livello superiore e cancelliamo il target man mano che appare fino al livello inferiore.

Complessità in HNSW

Le complessità temporali di ricerca, inserimento e cancellazione in HNSW dipendono da molteplici fattori, tra cui l’altezza dell’architettura, il numero di nodi vicini per nodo e la metrica della distanza. Ma in media, ricerca, inserimento e cancellazione hanno una complessità temporale di O(log n). La costruzione dell’HNSW può essere costosa. Dobbiamo inserire n nodi con una complessità di O(log n). Pertanto, la complessità temporale complessiva della costruzione del grafo sarà di O(n log n).

Le basi di dati vettoriali sono costruite per gestire centinaia di milioni di incorporazioni. L’indicizzazione di una tale quantità di dati richiede un algoritmo altamente efficiente, robusto e scalabile. HNSW soddisfa tutti i requisiti.

Svantaggi di HNSW

Anche se la ricerca, l’inserimento e la cancellazione sono più rapidi in HNSW, ci sono alcuni compromessi che devi conoscere prima di utilizzare HNSW. Ecco alcune cose da tenere a mente prima di implementare HNSW.

Prevalenza di memoria più elevata: HNSW mantiene una struttura gerarchica di incorporazioni, che aumenta significativamente il consumo di memoria rispetto ad algoritmi come NSW. Questo può essere problematico per dispositivi con risorse limitate.
Tuning dei parametri: HNSW ha diversi parametri regolabili. È necessario un accordo attento dei parametri per migliorare le prestazioni.
Difficoltà: Implementare HNSW da zero può diventare complicato. La maggior parte delle basi di dati vettoriali utilizza soluzioni precompilate affidabili come FAISS o HNSWlib.

HNSWlib: Un’implementazione HNSW con solo intestazione

HNSWlib è un’implementazione di HNSW in C++ con solo intestazione con collegamenti Python. È stata scritta dall’autore del paper HNSW, Yury Malkov. Si tratta di un’implementazione essenziale dell’algoritmo.

Quindi, iniziamo.

Puoi installare HNSWlib con qualsiasi gestore di pacchetti Python.

pip install hnswlib

Dichiara e inizializza l’indice HNSW.

import hnswlibimport numpy as npimport pickleim = 16num_elements = 100hnsw_index = hnswlib.Index(space = 'l2', dim = dim) #dichiara l'indicehnsw_index.init_index(max_elements = num_elements, ef_construction = 200, M = 16)

Il parametro “space” è la metrica della distanza che verrà utilizzata per calcolare la distanza tra i nodi. L’implementazione in Python supporta L2 al quadrato, Cosine e dot-product.
Il parametro “dim” è la dimensione dei vettori di embedding.
Il metodo “init_index” inizializza l’indice.
“ef_construction” definisce il compromesso tra tempo di costruzione e precisione.
“M” è il numero di collegamenti bidirezionali creati durante l’inserimento di un nodo.

Ora che abbiamo creato gli indici, aggiungiamo alcuni vettori.

data1 = np.float32(np.random.random((num_elements, dim)))ids1 = np.arange(num_elements)data2 = np.float32(np.random.random((100, dim)))ids2 = np.arange(100)data3 = np.float32(np.random.random((100, dim)))ids3 = np.arange(100)hnsw_index.add_items(data1, ids1)hnsw_index.add_items(data2, ids2)hnsw_index.set_ef(50) #imposta il compromesso tra velocità e precisione delle queryhnsw_index.set_num_threads(4) #imposta il numero di thread durante la costruzione in batch

Ora, vediamo come possiamo cercare il vicino approssimativo k.

etichette, distanze = p.knn_query(data, k = 1)

Serializza l’oggetto indice utilizzando pickle.

p_cp = pickle.loads(pickle.dumps(hnsw_index))

Elimina gli elementi.

per id in ids2:    hnsw_index.mark_deleted(id)

Questo libererà gli ultimi 100 elementi dall’indice. Se desideri, puoi anche riutilizzare la memoria degli elementi eliminati.

hnsw_index.add_items(data3, labels3, replace_deleted=True)

Conclusione

L’HNSW è uno degli algoritmi più cruciali al momento per lo sviluppo dei metodi di recupero di vettori. È l’algoritmo di indicizzazione primario utilizzato in tutti i principali database di vettori. Speriamo che tu abbia compreso il funzionamento di HNSW attraverso questo articolo. Con l’evoluzione dell’IA, assisteremo allo sviluppo di modelli di apprendimento più ampi e complessi, aumentando la necessità di utilizzare HNSW e incrementando le sue applicazioni e importanza.

Punti chiave

I database di vettori sono archivi di dati progettati appositamente per archiviare embedding di vettori ad alta dimensione.
L’indicizzazione degli embedding consente ai negozi di vettori di gestire la ricerca, l’inserimento e l’eliminazione degli embedding.
Esistono diversi modi di indicizzare i vettori, come IVF, Annoy, Quantization e HNSW.
HNSW è una combinazione di due algoritmi: le liste di salti e un Navigable Small World (NSW).

Domande frequenti

I media presentati in questo articolo non sono di proprietà di Analytics Vidhya e vengono utilizzati a discrezione dell’autore.

Algorithm,blogathon,databases,embeddings,Guide,HNSW,Indexing,Large Language Models