Esplorando il percorso per la ricerca rapida del vicino più vicino con i piccoli mondi navigabili gerarchici
Hierarchical Navigable Small World (HNSW) è diventato popolare come uno degli approcci più performanti per la ricerca approssimativa del vicino più vicino. HNSW è però un po’ complesso e le descrizioni spesso mancano di una spiegazione completa e intuitiva. Questo post intraprende un viaggio attraverso la storia dell’idea HNSW per aiutare a spiegare cosa significa realmente “piccolo mondo navigabile gerarchico” e perché è efficace.
- Ricerca approssimativa del vicino più vicino
- Piccoli mondi
- Piccoli mondi navigabili
- Piccoli mondi navigabili gerarchici
- Riepilogo
- Appendice
– Ricerca migliorata
– Ricerca e inserimento HNSW
– Inserimento migliorato - Riferimenti
Un’applicazione comune dell’apprendimento automatico è ricerca del vicino più vicinociò significa trovare gli elementi più simili* a un target, ad esempio per consigliare articoli simili alle preferenze di un utente o per cercare elementi simili alla query di ricerca di un utente.
Il metodo semplice consiste nel calcolare la somiglianza di ogni elemento con l’obiettivo e restituire quelli più vicini. Tuttavia, se è presente un numero elevato di elementi (forse milioni), l’operazione sarà lenta.
Invece, possiamo usare una struttura chiamata an indice per rendere le cose molto più veloci.
Esiste tuttavia un compromesso. A differenza del metodo semplice, gli indici danno solo risultati approssimativi: potremmo non recuperare tutti i vicini più vicini (cioè il ricordo potrebbe essere inferiore al 100%).
Esistono diversi tipi di indice (ad esempio hashing sensibile alla località; indice di file invertito), ma HNSW si è dimostrato particolarmente efficace su vari set di dati, raggiungendo velocità elevate mantenendo un elevato richiamo.
*In genere, gli elementi sono rappresentati come incastriche sono vettori prodotti da un modello di machine learning; la somiglianza tra gli elementi corrisponde a distanza tra gli incastri. Questo post parlerà solitamente di vettori e distanze, sebbene in generale HNSW possa gestire qualsiasi tipo di elemento con un certo grado di somiglianza.
I mondi piccoli furono notoriamente studiati nell’esperimento del piccolo mondo di Stanley Milgram (1).
Ai partecipanti è stata consegnata una lettera contenente l’indirizzo e altri dettagli di base di un individuo target scelto a caso, insieme alle istruzioni dell’esperimento. Nell’improbabile caso in cui conoscessero personalmente l’obiettivo, veniva loro chiesto di inviare loro la lettera; altrimenti, è stato detto loro di pensare a qualcuno che conoscevano e che aveva maggiori probabilità di conoscere l’obiettivo e di inviare loro la lettera.
La conclusione sorprendente è stata che le lettere venivano in genere inviate solo circa sei volte prima di raggiungere l’obiettivo, a dimostrazione della famosa idea dei “sei gradi di separazione”: due persone qualsiasi possono solitamente essere collegate da una piccola catena di amici.
Nel campo matematico della teoria dei grafi, a grafico è un insieme di punti, alcuni dei quali sono collegati. Possiamo pensare a un social network come a un grafico, con le persone come punti e le amicizie come connessioni. L’esperimento del mondo piccolo ha rilevato che la maggior parte delle coppie di punti in questo grafico sono collegate da percorsi brevi con un numero limitato di passaggi. (Questo è descritto tecnicamente come il grafico che ha un minimo diametro.)
Avere percorsi brevi non è di per sé così sorprendente: la maggior parte dei grafici ha questa proprietà, compresi i grafici creati semplicemente collegando coppie casuali di punti. Ma i social network non sono collegati in modo casuale, lo sono altamente Locale: gli amici tendono a vivere vicini e se conosci due persone, è molto probabile che anche loro si conoscano. (Questo è descritto tecnicamente come il grafico che ha un massimo coefficiente di clustering.) La cosa sorprendente dell’esperimento del piccolo mondo è che due punti distanti sono separati solo da un breve percorso nonostante le connessioni siano tipicamente a corto raggio.
In casi come questi, quando un grafo ha molte connessioni locali, ma ha anche percorsi brevi, diciamo che il grafo è a mondo piccolo.
Un altro buon esempio di mondo piccolo è la rete aeroportuale globale. Gli aeroporti della stessa regione sono molto collegati tra loro, ma è possibile effettuare un lungo viaggio in poche fermate utilizzando i principali hub aeroportuali. Ad esempio, un viaggio da Manchester, nel Regno Unito, a Osaka, in Giappone, in genere inizia con un volo locale da Manchester a Londra, quindi un volo a lunga percorrenza da Londra a Tokyo e infine un altro volo locale da Tokyo a Osaka. Gli hub a lungo raggio sono un modo comune per raggiungere la proprietà del piccolo mondo.
Un ultimo esempio interessante di grafici con la proprietà del mondo piccolo sono le reti neurali biologiche come il cervello umano.
Nei grafici del mondo di piccole dimensioni, possiamo raggiungere rapidamente un obiettivo in pochi passaggi. Ciò suggerisce un’idea promettente per la ricerca del vicino più vicino: forse se creiamo connessioni tra i nostri vettori in modo tale da formare un piccolo grafico mondiale, possiamo trovare rapidamente i vettori vicino a un bersaglio partendo da un vettore “punto di ingresso” arbitrario e quindi navigando attraverso il grafico verso l’obiettivo.
Questa possibilità è stata esplorata da Kleinberg (2). Notò che l’esistenza di percorsi brevi non era l’unica cosa interessante dell’esperimento di Miller: era anche sorprendente che le persone fossero in grado di Trovare questi brevi percorsi, senza utilizzare alcuna conoscenza globale del grafico. Piuttosto, la gente stava seguendo una strada semplice algoritmo avido. Ad ogni passaggio, hanno esaminato ciascuna delle loro connessioni immediate e l’hanno inviata a quella che ritenevano fosse più vicina all’obiettivo. Possiamo usare un algoritmo simile per cercare un grafico che collega i vettori.
Kleinberg voleva sapere se questo avido algoritmo avrebbe sempre trovato una strada breve. Ha eseguito semplici simulazioni di piccoli mondi in cui tutti i punti erano collegati ai loro immediati vicini, con ulteriori connessioni più lunghe create tra punti casuali. Scoprì che l’algoritmo avido avrebbe trovato un percorso breve solo in determinate condizioni, a seconda della lunghezza delle connessioni a lungo raggio.
Se le connessioni a lungo raggio fossero troppo lunghe (come avveniva quando collegavano coppie di punti in posizioni del tutto casuali), l’algoritmo goloso potrebbe seguire una connessione a lungo raggio per raggiungere rapidamente la zona approssimativa del bersaglio, ma dopodiché le connessioni a lungo raggio erano inutili e il percorso doveva passare attraverso le connessioni locali per avvicinarsi. D’altro canto, se i collegamenti a lungo raggio fossero troppo brevi, sarebbero necessari semplicemente troppi passi per raggiungere la zona dell’obiettivo.
Se, tuttavia, le lunghezze delle connessioni a lungo raggio fossero giuste (per essere precisi, se fossero distribuite uniformemente, in modo che tutte le lunghezze fossero ugualmente probabili), l’algoritmo avido raggiungerebbe tipicamente le vicinanze del bersaglio in un tempo particolarmente piccolo. numero di passi (per essere più precisi, un numero proporzionale a registro(n)Dove N è il numero di punti nel grafico).
In casi come questo, in cui l’algoritmo avido può trovare l’obiettivo in un numero limitato di passaggi, diciamo che il mondo piccolo è un navigabile piccolo mondo (NSW).
Un NSW sembra un indice ideale per i nostri vettori, ma per i vettori in uno spazio complesso e ad alta dimensione, non è chiaro come costruirne effettivamente uno. Fortunatamente, Malkov et al. (3) ha scoperto un metodo: inseriamo nel grafico un vettore scelto casualmente alla volta e lo colleghiamo a un piccolo numero M dei vicini più vicini già inseriti.
Questo metodo è straordinariamente semplice e non richiede una comprensione globale di come i vettori sono distribuiti nello spazio. È anche molto efficiente, poiché possiamo utilizzare il grafico costruito finora per eseguire la ricerca del vicino più vicino per inserire ciascun vettore.
Gli esperimenti hanno confermato che questo metodo produce un NSW. Poiché i vettori inseriti all’inizio vengono scelti in modo casuale, tendono ad essere piuttosto distanti. Costituiscono quindi le connessioni a lungo raggio necessarie per un mondo piccolo. Non è così ovvio il motivo per cui il piccolo mondo sia navigabile, ma man mano che inseriamo più vettori, le connessioni diventeranno gradualmente più brevi, quindi è plausibile che la distribuzione delle lunghezze delle connessioni sarà abbastanza uniforme, come richiesto.
I piccoli mondi navigabili possono funzionare bene per la ricerca approssimativa dei vicini più vicini, ma un’ulteriore analisi ha rivelato aree di miglioramento, portando Markov et al. (4) per proporre HNSW.
Un tipico percorso attraverso un NSW dal punto di ingresso verso il bersaglio ha attraversato due fasi: una fase di “zoom-out”, in cui le lunghezze delle connessioni aumentano da corte a lunghe, e una fase di “zoom-in”, in cui avviene il contrario .
Il primo semplice miglioramento consiste nell’utilizzare un hub a lungo raggio (come il primo vettore inserito) come punto di ingresso. In questo modo possiamo saltare la fase di zoom indietro e passare direttamente alla fase di zoom avanti.
In secondo luogo, nonostante i percorsi di ricerca fossero brevi (con un numero di passaggi proporzionale al registro(n)), l’intera procedura di ricerca non è stata così veloce. Ad ogni vettore lungo il percorso, l’algoritmo goloso deve esaminare ciascuno dei vettori connessi, calcolando la loro distanza dal bersaglio per scegliere quello più vicino. Mentre la maggior parte dei vettori connessi localmente aveva solo poche connessioni, la maggior parte degli hub a lungo raggio aveva molte connessioni (di nuovo, un numero proporzionale a registro(n)); ciò ha senso poiché questi vettori venivano solitamente inseriti nelle prime fasi del processo di costruzione e avevano molte opportunità di connettersi ad altri vettori. Di conseguenza, il numero totale di calcoli durante una ricerca era piuttosto elevato (proporzionale a log(n)²).
Per migliorare questa situazione, dobbiamo limitare il numero di connessioni controllate su ciascun hub. Ciò porta all’idea principale di HNSW: distinguere esplicitamente tra connessioni a corto e lungo raggio. Nella fase iniziale della ricerca prenderemo in considerazione solo i collegamenti a lungo raggio tra gli hub. Una volta che la ricerca avida ha trovato un hub vicino al bersaglio, passiamo all’utilizzo delle connessioni a corto raggio.
Dato che il numero di hub è relativamente piccolo, dovrebbero avere poche connessioni da controllare. Possiamo anche imporre esplicitamente un numero massimo di connessioni a lungo e corto raggio di ciascun vettore quando costruiamo l’indice. Ciò si traduce in un tempo di ricerca veloce (proporzionale a registro(n)).
L’idea di connessioni corte e lunghe separate può essere generalizzata per includere diversi livelli intermedi di lunghezze di connessione. Possiamo visualizzarlo come a gerarchia di strati di vettori connessi, con ogni strato che utilizza solo una frazione dei vettori nello strato sottostante.
Fonte: towardsdatascience.com
