IR for Asian Documents 亞洲人檔案的資訊檢索

Anno Accademico 2006/2007

Matteo Munaretto

Corso di Sistemi Informativi – Università di Padova

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 short-words 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.