Predizione e Statistica

(1)

Predizione e Statistica

Lo stretto legame tra predizione e statistica ha portato molti studiosi a concentrare le loro ricerche su questo binomio.

In questo capitolo prenderemo in esame i principali fondamenti teori- ci su cui si basano i moderni processi di predizione. Vedremo in dettaglio come modellare il linguaggio naturale ed analizzeremo vari modelli probabilistici fino ad arrivare al Part-of-Speech Tagging, ovvero una metodologia di comprensione automatica del testo.

2.1 Metodi Formali per il Trattamento del Lin- guaggio Naturale

L’ultimo secolo ha sempre più caratterizzato questa epoca definita più volte come la Società dell’Informazione. Si pensi come il linguaggio rappresenti la

35

(2)

nostra vita e come ci circonda. Inoltre la quantit`a di informazioni aumenta sempre pi`u velocemente soprattutto in forma testuale (libri, giornali, riviste) ed elettronica (pagine web, e-mail, chat).

Compito della linguistica computazionale è dunque quello di raccogliere grosse quantità di dati linguistici per ricostruire, attraverso opportune ope- razioni di analisi, l’organizzazione e la struttura del linguaggio. Per far questo i moderni strumenti vedono l’applicazione di metodi formali, come la logica, la matematica e la statistica, ma anche di strumenti informatici capaci di trattare le grandi quantità di dati in modo molto più veloce rispetto alle vecchie tecniche manuali.

Elemento base per svolgere tutto il procedimento di analisi sopra descrit- to, è il concetto di corpus. Un corpus è una raccolta di testi selezionati ed organizzati secondo precisi criteri al fine di essere utilizzata come campione rappresentativo del linguaggio [20]. L’avvento dell’informatica ha consentito un miglioramento dei procedimenti di formazione dei corpora con la nasci- ta dei cosiddetti corpora elettronici. Questi corpora particolari permettono di immagazzinare quantità inimmaginabili di contenuti, consentendo una migliore ed efficiente fase di gestione ed interrogazione.

La rappresentatività di un corpus è un elemento chiave poiché esso vuole fornire l’espressività di un linguaggio, nonostante rimanga una porzione finita. Naturalmente è importante considerare la dimensione di un corpus, intesa come il numero di parole che esso contiene. L’evoluzione dei corpora

(3)

ha visto due generazioni: una prima, negli anni ’60-’70, dove le collezioni di testi erano formate da milioni di parole, e una seconda generazione dove i corpora furono in grado di contenere decine di milioni di elementi (come quelli nati negli anni ’80-’90) o perfino centinaia di milioni di parole, come i corpora dei giorni nostri. Le tecniche statistiche di campionamento possono aumentare il grado di rappresentativit`a di un corpus, ma esso rimane comunque un frammento parziale e incompleto del linguaggio; per questo nel mondo della linguistica ci sono teorie classiciste che ritengono le tecniche basate su corpora del tutto prive di fondamenti logici.

Negli ultimi decenni `e emerso il consenso generale che la cognizione uma- na sia basata su processi probabilistici; lo dimostra il linguaggio che utilizziamo, sempre pi`u caratterizzato da un sistema probabilistico [21]. Ne consegue che le teorie linguistiche sono dirette verso metodi statistici per modellare il linguaggio.

Ma cosa vuol dire applicare la statistica ad un linguaggio? Lo scopo di un modello probabilistico per le sequenze di parole è di assegnare un valore ad ogni sequenza in modo da far acquisire espressività e di comprendere la regolarità del linguaggio.

La modellazione stocastica del linguaggio, introdotta dallo Speech Reco- gnition (riconoscimento vocale), `e una metodologia di successo nel campo del NLP. Esistono vari approcci ai modelli statistici, ma tutti sono riconducibili allo schema del Noisy Channel (o Bayesian Inference).

(4)

Nello Speech Recognition, data una stringa di fonemi che rappresenta la pronuncia di una parola in un contesto, vogliamo capire e calcolare la sequenza di sillabe che indica anzich´e la pronuncia lessicale, perci`o dobbiamo essere in grado di trovare la parola nel vocabolario. In modo analogo, data una sequenza non corretta di “mis-spelled word”, vogliamo trovare la serie corretta di lettere che rappresentano la “spelled word”.

SOURCE word noisy

word DECODER

guess at original word Noisy Channel

Figura 2.1: Il Noisy Channel Model.

L’intuizione del Noisy Channel Model (Figura 2.1) `e di riuscire a deco- dificare la pronuncia di una parola che ha attraversato un canale di comuni- cazione “rumoroso” (in inglese noisy). Questo canale introduce un rumore che rende difficile riconoscere le parole realmente pronunciate. `E necessario costruire un modello del canale in modo da capire come avvengono le modi- fiche e quindi essere capaci di compensare. La metafora del Noisy Channel

`e stata utilizzata nel modello di speech recognition nei laboratori IBM negli anni ’70 [22]. Questo tipo di problema `e un caso particolare dell’inferenza Bayesiana (1763).

Vediamo un esempio inerente lo speech recognition: data una stringa di suoni (diciamo [ni]), vogliamo conoscere quale parola corrisponde ad essa.

Secondo l’interpretazione di Bayes di questo problema, dovremmo iniziare

(5)

considerando tutte le possibili classi (in questo caso tute le possibili parole) cui la stringa di suoni pu`o equivalere. In altri termini vogliamo scegliere la parola che molto probabilmente viene associata alla combinazione di suoni ([ni]), ovvero la parola contenuta in un vocabolario V che massimizza la seguente probabilit`a:

P(w | O)

dove w identifica la parola che stiamo cercando, mentre O `e la sequenza di suoni osservata.

Indicando con ˆw la stima della parola corretta w, la seguente equazione¹ ci assicura la migliore parola per w:

ˆ

w = arg max

w∈ V P(w| O) (2.1)

Mentre appare chiaro cosa significa l’equazione (2.1), risulta difficile pen- sare a come calcolare il valore risultante. Applicando la regola di Bayes² è possibile spezzare l’equazione (2.1) in tre altre probabilità più semplici da calcolare:

ˆ

w = arg max

w∈ V

P(O| w) P(w)

P(O) (2.2)

Adesso, per esempio, possiamo stimare P(w) come la frequenza della

1La notazione arg max f (x) vuole indicare l’argomento x per cui la funzione f raggiunge il suo massimo valore.

2Regola di Bayes: dati due eventi A e B si ha che P(A| B) = P(A ∩ B)

P(B) = P(B| A)P(A) P(B) , si veda l’Appendice A.

(6)

parola stessa. Visto che stiamo massimizzando su tutte le parole del vocabolario, possiamo anche non considerare il denominatore P(O) in quanto compare ogni volta ma non cambia mai. Dunque:

ˆ

w = arg max

w∈ V

P(O| w) P(w)

P(O) = arg max

w∈ V P(O| w) P(w) (2.3)

Riassumendo, la parola più probabile data una sequenza di suoni, può essere calcolata come il prodotto di due probabilità per ogni vocabolo in V e scegliendo la parola per cui il prodotto è massimo. I due termini del prodotto sono chiamati Prior probability, P(w), e likelihood, P(O| w).

ˆ

w = arg max

w∈V P(O| w)

| {z }

likelihood

prior probability

z }| { P(w)

2.2 Modelli Probabilistici

Per svolgere le funzioni di predizione, un sistema di word prediction deve essere in grado di accedere ad un modello rappresentativo della lingua, ovvero una descrizione approssimativa della struttura e delle regolarit`a presenti nel linguaggio naturale. Esistono sostanzialmente due tipi di modelli linguistici (Language Model): statistici e knowledge-based (basati sulla conoscenza). Un modello statistico `e fondato sull’estrazione automatica di dati da vaste raccolte di testi (corpora), mentre un modello knowledge-based si affida alle generalizzazioni linguistiche definite, come le regole grammati-

(7)

cali. Generalmente i sistemi di word prediction fanno uso di modelli del primo tipo, ma alcuni di essi si avvalgono di informazioni predefinite sul linguaggio come quelle utilizzate dai modelli basati sulla conoscenza. Nascono cos`ı modelli ibridi che cercano di ottenere un modello pi`u rappresentativo e maggiormente inerente al linguaggio naturale.

2.2.1 Modelli Frequency-based

La maggior parte dei primi sistemi di predizione, sviluppati agli inizi degli anni ’80, fondò le sue origini su statistiche delle singole parole (“unigram”, come vedremo in seguito), ovvero valori dati dalla frequenza di occorrenze di un termine in uno o più testi di riferimento. Di conseguenza predire la parola corrente o la successiva dipendeva solo dalla probabilità della stessa parola di apparire in uno scritto, senza considerare alcuna informazione sul contesto.

L’assenza del quadro generale della frase comportava l’inappropriatezza dei suggerimenti sia dal punto di vista sintattico che semantico.

Il modello più semplice in assoluto utilizza il presupposto che ogni parola del linguaggio possa essere seguita da qualsiasi altra, senza alcun tipo di limitazione. In termini matematici avremo che tutte le parole hanno la stessa probabilità di apparire in una frase. In questo modo, se considerassimo un linguaggio composto da 100.000 vocaboli, la probabilità suddetta sarebbe

1

100.000. In relazione a ci`o, acquisisce un ruolo significativo il concetto di frequenza con cui le strutture linguistiche occorrono nei processi di acquisi-

(8)

zione, composizione e produzione del linguaggio. Ha senso, infatti, definire la frequenza come la probabilit`a di una parola di occorrere in un contesto oppure come la probabilit`a di estrarre una parola w da un certo corpus C.

Sia C(w) il numero delle volte in cui w appare in C e indichiamo con |C| la dimensione totale del corpus; definiamo formalmente:

P(w) ≈C(w)

|C| (2.4)

Dunque l’occorrenza di una parola in un corpus è paragonabile al verifi- carsi di un certo evento in un dato spazio di probabilità proprio come in una distribuzione uniforme, dove la probabilità di un evento A in uno spazio Ω

`e ricavabile da

P(A) = |A|

|Ω| (2.5)

Questo meccanismo non `e di particolare interesse quando ci troviamo di fronte un testo che rispetta delle regole ben precise che attribuiscono un significato ad esso. Ha senso parlare di metodi che riescano a comprendere il contesto in cui una parola appare cos`ı da rendere migliore il suo valore all’interno della frase (soprattutto nel caso di parole ambigue). In questa specifica ottica, si possono definire le collocazioni come le espressioni lessicali che consistono di due o pi`u termini che formano, ad esempio, i modi di dire, le locuzioni verbali e le espressioni idiomatiche o composte (come “a quattr’occhi”, “stanco morto”, “Banca d’Italia”, “prendere un granchio” o

(9)

“fare la cresta”). Contare le occorrenze di collocazioni risulta un metodo semplice per trovare la frequenza di queste sequenze di parole. `E evidente, infatti, che sussiste un legame tra i termini se questi occorrono spesso insieme all’interno di un corpus. Un primo passo interessante da fare potrebbe essere quello di analizzare un testo per trovare le sequenze di due parole pi`u comuni (comunemente dette “bigram”, definite in seguito).

C(w₁, w₂) w₁ w₂ 80.871 of the 58.841 in the 26.430 to the 21.842 on the 21.839 for the 18.568 and the 16.121 that the 15.630 at the

15.494 to be

13.899 in a

13.689 of a

13.361 by the 13.183 with the

Tabella 2.1: Collocazioni selezionate in un corpus in base alla frequenza.

Selezionare i bigram (coppie di parole) più frequenti, però, può risul- tare poco interessante (in Tabella 2.1 è riportato l’esempio in [1] in lingua inglese). La tabella mostra i bigram più frequenti in un corpus e la loro

(10)

frequenza.

Tag pattern Example AN linear function NN regression coefficients AAN Gaussian random variable ANN cumulative distribution function NAN mean squared error

NNN class probability function NPN degrees of freedom

Tabella 2.2: Part-of-Speech tag per il filtraggio delle collocazioni.

Un passaggio interessante si ottiene attraverso una funzione euristica che propone una ricerca nel corpus applicando una serie di filtri formati da sequenze di tag di Part-of-Speech [24], esempi in Tabella 2.2. Questi filtri³ servono per identificare le occorrenze pi`u frequenti di sequenze di parole. In questo modo si ottengono informazioni pi`u utili: in Tabella 2.3 sono indicate, dopo l’applicazione dei filtri, le collocazioni maggiormente collegate.

2.2.2 Modelli Basati su Media e Varianza

I metodi frequency-based funzionano bene per frasi fissate. Molte collocazioni consistono di due parole che per`o possono avere una relazione flessibile nel corpus e possono non comparire sempre in ordine all’interno della frase.

Considerando un semplice esempio in lingua inglese, mostrato in [1], possia-

3Nell’esempio in Tabella 2.3 si ha: A = Adjective, aggettivo; N = Noun, sostantivo;

P = Preposition, preposizione.

(11)

C(w1, w2) w1 w2 Tag Pattern

11.487 New York AN

7.261 United States AN

5.412 Los Angeles NN

3.301 last year AN

3.191 Suadi Arabia NN

2.699 last week AN

2.514 vice president AN

2.378 Persian Gulf AN

2.161 San Francisco NN

2.001 Middle East AN

1.867 Soviet Union AN

1.850 White House AN

1.633 United Nations AN

Tabella 2.3: Collocazioni filtrate con i Part-of-Speech tag.

mo spiegare meglio la situazione sopra descritta: osserviamo il verbo knock (“bussare”) e il suo argomento pi`u frequente, door (“porta”).

• she knocked on his door;

• they knocked at the door;

• 100 women knocked on Donaldson’s door;

• a man knocked on the metal front door.

Le parole che occorrono tra knock e door sono diverse e la distanza tra questi due termini non `e costante, ma varia a seconda del contesto. Un

(12)

metodo per scoprire la relazione tra i due termini `e calcolare media e varianza delle distanze⁴ tra le due parole all’interno del corpus. La media misura semplicemente la distanza media tra gli oggetti, mentre la varianza indica quanto la distanza individuale devia dal valore medio. Si pu`o dunque stimare cos`ı la varianza:

s²= Pn i=1

(di− ¯d )² n − 1

dove n è il numero di volte che le due parole sono occorse, d_i indica la distanza per la parola i-esima e ¯d è il valore medio. Se la distanza è la stessa in tutti i casi, la varianza varrà zero.

Il metodo basato su media e varianza caratterizza la distribuzione di distanze tra due parole in un corpus. Questa informazione pu`o essere usata per rivelare le collocazioni cercando le coppie con un basso scarto. Un valore basso significa che due parole occorrono solitamente alla stessa distanza mentre un valore nullo esprime che i due oggetti si presentano sempre esattamente alla stessa distanza.

2.2.3 Frequenza di Sequenze di Parole

La word prediction è un derivato dello Speech Recognition e coinvolge la cosiddetta Augmentative and Alternative Communication (AAC, comunica- zione aumentata e alternativa) per le persone disabili. In questo campo, l’identificazione della parola risulta alquanto difficile poiché l’input è ambi-

4Per distanza considereremo il numero di parole tra i due termini interessati.

(13)

guo. Di conseguenza solo guardando le parole precedenti `e possibile trovare uno spunto per indovinare la parola successiva.

Questa abilità di predire la parola è importante per i sistemi di comunica- zione assistita, i quali sono di ausilio a persone fisicamente o linguisticamente disabili. Inoltre consideriamo la possibilità di notare gli errori di ortografia e di poterli correggere.

La predizione della parola è intrinsecamente collegata ad un altro problema: calcolare la probabilità di una sequenza di parole. Vedremo adesso come l’introduzione dei modelli n-gram è stato determinante per la soluzione a questo problema.

2.3 Inferenza Statistica ed n -gram

Lo Statistical Natural Language Processing si occupa di fare inferenza statistica del linguaggio naturale. Ci`o consiste nel selezionare determinati dati (ovvero estrarre un campione significativo) ed effettuare deduzioni di tipo statistico sulla loro distribuzione.

Consideriamo la propriet`a che l’immissione di una parola in una frase `e strettamente influenzata dall’ambiente in cui appare, ovvero il suo contesto.

Questo fatto importante è stato a lungo studiato cos`ı da poter tener conto del contesto di applicazione. Il risultato è un “n-gram model ” il quale ha reso possibile calcolare la probabilità di una particolare parola come facente

(14)

parte di una sequenza. In questo modo si sono potute catturare alcune preziose dipendenze sintattiche e semantiche [23].

Definizione di n -gram

La predizione della parola successiva pu`o essere vista come il tentativo di stimare la funzione di probabilit`a P di:

P(wn| w1, w2, . . . , wn−1)

ovvero la probabilit`a che wn sia la parola successiva nella frase formata dalle n − 1 parole precedenti, w₁, . . . , w_n−1.

In questo problema stocastico, utilizzeremo una classificazione delle parole precedenti (spesso citata come history) per poter predire quale sarà la successiva. Nasce il bisogno di un metodo per raggruppare le diverse history che, in un certo senso, si assomigliano. Questo raggruppamento serve ad ottenere una migliore capacità di comprensione del contesto. Un possibile strumento per raggruppare è utilizzare l’Assunzione di Markov⁵ la quale prevede che solo il contesto locale (le ultime poche parole) influisce sulla determinazione della parola successiva. Se riusciamo a costruire un modello dove concentrare nella stessa classe di equivalenza tutte le history che

5Lo studio delle probabilità delle catene di eventi collegati tra loro fu iniziato dal matematico russo Andrei Andreieviˇc Markov (1856 - 1922), allievo di Chebyshev. L’analisi delle catene di Markov si è diffusa a partire dalla metà del XX secolo, grazie alle loro applicazioni nell’osservazione dei fenomeni fisici, biologici, sociali, in cui le probabilità di un evento dipendono dal risultato immediatamente precedente.

(15)

hanno le stesse ultime n − 1 parole, otteniamo un modello di Markov del (n − 1)-esimo ordine o un modello n-gram (n-gram word model ).

Naturalmente incrementando il valore di n, aumenta la precisione del modello, ma ne consegue un’esponenziale crescita dei parametri e quindi della complessit`a. Per questo solitamente vengono utilizzati n-gram con valori di n = 1 (unigram), 2 (bigram), 3 (trigram) o 4 (four-gram).

Gli n-gram non sono l’unico metodo per formare classi di equivalenza;

`e possibile infatti sfruttare lo stemming, ovvero l’analisi della radice del vocabolo, oppure il raggruppamento delle parole in classi semantiche.

Esempio di n -gram

Abbiamo visto che un possibile modello potrebbe considerare la sola frequenza relativa della parola. Di conseguenza le parole pi`u frequenti verran- no suggerite continuamente per prime, ma non sempre questo procedimento risulta corretto. Un modello leggermente pi`u complesso potrebbe permette- re che ogni termine che segue una frase, deve apparire nella sua frequenza normale di occorrenza.

Consideriamo un esempio, esposto in [2], per meglio comprendere il vantaggio introdotto dai modelli n-gram rispetto a quelli basati su frequenza di singole parole. L’articolo determinativo inglese “the” (“il”) ha un’alta frequenza relativa, infatti esso occorre 69.971 volte nel Brown Corpus, mentre il sostantivo “rabbit” (“coniglio”) appare solo 11 volte. Possiamo, dunque,

(16)

sfruttare queste frequenze relative per assegnare una distribuzione di pro- babilità alle parole da predire. Cos`ı facendo, dopo aver incontrato, in una frase, l’avverbio “anyhow ” (“ad ogni modo”, “comunque”), possiamo avere la probabilità 0.07 di avere “the” e 0.00001 per “rabbit”. Supponiamo, però, di avere la frase: “Just then, the white” (“Proprio allora, il bianco”);

in questo preciso contesto è evidente che la parola “rabbit” è più probabile che sia la successiva rispetto a “the”. Questo esempio suggerisce che risulta vantaggioso osservare, piuttosto che la frequenza relativa, la probabilità condizionata di una parola date le precedenti. Nel nostro caso sarebbe la probabilità di avere “rabbit” data la parola “white”, ovvero P(rabbit| white).

2.3.1 Modelli n -gram

Cerchiamo di esprimere formalmente tutti i concetti appena visti. Per far questo consideriamo l’esempio suddetto. Consideriamo una qualsiasi frase come una sequenza di parole lunga n; esprimiamo con w₁, . . . , w_n detta sequenza. Calcolare l’occorrenza di ogni parola nella sua corretta locazio- ne come un evento indipendente, significherebbe riuscire a quantificare la probabilit`a:

P(w1, w₂, . . . , wn) (2.6)

L’equazione (2.6) pu`o essere trasformata come una catena di probabilit`a

(17)

(come in Appendice A), decomponendo:

P(w1, . . . , wn) = P(w1)P(w2| w1)P(w3| w1, w2) . . . P(wn| w1, . . . , wn−1) =

= Yn k=1

P(wk| w₁, . . . , w_k−1) (2.7)

Adesso si pone il problema di come riusciamo a stimare il valore di

P(wk| w₁, . . . , w_k−1) (2.8)

E impensabile riuscire a calcolare la probabilit`` a di una parola data una lunga

sequenza di termini precedenti: siamo costretti ad approssimare e i modelli n-gram consentono una buona approssimazione.

In prima istanza consideriamo un bigram: questo consente di valutare la probabilità di una parola data solamente la precedente. Ciò che è stato appena detto può essere definito come l’approssimazione della probabilità (2.8) alla probabilità condizionata della parola k-esima data la (k −1)-esima, ovvero

P(wk| w1, . . . , wk−1) ≈ P(wk| wk−1) (2.9)

Il presupposto secondo il quale la probabilit`a di una parola dipenda solo dalla precedente, `e detta Assunzione di Markov (come visto nella Sezione 2.3). I modelli di Markov sono strumenti stocastici la cui predizione non si basa su una storia di grosse dimensioni, vale a dire non si affida a molte

(18)

parole antecedenti, ma ad un numero limitato.

E possibile generalizzare il bigram come trigram (dove vengono esamina-` te le due parole precedenti) e, di conseguenza, come n-gram. Cos`ı otteniamo che l’equazione generale per l’approssimazione degli n-gram alla probabilit`a condizionata della parola successiva in una sequenza, `e la seguente:

P(wk| w₁, . . . , w_k−1) ≈ P(wk| w_k−n+1, . . . , w_k−1) (2.10)

L’equazione (2.10) indica che la probabilità di un termine wkin una frase date tutte le parole precedenti, può essere stimata come la probabilità della stessa parola date solo le precedenti n.

I modelli n-gram possono essere addestrati attraverso il conteggio e la normalizzazione in modo da ottere probabilit`a con valori nell’intervallo [0, 1].

La probabilit`a di un certo bigram in un ben definito training corpus, `e ottenuta contando le occorrenze del bigram e dividendo per la somma di tutte le coppie che condividono la stessa prima parola:

P(wk| w_k−1) = C(w_k−1, wk) P

wC(w_k−1, w) (2.11)

Osserviamo che la somma dei bigram con la prima parola w_k−1deve essere uguale alla somma degli unigram di wk−1. Pertanto possiamo semplificare l’equazione (2.11):

P(wk| w_k−1) = C(wk−1, wk)

C(w_k−1) (2.12)

(19)

In generale, nel caso di un n-gram si ha

P(wk| wk−n+1, . . . , wk−1) = C(w_k−n+1, . . . , w_k−1, wk)

C(wk−n+1, . . . , wk−1) (2.13)

L’equazione (2.13) stima il rapporto tra la frequenza di una particolare sequenza e la frequenza di un prefisso. Questa proporzione indica la frequenza relativa e viene spesso usata nella tecnica del Maximum Likelihood Estimation (MLE, stima di massima verosimiglianza), [1] e [2].

2.3.2 Smoothing

Come abbiamo visto, l’uso degli n-gram permette di catturare importanti dipendenze sintattiche e semantiche tra le parole che occorrono frequentemente assieme. Nonostante ciò, alcuni suggerimenti rimangono del tutto non adatti perché gli n-gram sono limitati ad un contesto locale di un numero fissato di parole, abitualmente non maggiore a due o tre termini. Questa limitazione è dovuta al fatto che questi modelli necessitano di un addestramento con un corpus, il quale, completo che sia, rimane una porzione finita e limitata. Perciò alcuni n-gram sono sicuramente assenti nel corpus, questo comporta un’insufficienza dei dati. In quest’ottica, qualche bigram avrà probabilità a zero quando nella realtà non sarebbe cos`ı. Inoltre il metodo MLE produce stime non proporzionate quando la misura non è nulla ma è comunque un valore molto piccolo.

Questo problema `e diffuso per gli n-gram, dato che questi modelli non

(20)

producono un contesto a lunga distanza, ma tendono sempre più a sotto- stimare le probabilità delle sequenze che non occorrono vicine nel training corpus. Per ovviare a questo inconveniente sono materie di ricerche diverse tecniche, dette di smoothing, volte a garantire l’affidabilità delle frequenze degli n-gram che altrimenti avrebbero probabilità nulle. Un semplice esempio per un sistema che si affida a trigram potrebbe essere il valutare la probabilità di una parola come la somma pesata delle probabilità che ha quella parola di apparire in trigram, bigram e unigram.

2.3.3 Modelli di Markov

La modellazione stocastica del linguaggio naturale, indotta dallo Speech Recognition, utilizza vari strumenti di diverse tipologie, ma nel nostro caso ci soffermeremo sui modelli markoviani.

I modelli di Markov sono processi stocastici, detti senza memoria, particolarmente utili per risolvere problemi di classificazione che hanno una rappresentazione a sequenza di stati. Risulta spesso efficace considerare una sequenza di variabili aleatorie che non sono indipendenti, ma frequentemente accade che il valore di ogni variabile dipenda dagli elementi precedenti nella serie.

Formalizzando il tutto, supponiamo

X = (X1, . . . , XT)

(21)

come una successione di varibili aleatorie i cui valori appartengono ad un insieme finito

S = {s₁, . . . , sN}

(detto spazio degli stati ). Le due propriet`a che caratterizzano i modelli di Markovsono le seguenti:

P(Xt+1= sk| X₁, . . . , Xt) = P(Xt+1= sk| Xt) (2.14) P(Xt+1= sk| Xt) = P(X2= sk| X1) (2.15)

La proprietà (2.14), detta Orizzonte Limitato (o Limited Horizon), indica che la transizione dipende esclusivamente dallo stato attuale, mentre la (2.15), detta Stazionarietà (o Time invariant), suggerisce che la dipendenza non varia nel tempo e non dipende dal numero di transizioni. Se X soddisfa entrambe le suddette proprietà, allora viene chiamata Catena di Markov (oppure, in alternativa, modello o processo di Markov ).

In questa descrizione generale, appare evidente che un modello n-gram sia una catena di Markov. I processi markoviani possono essere usati quando si vuole modellare la probabilità di una sequenza lineare di eventi. Alterna- tivamente, possiamo rappresentare una catena di Markov come un insieme di stati connessi tra loro attraverso un insieme di probabilità di transizione che indicano le probabilità di passare da uno stato ad un altro.

In Figura 2.2 notiamo che gli stati sono indicati con un cerchio intorno

(22)

Figura 2.2: Un modello di Markov.

al nome dello stato stesso, mentre le frecce rappresentano le connessioni con le relative probabilità. La somma delle probabilità degli archi uscenti è sempre 1. Data l’analogia delle catene di Markov con i modelli n-gram, la probabilità di una sequenza di stati X1, . . . , XT è facilmente calcolata:

P(X1, . . . , XT) = P(X1) P(X2|X₁) P(X3|X₂, X₁) . . . P(XT|X₁, . . . , X_{T −1}) (2.16) L’equazione (2.16) pu`o essere meglio valutata sfruttando le propriet`a di Markov (2.14) e (2.15):

P(X1, . . . , X_T) = P(X1) P(X2|X₁) P(X3|X₂) . . . P(XT|X_{T −1}) (2.17)

(23)

Cos`ı, nel caso dell’esempio in Figura 2.2 avremo che la probabilit`a di avere la parola “tip” risulti essere la seguente:

P(t, i, p) = P(X1= t, X₂ = i, X₃= p) =

= P(X1= t) P(X2= i |X1= t) P(X3= p |X2 = i) =

= 1.0 × 0.3 × 0.6 = 0.18

2.3.4 Hidden Markov Models

Come si è visto, un processo di Markov è un automa a stati finiti (non- deterministico) in cui le transizioni sono etichettate da una misura di pro- babilità. In un modello di questo tipo è sempre osservabile la sequenza degli stati che vengono attraversati. Cos`ı non è per gli Hidden Markov Mo- dels (HMM o modelli di Markov nascosti) dove l’esatta successione degli stati attraversati è sconosciuta (hidden, nascosta).

I modelli di Markov nascosti cui faremo riferimento sono un’estensione delle catene di Markov viste precedentemente. Appare chiaro che se gli stati sono in numero finito, un modello markoviano può essere rappresentato attraverso un grafo (automa). In un tale modello c’è una corrispondenza tra i simboli emessi dall’automa e gli stati corrispondenti. In un HMM non è più cos`ı: è osservabile soltanto la sequenza di simboli in base alla quale è possibile inferire la probabilità degli stati corrispondenti.

Un HMM `e definito da:

(24)

• un insieme finito S = {s₁, . . . , s_N} detto spazio degli stati che denota i valori che possono essere assunti dalle variabili aleatorie del modello;

• una distribuzione di probabilit`a A : S × S → [0, 1] che specifica, per ogni k, l ∈ S, la probabilit`a di passare dallo stato k allo stato l;

• un insieme Σ di simboli osservabili;

• una distribuzione di probabilit`a B : S × Σ → [0, 1] che indica, per ogni b ∈ Σ e per ogni k ∈ S, la probabilit`a di osservare l’emissione del simbolo b quando il modello si trova nello stato k.

Come vedremo nelle sezioni successive, un POS tagger basato su HMM

`e definito da un insieme di tag (S), un insieme di token in input (Σ) e due funzioni di probabilit`a (A e B) stimate a partire da un training corpus precedentemente classificato.

Gli Hidden Markov Model sono stati il principale strumento per la modellazione statistica nei moderni sistemi di riconoscimento vocale. Nonostante le loro limitazioni, sono state studiate e adottate una larga serie di varianti che sono state sfruttate con successo in molte applicazioni.

Un HMM è un caso particolare di un processo markoviano e inoltre esso opera ad un livello di astrazione maggiore dei consueti modelli. Per questo si è in grado di osservare le categorie delle parole. L’applicazione maggiore degli HMM è rivolta al Part-of-Speech tagging.

(25)

2.4 Part-of-Speech Tagging

Per riuscire a fare predizione non `e sufficiente avere un vocabolario ricco, delle frequenze associate ai termini e i caratteri iniziali della parola stessa;

è necessario riuscire a interpretare il contesto in cui appare la parola desi- derata. Scopo della predizione è riuscire a capire quale parola può essere la successiva di una certa sequenza. In altri termini, un word predictor vuole stimare la probabilità che ha una parola di comparire dopo una catena di altri termini, ovvero

P(wi|w₁, w₂, . . . , w_i−1) (2.18)

Poiché il numero delle parole che compongono il contesto, w1, . . . , wi−1, cresce esponenzialmente con i, molte sequenze potranno non occorrere mai mentre alcune saranno rare. Di conseguenza l’ampiezza e la scarsità (“sparseness”) del contesto rendono praticamente impossibile riuscire ad estrarre le probabilità date da (2.18), anche nel caso di un linguaggio con un numero contenuto di vocaboli.

La soluzione a questo problema sta nel riuscire a trattare il contesto in modo da avere un numero accettabile di classi di equivalenza; in questo modo possiamo approssimare (2.18) in

P(wi|ϕ[w₁, . . . , w_i−1]) (2.19)

dove ϕ rappresenta un’opportuna trasformazione di w1, . . . , wi−1.

(26)

Il metodo pi`u diffuso per ottenere la trasformazione ϕ fa uso di gram- matiche basate su classificazioni di tipo Part-of-Speech.

Il processo di assegnamento di un’etichetta (o tag) a tutte le parole presenti in un testo, `e chiamato “tagging” (dall’inglese etichettare, classificare), mentre un’applicazione che esegue tale compito `e detto “tagger ”.

2.4.1 Introduzione al Part-of-Speech Tagging

Come gi`a spiegato, i corpora rappresentano la base di molti sistemi di NLP.

Queste raccolte di testi, selezionati spesso con intenti precisi, sono organizzati secondo criteri specifici. Un corpus deve essere, in genere, accessibile ed ordinabile secondo diversi valori chiave e deve includere alcune catego- rizzazioni linguistiche. Il tipo di classificazione più semplice è il Part-of- Speech(POS, “parte del discorso”) tagging, che consiste nell’associare ad ogni parola del corpus una particolare etichetta (tag). Tipicamente questi tag indicano la categoria sintattica, come sostantivo o verbo, mentre occa- sionalmente includono informazioni addizionali, come numero (singolare o plurale) o tempo del verbo. Il POS tagging può essere ottenuto per codifica manuale o per lemmatizzazione (semi)automatica, confrontando le parole con un dizionario.

Lo scopo del POS tagging è di associare ciascun token (ovvero un’unità lessicale) ad una categoria sintattica o parte del discorso. Questo lavoro aggiunge valore al corpus e viene svolto poiché risulta particolarmente utile

(27)

alle ricerche linguistiche, all’estrazione di collocazioni, ai modelli predittivi e di speech recognition. Inoltre il tagging rappresenta il punto di partenza per molte applicazioni linguistiche pi`u complesse come il parsing, l’information extracting, la traduzione automatica e molte altre.

Per etichettare ogni parola del corpus con la propria parte del discorso, abbiamo bisogno di un analizzatore lessicale o morfologico capace di fornire tutti i possibili tag per una parola. I POS tagger, successivamente, esamineranno tutte le interpretazioni morfosintattiche di quel termine ed assegneranno la forma corretta in base al contesto.

Nell’ambito della predizione, il POS tagging `e adottato in modo da riuscire ad analizzare ogni parola in una frase per descrivere come essa `e usata al suo interno. Attraverso accurati metodi statistici, che vedremo in seguito,

`e possibile catturare una certa regolarit`a nell’occorrenza dei tag: pertanto siamo in grado, con l’ausilio di strumenti specifici, di realizzare un sistema di predizione basato anche sulla categoria lessicale.

Poich´e il POS tagging rappresenta una materia di grande interesse nel campo del NLP, la ricerca ha cercato di migliorare la precisione del tagging utilizzando diversi modelli e metodi:

• Hidden Markov Models (HMM );

• Sistemi a regole (rule-based systems);

• Alberi decisionali (decision-tree systems);

(28)

• Sistemi ad entropia (maximum-entropy systems);

• Reti neurali (neural network systems).

Mentre vedremo i tagger basati su modelli markoviani, non scenderemo nella descrizione delle altre tecniche di tagging che vanno oltre lo scopo di questa tesi.

2.4.2 Classificazione dei Part-of-Speech Tagger

In questa sezione diamo visione di una classificazione dei tagger, come esposto in [25]. Esistono diversi approcci al POS tagging automatizzato: in Figura 2.3 si è cercato di esprimere una descrizione dello stato dell’arte delle tecniche di tagging esistenti. In realtà lo schema sarebbe più complicato poiché molti sistemi adottano aspetti di alcuni o di tutti gli approcci.

POS Tagging

Supervised Unsupervised

rule-based stochastic neural rule-based stochastic neural

maximum likelihood

Hidden Markov

n-grams

Viterbi

Algorithm Baum - Welch

Figura 2.3: Schema di Classificazione dei POS Tagger.

(29)

Sistemi “Supervised ” e Sistemi “Unsupervided ”

E possibile fare una prima distinzione tra i POS tagger in termini del grado` di automazione del processo di training (addestramento) e di annotazione.

Per questa distinzione vengono comunemente applicati i termini di “supervised tagging” (tagging supervisionato) e “unsupervised tagging” (tagging non supervisionato).

I sistemi del primo tipo fanno affidamento tipicamente a corpora lem- matizzati che servono da base per la generazione di qualsiasi strumento da usare durante tutto il processo di tagging. I modelli unsupervised, invece, non richiedono un corpus pre-taggato, ma utilizzano sofisticati metodi com- putazionali per indurre automaticamente i raggruppamenti delle parole (ad esempio gli insiemi di tag) e si basano successivamente su questi gruppi sia per calcolare le informazioni probabilistiche necessarie ai tagger stocastici, che per dedurre le regole di contesto di cui hanno bisogno i sistemi di tipo rule-based.

Il POS tagging con il metodo supervised, invece di formulare delle regole, si basa su una classificazione manuale di una modesta quantit`a di dati cos`ı da addestrare in modo automatico un programma che estrae generalizzazioni da questi dati. In seguito, questo strumento “addestrato” `e utilizzato per annotare nuovi dati. In altre parole, tutti i tagger basati sul paradig- ma supervisionato estraggono statistiche sull’occorrenza di certi pattern nel training corpus, e poi usano tali statistiche per effettuare il tagging di nuovi

(30)

dati. Fanno parte di questa tipologia di applicazione i tagger markoviani (visti nella Sezione 2.3.3).

L’approccio di apprendimento supervisionato `e molto comune nel campo della linguistica computazionale. Alcuni esperimenti hanno mostrato che con questo approccio vengono raggiunti risultati superiori sebbene esso utilizzi una quantit`a limitata di dati di addestramento.

Sistemi a Regole

Gli approcci al tagging di tipo rule-based si servono delle informazioni contestuali per assegnare un tag a parole sconosciute o ambigue. Queste regole vengono spesso citate come “context frame rules” (regole di contesto). Un esempio di regola di questo genere, valido soprattutto per la lingua inglese,

è il seguente: se una parola ambigua W è preceduta da un articolo determinativo (Det) ed è seguita da un sostantivo (Noun), il suo tag sarà aggettivo (Adj). La relativa context rule è esprimibile come segue:

Det − W − N oun ⇒ W/Adj

Oltre a conoscenze contestuali, molti tagger fanno uso di informazioni morfologiche per assistere il processo di disambiguazione. Una tale regola, sempre per la lingua inglese, può essere: se una parola termina in -ing ed è preceduta da un verbo, la sua categoria è verbo.

Alcuni sistemi utilizzano, in aggiunta, propriet`a ricavabili dall’osserva-

(31)

zione di altri fattori legati prettamente alla lingua presa in considerazio- ne. Un fattore pu`o essere la punteggiatura o l’uso delle maiuscole: si pensi a quanto questi elementi siano estremamente determinanti nella lingua tedesca.

Tagging Stocastico

Con il termine “tagging stocastico” si può far riferimento ad un numero sostanzioso di approcci differenti al problema del POS tagging. Il tagger stocastico più semplice esegue la disambiguazione delle parole basandosi unicamente sulla probabilità che un termine occorra con un particolare tag.

Per dirla altrimenti, il tag incontrato più frequentemente nel training set (insieme dei testi per l’addestramento) sarà quello che verrà assegnato a tutte le istanze ambigue di quella parola. Un’alternativa all’approccio basato sulla frequenza è calcolare la probabilità di una certa sequenza di tag. Questo metodo, conosciuto come n-gram (si veda la Sezione 2.3), si affida al fatto che il miglior tag per una specifica parola è determinato dalla probabilità che esso occorra con gli n tag precedenti. L’algoritmo più conosciuto per implementare un n-gram è l’Algoritmo di Viterbi (Sezione 2.4.5), un metodo di analisi che annulla l’espansione polinomiale di una ricerca in ampiezza (breadth first) attraverso un ordinamento dell’albero di ricerca ad ogni livello usando il miglior valore di n con la stima di massima verosimiglianza (dove n rappresenta il numero dei possibili tag per la parola successiva).

(32)

L’ulteriore livello di complessità che può essere introdotto in un tagger stocastico unisce i due approcci precedenti, servendosi sia di sequenze di tag che di misure di frequenza di singole parole. Questo metodo è conosciuto come Hidden Markov Model (HMM). Gli HMM possono essere implementati attraverso l’algoritmo di Viterbi ed è il metodo di tagging più efficiente tra quelli citati. Questi modelli non possono essere usati in schemi di tagging automatico poiché essi dipendono da statistiche sulle sequenze prodotte.

L’incapacità di addestrare gli HMM in modo meccanico, è risolta servendosi dell’algoritmo di Baum-Welch (altrimenti noto come l’algoritmo Forward- Backward). Questo algoritmo usa informazioni sulla parola, piuttosto che sul tag, per derivare iterativamente delle sequenze per migliorare la probabilità di dati di addestramento.

2.4.3 Part-of-Speech Tagging con Metodi Statistici

Al fine di generalizzare i modelli basati su n-gram, alcuni sistemi impiegano n-gram di part-of-speech al posto di catene di parole. In questo modo viene calcolata la probabilità del tag corrente in funzione dei tag precedenti (o solamente del tag precedente) evidenziando una loro dipendenza. Il maggior vantaggio che si riesce ad ottenere con questo metodo è dovuto al fatto che la part-of-speech riesce a catturare tutta una serie di differenti forme in una singola rappresentazione in modo da poter considerare i legami contestuali con un insieme minore di n-gram. Pertanto vi è la possibilità di considerare

(33)

un contesto pi`u rilevante e dunque pi`u significativo.

Per contro c’è una perdita di semantica: infatti un tag preciserà soltanto la categoria sintattica di appartenenza, ma non la parola precisa. Ad esempio, nel processo di predizione verrà indicato che dopo un sostantivo è più probabile trovare un verbo, ma il tag (che varrà verbo) non ci informerà su quale verbo in particolare è tipicamente connesso a quel sostantivo.

Un altro svantaggio è legato all’incontro di nuove parole (quelle, cioè, non presenti nel vocabolario) per le quali è necessario l’inserimento nel lessico anche se non è conosciuta la categoria sintattica. Un modo per risolvere la questione potrà essere l’interpretazione dei prefissi e dei suffissi delle nuove parole al fine di trovare la part-of-speech più probabile. In materia, sono all’attivo molte ricerche scientifiche.

2.4.4 Markov Model Taggers

I tagger markoviani sono modelli tanto semplici quanto intuitivi e sono molto diffusi. In essi, le sequenze di tag vengono considerate come catene di Markov e quindi trattate come abbiamo visto nella Sezione 2.3.3. Richiamiamo le propriet`a viste in (2.14) e in (2.15): nel seguito faremo uso delle notazioni proposte in [1] e riportate nella Tabella 2.4.

• Orizzonte limitato:

P(Xi+1= t^j| X₁, . . . , Xi) = P(Xi+1= t^j| Xi) (2.20)

(34)

• Stazionariet`a :

P(Xi+1= t^j| Xi) = P(X2= t^j| X1) (2.21)

wi la parola alla posizione i nel corpus ti il tag relativo a wi

w_{i, k} le parole che occorrono tra la posizione i e k (wi, . . . , w_k) ti, k i tag ti, . . . , tk di wi, . . . , wk

w^l la l -esima parola nel lessico t^j il j -esimo tag nel tag set

C(w^l) il numero di occorrenze di w^l nel training set C(t^j) il numero di occorrenze di t^j nel training set C(t^j, t^k) il numero di occorrenze di t^j seguite da t^k C(w^l, t^j) il numero di occorrenze di w^l classificata come t^j

Tabella 2.4: Notazione.

Le proprietà (2.20) e (2.21) esprimono la caratteristica che il tag di una parola dipende esclusivamente dal tag precedente (Orizzonte limitato) e che questa dipendenza non cambia nel tempo (Stazionarietà). Ad esempio, se un verbo nella forma all’infinito ha probabilità 0.2 di occorrere dopo una preposizione all’inizio di una frase, questa probabilità non cambierà a seconda di come classificheremo il resto della frase (o come annoteremo nuove frasi).

(35)

Per esprimere i seguenti concetti, utilizziamo la notazione vista nella Tabella 2.4. Le indicazioni in pedice sono usate per riferire parole e tag in particolari posizioni della frase e del corpus, mentre quelle in apice fanno riferimento a tipi di parole nel lessico e a tipi di tag nel tagset. In questo genere di notazione possiamo rappresentare la propriet`a (2.20) come:

P(ti+1| t_{1, i}) = P(ti+1| ti)

Attraverso l’ausilio di un testo etichettato (prendiamo in prestito il termine “taggato” derivante dal verbo inglese to tag: etichettare, classificare) manualmente come training set, è possibile addestrare il tagger in modo da far apprendere le regolarità delle sequenze di tag. La stima di massima verosimiglianza (o Maximum Likelihood Estimate, MLE) di un tag t^j seguito dal tag t^k, è misurata come la frequenza relativa di un certo tag seguito da tag differenti:

P(t^k| t^j) = C(t^j, t^k)

C(t^j) (2.22)

questo valore `e spesso chiamato “probabilit`a contestuale”.

Riassumendo, si pensi a come eseguire, per esempio, il tagging della frase

“a new play” (“un nuovo gioco”), ci aspettiamo di trovare, per la parola

“play”, che P(Noun | Adj) P(V erb | Adj). Infatti nel Brown Corpus si osserva che P(Noun | Adj) ≈ 0.45 e P(V erb | Adj) ≈ 0.0005.

(36)

Con la stima di P(ti+1| ti) possiamo calcolare la probabilità di una particolare sequenza di tag. In pratica vogliamo trovare la successione di tag più probabile per una catena di parole. Inoltre siamo capaci di stimare di- rettamente, via MLE, la probabilità che una parola venga emessa con un particolare tag, ovvero:

P(w^l| t^j) = C(w^l, t^j)

C(t^j) (2.23)

tale misura `e citata come “probabilit`a locale”.

Siamo in grado adesso di trovare la miglior sequenza di tag t₁, . . . , tn

(t_{1, n}) per una frase w₁, . . . , w_n (w_{1, n}) espressa come

arg max

t1, n P(t1, n| w1, n) (2.24)

Applicando la regola di Bayes, l’equazione (2.24) pu`o essere vista come

arg max

t1, n

P(t1, n| w_{1, n}) = arg max

t1, n

P(w1, n| t1, n) P(t1, n) P(w1, n) =

= arg max

t1, n P(w1, n| t_{1, n}) P(t1, n) (2.25)

Con queste premesse, riduciamo l’espressione (2.25) ai parametri che conosciamo e che sappiamo stimare mediante l’analisi del training corpus.

In aggiunta alla propriet`a (2.20), possiamo assumere che:

• le parole sono reciprocamente indipendenti, (2.26)

(37)

• l’identit`a di una parola dipende unicamente dal proprio tag, (2.27)

P(w1, n|t_{1, n}) P(t1, n) = Yn i=1

P(wi| t_{1, n}) (2.26)

× P(tn| t_{1, n−1}) × P(tn−1| t_{1, n−2}) × . . . × P(t2| t₁) =

= Yn i=1

P(wi| ti) (2.27)

× P(tn| tn−1) × P(tn−1| tn−2) × . . . × P(t2| t1) =

= Yn i=1

[P(wi| ti) × P(ti| ti−1)] (2.28)

(Per semplificare definiamo P(t1| t0) = 1.0).

Dunque, l’equazione finale per la determinazione della sequenza di tag ˆt che meglio approssima una frase `e cos`ı ottenuta:

ˆt_{1, n}= arg max

t¹, n P(t1, n| w_{1, n}) = Yn i=1

P(wi| ti) P(ti| t_i−1) (2.29)

L’algoritmo in Figura 2.4 mostra come `e possibile addestrare un tagger basato su un modello di Markov [1]. Ricordiamo che i valori ricavati con la tecnica di MLE, necessitano di smoothing a causa del fenomeno del “data sparseness”. A tal proposito, in molte implementazioni viene usato un metodo di smoothing per stimare P(t^k, t^j) e P(w^l, t^j).

Nella sezione seguente viene descritto come effettuare il tagging con un tagger gi`a addestrato.