Teoria informacji/TI Wykład 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Własności funkcji wypukłych

Do dalszego opisu własności kodów będziemy potrzebowali przypomnienia pewnych faktów z analizy matematycznej:


Definicja [Funkcja wypukła]

Funkcja jest wypukła (na [a,b]) jeśli , :

Funkcja jest ściśle wypukła, jeśli powyższa nierówność jest ścisła z wyjątkiem przypadku, gdy lub . Geometrycznie oznacza to, że dowolna cięciwa wykresu leży (ściśle) powyżej tego wykresu.

Funkcja wypukła


Lemat

Jeśli f jest ciągła na [a,b] i dwukrotnie różniczkowalna na (a,b) oraz (), to jest wypukła (ściśle wypukła).

Dowód

Załóżmy . Z twierdzenia Lagrange’a o wartości średniej zastosowanego do funkcji f’ wynika, że f’ jest słabo rosnąca na (a,b) (dla , ).

Niech . Przekształcając nieco naszą formułę, mamy pokazać

Używając ponownie twierdzenia Lagrange’a, tym razem dla f, sprowadzamy to do

gdzie jest jakimś punktem w przedziale , a w przedziale . Korzystając z tego, że , wystarczy nam pokazać

co jest równoważne

A to już wynika z faktu, że f’ jest słabo rosnąca na (a,b). Dla rozumowanie jest analogiczne. End of proof.gif


W ramach tego kursu będziemy zajmować się głównie skończonymi przestrzeniami probabilistycznymi. Określając X jako zmienną losową na S, zawsze będziemy zakładać, że S jest dana razem z rozkładem prawdopodobieństwa (a więc ), i . Przypomnijmy że wartość oczekiwana zmiennej X to

Jeśli , będziemy używać notacji , . W takim zapisie . Od razu zauważmy, że E X nie zależy od tych , dla których . Mówimy, że X jest stała, jeśli zachodzi tylko dla jednej wartości i.


Twierdzenie (Nierówność Jensena)

Jeśli jest funkcją wypukłą, to dla każdej zmiennej losowej ,
.
Jeśli dodatkowo f jest ściśle wypukła, to powyższa nierówność jest ścisła z wyjątkiem sytuacji, gdy X jest stała.

Dowód

Przez indukcję po . Przypadek jest trywialny, a dla nierówność możemy zapisać w postaci

co jest dokładnie definicją (ścisłej) wypukłości.

Niech i załóżmy, że twierdzenie jest spełnione dla dowolnych zmiennych losowych nad S’ o ile . Bez utraty ogólności możemy założyć, że Niech dla . Wtedy

Zauważmy, że użyliśmy dwukrotnie hipotezy indukcyjnej: po pierwsze dla zmiennej losowej wyznaczonej przez prawdopodobieństwa i wartości , po drugie dla zmiennej losowej wyznaczonej przez prawdopodobieństwa , i wartości oraz .

Załóżmy teraz, że f jest ściśle wypukła i że w powyższym wywodzie wszystkie nierówności są równościami. Wynika z tego, że obie zmienne losowe, dla których użyliśmy hipotezy indukcyjnej, są stałe. Po pierwsze dla wszystkich dla których , i ponadto jeśli to - a więc X jest stała. End of proof.gif


Konwencja Aby nie rozważać za każdym razem szczególnych przypadków, przyjmiemy konwencję

Jest to uzasadnione przejściami granicznymi: .

W dalszej części wykładu przydatna będzie funkcja . Na podstawie lematu powyżej łatwo pokazać, że dla funkcja ta jest ściśle wypukła na przedziale , mamy bowiem:


Lemat [Złoty]

Niech , gdzie i dla i niech . Wtedy
i równość zachodzi tylko wtedy, gdy dla .

Dowód

Załóżmy najpierw, że . Wtedy

Korzystając z nierówności Jensena dla funkcji (na , tzn. na dowolnym , gdzie ) i zmiennej losowej, która przyjmuje wartości z prawdopodobieństwami , dostajemy

.

A zatem . Ponieważ funkcja jest ściśle rosnąca, równość może zachodzić tylko dla stałej zmiennej losowej. Ponieważ i , implikuje to, że dla .

Założmy teraz, że . Dodajmy oraz . Analogicznie do poprzedniego przypadku uzyskamy

Zauważmy, że w tym przypadku nie może być równości, gdyż implikowałoby to . End of proof.gif

Entropia

Wróćmy do przykładu gry w zgadywanie z poprzedniego wykładu. Liczba pytań potrzebnych do zidentyfikowania obiektu wynosiła tam dokładnie . (Było to możliwe, ponieważ prawdopodobieństwa były potęgami .) Oczekiwana liczba pytań była więc

.

Korzystając ze Złotego Lematu, możemy pokazać, że liczba ta jest optymalna w tym sensie, że przy dowolnej strategii średnia liczba pytań nie może być mniejsza. Rozważmy w tym celu strategię, dla której liczba pytań dla każdego wynosi . Z nierówności Krafta mamy . Aplikując Złoty Lemat dla oraz dostajemy


Jesteśmy gotowi do wprowadzenia jednego z głównych pojęć Teorii Informacji:


Definicja [Entropia Shannona]

Entropią przestrzeni probabilistycznej S (parametryzowaną przez ) nazywamy funkcję

Innymi słowy, jest wartością oczekiwaną zmiennej losowej zdefiniowanej na S jako .

Z oczywistych przyczyn w informatyce zwykle przyjmuje się , dlatego będziemy często pisać po prostu H na określenie .

Claude E. Shannon (1916--2001) był amerykańskim matematykiem i inżynierem. Jego praca pt. A Mathematical Theory of Communication, opublikowana w 1948 r. zapoczątkowała teorię informacji.

Komentarz: Zauważmy, że definicja entropii łączy dwa pomysły:

  • wyliczenie wartości oczekiwanej pewnej funkcji złożonej z funkcją prawdopodobieństwa:
  • wybranie jako tej funkcji , co zapewne jest najistotniejsze.
Ernst Heinrich Weber (1795–1878)
Gustav Fechner (1801–1887)

Faktycznie, funkcja logarytmiczna odgrywa kluczowe znaczenie w naszej percepcji. Tak zwane prawo Webera-Fechnera w naukach kognitywnych głosi, że odbierana przez nasze zmysły percepcja (P) zmiany bodźca (S, od słowa stimuli) jest proporcjonalna nie do absolutnej, ale do względnej zmiany tego bodźca

Co po scałkowaniu daje

To zjawisko zostało zaobserwowane w percepcji ciężaru, jasności, dźwięku (zarówno jego głośności, jak i wysokości), a nawet statusu materialnego. Możemy więc myśleć o entropii jako naszej „percepcji prawdopodobieństwa”.


Jakie wartości może przyjmować entropia, w zależności od |S| i p? Z definicji wynika, że i że równość zachodzi jedynie wtedy, gdy całe prawdopodobieństwo jest skupione w jednym punkcie. Z drugiej strony, mamy


Fakt

Entropia jest zawsze ograniczona przez logarytm rozmiaru przestrzeni możliwości
i równość ma miejsce wtedy i tylko wtedy gdy dla wszystkich .

Dowód

Korzystając ze Złotego Lematu dla i , otrzymujemy
z równością dokładnie dla . End of proof.gif