Ricerca approssimativa del vicino più prossimo nei sistemi di raccomandazione
Introduzione
Nel febbraio 2024, abbiamo ascoltato Yury Malkov al SF Unstructured Data Meetup parlare di Approximate Nearest Neighbor (ANN) e del suo ruolo chiave nei sistemi di raccomandazione. La ricerca ANN è già integrata negli stack di produzione degli strumenti più popolari al mondo. Yury ci aiuta a comprendere i concetti chiave e il contesto che hanno guidato l’adozione di ANN nei sistemi di raccomandazione su larga scala.
Link al replay su YouTube del talk di Yury Malkov: Guarda il talk su YouTube
Perché dovrebbe interessarti ANN?
Yuri Malkov è letteralmente un genio. Se non mi credi, dai un’occhiata al suo profilo Google Scholar https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Fisico, ricercatore laser e inventore di HNSW - un algoritmo di indicizzazione basato su grafi ora integrato out of the box in tutti i principali database vettoriali. Ora lavora per OpenAI come Research Scientist. Dimmi che non sembra una plausibile biografia di Tony Stark nel 2024.
Detto questo, approfondiamo il talk di Yuri su “Approximate Nearest Neighbor Search in Recommender Systems.”
Che cos’è la ricerca ANN?
Saremo brevi, dato che abbiamo già trattato le basi della ricerca ANN in breve e in modo approfondito.
Le ricerche dei vicini più prossimi sono un insieme di tecniche statistiche che possiamo usare per effettuare ricerche di similarità in applicazioni di machine learning o data science. A differenza del loro cugino speciale al gusto K, KNN, che confronta ogni datapoint in un sistema con tutti gli altri quando completa la ricerca, gli algoritmi di ricerca ANN usano varie tecniche di indicizzazione per restituire vicini più prossimi approssimativi. Le ricerche ANN sono diventate fondamentali per molte applicazioni e tecnologie rivolte ai clienti oggi. Dai motori di ricerca (come Google, non la ricerca vettoriale) ai siti di social media, ANN e i sistemi di raccomandazione sono già integrati lungo tutto lo stack, in produzione.
ANN non era l’unica soluzione per i sistemi di raccomandazione. Quindi come siamo arrivati fin qui? Esamineremo le soluzioni ANN mature oggi presenti sul mercato, cosa rende i sistemi di raccomandazione un problema difficile per gli algoritmi di vicini più prossimi, come gli sviluppatori hanno strutturato i sistemi di raccomandazione e come i ricercatori stanno usando ANN per riscrivere lo stack dei sistemi di raccomandazione. Yuri osserva nel suo talk che esistono molte soluzioni ANN mature. Molti di questi argomenti sono trattati in modo approfondito nella nostra Guida visiva alla scelta di un indice vettoriale, ma ho preparato una tabella degli strumenti elencati nella presentazione di Yuri.
Tabella degli indici ANN menzionati
| Indice ANN | Classificazione | Scenario |
|---|---|---|
| LSH | Indice basato su grafo | - Grandi dataset multidimensionali altamente complessi - Usa la distanza euclidea per raggruppare i datapoint in bucket - Restituisce solo i risultati più vicini |
| HNSW | Indice basato su grafo | - Query ad altissima velocità - Richiede un tasso di recall il più alto possibile - Grandi risorse di memoria |
| SCANN | Indice basato su quantizzazione | - Query ad altissima velocità - Richiede un tasso di recall il più alto possibile - Grandi risorse di memoria |
| IVF_PQ | Indice basato su quantizzazione (invertito) | - Indice invertito - Query ad altissima velocità - Risorse di memoria limitate - Accetta un compromesso sostanziale nel tasso di recall |
| IVF_HSNW | Indice basato su grafo (invertito) | - Indice invertito - Basato su HSNW - Richiede un tasso di recall il più alto possibile - Grandi risorse di memoria |
| DiskANN | Indici di vicini più prossimi multipli | - Modifiche ANN e toolkit per ricerche ANN |
| ANNOY | Indici di vicini più prossimi multipli | - Implementazioni LSH o KDtrees - Ricerca efficiente in memoria e veloce in spazi ad alta dimensionalità |
| Molti altri | - | - FAISS, cuHNSW, ngt, song |
Informazioni sui benchmark ANN
Yuri passa in rassegna il benchmarking ANN a velocità lampo, indicando ANNBenchmarks con l’avvertenza che il benchmarking degli algoritmi ANN inversi può diventare complicato. Rallentiamo:
Che cos’è ANN-Benchmarks?
ANN-Benchmarks è un ambiente di benchmarking che valuta vari algoritmi di ricerca approssimata dei vicini più prossimi, fornendo sul proprio sito risultati suddivisi per misura di distanza e dataset. I benchmark mostrano metriche di performance come il tasso di recall e le query al secondo, e gli utenti possono contribuire inviando il proprio codice tramite pull request su GitHub .
Sebbene sia possibile trovare dati di benchmarking degli algoritmi ANN in molti posti (github, ANN-Benchmarks, persino nella documentazione del prodotto), vedrai sempre grafici che tracciano QPS - query al secondo. Più QPS, meglio è! Vroom vroom!
Una nota sulla scelta degli algoritmi ANN (e di altri algoritmi di ricerca vettoriale)
Se guardare i benchmark degli algoritmi ti fa venire il sangue dal naso, non sei solo. Ecco perché il team Milvus ha creato Knowhere. Knowhere è il motore di esecuzione vettoriale open-source centrale di Milvus, che incorpora diverse librerie di ricerca per similarità vettoriale, tra cui Faiss, Hnswlib e Annoy. Knowhere controlla su quale hardware (CPU o GPU) eseguire la costruzione degli indici e le richieste di ricerca. È così che Knowhere prende il suo nome: sapere dove eseguire le operazioni. Altri tipi di hardware, tra cui DPU e TPU, saranno supportati nelle release future.
Basandosi su Knowhere - il team di Zilliz Cloud ha rilasciato Cardinal, che è il motore di ricerca vettoriale principale di Zilliz. Questo motore di ricerca ha già dimostrato un aumento delle prestazioni di tre volte rispetto alla versione precedente, offrendo prestazioni di ricerca (QPS) che raggiungono dieci volte quelle di Milvus. La ricerca ANN è da tempo integrata nei sistemi di raccomandazione. Per scoprire perché gli algoritmi di ricerca ANN sono diventati così popolari nei sistemi di raccomandazione in produzione, dobbiamo fare un passo indietro e guardare alle motivazioni, all’architettura e alle soluzioni innovative che ANN ha superato.
Applicazioni dei sistemi di raccomandazione su larga scala: motivazioni e sfide
Obiettivo: L’obiettivo di base di tutti i sistemi di raccomandazione è restituire un elemento (video, prodotto, documento, messaggio) a una query (utente, applicazione, contesto). Ricorda questa relazione elemento-query: è importante per comprendere gli algoritmi di ricerca (raccomandazione).
Mercato: Le tecnologie di raccomandazione hanno presentato e rappresentano un grande mercato data la loro capacità di generare comportamenti dei consumatori.
Sfide tipiche su larga scala:
Generalizzabilità:
- Tradizionalmente i sistemi di raccomandazione hanno avuto una bassa generalizzabilità, in gran parte a causa della dipendenza da dati, modelli e infrastrutture interni.
Corpus enormi:
Grandi set di dati (da milioni a trilioni di elementi, query) generano elevati costi di inferenza.
Efficienza e contenimento dei costi di inferenza sono molto importanti.
L’elaborazione pesante di video e immagini ha richiesto ingegneri dedicati per mantenere l’infrastruttura.
Soluzioni, maturità:
Soluzioni/infrastrutture interne solitamente sviluppate internamente (ad es. Google, Meta, X,)
Tipicamente un funnel di raccomandazione a più stadi (vedi sotto) per risparmiare sui costi di inferenza
Gli strumenti pronti all’uso hanno guadagnato popolarità e trazione con l’ascesa dei database vettoriali e degli LLM.
Tipico funnel a più stadi
Yuri approfondisce un diagramma di un tipico sistema di raccomandazione in produzione. Nell’esempio seguente per la raccomandazione video, a un’applicazione vengono forniti elementi e una query e deve restituire un pin di raccomandazione video. Queste applicazioni sono funnel a più stadi in cui i candidati degli elementi vengono generati e sottoposti a modelli di ranking successivi per affinare i risultati di ricerca.
Passaggio 1: Generazione dei candidati - ANN + Modello leggero
In questa fase iniziale, il sistema utilizza vicini più prossimi approssimati per setacciare rapidamente il vasto database di video e identificare un elenco preliminare di video candidati pertinenti alla query dell’utente. Questo processo è progettato per essere rapido ed efficiente, gestendo potenzialmente milioni di elementi concentrandosi su quelli con maggiore probabilità di corrispondere alle caratteristiche della query. Il 'Modello leggero' utilizzato in questo passaggio è in genere un modello più semplice e meno intensivo dal punto di vista computazionale, che aiuta a restringere il pool di candidati a quelli che meglio si allineano agli interessi o ai termini di ricerca dell’utente.
Passaggio 2: Ranking leggero - Forza bruta + Modello intermedio
Una volta generato un insieme di candidati, il passaggio successivo comporta un esame più dettagliato di questi candidati. Ciò viene fatto utilizzando un approccio a 'Forza bruta' in cui ogni candidato viene valutato in modo più approfondito utilizzando un 'Modello intermedio', che è più complesso del Modello leggero utilizzato nel primo passaggio. Questo modello prende in considerazione funzionalità aggiuntive, come metriche di coinvolgimento degli utenti, rilevanza contestuale e qualità dei contenuti, per classificare i candidati in modo che i video più pertinenti vengano spinti verso la parte superiore dell’elenco delle raccomandazioni. Questo passaggio trova un equilibrio tra prestazioni e precisione, affinando la selezione concentrandosi maggiormente su qualità e rilevanza.
Passaggio 3: Ranking completo - Forza bruta + Modello pesante
La fase finale nel processo di raccomandazione è lo stadio di Full Ranking, che impiega un "Heavy Model"—il più sofisticato e dispendioso in termini di risorse tra i modelli utilizzati. Questo modello incorpora un’ampia gamma di segnali e punti dati, inclusa un’analisi più approfondita del profilo utente, preferenze a lungo termine, analisi dettagliata dei contenuti e possibilmente dati in tempo reale come le tendenze di visualizzazione attuali. Il metodo Brute Force applicato qui garantisce che ogni video venga valutato e classificato in modo completo, assicurando che le raccomandazioni finali siano altamente personalizzate e pertinenti. Questo passaggio assicura raccomandazioni della massima qualità, ma richiede più potenza di elaborazione e tempo, rendendolo adatto al perfezionamento finale dell’elenco delle raccomandazioni.
Perché HSNW vacilla nei sistemi di raccomandazione tradizionali e soluzioni (imperfette) Sapendo che i sistemi di raccomandazione in produzione su larga scala sono vincolati da grandi dataset e dai costi associati, Yuri afferma che elementi e query si trovano su due - piani incompatibili. Quando query ed elementi risiedono in spazi diversi e incompatibili, gli algoritmi tradizionali di ricerca per similarità come Hierarchical Navigable Small World (HNSW) incontrano difficoltà perché questi algoritmi dipendono da una relazione misurabile o da una funzione di distanza direttamente tra la query e gli elementi. Senza una metrica chiara per valutare la vicinanza, HNSW non può svolgere efficacemente la sua funzione, che è navigare attraverso un grafo di elementi per trovare le corrispondenze più vicine a una query.****
Una panoramica delle soluzioni innovative all’incompatibilità elemento-query
Distanza L2 sui vettori di dati
Come funziona: Usa la distanza L2 tra input di dati vettorializzati per creare una struttura di grafo surrogata per i sistemi di raccomandazione.
Pro: Semplifica il processo utilizzando un calcolo della distanza diretto, offrendo un vantaggio in termini di velocità durante le fasi di generazione dei candidati e di ri-ranking.
Contro: Potrebbe non catturare relazioni complesse o sfumature tra elementi e query con la stessa efficacia di modelli più sofisticati, portando potenzialmente a raccomandazioni meno personalizzate.
Ranking su grafo bipartito
Come funziona: Proietta elementi e query in un grafo bipartito in cui gli elementi sono collegati ai loro utenti o query più vicini, consentendo di generare archi basati su queste relazioni.
Pro: Efficace nello strutturare dati relazionali tra utenti ed elementi, sebbene i confronti diretti con altri metodi siano limitati.
Contro: La costruzione e la manutenzione del grafo bipartito possono richiedere molte risorse, e l’efficacia può variare notevolmente a seconda della densità e della qualità delle connessioni del grafo.
Fonte dell’immagine: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Ri-ranking su grafo (incentrato sul testo)
Come funziona: Utilizza un grafo creato da vettori per la generazione dei candidati, applicando direttamente un ranker pesante al grafo per il recupero di testo, il che migliora la qualità dei risultati.
Pro: Elimina il tradizionale funnel a più fasi, consentendo la correzione degli errori commessi nelle fasi precedenti di filtraggio dei candidati.
Contro: Principalmente efficace per il recupero basato su testo; potrebbe non essere altrettanto efficace in altri contesti in cui dominano caratteristiche non testuali, limitandone l’applicabilità.
Fonte dell’immagine: https://arxiv.org/pdf/2208.08942
Ricerca su grafo a cascata
Come funziona: Inizia con una funzione di distanza leggera per la ricerca iniziale e passa senza interruzioni a una funzione di distanza più pesante durante il processo di ricerca.
Pro: Offre flessibilità adattando la funzione di distanza in tempo reale, ottimizzando sia la velocità sia l’accuratezza durante tutto il processo di ricerca.
Contro: La complessità della gestione e dell’ottimizzazione di due funzioni di distanza può aumentare l’overhead computazionale e la complessità del sistema, con un potenziale impatto sulla scalabilità.
Fonte dell’immagine: https://arxiv.org/pdf/2202.10226
Perché la ricerca ANN è così popolare?
Mettendo insieme tutto questo – Yuri ha delineato un buon quadro del motivo per cui gli algoritmi ANN hanno visto un’implementazione così estesa, soprattutto in applicazioni (come i sistemi di raccomandazione su larga scala) che lavorano con dataset ad alta dimensionalità.
Matching abbastanza buono (o migliore) - Se non hai bisogno di una corrispondenza perfetta, una variante ANN è quasi sempre una soluzione migliore rispetto ad altri algoritmi NN.
Flessibilità - con un’ampia gamma di implementazioni, uno sviluppatore può scegliere il costo
Maturità - Gli ANN sono stati implementati in tutti i principali linguaggi di programmazione, e ci sono diversi framework popolari per selezionare ed eseguire ricerche ANN.
Ulteriori risorse
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Link al replay su YouTube dell’intervento di Yury Malkov: Guarda l’intervento su YouTube
Continua a leggere
Zilliz Cloud Enterprise Vector Search Powers High-Performance AI on AWS
Zilliz Cloud on AWS powers secure, scalable, ultra-fast vector search for enterprise AI apps, with BYOC, sub-10ms latency, and zero-DevOps simplicity.
Building RAG Pipelines for Real-Time Data with Cloudera and Milvus
explore how Cloudera can be integrated with Milvus to effectively implement some of the key functionalities of RAG pipelines.
Proactive Monitoring for Vector Database: Zilliz Cloud Integrates with Datadog
we're excited to announce Zilliz Cloud's integration with Datadog, enabling comprehensive monitoring and observability for your vectorDB deployments.