Stomachion

martedì 28 aprile 2015

L'entropia di un documento

Il linguaggio è stato ed è tutt'ora un campo di interesse anche per logici e matematici (in questo senso il più noto tra tutti è sicuramente Ludwig Wittgenstein). Nel 1959 il linguista George Kingsley Zipf diffuse la legge che prende il suo nome, la legge di Zipf, nonostante non ne fosse lo scopritore(1): essa stabilisce che dato un qualche corpo di enunciati in un linguaggio naturale, la frequenza di ogni parola è inversamente proporzionale al suo rango nella tabella delle frequenze.
Dal punto di vista matematico si può descrivere la legge di Zipf come segue: \[f (k; s, N) = \frac{1/k^s}{\sum_{n=1}^N (1/n^s)}\] dove $N$ è il numero degli elementi del linguaggio, $k$ il rango, $s$ un numero che caratterizza la distribuzione, $f$ la frequenza degli elementi di rango $k$.

Schema di un sistema di comunicazione generico
Tra il 1948(2) e il 1951(3), il matematico Claude E. Shannon innanzitutto pose le basi per la moderna teoria dell'informazione, i cui elementi sono:
  • una sorgente di informazioni che produce messaggi;
  • un trasmettitore che opera sui messaggi per creare un segnale che può essere inviato attraverso un canale;
  • un canale, che è il mezzo con il quale è inviato il segnale, che trasporta l'informazione composta nel messaggio;
  • un ricevente, che trasforma il segnale di ritorno nel messaggio da consegnare;
  • una destinazione, che può essere una persona o una macchina, per cui il messaggio è destinato.
Quindi definì e introdusse una sorta di entropia del linguaggio:
L'entropia è un parametro statistico che misura, in un certo senso, quanta informazione è prodotta in media per ogni lettera in un testo del linguaggio.
Dal punto di vista matematico Shannon calcola l'entropia come limite di una serie: \[F_N = - \sum_{i,j} p (b_i, j) \log_2 p_{b_i} (j)\] dove $b_i$ è un blocco di $N - 1$ lettere (detto $(N-1)$-gramma), $j$ è una lettera arbitraria scelta tra le $b_i$, $p (b_i, j)$ è la probabilità dell'$N$-gramma $b_i$, $j$, $p_{b_i} (j)$ è la probabilità condizionata della lettera $j$ con il blocco $b_i$, data da $p(b_i, j) / p (b_i)$.
L'entropia è quindi data come il limite all'infinito delle $F_N$: \[H = \lim_{N \rightarrow \infty} F_N\]

Frequenza relativa vs rango per le parole inglesi
In un papero uscito su arXiv (via Peppe Liberti) Sachio Hirokawa e Eisuke Ito, seguendo i lavori di Shannon e Yavuz(4) (che non sono riuscito a trovare...) sull'entropia nel linguaggio, calcolano il limite superiore dell'entropia di un documento.
Innanzitutto sia $D$ un insieme di documenti ed $fr (w)$ il numero di volte che una data parola $w$ compare nei documenti. Dato un intero $k$, si indica con $F (k)$ il numero di parole la cui frequenza è $k$, ovvero \[f(k) = \#\lbrace w \in D | fr (w) = 4 \rbrace\] L'entropia dell'insieme di documenti è definita come \[E (D) = \sum_{w \in D} p(w) \log (p(w))\] dove $p(w) = fr(w) / N$ ed $N = \sum_{w \in D} fr(w)$.
Se $F(k)$ segue la legge di potenza \[\log(F(k)) = −a \cdot \log(k)+b\] con $a \geq 1$, allora \[E(D) \leq e^{b(1−\frac{1}{a})} \left ( \frac{b}{a} + 1 \right )\]
(1) Per quel che si sa fino a ora, il primo ad aver utilizzato una legge di questo genere è stato il fisico Felix Auerbach nel 1913:
Auerbach F (1913) Das Gesetz der Bevölkerungskonzentration. Petermanns Geogr Mitt 59: 74–76
(2) Shannon C.E. (1948). A Mathematical Theory of Communication, Bell System Technical Journal, 27 (3) 379-423. DOI: http://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x archive.org)
(3) Shannon C.E. (1951). Prediction and Entropy of Printed English, Bell System Technical Journal, 30 (1) 50-64. DOI: http://dx.doi.org/10.1002/j.1538-7305.1951.tb01366.x archive.org)
(4) Yavuz D. (1974). Zipf's law and entropy (Corresp.), IEEE Transactions on Information Theory, 20 (5) 650-650. DOI: http://dx.doi.org/10.1109/tit.1974.1055269

1 commento: