01 - Entropia di Shannon

Quanti bit servono, in media, per dire a qualcuno quale esito di un esperimento casuale si è verificato? Dipende da quanto l'esito era prevedibile: se so già che uscirà testa, non devo dirti nulla; se la moneta è equa, mi serve esattamente un bit.

L'entropia di Shannon mette questo ragionamento in una formula: per una sorgente che produce il simbolo x con probabilità p(x), vale H(X) = Σ p(x) · log₂(1/p(x)) bit, la media della «sorpresa» log₂(1/p(x)) di ogni esito. Per la moneta equa fa 1 bit, per una moneta che esce testa il 90% delle volte fa 0,469 bit, per un esito certo fa zero.

Questo articolo costruisce la definizione, la mette alla prova su numeri, ne ricava l'entropia congiunta e condizionata con la regola della catena, e chiude con due trappole che le formule da sole non mostrano: la stima dai dati e l'entropia dei numeri reali.

Ogni listato è stato eseguito due volte con uscita identica, con Python 3.14.4, numpy 2.3.5, scipy 1.16.3 e sympy 1.14.0, senza rete e con semi fissi per i numeri casuali. Le formule di Shannon sono controllate sul testo originale (A Mathematical Theory of Communication) e sul libro di MacKay, indicati in fondo.

La sorpresa di un evento e la sua media

Un evento di probabilità 1/8 ti sorprende più di uno di probabilità 1/2, e ha senso misurare la sorpresa con il numero di domande sì/no che servono per identificarlo: tre per 1/8 (è la metà sinistra? la metà sinistra di quella? ...), una per 1/2.

Questa è la quantità log₂(1/p), che con base 2 si misura in bit: Shannon attribuisce il nome a J. W. Tukey nell'introduzione dell'articolo. Con il logaritmo naturale l'unità è il nat, e 1 nat vale 1/ln 2 ≈ 1,4427 bit: cambiare base cambia solo una costante, e questo articolo usa sempre i bit.

L'entropia è il valore atteso della sorpresa: ogni esito contribuisce con la propria sorpresa, pesata con la frequenza con cui accade. Il listato la calcola per cinque sorgenti.

La riga con if x > 0 implementa la convenzione 0·log 0 = 0: è la convenzione giusta perché x·log x tende a zero quando x tende a zero, e senza quell'if un esito impossibile produrrebbe un errore di dominio. Scrivere log2(1/x) invece di -x * log2(x) evita che l'esito certo stampi il fastidioso «-0.0000».

Il secondo calcolo, indipendente, rifà i conti con frazioni esatte e logaritmi simbolici di sympy, e lo scarto massimo fra i due è dell'ordine dell'errore di arrotondamento.

from math import log2
import sympy as sp


def entropia(p):
    """Entropia di Shannon in bit; la convenzione 0·log 0 = 0 è l'if."""
    return sum(x * log2(1 / x) for x in p if x > 0)


casi = {
    "moneta equa": [0.5, 0.5],
    "moneta 90-10": [0.9, 0.1],
    "dado a tre facce": [1 / 3] * 3,
    "esito certo": [1.0, 0.0],
    "cinque articoli": [0.4, 0.25, 0.2, 0.1, 0.05],
}
for nome, p in casi.items():
    print(f"{nome:17s} {entropia(p):.4f} bit")

# secondo calcolo, indipendente: frazioni esatte e logaritmi simbolici di sympy
R = sp.Rational
esatti = [
    [R(1, 2), R(1, 2)],
    [R(9, 10), R(1, 10)],
    [R(1, 3)] * 3,
    [R(2, 5), R(1, 4), R(1, 5), R(1, 10), R(1, 20)],
]
numerici = [casi[k] for k in ("moneta equa", "moneta 90-10", "dado a tre facce", "cinque articoli")]
scarto = max(
    abs(float(sp.N(sum(q * sp.log(1 / q, 2) for q in pe), 30)) - entropia(pn))
    for pe, pn in zip(esatti, numerici)
)
print(f"scarto massimo fra i due calcoli: {scarto:.1e}")

# Output:
# moneta equa       1.0000 bit
# moneta 90-10      0.4690 bit
# dado a tre facce  1.5850 bit
# esito certo       0.0000 bit
# cinque articoli   2.0414 bit
# scarto massimo fra i due calcoli: 4.4e-16

La moneta al 90% ha entropia 0,469 bit: quasi la metà di quella equa, perché solo un lancio su dieci ti sorprende. Il dado a tre facce vale log₂ 3 ≈ 1,585 bit, il massimo possibile con tre esiti.

La quinta riga riguarda una distribuzione inventata per l'esempio (cinque articoli italiani con le frequenze 0,40, 0,25, 0,20, 0,10 e 0,05; non è una misura su un corpus reale): dà 2,0414 bit, fra zero e il massimo log₂ 5 = 2,3219, perché la distribuzione è sbilanciata ma non concentrata su un esito solo.

Perché proprio questa formula

La scelta di Shannon non è arbitraria, ma nemmeno obbligata, e l'articolo originale lo dice con onestà. Nella sezione 6, «Choice, uncertainty and entropy», chiede che una misura H(p₁, ..., p_n) di «incertezza» abbia tre proprietà, elencate qui in forma abbreviata.

• Continuità: H è una funzione continua delle probabilità.
• Monotonia sull'uniforme: se tutti gli n esiti sono equiprobabili, H cresce con n (più scelta, più incertezza).
• Scomposizione: se una scelta si spezza in due scelte successive, l'H originale è la somma pesata delle H delle parti.

Il teorema 2 dell'articolo afferma che l'unica H con queste tre proprietà ha la forma −K Σ p_i log p_i, con K costante positiva che fissa l'unità di misura. Sono tre, e non quattro: la simmetria per permutazione e il massimo sull'uniforme discendono dalla forma trovata, non sono ipotesi.

Subito dopo, Shannon scrive che il teorema e le ipotesi su cui poggia non sono in alcun modo necessari alla teoria e servono a rendere plausibili le definizioni: la giustificazione vera sta nelle loro conseguenze, cioè nei teoremi di codifica degli articoli successivi. Osserva anche che la forma coincide con quella dell'entropia della meccanica statistica, quella del teorema H di Boltzmann, ma la introduce partendo dalla comunicazione e non dalla fisica.

La terza proprietà si controlla sull'esempio dell'articolo stesso, con tre esiti di probabilità 1/2, 1/3 e 1/6: scegliere fra tre equivale a scegliere prima fra due esiti equiprobabili e, se esce il secondo (metà delle volte), scegliere fra due esiti con probabilità 2/3 e 1/3.

La prima parte del listato seguente verifica in modo esatto con sympy che H(1/2, 1/3, 1/6) = H(1/2, 1/2) + ½ · H(2/3, 1/3).

Le altre due parti provano numericamente proprietà che ricorreranno: su 100.000 distribuzioni casuali con 2-8 esiti l'entropia non esce mai dall'intervallo [0, log₂ n], e rispetta la concavità H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q), cioè mescolare due distribuzioni non diminuisce mai l'incertezza media. Le distribuzioni sono estratte da una Dirichlet a parametri 1 con seme 2026; il margine minimo osservato è positivo, 7·10⁻¹¹ bit. Non è una dimostrazione, ma qualunque errore di segno nelle formule l'avrebbe fatta fallire subito.

import numpy as np
import sympy as sp
from math import log2

R = sp.Rational
# La terza ipotesi di Shannon nel suo esempio: H(1/2,1/3,1/6) = H(1/2,1/2) + 1/2 H(2/3,1/3)
H = lambda p: -sum(q * sp.log(q, 2) for q in p)
sinistra = H([R(1, 2), R(1, 3), R(1, 6)])
destra = H([R(1, 2), R(1, 2)]) + R(1, 2) * H([R(2, 3), R(1, 3)])
print("raggruppamento esatto:", sp.simplify(sinistra - destra) == 0)

rng = np.random.default_rng(2026)


def ent(p):
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum())


viol_limiti = viol_conc = 0
margine_min = np.inf
for _ in range(100_000):
    n = int(rng.integers(2, 9))
    p, q = rng.dirichlet(np.ones(n)), rng.dirichlet(np.ones(n))
    lam = rng.random()
    h = ent(p)
    viol_limiti += not (-1e-12 <= h <= log2(n) + 1e-12)
    gap = ent(lam * p + (1 - lam) * q) - (lam * h + (1 - lam) * ent(q))
    margine_min = min(margine_min, gap)
    viol_conc += gap < -1e-12
print("violazioni 0 <= H <= log2 n:", viol_limiti, "su 100000")
print("violazioni della concavità: ", viol_conc, "su 100000")
print(f"margine minimo di concavità: {margine_min:.2e} bit")

# regola della catena su 20000 congiunte casuali 3x4
massimo = 0.0
for _ in range(20_000):
    J = rng.dirichlet(np.ones(12)).reshape(3, 4)
    px = J.sum(axis=1)
    h_y_dato_x = sum(px[i] * ent(J[i] / px[i]) for i in range(3))
    massimo = max(massimo, abs(ent(J.ravel()) - ent(px) - h_y_dato_x))
print(f"scarto massimo della regola della catena: {massimo:.1e} bit")

# Output:
# raggruppamento esatto: True
# violazioni 0 <= H <= log2 n: 0 su 100000
# violazioni della concavità:  0 su 100000
# margine minimo di concavità: 6.82e-11 bit
# scarto massimo della regola della catena: 1.3e-15 bit

Entropia congiunta, condizionata e regola della catena

Con due variabili casuali, l'entropia congiunta H(X, Y) è l'entropia della coppia, calcolata su p(x, y). L'entropia condizionata H(Y|X) è l'incertezza che resta su Y quando X è noto, mediata su tutti i valori di X: H(Y|X) = Σ_x p(x) · H(Y|X=x).

La regola della catena dice che l'incertezza della coppia è quella del primo elemento più quella del secondo dato il primo: H(X, Y) = H(X) + H(Y|X), ed è simmetrica scambiando i ruoli.

La dimostrazione è di tre passaggi. Dalla definizione di probabilità condizionata, p(x, y) = p(x) · p(y|x), e il logaritmo del prodotto è la somma dei logaritmi: −Σ p(x, y) log p(x, y) si spezza in −Σ p(x, y) log p(x) e −Σ p(x, y) log p(y|x).

Nel primo termine il logaritmo non dipende da y, quindi sommando su y resta Σ_x p(x) log p(x), cioè H(X). Il secondo termine è, per definizione, H(Y|X).

Per tre variabili si applica la regola due volte, e in generale H(X₁, ..., X_n) è la somma delle entropie di ogni variabile dato tutto ciò che la precede.

Il listato prova la regola su una congiunta piccola: due parole di un testo immaginario, il soggetto (gatto o cane) e il verbo (corre o dorme), con le probabilità 0,4, 0,1, 0,3 e 0,2 scelte per l'esempio. H(Y|X) è calcolata due volte: dalla definizione (media pesata delle entropie delle condizionate, stampate una per una) e come differenza H(X, Y) − H(X).

from math import log2

joint = {
    ("gatto", "corre"): 0.4, ("gatto", "dorme"): 0.1,
    ("cane", "corre"): 0.3, ("cane", "dorme"): 0.2,
}


def H(ps):
    return -sum(p * log2(p) for p in ps if p > 0)


px, py = {}, {}
for (x, y), p in joint.items():
    px[x] = px.get(x, 0) + p
    py[y] = py.get(y, 0) + p

H_x, H_y, H_xy = H(px.values()), H(py.values()), H(joint.values())

# H(Y|X) dalla definizione: media, pesata con p(x), delle entropie di p(y|x)
H_y_dato_x = 0.0
for x in px:
    h = H([joint[(x, y)] / px[x] for y in py])
    print(f"H(Y|X={x}) = {h:.4f} bit")
    H_y_dato_x += px[x] * h

print(f"H(X)={H_x:.4f}  H(Y)={H_y:.4f}  H(X,Y)={H_xy:.4f}")
print(f"H(Y|X) dalla definizione      = {H_y_dato_x:.4f}")
print(f"H(X,Y) - H(X) (regola catena) = {H_xy - H_x:.4f}")

H_x_dato_y = sum(
    py[y] * H([joint[(x, y)] / py[y] for x in px]) for y in py
)
print(f"H(X|Y) = {H_x_dato_y:.4f}   H(X,Y) - H(Y) = {H_xy - H_y:.4f}")

# Output:
# H(Y|X=gatto) = 0.7219 bit
# H(Y|X=cane) = 0.9710 bit
# H(X)=1.0000  H(Y)=0.8813  H(X,Y)=1.8464
# H(Y|X) dalla definizione      = 0.8464
# H(X,Y) - H(X) (regola catena) = 0.8464
# H(X|Y) = 0.9651   H(X,Y) - H(Y) = 0.9651

I due modi danno 0,8464 bit, e lo stesso vale per H(X|Y) = 0,9651.

Guarda le due righe sulle condizionate per valore: se il soggetto è «gatto» l'incertezza sul verbo scende a 0,7219 bit, ma se è «cane» sale a 0,9710, più dei 0,8813 bit di H(Y) senza condizione. Conoscere un valore specifico di X può quindi aumentare l'incertezza su Y. Ciò che non può mai fare è aumentarla in media: H(Y|X) ≤ H(Y), qui 0,8464 contro 0,8813, con uguaglianza solo se X e Y sono indipendenti.

Il guadagno medio, 0,0349 bit, è l'informazione mutua di cui si occupa l'articolo 02 della serie. La terza parte del listato delle proprietà, qui sopra, ha verificato la regola della catena su 20.000 congiunte casuali 3×4 (scarto massimo 1,3·10⁻¹⁵ bit, cioè arrotondamento).

Che cosa dice l'entropia, e che cosa no

Le proprietà che servono davvero sono quattro, e l'ordine in cui le elenchi non cambia il senso.

• H(X) ≥ 0, con uguaglianza solo se un esito ha probabilità 1 (è la proprietà 1 dell'articolo di Shannon).
• H(X) ≤ log₂ |X|, con uguaglianza solo se gli esiti sono equiprobabili: 3 bit per otto simboli, al massimo.
• L'entropia è una funzione concava delle probabilità, come verificato sopra.
• Se X e Y sono indipendenti, H(X, Y) = H(X) + H(Y): è la regola della catena con H(Y|X) = H(Y).

La prima e la seconda sono i due estremi che servono nel confronto con i codici: l'entropia è il costo minimo medio di descrizione, e non ha senso aspettarsi di scendere sotto zero né di superare log₂ |X|, perché con simboli equiprobabili un codice a lunghezza fissa è già ottimo.

Una cosa che l'entropia non dice è quanto sia «informativo» un singolo messaggio nel senso di significato: misura solo l'imprevedibilità statistica della sorgente, e per questo il suo valore dipende dal modello probabilistico che le attribuisci, non dai dati in sé.

Stimare l'entropia dai dati: la stima è distorta

In pratica le probabilità non si conoscono, si stimano dalle frequenze. Sostituire le probabilità con le frequenze osservate è l'approccio ovvio, detto stimatore plug-in, e ha un difetto sistematico: in media sottostima l'entropia, perché la frequenza osservata ha come media la probabilità vera, l'entropia è concava, e per la disuguaglianza di Jensen la media dell'entropia delle frequenze non supera l'entropia della media. Il listato lo misura su una moneta con p = (0,7, 0,3), la cui entropia vera è 0,8813 bit, estraendo 4000 campioni per ognuna delle quattro dimensioni n e riportando la media delle stime con il suo errore standard.

import numpy as np
from math import log, log2

rng = np.random.default_rng(12345)
p = np.array([0.7, 0.3])
vera = float(-(p * np.log2(p)).sum())
print(f"entropia vera: {vera:.4f} bit")
print("      n   stima media   errore std.   distorsione   teoria -(k-1)/(2n ln2)")
for n in (10, 100, 1000, 10000):
    stime = []
    for _ in range(4000):
        c = np.bincount(rng.choice(2, size=n, p=p), minlength=2) / n
        c = c[c > 0]
        stime.append(float(-(c * np.log2(c)).sum()))
    s = np.array(stime)
    err = s.std(ddof=1) / np.sqrt(len(s))
    print(f"{n:7d}   {s.mean():.4f}      {err:.4f}        {s.mean() - vera:+.4f}       {-1 / (2 * n * log(2)):+.4f}")

# Output:
# entropia vera: 0.8813 bit
#       n   stima media   errore std.   distorsione   teoria -(k-1)/(2n ln2)
#      10   0.8033      0.0033        -0.0780       -0.0721
#     100   0.8738      0.0009        -0.0075       -0.0072
#    1000   0.8811      0.0003        -0.0002       -0.0007
#   10000   0.8812      0.0001        -0.0000       -0.0001

Con 10 estrazioni la stima media è 0,8033: sbaglia di 0,078 bit, quasi il 9% del valore. Con 100 estrazioni la distorsione scende a −0,0075, con 1000 è dell'ordine dell'errore (−0,0002 ± 0,0003) e con 10.000 sparisce.

L'ultima colonna è la correzione di primo ordine −(k−1)/(2n ln 2), con k il numero di esiti: l'ho usata come ordine di grandezza e non l'ho dimostrata qui; coincide con la misura per n = 100, per n = 1000 resta entro due errori standard e per n = 10 la sottostima di poco (−0,072 contro −0,078), perché con così pochi dati l'approssimazione non regge.

La lezione pratica vale per tutto ciò che stima entropie, informazioni mutue o divergenze da conteggi: con pochi dati e molti simboli il numero ottenuto è sistematicamente troppo basso, e un confronto fra campioni di dimensione diversa è falsato.

L'entropia dei numeri reali può essere negativa

Per una variabile continua con densità f(x) si definisce l'entropia differenziale h(X) = −∫ f(x) log₂ f(x) dx. Non è l'estensione naturale dell'entropia discreta, e il segno ne è la prova: per la gaussiana di varianza σ² vale ½ log₂(2πeσ²), e con σ = 0,01 il logaritmo contiene un numero minore di 1, per cui h è negativa.

Il listato calcola quel valore in tre modi (formula chiusa, la funzione entropy di scipy.stats, integrale numerico con quad) e poi discretizza la stessa gaussiana in celle di larghezza Δ per vedere che cosa succede all'entropia discreta.

import numpy as np
from math import log2, pi, e
from scipy import integrate, stats

sigma = 0.01
chiusa = 0.5 * log2(2 * pi * e * sigma**2)                  # formula chiusa, in bit
scipy_ = stats.norm(0, sigma).entropy() / np.log(2)          # libreria (restituisce nat)
f = lambda x: stats.norm.pdf(x, 0, sigma)
numerica, _ = integrate.quad(lambda x: -f(x) * np.log2(f(x)), -10 * sigma, 10 * sigma, points=[0])
print(f"h(N(0, 0.01^2)): chiusa {chiusa:.4f}  scipy {scipy_:.4f}  integrale {numerica:.4f} bit")

# stessa gaussiana, discretizzata in celle larghe delta: l'entropia è discreta, e positiva
for delta in (1e-2, 1e-3, 1e-4):
    bordi = np.arange(-10 * sigma, 10 * sigma + delta, delta)
    p = np.diff(stats.norm.cdf(bordi, 0, sigma))
    p = p[p > 0]
    H_disc = float(-(p * np.log2(p)).sum())
    print(f"delta={delta:g}: H discreta {H_disc:8.4f}   h - log2(delta) = {chiusa - log2(delta):8.4f}")

# cambiare unità di misura (x -> a·x) somma log2(a) all'entropia differenziale
print("h con sigma 0.01:", round(chiusa, 4), "  h con sigma 10 (a = 1000):",
      round(0.5 * log2(2 * pi * e * 10.0**2), 4), "  differenza:", round(log2(1000), 4))

# Output:
# h(N(0, 0.01^2)): chiusa -4.5968  scipy -4.5968  integrale -4.5968 bit
# delta=0.01: H discreta   2.1048   h - log2(delta) =   2.0471
# delta=0.001: H discreta   5.3696   h - log2(delta) =   5.3690
# delta=0.0001: H discreta   8.6910   h - log2(delta) =   8.6910
# h con sigma 0.01: -4.5968   h con sigma 10 (a = 1000): 5.369   differenza: 9.9658

I tre calcoli danno −4,5968 bit.

Il motivo del segno è che f(x) è una densità e può superare 1: una gaussiana stretta ha picco 40, e log₂ 40 è positivo, quindi il suo contributo all'integrale è negativo.

Le righe con la discretizzazione mostrano che cosa h misura davvero: l'entropia discreta delle celle è positiva e cresce di un bit ogni volta che le celle si dimezzano, ed è vicina a h − log₂ Δ (5,3696 contro 5,3690 per Δ = 0,001, e 8,6910 in entrambi i calcoli per Δ = 0,0001; per Δ = 0,01 la cella è larga come σ e la differenza sale a 0,06 bit).

Cambiare unità di misura moltiplica x per a e somma log₂ a a h: portare σ da 0,01 a 10 fa passare da −4,5968 a 5,3690, con differenza 9,9658 = log₂ 1000. Per questo h ha senso soprattutto in differenza: h(X) e h(X|Y) cambiano della stessa costante e l'informazione mutua, che le sottrae, non dipende dall'unità. Per descrivere un segnale reale in bit lo si discretizza e si dichiara la larghezza delle celle.

Errori tipici

• Dire che un simbolo «costa» H(X) bit. H è una media: un simbolo raro costa molti bit (log₂(1/p)), uno frequente pochi.
• Confrontare entropie in basi diverse. 0,693 nat sono 1 bit: se due numeri non coincidono, controlla prima l'unità.
• Stimare l'entropia su pochi dati e fidarsi. Con la distorsione sopra, un valore piccolo può essere il segno di un campione piccolo.
• Dimenticare che dipende dal modello. L'entropia di un testo è diversa se i simboli sono lettere, parole o coppie di lettere: l'incertezza è della sorgente come l'hai descritta.

Il terzo errore è quello che il codice non segnala: nessuna eccezione avverte che il numero è troppo basso, e il valore sembra plausibile. Gli altri si evitano con la disciplina delle unità e della definizione del problema. Tutti discendono dalla stessa idea: l'entropia è una proprietà di una distribuzione di probabilità, non di un messaggio.

Che cosa sai fare adesso

Sai calcolare l'entropia di una distribuzione e verificarla con un secondo calcolo, sai dire quali tre proprietà la determinano e perché Shannon stesso le considera una giustificazione di plausibilità, sai dimostrare la regola della catena e usarla per calcolare H(Y|X) senza partire dalla definizione, e sai riconoscere che condizionare su un valore può aumentare l'incertezza mentre in media non può. Sai anche che stimare un'entropia dai conteggi è distorto per campioni piccoli, e che quella dei numeri reali può essere negativa senza contraddizioni.

Il passo seguente è misurare quanta incertezza due variabili condividono, e quanto una distribuzione ne approssima un'altra: l'articolo 02 della serie definisce informazione mutua e divergenza di Kullback-Leibler. L'elenco di tutti gli articoli è nella pagina della serie; per la probabilità condizionata e le distribuzioni discrete, il prerequisito è Variabili aleatorie discrete.

Più avanti nella serie trovi anche l'articolo 04 sul canale rumoroso, l'articolo 05 sui codici correttori e l'articolo 06 sulla compressione con perdita.