Blog divulgativo sulla matematica applicata

Game Of Math: L'algoritmo MaxEnt e il Trono di Spade.

Game of Thrones.

Sicuramente vi starete chiedendo cosa c'entra la Matematica con Game of Thrones? Beh lo ammetto, avrei potuto utilizzare una qualsiasi altra serie TV per dirvi quello che segue in questo post, ma onestamente ... cosa è meglio di Game of Thrones (GoT)?
Il collegamento con la Matematica non sta tanto nella serie considerata ma nel tipo di dati utilizzati. In particolare quello che si è utilizzato è l'insieme dei commenti inseriti sul sito di recensioni IMDb riguardo GoT (in inglese) per produrre questa infografica, all quale ho lavorato insieme a mio fratello.

got

 

Analisi dell'Infografica.

Molto brevemente andiamo a vedere dapprima quali tipi di informazione sono stati estratti dai vari commenti (671).

Nella mappa a sinistra vengono riportate le principali casate posizionate ciascuna nella propria città di riferimento, indicando per ognuna:

  • il numero di review in cui la singola casata viene nominata;
  • il numero di review in cui si parla positivamente della casata;
  • il numero di review in cui si parla negativamente della casata;
  • il membro della casata più citato;
  • il membro della casata meno citato.

Nel carteggio a destra invece compaiono invece:

  • l'andamento dei personaggi più nominati di ciascuna casata nelle 5 stagioni della serie;
  • i personaggi non attribuibili a casate più citati;
  • i grafi delle co-occorrenze tra personaggi e tra casate.

La parte dell'infografica sulla quale però vorrei focalizzare l'attenzione è quella relativa alla wordcloud in basso a destra, dove sono riportati gli aggettivi maggiormente utilizzati nelle review di una casata.
Dal punto di vista dell'analisi l'aspetto da spiegare è come stabilire se una parola all'interno di un discorso debba essere considerata come aggettivo piuttosto che come preposizione o articolo. Ed è qui che entra in gioco la Matematica.

Per effettuare questo tipo di analisi è stato utilizzato un POS (Part of Speech) Tagger, ossia uno strumento in grado di effettuare analisi grammaticale su un testo. Il POS Tagger preso in considerazione è quello presente nella libreria OpenNLP basato sul modello Maximum Entropy che andremo ad analizzare in dettaglio.

La teoria dell'informazione e il concetto di entropia.

Prima di addentrarci nell'esame dell'algoritmo MaxEnt vorrei precisare il concetto di entropia qui utilizzato.
Più comunemente si parla di entropia nei seguenti ambiti:

  • termodinamica: l'entropia di un gas è una funzione della sua temperatura, volume, massa e natura del gas; è un indice di reversibilità: quando non vi è variazione, il processo è reversibile, altrimenti è irreversibile (basti pensare allo scambio di calore tra due corpi, uno caldo e uno freddo).
  • meccanica statistica: l'entropia significa un aumento di disordine (impossibilità di prevedere posizione e velocità delle particelle); in sostanza maggiore è la conoscenza, minore è l'entropia e viceversa.

A queste interpretazioni dell'entropia se ne aggiunge un'altra, che riveste un ruolo molto importante nella teoria dell'informazione (soprattutto nell'ambito della teoria dei segnali) e sarà il modo in cui dovremo intenderla nel nostro caso.

Si consideri una sorgente di messaggi X. La quantità di informazione trasmessa dal messaggio aumenta con l'aumentare dell'incertezza del messaggio prodotto.
Tanto maggiore è la nostra conoscenza sul messaggio prodotto dalla sorgente, tanto minore sarà l'incertezza, minore l'entropia e minore l'informazione trasmessa.
Formalizziamo il concetto di entropia, così come introdotta da Claude Shannon nel 1948.

Definizione 1

Siano X una sorgente ed x un segnale emesso da X. L'informazione contenuta da x è detta autoinformazione e si definisce come

I(x) = -\log_{2}{p(x)}

dove p(x) è la probabilità che l'evento x accada.

Definizione 2

Si definisce entropia di una sorgente X il valore atteso dell'autoinformazione, ossia l'informazione media contenuta in ogni segnale proveniente da X, in particolare

H(X) = E[I(X)] = \sum_{i=1}^N P(x_i) \log_{2}{p(x_i)}
in caso di variabile X discreta

H(X) = - \int p(x) \log_{2}{p(x)}\, dx
in caso di variabile X continua

Proposizione 1

Sia X una sorgente discreta, allora si ha

0\leq H(X) \leq \log_{2}{N}

In particolare si ha che il massimo dell'entropia è \log_{2}{N} e si raggiunge quando tutti gli N eventi sono equiprobabili.

shannon

Esaminiamo un semplice esempio

Esempio 1
Supponiamo di avere una sorgente X che ha probabilità p di emettere 1 e probabilità 1-p di emettere 0.

Allora

H(X) = -(p\log_{2}{p} + (1-p)\log_{2}{(1-p))}

e si ha che l'entropia vale 1 se p=1/2 (sorgente imprevedibile), mentre vale 0 se p=1 (sorgente completamente prevedibile, ossia emetterà o sempre 1 o sempre 0).

L'algoritmo MaxEnt.

Introduzione.

Il classificatore Maximum Entropy è un classificatore discriminativo molto usato negli ambiti di Natural Language Processing, Speech Recognition e Information Retrieval, in particolare per risolvere problemi di classificazione del testo quali rilevamento della lingua, dei topic e sentiment analysis.
L'algoritmo Max Entropy si basa su principio di Massima Entropia e seleziona il modello che presenta la massima entropia (intesa secondo quanto enunciato da Shannon) sul training set tra tutti i modelli testati.

Richiamando il teorema di Bayes (vedi qui), il classificatore Max Entropy viene utilizzato quando non si ha nessuna informazione sulla distribuzione a priori dei dati e non è corretto fare delle assunzioni in merito.
Diversamente dal classificatore Naive Bayes, il Max Entropy non ha come ipotesi quella che le variabili siano indipendenti tra di loro, cosa che rispecchia la natura del testo naturale dove le variabili in considerazione sono le parole, che ovviamente non sono indipendenti tra di loro in quanto legate dalle regole grammaticali della lingua; inoltre rispetto al modello Naive Bayes richiede maggior tempo nell'addestramento pur fornendo risultati molto più affidabili.

Esempio 2
Prima di addentrarci nella teoria che sta dietro il MaxEnt, consideriamo un esempio che chiarisce sin da subito cosa verrà detto in maniera formale nel seguito.

Supponiamo di voler determinare la forma grammaticale della parola "amare".

La parola "amare" può assumere le seguenti forme:

  • Aggettivo: "Queste cioccolate sono tutte amare."
  • Sostantivo: "Amare è un bisogno innato dell'uomo."
  • Verbo: "I narcisisti riescono ad amare solo se stessi."

Collezioniamo un numero abbastanza grande di esempi dal quale estrarre informazioni per stabilire il modello decisionale. Il modello p che andremo a costruire assegnerà alla parola "amare" una probabilità di assumere un particolare significato grammaticale.

Non avendo altre informazioni dai dati, si può imporre per il nostro modello p:

p(aggettivo) + p(sostantivo) + p(verbo) = 1

Ci sono infiniti modelli p per cui vale la precedente identità, tra questi:

  • p(aggettivo) = 1, p(sostantivo) = p(verbo) = 0
  • p(sostantivo) = 1, p(aggettivo) = p(verbo) = 0
  • p(verbo) = 1, p(aggettivo) = p(sostantivo) = 0
  • p(aggettivo) = p(sostantivo) = p(verbo) = \frac{1}{3}

Analizzando ulteriormente il dataset, supponiamo di entrare in possesso di altre informazioni, ad esempio ogni volta che la parola "amare" è preceduta dalla parola "sono" è un aggettivo. Questo, aggiunto alla condizione di normalizzazione, cambia le possibili probabilità, riducendo i possibili modelli.

Lo scopo che si prefigge l'algoritmo MaxEnt è quello di determinare il modello p più uniforme possibile (massimizzando l'entropia), attenendosi alle sole informazioni derivanti dai dati, senza fare nessuna ulteriore ipotesi.

L'algoritmo.

Passiamo alla spiegazione dell'algoritmo MaxEnt.

Consideriamo un documento di tipo testuale d e siano \left\{w_1, w_2, \dots, w_m \right\} m parole a ciascuna delle quali corrisponde un particolare tag \left\{y_1, y_2, \dots, y_m \right\} (ossia una parte grammaticale del documento: sostantivo, aggettivo, pronome, articolo, ecc.); introduciamo il concetto di "storia" della parola w_i come le possibili informazioni derivanti dal contesto in cui è collocata w_i e la indichiamo x_{i}.

Facciamo un piccolo esempio per spiegare come si può intendere la "storia" di una parola.

Esempio 3
Consideriamo la frase "Oggi è proprio una bella giornata". L'insieme delle parole è {Oggi, è, proprio, una, bella, giornata} e intendiamo qui la "storia" delle varie parole come le informazioni grammaticali della parola precedente e successiva.
Ad esempio, per la parola "bella",

x_{ = {articolo indeterminato femminile singolare - "una", sostantivo singolare femminile - "giornata"}

 

Quello che andiamo ora a definire è un modello stocastico che stimi la probabilità condizionale di ottenere un tag y, dato una particolare "storia" x, ossia p(y | x).

Allora seguendo il solito schema di classificazione, costruiamo il nostro modello a partire dalle coppie (x_i, y_i) del training set, dove x_i è la "storia" della parola w_i e y_i è la classe ad essa attribuita (la parte grammaticale del discorso).
Consideriamo la distribuzione di probabilità basata sul campione

\tilde p(x, y) = \frac{1}{N}|(x, y)|

dove N è la dimensione del training set, mentre |(x, y)| è il numero di occorrenze della coppia (x, y) nel training set.
Introduciamo la funzione indicatrice

f_j(x, y) := \left\{\begin{array}{ll}1 \ & y = y_i \ e \ x \ contiene \ w_k \\ 0 \ & altrimenti\end{array}\right.

e consideriamo queste funzioni f_j come le variabili per la costruzione del nostro modello.
Si ha che il valore medio della variabile f_j rispetto alla probabilità derivante dal campione è

\tilde p(f_j) = \sum\limits_{x, y} \tilde p(x, y) f_j(x, y)

dove chiaramente \tilde p(x, y) = \frac{1}{N} se ciascuna coppia del training set ha occorrenza 1.

Mentre il valore medio della variabile f_j rispetto alla probabilità del modello p(y | x) è pari a

p(f_j) = \sum\limits_{x, y} \tilde p(x) p(y | x) f_j(x, y)

Si impone la condizione che il valore medio del modello sia limitato a quello di f_j sul training set, ossia

\tilde p(f_j) = \sum\limits_{x, y} \tilde p(x, y) f_j(x, y) = \sum\limits_{x, y} \tilde p(x) p(y | x) f_j(x, y) = p(f_j)

Si hanno ora tante condizioni come la precedente per ciascuna f_j, che possono essere soddisfatte da infiniti modelli e per scegliere il migliore utilizziamo il principio di Massima Entropia, selezionando il modello più vicino possibile al modello uniforme (massimizzazione dell'informazione).

In particolare si dimostra che esiste ed è ben definito il modello p^* che massimizza l'entropia su un sistema di vincoli C.

Nel nostro caso il problema da risolvere è il seguente:

Determinare p^* tale che

p^* = \underset{p \in C}{\arg\max} \ H(p) = \underset{p \in C}{\arg\max} \ ( - \sum\limits_{x, y} \tilde p(y | x) log p( y | x))
con

  • p(y|x) \geq 0 \ \forall x, \ y.
  • \sum\limits_{y} p(y|x) =1, \ \forall x.
  • \sum\limits_{x, y} \tilde p(x, y) f_j(x, y) = \sum\limits_{x, y} \tilde p(x) p(y | x) f_j(x, y).

Si procede alla risoluzione tramite i moltiplicatori di Lagrange

\begin{equation}\begin{split}\Xi(p, \Lambda, \gamma) & = - \sum\limits_{x, y} \tilde p(y | x) log p( y | x) \ + \\& \sum\limits_{j} \lambda_{j} (\sum\limits_{x, y} \tilde p(x, y) f_j(x, y) - \tilde p(x) p(y | x) f_j(x, y)) \ + \\& \gamma \sum\limits_{x} \tilde p(y | x) - 1\end{split}\end{equation}

ottenendo la soluzione

p^*(y|x) = \gamma^* \ exp(\sum\limits_j \lambda_j f_j(x,y)) = \frac{1}{\sum\limits_{y} exp(\sum\limits_{j} \lambda_j f_j(x,y))} \ exp(\sum\limits_j \lambda_j f_j(x,y))

A questo punto inseriamo nella Lagrangiana i valori di p^* e \gamma^* ed otteniamo \Lambda^*, massimizzando la funzione che ne segue, per la quale si precisa che (senza dimostrarlo qui):

  • è la log-verosimiglianza del modello esponenziale p(y | x);
  • il problema di massimo non si risolve analiticamente ma tramite metodi numerici (gradiente coniugato, GIS - Generalized Iterative Scaling), sfruttando la regolarità e la convessità della funzione per ogni \lambda_j.

Quindi, effettuato l'addestramento del POS Tagger su un training set, si procede ad effettuare una classificazione sulle nuove parole da analizzare (test set). Nel nostro caso il POS Tagger, già addestrato su un dataset abbastanza grande, viene utilizzato per la classificazione delle parole presenti nelle review di IMDb; scartate tutte le parole che non vengono classificate come aggettivi, si procede quindi all'attribuzione degli aggettivi alle casate in base alla frequenza nelle review di una specifica casata.

Conclusioni.

Ora, se non siete dei fan di Game of Thrones, ripeto che quanto raccontato sopra si può applicare anche ad altre serie TV (House of Cards, The Walking Dead, etc.) oppure in ambiti completamente differenti, tipo … quello che vedremo nel prossimo post :P.
Per questa volta la conclusione è una sola ... il 24.04 inizia la sesta stagione.
Winter is coming ...


jon_snow

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Seguici su Twitter

Tag Cloud

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination