72  Entropia e informazione di Shannon

Obiettivi di apprendimento

Al termine di questo capitolo, sarai in grado di:

• Comprendere e sapere calcolare l’informazione di Shannon.
• Comprendere e sapere calcolare l’entropia per variabili casuali discrete.
• Comprendere il concetto di entropia per variabili casuali continue.

Prerequisiti

• Per i concetti di base sulla teoria dell’informazione, si rimanda ai primi due capitoli di Information Theory: A Tutorial Introduction (Stone, 2022).

Preparazione del Notebook

72.1 Introduzione

In questo capitolo, descriveremo il concetto di entropia, una misura fondamentale sviluppata nell’ambito della teoria dell’informazione. L’entropia ci permette di quantificare l’incertezza associata a una distribuzione di probabilità e, di conseguenza, la quantità di informazione che un evento ci fornisce.

L’entropia è legata alla nostra capacità di prevedere l’esito di un evento: più un risultato è imprevedibile, maggiore sarà l’entropia. In termini più generali, l’entropia di una variabile casuale misura quanto il valore che essa assumerà in media sia incerto o “sorprendente”. Se ogni possibile esito ha la stessa probabilità di verificarsi, l’entropia sarà massima. Se invece alcuni esiti sono molto più probabili di altri, l’entropia diminuisce, poiché l’incertezza complessiva si riduce.

Un’intuizione sull’entropia può essere ottenuta considerando il seguente esempio. Immaginiamo un sacchetto di palline colorate. Se il sacchetto contiene solo palline di un unico colore, possiamo essere sicuri di quale pallina estrarremo ogni volta. Non c’è alcuna incertezza o sorpresa, quindi l’entropia è pari a zero. Tuttavia, se nel sacchetto ci sono palline di diversi colori in numero uguale, ogni estrazione è un’incognita: l’incertezza è massima e, di conseguenza, lo è anche l’entropia.

Il concetto di entropia va ben oltre questo semplice esempio. Si applica a qualunque situazione in cui vi sia un insieme di risultati possibili con probabilità diverse. In questo capitolo ci concentreremo sul significato matematico dell’entropia, esplorando come può essere calcolata per diverse distribuzioni di probabilità e come essa sia correlata alla quantità di informazione che un sistema può fornire. Inizieremo con esempi semplici, come l’entropia di una moneta equa o di un dado, per poi passare a situazioni più complesse.

72.2 Che cos’è l’informazione?

L’informazione è solitamente misurata in bit e un bit di informazione permette di scegliere tra due alternative ugualmente probabili. Il termine bit deriva da “binary digit”, ovvero “cifra binaria”, che può assumere il valore 0 o 1.

Per capire come l’informazione possa essere misurata in bit, consideriamo il seguente esempio. Immaginiamo di trovarci a un incrocio e di dover scegliere una strada tra due possibilità. Ogni volta che ci troviamo di fronte a un incrocio, dobbiamo prendere una decisione: andare a destra o a sinistra. Ogni decisione può essere rappresentata da un bit di informazione: 0 per la sinistra e 1 per la destra.

Consideriamo il percorso con più incroci rappresentato nell’immagine seguente. Ogni percorso completo può essere codificato da una sequenza di bit, dove ogni bit corrisponde a una decisione (binaria) presa a un incrocio. Ad esempio, per raggiungere il punto D011, la sequenza di bit corretta è 011.

Quanti bit sono necessari per identificare una destinazione specifica?

Ogni bit raddoppia il numero di possibili percorsi. Quindi, se abbiamo \(n\) bit, possiamo identificare \(2^n\) destinazioni distinte. Viceversa, se conosciamo il numero di destinazioni \(m\), possiamo calcolare il numero di bit necessari utilizzando la formula:

\[ n = \log_2 m. \]

Nel nostro esempio, abbiamo otto destinazioni finali. Pertanto, sono necessari 3 bit (3 decisioni binarie) per identificarne una in modo univoco.

Cosa rappresenta un bit in questo contesto?

Un bit rappresenta un’unità elementare di informazione. In questo caso, ogni bit risponde alla domanda: “Devo andare a destra o a sinistra?”.

Perché utilizziamo i logaritmi?

Il logaritmo in base 2 ci permette di calcolare l’esponente a cui elevare 2 per ottenere un dato numero. In altre parole, ci indica quanti bit sono necessari per rappresentare un certo numero di destinazioni. Per l’esempio considerato, per arrivare a \(D011\) partendo da \(A\), sono necessarie 3 domande la cui risposta è binaria (destra/sinistra).

Per riassumere:

• per raggiungere il punto D011 partendo da A, abbiamo bisogno di prendere tre decisioni binarie (sinistra o destra) in corrispondenza di tre incroci;
• ogni decisione binaria può essere rappresentata da un bit (0 o 1). Quindi, per l’intero percorso, abbiamo bisogno di una sequenza di tre bit: 011;
• per rispondere alla domanda “Come si va da A a D011?”, abbiamo dunque bisogno di 3 bit di informazione.

In sintesi, esiste una relazione diretta tra il numero di bit di informazione e il numero di possibili destinazioni in un percorso decisionale binario. Ogni bit ci permette di scegliere tra due alternative, raddoppiando così il numero di possibili percorsi.

72.3 La Sorpresa e l’Informazione di Shannon

Nel primo esempio abbiamo visto che l’informazione può essere misurata in bit, dove ogni bit corrisponde a una scelta binaria che ci aiuta a raggiungere una destinazione specifica lungo un percorso. Tuttavia, la quantità di informazione può variare anche in base alla probabilità con cui si verificano determinati eventi o si fanno determinate scelte. È qui che entra in gioco il concetto di “informazione di Shannon”, che prende in considerazione la sorpresa associata a un risultato.

Immaginiamo, ad esempio, di avere una moneta che cade “testa” nel 90% dei casi. Poiché il risultato “testa” è molto probabile, non ci sorprenderemmo molto se lo ottenessimo. Al contrario, il risultato “croce”, che si verifica solo nel 10% dei casi, ci sorprenderà di più. Più un risultato è improbabile, maggiore sarà la sorpresa nel vederlo.

In termini di informazione, i risultati meno probabili forniscono più informazione perché ci sorprendono di più. Una prima idea per misurare questa sorpresa è definirla come inversamente proporzionale alla probabilità del risultato, ovvero \(1/p(x)\). Tuttavia, Shannon ha dimostrato che è più utile esprimere la sorpresa come il logaritmo di \(1/p(x)\). Ciò ci porta alla definizione dell’informazione di Shannon, che si misura in bit (se si utilizza il logaritmo in base 2, lo stesso utilizzato per misurare i percorsi nel primo esempio). L’informazione di Shannon per un risultato \(x\) è quindi:

\[ h(x) = \log_2 \frac{1}{p(x)} = -\log_2 p(x) \text{ bit}. \tag{72.1}\]

In questo modo, vediamo che l’informazione associata a un evento dipende dalla sua probabilità: eventi meno probabili portano più informazione, e viceversa.

72.4 Sorpresa e Probabilità

Per comprendere pienamente la sorpresa, dobbiamo conoscere le probabilità dei diversi risultati. Questo significa che l’informazione di Shannon dipende dalla distribuzione di probabilità \(p(X)\) della variabile casuale \(X\). In altre parole, per misurare quanta informazione otteniamo da un risultato, dobbiamo sapere quanto è probabile ciascun possibile esito.

Un modo per stimare queste probabilità è osservare i risultati di un esperimento ripetuto nel tempo. Utilizzando le osservazioni, possiamo stimare la probabilità di ciascun risultato e quindi calcolare l’informazione di Shannon associata. Questo approccio ci permette di collegare il concetto di informazione misurata in bit (come nel primo esempio sugli incroci) con la sorpresa generata da eventi più o meno probabili.

72.5 Entropia come Media dell’Informazione di Shannon

Quando si lavora con fenomeni casuali, non ci interessa solo la sorpresa associata a un singolo risultato, ma piuttosto la sorpresa media che si può ottenere considerando tutti i possibili risultati di una variabile. Questa sorpresa media è chiamata “entropia” e si indica con \(H(X)\). L’entropia fornisce una misura della quantità di incertezza (o informazione potenziale) contenuta in una variabile casuale \(X\) la cui distribuzione di probabilità è data da \(p(X)\).

L’entropia rappresenta quindi la quantità media di informazione che si ottiene osservando i risultati della variabile \(X\). Se, per esempio, lanciamo una moneta molte volte, l’entropia della distribuzione dei risultati riflette la media delle informazioni di Shannon ottenute da ciascun lancio. In altre parole, ci dice quanto ci si può aspettare di “imparare” in media da ogni lancio.

Matematicamente, l’entropia può essere approssimata dalla media delle informazioni di Shannon associate a ciascun possibile risultato \(x_i\):

\[ H(X) \approx \frac{1}{n} \sum_{i=1}^{n} h(x_i). \tag{72.2}\]

In questa formula, \(h(x_i)\) rappresenta l’informazione di Shannon di un singolo risultato \(x_i\), come discusso in precedenza. L’entropia, quindi, non si riferisce a un evento specifico, ma alla sorpresa media che ci si aspetta quando si osserva ripetutamente una variabile casuale. Più la distribuzione delle probabilità dei risultati è equilibrata (per esempio, se tutti i risultati sono ugualmente probabili), maggiore sarà l’entropia, perché ciascun risultato fornirà una quantità simile di informazione. Al contrario, se alcuni risultati sono molto più probabili di altri (per esempio, una moneta truccata che dà quasi sempre “testa”), l’entropia sarà minore, perché si otterrà meno informazione da ogni osservazione.

Esempio 72.1 Se una moneta è equa, allora \(p(x_h) = 0.5\) e la sorpresa di osservare una testa è

\[ \begin{align} h(x_h) &= \log_2 \frac{1}{p(x_h)} \notag\\ &= \log_2(1/0.5) = 1 \text{ bit}.\notag \end{align} \]

Dato che \(p(x_t) = 0.5\), la sorpresa di osservare una testa (o una croce) è di un bit.

Possiamo trovare la sorpresa media lanciando la moneta, diciamo, 100 volte, misurando la sorpresa di ogni risultato e poi calcolando la media dei 100 risultati. Se lanciamo una moneta 100 volte, ci aspettiamo di osservare testa circa 50 volte e croce circa 50 volte. Se osserviamo esattamente 50 teste e 50 croci, la quantità media di sorpresa diventa

\[ \begin{align} H(X) &= \frac{1}{100} \left( \sum_{i=1}^{50} \log_2 \frac{1}{p(x_h)} + \sum_{i=1}^{50} \log_2 \frac{1}{p(x_t)} \right)\notag\\ &=1 \text{ bit per lancio della moneta}\notag. \end{align} \]

In sintesi, poiché la quantità di sorpresa o informazione di Shannon fornita dall’osservazione del risultato di ogni lancio di questa moneta equa è di un bit, ne segue che l’informazione media \(H(X)\) di ogni lancio è anch’essa di un bit.

72.6 Interpretazione dell’entropia (1)

Se consideriamo una distribuzione di probabilità uniforme, una variabile con entropia \(H(X)\) espressa in bit fornisce un’informazione sufficiente (nel senso della teoria dell’informazione di Shannon) per distinguere tra \(m = 2^(H(X))\) alternative ugualmente probabili. In altre parole, l’entropia misura la quantità di informazione contenuta in una variabile, esprimendola in termini del numero di scelte ugualmente probabili possibili per quella variabile.

Esempio 72.2 Una moneta sbilanciata ha una quantità media di informazione (o incertezza) inferiore rispetto a una moneta equa.

La sorpresa associata a testa è:

\[ h(\text{testa}) = \log\left(\frac{1}{0.9}\right) = 0.15 \text{ bit}, \]

mentre la sorpresa associata a croce è maggiore:

\[ h(\text{croce}) = \log\left(\frac{1}{0.1}\right) = 3.32 \text{ bit}. \]

72.7 Interpretazione dell’Entropia (2)

Se immaginiamo di lanciare la moneta molte volte, la sorpresa media o entropia di questa moneta, considerando \(p(\text{testa}) = 0,9\) e \(p(\text{croce}) = 0,1\), è:

\[H(X) = 0.9 \log_2 \frac{1}{0.9} + 0.1 \log_2 \frac{1}{0.1} = 0.469 \text{ bit per lancio}.\]

L’incertezza media di questa moneta sbilanciata è dunque inferiore a quella di una moneta equa (che ha un’entropia di 1 bit), anche se l’incertezza associata all’esito meno probabile (croce) è maggiore (3.32 bit) rispetto a quella di una moneta equa (1 bit). In generale, nessuna moneta sbilanciata può avere un’entropia media maggiore di quella di una moneta equa.

Poiché \(p(\text{testa}) = 0.9\) e \(p(\text{croce}) = 0.1\), la formula dell’entropia può essere scritta come:

\[ H(X) = p(\text{testa}) \log\left(\frac{1}{p(\text{testa})}\right) + p(\text{croce}) \log\left(\frac{1}{p(\text{croce})}\right) = 0.469 \text{ bit per lancio}. \]

Per semplificare ulteriormente, possiamo rappresentare l’entropia sommando i due possibili esiti (testa e croce):

\[ H(X) = \sum_{i=1}^{2} p(x_i) \log\left(\frac{1}{p(x_i)}\right) = 0.469 \text{ bit per lancio}. \]

Questa entropia di 0.469 bit implica che l’informazione contenuta in 1000 lanci di questa moneta potrebbe essere rappresentata utilizzando solo 469 bit binari, ovvero \(1000 \times 0.469\).

Possiamo interpretare questo risultato considerando l’entropia in termini di numero di alternative ugualmente probabili. La variabile \(X\), che rappresenta il lancio della moneta, può essere vista come equivalente a una variabile che può assumere i valori:

\[ m = 2^{H(X)} = 2^{0.469} \approx 1.38 \text{ valori equiprobabili}. \]

A prima vista, questo risultato può sembrare strano, dato che stiamo considerando una moneta che ha solo due esiti possibili. Tuttavia, interpretare l’entropia in termini di un numero equivalente di valori ugualmente probabili ci fornisce un’intuizione sull’informazione rappresentata da una variabile. Un modo per comprendere questo concetto è immaginare che una moneta con entropia \(H(X) = 0.469\) bit abbia la stessa quantità di incertezza di un ipotetico dado con 1.38 facce.

72.8 Caratteristiche dell’entropia

• Entropia massima: l’entropia raggiunge il suo valore massimo quando tutti gli esiti di un evento hanno la stessa probabilità di verificarsi. In questa situazione, l’incertezza è massima, poiché non ci sono indizi che ci permettano di prevedere il risultato. Ciò rappresenta il massimo grado di imprevedibilità.

• Entropia minima: l’entropia è minima quando l’esito di un evento è completamente certo (con probabilità pari a 1) o impossibile (con probabilità pari a 0). In questi casi, non c’è incertezza né sorpresa, quindi non c’è alcuna informazione aggiuntiva da ottenere osservando il risultato.

72.8.1 Additività dell’entropia per eventi indipendenti

L’entropia è additiva nel caso di eventi indipendenti. Ciò significa che, se si verificano due o più eventi indipendenti, l’entropia totale della loro combinazione è pari alla somma delle entropie di ciascun evento considerato singolarmente. Questa proprietà deriva dall’additività dei logaritmi che permette di sommare le entropie individuali per ottenere l’entropia complessiva.

72.9 Stimare l’Entropia da una Distribuzione di Probabilità

Consideriamo una variabile casuale discreta \(X\), che rappresenta una serie di eventi distinti, ciascuno con una probabilità associata. Per una variabile discreta \(X\) con possibili valori \(x_1, x_2, \dots, x_n\) e una funzione di massa di probabilità \(p(x) = \Pr\{X = x\}\), l’entropia \(H(X)\) misura l’incertezza complessiva associata a questa distribuzione di probabilità e si calcola con la formula:

\[ \begin{equation} H(X) = -\sum_{x \in X} p(x) \log_2 p(x). \end{equation} \tag{72.3}\]

In questo contesto, l’entropia \(H(X)\) rappresenta l’incertezza media relativa alla collezione di eventi descritti dalla variabile \(X\). La formula fornisce una somma pesata delle sorprese associate a ciascun esito, dove la sorpresa di un risultato \(x\) dipende dalla sua improbabilità, calcolata come \(-\log_2 p(x)\). Il segno negativo è necessario perché i logaritmi delle probabilità, essendo inferiori a 1, sono negativi; il segno negativo li trasforma in valori positivi, che rappresentano correttamente la sorpresa o l’informazione associata.

Ogni termine della somma, \(-p(x) \log_2 p(x)\), esprime la quantità di informazione o sorpresa relativa a un singolo evento, ponderata dalla sua probabilità \(p(x)\). Più le probabilità degli eventi sono distribuite in modo uniforme, maggiore sarà l’entropia complessiva. Al contrario, se uno o più eventi sono molto più probabili rispetto agli altri, l’entropia sarà inferiore, riflettendo una minore incertezza.

In sintesi, l’entropia \(H(X)\) misura l’incertezza complessiva associata alla distribuzione di probabilità di una variabile casuale discreta \(X\). Essa quantifica la sorpresa media che ci si può aspettare quando si osserva un evento estratto casualmente da questa collezione.

Esempio 72.3 Supponiamo di avere un dado con otto facce. Ci sono \(m = 8\) esiti possibili:

\[ A_x = \{1,2,3,4,5,6,7,8\}. \]

Poiché il dado è equo, tutti gli otto esiti hanno la stessa probabilità di \(p(x) = 1/8\), definendo così una distribuzione di probabilità uniforme:

\[ p(X) = \left\{\frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}\right\}. \]

L’entropia di questa distribuzione può essere calcolata come:

\[ H(X) = - \sum_{i=1}^{8} \frac{1}{8} \log_2 \frac{1}{8} = \log_2 8 = 3 \text{ bit}. \]

Poiché l’informazione associata a ciascun esito è esattamente 3 bit, anche l’entropia media è di 3 bit, che rappresenta l’incertezza complessiva della variabile \(X\).

Dato che \(X\) ha un’entropia di \(H(X) = 3\) bit, possiamo dire che \(X\) può rappresentare fino a:

\[ m = 2^{H(X)} = 2^3 = 8 \]

esiti equiprobabili.

Esempio 72.4 Sia \(X\) una variabile casuale discreta che può assumere i valori \(a, b, c,\) e \(d\) con una distribuzione di probabilità di massa \(p(a) = \frac{1}{2}\), \(p(b) = \frac{1}{4}\), \(p(c) = \frac{1}{8}\), e \(p(d) = \frac{1}{8}\), rispettivamente. L’entropia di \(X\), che misura l’incertezza associata alla distribuzione di probabilità, è calcolata come:

\[ H(X) = -\left(\frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{8} \log_2 \frac{1}{8} + \frac{1}{8} \log_2 \frac{1}{8}\right). \]

Calcolando i singoli termini, otteniamo:

\[ H(X) = -\left(\frac{1}{2} \cdot (-1) + \frac{1}{4} \cdot (-2) + \frac{1}{8} \cdot (-3) + \frac{1}{8} \cdot (-3)\right) = \frac{7}{4} \text{ bits}. \]

È importante notare che l’entropia \(H(X)\) dipende esclusivamente dalla distribuzione di probabilità dei valori di \(X\) e non dai valori stessi.

72.10 Stimare l’Entropia in un Campione di Osservazioni

L’entropia può essere calcolata non solo per distribuzioni teoriche, ma anche per campioni di dati osservati. In questo caso, l’entropia fornisce una misura di quanto la distribuzione dei valori all’interno del campione sia incerta o imprevedibile.

Esempio 72.5 Per comprendere meglio questo concetto, possiamo calcolare l’entropia associata a insiemi di osservazioni. Consideriamo i due vettori seguenti:

\[ \begin{align} x &= \{1, 2, 3, 3, 3, 3, 2, 1, 3, 3, 2, 1, 1, 4, 4, 3, 1, 2\}, \notag\\ y &= \{3, 4, 1, 1, 1, 1, 4, 3, 1, 1, 4, 3, 3, 2, 2, 1, 3, 4\}. \notag \end{align} \]

Troviamo l’entropia associata a ciascuno di essi.

# Vettori x e y
x <- c(1, 2, 3, 3, 3, 3, 2, 1, 3, 3, 2, 1, 1, 4, 4, 3, 1, 2)
y <- c(3, 4, 1, 1, 1, 1, 4, 3, 1, 1, 4, 3, 3, 2, 2, 1, 3, 4)

# Conta le frequenze
x_counts <- table(x)
y_counts <- table(y)

# Calcola le probabilità relative
x_probabilities <- as.numeric(x_counts) / length(x)
y_probabilities <- as.numeric(y_counts) / length(y)

# Funzione per calcolare l'entropia (log in base 2)
calculate_entropy <- function(probabilities) {
  -sum(probabilities * log2(probabilities))
}

# Calcolo dell'entropia
x_entropy <- calculate_entropy(x_probabilities)
y_entropy <- calculate_entropy(y_probabilities)

# Stampa i risultati
cat(sprintf("Entropia di x: %.4f bit\n", x_entropy))
#> Entropia di x: 1.8776 bit
cat(sprintf("Entropia di y: %.4f bit\n", y_entropy))
#> Entropia di y: 1.8776 bit

Entrambi i vettori hanno la stessa entropia di 1.8776 bit.

72.11 Entropia di una Variabile Casuale Continua

Nel caso delle variabili casuali continue, il concetto di entropia viene generalizzato sostituendo la somma con un integrale. Questo è necessario perché le variabili continue possono assumere un numero infinito di valori all’interno di un intervallo.

Per una variabile casuale continua \(X\) con una funzione di densità di probabilità \(p(x)\), l’entropia (nota anche come entropia differenziale) è definita dalla seguente formula:

\[ H(X) = -\int p(x) \log_2(p(x)) \, dx, \]

dove:

• \(p(x)\) è la funzione di densità di probabilità di \(X\),
• l’integrale è calcolato su tutto il dominio di \(X\).

L’entropia di una variabile casuale continua fornisce una misura dell’incertezza o della sorpresa associata alla distribuzione della variabile. Come nel caso discreto, l’entropia continua quantifica l’incertezza associata a \(X\). Una PDF molto concentrata (ad esempio, una distribuzione con picchi stretti) implica bassa entropia, poiché l’evento è più prevedibile. Una PDF distribuita uniformemente implica alta entropia, poiché l’evento è meno prevedibile.

Il segno negativo assicura che l’entropia sia una quantità positiva, in quanto \(\log_2(p(x))\) è negativo per \(p(x)\) compreso tra 0 e 1.

Esempi relativi al calcolo dell’entropia nel caso di variabili continue sono fornite nel ?sec-entropy-rv-cont.

72.12 La codifica di Huffman

Immagina di dover inviare un messaggio usando il minor numero possibile di bit, cioè di 0 e 1. Alcuni simboli (come le lettere A, E, o spazi vuoti) appaiono spesso nei testi, mentre altri (come Z o Q) sono molto rari. Ha senso usare codici più brevi per i simboli più frequenti, e codici più lunghi per quelli rari. Questo è esattamente ciò che fa la codifica di Huffman: costruisce un codice binario che minimizza la lunghezza totale del messaggio, adattandosi alla frequenza dei simboli.

72.12.1 Passaggi per creare una codifica di Huffman

Immaginiamo di avere un messaggio, o un insieme di dati. Prima di tutto, dobbiamo contare quante volte appare ciascun simbolo. Ad esempio:

Simbolo	Frequenza
A	20
B	10
C	8
D	5

Queste frequenze ci dicono quali simboli sono più “comuni”.

Il secondo passo è quello di costruire l’albero di Huffman. In altre parole, usiamo un metodo visivo per costruire una specie di albero genealogico al contrario:

1. creiamo un nodo per ogni simbolo, con la sua frequenza;
2. uniamo i due simboli meno frequenti creando un nuovo nodo; la frequenza del nuovo nodo è la somma delle due;
3. ripetiamo il processo unendo ogni volta i due nodi con frequenza minore, finché non rimane un solo nodo (la radice dell’albero).

Esempio passo-passo con i nostri simboli:

• (D:5) e (C:8) → uniti in (DC:13)
• (B:10) e (DC:13) → uniti in (BDC:23)
• (A:20) e (BDC:23) → uniti in (ABDC:43)

Struttura dell’albero:

       (43)
      /    \
    (20)   (23)
     A     /   \
         (10)  (13)
          B    /  \
              D    C

Ora possiamo assegnare i codici binari:

• ad ogni ramo sinistro mettiamo uno 0;
• ad ogni ramo destro mettiamo un 1;
• il codice di un simbolo è la sequenza di 0 e 1 dal nodo radice fino al simbolo.

Risultati finali:

Simbolo	Codice Huffman
A	0
B	10
D	110
C	111

Notiamo che:

• A, il più frequente, ha il codice più corto (1 bit);
• C e D, i meno frequenti, hanno codici più lunghi (3 bit).

72.12.2 Perché la codifica di Huffman funziona così bene?

• La codifica è senza perdita: possiamo sempre ricostruire il messaggio originale.
• È ottimale: tra tutte le codifiche possibili che usano un numero intero di bit per simbolo, la codifica di Huffman è la più efficiente.
• È una codifica prefissa: nessun codice è l’inizio di un altro. Questo rende la decodifica univoca e automatica.

72.13 L’entropia come lunghezza media del codice binario

L’entropia può essere interpretarla come la quantità media di informazione che riceviamo quando osserviamo il valore di una variabile casuale. In pratica, rappresenta la lunghezza media più breve (in bit) che possiamo usare per codificare gli esiti di quella variabile, tenendo conto delle loro probabilità.

Esempio 72.6 Supponiamo di avere una variabile casuale \(X\) che può assumere quattro valori: \(A\), \(B\), \(C\), e \(D\), con le seguenti probabilità:

• \(p(A) = 0.4\)
• \(p(B) = 0.3\)
• \(p(C) = 0.2\)
• \(p(D) = 0.1\)

Per rappresentare questi esiti con un codice binario efficiente possiamo usare la codifica di Huffman, che assegna codici più brevi ai simboli più probabili, e codici più lunghi a quelli meno probabili.

Supponiamo che Huffman produca la seguente codifica:

• A = 0 (1 bit)
• B = 10 (2 bit)
• C = 110 (3 bit)
• D = 111 (3 bit)

La lunghezza media del codice si ottiene moltiplicando la probabilità di ciascun simbolo per la lunghezza del suo codice binario, e poi sommando:

\[ \begin{align} \text{Lunghezza media} &= (0.4 \times 1) + (0.3 \times 2) + (0.2 \times 3) + (0.1 \times 3) \\ &= 0.4 + 0.6 + 0.6 + 0.3 = 1.9 \text{ bit}. \end{align} \]

Questo significa che, in media, servono 1.9 bit per rappresentare un’osservazione della variabile \(X\) usando la codifica di Huffman.

Confermiamo il risultato con il seguente codice R:

# Definizione delle probabilità
probabilities <- list(A = 0.4, B = 0.3, C = 0.2, D = 0.1)

# Funzione per la codifica di Huffman
huffman_encoding <- function(probabilities) {
  nodes <- lapply(names(probabilities), function(sym) {
    list(symbol = sym, prob = probabilities[[sym]], left = NULL, right = NULL)
  })

  while (length(nodes) > 1) {
    nodes <- nodes[order(sapply(nodes, function(n) n$prob))]
    left <- nodes[[1]]
    right <- nodes[[2]]
    merged <- list(symbol = NULL, prob = left$prob + right$prob, left = left, right = right)
    nodes <- c(nodes[-c(1, 2)], list(merged))
  }

  assign_codes <- function(node, prefix = "", code_map = list()) {
    if (!is.null(node$symbol)) {
      code_map[[node$symbol]] <- prefix
    } else {
      code_map <- assign_codes(node$left, paste0(prefix, "0"), code_map)
      code_map <- assign_codes(node$right, paste0(prefix, "1"), code_map)
    }
    return(code_map)
  }

  code_map <- assign_codes(nodes[[1]])

  avg_length <- sum(sapply(names(probabilities), function(sym) {
    probabilities[[sym]] * nchar(code_map[[sym]])
  }))

  return(list(avg_length = avg_length, huffman_dict = code_map))
}

# Applicazione e stampa dei risultati
result <- huffman_encoding(probabilities)

cat(sprintf("Lunghezza media del codice di Huffman: %.2f bit/simbolo\n", result$avg_length))
#> Lunghezza media del codice di Huffman: 1.90 bit/simbolo
cat("Codici di Huffman:\n")
#> Codici di Huffman:
for (sym in names(result$huffman_dict)) {
  cat(sprintf("%s: %s\n", sym, result$huffman_dict[[sym]]))
}
#> A: 0
#> B: 10
#> D: 110
#> C: 111

Ora calcoliamo l’entropia teorica della variabile \(X\), cioè la lunghezza media minima che qualsiasi codifica binaria può raggiungere:

\[ \begin{align} H(X) &= - \sum p(x) \log_2 p(x) \\ &= -[0.4 \log_2 0.4 + 0.3 \log_2 0.3 + 0.2 \log_2 0.2 + 0.1 \log_2 0.1] \\ &= 1.8465 \text{ bit}. \end{align} \]

Il valore dell’entropia è leggermente inferiore alla lunghezza media di Huffman (1.9 bit). Questo è normale: Huffman fornisce codici con lunghezza intera in bit, mentre l’entropia può assumere valori decimali. La codifica di Huffman è quindi quasi ottimale.

In sintesi:

• l’entropia \(H(X)\) rappresenta la lunghezza media teorica minima (in bit) per codificare una variabile casuale;
• la codifica di Huffman costruisce un codice binario che si avvicina molto a questo limite, usando più bit per i simboli rari e meno bit per quelli frequenti;
• in questo modo, l’entropia ci offre un criterio per valutare quanto efficiente è una codifica: più la lunghezza media si avvicina all’entropia, più è efficiente.

72.14 Applicazioni Psicologiche

Un esempio di applicazione dell’entropia dell’informazione in psicologia riguarda l’effetto della sorpresa nello studio dell’umore. La sorpresa, o entropia, è stata documentata sia in laboratorio che in contesti naturali come un fattore in grado di influenzare le emozioni. Ad esempio, Spector (1956) ha osservato l’effetto della probabilità a priori sulla soddisfazione dei soggetti in risposta a una promozione lavorativa. I risultati indicano che gli esiti meno probabili a priori (e quindi più sorprendenti quando si verificano) hanno un impatto maggiore sull’umore. In altre parole, quando un evento inatteso e sorprendente si verifica, tende a influenzare l’umore in modo più forte rispetto agli eventi previsti e probabili.

72.15 Riflessioni Conclusive

In questo capitolo abbiamo introdotto il concetto di entropia come misura dell’incertezza associata a una variabile casuale. Attraverso esempi concreti – dalla moneta al dado, fino alla codifica di Huffman – abbiamo visto come l’entropia permetta di quantificare la sorpresa media di un sistema, e come questa sorpresa sia strettamente legata alla quantità media di informazione necessaria per rappresentare un evento.

L’entropia non è solo uno strumento astratto, ma un ponte tra la probabilità e la codifica dell’informazione: ci dice quanto ci aspettiamo di “imparare” quando osserviamo un dato, e quanto dovrebbe “costare”, in bit, trasmettere quell’informazione. Nella codifica Huffman, per esempio, abbiamo visto che l’entropia rappresenta un limite inferiore teorico alla lunghezza media di qualsiasi codifica binaria senza perdita.

Questi concetti non sono fini a sé stessi. Servono come fondamenta concettuali per comprendere i criteri di confronto tra modelli probabilistici – e in particolare tra modelli bayesiani. Nei prossimi capitoli estenderemo l’idea di entropia alla divergenza di Kullback-Leibler (KL), che misura quanto una distribuzione di probabilità differisce da un’altra. La divergenza KL sarà fondamentale per definire l’Expected Log Predictive Density (ELPD), una metrica chiave per valutare e confrontare modelli in termini della loro capacità predittiva fuori campione. Il collegamento è il seguente:

• l’entropia misura quanto “impariamo” da una distribuzione nota;
• la divergenza KL misura quanto un modello si discosta da quella distribuzione;
• l’ELPD si basa proprio sulla somma di log-verosimiglianze predittive, valutate su dati non utilizzati per l’adattamento del modello, ed è legato alla minimizzazione della divergenza KL rispetto ai dati generati dal “vero” processo.

Capire l’entropia, quindi, non è solo utile per comprendere la codifica e la compressione: è propedeutico per interpretare correttamente cosa significa che un modello “funziona bene” dal punto di vista dell’informazione.

Concludiamo con una nota filosofica. La celebre osservazione di Eckhardt (2012) ci ricorda che l’informazione non è solo quantità, ma anche qualità:

“…our mind, and even the subconscious self resonate. A poet can recall chains of ideas, emotions and memories with a well-turned word. In this sense, writing is magic.”

Questa immagine della risonanza come effetto dell’informazione sul ricevente ci invita a non ridurre l’informazione al solo contenuto numerico o simbolico. Nei modelli psicologici – specialmente in quelli predittivi – è fondamentale ricordare che l’interpretabilità e il significato dell’informazione dipendono anche dal contesto umano e cognitivo in cui essa è ricevuta. Nel valutare i modelli, dunque, dovremo considerare non solo quanto bene il modello predice, ma anche cosa ci dice sul fenomeno, quanto è interpretabile, e in che misura risuona con le domande psicologiche che ci poniamo.

Informazioni sull’Ambiente di Sviluppo

sessionInfo()
#> R version 4.5.1 (2025-06-13)
#> Platform: aarch64-apple-darwin20
#> Running under: macOS Sequoia 15.6
#> 
#> Matrix products: default
#> BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
#> LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1
#> 
#> locale:
#> [1] C/UTF-8/C/C/C/C
#> 
#> time zone: Europe/Zagreb
#> tzcode source: internal
#> 
#> attached base packages:
#> [1] stats     graphics  grDevices utils     datasets  methods   base     
#> 
#> other attached packages:
#>  [1] tidygraph_1.3.1  ggraph_2.2.1     igraph_2.1.4     thematic_0.1.7  
#>  [5] MetBrewer_0.2.0  ggokabeito_0.1.0 see_0.11.0       gridExtra_2.3   
#>  [9] patchwork_1.3.1  bayesplot_1.13.0 psych_2.5.6      scales_1.4.0    
#> [13] markdown_2.0     knitr_1.50       lubridate_1.9.4  forcats_1.0.0   
#> [17] stringr_1.5.1    dplyr_1.1.4      purrr_1.1.0      readr_2.1.5     
#> [21] tidyr_1.3.1      tibble_3.3.0     ggplot2_3.5.2    tidyverse_2.0.0 
#> [25] rio_1.2.3        here_1.0.1      
#> 
#> loaded via a namespace (and not attached):
#>  [1] gtable_0.3.6       xfun_0.52          htmlwidgets_1.6.4 
#>  [4] ggrepel_0.9.6      lattice_0.22-7     tzdb_0.5.0        
#>  [7] vctrs_0.6.5        tools_4.5.1        generics_0.1.4    
#> [10] parallel_4.5.1     pacman_0.5.1       pkgconfig_2.0.3   
#> [13] RColorBrewer_1.1-3 lifecycle_1.0.4    compiler_4.5.1    
#> [16] farver_2.1.2       mnormt_2.1.1       ggforce_0.5.0     
#> [19] graphlayouts_1.2.2 htmltools_0.5.8.1  yaml_2.3.10       
#> [22] pillar_1.11.0      MASS_7.3-65        cachem_1.1.0      
#> [25] viridis_0.6.5      nlme_3.1-168       tidyselect_1.2.1  
#> [28] digest_0.6.37      stringi_1.8.7      labeling_0.4.3    
#> [31] polyclip_1.10-7    rprojroot_2.1.0    fastmap_1.2.0     
#> [34] grid_4.5.1         cli_3.6.5          magrittr_2.0.3    
#> [37] withr_3.0.2        timechange_0.3.0   rmarkdown_2.29    
#> [40] hms_1.1.3          memoise_2.0.1      evaluate_1.0.4    
#> [43] viridisLite_0.4.2  rlang_1.1.6        Rcpp_1.1.0        
#> [46] glue_1.8.0         tweenr_2.0.3       rstudioapi_0.17.1 
#> [49] jsonlite_2.0.0     R6_2.6.1

Bibliografia

Eckhardt, W. (2012). Paradoxes in probability theory. Springer Science & Business Media.

Spector, A. J. (1956). Expectations, fulfillment, and morale. The Journal of Abnormal and Social Psychology, 52(1), 51–56.

Stone, J. V. (2022). Information theory: a tutorial introduction, 2nd edition.