Il simplesso delle probabilità
Una distribuzione di probabilità su q simboli è un punto nel simplesso (q−1)-dimensionale: l'insieme di tutti i vettori (p₁, ..., p_q) con pᵢ ≥ 0 e Σ pᵢ = 1.
Per q = 2: il simplesso è un segmento di linea [0,1], parametrizzato da una singola probabilità p. Per q = 3: il simplesso è un triangolo equilatero in ℝ². Ogni angolo è una distribuzione deterministica (tutta la probabilità su un simbolo); il centro è la distribuzione uniforme.
L'entropia H(p) assegna un numero reale a ogni punto del simplesso. La geometria della funzione determina molti risultati fondamentali.
Concavità
H è concava sul simplesso: per qualsiasi due distribuzioni p e q e qualsiasi λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Una miscela di due distribuzioni ha entropia almeno pari alla media ponderata delle loro singole entropie. Intuizione: mescolare due sorgenti aumenta l'incertezza.
Verificare la concavità
Per l'entropia binaria H(p), la concavità è visibile nel grafico: la curva si incurva verso l'alto, mai scendendo sotto alcuna corda che colleghi due punti.
Test formale per la concavità: la derivata seconda H''(p) ≤ 0 ovunque.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 for all p ∈ (0,1)
La derivata seconda è strettamente negativa ovunque nell'interno: H è strettamente concava.
La distribuzione che ottiene la capacità
La capacità del canale è definita come l'informazione mutua massima su tutte le distribuzioni di input p(x):
C = max_{p(x)} I(X; Y)
dove I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Per il canale binario simmetrico con probabilità di errore Q: la distribuzione di input che ottiene la capacità è la distribuzione uniforme p(0) = p(1) = 0,5.
Perché: H(Y) è massimizzato dalla distribuzione di output uniforme. Con un BSC, un input uniforme dà un output uniforme. Qualsiasi altra distribuzione di input rende H(Y) più piccolo, riducendo I(X;Y).
Geometricamente: l'informazione mutua I(X;Y) è una funzione concava della distribuzione di input p(x) sul simplesso. Il massimo di una funzione concava su un insieme convesso è raggiunto in un punto unico (il centro, per un canale simmetrico).
La divergenza di Kullback-Leibler
La divergenza di Kullback-Leibler (entropia relativa) dalla distribuzione q alla distribuzione p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 sempre (disuguaglianza di Gibbs). D(p || q) = 0 se e solo se p = q.
D non è una vera distanza: è asimmetrica (D(p||q) ≠ D(q||p) in generale) e non soddisfa la disuguaglianza triangolare. Ma agisce come una misura di quanto 'lontana' p è da q nello spazio delle probabilità.
La divergenza KL appare in tutta la teoria dell'informazione:
- Informazione mutua: I(X;Y) = D(p(x,y) || p(x)p(y)). L'informazione mutua è la divergenza KL tra la distribuzione congiunta e il prodotto dei marginali — quanto la distribuzione congiunta è lontana dall'indipendenza.
- Disuguaglianza di Gibbs: il teorema della codifica senza rumore segue direttamente da D(p || q) ≥ 0.
- Capacità del canale: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Calcolare la divergenza di Kullback-Leibler
Esempio: p = (0,5, 0,5) uniforme binaria, q = (0,8, 0,2) binaria asimmetrica.
D(p || q) = 0,5 log₂(0,5/0,8) + 0,5 log₂(0,5/0,2)
= 0,5 log₂(0,625) + 0,5 log₂(2,5)
≈ 0,5 × (−0,678) + 0,5 × 1,322 ≈ −0,339 + 0,661 ≈ 0,322 bit
La capacità del canale come distanza geometrica
La capacità del canale ha un'interpretazione geometrica nello spazio delle distribuzioni di probabilità.
Per un canale p(y|x), definisci la distribuzione di input che ottiene la capacità p*(x). La capacità soddisfa:
C = D(p*(y) || r(y))
dove p(y) = Σ p(x) p(y|x) è la distribuzione di output sotto l'input ottimale, e r(y) = argmin_r max_x D(p(y|x) || r(y)) è la distribuzione di output a informazione minima — il punto nello spazio delle probabilità di output più vicino (nella divergenza KL) a tutte le distribuzioni condizionate contemporaneamente.
Questo è il punto di vista della geometria dell'informazione: la capacità del canale è il raggio della più piccola palla a divergenza KL nello spazio delle distribuzioni di output che contiene tutte le distribuzioni condizionate p(y|x=0) e p(y|x=1).
Per il BSC: p(y|x=0) = (1−Q, Q) e p(y|x=1) = (Q, 1−Q). Per simmetria, la distribuzione di output a informazione minima r(y) = (0,5, 0,5). Capacità = D((1−Q, Q) || (0,5, 0,5)) = 1 − H(Q). La formula recupera il risultato standard dalla geometria.
Capacità dalla divergenza di Kullback-Leibler
Verifica la formula geometrica: C = D(p(y|x=0) || r(y)) per un BSC con Q = 0,1, r(y) = (0,5, 0,5).
p(y|x=0) = (0,9, 0,1) (invia 0, ricevi 0 con prob 0,9, ricevi 1 con prob 0,1).
D((0,9, 0,1) || (0,5, 0,5)) = 0,9 log₂(0,9/0,5) + 0,1 log₂(0,1/0,5)
= 0,9 log₂(1,8) + 0,1 log₂(0,2)
log₂(1,8) ≈ 0,848, log₂(0,2) ≈ −2,322
= 0,9×0,848 + 0,1×(−2,322) ≈ 0,763 − 0,232 ≈ 0,531 bit
Verifica: C = 1 − H(0,1) ≈ 1 − 0,469 = 0,531 bit ✓
Rate-Distortion & i limiti della compressione
La teoria della compressione con distorsione estende la teoria dell'informazione alla compressione con perdita. Invece di chiedere 'quali sono i bit minimi per rappresentare una sorgente esattamente?' chiede: 'data la tolleranza per una certa distorsione media D, qual è il tasso minimo R(D) bit per simbolo?'
La funzione rate-distortion R(D) è convessa e decrescente in D: più tolleranza per la distorsione permette tassi più bassi. A D = 0 (senza perdita): R(0) = H(sorgente). Man mano che D aumenta, R(D) → 0.
Geometricamente: R(D) traccia una curva sul piano (tasso, distorsione). Ogni coppia (R, D) realizzabile giace sulla o sopra questa curva. I punti sotto la curva sono impossibili — non puoi comprimere al di sotto del limite fondamentale a nessun livello di distorsione.
Il teorema della compressione con distorsione (Shannon, 1959): per ogni R > R(D), i codici che raggiungono la distorsione media attesa D esistono. Per R < R(D): nessun codice raggiunge la distorsione media attesa D. La curva è una frontiera geometrica nello spazio (tasso, distorsione).