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){=}_{{d}ef}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ć (błąd składni): {\displaystyle 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 {ℬ}}p(B=b\wedge A=\mathrm{\Delta }(b))$

$=\sum _{b\in {ℬ}}p(A=\mathrm{\Delta }(b))\cdot (B=b|A=\mathrm{\Delta }(b))$

$=\sum _{b\in {ℬ}}p(A=\mathrm{\Delta }(b))\cdot P(\mathrm{\Delta }(b)\to b)$

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

$P{r}_E(\mathrm{\Delta },A)=1-P{r}_C(\mathrm{\Delta },A)$

$=\sum _{a\in {𝒜},b\in {ℬ}}p(A=a\wedge B=b\wedge \mathrm{\Delta }(b)\ne a)$

$=\sum _{a\in {𝒜}}p(A=a)\cdot p(\mathrm{\Delta }\circ B\ne a|A=a)$

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)}{\sum _{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 (TODO ćwiczenie). 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

$\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>}=\underset{\text{<mi fromhbox="1">p</mi>}\in {𝒫}}{\int }\sum _{b\in {ℬ}}\text{<mi fromhbox="1">p</mi>}(\mathrm{\Delta }(b))\cdot p(\mathrm{\Delta }(b)\to b)d\text{<mi fromhbox="1">p</mi>}$

$=\sum _{b\in {ℬ}}p(\mathrm{\Delta }(b)\to b)\cdot \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>}$

Można teraz zauważyć (lub udowodnić formalnie, korzystając z całki Lebesgue), ż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 TODO ćwiczenie).

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

Zauważmy po pierwsze ż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.