Come fa un motore di ricerca a decidere che cosa mostrarti

Quando premi invio nessuno va a cercare nel web

Livello Base — linguaggio semplice, senza matematica

La prima cosa da mettere in chiaro è che un motore di ricerca non va a guardare il web quando scrivi qualcosa. Non potrebbe proprio: la risposta arriva in circa due decimi di secondo, che non bastano a visitare nemmeno un sito lontano, figurarsi un miliardo. Tutto è stato fatto in anticipo.

Quello che succede in anticipo si chiama scansione. Un programma parte da una pagina qualsiasi, la legge, si annota ogni parola che contiene, poi segue ogni collegamento su quella pagina per trovarne altre, e ripete, per sempre. Il web è tenuto insieme dai collegamenti, quindi seguirli a partire da qualche punto di partenza alla fine raggiunge quasi tutto.

Quello che viene annotato è un indice, ed è costruito al contrario di come ti aspetteresti. Invece di un elenco di pagine con le parole che contengono, è un elenco di parole con le pagine che le contengono. Cerchi vulcano e hai immediatamente ogni pagina che lo nomina. È questo il trucco che rende la risposta istantanea: il lavoro duro è stato fatto la settimana scorsa.

Poi arriva la parte interessante, l'ordine. Contare quante volte una pagina dice vulcano è un inizio, ma chiunque può scrivere una parola mille volte, e nel web delle origini la gente faceva esattamente così. L'idea che ha risolto il problema è stata guardare i collegamenti: trattare un collegamento come un voto, e contare i voti delle pagine importanti come se valessero di più di quelli di nessuno. Muovi il cursore nella simulazione e guarda la pagina del negozio, che nomina i vulcani in continuazione e a cui nessuno rimanda, scivolare in fondo alla lista dove le spetta.

Indici inversi, TF-IDF e il navigatore casuale

Livello Studente — le equazioni principali

L'indice è la fondazione. Per ogni termine il motore memorizza una lista di occorrenze: i documenti che lo contengono, di solito con le posizioni, in modo che le ricerche di frasi funzionino. Una query di due parole diventa un'intersezione di due liste, che è veloce perché le liste sono ordinate e compresse. Tutto il resto - ordinamento, anteprime, filtri - lavora su quella struttura.

Ordinare col solo testo usa TF-IDF, e contano entrambe le metà. La frequenza del termine premia un documento per aver nominato la parola, di solito con una funzione di smorzamento perché la cinquantesima occorrenza aggiunge meno della seconda. La frequenza inversa di documento penalizza le parole che compaiono ovunque: una corrispondenza su il non vale nulla, una su termoclino è estremamente informativa, e il peso è \(\log(N/\text{df})\). Il raffinamento moderno è BM25, che aggiunge la normalizzazione per lunghezza in modo che i documenti lunghi non vincano solo perché contengono più parole.

PageRank fornisce la seconda metà, e la sua definizione è ricorsiva in un modo che sembra circolare ma non lo è: una pagina è importante se pagine importanti la collegano. Immagina un navigatore che clicca collegamenti a caso e ogni tanto salta invece su una pagina qualsiasi - il fattore di smorzamento \(d\), convenzionalmente 0,85, è la probabilità di cliccare invece di saltare. Il PageRank è la frazione di tempo che il navigatore passa su ciascuna pagina nel lungo periodo, che è l'autovettore principale della matrice dei collegamenti, calcolato iterando finché non si ferma.

Il punteggio finale li mescola, e nella miscela sta il giudizio. Troppo peso al testo e vince il riempimento di parole chiave; troppo ai collegamenti e una pagina popolare batte una pertinente. I sistemi reali aggiungono centinaia di altri segnali - freschezza, comportamento sui clic, velocità della pagina, e dal 2019 modelli linguistici neurali che valutano il passaggio rispetto al significato della domanda invece che alle sue parole - ma la struttura in due parti, pertinenza e autorevolezza, è ancora visibile sotto.

Autovettori, compressione dell'indice e l'ordinamento dopo il recupero denso

Livello Esperto — profondità matematica completa

01PageRank come catena di Markov

Scrivi il web come una matrice stocastica per colonne \(M\) dove \(M_{ij} = 1/L(j)\) se \(j\) collega \(i\). L'operatore smorzato \(G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^{\!\top}\) è stocastico, irriducibile e aperiodico, quindi Perron-Frobenius garantisce un unico vettore stazionario positivo: il PageRank è il suo autovettore principale. Il metodo delle potenze converge a un ritmo governato dal secondo autovalore, che per la catena smorzata è limitato da \(d\); a \(d = 0,85\) è circa una cifra decimale ogni dozzina di iterazioni, ed è per questo che cinquanta iterazioni bastavano su un web di miliardi di pagine. I nodi pendenti, che non collegano nulla, vanno gestiti esplicitamente o la massa di probabilità si disperde.

02L'indice, e perché la compressione è un problema di ordinamento

Le liste di occorrenze vengono memorizzate come differenze fra identificatori di documento invece che come gli identificatori stessi, poi codificate con schemi a byte variabile, Elias-Fano o adatti alle istruzioni SIMD. Assegnare gli identificatori in modo che documenti simili abbiano numeri vicini riduce le differenze e quindi l'indice, il che rende l'ordinamento dei documenti una decisione di compressione con conseguenze dirette sulla latenza delle interrogazioni. La valutazione usa poi la potatura dinamica: WAND e block-max WAND saltano interi blocchi di una lista il cui contributo massimo possibile non può raggiungere la soglia corrente dei primi k, ed è questo che rende superfluo il punteggio esaustivo.

03Imparare a ordinare

Quando i segnali sono centinaia, la messa a punto manuale finisce. Il learning-to-rank tratta l'ordinamento come un problema supervisionato su coppie query-documento giudicate, e gli obiettivi utili sono di lista più che di punto, perché la metrica che conta - il guadagno cumulato scontato normalizzato - dipende dall'intero ordinamento e non è differenziabile. LambdaMART aggira il problema definendo i gradienti direttamente dalla variazione della metrica sotto uno scambio, ed è rimasto lo standard di produzione per anni proprio perché gli alberi con boosting gestiscono meglio delle reti caratteristiche eterogenee e mal scalate.

04Recupero denso e la fine della corrispondenza esatta

Gli indici inversi recuperano per sovrapposizione lessicale, quindi un documento che dice auto è invisibile a una ricerca di automobile. Il recupero denso codifica query e documento in vettori con un transformer e recupera per ricerca approssimata del vicino più prossimo su grafi HNSW, facendo corrispondere il significato invece delle stringhe. Di solito viene affiancato all'indice lessicale in un ibrido, perché il recupero denso è debole esattamente dove quello sparso è forte: nomi propri rari, identificatori e termini che il codificatore non ha mai visto in addestramento. L'ultimo stadio è un cross-encoder che legge insieme query e candidato, troppo costoso per il recupero e accettabile per riordinare i primi cento.

05Un sistema avversariale

Unico fra i problemi di ordinamento, qui i documenti sono scritti da parti che conoscono la funzione di ordinamento e traggono profitto dal batterla. Questo cambia l'ingegneria: i segnali devono essere costosi da falsificare, ed è per questo che i collegamenti da fonti fidate pesano più dei collegamenti che una pagina può crearsi da sola, e per cui i segnali di clic vengono ripuliti pesantemente. Spiega anche perché i dettagli dell'ordinamento non vengono pubblicati. L'arrivo di testo generato su larga scala acuisce il problema: i segnali economici di sforzo su cui l'ordinamento si è appoggiato in silenzio per vent'anni non separano più chi ha lavorato da chi ha automatizzato.