Linguistica computazionale - parte 2

Linguistica computazionale – Parte 2

Teoria dell'informazione di Shannon

L'entropia è sempre un numero ≥ 0. L'entropia (H) è una misura del grado di incertezza di un sistema, ovvero misura quanto è difficile prevedere quale è l'esito di un fenomeno probabilistico. Dal greco en (dentro) e trope (rivolgimento, mutazione).

Maggiore incertezza = maggiore informatività data dal verificarsi degli eventi = maggiore entropia.

Minore incertezza = minore informatività = minore entropia. Più è incerto il sistema, maggiore è l'incertezza con cui abbiamo a che fare (maggiore è l'entropia di quel sistema).

Dipendenze del grado di incertezza

• Numero di esiti alternativi possibili
• Distribuzione delle probabilità per ciascun esito: probabilità uniforme genera maggior incertezza di una probabilità non uniforme

L'informazione è la diminuzione dell'incertezza. Alcuni eventi sono più informativi di altri: meno scontato è il messaggio dato dal verificarsi di un certo evento, maggiore è il suo grado di informatività. Dato un singolo evento, più l'evento è raro (non mi aspetto che accada), maggiore è l'informazione che otteniamo sapendo che si è verificato: il verificarsi di un evento raro ci sorprende di più del verificarsi di un evento scontato che ci aspettiamo accada. Concetto di sorpresa: “l’uomo ha morso un cane” fa notizia perché è un evento raro che non ci aspettavamo, “il cane ha morso un uomo” no.

L'entropia è la misura della quantità di informazione portata dagli eventi prodotti da un determinato sistema aleatorio (formalizzato come una variabile casuale). NB è importante distinguere tra sistema probabilistico e singoli eventi prodotti da tale sistema.

Variabile casuale

Una variabile casuale (random variable) è una variabile (aleatoria) ai cui valori è associata una distribuzione di probabilità (che specifica la probabilità di ogni valore).

Una variabile casuale rappresenta un sistema aleatorio. Possiamo rappresentare un testo o una lingua come una variabile casuale (W): lingua come sistema probabilistico tale che in ogni momento genera una certa parola descritta da una certa probabilità W. Stati possibili sono le parole del vocabolario di tale lingua, e queste parole sono descritte da una certa distribuzione di probabilità.

L'unità di misura dell'informazione è il bit (cifre binarie 0, 1).

Entropia puntuale

È l'entropia associata a un (ciascuno) particolare esito (stato) del sistema probabilistico: h(v) = - log₂p(v) oppure h(v)= log₂p(v). Nel caso di stati equiprobabili, all'aumentare del numero di stati del sistema, l'entropia di ciascuno stato aumenta. Il log in base 2 deriva dal fatto che l'unità di misura dell'informazione sono i bit (0,1).

Entropia generale del sistema

Ma quale è il grado di incertezza generale dell'intero sistema, a prescindere dai singoli esiti? Entropia in senso generale = entropia di un sistema (variabile casuale) = numero medio di bit necessari per trasmettere tutti i messaggi associati a ciascun esito della variabile casuale. Gli stati più probabili (più frequenti) sono descritti con meno bit (messaggi più corti), gli stati meno probabili sono descritti con più bit (messaggi più lunghi) (codice di Shannon-Fano).

Nel caso del testo (finito), si può assumere che i valori (stati) di W siano gli elementi del vocabolario V di un corpus C. Per ogni stato io posso calcolare l'entropia puntuale.

Entropia di una variabile aleatoria

L'entropia di W in generale di una variabile aleatoria è la media delle entropie puntuali dei suoi possibili stati (somma delle entropie puntuali delle parole tipo per le frequenze delle parole tipo diviso |C|). Entropia generale di un sistema = media delle entropie puntuali dei suoi possibili stati (entropia media)

H(W) = p(v₁)h(v₁) + p(v₂)h(v₂) + … + p(v_i)h(v_i) / |C| oppure H(W) = - p(v₁)log₂p(v₁) + p(v₂)log₂p(v₂) + … + p(v_i)log₂p(v_i).

È più informativo, dunque, un testo che contiene un numero maggiore di parole rare. Se gli stati sono equiprobabili, l'entropia media = entropia puntuale; h(v) = H(W). Nel caso in cui gli stati non siano equiprobabili (che è il caso della lingua): a parità di stati del sistema, l'entropia media del sistema è minore di quella che si avrebbe se i suoi stati fossero equiprobabili, ovvero l'incertezza è minore, quindi è più facile predire gli esiti del sistema perché non sono tutti equiprobabili (come in un dado truccato).

A parità di numero di esiti possibili, meno uniforme è la distribuzione di probabilità, minore è l'entropia; una distribuzione uniforme di probabilità crea la situazione di massima incertezza (massima imprevedibilità, dunque massima entropia): a parità di vocabolario, il testo in assoluto più imprevedibile è quello in cui, a ogni istante, ogni parola può apparire con la stessa probabilità di ogni altra, senza alcun tipo di vincoli o restrizioni. Da un punto di vista linguistico, l'entropia è tanto più grande quanto meno numerosi sono i vincoli che condizionano la distribuzione delle parole.

Codice di Shannon-Fano

L'entropia permette anche di capire quale è il modo ottimale di codificare gli stati di un sistema (stabilire il codice ottimale). Gli stati più probabili (più frequenti) sono descritti con meno bit (messaggi più corti), gli stati meno probabili sono descritti con più bit (messaggi più lunghi).

Esempio di stati del sistema: {il, cane, mangia, gatto}

• p(cane) = 1/4
• p(il) = 1/2
• p(mangia) = 1/8
• p(gatto) = 1/8

La codifica ottimale in bit:

• il = 0
• cane = 10
• gatto = 110
• mangia = 111

Entropia e grado di organizzazione

L'entropia è una misura del grado di organizzazione (o disordine) di un sistema: più randomico è il sistema, maggiore è l'equiprobabilità, dunque maggiore è l'entropia; più regolato è il sistema (come la lingua regolata dalla grammatica), minore è l'equiprobabilità, minore è l'entropia a parità di stati possibili. L'entropia diminuisce se aumenta la “struttura” e l'”organizzazione” del sistema, ovvero se aumenta la predicibilità delle dinamiche del sistema.

Applicazioni dell'entropia

Individuare le parole più informative sul contenuto di un testo al fine di classificarlo: più una parola è uniformemente distribuita in testi diversi, minore è l'informazione che è in grado di trasmetterci sul contenuto di un determinato testo, dunque minore è la sua entropia. L'entropia viene usata per pesare le parole con cui indicizzare i testi (verranno usate le parole con maggiore entropia).

Entropia e psicolinguistica

Quando leggiamo un testo, tendiamo a soffermarci visivamente sulle parole più rare (“Gianni ha letto un libro” vs “Gianni ha letto un'epigrafe”), perché ci sorprendono di più. Quando comprendiamo il linguaggio facciamo costantemente delle predizioni su ciò che deve venire: se la predizione è molto diversa da quel che ci aspetteremmo ci sorprendiamo (a livello di movimenti oculari e cerebralmente) – siamo molto sensibili alla sorpresa.

Il grado di sorpresa di una parola può essere misurata con l'entropia puntuale date le parole precedenti. Entropia + modello markoviano: sorpresa(W) = - log₂p(w_i| w_i-1, ..., w₁).

Entropie di sequenze di parole

Entropia per parola (entropy rate): frasi con entropia maggiore sono più complicate da processare. Principio di costanza dell'entropy rate (Genzel e Charniak 2002): i parlanti producono le frasi in modo tale che in media la loro entropia rimanga costante, e ciò è correlato con la capacità di predire le successioni di eventi linguistici (word prediction task).

Entropia di un linguaggio

Entropia di un linguaggio (linguaggio inteso come una sequenza di parole potenzialmente infinita generata da un processo stocastico) = limite a cui tende l'entropia per parola di un campione di un linguaggio che diventa progressivamente più grande. Teorema di Shannon-McMillan-Breiman: se il linguaggio L è generato da un processo stocastico ergodico (= aumentando la lunghezza di una sequenza di parole da esso generate possiamo ottenere un campione perfettamente rappresentativo del processo) e stazionario (= la probabilità che assegna a sequenze di parole sono invarianti rispetto all'asse temporale, come i modelli markoviani), allora vale che:

Ma il linguaggio non è generato da un processo né stazionario né ergodico. Cross entropy: consente di valutare quanto bene un modello probabilistico approssima un certo processo stocastico:

H(W) ≤ H(W, m)

La cross entropy è il costo in bit di usare m come modello per descrivere un processo con distribuzione p. Siano m₁, ..., m_n modelli stocastici di un linguaggio L, la cui distribuzione di prob è p: quale m_i è il modello corretto per L (che meglio lo rappresenta)? Si calcola H(L) approssimandola con l'entropia misurata su un corpus sufficientemente ampio e rappresentativo di L, poi per ogni m_i si calcola H(L, m_i): il modello corretto è quello per il quale è minore lo scarto H(L, m_i) – H(L): dato un insieme di modelli m₁, ..., m_n, il modello più accurato è il modello m_i con la cross entropy minore.

Sostanzialmente, la cross entropy consiste nell'estrarre sequenze di parole secondo la distribuzione di probabilità p, sommando poi il log della loro probabilità m: Per il teorema di Shannon-McMillan... possiamo approssimare la cross entropy prendendo un campione sufficientemente grande di testi del linguaggio.

Tecnologie del linguaggio

Sistemi in grado di accedere al contenuto di informazione attraverso l'elaborazione automatica del linguaggio (NLP o trattamento automatico della lingua): natural language understanding + natural language generation. OB principe: estrarre informazione dal linguaggio in modo automatico.

NLP: testo > sentence splitter > tokenizzatore > analizzatore morfologico (produce le interpretazioni morfologiche di ciascun token) > POS tagger (sceglie l'interpretazione morfologica corretta per quel contesto) > analisi sintattica > analisi semantica > analisi pragmatica. Annotazione del testo.

Concetto di ambiguità

Le espressioni linguistiche possono avere più di una interpretazione, non hanno un significato univoco, il linguaggio è ricco di sfumature; le ambiguità esistono a tutti i livelli di analisi (ambiguità fonologiche, morfologiche e morfosintattiche, sintattiche, semantiche, pragmatiche), e svolgere un determinato task in NLP solitamente significa compiere un'operazione di disambiguazione.

Soluzione all'ambiguità: conoscenza del contesto

• NLP tradizionale: il sistema svolge un task utilizzando una grammatica di regole definite e formalizzate manualmente dal linguista. Vantaggio: basato su analisi linguistiche; svantaggi: limitate capacità di estensione e adattamento a nuovi domini e alla variabilità, lentezza di sviluppo, “language-dependent”, scarsa robustezza.
• NLP e machine learning (su base statistica): l'algoritmo sfrutta la distribuzione statistica dei dati del training corpus per costruire un modello dell'organizzazione e struttura linguistica. Vantaggi: adattabilità ed estendibilità, robustezza, rapidità di sviluppo, “language-independent”; svantaggio: forte dipendenza dai dati del training corpus.

Algoritmi di Machine Learning

Algoritmi che imparano a svolgere un determinato task sulla base di esempi rappresentativi del task che devono imparare a svolgere. Algoritmi che in principio sono in grado di imparare QUALSIASI tipo di task.

Tipi di algoritmi basati su metodi di ML

• Algoritmi non supervisionati (unsupervised): non necessitano di un corpus annotato a mano per creare il modello; adatti a compiti di organizzazione dei dati: clustering e ranking.