19 ottobre 2016

Linguistica Computazionale

2

Probabilità e linguaggio l  Per stimare queste probabilità “linguistiche” devo integrare

informazioni sul modo in cui si distribuiscono le strutture del linguaggio l  decidere come segmentare una sequenza di suoni in parole

discrete l  lamacchinaeraparcheggiatadavantiallaporta

§  lamac non è un probabile confine di parola, perché ci sono poche parole che finiscono per consonante, ecc.

l  decidere la categoria di morfosintattica di una parola l  la macchina la aspettava davanti alla porta

§  se la ricorre davanti a un nome è probabile che sia un articolo (perché di solito gli articoli precedono i nomi)

§  se la ricorre davanti a un verbo è probabile che sia un pronome clitico, ecc. l  decidere come tradurre un’espressione linguistica

l  L’aquila ha perso una penna volando §  dal momento che l’aquila è un uccello, è molto probabile che penna vada

tradotto con feather (perché di solito gli uccelli hanno le penne/feather), ecc.

Linguaggio e probabilità

“The key characteristic of language used by the learners in the construction of their individual armamentaria is revealed at every level one cares to consider. It is non-randomness, or DEPARTURE FROM EQUIPROBABILITY, in the distribution of symbols and symbol sequences (Harris, 1991, p:32)” S. Edelman (2008), Computing the Mind: 247

4

Modelli statistici del linguaggio l  Un modello statistico (probabilistico) di un evento è un

modello matematico che determina la probabilità del verificarsi di quell’evento

l  Le statistiche estratte da un campione di dati su eventi noti vengono usate per stimare la probabilità del loro verificarsi e predire così nuovi eventi

l  Un corpus di testi è usato per calcolare statistiche sulle distribuzioni delle strutture linguistiche (es. parole) e costruire un modello che assegna una probabilità a eventi linguistici l  es. l’evento che la sia un articolo, che Il cane rincorre il

gatto sia una frase grammaticale dell’italiano, ecc.

5

Modelli statistici definizione della struttura del modello probabilistico

stima dei parametri del modello (stima delle probabilità)

training corpus

modello probabilistico

valutazione della capacità predittiva del modello

test corpus

6

A Statistical NLP approach seeks to solve these problems by automatically learning lexical and structural preferences from corpora

Manning & Schütze (1999: 19)

Modelli statistici del linguaggio

l  Modelli statistici per NLP l  maggiore robustezza

l  “graceful degradation” in caso di errore l  capacità di generalizzazione l  approccio induttivo ed empirico

l  i parametri dei modelli vengono automaticamente stimati a partire da corpora di addestramento §  velocità di sviluppo §  interessanti dal punto di vista cognitivo come modelli

dell’acquisiione del linguaggio

7

Che cosa è la probabilità? l  Eventi aleatori

l  eventi incerti, che possono verificarsi oppure no l  l’evento di tirare un dado e ottenere 6 l  l’evento che domani piova l  l’evento che venga estratto il numero 15 al lotto l  l’evento che estraendo una parola a caso da un testo ottenga la

parola “uomo” l  Probabilità

l  un numero che attribuiamo ad un evento per quantificare il suo grado di incertezza l  quanto è probabile che domani piova? l  quanto è probabile che tirando un dado ottenga il numero 6?

l  le probabilità ci permettono di prendere decisioni in caso di incertezza, per prevedere la possibilità del verificarsi di un evento aleatorio

8

La definizione di probabilità l  Esperimento

l  il processo attraverso cui viene compiuta una certa osservazione l  lanciare un dado e vedere l’esito che produce (il numero ottenuto)

l  un esperimento aleatorio è un esperimento il cui esito non può essere previsto con certezza prima che venga eseguito

l  la teoria della probabilità si occupa di assegnare una probabilità al verificarsi di un evento sulla base di una serie di esperimenti (osservazioni) ripetuti

l  Esperimento composto l  un insieme di n repliche di un esperimento (nelle stesse condizioni)

l  n lanci successivi di un dado l  n successive osservazioni scientifiche dello stesso fenomeno

l  Spazio campione (Ω) l  l’insieme degli esiti (risultati) possibili di un esperimento

l  ciascun esito si chiama punto campione l  esperimento: lancio di un dado

§  Ωd = {1, 2, 3, 4, 5, 6} l  esperimento: lancio di una moneta

§  Ωm = {testa, croce}

9

La definizione di probabilità l  Evento

l  un sottoinsieme A dello spazio campione Ω, i cui elementi si dicono i risultati favorevoli all’evento A l  l’insieme di tutti i possibili eventi di Ω si chiama spazio degli eventi (E) l  i punti campione sono gli eventi elementari l  un evento formato da più di un punto campione si dice evento complesso

l  Esperimento: lancio di un dado l  Ωd = {1, 2, 3, 4, 5, 6}

l  evento A = {ottenere un numero pari} evento complesso §  A = {2, 4, 6}

l  evento B = {ottenere un 6} evento elementare §  B = {6}

l  evento C = {ottenere un numero compreso tra 1 e 6} §  C = {1, 2, 3, 4, 5, 6} = Ωd

§  un evento equivalente allo spazio campionario si dice evento certo l  evento D = {ottenere un numero maggiore di 6}

§  D = { } = ∅ §  un evento equivalente all’insieme vuoto (∅) si dice evento impossibile

10

Ω=A

AP )(

La definizione di probabilità l  Dato uno spazio campione Ω, una funzione di probabilità P

(distribuzione di probabilità) assegna a ogni evento di Ω un numero reale compreso tra 0 e 1 (P: E à [0, 1]) l  una funzione di probabilità definisce uno spazio probabilistico per Ω

l  Definizione classica di probabilità (a priori) l  dato un esperimento in cui Ω è finito e tutti i punti campione sono

egualmente verosimili e mutuamente esclusivi, per ogni evento A:

11

Probabilità classica l  Esperimento: lancio di un dado (non truccato)

l  Ωd = {1, 2, 3, 4, 5, 6} |Ωd| = 6 l  A = {ottenere un 6}

§  A = {6} |A| = 1 §  P(A) = |A|/|Ωd| = 1/6 = 0,16666666666666

l  B = {ottenere un numero pari} §  B = {2, 4, 6} |B| = 3 §  P(B) = |B|/|Ωd| = 3/6 = 1/2 = 0,5

l  C = {ottenere un numero compreso tra 1 e 6} §  C = {1, 2, 3, 4, 5, 6} |C| = 6 §  P(C) = |C|/|Ωd| = 6/6 = 1 (evento certo, |C| = |Ω|)

l  D = {ottenere un numero maggiore di 6} §  D = { } |D| = 0 §  P(D) = |C|/|Ωd| = 0/6 = 0 (evento impossibile)

l  La definizione classica non è appropriata se Ω è infinito o i vari esiti non sono egualmente verosimili

12

nfAP A

n ∞→= lim)(

l  Esperimento: lancio di un dado (truccato) l  A = {ottenere un numero pari} l  fA = numero di volte in cui è stato ottenuto 2, 4 o 6 come esito del lancio l  n = numero di lanci

§  al crescere di n, P(A) ≈ fA/n

Frequenza e probabilità l  Legge dei Grandi Numeri

l  la frequenza relativa di un evento converge verso la sua vera probabilità con l’aumentare del numero degli esperimenti

l  Definizione frequentista di probabilità (empirica o a posteriori) l  la probabilità di un evento è interpretata come la sua frequenza relativa in

una serie di repliche dello stesso esperimento (esperimento composto) l  sia n il numero di volte in cui un esperimento viene ripetuto, e fA il numero

di volte in cui si osserva l’evento A nell’esperimento:

13 ||

)(CfvP v≈

Probabilità di una parola definizione frequentista l  Esperimento aleatorio

l  selezionare una parola a caso da un testo l  qual è la probabilità di selezionare una parola v?

l  Stimiamo la probabilità di v a partire da un corpus C l  usiamo il corpus come oggetto di un esperimento composto di n

selezioni successive di parole l  numero di esperimenti n = |C|

l  per ogni token t del corpus, si verifica se t è di tipo v oppure no l  = calcoliamo la frequenza di v

l  La frequenza relativa di una parola v in C permette di stimare la sua probabilità (ovvero la probabilità che venga estratta):

14 ||

)(CfvP v≈

Probabilità di una parola definizione frequentista l  Esperimento aleatorio

l  selezionare una parola a caso da un testo l  qual è la probabilità di selezionare una parola v?

l  Stimiamo la probabilità di v a partire da un corpus C l  usiamo il corpus come oggetto di un esperimento composto di n

selezioni successive di parole l  numero di esperimenti n = |C|

l  per ogni token t del corpus, si verifica se t è di tipo v oppure no l  = calcoliamo la frequenza di v

l  La frequenza relativa di una parola v in C permette di stimare la sua probabilità (ovvero la probabilità che venga estratta):

Data sparseness e stima frequentista della probabilità

l  La stima frequentista della probabilità viene anche chiamata Maximum Likelihood Estimation dei parametri di un modello probabilistico l  se la frequenza relativa di una parola in un corpus è 0.8,

la probabilità della parola nel linguaggio è 0.8

l  La MLE è la funzione di assegnazione di probabilità che assegna la probabilità più alta agli eventi osservati nel training corpus

15

Data sparseness e stima frequentista della probabilità l  Data sparseness

l  i dati estratti da un corpus non sono sufficienti per creare modelli probabilistici accurati del linguaggio

l  Ci sono molte parole rare per le quali la frequenza relativa non fornisce una stima di probabilità affidabile

l  Poiché un corpus (comunque grande) non esaurisce mai tutto il vocabolario, MLE sovrastima la probabilità delle parole nel corpus, senza lasciare nessuna porzione di probabilità alle parole non viste l  l’intera massa di probabilità viene ripartita tra tutte le parole tipo del

corpus l  se una parola tipo vi non appartiene al corpus, p(vi) = 0

l  Smoothing l  metodi matematici attraverso i quali vengono ridotte le probabilità

degli eventi più frequenti, per riservare porzioni della massa di probabilità a eventi rari e a possibili eventi non visti corpus

16

Smoothing

l  Add one smoothing (Legge di Laplace)

l  Esempio l  |C| = 50 l  |V| = 20 l  il = 15 l  cane = 3 l  morde = 1

ps (w) =f (w)+1|C |+ |V |

pMLE(il) = 15/50 = 0.3

pMLE(cane) = 3/50 = 0.06

pMLE(morde) = 1/50 = 0.02

ps(il) = (15+1)/(50+20) = 0.22

Ps(cane) = (3+1)/(50+20) = 0.057

Ps(morde) = (1+1)/(50+20) = 0.028

unsmoothed

smoothed

18

P(nome ∪ aggettivo) = fnome+aggettivo/|C| = 15/38 = 0,394 P(nome ∪ aggettivo) = P(nome) + P(aggettivo) = 10/38 + 5/38 = 15/38 = 0,394

probabilità dell’unione di eventi = somma di probabilità

Regola della somma generalizzata (per eventi mutuamente esclusivi)

∑=

=∪∪∪n

iin APAAAP

121 )()( …

Probabilità dell’unione di eventi

l  Qual è la probabilità di selezionare un nome o un aggettivo? l  fnome = 10 faggettivo = 5 fnome+aggettivo = 15

19

Assiomi della probabilità l  Ogni funzione di probabilità P per essere tale deve soddisfare i

seguenti assiomi: l  P(A)≥0, per ogni A (positività)

l  la probabilità è sempre un numero positivo

l  P(A∪B) = P(A) + P(B), se A∩B=∅ (Regola della somma o unione)

l  P(Ω) = 1 (Certezza)

l  Gli assiomi stabiliscono soltanto i vincoli che una misura di probabilità deve rispettare, ma non dicono come misurare la probabilità di un evento elementare l  sia la definizione classica di probabilità che quella frequentista

deve rispettare gli assiomi della probabilità

20

1)( 21 ==+++=ΩCC

Cf

Cf

Cf

P nvvv …

Sommare probabilità l  Dalla regola della somma segue anche il postulato

della certezza: l  Esperimento: selezione di una parola da un corpus

l  Ω = {v1, v2, …, vn} §  le parole tipo del corpus

l  P(Ω) = P({v1}∪{v2} ∪ …∪{vn}) §  le parole tipo rappresentano tutti eventi elementari mutuamente

disgiunti l  P(Ω) = P({v1})+P({v2}+…+P({vn})

§  per la regola della somma

21

probabilità di eventi congiunti = prodotto di probabilità

Probabilità congiunte

l  P(A∩B) oppure P(A,B) l  probabilità del verificarsi congiunto di due eventi A e B

l  esperimento: lancio di due dadi §  probabilità di ottenere 6 in tutti e due dadi

l  esperimento: estrazione di una carta da un mazzo §  probabilità di estrarre una regina nera

§  A = { estrarre una regina} B = {estrarre una carta nera} l  esperimento: estrazione di due parole da un testo

§  probabilità di ottenere un verbo e un aggettivo insieme

l  Il calcolo del prodotto delle probabilità dipende dalla relazione tra i due eventi l  eventi indipendenti

l  il verificarsi dell’uno non condiziona il verificarsi dell’altro l  eventi dipendenti

l  il verificarsi dell’uno condiziona il verificarsi dell’altro

22

)()()( BPAPBAP ∗=∩

Probabilità congiunte eventi indipendenti l  Due eventi A e B sono indipendenti se e solo se il verificarsi di

A non ha nessun effetto sulla probabilità per B di verificarsi, e viceversa l  esperimento: lancio di due dadi l  Qual è la probabilità di ottenere in un lancio 6 in entrambi i dadi?

l  evento A = {1o dado = 6} P(A) = 1/6 l  evento B = {2o dado = 6} P(B) = 1/6 l  la probabilità che lanciando i due dadi ottenga 6 in entrambi i casi

è dunque uguale a 1/6 di 1/6, ovvero 1/36 §  P(A,B) = 1/36 = 1/6 * 1/6 = P(A) * P(B)

l  Se due eventi A e B sono indipendenti, in generale vale che:

23 v1, v2

Probabilità congiunte eventi indipendenti l  Esperimento

l  estrarre due parole v1 e v2 a caso da un testo l  Qual è la probabilità che estragga insieme un nome e un articolo?

l  |C| = 50 fN = 10 fArt = 15 l  P(N, Art) = P(N) * P(Art) = fN/|C| * fArt/|C| l  P(N, Art) = 10/50 * 15/50 = 0,2 * 0,3 = 0,06

l  ATTENZIONE !!! questo funziona solo assumendo che la probabilità di estrarre un nome sia indipendente dalla probabilità di estrarre un articolo l  modello dell’urna

l  consideriamo il testo come un insieme di parole indipendenti l’una dall’altra (= il ricorrere dell’una in un corpus non dipende dalla presenza di un’altra parola). Tutti i tokens vengono vengono messi in un’urna, da cui si compiono le estrazioni