Teoria della decisione - criteri MAP, ML e MD

La probabilità di decisione corretta

Il ricevitore osserva $\mathbf r$ e deve scegliere un simbolo. Con $\hat b$ la decisione e $b$ il simbolo trasmesso, ci sono due eventi: decisione corretta $C=\{\hat b=b\}$ ed errore $E$, con $P[E]=1-P[C]$. Come visto in Il rumore AWGN nello spazio dei segnaliIl ricevitore vede solo la componente del rumore nello spazio dei segnali: $w_i=\langle w,\phi_i\rangle$. Per un rumore bianco gaussiano le $w_i$ sono gaussiane a media nulla, scorrelate (quindi indipendenti) e con la stessa varianza $\sigma_I^2=\frac{N_0}2$, qualunque sia la base ortonormale. Il vettore ricevuto $\mathbf r=\mathbf s_m+\mathbf w$ ha densità condizionata $p_{\mathbf r|m}(\boldsymbol\rho|m)=\left(\pi N_0\right)^{-I/2}e^{-\lVert\boldsymbol\rho-\mathbf s_m\rVert^2/N_0}$: il rumore sposta il punto trasmesso in modo circolare.Il rumore AWGN nello spazio dei segnali →: $$P[C]=\sum_m\int_{\mathcal R_m}D(\boldsymbol\rho;m)\,d\boldsymbol\rho,\qquad D(\boldsymbol\rho;m)=P_m\,p_{\mathbf r|m}(\boldsymbol\rho\mid m),$$ con $P_m=P[b=b_m]$ la probabilità a priori e $p_{\mathbf r|m}$ la verosimiglianzadensità di probabilità del segnale ricevuto, dato il simbolo trasmesso. La somma degli integrali è massima se, in ogni punto $\boldsymbol\rho$, lo si assegna alla regione il cui $D$ è il più alto. Per rendere $P[C]$ più grande l'unica cosa su cui si può agire è il ricevitore, cioè le regioni.

Criterio MAP (massimo a posteriori)

$$\boxed{\mathcal R_m=\left\{\boldsymbol\rho\in\mathbb R^I\ \Big|\ m=\arg\max_{m'}D(\boldsymbol\rho;m')\right\}}$$ Perché si chiama a posteriori: per il teorema di Bayes la probabilità del simbolo $b_m$ dopo aver osservato $\mathbf r=\boldsymbol\rho$ è $$P\left[b=b_m\mid\mathbf r=\boldsymbol\rho\right]=\frac{p_{\mathbf r|m}(\boldsymbol\rho|m)\,P_m}{p_{\mathbf r}(\boldsymbol\rho)}=\frac{D(\boldsymbol\rho;m)}{p_{\mathbf r}(\boldsymbol\rho)}$$ e il denominatore non dipende da $m$: massimizzare $D$ equivale a massimizzare la probabilità a posterioriprobabilità del simbolo dopo avere osservato il segnale ricevuto (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 →). Il MAP è per costruzione il criterio ottimo: massimizza $P[C]$. Ma richiede di conoscere le probabilità a prioriprobabilità che il simbolo sia trasmesso, prima di osservare il segnale ed è complicato da implementare. Si guardano quindi criteri più semplici.

Criterio ML (massima verosimiglianza)

Idea: l'ipotesi vera è la più verosimile. $$\hat m=\arg\max_mp_{\mathbf r|m}(\boldsymbol\rho\mid m).$$ Per ogni realizzazione $\boldsymbol\rho$ si considerano le $M$ ipotesi $H_0,\dots,H_{M-1}$, si calcola $p_{\mathbf r|m}(\boldsymbol\rho|m)$ per ognuna e si prende la più alta. Non tiene conto delle probabilità a priori.

Teorema. Se le ipotesi sono equiprobabili ($P_m=P$ per ogni $m$), il criterio MAP coincide con il ML. Dimostrazione: $\arg\max_mP\,p_{\mathbf r|m}=\arg\max_mp_{\mathbf r|m}$, perché $P$ è una costante.

Criterio MD (minima distanza)

Si calcolano le distanze dal punto ricevuto a tutti i punti della costellazione e si sceglie il più vicino: $$\hat m=\arg\min_m\frac{\lVert\boldsymbol\rho-\mathbf s_m\rVert^2}{N_0}=\arg\min_m\lVert\boldsymbol\rho-\mathbf s_m\rVert.$$ Teorema. Se il canale è AWGN, MD coincide con ML. Dimostrazione: con $p_{\mathbf r|m}=\left(\pi N_0\right)^{-I/2}e^{-\lVert\boldsymbol\rho-\mathbf s_m\rVert^2/N_0}$, massimizzare l'esponenziale equivale a massimizzare $-\lVert\boldsymbol\rho-\mathbf s_m\rVert^2$, cioè a minimizzare la distanza (la costante $(\pi N_0)^{-I/2}$ non conta).

Riassumendo:

Il criterio MD è il più semplice ma coincide col MAP solo se i simboli sono equiprobabili e il canale è AWGN. È la risposta tipica alla domanda d'esame: "quale criterio si usa in questa situazione e tale criterio è ottimo?"

Regioni di decisione con MD. Il confine tra due punti $\mathbf s_m$ e $\mathbf s_n$ è l'asse del segmento che li unisce (retta perpendicolare a metà): le regioni sono i poligoni di Voronoipartizione in cui ogni regione contiene i punti più vicini a un dato punto della costellazione della costellazione. Con MAP e probabilità diverse la frontiera resta perpendicolare al segmento ma si sposta verso il simbolo meno probabile, ampliando la regione del più probabile.

Soglia MAP tra due punti in una dimensione

In dimensione 1 con due punti $s_i<s_j$, rumore $\mathcal N\left(0,\sigma_I^2\right)$ con $\sigma_I^2=\frac{N_0}2$ e probabilità $P_i,P_j$: i due valori $D$ si uguagliano in $$P_i\,e^{-\frac{(\rho-s_i)^2}{N_0}}=P_j\,e^{-\frac{(\rho-s_j)^2}{N_0}}\quad\Longrightarrow\quad\boxed{\rho^*=\frac{s_i+s_j}2+\frac{N_0}2\,\frac{\ln\left(P_i/P_j\right)}{s_j-s_i}=\frac{s_i+s_j}2+\sigma_I^2\frac{\ln\left(P_i/P_j\right)}{s_j-s_i}.}$$ Si decide $s_j$ se $\rho>\rho^*$. Se $P_i=P_j$ il secondo termine è nullo: la soglia è a metà (MD). Se $P_i>P_j$ la soglia si sposta verso $s_j$ (verso il punto meno probabile, cioè la regione di $s_i$ si allarga).

Esempio numerico. $s_1=0$, $s_2=1$, rumore $\sigma_I=0{,}5$, probabilità $P_1=0{,}9$, $P_2=0{,}1$.

• MD (soglia $0{,}5$): $P[E]=0{,}9\,Q\left(\frac{0{,}5}{0{,}5}\right)+0{,}1\,Q(1)=Q(1)=0{,}159$.
• MAP: $\rho^*=0{,}5+0{,}25\ln9=1{,}049$. $P[E]=0{,}9\,Q\left(\frac{1{,}049}{0{,}5}\right)+0{,}1\,P\left[w<1{,}049-1\right]=0{,}9\cdot0{,}0179+0{,}1\cdot0{,}539=0{,}070$.

Il MAP dimezza l'errore (da $0{,}159$ a $0{,}070$). In particolare, 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$), il MAP sceglie $s_1$ ($D_1=0{,}9\cdot0{,}22=0{,}20>D_2=0{,}1\cdot0{,}74=0{,}074$), perché $s_1$ è molto più probabile a priori.

Un altro esempio, non di telecomunicazioni. Un test clinico misura i linfociti: sano $=3{,}5$, malato $=18{,}5$; i pazienti sani sono il 99%. Un paziente con misura $10$: la distanza minima lo dà come sano; il ML (con un modello di Poisson) come malato; il MAP (che tiene conto che la malattia è rara) come sano. Attenzione: il MAP massimizza la probabilità di decisione corretta, ma per un esame clinico può contare di più non avere falsi negativi: il criterio va scelto in base a ciò che interessa davvero.

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 tre regioni sono tre settori da $120^\circ$ delimitati dagli assi dei lati, che si incontrano nel baricentro. Se $P_1$ cresce, il baricentro si sposta verso gli altri due punti e $\mathcal R_1$ si allarga.

Errori comuni

• Usare MD con simboli non equiprobabili e dire che è ottimo.
• Dimenticare che le soglie MAP si spostano verso il punto meno probabile.
• Confondere $\sigma_I^2=\frac{N_0}2$ con $N_0$ nella formula della soglia.
• Dimenticare che MD, ML e MAP coincidono solo sotto le due condizioni (equiprobabilità e AWGN).