Segnalo anche questo:

http://nlp.stanford.edu/IR-book/pdf/irbook.pdf

'An introduction to information retrieval'

Introduction mica tanto dato che son 190 e passa pagine...cmq...ed è pure molto recente. Agli esperti il giudizio.

Scusate l'ignoranza ma mi sta scoppiando il cervello... sto ancora studiando l'IR ma non riesco a figurarmi la situazione...

Sono confuso credo di essere fuori strada non riesco a figurarmi l'esempio della battaglia navale che ho trovato anche in wikypedia... per navi cosa si intende? quello che digita l'utente o come classifica google le query?

Ragiono male nel pensare che un documento dovrebbe contenere termini che si avvicinano più possibile a quello che potrebbe digitare l'utente??? per esempio "ristrutturazioni" dovrebbe essere contenuto in parti strategiche della pagina come riportato nelle guide.... e magari usare anche sinonimi per espandere la ricerca...
O l'esempio intende creare più documenti che trattano dello stesso argomento racchiusi in una dorectory???

Mah! sono fuori strada rispetto a quello che si è detto fin' ora ???

Potete cortesemente semplificarmi l'esempio della battaglia navale che ho capito ma che non risco a figurarmi con Google... sicuramente sono rincoglionito rispetto ai ragazzini che hanno capito al volo portate pazienza... ()

Nel corso dei mesi non ho avuto molto tempo per osservare le novità sviluppate dai GTaviani su questo argomento.

L'IR è una disciplina che richiede un bel po' di studio e questo forum l'ha affrontata con uno spirito estremamente determinato, buttandosi a capofitto nella progettazione di un motore di ricerca.

Ma la progettazione di un motore, per quanto semplice esso possa essere, non è l'unica strada per giungere all'estrapolazione di qualche nozione utile al posizionamento. E sicuramente non è la strada più breve.

Adesso che ho un po' più di tempo per frequentare il forum, scrivo finalmente il raccontino sulla battaglia navale da più parti richiesto. Con tanto di disegni necessari a visualizzare il problema.

Facciamo finta di essere un motore di ricerca e vediamo un po' che metodo potremmo usare per capire quanto un documento ha a che fare con una query.

Per semplificare al massimo le cose, prendiamo in esame un'ipotetica lingua che possiede un vocabolario composto da una sola parola: "cane".

I documenti scritti in questa lingua possono dunque contenere solo la parola "cane", in un numero variabile di volte.

Dobbiamo innanzitutto trovare il modo per "misurare" i documenti in base alle parole che essi contengono. Lo facciamo disegnando un segmento verticale e dividendolo con cinque tacche:

La tacca in fondo al segmento vale zero, quella appena sopra vale uno, e così via, con la tacca in cima al segmento che vale cinque.

Poniamo il caso di dover "misurare" i seguenti due documenti:

Il documento A, che contiene una sola vola la parola "cane".
Il documento B, che contiene quattro volte la parola "cane".

Come facciamo a "misurare" i due documenti in base alle parole che contengono?

Semplice: il documento A contiene la parola "cane" solo una volta e pertanto gli assegnamo "altezza uno", disegnandolo vicino alla tacca che vale uno.

Il documento B contiene invece la parola "cane" 4 volte e quindi gli assegnamo "altezza 4", disegnandolo vicino alla tacca che vale 4.

Fin qui tutto chiaro? Abbiamo semplicemente tradotto un documento in una posizione lungo un segmento verticale. Più parole "cane" contiene, e più sta in alto.

Anche una query può essere considerata un documento e nella nostra lingua immaginaria anche le query contengono solo la parola "cane", in una quantità variabile di volte.

Di conseguenza, anche le query possono essere posizionate lungo il segmento a seconda del numero di volte in cui la parola "cane" compare al loro interno.

Ad esempio, se l'utente cerca semplicemente "cane", io devo consigliargli il documento A, in quanto il suo contenuto corrisponde esattamente alla query.

Se invece l'utente cerca "cane cane cane cane", io devo consigliargli il documento B, che corrisponde esattamente a questa seconda query.

A seconda di quante volte la parola "cane" appare nella query, io devo calcolare qual'è il documento geometricamente più vicino e proporre all'utente una lista di documenti ordinata per vicinanza geometrica dalla query.

Ovviamente il nostro sistema possiede diverse pecche.

Prima pecca: il segmento ha solo cinque tacche e quindi non si riesce a misurare correttamente un documento contenente la parola "cane" più di cinque volte. Soluzione: si allunga il segmento e si disegnano più tacche.

Seconda pecca: un singolo segmento va bene per misurare i documenti scritti in una lingua che possiede una sola parola. Ma per lingue con vocabolari più grandi è necessario usare più di un segmento.

Vediamo un esempio con una seconda lingua, che possiede due sole parole: "cane" e "gatto".

Ci vuole un secondo segmento per misurare la quantità di volte in cui la parola "gatto" appare nei documenti.

Allora lo disegno in orizzontale e creo una specie di schema della battaglia navale, così che un qualsiasi punto sulla scacchiera sia in grado di dirmi sia quante volte un documento contiene la parola "cane" sia quante volte contiene la parola "gatto":

I documenti da dover analizzare sono stavolta i seguenti:

Il documento A, che contiene 5 volte la parola "cane" e 4 volte la parola "gatto".
Il documento B, che contiene 1 volta la parola "cane" e 2 volte la parola "gatto".

Pertanto la posizione di A è "in alto di 5 e a destra di 4" mentre la posizione di B è "in alto di 1 e a destra di 2" (per il momento guardate solo i punti A e B sul disegno, ignorando i segmenti rossi).

Che succede quando l'utente cerca, ad esempio, "cane gatto"?

Succede che la query "cane gatto" (indicata con q) si posiziona alle coordinate 1:1, in quanto contiene una sola volta la parola "cane" ed una sola volta la parola "gatto", e che il documento apparentemente più vicino a q è B.

E invece no.

Perché il motore non misura il grado di similarità tra query e documento calcolandola semplice distanza tra i due punti bensì calcolando quanto è ampio l'angolo tra i segmenti rossi che ho disegnato sopra.

Come potete notare, l'angolo tra i segmenti rossi appartenenti ad A e q è più stretto dell'angolo esistente tra i segmenti di q e B.

Quindi il motore ritiene che il documento A sia più simile alla query q di quanto lo sia il documento B.

In pratica il motore misura la similarità in base ai rapporti esistenti tra le varie parole contenute nel documento (o query).

Iniziamo ad avvicinarci alle prime conclusioni.

Innanzitutto va notato che il nostro linguaggio composto da due soli termini è ancora distante dai linguaggi reali, che sfruttano decine di migliaia di parole diverse.

Se volessimo creare un sistema per la misurazione di documenti scritti in un linguaggio con soli 3 termini dovremmo aggiungere un terzo segmento a quelli disegnati sopra. Si otterrebbe una struttura 3D, simile ad un cubo di Rubik, che ospita punti in grado di fornire informazioni sui termini che compongono i documenti scritti nel linguaggio di tre termini.

Notate però che (dovreste immaginarlo visualmente) se la query è "cane gatto" e se si aggiunge ad un documento contenente solo parole "cane" e "gatto" un terzo termine, il segmento rosso si sposterebbe e il relativo angolo si amplierebbe.

E si amplierebbe ancora di più aggiungendo nuovi termini/dimensioni (la struttura avrebbe più di 3 dimensioni e la nostra mente non è in grado di immaginarla, ma dal punto di vista geometrico le regole non cambiano).

Questo ci porta alla prima conclusione: fermo restando che il documento deve contenere i termini usati nella query, aumentando il numero di TERMINI DIFFERENTI nel documento ci si allontana inevitabilmente dalla query.

Il secondo punto, altrettanto importante, è che nella realtà le tacche dei segmenti non sono mai equidistanti. Un documento che contiene 10 "cane" non è "alto" il doppio di un documento che contiene 5 "cane", ma generalmente lo è molto meno. Ciò è facilmente desumibile dalle varie formule di tf*idf esistenti.

Questo ci porta alla seconda conclusione: l'influenza di un termine in un documento non è linearmente proporzionale alla quantità di volte in cui il termine appare. Se con una parola ripetuta X volte ottenete un effetto, per ottenere l'effetto doppio non sono sufficienti 2*X ripetizioni, ma molte di più.

Il terzo punto è che le tacche dei segmenti relativi ai termini più diffusi nel corpus posseduto dal motore, distano l'una dall'altra meno di quanto distano le tacche dei segmenti relativi ai termini meno diffusi.

Che significa questo? Significa che i segmenti dei termini meno diffusi hanno tacche più distanti tra loro e che (terza conclusione) la presenza di un termine poco diffuso (nel corpus) allontana il documento dalla query più di quanto faccia la presenza di un termine più diffuso.

Queste sono le basi, sono desumibili anche dalla più semplice delle formule di tf*idf, disponibili a tutti noi fin dagli anni '70. E tante, tantissime altre regole sono deducibili da formule ben più complesse e più recenti.

Ovviamente a tutte le considerazioni scritte si aggiunge il fatto che il motore poi tiene conto di mille altri parametri.

@LowLevel said:

Adesso che ho un po' più di tempo per frequentare il forum

[CUT]

@tutto il forum: per cortesia, fate caso all'ora in cui ha Enrico ha scritto questo post

@Low: illuminante, grazie

@LowLevel said:

Ovviamente a tutte le considerazioni scritte si aggiunge il fatto che il motore poi tiene conto di mille altri parametri.
Già. Ma è proprio questo che rende il "mestiere dei motori" così avvincente, non è vero?

Complimenti per il post, è scritto con una chiarezza invidiabile. E' un peccato che tu non faccia l'insegnante.

Stamattina ho fatto questo: [url=http://www.fattori-arcani-gt.info/ir.php]I.R. Tool..ho seguito alla lettera i consigli di Low, ma aspetto che sia lui a dire se ho sbagliato qualcosa o no. A me sembra che funzioni.

Direi che creando lo script le idee mi si sono chiarite abbastanza. Ho una sola questione per Low: questo sistema si basa solo sulla frequenza delle parole in un documento e non sulla loro posizione: per esempio se la query è gatto nero in genere il motore di ricerca preferirà i testi in cui le parole gatto e nero sono consecutive e disposte nell'ordine della query ("...gatto nero..." è meglio di "...nero gatto..." e sicuramente è meglio di "gatto ... nero"). La posizione delle parole è un fattore di grande importanza e immagino che google non possa non tenerne conto al momento del calcolo dell'angolo. Infatti non si tratta di una funzione di perfezionamento dei risultati (come può essere la popolarità), ma più che altro deve fare parte del sistema che stabilisce qual'è il grado di pertinenza tra un documento e una query..quindi, detto ciò: come gestisce google questo aspetto e come lo implemento nello script in modo da stabilire quale documento testuale sia più adeguato alla query?

Un ultima questione: come hai detto tu ho calcolato l'angolo tramite la formula => prodotto scalare diviso il prodotto delle lunghezze

Dato che la query è necessariamente un sotto insieme del documento sono arrivato alla banale conclusione che il prodotto scalare possa ridursi al prodotto tra i pesi delle varie parole che compongono la query e i corrispettivi pesi nel documento.

Esempio:

=> query:

====> gatto [peso: 0,01]
====> nero [peso: 0,05]

=> documento:

====> io [peso: 0,03]
====> non [peso: 0,05]
====> sono [peso: 0,02]
====> un [peso: 0,09]
====> gatto [peso: 0,002]
====> nero [peso: 0,01]

Da 2 array composti dalle parole che ho elencato e con i pesi che ho elencato, un rapporto scalare tra i due array sarebbe riducibile a:

query_peso_gatto * documento_peso_gatto + query_peso_nero * documento_peso_nero

?

E' corretto o ho sbagliato a fare il prodotto scalare?

P.S. allo script ho aggiunto un database in cui memorizzo le frequenze su yahoo per ogni parola chiave..in modo da disturbare yahoo il meno possibile ed accelerare i tempi di esecuzione. Ovviamente ad ogni parola presente nel database ho associato anche la data in cui è stata recuperata, in modo tale da recuperarla nuovamente una volta ogni mese (nell'ipotesi che la frequenza nel web non cambi di molto in un mese).

P.P.S. per chi volesse usare lo script: non inserite testi lunghi per ora, perchè ancora il database delle frequenze è molto piccolo e quindi con tutta probabilità un documento lungo non permetterà allo script di terminare tutto il lavoro (perchè dovrà fare molte richieste a yahoo). Ho settato il time limit a 240 secondi, ma potrebbe anche fermarsi molto prima.

@kerouac3001 said:

...questo sistema si basa solo sulla frequenza delle parole in un documento e non sulla loro posizione: per esempio se la query è gatto nero in genere il motore di ricerca preferirà i testi in cui le parole gatto e nero sono consecutive e disposte nell'ordine della query ("...gatto nero..." è meglio di "...nero gatto..." e sicuramente è meglio di "gatto ... nero"). La posizione delle parole è un fattore di grande importanza e immagino che google non possa non tenerne conto al momento del calcolo dell'angolo. Infatti non si tratta di una funzione di perfezionamento dei risultati (come può essere la popolarità), ma più che altro deve fare parte del sistema che stabilisce qual'è il grado di pertinenza tra un documento e una query..quindi, detto ciò: come gestisce google questo aspetto e come lo implemento nello script in modo da stabilire quale documento testuale sia più adeguato alla query?Forse questo può chiarire un pò idee, occhio che risale al 1998

http://www.public.asu.edu/~ychen127/cse591f05/anatomy.pdf

**The Anatomy of a Large-Scale Hypertextual Web Search Engine

4.5.1 The Ranking System**

For a multi-word search, the situation is more complicated. Now multiple hit lists must be scanned through at once so that hits occurring close together in a document are weighted higher than hits occurring far apart. The hits from the multiple hit lists are matched up so that nearby hits are matched together. For every matched set of hits, a proximity is computed. The proximity is based on how far apart the hits are in the document (or anchor) but is classified into 10 different value "bins" ranging from a phrase match to "not even close". Counts are computed not only for every type of hit but for every type and proximity. Every
type and proximity pair has a type-prox-weight. The counts are converted into count-weights and we take the dot product of the count-weights and the typeprox- weights to compute an IR score. All of these numbers and matrices can all be displayed with the search results using a special debug mode. These displays have been very helpful in developing the ranking system.

All of these numbers and matrices can all be displayed with the search results using a special debug mode.

Beke, tu lo sai, vero, come si fa ad attivare il debug mode di Google?

E come no
Basta fare la ricerca digitando ~LowLevel dopo la query

A parte gli scherzi, non è detto che nel 2006 Google utilizzi ancora gli stessi approcci al problema del ranking, tuttavia quello, secondo me, è un documento da leggere, almeno una volta.

@Schiappa said:

Scusate l'ignoranza ma mi sta scoppiando il cervello... sto ancora studiando l'IR ma non riesco a figurarmi la situazione...

Per me è stato illuminante il libro:

Intelligenza Artificiale, Autori: S. Russel & P. Norvig. Volume 2 - pgg.555-565 (ISBN 88-7192-229-8 ), Ed. Pearson

ps: P. Norvig è direttore di "Search Quality" della Google Inc.

Certo ...bisogna rispolverare qualche formuletta di teoria della probabilità...
alla fine della fiera si scopre che per avere un buon posizionamento bisogna massimizzare la quantità: A*B dove

A= probabilità di una query per un dato documento "rilevante"
B= Indice della "qualità" del documento (dipendente dai famosi fattori arcani: citazioni accademiche, backlink, PR(? ndr), age,...

la cosa "buffa" è che nella formula è scontato che un documento sia "rilevante"...ergo OTTIMI contenuti!