Catalogazione by Context: idee di base

La catalogazione by context ha l'obiettivo di catalogare un documento web W analizzando i contesti in cui compaiono i link a W.

Consideriamo i seguenti fatti:

I contesti contengono molto meno testo di quanto non ne contenga il documento vero e proprio.
I contesti nei quali i link sono immersi devono essere indicativi del contenuto del documento puntato (se cio' non fosse vero un utente non sarebbe piu' guidato dai link nella navigazione sul web).

Poiche' i contesti sono piccoli e significativi, i termini in essi contenuti devono essere fortemente indicativi del contenuto del documento.

Dalla piccola dimensione dei contesti segue anche che la loro analisi non puo' essere effettuata con tecniche basate su analisi statistiche della frequenza dei termini. Deve piuttosto essere utilizzato un algoritmo che estragga i termini significativi dai contesti e sfrutti la loro semantica.

L'estrazione dei termini verra' effettuata utilizzando un part-of-speech tagger (LTPOS), l'analisi semantica verra' effettuata utilizzando un thesaurus (WordNet).

Algoritmo di catalogazione

Per effettuare l'analisi dei contesti descriviamo ogni categoria con un vettore di pesi. Ogni elemento del vettore corrisponde ad un livello dell'albero delle categorie.

L'insieme di tutte le categorie è rappresentato da una matrice MC di pesi. Ogni riga della matrice MC corrisponde ad una categoria.

L'analisi dei contesti consiste nell'aggiornamento degli elementi della matrice MC, via via che si estraggono i termini.

Algoritmo di aggiornamento di MC

Per ogni termine t del contesto in esame, si aggiornano gli elementi della matrice MC corrisponenti.

L'aggiornamento consiste nel sommare agli elementi di MC un peso pari a:

dl * pm * dw
dl * sm * dw
dl * rm * dw
dl * hm(n) * dw

a seconda che si abbia un match di morph(t) con:

un termine che descrive le categorie
un sinonimo
un termine correlato
un hyponim di livello n

(dl dipende dalla profondità del contesto, dw dipende dalla categoria sintattica del termine t).

Vorremo trattare correttamente il caso dei termini composti (noun phrases formati da piu' termini di WordNet, vedi hypernyms.html).

Nel seguito indicheremo con D l'insieme dei termini composti che descrivono le categorie, mentre indicheremo con DS l'insieme dei termini semplici che compongono i termini in D.

Tabella degli intorni TI

Per ogni termine t in DS costruiamo l'insieme I(t) dei termini dell'intorno di t (sinonimi, hyponyms, ecc.). Per ogni termine s in I(t) e' definito, inoltre, il peso di s rispetto a t che indichiamo con w(s,t) (ad esempio w(s,t) = sm se s e' un sinonimo di t. Alcuni termini possono essere contemporaneamente, sia sinonimi, sia correlati, sia hyponyms, in tal caso assumiamo per w(s,t) il massimo dei pesi previsti).

Poiche' i termini in DS sono semplici, la costruzione degli intorni I(t) sara' effettuata utilizzando WordNet.

La tabella TI e' una tabella hash con chiave un termine semplice e valore un insieme di coppie <t, w> dove t e' un termine semplice e w un peso.

Indichiamo con TI(s) l'insieme delle coppie <t, w> associate ad s.

Costruiamo la tabella TI secondo il seguente algoritmo:

Poniamo TI(s) = insieme vuoto per ogni termine semplice s
Per ogni t in DS:
- Per ogni s in I(t)
  - Poniamo TI(s) = TI(s) unito {<t, w(s,t)>}

Con la tabella TI cosi' costruita, dato un termine s si puo' risalire velocemente ad un termine t usato nella descrizione delle categorie ed avere il peso w(s,t).

esempio:

sia 'sport event' la descrizione di una categoria, allora sport event e' in D, sport ed event sono in DS.

Allora:

I(sport) = {football, basketball, tennis, ... }
I(event) = {happening, ... }
...

TI(sport) = {<sport, 1.0>, ... }
TI(event) = {<event, 1.0>, ... }
TI(football) = {<sport, 0.9>, ... }
TI(basketball) = {<sport, 0.9>, ... }
TI(tennis) = {<sport, 0.9>, ... }
TI(happening) = {<event, 0.6>, ... }
...

(i pesi in questo esempio sono del tutto ipotetici)

Tabella dei termini TT

La tabella dei termini TT e' una tabella hash con chiave un termine composto t e valore un insieme di riferimenti {<r₁,c₁>, ..., <r_n,c_n>} agli elementi di MC (la matrice delle categorie) corrispondeti al termine t.

Indichiamo con TT(t) l'insieme {<r₁,c₁>, ..., <r_n,c_n>} dei riferimenti.

I termini composti presenti in TT sono i termini di D.

Tramite la tabella TT possiamo risalire velocemente agli elementi della matrice MC da aggiornare.

Estrazione dei termini dai contesti

Utilizzando LTPOS si esegue un tagging dei termini nei contesti.

Analizzeremo i tag e considereremo sequenze di aggettivi e sostantivi come termini composti.

esempio:

la frase:

The World Wide Web has evolved into an impressive open structure for sharing information.

sara' marcata da LTPOS come:

The_DT World_NP Wide_NP Web_NN has_VBZ evolved_VBN into_IN an_DT impressive_JJ open_JJ structure_NN for_IN sharing_VBG information_NN ._.

Considerando le sequenze di aggettivi e sostantivi otteniamo i seguenti termini composti:

World Wide Web
impressive open structure
information

Notare che estraendo i termini composti non commetteremo l'errore di considerare il termine world a se' stante (che ci porterebbe fuori strada), ma piuttosto come parte di un termine piu' complesso (World Wide Web e' in WordNet) e piu' indicativo del contenuto semantico della frase.

L'utilizzo di LTPOS ci permette, inoltre, di disambiguare i ruoli che i vari termini svolgono all'interno di una frase: sarebbe stato difficile utilizzando esclusivamente WordNet, stabilire, ad esempio, che open svolge il ruolo di aggettivo nella frase precedente (open puo' anche essere, a seconda dei contesti, un sostantivo o un verbo).

Elementi della matrice da aggiornare

I termini composti estratti dai contesti non sempre combacieranno con i termini composti nella tabella TT, cercheremo, quindi, utilizzando la tabella degli intorni TI (costruita utilizzando WordNet), di risalire ai termini di nostro interesse.

Ad esempio se incontrassimo il termine composto football happening potremmo voler risalire al termine composto sport event presente in TT.

Sia s il termine composto estratto da un contesto e siano s₀, ..., s_n i termini complessi che compongono s (vedi hypernyms.html).

Determinazione degli elementi da aggiornare

Per ogni termine s_i consideriamo l'insieme T_i = { t | <t,w> e' in TI(s_i) } dei termini semplici di interesse correlati ad s_i (ad esempio: se s_i = football allora sport e' in T_i).

Generalmente l'insieme T_i conterra' un solo termine, ma niente ci permette di escludere che in casi particolari possa contenere piu' di un elemento (questa eveninenza e' legata al fatto che i termini del linguaggio naturale possono avere molteplici significati).

Puo' accadere che T_i non contenga nessun termine, allora sara' scartato.

Quindi costruiremo tutti i termini composti possibili della forma:

t₀ , ..., t_n

al variare di t_i in T_i.

Per ogni termine t = t₀ , ..., t_n cosi' ottenuto aggiorneremo gli elementi della matrice MC corrispondenti ai riferimenti TT(t). Se t non e' in TT allora non effettueremo alcun aggiornamento.

Puo' accadere che nessun termine cosi' ottenuto sia in TT a causa di aggettivi che "specializzano troppo" il termine t.

Per ovviare a questa evenienza se nessun t e' in TT, allora si scarta il termine semplice piu' lontano dal sostantivo e si ripete il procedimento.

Con questa euristica per il riconoscimento dei termini composti si risolvono anche i problemi relativi alle relazioni Hypernym e Hyponym evidenziati in hypernyms.html.

Determinazione dei pesi

Per aggiornare la matrice MC e' necessario stabilire il peso del termine t. Tramite la tabella TI e' possibile risalire al peso dei termini semplici. Vorremo definire una misura per dare un peso ai termini composti.

Sia s = s₀ , ..., s_n un termine composto estratto da un contesto e sia t = t₀ , ..., t_n un termine composto corrispondente, presente in TT.

Due possibili misure per valutare w(s,t) (il peso del termine composto s rispetto al termine composto t) sono:

Prodotto dei termini w(s_i, t_i) al variare di i
Media dei termini w(s_i, t_i) al variare di i

La misura 1 tendera' a fornire valori per w(s,t) piu' piccoli di quelli forniti dalla misura 2.