Decisione ottima - criteri MAP e ML

Nel capitolo precedente (Spazio dei segnali e Gram-SchmidtNella modulazione digitale ogni simbolo di un alfabeto di $M$ elementi è associato a una forma d'onda $s_j(t)$ di energia finita, trasmessa in un tempo di simbolo $T$. Le forme d'onda sono elementi dello spazio $\mathcal L^2$ con prodotto scalare $\langle x,y\rangle=\int xy^*,dt$ e energia $E_x=\lVert x\rVert^2$; con una base ortonormale ${\varphi_i}_{i=1}^I$ ($I\le M$, trovata con Gram-Schmidt) ogni segnale è un punto $\mathbf s_j=[\langle s_j,\varphi_i\rangle]i$ e l'insieme dei punti è la costellazione. Il rumore bianco gaussiano ha componenti sulla base indipendenti $\mathcal N(0,\frac{N_0}2)$ (la parte fuori dallo spazio dei segnali è irrilevante), quindi il ricevuto è $\mathbf r=\mathbf s_j+\mathbf w$.Spazio dei segnali e Gram-Schmidt →) si è visto che il ricevitore, proiettando $r(t)=s_j(t)+w(t)$ sulla base, ottiene un vettore $\mathbf r=\mathbf s_j+\mathbf w\in\mathbb R^I$ in cui $\mathbf w$ ha componenti indipendenti $\mathcal N\left(0,\frac{N_0}2\right)$. Resta da rispondere alla domanda del demodulatore: dato $\mathbf r$, quale simbolo è stato trasmesso? Versione per Ing. Elettronica: Teoria della decisione - criteri MAP, ML e MDLe regioni di decisione che massimizzano la probabilità di decisione corretta sono $\mathcal R_m={\boldsymbol\rho:\ m=\arg\max_mP_m,p{\mathbf r|m}(\boldsymbol\rho|m)}$: criterio MAP (ottimo). Il criterio ML ignora le probabilità a priori; se i simboli sono equiprobabili coincide con il MAP. Il criterio MD sceglie il punto più vicino, $\hat m=\arg\min_m\lVert\boldsymbol\rho-\mathbf s_m\rVert$; con canale AWGN coincide con il ML. Quindi con simboli equiprobabili e AWGN la distanza minima è ottima; con probabilità diverse le soglie si spostano verso il punto meno probabile.Teoria della decisione - criteri MAP, ML e MD →. L'idea di fondo è un problema di inferenza statistica (test di ipotesi), quello che si risolve con Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →.

1. Il problema di decisione

Non si conosce il vero valore del simbolo trasmesso $a_0\in\{1,\dots,M\}$: si osserva soltanto $\mathbf r$ e si prova a stimare $\hat a_0$. La sorgente è caratterizzata probabilisticamente: per ogni simbolo $j$ si considera la probabilità a priori $$p_j=\text{Prob}\left[a_0=j\right],\qquad\sum_{j=1}^Mp_j=1 .$$ Si assume tacitamente che i simboli successivi $a_0,a_1,\dots$ siano indipendenti e identicamente distribuiti (i.i.d.) con le stesse $p_j$; lo sono davvero come conseguenza di una buona codifica di sorgente (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →), che peraltro li rende anche quasi equiprobabili (ma questo, per ora, non lo si assume).

Se si interpreta come un test di ipotesi (il "problema epistemologico fondamentale" della scienza: scegliere tra possibili spiegazioni): si osserva $\mathbf r$ e si hanno $M$ ipotesi $H_1,\dots,H_M$ ("è stato trasmesso $\mathbf s_1$", "...$\mathbf s_2$", ...).

Regioni di decisione. Una regola di decisione è una partizione dello spazio $\mathbb R^I$ in $M$ regioni di decisione $\mathcal R_1,\dots,\mathcal R_M$: $$\mathcal R_i\cap\mathcal R_j=\emptyset\ (i\ne j),\qquad\bigcup_j\mathcal R_j=\mathbb R^I,\qquad\boxed{\hat a_0=j\ \Longleftrightarrow\ \mathbf r\in\mathcal R_j.}$$ Il ricevitore ottimo è quello che sceglie le regioni in modo da minimizzare la probabilità di sbagliare, cioè da massimizzare la probabilità di decisione corretta $$P[C]=\text{Prob}[a_0=\hat a_0]=\sum_{j=1}^M\text{Prob}\left[a_0=j,\hat a_0=j\right].$$

2. La probabilità di decisione corretta

Si calcola in più passi. Per la regola di Bayes si scrive $\text{Prob}[a_0=j,\hat a_0=j]=\text{Prob}[\hat a_0=j\mid a_0=j]\,p_j$; la prima probabilità, per la regola di decisione, è la probabilità che $\mathbf r$ cada dentro $\mathcal R_j$ quando è stato trasmesso $j$, cioè l'integrale della densità condizionata di $\mathbf r$ su quella regione: $$P[C]=\sum_{j=1}^M\underbrace{\int_{\mathcal R_j}p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,d\boldsymbol\rho}_{\text{Prob}[\mathbf r\in\mathcal R_j\mid a_0=j]}\;p_j=\sum_{j=1}^M\int_{\mathcal R_j}D_j(\boldsymbol\rho)\,d\boldsymbol\rho,\qquad D_j(\boldsymbol\rho)=p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,p_j .$$ Qui $\mathbf r=\mathbf s_j+\mathbf w$ è un vettore aleatorio gaussiano con media $\mathbf s_j$ (diversa da zero!) e componenti indipendenti: $p_{\mathbf r|a_0}(\boldsymbol\rho|j)=(\pi N_0)^{-I/2}e^{-\lVert\boldsymbol\rho-\mathbf s_j\rVert^2/N_0}$ (Spazio dei segnali e Gram-SchmidtNella modulazione digitale ogni simbolo di un alfabeto di $M$ elementi è associato a una forma d'onda $s_j(t)$ di energia finita, trasmessa in un tempo di simbolo $T$. Le forme d'onda sono elementi dello spazio $\mathcal L^2$ con prodotto scalare $\langle x,y\rangle=\int xy^*,dt$ e energia $E_x=\lVert x\rVert^2$; con una base ortonormale ${\varphi_i}_{i=1}^I$ ($I\le M$, trovata con Gram-Schmidt) ogni segnale è un punto $\mathbf s_j=[\langle s_j,\varphi_i\rangle]_i$ e l'insieme dei punti è la costellazione. Il rumore bianco gaussiano ha componenti sulla base indipendenti $\mathcal N(0,\frac{N_0}2)$ (la parte fuori dallo spazio dei segnali è irrilevante), quindi il ricevuto è $\mathbf r=\mathbf s_j+\mathbf w$.Spazio dei segnali e Gram-Schmidt →). Il termine $p_{\mathbf r|a_0}(\boldsymbol\rho|j)$ si chiama verosimiglianza (likelihood); $p_j$ è l'a priori.

Come massimizzare. Ogni regione $\mathcal R_j$ somma i valori di $D_j(\boldsymbol\rho)$ sui punti che le sono assegnati, e ogni punto $\boldsymbol\rho$ deve essere assegnato a una sola regione: il contributo più grande si ottiene assegnandolo a quella per cui $D_j(\boldsymbol\rho)$ è massima. L'unica cosa su cui si può agire è il ricevitore, cioè le regioni.

Si può "vedere" il risultato in dimensione $I=1$. Per tre simboli $s_1,s_2,s_3$ le $D_j(\rho)$ sono tre campane gaussiane, centrate sui punti e di altezza proporzionale a $p_j$. Si decide $\hat a_0=j$ dove la campana $j$ è la più alta: i confini delle regioni sono i punti d'incrocio delle campane, e l'area (colorata) sotto la campana più alta è proprio $P[C]$.

3. Il criterio MAP

Dall'argomento precedente si ricava la regola ottima:

Criterio MAP (maximum a posteriori probability). $$\boxed{\hat a_0=\arg\max_{j}D_j(\boldsymbol\rho)=\arg\max_j\ p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,p_j,\qquad\mathcal R_j=\left\{\boldsymbol\rho:\ j=\arg\max_kD_k(\boldsymbol\rho)\right\}}$$ È il criterio ottimo: massimizza $P[C]$.

Perché si chiama "a posteriori". Per il teorema di Bayes la probabilità del simbolo $j$ dopo aver osservato $\mathbf r=\boldsymbol\rho$ è $$p_{a_0|\mathbf r}(j\mid\boldsymbol\rho)=\frac{p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,p_j}{p_{\mathbf r}(\boldsymbol\rho)}=\frac{D_j(\boldsymbol\rho)}{p_{\mathbf r}(\boldsymbol\rho)}$$ e il denominatore $p_{\mathbf r}(\boldsymbol\rho)$ non dipende da $j$ (è la stessa per ogni ipotesi): massimizzare $D_j$ equivale a massimizzare la probabilità a posteriori. Quindi: a priori $p_j$ = quanto credo nel simbolo prima di misurare; verosimiglianza = quanto la misura è compatibile con quel simbolo; a posteriori = la credenza dopo la misura.

Il MAP richiede però di conoscere le $p_j$ e le verosimiglianze, ed è complicato da realizzare. Si cercano criteri più semplici.

4. Il criterio ML

Quando le probabilità a priori sono tutte uguali, oppure non si conoscono, ha senso usare la sola verosimiglianza.

Criterio ML (maximum likelihood). $$\hat a_0=\arg\max_j\ p_{\mathbf r|a_0}(\boldsymbol\rho\mid j).$$

Per ogni $\boldsymbol\rho$ si calcola la verosimiglianza di ciascuna ipotesi e si prende la più alta: ignora le probabilità a priori.

Teorema. Se i simboli sono equiprobabili ($p_j=\frac1M$) il MAP coincide con il ML (e quindi il ML è ottimo). Dimostrazione: $\arg\max_j\frac1M\,p(\boldsymbol\rho|j)=\arg\max_jp(\boldsymbol\rho|j)$, perché $\frac1M$ è una costante e non cambia dove sta il massimo.

Se i simboli non sono equiprobabili, o le $p_j$ non sono note, il ML è la "migliore opzione disponibile" (ma non l'ottimo).

5. Il criterio MD (minima distanza)

Anche il ML può essere complicato da calcolare; si cerca qualcosa di più semplice e geometrico.

Criterio MD (minimum distance). $$\hat a_0=\arg\min_j\ \text{dist}(\boldsymbol\rho,\mathbf s_j)=\arg\min_j\lVert\boldsymbol\rho-\mathbf s_j\rVert .$$ Si calcola la distanza del punto ricevuto da ciascun punto della costellazione e si sceglie il più vicino.

Funziona se essere vicini equivale a essere verosimili, ed è proprio il caso dei segnali gaussiani:

Teorema. Se il rumore è AWGN, MD coincide con ML. Dimostrazione. La verosimiglianza è $p_{\mathbf r|a_0}(\boldsymbol\rho|j)=(\pi N_0)^{-I/2}\exp\left(-\frac{\lVert\boldsymbol\rho-\mathbf s_j\rVert^2}{N_0}\right)$. Il fattore davanti non dipende da $j$ e l'esponenziale è crescente, quindi massimizzare la verosimiglianza equivale a massimizzare $-\lVert\boldsymbol\rho-\mathbf s_j\rVert^2$, cioè a minimizzare la distanza. $\square$

Conclusione chiave. Se il rumore è AWGN e i simboli sono equiprobabili, il ricevitore a minima distanza è ottimo e anche semplice da realizzare (Ricevitore a minima distanza e filtro adattatoIl ricevitore a minima distanza ottiene $\mathbf r$ proiettando $r(t)$ sulla base, $r_j=\langle r,\varphi_j\rangle$: ogni proiezione è l'uscita, campionata in $t_0$, di un filtro con risposta impulsiva $\psi_j(t)=\varphi_j^(t_0-t)$ (il filtro adattato). Poi calcola le distanze e sceglie il minimo (tipo I, $I$ filtri), oppure usa direttamente i segnali con $\hat a_0=\arg\max_j{\operatorname{Re}\langle r,s_j\rangle-\frac{E_j}2}$ (tipo II, $M$ filtri). Il filtro adattato massimizza l'SNR all'istante di campionamento, con valore massimo $\frac{2E}{N_0}$. Per modulazioni binarie basta un solo filtro e un rivelatore a soglia.Ricevitore a minima distanza e filtro adattato →). È la risposta tipica alla domanda d'esame "quale criterio si usa e tale criterio è ottimo?". Per questo, nel seguito, si assumerà MD e simboli equiprobabili, e si calcoleranno le probabilità d'errore (Probabilità d'errore e funzione QPer due segnali di energie $E_1,E_2$ con coefficiente di correlazione $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_1E_2}}$ la distanza è $d_{12}=\sqrt{E_1+E_2-2\rho\sqrt{E_1E_2}}$ e, con rumore AWGN, simboli equiprobabili e criterio MD, $P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)=Q\left(\sqrt{\frac{E_s(1-\rho)}{N_0}}\right)$ con $\sigma_I^2=\frac{N_0}2$ e $Q$ la coda della gaussiana. Il caso antipodale ($\rho=-1$) dà $Q\left(\sqrt{\frac{2E_s}{N_0}}\right)$, l'ortogonale ($\rho=0$) $Q\left(\sqrt{\frac{E_s}{N_0}}\right)$: 3 dB peggio. Con $M>2$ segnali si usano limiti: $\frac{N^}M Q\left(\frac{d_{min}}{2\sigma_I}\right)\le P[E]\le(M-1)Q\left(\frac{d_{min}}{2\sigma_I}\right)$ (union bound); la probabilità dipende solo da $\frac{E_s}{N_0}$, cioè dall'SNR.Probabilità d'errore e funzione Q →).

6. La forma delle regioni di decisione

Con MD. Il confine tra due punti $\mathbf s_j$ e $\mathbf s_k$ è l'asse del segmento che li unisce (l'iperpiano perpendicolare a metà strada); le regioni sono i poligoni di Voronoi della costellazione.

Con MAP e simboli non equiprobabili. Il confine tra $j$ e $k$ è dove $D_j=D_k$: $$\ln p_j-\frac{\lVert\boldsymbol\rho-\mathbf s_j\rVert^2}{N_0}=\ln p_k-\frac{\lVert\boldsymbol\rho-\mathbf s_k\rVert^2}{N_0}\ \Longrightarrow\ \lVert\boldsymbol\rho-\mathbf s_k\rVert^2-\lVert\boldsymbol\rho-\mathbf s_j\rVert^2=N_0\ln\frac{p_k}{p_j}.$$ Si espandono i quadrati ($\lVert\boldsymbol\rho-\mathbf s\rVert^2=\lVert\boldsymbol\rho\rVert^2-2\langle\boldsymbol\rho,\mathbf s\rangle+\lVert\mathbf s\rVert^2$; il termine $\lVert\boldsymbol\rho\rVert^2$ si cancella): $$\boxed{\langle\boldsymbol\rho,\ \mathbf s_j-\mathbf s_k\rangle=\frac{\lVert\mathbf s_j\rVert^2-\lVert\mathbf s_k\rVert^2}2+\frac{N_0}2\ln\frac{p_k}{p_j}.}$$ È ancora un iperpiano perpendicolare a $\mathbf s_j-\mathbf s_k$, ma non più a metà strada: se $p_k<p_j$ il logaritmo è negativo e il confine si sposta verso il punto meno probabile $\mathbf s_k$, allargando la regione del più probabile.

Soglia in dimensione 1. Con due punti $s_i<s_j$, rumore $\mathcal N(0,\sigma_I^2)$, $\sigma_I^2=\frac{N_0}2$, e probabilità $p_i,p_j$, la formula dà $$\boxed{\rho^*=\frac{s_i+s_j}2+\sigma_I^2\,\frac{\ln\left(p_i/p_j\right)}{s_j-s_i}}$$ e si decide $s_j$ se $\rho>\rho^*$. Se $p_i=p_j$ il secondo termine è nullo e la soglia è a metà (MD); se $p_i>p_j$ la soglia va verso $s_j$ (verso il punto meno probabile). Lo spostamento è tanto maggiore quanto più grande è la varianza del rumore e quanto più vicini sono i due punti.

Esempio numerico. $s_1=0$, $s_2=1$, $\sigma_I=0{,}5$, $p_1=0{,}9$, $p_2=0{,}1$. Con la minima distanza (soglia $0{,}5$): $P[E]=0{,}9\,Q\left(\frac{0{,}5}{0{,}5}\right)+0{,}1\,Q(1)=Q(1)=0{,}159$ (con $Q$ la funzione Q, vedi Probabilità d'errore e funzione QPer due segnali di energie $E_1,E_2$ con coefficiente di correlazione $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_1E_2}}$ la distanza è $d_{12}=\sqrt{E_1+E_2-2\rho\sqrt{E_1E_2}}$ e, con rumore AWGN, simboli equiprobabili e criterio MD, $P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)=Q\left(\sqrt{\frac{E_s(1-\rho)}{N_0}}\right)$ con $\sigma_I^2=\frac{N_0}2$ e $Q$ la coda della gaussiana. Il caso antipodale ($\rho=-1$) dà $Q\left(\sqrt{\frac{2E_s}{N_0}}\right)$, l'ortogonale ($\rho=0$) $Q\left(\sqrt{\frac{E_s}{N_0}}\right)$: 3 dB peggio. Con $M>2$ segnali si usano limiti: $\frac{N^*}M Q\left(\frac{d_{min}}{2\sigma_I}\right)\le P[E]\le(M-1)Q\left(\frac{d_{min}}{2\sigma_I}\right)$ (union bound); la probabilità dipende solo da $\frac{E_s}{N_0}$, cioè dall'SNR.Probabilità d'errore e funzione Q →). Con il MAP: $\rho^*=0{,}5+0{,}25\ln9=1{,}049$ e $$P[E]=0{,}9\,Q\left(\frac{1{,}049}{0{,}5}\right)+0{,}1\left[1-Q\left(\frac{1{,}049-1}{0{,}5}\right)\right]=0{,}9\cdot0{,}0179+0{,}1\cdot0{,}539=0{,}070 .$$ Il MAP più che dimezza l'errore (da $0{,}159$ a $0{,}070$). Per esempio con $\rho=0{,}8$: ML e MD scelgono $s_2$ (è più vicino: $p(0{,}8|s_2)=0{,}74>p(0{,}8|s_1)=0{,}22$), ma il MAP sceglie $s_1$, perché $D_1=0{,}9\cdot0{,}22=0{,}20>D_2=0{,}1\cdot0{,}74=0{,}074$: il simbolo $s_1$ è a priori molto più probabile.

(Le costanti $0{,}7181$ e $0{,}0798$ sono $\frac{0{,}9}{\sqrt{2\pi}\,0{,}5}$ e $\frac{0{,}1}{\sqrt{2\pi}\,0{,}5}$, e $\frac1{2\sigma_I^2}=2$.)

Esempio in due dimensioni. Tre punti $\mathbf s_1=(0,0)$, $\mathbf s_2=(2,0)$, $\mathbf s_3=(1,\sqrt3)$ (triangolo equilatero di lato $2$), canale AWGN e simboli equiprobabili: il criterio ottimo è MD e le regioni sono tre settori da $120^\circ$ delimitati dagli assi dei lati, che si incontrano nel baricentro $\left(1,\frac1{\sqrt3}\right)$. Se $p_1$ cresce, il punto d'incontro si sposta verso gli altri due simboli e $\mathcal R_1$ si allarga.

7. Un esempio "della vita reale": dove MAP e ML dividono

Un ingegnere trascorre la notte del 14 febbraio con la compagna e le prepara un regalo di valore $r$. La variabile $r$ ha media $s_a$ che dipende dallo stato di coscienza $a\in\{0,1\}$ ($0$ = coscienza pulita, $1$ = colpevole): $s_0=50$, $s_1=150$. Si sa che le probabilità a priori sono $p_0=0{,}9$ e $p_1=0{,}1$. Il valore dipende anche da un'incertezza $w$ gaussiana a media nulla e varianza $\sigma_w^2=1600$: $r=s_a+w$. La compagna scarta il regalo e vede $r=125$. Che cosa deduce?

• MD: $\text{dist}(r,s_0)=75>\text{dist}(r,s_1)=25\Rightarrow$ "coscienza sporca".
• ML (il rumore è AWGN, quindi uguale a MD): stessa deduzione. Verosimiglianze: $p(r|0)\propto e^{-75^2/3200}=e^{-1{,}76}=0{,}172$, $p(r|1)\propto e^{-25^2/3200}=e^{-0{,}195}=0{,}823$.
• MAP: si pesano le verosimiglianze con le a priori: $D_0\propto0{,}9\cdot0{,}172=0{,}155>D_1\propto0{,}1\cdot0{,}823=0{,}082$. In termini di logaritmi: $-0{,}105-1{,}758=-1{,}86>-2{,}30-0{,}195=-2{,}50$. Il MAP conclude "coscienza pulita": il regalo è troppo costoso per essere sospetto, ma soprattutto la colpa è rara.

MAP, ML e MD portano a risultati diversi perché i simboli non sono equiprobabili ($p_0\ne p_1$); in questo caso solo il MAP è il criterio ottimo. (Lo stesso accade nell'esempio medico dell'Esercizio - diagnosi con MAP, ML e minima distanza, con distribuzioni di Poisson.) Va ricordato che il MAP massimizza la probabilità di decisione corretta: se i due errori hanno "costi" diversi (un falso negativo in un test clinico) il criterio va scelto in base a ciò che interessa davvero.

Errori comuni

• Usare MD con simboli non equiprobabili e dire che è ottimo: lo è solo con equiprobabilità e rumore AWGN.
• Spostare la soglia MAP dalla parte sbagliata: si sposta verso il simbolo meno probabile (la regione del più probabile si allarga).
• Confondere $\sigma_I^2=\frac{N_0}2$ con $N_0$ nella soglia $\rho^*=\frac{s_i+s_j}2+\sigma_I^2\frac{\ln(p_i/p_j)}{s_j-s_i}$.
• Dire che MD $=$ ML sempre: vale solo con rumore AWGN (con verosimiglianze non gaussiane, come Poisson, i due criteri differiscono).
• Dimenticare che il denominatore $p_{\mathbf r}(\boldsymbol\rho)$ di Bayes non conta nel $\arg\max$.