Introduzione alla ricerca di similarità vettoriale
Nei tutorial precedenti, abbiamo dato un'occhiata ai dati non strutturati, ai database vettoriali e a Milvus - il database vettoriale open-source più popolare al mondo utilizzato per la ricerca per similarità. Abbiamo anche accennato brevemente all'idea di embedding, vettori ad alta dimensionalità che fungono da eccellenti rappresentazioni semantiche dei dati non strutturati. Una nota chiave da ricordare: embedding e rappresentazioni vettoriali che sono "vicini" tra loro rappresentano porzioni di dati semanticamente simili.
In questa introduzione alla ricerca vettoriale (alias ricerca per similarità), definiremo che cos'è e risponderemo ad alcune domande fondamentali al riguardo. Poi, svilupperemo questa conoscenza esaminando un esempio di word embedding e vedendo come porzioni di dati non strutturati semanticamente simili siano "vicine" tra loro, mentre porzioni di dati non strutturati dissimili siano "lontane" tra loro. Questo porterà a una panoramica di alto livello della ricerca del vicino più prossimo, un problema computazionale che implica trovare il/i vettore/i più vicino/i a un vettore di query sulla base di una metrica di distanza unificata. Esamineremo alcuni metodi ben noti (algoritmi di ricerca per similarità vettoriale) per la ricerca del vicino più prossimo (incluso il mio preferito: ANNOY) oltre alle metriche di distanza comunemente usate.
Immergiamoci.
Che cos'è la ricerca vettoriale o ricerca per similarità vettoriale?
La ricerca vettoriale, nota anche come ricerca per similarità vettoriale o ricerca del vicino più prossimo o ricerca semantica, è una tecnica utilizzata nei sistemi di recupero dei dati e di recupero delle informazioni per trovare elementi o punti dati simili o strettamente correlati a un dato vettore di query. A differenza della tradizionale ricerca per parole chiave, che abbina parole o frasi esatte, la ricerca semantica comprende l'intento e il significato contestuale dietro una query, consentendole di restituire risultati più pertinenti anche quando le parole chiave esatte non sono presenti nel contenuto. Nella ricerca vettoriale, rappresentiamo i punti dati, come immagini, testi e audio, come vettori in uno spazio ad alta dimensionalità. L'obiettivo della ricerca vettoriale è cercare e recuperare in modo efficiente i vettori più pertinenti che sono simili o più vicini a un vettore di query.
Tipicamente, metriche di distanza come la distanza euclidea o la similarità del coseno misurano la similarità tra vettori. La prossimità del vettore nello spazio vettoriale determina quanto sia simile. Per organizzare e mostrare in modo efficiente i risultati di ricerca per i vettori, gli algoritmi di ricerca vettoriale utilizzano strutture di indicizzazione come strutture basate su alberi o tecniche di hashing.
La ricerca vettoriale è centrale nei database vettoriali e ha varie applicazioni, tra cui sistemi di raccomandazione, recupero di immagini e video, elaborazione del linguaggio naturale, rilevamento di anomalie e chatbot per domande e risposte. L'uso della ricerca semantica rende possibile trovare elementi, pattern o relazioni pertinenti all'interno di dati ad alta dimensionalità, consentendo un recupero delle informazioni più accurato ed efficiente.
La ricerca vettoriale è un metodo potente per analizzare e recuperare informazioni da spazi ad alta dimensionalità. Consente agli utenti di trovare elementi simili o strettamente correlati a una data query, rendendola cruciale in vari domini. Ecco i vantaggi della ricerca vettoriale:
Recupero basato sulla similarità— La ricerca semantica consente il recupero basato sulla similarità, permettendo agli utenti di trovare elementi simili o strettamente correlati a una data query. Il recupero basato sulla similarità è cruciale in vari domini, come i sistemi di raccomandazione, dove gli utenti si aspettano raccomandazioni personalizzate basate sulle loro preferenze o sulle similarità con altri utenti.
Analisi dei dati ad alta dimensionalità — Con la crescente disponibilità di dati ad alta dimensionalità, come immagini, audio e dati testuali, i metodi di ricerca tradizionali diventano meno efficaci. La ricerca vettoriale offre un modo potente per analizzare e recuperare informazioni da spazi ad alta dimensionalità, consentendo un’esplorazione dei dati più accurata ed efficiente.
Ricerca del vicino più prossimo — Algoritmi efficienti di ricerca del vicino più prossimo trovano i vicini più prossimi a un dato vettore di query. La ricerca del vicino più prossimo è utile per attività critiche come la ricerca di similarità di immagini o documenti, il Retrieval basato sui contenuti o il rilevamento di anomalie, che richiedono di trovare le corrispondenze più vicine o elementi simili.
Esperienza utente migliorata— Sfruttando la ricerca semantica, le applicazioni possono fornire agli utenti risultati più pertinenti e personalizzati. Che si tratti di offrire raccomandazioni pertinenti, recuperare immagini visivamente simili o trovare documenti con contenuti simili, la ricerca vettoriale migliora l’esperienza utente complessiva fornendo risultati più mirati e significativi.
Scalabilità — Gli algoritmi di ricerca vettoriale e le strutture di indicizzazione gestiscono in modo efficiente dataset su larga scala e spazi ad alta dimensionalità. Consentono operazioni rapide di ricerca e recupero, rendendo possibile eseguire query basate sulla similarità in tempo reale, anche su dataset enormi.
Come funziona un motore di ricerca vettoriale?
Con la popolarità dell’AI e degli LLM, ogni strumento per sviluppatori, motore di ricerca e database sta aggiungendo funzionalità di ricerca vettoriale al proprio set di funzionalità e, per questo motivo, i termini motore vettoriale e motori di ricerca vettoriale sono spesso usati in modo intercambiabile con database vettoriali. I motori di ricerca vettoriale eseguiranno una ricerca semantica vettoriale (a volte indicata come ricerca vettoriale). La ricerca vettoriale è una tecnica per trovare elementi o punti dati simili in un dataset in base alla loro rappresentazione come vettori in uno spazio ad alta dimensionalità. Ogni elemento è mappato su un punto in questo spazio, con ogni dimensione del vettore che rappresenta una caratteristica specifica. Il processo di ricerca vettoriale prevede indicizzazione, interrogazione, classificazione e recupero.
Per eseguire la ricerca vettoriale, innanzitutto rappresenti i tuoi elementi di dati come vettori, usando tecniche come Word2Vec o per dati testuali. Una struttura dati di indice memorizza in modo efficiente questi vettori per un recupero rapido, usando metodi come KD-trees o tabelle hash. Quando un utente invia un elemento di query, viene convertito in una rappresentazione vettoriale, confrontato con i vettori indicizzati usando metriche di similarità come la similarità coseno o la distanza euclidea, e gli elementi più simili vengono recuperati e classificati.
Casi d’uso della ricerca vettoriale
- Ricerca di similarità di immagini, video, audio
- Scoperta di farmaci con AI
- Motore di ricerca semantica
- Classificazione di sequenze di DNA
- Sistema di risposta alle domande
- Sistema di raccomandazione
- Rilevamento di anomalie
- Retrieval Augmented Generation (RAG)
Ora che abbiamo coperto le basi della ricerca vettoriale, esaminiamo i dettagli più tecnici guardando un esempio di word embedding e concludiamo con una panoramica di alto livello della ricerca del vicino più prossimo.
Confrontare gli embedding
Una volta che gli utenti decidono di voler intraprendere la creazione della ricerca vettoriale nella loro soluzione, la domanda successiva che spesso pongono è “Quale modello di Machine Learning dovrei usare per creare Vector Embeddings.” Prima di poter scegliere un modello, è importante comprendere gli embedding vettoriali confrontando alcuni esempi. Esaminiamo un paio di esempi di word embedding. Per semplicità, useremo word2vec, un vecchio modello che utilizza una metodologia di addestramento basata su skipgrams. BERT e altri modelli moderni basati su transformer saranno in grado di fornirti word embedding più contestualizzati, ma ci atterremo a word2vec per semplicità. Jay Alammar offre un ottimo tutorial su word2vec, se sei interessato a usare un po’ di più i modelli di machine learning.
Un po’ di preparazione
Prima di iniziare, dovremo installare la libreria gensim e caricare un modello word2vec.
% pip install gensim --disable-pip-version-check
% wget https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
% gunzip GoogleNews-vectors-negative300.bin
Requirement already satisfied: gensim in /Users/fzliu/.pyenv/lib/python3.8/site-packages (4.1.2)
Requirement already satisfied: smart-open>=1.8.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (5.2.1)
Requirement already satisfied: numpy>=1.17.0 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.19.5)
Requirement already satisfied: scipy>=0.18.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (1.7.3)
--2022-02-22 00:30:34-- https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
Resolving s3.amazonaws.com (s3.amazonaws.com)... 52.216.20.165
Connecting to s3.amazonaws.com (s3.amazonaws.com)|52.216.20.165|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1647046227 (1.5G) [application/x-gzip]
Saving to: GoogleNews-vectors-negative300.bin.gz
GoogleNews-vectors- 100%[===================>] 1.53G 2.66MB/s in 11m 23s
2022-02-22 00:41:57 (2.30 MB/s) - GoogleNews-vectors-negative300.bin.gz saved [1647046227/1647046227]
gunzip: GoogleNews-vectors-negative300.bin: unknown suffix -- ignored
Ora che abbiamo completato tutto il lavoro preparatorio necessario per generare embedding da parole a vettori, carichiamo il modello word2vec addestrato.
>>> from gensim.models import KeyedVectors
>>> model = KeyedVectors.load_word2vec_format('GoogleNews-vectors-negative300.bin', binary=True)
Esempio 0: Marlon Brando
Diamo un'occhiata a come word2vec interpreta il famoso attore Marlon Brando.
>>> print(model.most_similar(positive=['Marlon_Brando']))
[('Brando', 0.757453978061676), ('Humphrey_Bogart', 0.6143958568572998), ('actor_Marlon_Brando', 0.6016287207603455), ('Al_Pacino', 0.5675410032272339), ('Elia_Kazan', 0.5594002604484558), ('Steve_McQueen', 0.5539456605911255), ('Marilyn_Monroe', 0.5512186884880066), ('Jack_Nicholson', 0.5440199375152588), ('Shelley_Winters', 0.5432392954826355), ('Apocalypse_Now', 0.5306933522224426)]
Marlon Brando ha lavorato con Al Pacino ne Il padrino e con Elia Kazan in Un tram che si chiama Desiderio. Ha anche recitato in Apocalypse Now.
Esempio 1: Se tutti i re avessero le loro regine sul trono
I vettori possono essere sommati e sottratti tra loro per dimostrare cambiamenti semantici sottostanti.
>>> print(model.most_similar(positive=['king', 'woman'], negative=['man'], topn=1))
[('queen', 0.7118193507194519)]
Chi dice che gli ingegneri non possano godersi un po' di dance-pop ogni tanto?
Esempio 2: Apple, l'azienda, il frutto, ... o entrambi?
La parola "apple" può riferirsi sia all'azienda sia al delizioso frutto rosso. In questo esempio, possiamo vedere che Word2Vec conserva entrambi i significati.
>>> print(model.most_similar(positive=['samsung', 'iphone'], negative=['apple'], topn=1))
>>> print(model.most_similar(positive=['fruit'], topn=10)[9:])
[('droid_x', 0.6324754953384399)]
[('apple', 0.6410146951675415)]
"Droid" si riferisce al primo smartphone 4G LTE di Samsung ("Samsung" + "iPhone" - "Apple" = "Droid"), mentre "apple" è la decima parola più vicina a "fruit".
Strategie di ricerca vettoriale
Ora che abbiamo visto la potenza degli embedding vettoriali, diamo brevemente un'occhiata ad alcuni dei modi in cui possiamo effettuare la ricerca del vicino più prossimo. Questo non è un elenco esaustivo; esamineremo solo brevemente alcuni metodi comuni per fornire una panoramica di alto livello di come la ricerca vettoriale viene condotta su larga scala. Nota che alcuni di questi metodi non si escludono a vicenda: è possibile, ad esempio, utilizzare la quantizzazione insieme alla partizione dello spazio.
(Analizzeremo anche ciascuno di questi metodi in dettaglio nei prossimi tutorial, quindi restate sintonizzati.)
Ricerca lineare
L'algoritmo di ricerca del vicino più prossimo più semplice ma più ingenuo è la buona vecchia ricerca lineare: calcolare la distanza da un vettore di query a tutti gli altri vettori nel database vettoriale.
Per ovvi motivi, la ricerca ingenua non funziona quando si cerca di scalare il nostro database vettoriale a decine o centinaia di milioni di vettori. Ma quando il numero totale di elementi nel database è piccolo, questo può effettivamente essere il modo più efficiente per eseguire la ricerca vettoriale, poiché non è richiesta una struttura dati separata per l'indice, mentre inserimenti ed eliminazioni possono essere implementati abbastanza facilmente.
A causa della mancanza di complessità spaziale e del sovraccarico costante di spazio associati alla ricerca ingenua, questo metodo può spesso superare il partizionamento dello spazio anche quando si eseguono query su un numero moderato di vettori.
Partizionamento dello spazio
Il partizionamento dello spazio non è un singolo algoritmo, ma piuttosto una famiglia di algoritmi che utilizzano tutti lo stesso concetto.
Gli alberi K-dimensionali (kd-tree) sono forse i più noti di questa famiglia e funzionano bisecando continuamente lo spazio di ricerca (suddividendo i vettori in bucket “sinistro” e “destro”) in modo simile agli alberi di ricerca binaria.
L'indice a file invertito (IVF) è anch'esso una forma di partizionamento dello spazio e funziona assegnando ogni vettore al suo centroide più vicino: le ricerche vengono quindi condotte determinando prima il centroide più vicino del vettore di query ed eseguendo la ricerca attorno a esso, riducendo significativamente il numero totale di vettori che devono essere cercati. IVF è una strategia di indicizzazione piuttosto popolare ed è comunemente combinata con altri algoritmi di indicizzazione per migliorare le prestazioni.
Quantizzazione
La quantizzazione è una tecnica per ridurre la dimensione totale del database riducendo la precisione dei vettori.
La quantizzazione scalare (SQ), ad esempio, funziona moltiplicando vettori in virgola mobile ad alta precisione per un valore scalare, quindi convertendo gli elementi del vettore risultante nei loro interi più vicini. Questo non solo riduce la dimensione effettiva dell'intero database (ad esempio di un fattore otto per la conversione da float64_t a int8_t), ma ha anche l'effetto collaterale positivo di accelerare i calcoli della distanza vettoriale tra vettori.
La quantizzazione del prodotto (PQ) è un'altra tecnica di quantizzazione che funziona in modo simile alla compressione tramite dizionario. In PQ, tutti i vettori vengono suddivisi in sottovettori di uguale dimensione e ogni sottovettore viene quindi sostituito con un centroide.
Hierarchical Navigable Small Worlds (HNSW)
Hierarchical Navigable Small Worlds è un algoritmo di indicizzazione e recupero basato su grafi.
Funziona in modo diverso dalla quantizzazione del prodotto: invece di migliorare la ricercabilità del database riducendone la dimensione effettiva, HNSW crea un grafo multilivello a partire dai dati originali. I livelli superiori contengono solo "connessioni lunghe", mentre i livelli inferiori contengono solo "connessioni corte" tra i vettori nel database (vedi la sezione successiva per una panoramica delle metriche di distanza vettoriale). Le singole connessioni del grafo vengono create à la skip list.
Con questa architettura in atto, la ricerca diventa piuttosto semplice: attraversiamo avidamente il grafo più alto (quello con le connessioni inter-vettoriali più lunghe) per trovare il vettore più vicino al nostro vettore di query. Poi facciamo lo stesso per il secondo livello, usando il risultato della ricerca del primo livello come punto di partenza. Questo continua finché non completiamo la ricerca al livello più basso, il cui risultato diventa il vicino più prossimo del vettore di query.
HNSW, visualizzato. Fonte immagine: https://arxiv.org/abs/1603.09320
Approximate Nearest Neighbors Oh Yeah
Questo è probabilmente il mio algoritmo ANN preferito semplicemente per via del suo nome giocoso e poco intuitivo. Approximate Nearest Neighbors Oh Yeah (ANNOY) è un algoritmo basato su alberi reso popolare da Spotify (è utilizzato nel loro sistema di raccomandazione musicale). Nonostante il nome strano, il concetto alla base di ANNOY è in realtà piuttosto semplice: alberi binari.
ANNOY funziona selezionando prima casualmente due vettori nel database e bisecando lo spazio di ricerca lungo l’iperpiano che separa quei due vettori. Questo viene fatto iterativamente finché non ci sono meno di un certo parametro predefinito NUM_MAX_ELEMS per nodo. Poiché l’indice risultante è essenzialmente un albero binario, questo ci permette di eseguire la nostra ricerca con complessità O(log n).
ANNOY, visualizzato. Fonte dell’immagine: https://github.com/spotify/annoy
Metriche di similarità comunemente usate
I migliori database vettoriali sono inutili senza metriche di similarità: metodi per calcolare la distanza tra due vettori. Esistono numerose metriche, quindi qui discuteremo solo il sottoinsieme più comunemente usato.
Metriche di similarità per vettori in virgola mobile
Le metriche di similarità più comuni per vettori in virgola mobile sono, senza un ordine particolare, distanza L1, distanza L2 e similarità coseno. I primi due valori sono metriche di distanza (valori più bassi implicano maggiore similarità, mentre valori più alti implicano minore similarità), mentre la similarità coseno è una metrica di similarità (valori più alti implicano maggiore similarità).
La distanza L1 è anche comunemente chiamata distanza di Manhattan, nome appropriato dato dal fatto che andare dal punto A al punto B a Manhattan richiede di muoversi lungo una delle due direzioni perpendicolari. La seconda equazione, la distanza L2, è semplicemente la distanza tra due vettori nello spazio euclideo. La terza e ultima equazione è la distanza coseno, equivalente al coseno dell’angolo tra due vettori. Nota che l’equazione per la similarità coseno risulta essere il prodotto scalare tra le versioni normalizzate dei vettori di input a e b.
Con un po’ di matematica, possiamo anche mostrare che la distanza L2 e la similarità coseno sono effettivamente equivalenti quando si tratta di classificazione della similarità per vettori a norma unitaria:
Ricorda che i vettori a norma unitaria hanno una magnitudine di 1:
Con questo, otteniamo:
Poiché abbiamo vettori a norma unitaria, la distanza coseno risulta essere il prodotto scalare tra a e b (il denominatore nell’equazione 3 sopra risulta essere 1):
Essenzialmente, per vettori a norma unitaria, la distanza L2 e la similarità coseno sono funzionalmente equivalenti! Ricorda sempre di normalizzare i tuoi embeddings.
Metriche di similarità per vettori binari
I vettori binari, come suggerisce il loro nome, non hanno metriche basate sull’aritmetica alla maniera dei vettori in virgola mobile. Le metriche di similarità per vettori binari si basano invece sulla matematica degli insiemi, sulla manipolazione dei bit o su una combinazione di entrambe (va bene, anch’io odio la matematica discreta). Ecco le formule per due metriche di similarità per vettori binari comunemente usate:
La prima equazione è chiamata distanza di Tanimoto/Jaccard ed è essenzialmente una misura della quantità di sovrapposizione tra due vettori binari. La seconda equazione è la distanza di Hamming ed è un conteggio del numero di elementi vettoriali in a e b che differiscono tra loro.
Molto probabilmente puoi ignorare senza problemi queste metriche di similarità, poiché la maggior parte delle applicazioni utilizza la similarità del coseno su embedding in virgola mobile.
Conclusione
In questo tutorial, abbiamo dato uno sguardo alla ricerca vettoriale, insieme ad alcuni algoritmi comuni di ricerca vettoriale e metriche di distanza. Ecco alcuni punti chiave:
I vettori di embedding sono rappresentazioni potenti, sia in termini di distanza tra i vettori sia in termini di aritmetica vettoriale. Applicando una generosa quantità di algebra vettoriale agli embedding, possiamo eseguire analisi semantica scalabile usando solo operatori matematici di base.
La ricerca vettoriale semantica supera la limitazione della ricerca per parole chiave consentendoti di effettuare ricerche in base al significato della tua query. Consente un recupero rapido delle risposte eseguendo una ricerca vettoriale.
Esiste un’ampia varietà di algoritmi di ricerca approssimata dei vicini più prossimi e/o tipi di indice tra cui scegliere. Quello più comunemente usato oggi è HNSW, ma un algoritmo di indicizzazione diverso potrebbe funzionare meglio per la tua particolare applicazione, a seconda del numero totale di embedding vettoriali che hai oltre alla lunghezza di ciascun singolo vettore.
Le due principali metriche di distanza utilizzate oggi sono la distanza L2/Euclidea e la distanza del coseno. Queste due metriche, quando utilizzate su embedding normalizzati, sono funzionalmente equivalenti.
Grazie per averci seguito in questo tutorial! La ricerca vettoriale è una parte fondamentale di Milvus, e continuerà a esserlo. Nei tutorial futuri, approfondiremo alcuni degli algoritmi ANNS più comunemente utilizzati: HNSW e ScaNN.
Dai un’altra occhiata ai corsi Vector Database 101
- Introduzione ai dati non strutturati
- Che cos’è un database vettoriale?
- Confronto tra database vettoriali, librerie di ricerca vettoriale e plugin di ricerca vettoriale
- Introduzione a Milvus
- Guida rapida a Milvus
- Introduzione alla ricerca di similarità vettoriale
- Fondamenti degli indici vettoriali e indice a file invertito
- Quantizzazione scalare e quantizzazione del prodotto
- Hierarchical Navigable Small Worlds (HNSW)
- Approximate Nearest Neighbors Oh Yeah (ANNOY)
- Scegliere l’indice vettoriale giusto per il tuo progetto
- DiskANN e l’algoritmo Vamana
Continua a leggere
Milvus WebUI: A Visual Management Tool for Your Vector Database
Explore Milvus WebUI to monitor, manage, and optimize your vector database with real-time insights, performance tracking, and system health monitoring.
Vector Databases vs. Graph Databases
Use a vector database for AI-powered similarity search; use a graph database for complex relationship-based queries and network analysis.
Introducing DeepSearcher: A Local Open Source Deep Research
In contrast to OpenAI’s Deep Research, this example ran locally, using only open-source models and tools like Milvus and LangChain.