Teoria informacji/TI Wykład 8

From Studia Informatyczne

Reguły decyzyjne

Przypuśćmy, że na wyjściu z kanału \Gamma otrzymujemy sekwencję znaków b_{i_1}, \ldots , b_{i_k}. Znając mapowanie P(a \to b) dla a \in \mathcal{A}, b \in \mathcal{B}, 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 \Delta : \mathcal{B} \to \mathcal{A}.

Jakość reguły mierzymy przez

Pr_C ( \Delta , A ) \stackrel{def}{=} p ( \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.:

\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) \endaligned


Dualnie, prawdopodobieństwo błędu reguły \Delta, definiujemy jako

\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) \endaligned


Interesuje nas maksymalizacja Pr_C(\Delta,A), a więc minimalizacja Pr_E(\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 \mathcal{B} na \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)} { \Sigma_{a' \in {\cal A}} p (a' \to b )  \cdot  p (a')}

Z definicji wynika, że

Pr_C ( \Delta_o , A ) \geq Pr_C ( \Delta , A )

dla dowolnej reguły decyzyjnej \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 \mathcal{B} na \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}{\mathcal{A}}), to reguła ta odpowiada regule \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 \mathcal{A}=\{a_1,\ldots,a_m\}, i niech \mathcal{P} będzie zbiorem wszystkich rozkładów prawdopodobieństwa na \mathcal{A},

\mathcal{P}=\{ {\textbf p} : \sum_{a \in {\mathcal A}} {\textbf p}(a) = 1 \}

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

\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} \endaligned


Można teraz zauważyć (lub udowodnić formalnie, korzystając z całki Lebesgue'a), że \int_{{\textbf p} \in {\mathcal P}} {\textbf p} (a)\, d {\textbf p} nie zależy od wyboru a. Zatem \int_{{\textbf p} \in {\mathcal P}} {\textbf p} (\Delta(b))\, d {\textbf p} jest zawsze takie samo, i żeby zmaksymalizować \int_{{\textbf p} \in {\mathcal P}} Pr_C (\Delta  , {\textbf p})\, d {\textbf p}, musimy maksymalizować \sum_{b \in {\mathcal B}} p (\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, \ldots, a_k. Jakie jest prawdopodobieństwo, że wyjściowym ciągiem będzie b_1, b_2, \ldots, 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, \ldots, X_k są niezależne, jeśli

P(X_1=x_1 \wedge \ldots \wedge X_k = x_k ) = p (X_1 = x_1) \cdot \ldots \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 \ldots \wedge X_k = x_k ) do p (x_1\ldots x_k ).

Lemat

Jeśli zmienne losowe (X,Y) oraz (X',Y') są niezależne, to
p (Y = y \wedge Y' = y' | X = x \wedge X' = x')=p(Y = y | X = x) \cdot p (Y' = y' | X' = x')
o ile zachodzi zachodzi p  (X = x \wedge X' = x') > 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') = p \left( (x \wedge \bigvee {\mathcal Y}) \wedge (x' \wedge \bigvee {\mathcal Y}') \right) = \sum_{y,y'} p (x \wedge y) \cdot p(x' \wedge y') = p(x) \cdot p(x')

Zatem

p (y \wedge y' | x \wedge x') = \frac{p(y \wedge y' \wedge  x \wedge x')}{p(x \wedge x')} = \frac{p(y \wedge x) \cdot p(y' \wedge x')}{p(x) \cdot p(x')} = p (y |x) \cdot p (y'|x')
image:End_of_proof.gif


Wniosek [Niezależność symboli]

Załóżmy, że (A_1,B_1), \ldots, (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 \Gamma. Wtedy
p( b_1 \ldots b_k | a_1 \ldots a_k ) = p( b_1| a_1) \cdot \ldots  \cdot p( b_k | a_k )

Dowód

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

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), \ldots, (A_k,B_k) spełniają poniższe wymagania:

Bezstanowość

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

Brak feedbacku

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

Wtedy niezależność symboli jest zachowana.


Dowód

Przez indukcję możemy pokazać, że
p (a_1 \wedge \ldots \wedge a_k \wedge b_1 \wedge \ldots \wedge b_k ) = p (b_1 | a_1) \cdot \ldots \cdot p (b_k | a_k) \cdot p (a_1 \wedge \ldots \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 \ldots \wedge a_k \wedge b_1 \wedge \ldots \wedge b_k ) = p( b_k | a_k) \cdot p (a_1 \ldots a_k, b_1\ldots b_{k-1})

z brakiem feedbacku:

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

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

\frac{p (a_1 \wedge \ldots \wedge a_{k-1} \wedge b_1 \wedge \ldots \wedge b_{k-1} )}{p (a_1 \wedge \ldots \wedge a_{k-1})} = p (b_1 | a_1) \cdot \ldots \cdot p (b_{k-1} | a_{k-1})
co kończy dowód. image:End_of_proof.gif


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.