Search Marketing

Guida al posizionamento dei siti web nei motori di ricerca

Amico degli spider
Home
2 Apr '05
Guida
8 Nov '04
Articoli
27 Mar '05
News/Blog
La Newsletter
30 Apr '09
FAQ
12 Gen '03
Risorse
10 Ott '04

Intervista a Sebastiano Vigna

Sebastiano Vigna, matematico ed esperto di IR, discute di uno studio sul PageRank presentato al recente WWW2005, di tecniche antispam e delle ricerche a cui lavora.
12 luglio '05 10:09:08
Conosco Sebastiano Vigna di fama da quando, molti anni fa, era autore di ottimi software per la piattaforma Amiga. Lo "incontro" nuovamente oggi nelle mie scorribande sul Web, scoprendolo esperto di information retrieval e coautore di uno studio sul PageRank presentato alla recente conferenza WWW2005. L'idea di intervistarlo è nata immediatamente.

Ne è venuta fuori una interessantissima chiacchierata informale su PageRank, software, spam ed algoritmi, spiegati da chi i motori di ricerca li progetta.

Buona lettura a tutti.


Enrico Altavilla: Sebastiano, ti invito ad introdurre brevemente il tipo di studi che effettui presso l'Università degli Studi di Milano, in particolar modo quelli inerenti l'information retrieval.

Sebastiano Vigna: Sono professore associato presso il Dipartimento di Scienze dell'Informazione. Assieme ad alcuni colleghi abbiamo fondato il LAW (laboratorio di algoritmica del web), dove studiamo tutti i fenomeni relativi al trattamento di dati di dimensione paragonabile al web: per esempio, abbiamo sviluppato un sistema di indicizzazione estremamente sofisticato (MG4J) che utilizziamo per creare motori di ricerca sperimentali. Oppure abbiamo sviluppato WebGraph, un sistema in grado di rappresentare e manipolare in memoria centrale grafi enormi, grazie a nuove tecniche di compressione. Con WebGraph possiamo porci domande come "Ma che cosa succede se calcolo PageRank ma conosco solo la metà del web?" e avere risposte esatte.

Tutto questo software è libero e distribuito sotto la GPL o la LPGL; viene peraltro usato da altre comunità scientifiche (so di medici di Cornell, e di gente che si occupa di information retrieval presso La Coruña). Abbiamo poi un crawler distribuito, UbiCrawler, che utilizziamo per raccogliere dati e snapshot di porzioni del web.

Sviluppiamo quasi esclusivamente in Java sotto Linux o OSX. Ci sono diverse classi Java di contorno sviluppate negli anni per avere sistemi ad alte prestazioni, come fastutil, anche queste disponibili sotto LPGL. Se si vuol sapere di più sui singoli progetti, c'è un sito gestito dall'università (www.uxc.it) che contiene descrizioni dettagliate.

Tutto questo, però, ci serve solo da strumento: quello che ci interessa capire è come fare funzionare bene (o ingannare, il che è poi lo stesso) i meccanismi di ranking, cioè di posizionamento nelle risposte dei motori di ricerca. Abbiamo anche sviluppato diversi nuovi meccanismi di ranking sperimentale.

Enrico Altavilla: Il gruppo di ricercatori di cui fai parte ha presentato un documento dal titolo "PageRank as a Function of the Damping Factor" [PDF] alla recente Conferenza Internazionale del World Wide Web (WWW2005), ospitata in Giappone. Quali caratteristiche del PageRank vengono discusse nel documento e che innovazioni vengono proposte?

Sebastiano Vigna: Mah, è una domanda a cui non è facilissimo rispondere. Quel lavoro è certamente il più teorico che abbiamo mai scritto, e sebbene abbia avuto un grosso successo al WWW, le applicazioni sono ancora lontane. L'idea è che PageRank è calcolato utilizzando un fattore di attenuazione (damping factor) che sparge una parte del ranking su tutte le pagine. I siti che accumulano fraudolentemente ranking con numerose pagine finte riescono a farlo per via del fattore di attenuazione, e l'idea è che studiando come varia PageRank modificando il fattore di attenuazione si possono trovare i siti che imbrogliano (per la precisione, quest'idea non è nostra ma la potete trovare negli atti di WAW 2004 [PS]). Ora, se vuoi sapere come varia qualcosa la risposta matematica è una sola: guarda le derivate. Quello che abbiamo fatto è calcolare in forma esplicita le derivate di PageRank, e dare degli algoritmi di approssimazione.

Il resto è tutto da fare, ma posso aggiungere che a un panel di discussione del WWW 2005 un consulente scientifico di Google si è fatto scappare la parola "derivatives" parlando dei modi di rendere PageRank più resistente allo spamming.

Enrico Altavilla: So che non è facile addentrarsi nei lati tecnici, ma provo comunque a scendere un po' nello specifico, per capire con più precisione a che punto è giunta la ricerca. Il damping factor della formula determina la percentuale di PageRank destinata ad essere trasmessa attraverso i link. Tuttavia avete osservato che valori di damping factor vicini ad 1 non conducono, come intuitivamente si potrebbe credere, ad una concentrazione del PageRank sulle pagine considerate "globalmente importanti" bensì portano a far accumulare il PageRank su pagine fortemente inter-collegate e meno integrate con altre zone del Web. Il mio dubbio è: la ricerca è andata avanti per controllare se queste distribuzioni identificano principalmente delle tipiche situazioni di spam, oppure gli studi si sono attualmente limitati alle osservazioni matematiche, senza sapere se tali fenomeni di forti interconnessione avvengono anche "naturalmente" nel Web?

Sebastiano Vigna: È possibile in effetti che le componenti terminali (quelle che, come osservi, assorbono interamente PageRank quando il fattore di attenuazione va a 1) siano dovute a spam. Ma non possono di fatto essere utilizzate per individuare lo spam--se fossi uno spammer, mi basterebbe aggiungere un solo link verso una pagina della componente principale del web per non apparire più come una componente terminale. Il punto è che le componenti terminali sorgono naturalmente nella struttura del web e, nell'attuale formulazione di PageRank, impediscono di usare fattori di attenuazione superiori a .99 (ci sono anche problemi di stabilità numerica, ma quelli possono essere superati). Quello a cui lavoriamo sono meccanismi di ranking alternativi, come TruRank, che rimangono validi anche quando il fattore di attenuazione è molto vicino a uno. In questo modo si può minimizzare l'effetto della "raccolta" del ranking dovuto al fattore di attenuazione.

Enrico Altavilla: Ho letto molti studi sul PageRank. Quasi tutti si basano sulla formula originale sviluppata da Brin e Page, proponendone dei miglioramenti. So però che Google ha leggermente modificato la formula iniziale nel corso degli anni. Tenuto conto delle carenze della formula originale e delle esigenze di un moderno motore di ricerca, quali modifiche è più facile che siano state apportate da Google alla propria implementazione del PageRank, a tuo parere?

Sebastiano Vigna: Hypotheses non fingo. Sono uno scienzato, non un rabdomante, per cui non posso immaginare che cosa combina Google. Certamente, dagli ultimi brevetti che ha sottoposto è evidente che adoperano tecniche sempre più raffinate di tipo antropico. Mi spiego meglio: invece di cercare un qualche meccanismo algoritmico o matematico che individui i siti fraudolenti, tengono memoria delle trasformazioni dei siti e abbassano il ranking di quelli che subiscono trasformazioni "da spam": per esempio, se improvvisamente cambiano completamente argomento, e se improvvisamente acquisiscono numerosissimi link. Vanno cioè a misurare le attività umane legate allo spamming. Ovviamente è solo questione di tempo prima che qualcuno realizzi un software che modifica un sito un po' alla volta... ci sono già i blog finti, non sarà mica un problema 8^).

Ci sono poi milioni di ritocchi che invece posso immaginare: eliminare i cappi (cioè i link autoreferenziali), moderare con un limite massimo il numero di link dallo stesso dominio, e così via.

Enrico Altavilla: Solo un'osservazione sulle trasformazioni "da spam": l'acquisto improvviso di link non dovrebbe essere di per sé un evento dubbio. Mi è parso di osservare che le loro analisi sulle trasformazioni delle pagine prendano in considerazione anche i comportamenti degli utenti che effettuano ricerche. L'improvvisa acquisizione di link da parte di una pagina può essere considerata genuina se Google osserva anche un incremento improvviso delle ricerche sui temi discussi nella pagina. Osservazioni di questo tipo vengono indubbiamente utilizzate in Google News per individuare gli argomenti "caldi". Non sapremo mai quello che effettivamente fanno, ma a tuo parere questi incroci tra informazioni sui siti e informazioni sulle ricerche sarebbero tecnicamente fattibili e sopratutto sensati?

Sebastiano Vigna: Mah, tecnicamente fattibili di sicuro. Credo comunque che per acquisizione improvvisa di link si intenda un'acquisizione massiccia, e che "stona" con le storia delle modifiche alla pagina. Se fossi uno spammer, poi, utilizzerei precisamente parole chiave che riguardano argomenti "caldi" nella pagina, e quindi non credo avrebbe molto senso vedere positivamente la presenza di tali parole chiave. Separerei poi la questione news dalla questione web perché la variazione in dimensione è di almeno quattro ordini di grandezza, e quindi le tecniche utilizzate sono completamente diverse.

Enrico Altavilla: Circa le possibili modifiche al PageRank, mi sono sempre chiesto perché tutti i link di una pagina dovrebbero possedere uguale probabilità di essere seguiti dall'utente, indipendentemente dalla loro prominenza nella pagina, dal testo dell'ancora o dal contesto intorno al link. A prescindere dai criteri applicabili per determinare una "probabilità di click", esistono attualmente i mezzi per assegnare una probabilità diversa ad ogni link di ogni pagina archiviata? Se no, ritieni che si otterrebbero risultati comunque migliori se l'assegnazione di probabilità diverse venisse limitata alle pagine con un valore di PageRank maggiore di una certa soglia?

Sebastiano Vigna: Direi che non se ne parla neppure... dare un'importanza diversa a ogni link implica memorizzare centinaia di miliardi di pesi, o di ricalcolarli al volo durante ogni iterazione del calcolo di PageRank. Limitandosi alle pagine con PageRank molto alto sarebbe invece possibile, anche se non saprei dire con che criteri variare l'assegnazione.

Enrico Altavilla: Del PageRank si discute molto e continuamente, sia tra i webmaster/SEO sia tra i matematici. Esistono valide alternative? Sapresti indicare altri algoritmi o formule in grado di calcolare efficacemente la "qualità" o "importanza" delle pagine web?

Sebastiano Vigna: Intanto, è importante (sebbene poco noto) dire che PageRank è la traduzione immediata di un algoritmo sviluppato negli anni '70 per misurare l'autorevolezza scientifica di un lavoro: un link è una citazione bibliografica, e si fa andare l'algoritmo che oggi chiamiamo PageRank (tale e quale). Sinceramente, se Google dovesse mai far valere il suo brevetto, un bravo avvocato non credo avrebbe difficoltà a dimostrare che PageRank in realtà non è proprio nuovo. Certo, il contesto di applicazione cambia, il che potrebbe comunque rendere il brevetto applicabile. IANAL (I am not a lawyer).

Ci sono diversi altri algoritmi esistenti in letteratura--in particolare, SALSA e HITS. Entrambi si basano sull'algebra lineare, come PageRank, e probabilmente in qualche forma sono utilizzati da altri motori di ricerca.

Purtroppo confrontare meccanismi di ranking è difficilissimo, perché a parte prove a campione con esseri umani intelligenti e informati non c'è molto da fare... e la categoria non è proprio diffusa 8^).

Enrico Altavilla: Tutti gli algoritmi citati si basano sui link. Che tu sappia, esistono nell'IR applicata al Web degli algoritmi che calcolano l'autorevolezza di una pagina basandosi sulle citazioni del suo testo da parte di altre pagine?

Sebastiano Vigna: Intendi basate sulla presenza effettiva di frammenti di testo? Che io sappia no--e peraltro la cosa sarebbe di dubbia determinazione, e computazionalmente intrattabile.

Enrico Altavilla: Ho qualche dubbio circa la possibilità per Google di avanzare diritti sul PageRank. Anche io non sono un avvocato e non vorrei dire una castroneria, ma il brevetto sul PageRank non appartiene alla Stanford University?

Sebastiano Vigna: Sì, il brevetto è di Stanford. Comunque molti usano PageRank e non credo proprio paghino alcunché. Google ha comunque molti brevetti relativi a zillioni di piccole modifiche o migliorie, e potrebbe far valere quelli.

Enrico Altavilla: Tra gli accessi registrati da alcuni miei siti ho notato alcune volte la presenza del vostro UbiCrawler. Che caratteristiche ha questo spider e per quali scopi lo utilizzate attualmente?

Sebastiano Vigna: UbiCrawler è un crawler completamente distribuito. Gira sotto forma di agenti completamente identici che si dividono il web a pezzi: ogni agente scarica la sua parte di web, e invia eventuali informazioni relative a parti che non gli competono all'agente preposto. Il primo aspetto interessante di UbiCrawler è un uso innovativo che abbiamo fatto di una tecnica detta "hashing coerente". In sostanza, se a metà crawl vengono aggiunte delle macchine o ne muoiono, il sistema si comporta così da dover spostare la responsabilità del minor numero di pagine possibili. L'altro aspetto interessante è che scala linearmente: se hai 10 macchine vai a una certa velocità, se ne hai 100 va 10 volte più veloce (banda permettendo).

C'è un articolo su "Software: Practice & Experience" (ma anche scaricabile online [PDF]) che spiega i dettagli, e le classi Java che calcolano lo hashing coerente sono disponibili sotto la LGPL.

Enrico Altavilla: Puoi dirmi che cosa è WebGraph?

Sebastiano Vigna: È un sistema per comprimere e accedere in forma compressa grafi di grandi dimensioni. Permette di comprimere uno snapshot del web a circa 3 bit per link, e di accedere alle liste di successori di un nodo (cioè le pagine puntate) con un costo dell'ordine del 200ns per pagina. Attualmente è il sistema di questo tipo con il miglior rapporto di compressione. Come ho detto all'inizio, lo usiamo per porci domande sul web e avere risposte sperimentali concrete.

Un altro scopo di WebGraph è fornire un formato per distribuire grafi di grandi dimensioni. Se altri ricercatori vogliono utilizzare degli snapshot del web per la loro ricerca, o vogliono verificare i nostri risultati, gli basta andare su webdata.iit.cnr.it o webgraph-data.dsi.unimi.it e tirarsi giù i grafi in formato WebGraph. Anche questa caratteristica (fornire i dati sulla base dei quali scriviamo i nostri lavori) è decisamente controcorrente con la pratica attuale nello studio del web, sebbene dovrebbe essere il livello zero di una pubblicazione che si voglia dire scientifica.

Enrico Altavilla: Come mai la maggior parte degli altri ricercatori non fornisce i dati su cui i lavori si basano? E' semplicemente una cattiva abitudine oppure esiste una "gelosia" nei confronti del proprio lavoro che li frena dal facilitare l'analisi dei colleghi?

Sebastiano Vigna: Mah, ci sono alla base alcune difficoltà oggettive (dimensioni dei dati), ma sinceramente penso che sia solo cattiva abitudine, e un po' di tracotanza da parte degli scienziati delle grosse università americane.

Enrico Altavilla: Tra i webmaster è uso scambiarsi link per far apparire i propri siti web più "popolari" agli occhi degli algoritmi dei motori di ricerca. Avendo a disposizione un grafo del Web, esiste attualmente la tecnologia per individuare link reciproci tra i siti o addirittura pattern di link circolari (A > B > C > A)?

Sebastiano Vigna: Sì, questo è relativamente banale. Può non essere banale farlo per una distanza significativa, perché l'individuazione dei cicli che passano per A richiede una visita, che è lineare nel numero di link del grafo. Se però ci interessano, diciamo, i cicli più corti di cinque link, la faccenda è decisamente più semplice, grazie al fatto che il web ha un grado positivo medio (il numero di link verso altre pagine) piuttosto basso. Invito chiunque fosse interessato alla cosa a scaricarsi uno snapshot di .it e fare una prova con WebGraph.

Enrico Altavilla: Il LAW è il laboratorio che racchiude i vostri progetti sull'algoritmica dedicata al Web. Quali strumenti è in grado di fornire il LAW a qualcuno che intendesse progettare un proprio motore di ricerca? In particolare, che aiuti potrebbe fornire MG4J?

Sebastiano Vigna: Attualmente abbiamo un contratto di ricerca con Wind su queste tematiche: il nostro ruolo è precisamente fornire tecniche algoritmiche e idee a chi crea motori di ricerca. In alcuni casi, fungiamo puramente da "filtro" rispetto alla letteratura esistente, spesso non facilmente accessibile, e in altri sviluppiamo teoria o software per rispondere alle domande che ci vengono poste. Per quanto riguarda il software, credo che con MG4J e qualche piccola aggiunta non sia affatto difficile creare un motore di ricerca nazionale (noi lo facciamo, perlomeno). Certo, un motore che funziona davvero bene richiede un'accordatura costante, e non è certo un'attività che ci interessa.

Enrico Altavilla: Che peso ha l'esistenza del web spam sullo sviluppo di algoritmi per l'information retrieval? Tu o i tuoi colleghi del LAW avete mai effettuato studi sugli effetti del web spam o su tecniche per minimizzarne l'influenza sui risultati delle ricerche?

Sebastiano Vigna: In questo momento, lo spam è il peso maggiore nel web information retrieval. Non serve a niente avere meccanismi di ranking sofisticatissimi se il tuo database è pieno di spam (come dicono gli inglesi: garbage in, garbage out). Uno dei nostri argomenti di studio è precisamente l'individuazione delle tecniche di spam e delle relative contromisure, anche se, come è ben noto, c'è un problema di braccio di ferro: non appena una contromisura diventa nota, qualcuno trova il modo di aggirarla, e bisogna trovarne un'altra. Per questa ragione spesso tecniche di antispam, anche molto ingegnose, non vengono pubblicate nella letteratura scientifica, ma rimangono sepolte nei laboratori dei grandi motori di ricerca.

Noi siamo solo agli inizi (in effetti, non abbiamo ancora pubblicato nulla sull'argomento, se non l'articolo che citavi prima). Certo è che il numero di partecipanti e la frequenza a congressi che spiegano come fare spam è infinitamente superiore a quello di qualunque congresso scientifico: gli interessi economici in gioco sono veramente enormi. D'altra parte, se un problema non è difficile, dov'è il divertimento?

Enrico Altavilla: Com'è possibile che i metodi di spam discussi in quei congressi funzionino realmente, se si pensa che gli spammer si confrontano, seppure indirettamente, con ingegneri informatici, matematici e scienziati? La differenza culturale tra le due classi è indubbiamente consistente, eppure persino motori avanzati come Google sono facilmente vittima di fenomeni come gli "spam engine", pagine con risultati di ricerca che si auto-riproducono in quantità industriali e che imperversano nei risultati di ricerca. Stiamo assistendo alla vittoria della pratica sulla teoria?

Sebastiano Vigna: Beh, è come dire che i ladri riescono a entrare nelle case, che sono progettate da fior di architetti e ingegneri, o che i dirigenti della Parmalat hanno sottratto denaro a un sacco di gente esperta di borsa. È un problema, come ho già detto, di braccio di ferro e di risorse impiegate. Ci sono decine di migliaia di spammer, e un Google. Peraltro, dati gli sforzi e la quantità di soldi investita dagli spammer, direi che i risultati sono piuttosto scarsi: le mie ricerche su Google raramente portano a spam (su altri motori, ovviamente, le cose possono essere diverse).

Enrico Altavilla: Grazie Sebastiano per tutte le interessantissime informazioni che hai fornito e per essere riuscito a rendere questi argomenti piuttosto complessi facilmente fruibili ai lettori di Motoricerca.info. Auguro a te e ai tuoi colleghi dell'università di proseguire nell'eccellente lavoro svolto finora e mi auguro che in futuro si possa tornare a chiacchierare su qualche vostro nuovo lavoro o progetto.

Sebastiano Vigna: Con piacere. I problemi in information retrieval relativi al web sono sempre interessantissimi, soprattuto per via della dimensione dei dati: occorre sempre essere particolarmente furbi (e occorre rispolverare molte tecniche di gestione dei dati in memoria esterna degli anni sessanta). Ma è proprio questo che rende i problemi divertenti...


Gli autori di questa intervista, Sebastiano Vigna ed Enrico Altavilla, hanno deciso di pubblicarla sotto questa licenza Creative Commons, qui riassunta, per facilitarne la diffusione.

< Torna alla pagina con le notizie più recenti

<< Torna alla pagina principale di Motoricerca.info