Hilltop è un algoritmo di ordinamento che permette di assegnare ai documenti un punteggio di “autorevolezza” relativo a specifici argomenti, e migliorare in molti casi gli ordinamenti basati sull’analisi del contenuto e, per esempio, sul PageRank.
Quando gli utenti interrogano i motori di ricerca su argomenti molto popolari i motori restituiscono generalmente un grande numero di documenti. Ordinare questi documenti può essere un grosso problema per degli algoritmi che si limitano ad analizzarne il contenuto, perché, diversamente da quanto accade nel campo dell’information retrieval classica, dove si suppone che tutti i documenti provengano da fonti autorevoli, nel web esiste una grossa percentuale di SPAM, ovvero documenti che sono scritti appositamente per avere un buon posizionamento nei motori di ricerca ma che presentano un contenuto di bassa utilità per l’utente finale. Anche quando non c’è un tentativo deliberato di ingannare i motori di ricerca, i loro indici sono affollati da un grande numero di documenti di qualità estremamente variabile e difficili da ordinare.
Quello che ho appena scritto non è un opinione personale, ma il riassunto dell’introduzione di una pubblicazione del 2002 di Krishna Bharat, un ingegnere di Google, noto fra le altre cose per essere il creatore di Google News.
In response to a query, a search engine returns a ranked list of documents. If the query is about a popular topic (i.e., it matches many documents), then the returned list is usually too long to view fully. Studies show that users usually look at only the top 10 to 20 results. However, we can exploit the fact that the best targets for popular topics are usually linked to by enthusiasts in the same domain. In this paper, we propose a novel ranking scheme for popular topics that places the most authoritative pages on the query topic at the top of the ranking. Our algorithm operates on a special index of “expert documents.” These are a subset of the pages on the WWW identified as directories of links to non-affiliated sources on specific topics. Results are ranked based on the match between the query and relevant descriptive text for hyperlinks on expert pages pointing to a given result page. We present a prototype search engine that implements our ranking scheme and discuss its performance. With a relatively small (2.5 million page) expert index, our algorithm was able to perform comparably on popular queries with the best of the mainstream search engines.
Khrisna Barat aveva già pubblicato interessanti studi, per esempio riguardo alla distillazione del topic di un documento (Improved algorithms for topic distillation in a hyperlinked environment.) ed alla realizzazione di vettori di termini (The Term Vector Database: fast access to indexing terms for Web pages).
Nel 2002, insieme a George A. Mihaila (altro “geniaccio” di cui riparlerò) pubblica “When experts agree: using non-affiliated experts to rank popular topics”. Questa pubblicazione analizza il problema sopra indicato e tenta di trovare una soluzione efficiente.
Per prima cosa vengono analizzati gli approcci usati precedentemente per tentare di risolvere il problema, fra questi vi è un accenno specifico al PageRank, del quale individua un limite specifico nel “non poter distinguere fra pagine autorevoli in generale e pagine autorevoli relativamente all’argomento della ricerca. In particolare un sito autorevole in generale può contenere una pagina che soddisfa una certa query ma che non è autorevole rispetto all’argomento”.
In altre parole un sito che tratta, per esempio, di animali domestici può essere molto popolare ed avere un alto PR. Molto probabilmente questo PR proviene da link di altri siti che trattano lo stesso argomento e lo consigliano come approfondimento ai propri utenti, un consiglio valido e fondato quindi. Ma se in quello stesso sito ci fosse una sola pagina che trattasse di auto da corsa, non significherebbe che i siti che lo consigliano intendano raccomandare anche la lettura di quella pagina. Eppure in virtù del PR del sito, se ben inserita nella struttura dei link, questa pagina avrebbe buone possibilità di posizionarsi per ricerche riguardanti le auto da corsa.
L’approccio “Hilltop” si basa, come quello del PageRank, sull’assunto che la qualità e la quantità dei link che puntano ad un documento è un buon indice della qualità del documento, la differenza è che Hilltop considera solo i link provenienti da specifici documenti ritenuti “esperti” relativamente alla ricerca effettuata dall’utente, “documenti creati con lo specifico scopo di dirigere le persone verso le risorse”. Quando viene eseguita una query, l’algoritmo Hilltop per prima cosa individua una lista dei documenti “esperti” più rilevanti per l’argomento, poi all’interno di questi seleziona i link più rilevanti rispetto alla query e seguendo questi individua le pagine da posizionare. Queste pagine sono poi “ordinate secondo il numero e la rilevanza di esperti non affiliati che puntano ad esse. Così il punteggio di una pagina riflette l’opinione collettiva dei migliori esperti indipendenti dell’argomento della query”.
E’molto importante capire che questo tipo di algoritmo funziona solo in presenza di un numero sufficiente di “documenti esperti”, cosa che in generale capita per argomenti molto popolari, dove esistono molti siti web che compilano liste di risorse a tema. D’altra parte i webmaster dei siti, in generale, cercano di pubblicare liste di link aggiornate e complete per aumentare la loro popolarità e la loro influenza nella comunità web interessata ad un certo argomento.
Per interrogazioni che non permettano di individuare una lista di documenti esperti ritenuta sufficiente l’algoritmo Hilltop semplicemente non viene utilizzato, ma questo non è un grosso limite, perché viene specificato chiaramente che l’algoritmo serve a migliorare l’accuratezza delle query sulle quali viene applicato e non è assolutamente necessario che venga utilizzato per tutte quelle eseguite dagli utenti. D’altronde Hilltop ha maggiori possibilità di funzionare bene in presenza di un elevato numero di siti attinenti alla ricerca effettuata, proprio la situazione in cui l’analisi del contenuto si rivela insufficiente.
E’ molto probabile che questo algoritmo sia già utilizzato da Google fin dall’update Florida, del 2004, quello in cui ci fu un vero e proprio terremoto nelle serp (pagine dei risultati). Il fatto che venga applicato soltanto alle ricerche più “popolari” spiegherebbe anche un certo comportamento di Google, che per le ricerche con un basso numero di risultati sembra tendere a dare maggior peso all’analisi dei contenuti. Nei prossimi due articoli vedremo in dettaglio come Hilltop seleziona i documenti esperti e come assegna il punteggio di “Autorevolezza” ai documenti che restituisce come risultato.
Hilltop: la selezione dei documenti esperti
L’algotitmo Hilltop di Google ordina i risultati delle ricerche in base al numero ed alla qualità di link provenienti da documenti esperti. Vediamo come vengono selezionati questi documenti.
Il requisito fondamentale di un “documento esperto” è che esso deve contenere numerosi link che puntino a pagine correlate alla ricerca eseguita dall’utente e che non siano affiliate fra loro. Quindi per prima cosa l’algoritmo Hilltop deve saper distinguere quando due siti diversi appartengono alla stessa organizzazione. Hilltop giudica due siti affiliati fra loro quando si verifichi almeno una delle due seguenti circostanze:
– I due siti dividono gli ultimi tre ottetti di un indirizzo IP (stessa classe C)
– La sezione più a destra e non generica del nome del dominio è la stessa.
In generale le aziende, e specialmente le grandi aziende possiedono i server sui quali risiedono i loro siti. Quindi se esse posseggono più siti questi condivideranno lo stesso indirizzo, oppure avranno indirizzi vicini, dal momento che gli indirizzi vengono assegnati in tranche alle varie organizzazioni che ne fanno richiesta.
Le tranche in cui vengono assegnati gli indirizzi IP possono però essere anche molto più piccole di quelle considerate da Hilltop come soglia di affiliazione, infatti le ultime tre cifre contengono effettivamente 256 indirizzi IP, ma attraverso un artificio tecnico chiamato Subnet Mask, ad una organizzazione ne possono venire assegnati anche molti meno, per esempio 16, ed in questo caso Hilltop potrebbe considerare affiliate 16 organizzazioni che in realtà non lo sono.
Addirittura molti servizi di hosting economici usano lo stesso server ed un solo indirizzo IP per ospitare decine e decine di siti e domini diversi.
Di conseguenza, durante la selezione dei documenti esperti Hilltop potrebbe scartarne alcuni perché contengono link che puntano a pagine che vengono rilevate come affiliate. Tuttavia questo è ritenuto accettabile, perché se viene comunque individuato un numero sufficiente di documenti esperti ci sarà in questo caso la certezza o quasi che siano realmente imparziali e che contengano link a pagine ritenute sinceramente valide.
La condizione di affiliazione che riguarda il nome del dominio, invece, adotta la convenzione di considerare “sezioni” di questo le parti delimitate dai punti e di considerare come generiche, e quindi ignorare, le parti che si ripetono identiche in un grande numero di siti, come per esempio “.it”, “.co.uk”, “.com” ecc.
Per esempio comparando “www.ibm.com” e “www.ibm.co.mx” vengono ignorati i suffissi “.com” e “.co.mx”, per cui le sezioni più a destra, delimitate da un punto risulteranno essere “ibm” in entrambi i casi e i due siti saranno considerati affiliati.
La relazione di affiliazione è inoltre transitiva, per cui se i siti A e B sono rilevati come affiliati ed i siti B e C sono rilevati come affiliati, allora i siti A e C saranno considerati affiliati anche senza ulteriori “prove a carico” del fatto.
Prima ancora di selezionare i documenti esperti viene costruito uno specifico indice di affiliazioni fra i vari siti, dove a tutti quelli che vengono ritenuti affiliati, in base ai criteri già specificati, viene assegnato uno stesso codice identificativo. Questo indice viene usato per verificare velocemente l’affiliazione fra due siti: se hanno lo stesso codice sono affiliati, altrimenti non lo sono.
Dopo aver creato l’indice delle affiliazioni viene creato un nuovo indice, quello dei documenti esperti. Questo indice viene ricavato analizzando il database principale del motore ed estraendone i documenti che vengono considerati buone sorgenti di link tematizzati.
Per prima cosa vengono considerati i documenti che hanno un numero di link in uscita superiore ad una determinata soglia, diciamo, per esempio, 5 link in uscita. Dopodichè i link in uscita di tutti i documenti vengono confrontati con l’indice delle affiliazioni. Se risulta che i 5 link puntano a 5 siti non affiliati il documento è considerato un documento esperto. Anche un certo tipo di formattazione “regolare del documento”, stile directory per intenderci, può avere del peso nell’aiutare l’algoritmo a capire che il documento è una vera lista di risorse.
Infine se nell’indice di partenza del motore è memorizzata una classificazione di massima dell’argomento trattato dai documenti indicizzati (come per esempio arte, sport, scienza ecc.) può essere anche posta la condizione che la maggior parte o tutti i link in uscita del documento esperto debbano puntare a documenti che condividano la stessa classificazione di argomento.
Vedremo ora come vengono indicizzati i documenti esperti e come vengono assegnati i punteggi ai documenti restituiti agli utenti.
Hilltop: ordinamento dei risultati
Quando viene eseguita una ricerca, Hilltop estrae dal suo indice dei documenti esperti quelli rilevanti e li utilizza per individuare ed ordinare i documenti che restituisce all’utente finale.
Nella fase d’analisi dei documenti esperti, l’algoritmo Hilltop esamina solo alcune parti di essi, parti che nel gergo specifico di questo algoritmo sono chiamate “frasi chiave”. Le “frasi chiave” di Hilltop non hanno niente a che vedere con le parole o le frasi digitate dagli utenti per effettuare una ricerca. La definizione di “frase chiave” nell’ambito di Hilltop è “una parte di testo che qualifica uno o più link in uscita”.
I documenti esperti contengono, come abbiamo visto nel precedente articolo, numerosi link in uscita: Hilltop associa ad ognuno di essi alcune “frasi chiave” presenti in specifiche parti della struttura del documento.
I documenti esperti sono inseriti in uno speciale indice inverso organizzato per keyword, nel quale esiste un record per ogni associazione fra una keyword ed una “frase chiave” di un documento esperto. Per ognuno di questi record è memorizzato anche il tipo di “frase chiave” (tag title, intestazione, ecc.) e la prominenza della keyword all’interno della frase.
Quando l’utente esegue una ricerca, l’algoritmo seleziona una lista di documenti esperti rilevanti rispetto ad essa (nell’esperimento relativo alla pubblicazione in esame la lista era composta di 200 documenti esperti). Per essere considerato rilevante rispetto ad una ricerca, il documento esperto deve contenere almeno un link che abbia tutte le parole della ricerca nelle “frasi chiave” che lo qualificano.
Ai documenti esperti viene assegnato un punteggio basato sul numero e sul tipo di “frasi chiave” (tag title, intestazione, ecc.) contenenti le keywords della ricerca. Nell’assegnamento del punteggio sono considerate soltanto le “frasi chiave” che contengono quasi tutte le keyword e viene tenuto conto anche della percentuale di testo che le keyword rappresentano all’interno di ogni frase. I duecento documenti con punteggi più alti vengono scelti come documenti esperti per la ricerca in questione.
A questo punto l’algoritmo Hilltop esamina tutti i documenti a cui puntano i link contenuti negli esperti selezionati ed estrae tutti quelli che ricevono un link da almeno due esperti non affiliati fra loro (ed ovviamente neppure con il documento in esame). Questi documenti sono definiti “bersagli”, e sono quelli che saranno ordinati nei risultati che verranno forniti agli utenti.
Ogni associazione fra una “frase chiave” contenuta in un esperto e un documento “bersaglio” trasmette a quest’ultimo un punteggio proporzionale a quello del documento esperto ed al tipo di “frase chiave” (tag title, intestazione, ecc.). Se due documenti esperti affiliati puntano allo stesso “documento bersaglio” il punteggio di uno dei due, per la precisione di quello più basso, non viene conteggiato.
Ai “documenti bersaglio” viene assegnato un punteggio uguale alla sommatoria dei punteggi ricevuti dai documenti esperti. I risultati vengono infine ordinati combinando i punteggi dell’algoritmo Hilltop e quelli ottenuti dall’analisi dei contenuti dei “documenti bersaglio“.
Sono state eseguite prove di confronto fra i risultati forniti dall’algoritmo Hilltop e quelli forniti da tre motori di ricerca commerciali: Altavista, Direct Hit e Google (prima che assumessero Khrisna Barat, l’inventore dell’algoritmo). I risultati sono stati esaminati da giudici esterni che non sapevano quale lista appartenesse a quale motore. I test hanno evidenziato una capacità di Hilltop pari o migliore degli altri motori di ricerca nel generare una prima pagina di risultati contenente siti molto rilevanti. E’ anche probabile che le prestazioni di Hilltop siano estremamente migliorate al momento della sua integrazione in Google, grazie all’’ampio indice di documenti ed ai sofisticati algoritmi di analisi del contentuto che ha potuto sfruttare.
Se vuoi leggere tutto il paper su Hilltop lo trovi qui: http://ftp.cs.toronto.edu/pub/reports/csrg/405/hilltop.html
Articolo originale di Stefano Becheroni