Matteo Munaretto
Corso di Sistemi Informativi – Università di Padova
IR for Asian Documents
亞洲人檔案的資訊檢索
Anno Accademico 2006/2007
Introduzione
In questo seminario si presentano delle tecniche di Information
Retrieval su documenti in lingue asiatiche, in particolar
riferimento alla lingua Cinese confrontata successivamente
a quella Giapponese.
L’information retrieval su documenti in lingua Inglese ha più di
30 anni di storia ma nell’ulitma decade con lo enorme
sviluppo della Cina l’attenzione si è maggiormente spostata
sull’asse orientale.
Di conseguenza si sono susseguiti studi e sviluppi su diverse
tematiche quali indicizzazione di pagine in queste lingue
(Cinese, Giapponese, Thai..), traduzione di testi e
riconoscimenti vocali.
Problematiche
Nelle lingue Asiatiche la struttura della frase è nettamente
diversa da quella occidentale, nelle lingue indoeuropee per
esempio il verbo è l’elemento centrale mentre si ritrova ad
essere una semplice componente all’interno di una frase in
Cinese/Giapponese.
Il Cinese scritto consiste di stringhe di ideogrammi separati da
segni di punteggiatura. Questi ideogrammi, cosiddetti kanji
(kan=cina, ji=carattare) sono una rappresentazione grafica
di quello che si vuole esprimere e possono rappresentare
un/più significato/i o far parte di una parola composta con
un significato più complesso.
Il maggior problema che si riscontra in questi di testi è la
mancanza di delimitatori e di spazi che rendono molto
difficile il determinare i limiti di una parola (di un o più
caratteri) in una stringa e bisogna quindi fare riferimento al
suo constesto.
Segmentation
Primo passo quindi prima di sottoporsi a successive analisi è
quello della segmentazione.
Solitamente con questo termine si vuole suddividere le più
lunghe parole con significato preciso all’interno di una
stringa in modo tale da suddividere i vari ideogrammi dando
a ciascuno un senso compiuto all’interno della frase.
Ci sono tre metodi per suddividere un carattere/frase
composto/a in una sue unità ridotta:
• Single characters
• Bigrams
• Simple segmentation of text
Single Characters (1-gram)
Con questo metodo vengono elimitati tutti i segni di
punteggiatura e la parte di testo viene suddivisa in
sequenze di 1 carattere.
Utile se ci fosse sempre un matching esatto tra queries e
documenti prendendo come unità di misura la singola
parola.
PROBLEMA: le sequenze di un carattere hanno molto spesso
significato ambiguo > influiscono su precision (fraz. di
documenti recuparati che sono rilevanti)
Bigrams (2-grams)
Qui la parte di testo viene suddivisa in sequenze di due
caratteri e come per la precedente vengono rimossi i segni
di punteggiatura.
È stimato che l’80% delle parole in Cinese sono bi-sillabe. Su un
testo di un milione di parole, il 67.8% di simboli e il 33.68% di
parole sono di 2 caratteri.
Lo svantaggio sta però nel fatto che possono crearsi degli
accoppiamenti di caratteri senza senso che portano a dei
matching errati tra queries e documenti, sfavorendo la
precision (fraz. di documenti recuperati che sono rilevanti)
Si utilizza il coefficiente di Jaccard per misurare
l’accoppiamento tra l’insieme di 2-grams della query e
l’insieme 2-grams del dizionario. |AUB|/|A∪B|
Es.: 基因改造 sostantivo - 基因
改造 suddivisione senza senso
Simple Segmentation of Text
Per evitare il problema di sequenze senza significato si cerca
con questo metodo di creare sequenze di lunghezza
variabile da 1 a 4 caratteri per poi effettuare poi il matching
esatto durante la fase di recupero.
Questa implementazione si sviluppa in quattro passi.
Simple Segmentation of Text - 1
1. Si controlla la presenza su un piccolo dizionario (2000 parole)
di parole di 1-3 caratteri + alcuni nomi propri di 4 caratteri.
Ad ognuno viene data un etichetta che sta ad indicare se è
un carattere inutile di terminazione, un utile valore numerico
e così via. In caso il matching sia un valore utile allora la
sentenza viene spezzata.
Durante la ricerca richieste di dimensione diversa possono
corrispondere al testo nella stessa posizione causando
ambiguità
> per risolverla viene accennato HMM – ma solitamente
viene trascurato.
Simple Segmentation of Text - 2
2. Vengono applicate diverse regole specifiche per la lingua in
modo da suddividere le sequenza in sottoparole di 2-3
caratteri.
XX due simili caratteri adiacenti fanno spesso riferimento ad
un’unica parola
AX dove A è un insieme di caratteri speciali
…
Simple Segmentation of Text - 3
3. FREQUENCY FILTERING – a questo punto ci possono essere
delle sequenze di 1-4 caratteri dai punti precedenti che non
hanno significato in senso linguistico.
Viene pertanto effettuato un controllo sulle frequenze delle
varie occorrenze nel documento per estrarne delle shortwords più comuni e con significato.
Simple Segmentation of Text - 4
4. Iterazione – le parole del punto tre (etichettate ora come
utili) vengono aggiunte al dizionario di partenza ed è
possibile ripetere l’intero processo.
Diverse soluzioni - 1
• Approccio basato su dizionario
molti algoritmi di segmentazione sono stati
sviluppati usando un dizionario e portano tuttora a
risultati molto soddisfacenti (~90%).
Il punto di forza sta nell’avere un dizionario il più
possibile esaustivo e completo.
Problema è che questa accuratezza nella
segmentazione decade velocemente con la
comparsa di nuove parole/termini.
Diverse soluzioni - 2
• Approccio basato sul carattere
le sequenze vengono suddivise semplicemente
prendendo ogni carattere come unità
fondamentale
Ha il vantaggio di non utilizzare un dizionario pre
definito
Ma file di indici sono molto grandi, molto lento nel
recupero delle informazioni e non è possibile
inserire nessun tipo di informazione linguistica.
Diverse soluzioni - 3
• Approccio statistico
la segmentazione viene effettuata su regole e
statistiche proprie del linguaggio.
> Simple Segmentation of Text
Diverse soluzioni - 4
• Approccio Machine-Learning
in rapporto ai metodi visti precedentemente questi
hanno il vantaggio di non utilizzare un dizionario e
di essere più flessibili alla comparsa di nuovi termini.
Approccio MACHINE-LEARNING
L’approccio in esame utilizza una metodo basato
sull’algoritmo EM (Expectation-Maximization) per il
recupero di informazioni per la lingua Cinese.
Ha i vantaggi di tutti gli altri metodi e colma inoltre alcune
loro mancanze.
Come già detto non utilizza dizionari ma al suo posto
necessita di un ampio documento non segmentato
(facile da reperire).
Da questo documento apprendiamo automaticamente
due dizionari e una distribuzione del lessico utilizzando
l’algoritmo EM e successivamente segmentando il tutto
attraverso l’algoritmo di Viterbi.
Questo approccio per la segmentazione è completamente
non supervisionato e indipendente dal linguaggio, può
quindi essere adattato ad altre lingue.
Self-supervised Segmentation
È spesso possibile recuperare informazioni da parole
composte che al suo interno hanno parole non
conosciute.
Per esempio: se il termine “computer” è già
conosciuto allora se ci imbattiamo in una parola
tipo “computerscience” è naturale spezzare
“science” come possibile nuova parola.
Da questa osservazione il metodo qui proposto è una
variante dello standard EM training ed evita di
rimanere intrappolati in un massimo locale
utilizzando due dizionari:
CORE – che contiene parole ritenute sicure
CANDIDATE – contiene tutti gli altri termini incontrati
EM segmentation and training
Abbiamo una sequenza di caratteri
che vogliamo
suddividere in parti
dove T è il numero di caratteri
nella sequenza ed M è il numero di parole nella
segmentazione.
Il segmento s[i] sarà scelto dal dizionario CORE
o dal dizionario CANDIDATE
Avendo le distribuzioni di probabilità
definita su CORE e
definita si CANDIDATE allora possiamo recuperare la più
probabile segmentazione della sequenza C in parti S come di
seguito.
Per ogni segmento S di C calcoliamo la probabilità congiunta di S
e C tramite:
M1: numero di segmenti che occorrono in CORE
M2: numero di segmenti che occorrono in CANDIDATE
S[k]: occorrenza di uno dei due dizionari
Il goal di questo approccio è trovare la massima probabilità S*
Algoritmo di Viterbi
Data una distribuzione di probabilità definita da θ e Φ su un dizionario,
l’algoritmo di Viterbi viene utilizzato per calcolare la migliore
segmentazione S per la mia sequenza C.
Apprendere quale probabilità utilizzare dato il documento è compito
dell’algoritmo EM.
Tramite l’algoritmo di Viterbi le formule precedenti divengono delle
frequenze pesate:
Il denominatore è una somma pesata del numero di parole in tutte le
possibili segmentazioni, il numeratore è una costante normalizzata.
I passi possono essere calcolati efficientemente attraverso gli algoritmi di
forward and backward.
Defianiamo C1 e C2 rispettivamente come il documento di
training e il documento di validation
V1 e V2 come il CORE e il CANDIDATE
Inizialmente V1 è vuoto e V2 contiene tutte le parole, di lunghezza
1-L, generate dal training; partendo da una distribuzione
uniforme EM viene utilizzato per aumentare la probabilità del
training C1; quando il processo si stabilizza le M parole con più
alta probabilità sono prese da V2 e spostate su V1 cosicché V1
e V2 ora contengano la metà della probabilità totale. Questo
spostamento verso V1 aumento l’influenza delle parole
contenute in CORE nel determinare la segmentazione.
L’algoritmo EM viene rieseguito.
Questa procedura di muovere successivamente le M parole verso
V1 viene detta appunto forward selection.
Viene ripetuta finché l’accuratezza della segmentazione in C2
(documento di validation) porta ad una diminuzione della
F-measure – il che vuol dire che abbiamo incluso erroneamente
alcune parole nel CORE
Quando la forward selection termina, M è decrementata e si
inizia il processo di backward deletion dove le M parole con
più bassa probabilità in V1 sono spostate nuovamente su V2.
EM training viene così ripetuto finché F-measure diminuisce in C2 –
il che significa che abbiamo cancellato alcune parole corrette
nel CORE
Il risultato di tutto ciò è la distribuzione probabilità su un dizionario
che può essere usato da Viterbi per segmentare le sequenze di
test.
Lexicon pruning
Per eliminare erronee agglomerazioni, tipo suddividere
sizeofthecity in sizeof|thecity, e per evitare al nostro algoritmo
EM il massimo locale, utilizziamo criteri basati su mutua
esclusione per fare il pruning.
La mutua informazione tra due variabili è data da:
dove un valore alto indica una forte dipendenza e 0 la completa
indipendenza.
Nel nostro caso vengono confrontati i valori ottenuti con dei valori
soglia e ricalcolata la probabilità tra le due variabili in gioco, in
modo da spostare i pesi della distribuzione su parole con
lunghezza minore.
Prestazioni
A differenza di altri metodi di segmentazione sempre
basati sull’algoritmo EM questo qui presentato ha il
vantaggio di utilizzare delle statistiche più affidabili
da semplici statistiche sulla frequenza nonché si
utilizza uno schema di probabilità che sposta
quest’ultima tra parole senza per forza eliminarne.
Il più grande svantaggio è il time-consuming.
Segmentation related to IR-performance
Performance diminuiscono anche perché in Cinese molte
parole sono legalmente rappresentate da alcune sue
sottoparti
Per concludere
Questo metodo dimostra come le tecniche di
machine learning possano essere efficaciemente
utilizzate per segmentazioni di testi ed information
retrieval per la costruzione di sistemi adattabili.
L’accuratezza del IR aumenta all’aumentare
dell’accuratezza della segmentazione fino ad un
certo punto per poi arrivare ad una saturazione e
diminuire.
In futuro probabilmente ci si focalizzerà nell’avere
una più precisa estrazione di parole chiave
piuttoste che una migliore segmentazione.
Un soddisfacente Chinese IR system dovrebbe
utilizzare un insieme di techine pure utilizzate per la
lingua inglese in concomitanza con questa
tecnica di segmentazione non supervisionata.
Chinese VS Japanese
La lingua Giapponese utilizza in gran parte i Kanjii, ovvero i
caratteri Cinesi e per questo motivo gran parte degli
argomenti/topics in lingua Cinese possono essere riportati tale
e quali negli equivalenti in lingua Giapponese.
Per esempio:
Sembrano uguali visto che anche la parte giapponese utilizza
solamente Kanjii.
Questo non è però più vero nel sequente esempio:
Pertanto non è sempre vera questa correlazione e deve essere
eventualmente utilizzata attentamente in combinazione con
altri metodi.