Lorenzo Vainigli

Android developer

Tre algoritmi di Word Sense Disambiguation

24 Gennaio 2020
Programmazione
3 min.
423

This post is available in English

La disambiguazione del significato delle parole (word sense disambiguation, w.s.d.) è quella parte dell’elaborazione del linguaggio naturale che si occupa di attribuire ad una parola (token) il suo significato nel contesto in cui appare.

In questo articolo sono presentati tre algoritmi probabilistici per risolvere questo problema, accompagnati dalla loro implementazione in Python.

Gli algoritmi sono:

  • algoritmo Naive Bayes;
  • algoritmo di Lesk;
  • algoritmo EM (Expectation-Maximization);

e sono stati testati su questo corpus opportunamente pre-processato con il codice presente in corpus_preprocessing.py.

Algoritmo Naive Bayes

Questo algoritmo appartiene alla classe degli algoritmi di apprendimento supervisionato e si basa su tre fattori:

w_i: \text{parola} \\ s_i: \text{significato} \\ f_i: \text{feature}

Per semplicità indichiamo come feature fi di una parola wi tutte le altre parole wj che appaiono nella stessa frase; con i ≠ j.

count(x): \text{numero di occorrenze di } x \\ count(s_i, w_j): \text{numero di volte in cui } s_i \text{ viene attribuito a } w_j \\ count(f_j, s_i): \text{numero di volte in cui } f_j \text{ compare in una frase } \\ \text{in cui c’è una parola a cui è attribuito } s_i

Avremo quindi:

P(s_i)=\frac{count(s_i,w)}{count(w)} \\ P(f_j|s_i)=\frac{count(f_j,s_i)}{count(s_i)} \\ \hat{s} = \argmax_{i \in S} P(s_i) \prod_j P(f_j,s_i)

Il risultato dell’ultima espressione rappresenta il significato più adatto per la parola w.

Implementazione in Python: naive_bayes.py

Algoritmo di Lesk

L’algoritmo di Lesk utilizza un dizionario per disambiguare le parole: WordNET è il database che serve.

Il concetto alla base dell’algoritmo di Lesk è l’intersezione tra la definizione data dal dizionario e il contesto in cui appare la parola da disambiguare. Più precisamente, il significato attribuito dall’algoritmo è quello nella cui definizione (che può essere estesa con alcune frasi di esempio) compaiono il numero maggiore di parole (feature) del contesto.

\overrightarrow{d_s}: \text{parole che compongono la definizione di } s \\ \overrightarrow{e_s}: \text{parole che compongono gli esempi per } s \\ \overrightarrow{f}: \text{parole che appaiono nel contesto} \\ \hat{s} = \argmax_{s \in S} |(\overrightarrow{d_s} \cup \overrightarrow{e_s}) \cap \overrightarrow{f}|

Implementazione in Python: lesk.py

Algoritmo EM

L’algoritmo Expectation-Maximization fa parte della classe degli algoritmi di apprendimento non supervisionato.

L’obiettivo è la massimizzazione del likelihood del corpus:

l(C) = log(\prod_i P(c_i))

dove C è il corpus e ci sono i singoli contesti che compongono il corpus, ovvero le frasi.

P(c_i) = \sum_k P(c_i|s_k)P(s_k) \\ P(c_i|s_k) = \prod_{f_j \in c_i} P(f_j|s_k)

All’inizio i parametri P(sk) e P(fj|sk) vengono inizializzati in modo casuale. Come il nome suggerisce, l’algoritmo iterativo è composto dalle fasi:

  • E-step: stima la probabilità a posteriori che il senso sk generi il contesto ci.
h_{ik} = \frac{P(c_i|s_k)}{\sum_{k=1}^{K}(P(c_i|s_k)}
  • M-step: ricalcolo dei parametri P(sk) e P(fj|sk).
P(s_k) = \frac{\sum_{i=1}^{I}h_{ik}}{\sum_{k=1}^{K}\sum_{i=1}^{I}h_{ik}} \\ P(w_j|s_k) = \frac{\sum_{\{c_i|w_j \in c_i\}}h_{ik}}{Z_k} \\ Z_k = \sum_{k=1}^{K} \sum_{\{c_i|w_j \in c_i\}}h_{ik}

Il ciclo iterativo va avanti finché l(C) viene migliorato.

Implementazione in Python: em.py

Note

Nonostante non abbia riscontrato altri errori nei codici sorgente se non quelli segnalati con i commenti nei file stessi, non garantisco la loro completa correttezza.

Riferimenti

Lorenzo Vainigli

Sviluppatore Android e appassionato fin da piccolo di computer e tecnologia.
Ho una laurea magistrale in Informatica conseguita all'Università di Bologna.
Mi piacciono l'astronomia 🌌 e la cultura giapponese ⛩️.
Qui racconto di più su di me.