Ricerca di Similarità, Parte 3 Combinazione dell’Indice di File Invertito e della Quantizzazione del Prodotto

Combining Inverted File Index and Product Quantization for Similarity Search, Part 3.

Scopri come combinare due indici di ricerca di similarità di base per ottenere i vantaggi di entrambi

La ricerca di similarità è un problema in cui, data una query, 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 dell’NLP, nei motori di ricerca o nei sistemi di raccomandazione in cui è necessario recuperare i documenti o gli oggetti più rilevanti per una query. Esiste una grande varietà di modi diversi per migliorare le prestazioni di ricerca in volumi massicci di dati.

Nelle prime due parti di questa serie abbiamo discusso due algoritmi fondamentali nell’information retrieval: l’indice di file invertito e la quantizzazione del prodotto. Entrambi ottimizzano le prestazioni di ricerca, ma si concentrano su aspetti diversi: il primo accelera la velocità di ricerca, mentre il secondo comprime i vettori in una rappresentazione più piccola ed efficiente in termini di memoria.

• Questo articolo mette alla prova il senso dell’umorismo di ChatGPT oltre il 90% delle battute generate da ChatGPT sono le stesse 25 battute.
• Incontra FinGPT un modello di linguaggio finanziario open-source di grande dimensione (LLM)
• Come l’IA sta rendendo le foreste più sicure dagli incendi?

Ricerca di similarità, Parte 1: kNN & Indice di file invertito

La ricerca di similarità è un problema popolare in cui, data una query Q, dobbiamo trovare i documenti più simili ad essa tra tutti…

towardsdatascience.com

Ricerca di similarità, Parte 2: Quantizzazione del prodotto

Nella prima parte di questa serie di articoli abbiamo esaminato la struttura di kNN e dell’indice di file invertito per eseguire la similarità…

Nisoo.com

Dato che entrambi gli algoritmi si concentrano su aspetti diversi, la domanda che sorge naturalmente è se sia possibile unire questi due algoritmi in uno nuovo

In questo articolo, combineremo i vantaggi di entrambi gli approcci per produrre un algoritmo veloce ed efficiente in termini di memoria. Per informazione, la maggior parte delle idee discusse si baserà su questo articolo.

Prima di entrare nei dettagli, è necessario capire cosa sono i vettori residui e ottenere un’intuizione semplice sulle loro proprietà utili. Li useremo in seguito durante la progettazione di un algoritmo.

Vettori residui

Immagina che sia stato eseguito un algoritmo di clustering e che abbia prodotto diversi cluster. Ogni cluster ha un centroide e punti associati ad esso. Il residuo è uno scostamento di un punto (vettore) dal suo centroide. Fondamentalmente, per trovare il residuo per un particolare vettore, il vettore deve essere sottratto dal suo centroide.

Se il cluster è stato costruito dall’algoritmo k-means, allora il centroide del cluster è la media di tutti i punti appartenenti a quel cluster. Pertanto, trovare un residuo da qualsiasi punto sarebbe equivalente a sottrarre la media di un cluster da esso. Sottraendo il valore medio da tutti i punti appartenenti a un particolare cluster, i punti sarebbero centrati intorno allo zero.

Possiamo osservare un fatto utile:

La sostituzione dei vettori originali con i loro residui non cambia la loro posizione relativa l’uno rispetto all’altro.

Cioè, la distanza tra i vettori rimane sempre la stessa. Guardiamo semplicemente le due equazioni qui sotto.

La prima equazione è la formula della distanza euclidea tra una coppia di vettori. Nella seconda equazione, il valore medio del cluster viene sottratto ad entrambi i vettori. Possiamo vedere che il termine medio si annulla semplicemente: l’intera espressione diventa identica alla distanza euclidea nella prima equazione!

Abbiamo dimostrato questa affermazione utilizzando la formula per la metrica L2 (distanza euclidea). È importante ricordare che questa regola potrebbe non funzionare per altre metriche.

Quindi, se per una determinata query l’obiettivo è trovare il vicino più vicino, è possibile sottrarre semplicemente la media del cluster dalla query e procedere alla normale procedura di ricerca tra i residui.

Adesso, guardiamo un altro esempio nella figura qui sotto con due cluster in cui i residui per i vettori di ogni cluster vengono calcolati separatamente.

Sottrarre la media del centroide corrispondente da ogni vettore di un cluster centrerà tutti i vettori del dataset intorno allo 0.

Questa è un’osservazione utile che verrà utilizzata in futuro. Inoltre, per una determinata query, possiamo calcolare i residui della query per tutti i cluster. I residui della query ci consentono di calcolare le distanze dai residui originali del cluster.

Formazione

Dopo aver preso in considerazione le osservazioni utili nella sezione precedente, possiamo iniziare a progettare l’algoritmo.

Dato un database di vettori, viene costruito un indice a file invertito che divide l’insieme di vettori in n partizioni Voronoi e riduce così la portata della ricerca durante l’infrazione.

All’interno di ogni partizione Voronoi, le coordinate del centroide vengono sottratte da ogni vettore. Di conseguenza, i vettori di tutte le partizioni diventano più vicini l’uno all’altro e centrati intorno allo 0. In questo momento, non c’è bisogno dei vettori originali poiché memorizziamo invece i loro residui.

Dopo di che, l’algoritmo di quantizzazione del prodotto viene eseguito su vettori da tutte le partizioni.

Aspetto importante: la quantizzazione del prodotto non viene eseguita per ogni partizione separatamente – sarebbe inefficiente perché il numero di partizioni tende di solito ad essere elevato e potrebbe risultare in una grande quantità di memoria necessaria per memorizzare tutti i codebook. Invece, l’algoritmo viene eseguito per tutti i residui di tutte le partizioni contemporaneamente.

In effetti, ora ogni sottospazio contiene subvettori da diverse partizioni Voronoi. Quindi, per ogni sottospazio, viene eseguito un algoritmo di clustering e vengono creati k cluster con i loro centroidi, come al solito.

Qual è stata l’importanza della sostituzione dei vettori con i loro residui? Se i vettori non fossero stati sostituiti con i loro residui, ogni sottospazio avrebbe contenuto subvettori più vari (perché i sottospazi avrebbero memorizzato subvettori da diverse partizioni Voronoi non intersecanti che potevano essere molto distanti l’uno dall’altro nello spazio). Ora i vettori (residui) dalle diverse partizioni si sovrappongono tra loro. Poiché ora c’è meno varietà in ogni sottospazio, ci vogliono meno valori di riproduzione per rappresentare efficacemente i vettori. In altre parole:

Con la stessa lunghezza dei codici PQ utilizzati in precedenza, i vettori possono essere rappresentati in modo più accurato perché hanno meno varianza.

Infrazione

Per una determinata query, vengono trovati i k centroidi più vicini delle partizioni Voronoi. Tutti i punti all’interno di queste regioni vengono considerati come candidati. Poiché i vettori originali sono stati inizialmente sostituiti dai loro residui in ogni regione Voronoi, il residuo del vettore di query deve essere calcolato anche questo caso, il residuo della query deve essere calcolato separatamente per ogni partizione Voronoi (perché ogni regione ha centroidi diversi). Solo i residui dalle partizioni Voronoi scelte vanno ai candidati.

Il residuo della query viene quindi diviso in sottovettori. Come nell’algoritmo di quantizzazione originale del prodotto, per ogni sottospazio viene calcolata la matrice delle distanze d contenente le distanze dai centroidi del sottospazio al sottovettore della query. È essenziale tenere presente che il residuo della query è diverso per ogni partizione di Voronoi. In sostanza significa che la matrice delle distanze d deve essere calcolata separatamente per ciascuno dei residui della query. Questo è il prezzo computazionale per l’ottimizzazione desiderata.

Infine, le distanze parziali vengono sommate come è stato fatto in precedenza nell’algoritmo di quantizzazione del prodotto.

Ordinamento dei risultati

Dopo che tutte le distanze sono state calcolate, è necessario selezionare i k vicini più vicini. Per farlo in modo efficiente, gli autori propongono di mantenere una struttura dati MaxHeap. Ha una capacità limitata di k e in ogni passaggio, memorizza le k distanze più piccole correnti. Ogni volta che viene calcolata una nuova distanza, il suo valore viene aggiunto a MaxHeap solo se il valore calcolato è inferiore al valore più grande in MaxHeap. Dopo il calcolo di tutte le distanze, la risposta alla query è già memorizzata in MaxHeap. Il vantaggio dell’utilizzo di MaxHeap è il suo rapido tempo di costruzione che è di O(n).

Prestazioni

L’algoritmo sfrutta sia l’indice del file invertito che la quantizzazione del prodotto. A seconda del numero di partizioni Voronoi sondati durante l’infrazione, lo stesso numero di matrici di sottovettore-a-centroide d deve essere calcolato e memorizzato nella memoria. Questo potrebbe sembrare uno svantaggio, ma confrontandolo con gli svantaggi complessivi, è un compromesso abbastanza buono.

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 memorizzare i dati in modo efficiente e svolgere le query.

In base alle informazioni dalla documentazione di Faiss, vedremo come gli indici del file invertito e della quantizzazione del prodotto possono essere combinati insieme per formare un nuovo indice.

Faiss implementa l’algoritmo descritto nella classe IndexIVFPQ che accetta i seguenti argomenti:

• quantizer: specifica come viene calcolata la distanza tra i vettori.
• d: dimensionalità dei dati.
• nlist: numero di partizioni Voronoi.
• M: numero di sottospazi.
• nbits: numero di bit necessari per codificare un singolo ID di cluster. Ciò significa che il numero totale di cluster in un singolo sottospazio sarà pari a k = 2^nbits.

Inoltre, è possibile regolare l’attributo nprobe che specifica quante partizioni Voronoi devono essere utilizzate per la ricerca di candidati durante l’infrazione. La modifica di questo parametro non richiede la riformazione.

La memoria richiesta per memorizzare un singolo vettore è la stessa del metodo di quantizzazione del prodotto originale, tranne che ora aggiungiamo altri 8 byte per memorizzare le informazioni sul vettore nell’indice del file invertito.

Conclusione

Utilizzando le conoscenze delle parti precedenti dell’articolo, abbiamo esaminato l’implementazione di un algoritmo all’avanguardia che raggiunge una compressione della memoria elevata e una velocità di ricerca accelerata. Questo algoritmo è ampiamente utilizzato nei sistemi di recupero delle informazioni quando si tratta di volumi di dati massicci.

Risorse

• Quantizzazione del prodotto per la ricerca più vicina
• Documentazione di Faiss
• Repository di Faiss
• Riassunto degli indici di Faiss

Tutte le immagini, a meno che non sia diversamente indicato, sono dell’autore.