Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...

Paolo Ferragina, Università di Pisa

Motori di Ricercapresente e futuro prossimo

Rilevanza dei Risultati:Prima generazione

Concetto di rilevanza difficile da “catturare”: Dipende dall’utente che formula la interrogazione Dipende dall’istante di formulazione della interrogazione Contenuto pagine eterogeneo: lingua, tipo (pdf, doc, jpg,..)

Il motore deve “inferire user need” da vari elementi !!

Problemi sul Web nel catturare “pagine rilevanti”

Crescita del Web: 110,000 pagine del 1994 ... 8mld pagine del 2005

Crescita proporzionale del numero delle risposte !!

Utenti guardano a poche risposte: 85% guardano solo ai primi 10 risultati.

Rilevanza derivata dal contenuto

Per ogni occorrenza di una parola si memorizzano: Luogo

URL: www.pisa.comune.it Titolo pagina Testo hyperlink: “Città di Pisa” Metatag: autore, data,...

Assegnamo il “peso”a ogni termine e

sommiamo i contributiper ogni pagina

Tipo Dimensione e tipo di carattere

Maiuscolo o minuscolo

Informazioni sulla “frequenza”

Frequenza “binaria” o “completa”

docs t1 t2 t3D1 1 0 1D2 1 0 0D3 0 1 1D4 1 0 0D5 1 1 1D6 1 1 0D7 0 1 0D8 0 1 0D9 0 0 1D10 0 1 1D11 1 0 1

docs t1 t2 t3D1 2 0 3D2 1 0 0D3 0 4 7D4 3 0 0D5 1 6 3D6 3 5 0D7 0 8 0D8 0 10 0D9 0 0 1D10 0 3 5D11 4 0 1

Ma le Leggi di Zipf e di Luhn ci suggeriscono che dobbiamo pesare molto i termini che sono frequenti in documenti rilevanti ma rari nella intera collezione

Infatti

La frequenza nel singolo documento non aiuta… 10 occorrenze di culla 10 occorrenze di e

Per ogni coppia <termine,documento> assegnamo un peso

che riflette l’importanza del termine in quel documento

Il peso cresce con il “numero di occorrenze” del termine entro quel documento

Il peso cresce con la “rarità” del termine fra tutti i

documenti della collezione

Un “peso” famoso: tf x idf

)/log( iijij nntfw

dove ni = #documenti che contengono il termine i n = #documenti della collezione

Frequenza del termine i nel documento j

Termine ti ha associato un vettore D-dim: [ wi1, wi2, ..., wiD]

Documento Dj ha associato un vettore T-dim: [ w1j, w2j, ..., wTj]

Come usiamo questi pesi ?

Data una interrogazione sui termini th e tk potremmo:

Sommare whj e wkj per ogni documento dj che li contiene, o

utilizzare un’altra funzione dei due valori

Pesare l’importanza di th e tk all’interno della query e quindi

calcolare una combinazione lineare di whj e wkj.

Interpretare ogni documento e la query come vettori, e

postulare la similarità tra doc-query in base alla loro

vicinanza euclidea o tramite altra misura correlata.

Documenti come vettori

2D)7.0 ,2.0(

)3.0 ,8.0(

0.60.4 1.00.2

Similarità tra Doc e Interrogazione

98.0cos

74.0cos

)8.0 ,4.0(

)7.0 ,2.0(

)3.0 ,8.0(

0.60.4 1.00.2

Documenti come vettori

Alcune osservazioni…. Non c’è una reale base teorica per il modello vettoriale

I termini non sono relamente indipendenti

Siccome Q consiste di pochi termini ti, non la

confrontiamo con tutti i docs, ma piuttosto: Lista invertita per prendere docs Dj che li contengono

Estraiamo da ogni Dj il peso wij , relativo ai ti che contiene

Combiniamo “in qualche modo” i contributi, per conoscere la

“similarità” tra Q e Dj indotta dalle frequenze locali e globali

Un altro peso: Anchor text

Qui trovate una bella immagine di una tigre

Immagine di una tigre

Ganza pagina con immagini sulle tigri

NOTA: Il testo nella vicinanza di un hyperlink è molto descrittivo del

contenuto della pagina a cui esso fa riferimento !

Indicizziamo i virtual doc costruiticoncatenando gli anchor text dei link

che puntano a una determinata pagina

Ricapitolando

Per ogni occorrenza di una parola si memorizzano: Luogo

TF x Idf

I motori di prima generazione usavano questi pesi per

inferire la similarità dei documenti con la query

Poi ordinavano le risposte (docs) in accordo a questa

Rilevanza dei Risultati:Seconda generazione

Sfruttare gli hyperlink

Problema:

Molte pagine contengono le parole in Q ma sono “non rilevanti” oppure

includono parole “diverse” dal loro contenuto (spamming).

Altre pagine sono sì rilevanti ma non contengono le parole di Q oppure

non contengono testo, ma solo p.e. immagini o form.

Hyperlink Citazione

Analisi degli hyperlink Due approcci fondamentali

Indipendente dalla interrogazione

Se due pagine contengono le parole di Q, una sarà

sempre migliore dell’altra indipendentemente da Q

(Pagerank di Google)

Dipendente dalla interrogazione

Se due pagine contengono le parole di Q, una sarà migliore dell’altra a seconda del contenuto di Q

(HITS di IBM e Teoma)

PageRank (Google)

Pagina rilevante se:

Molte pagine puntanto a essa (popolare) Alcune pagine “rilevanti” puntano a essa (élite)

I(p) = (1-q) + q

Calcolato su tutte le pagine e in modo iterativo (~100)

I(p1) + I(p2) + ... + I(pn) u1 u2 un

Attenti ai Blog !

Un esempio: passo iniziale

Page A 1

Page C1

Page B1

Page D1

1*0.85/2

1*0.85/21*0.85

1*0.85

q = 0.15

Esempio: dopo 20 iterazioni

Page A 1.490

Page C1.577

Page B0.783

Page D0.15

q = 0.15

Sarebbe necessario, in verità, cambiare +q in +(q/#pagine) questo garantisce che il vettore dei pesi uscenti ha somma 1,

e quindi (Teorema) il PageRank è una distribuzione di probabilità

HITS (IBM)

A seguito di una interrogazione si cercano due insiemi “correlati” di pagine:

Pagine Hub = pagine che contengono una buona lista di link sul soggetto della interrogazione.

Pagine Authority = pagine che occorrono ripetutamente nelle liste contenute dei buoni Hubs.

Si tratta di una definizione circolare che quindi richiede una computazione iterativa

HITS: Primo passo per risolvere Q

base set

Data una interrogazione Q={ browser }, si forma il base set:

1. Le pagine che contengono browser (root set)

2. Le pagine collegate da o per quelle del root set

Root set

Calcoliamo, per ogni pagina x del base set:

un hub score h(x), inizializzato a 1 un authority score a(x), inizializzato a 1

Per poche iterazioni, ricalcoliamo di ogni nodo x:

a(x) = h(zi) , h(x) = a(yi)

Scaliamo i valori, e iteriamo

Alla fine, restituiamo le pagine con più alto valore di h() come hubs, e di a() come authorities

Costoso: Accumulo del base set e calcolo iterativo !!

Controindicazioni: Facilmente soggetto a SPAM !!

HITS: Secondo passo per risolvere Q

Un esempio

AutoritàHub

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Rilevanza dei Risultati:Terza generazione

Nuovi obiettivi

Obiettivo: Integrare dati provenienti dalle sorgenti più

disparate – quali, preferenze, click, affinità tra utenti, transazioni–

al fine di soddisfare meglio l’interrogazione posta da un utente

Esempio: Su una interrogazione come “San Francisco” il sistema dovrebbe trovare anche gli hotel o i musei, siti per le previsioni del tempo o mappe stradali, intuendo anche quali di questi è più rilevante per l’utente

Tools: Ciò richiede analisi semantica, determinazione del contesto, selezione dinamica di archivi utili, confronto tra sessioni …

Nuove nozioni di Rilevanza !!!

Rilevanza per “affinità”

Precedenti transazioni: [Collaborative Filtering]

Quali documenti/pagine sono state visitate, anche da altri utenti Quali prodotti sono stati acquistati, anche da altri utenti Pagine nei bookmarks dell’utente

Contesto corrente: [User behavior]

Storia della presente navigazione Ricerche già formulate dallo stesso utente

Profilo: [Personalization] Professione dell’utente e informazione demografica Interessi dell’utente

Esistono dei problemi di privacy !!!

Ricapitolando...

Data una interrogazione Q su più parole Troviamo le pagine dove occorrono quelle parole Per ogni pagina determiniamo:

Peso testuale: font, luogo, posizione, vicinanza,… Peso degli hyperlinks: grafo e anchor-text Peso dato da altri fattori: preferenze, comportamento,…

Sommiamo “in qualche modo” i pesi

Ordiniamo le pagine in funzione di essi Risultati !!

Questo è un motore di ricerca moderno !!(siamo alla terza generazione)

Offriamo possibilmente dei suggerimenti, anche semantici

Motore di Ricerca: struttura W

Crawler

Archivio Pagine

Analizzatorepagine

Controllo

RisolutoreAnalizzatoreRilevanza

TestoStruttura

Utilità

Indicizzatore

risposte

Valutazione dei Risultati

Quanto è “buono” un motore di ricerca?

Alcune misure di valutazione:

Costruzione:

Velocità nell’indicizzazione

Spazio occupato dall’indice

Copertura del Web

Modifica:

Frequenza e ampiezza delle modifiche

Interrogazione:

Velocità nel produrre le risposte

“Rilevanza” dei risultati: precisione e completezza

Scenario generale

Rilevanti

Recuperati

Tutti docs

Precisione: % documenti recuperati che sono rilevanti

Quanta “spazzatura” abbiamo recuperato

Approccio classico: Precisione vs. Completezza

Rilevanti

Recuperati

Tutti docs

Completezza: % docs rilevanti che sono recuperati

Quanta “informazione” abbiamo recuperato

Approccio classico: Precisione vs. Completezza

Rilevanti

Recuperati

Tutti docs

Precisione vs. Completezza

Rilevanti

Recuperati

| Collezionein Ril|

| atiRilRecuper| aCompletezz

|Recuperati|

|atiRilRecuper| Precisione

Tutti docs

Rilevanti

Altissima precisione, bassissima completezza

recuperati

| Collezionein Ril|

|Recuperati|

Rilevanti

Bassissima precisione, bassissima completezza

recuperati

| Collezionein Ril|

|Recuperati|

Recuperati

Rilevanti

Alta completezza, bassissima precisione

| Collezionein Ril|

|Recuperati|

Recuperati

Rilevanti

Alta completezza e precisione

| Collezionein Ril|

|Recuperati|

Trade-off

Si misura la Precisione a diversi livelli di Completezza

Nota: è una MEDIA su numerose interrogazioni

precisione

completezza

Difficoltà per il web

precisione

completezza

Sul Web non conosciamo la “completezza”, quindi guardiamo

soltanto ai primi 10100 risultati. Su questi si gioca la “partita” !!

Ognuno sceglie il suo Ranking !

http://www.langreiter.com/exec/yahoo-vs-google.html?q=...

Il quadro presente

Fino a pochi anni fa...

Yahoo (migliore del 1995)

Inktomi (migliore del 1997)

Altavista (migliore del 1999)

Lycos, Excite, Northern Light,...

In Gennaio 2004, i preferiti sono Google (60 mil), Yahoo e MSN (45

mil ciascuno), AOL (23 mil), AskJeeves (13 mil). Ogni utente visita

più motori di ricerca per le sue query.

Alcune statistiche recenti...

In Gennaio 2004, 52% utenti indicano nella rilevanza dei risultati la

cosa più importante, 33% velocità. Interfaccia non importante.

Yahoo, AOL e EarthLink si appoggiano a Google e poi mixano i suoi

risultati con loro tecniche per mantenere una qualche autonomia

(Feb 04, Yahoo si divide da Google!)

Il motore più famoso ...

Cosa non è Google

Indice su tutti i documenti disponibili sul Web Nessun motore lo è

Credibile in ogni cosa che ci segnala Non esiste controllo sulla pubblicazione delle pagine

Perfettamente aggiornato Non riesce a seguire le modifiche giornaliere (milioni di pagine)

Protetto da contenuto offensivo Dispone di un meccanismo di filtering, ma non sicuro al 100%

Cosa è oggi Google Alcuni dati interessanti (NY Times, Aprile 2003):

Più di 1000 persone 54,000 server - 100,000 processor - 261,000 dischi

~4Mld pagine (1/04), 200 milioni query/giorno (30% del totale)

300 milioni di dollari di fatturato 2002 (750 nel 2003 ?)

“google” è la parola più utile del 2002 [American Dialect Society]

Un nuovo scenario di:

Gestione ed estrazione della conoscenza: non solo Web

Problemi matematici interessanti: Qualità risposte, Efficienza, Copertura del web Nuove applicazioni (news,prodotti), Nuovi domini (audio,video)

Business: tra i pochissimi a fare molti profitti !

Google: Il modello di business in 2 iniziative

Search services via la Google search appliance Soluzione hardware+software per un motore di ricerca in ambito

intranet o singolo website Hardware fissato e quindi limitati problemi di sviluppo e mantenimento

del software Per ora disponibile soltanto in USA e Canada (??)

Advertising programs (100.000 sottoscrittori) AdSense: Un sito può fornire spazio sulla sua pagina; le pubblicità da

visualizzare vengono scelte da AdSense in funzione dei contenuti della

pagina così da rivolgersi a probabili clienti. Il sito riceve un pagamento

in funzione del numero di click sul banner. AdWords: Una società può scegliere quanto pagare al giorno/mese e

indicare le parole chiave che descrivono il suo business. Un banner

viene visualizzato da Google all’atto di ricerche per quelle parole

chiave, e la società paga in funzione del numero di click ricevuti.

Google: altre notizie... Il nome deriva dalla parola GOOGOL, coniata da un bambino

americano di 9 anni per riferirsi al numero 10100

Un po’ di storia:

[1996-97] Esce il primo prototipo (BackRub).

[1998-99] Nasce Google, risponde a 10,000 Qpg 3Ml Qpg

[2000] 1Mld pagine e 60Ml Qpg

[2001] 2Mld pagine e 100Ml Qpg, ricerche limitabili a 26 linguaggi.

Introduce Image e File type search, Usenet dal 1981, Google Catalog.

[2002] 2,5Mld pagine, ricerche limitabili a 40 linguaggi. Intoduce AdWords, Google news, Web API, Froogle, Google Labs.

[2003] 3Mld di pagine, più linguaggi supportati. Il programma di business raggiunge i 100,000 sottoscrittori e viene promosso in Italia. Introduce Google AdSense, Local Search.

Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...

Documents

Transcript of Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...

Rischi prossimo anno

per l’inizio del mio prossimo

Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Cosa è un motore di ricerca ?

La rilevanza della scriminate culturale nel sistema penale ... · PDF file2016 giurisprudenzapenale© redazione@ La rilevanza della scriminate culturale nel

ITALIANO-LETTERA-PASSATO PROSSIMO

3 Il passato prossimo 3.1. Il passato prossimo …russoscript.eu/app/download/5779766838/parte_terza.pdfIII. Parte terza 3 Il passato prossimo andato iniziata ﬁnita invitato letto

Imperfetto vs passato prossimo

passato prossimo ausiliare avere.doc

Aspetti epidemiologici e rilevanza clinica

LA RILEVANZA DEI FATTORI PSICOSOCIALI NELL’EVOLUZIONE ...

L’Italia nell’economia internazionale · 2018-01-26 · Stefano Costa, Giuseppe De Arcangelis, Luca De Benedictis, Sergio de Nardis, Daniela Federici, Anna Ferragina, Francesco

SISTEMI DI GESTIONE AMBIENTALE RILEVANZA PER L’IMPRESA.

Avanti il prossimo

Il boom demografico prossimo venturo

Rilevanza delle malattie dell’apparato respiratorio PDFs/1.Burden... · Rilevanza delle malattie dell’apparato respiratorio 1 Le malattie dell’apparato respiratorio nel mondo

Il Passato Prossimo

Il passato prossimo edited

PROCEDURA APERTA A RILEVANZA COMUNITARIA PER LA …

Scuola futuro prossimo

Passado Prossimo, Imperfetto.pdf