Teoria informacji/TI Wykład 8

Reguły decyzyjne

Przypuśćmy, że na wyjściu z kanału $\mathrm{\Gamma }$ otrzymujemy sekwencję znaków $b_{i_1},\dots ,b_{i_k}$. Znając mapowanie $P(a\to b)$ dla $a\in {𝒜},b\in {ℬ}$, czy możemy odzyskać pierwotną wiadomość wysłaną kanałem?

W niektórych przypadkach jest to oczywiste. Przykładowo dla wiernego kanału odwracającego wystarczy, że odwrócimy wszystkie bity w sekwencji. W większości przypadków jednak nie ma jedynej pewnej metody odkodowania. Przykładowo, dla wadliwej maszyny do pisania tekst wynikowy afu mógł pochodzić z tekstu zet, ale również z tekstu aft i wielu innych. W ogólności zadaniem dla odbiorcy jest wybranie w jakiś sposób wejścia, które mogło dać wskazany wynik. Oczywiście odbiorca chce zmaksymalizować p(A=a|B=b).

Definicja [Reguła decyzyjna}

Regułą decyzyjną nazwiemy każde mapowanie $\mathrm{\Delta }:{ℬ}\to {𝒜}$.

Jakość reguły mierzymy przez

$P{r}_C(\mathrm{\Delta },A)\stackrel{def}{=}p(\mathrm{\Delta }\circ B=A)$ gdzie (A,B) są parą wejście-wyjście (zauważmy że B jest tu jednoznacznie określone, więc definicja jest spójna).

Używając prawdopodobieństwa warunkowego, jakość reguły możemy policzyć na kilka sposobów, np.:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned p( \Delta \circ B = A) & = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p (A = a \wedge B = b \wedge \Delta (b) = a ) \\ & = \sum_{b \in {\mathcal B}} p ( B = b \wedge A = \Delta (b) )\\ & = \sum_{b \in {\mathcal B}} p(A = \Delta (b)) \cdot (B = b | A = \Delta (b) )\\ & = \sum_{b \in {\mathcal B}} p(A = \Delta (b)) \cdot P (\Delta (b) \to b) \end{align} }

Dualnie, prawdopodobieństwo błędu reguły $\mathrm{\Delta }$, definiujemy jako

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned Pr_E ( \Delta , A ) & = 1 - Pr_C ( \Delta , A ) \\ & = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p (A = a \wedge B = b \wedge \Delta (b) \neq a )\\ & = \sum_{a \in {\mathcal A}} p (A = a) \cdot p (\Delta \circ B \neq a | A = a) \end{align} }

Interesuje nas maksymalizacja $P{r}_C(\mathrm{\Delta },A)$, a więc minimalizacja $P{r}_E(\mathrm{\Delta },A)$.

Jeśli rozkład prawdopodobieństwa na A jest znany, możemy taką regułę jednoznacznie wyznaczyć:

Definicja [Reguła idealnego obserwatora]

Ta reguła odwzorowuje $b\in {ℬ}$ na ${\mathrm{\Delta }}_o(b)=a$, takie że $p(a|b)$ jest maksymalne. $p(a|b)$ możemy wyznaczyć (znając rozkład A) ze wzoru: $p(a|b)=\frac{p(a\wedge b)}{p(b)}=\frac{p(a\to b)\cdot p(a)}{{\mathrm{\Sigma }}_{a^{\prime }\in {𝒜}}p(a^{\prime }\to b)\cdot p(a^{\prime })}$

Z definicji wynika, że

$P{r}_C({\mathrm{\Delta }}_o,A)\ge P{r}_C(\mathrm{\Delta },A)$

dla dowolnej reguły decyzyjnej $\mathrm{\Delta }$.

Jeśli rozkład prawdopodobieństwa na A jest nieznany, racjonalnym wyborem jest

Definicja [Reguła maksymalnego podobieństwa]

Ta reguła odwzorowuje $b\in {ℬ}$ na ${\mathrm{\Delta }}_{max}(b)=a$ w taki sposób, że $p(a\to b)=p(b|a)$ jest maksymalne.

Jeśli rozkład na A jest jednostajny ($p(a)=\frac{1}{{𝒜}}$), to reguła ta odpowiada regule ${\mathrm{\Delta }}_o$.

Jeśli rozkład na A nie jest jednostajny, ta reguła nie musi być optymalna. Jest jednak w pewnym sensie „globalnie optymalna”. Przedstawimy tutaj szkic dowodu:

Niech ${𝒜}=\{a_1,\dots ,a_m\}$, i niech ${𝒫}$ będzie zbiorem wszystkich rozkładów prawdopodobieństwa na ${𝒜}$,

${𝒫}=\{\text{<mi fromhbox="1">p</mi>}:\sum _{a\in {𝒜}}\text{<mi fromhbox="1">p</mi>}(a)=1\}$

Utożsamiamy tutaj zmienną losową A z jej rozkładem prawdopodobieństwa $\text{p}$. Średnią (globalną) jakością reguły $\mathrm{\Delta }$ niech będzie

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \int_{{\textbf p} \in {\mathcal P}} Pr_C (\Delta , {\textbf p})\, d {\textbf p} & = \int_{{\textbf p} \in {\mathcal P}} \sum_{b \in {\mathcal B}} {\textbf p} (\Delta (b)) \cdot p (\Delta (b) \to b)\, d {\textbf p}\\ & = \sum_{b \in {\mathcal B}} p (\Delta (b) \to b) \cdot \int_{{\textbf p} \in {\mathcal P}} {\textbf p} (\Delta (b)) \, d {\textbf p} \end{align} }

Można teraz zauważyć (lub udowodnić formalnie, korzystając z całki Lebesgue'a), że $\underset{\text{<mi fromhbox="1">p</mi>}\in {𝒫}}{\int }\text{<mi fromhbox="1">p</mi>}(a)d\text{<mi fromhbox="1">p</mi>}$ nie zależy od wyboru a. Zatem $\underset{\text{<mi fromhbox="1">p</mi>}\in {𝒫}}{\int }\text{<mi fromhbox="1">p</mi>}(\mathrm{\Delta }(b))d\text{<mi fromhbox="1">p</mi>}$ jest zawsze takie samo, i żeby zmaksymalizować $\underset{\text{<mi fromhbox="1">p</mi>}\in {𝒫}}{\int }P{r}_C(\mathrm{\Delta },\text{<mi fromhbox="1">p</mi>})d\text{<mi fromhbox="1">p</mi>}$, musimy maksymalizować $\sum _{b\in {ℬ}}p(\mathrm{\Delta }(b)\to b)$, co realizuje właśnie reguła maksymalnego podobieństwa.

Wielokrotne używanie kanału

Przypuśćmy, że wysyłamy przez kanał ciąg symboli $a_1,a_2,\dots ,a_k$. Jakie jest prawdopodobieństwo, że wyjściowym ciągiem będzie $b_1,b_2,\dots ,b_k$? Jeśli transmisje są niezależne, prawdopodobieństwo to będzie iloczynem kolejnych $P(a\to b)$.

Przypomnijmy, że zmienne losowe $X_1,X_2,\dots ,X_k$ są niezależne, jeśli

$P(X_1=x_1\wedge \dots \wedge X_k=x_k)=p(X_1=x_1)\cdot \dots \cdot p(X_k=x_k)$

(warto zauważyć, że jest to wymaganie silniejsze niż niezależność każdej pary zmiennych).

Rozszerzając naszą konwencję zapisową, będziemy skracać $p(X_1=x_1\wedge \dots \wedge X_k=x_k)$ do $p(x_1\dots x_k)$.

Lemat

Jeśli zmienne losowe (X,Y) oraz (X',Y') są niezależne, to $p(Y=y\wedge Y^{\prime }=y^{\prime }|X=x\wedge X^{\prime }=x^{\prime })=p(Y=y|X=x)\cdot p(Y^{\prime }=y^{\prime }|X^{\prime }=x^{\prime })$ o ile zachodzi zachodzi $p(X=x\wedge X^{\prime }=x^{\prime })>0$.

Dowód

Po pierwsze, zauważmy, że niezależność (X,Y) i (X',Y') implikuje niezależność X i X'. $p(x\wedge x^{\prime })=p((x\wedge \bigvee {𝒴})\wedge (x^{\prime }\wedge \bigvee {{𝒴}}^{\prime }))=\sum _{y,y^{\prime }}p(x\wedge y)\cdot p(x^{\prime }\wedge y^{\prime })=p(x)\cdot p(x^{\prime })$

Zatem

$p(y\wedge y^{\prime }|x\wedge x^{\prime })=\frac{p(y\wedge y^{\prime }\wedge x\wedge x^{\prime })}{p(x\wedge x^{\prime })}=\frac{p(y\wedge x)\cdot p(y^{\prime }\wedge x^{\prime })}{p(x)\cdot p(x^{\prime })}=p(y|x)\cdot p(y^{\prime }|x^{\prime })$

Wniosek [Niezależność symboli]

Załóżmy, że $(A_1,B_1),\dots ,(A_k,B_k)$ są niezależnymi zmiennymi losowymi o takim samym rozkładzie, takimi że każda para $(A_i,B_i)$ jest parą wejście-wyjście dla kanału $\mathrm{\Gamma }$. Wtedy $p(b_1\dots b_k|a_1\dots a_k)=p(b_1|a_1)\cdot \dots \cdot p(b_k|a_k)$

Dowód

Niezależność $(A_1,B_1),\dots ,(A_k,B_k)$ implikuje, że $(A_i,B_i)$ jest niezależne od $(A_2,B_2),\dots ,(A_k,B_k)$. Dowód sprowadza się zatem do skorzystania wielokrotnie z powyższego lematu.

Założenie o niezależności kolejnych par w powyższym wniosku jest bardzo silne i w większości wypadków nie możemy go użyć. Okazuje się, że można je zastąpić czymś znacznie słabszym:

Twierdzenie

Załóżmy, że $(A_1,B_1),\dots ,(A_k,B_k)$ spełniają poniższe wymagania:

Bezstanowość

$p(b_k|a_1\dots a_k,b_1\dots b_{k-1})=p(b_k|a_k)$

Brak feedbacku

$p(a_k|a_1\dots a_{k-1},b_1\dots b_{k-1})=p(a_k|a_1\dots a_{k-1})$

Wtedy niezależność symboli jest zachowana.

Dowód

Przez indukcję możemy pokazać, że $p(a_1\wedge \dots \wedge a_k\wedge b_1\wedge \dots \wedge b_k)=p(b_1|a_1)\cdot \dots \cdot p(b_k|a_k)\cdot p(a_1\wedge \dots \wedge a_k)$

jeśli tylko ostatnie prawdopodobieństwo jest niezerowe. Przypadek $k=1$ jest trywialny. Krok indukcyjny uzyskujemy łącząc bezstanowość:

$p(a_1\wedge \dots \wedge a_k\wedge b_1\wedge \dots \wedge b_k)=p(b_k|a_k)\cdot p(a_1\dots a_k,b_1\dots b_{k-1})$

z brakiem feedbacku:

$p(a_1\dots a_k,b_1\dots b_{k-1})=p(a_1\wedge \dots \wedge a_{k-1}\wedge b_1\wedge \dots \wedge b_{k-1})\cdot \frac{p(a_1\wedge \dots \wedge a_k)}{p(a_1\wedge \dots \wedge a_{k-1})}$

i włączając założenie indukcyjne:

$\frac{p(a_1\wedge \dots \wedge a_{k-1}\wedge b_1\wedge \dots \wedge b_{k-1})}{p(a_1\wedge \dots \wedge a_{k-1})}=p(b_1|a_1)\cdot \dots \cdot p(b_{k-1}|a_{k-1})$ co kończy dowód.

Komentarz Od tej pory domyślnie będziemy przyjmować, że niezależność symboli jest zachowana za każdym razem, gdy wielokrotnie używamy kanału BSC.