Teoria informacji/TI Wykład 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Reguły decyzyjne

Przypuśćmy, że na wyjściu z kanału otrzymujemy sekwencję znaków . Znając mapowanie dla , 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 .

Jakość reguły mierzymy przez

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.:


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


Interesuje nas maksymalizacja , a więc minimalizacja .

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 na , takie że jest maksymalne. możemy wyznaczyć (znając rozkład A) ze wzoru:

Z definicji wynika, że

dla dowolnej reguły decyzyjnej .


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

Definicja [Reguła maksymalnego podobieństwa]

Ta reguła odwzorowuje na w taki sposób, że jest maksymalne.


Jeśli rozkład na A jest jednostajny (), to reguła ta odpowiada regule .

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 , i niech będzie zbiorem wszystkich rozkładów prawdopodobieństwa na ,

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


Można teraz zauważyć (lub udowodnić formalnie, korzystając z całki Lebesgue'a), że nie zależy od wyboru a. Zatem jest zawsze takie samo, i żeby zmaksymalizować , musimy maksymalizować , 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 . Jakie jest prawdopodobieństwo, że wyjściowym ciągiem będzie ? Jeśli transmisje są niezależne, prawdopodobieństwo to będzie iloczynem kolejnych .

Przypomnijmy, że zmienne losowe są niezależne, jeśli

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

Rozszerzając naszą konwencję zapisową, będziemy skracać do .

Lemat

Jeśli zmienne losowe (X,Y) oraz (X',Y') są niezależne, to
o ile zachodzi zachodzi .


Dowód

Po pierwsze, zauważmy, że niezależność (X,Y) i (X',Y') implikuje niezależność X i X'.

Zatem

End of proof.gif


Wniosek [Niezależność symboli]

Załóżmy, że są niezależnymi zmiennymi losowymi o takim samym rozkładzie, takimi że każda para jest parą wejście-wyjście dla kanału . Wtedy

Dowód

Niezależność implikuje, że jest niezależne od . Dowód sprowadza się zatem do skorzystania wielokrotnie z powyższego lematu. 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 spełniają poniższe wymagania:

Bezstanowość

Brak feedbacku

Wtedy niezależność symboli jest zachowana.


Dowód

Przez indukcję możemy pokazać, że

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

z brakiem feedbacku:

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

co kończy dowód. 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.