"Gli è tutto sbagliato, tutto da rifare..." (Bartali)

LowLevel · 30-04-06, 08:57

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.

30-04-06, 08:57	#49 (permalink)
LowLevel Data di registrazione: Mar 2005 Ubicazione: Milano Messaggi: 1,542	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 tfidf 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 2X 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.