Teoria informacji/TI Wykład 2

From Studia Informatyczne

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 f : [a,b] \to {\mathbb R} jest wypukła (na [a,b]) jeśli \forall x_1, x_2 \in [a,b], \forall \lambda \in [0,1]:
\lambda f(x_1 ) + (1 - \lambda ) f(x_2 )  \geq f (\lambda x_1 + (1 - \lambda ) x_2 )

Funkcja jest ściśle wypukła, jeśli powyższa nierówność jest ścisła z wyjątkiem przypadku, gdy \lambda \in \{ 0,1\} lub x_1 = x_2. 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 f'' \geq 0 (f'' > 0), to jest wypukła (ściśle wypukła).

Dowód

Załóżmy f'' \geq 0. Z twierdzenia Lagrange’a o wartości średniej zastosowanego do funkcji f’ wynika, że f’ jest słabo rosnąca na (a,b) (dla a<t_1<t_2<b , f'(t_2)-f'(t_1)=f''(\tilde{t})(t_2 - t_1) \geq 0).

Niech {x_{\lambda }} = \lambda x_1 + (1 - \lambda ) x_2. Przekształcając nieco naszą formułę, mamy pokazać

\lambda (f(x_{\lambda }) - f(x_1)) \leq (1 - \lambda ) (f (x_2) - f (x_{\lambda }))

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

\lambda  f' (\tilde{x_1}) (x_{\lambda } - x_1) \leq (1 - \lambda ) f' (\tilde{x_2})  (x_2 - x_{\lambda })

gdzie \tilde{x_1} jest jakimś punktem w przedziale (x_1,x_{\lambda}), a \tilde{x_2} w przedziale (x_{\lambda},x_2). Korzystając z tego, że x_{\lambda}-x_1= \lambda(x_2-x_1), wystarczy nam pokazać

\lambda (1 - \lambda )  f' (\tilde{x_1})  (x_2 -  x_1) \leq \lambda (1 - \lambda )  f' (\tilde{x_2})  (x_2 -  x_1)

co jest równoważne

f' (\tilde{x_1})  \leq f' (\tilde{x_2})
A to już wynika z faktu, że f’ jest słabo rosnąca na (a,b). Dla f''>0 rozumowanie jest analogiczne. image: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 p:S \to [0,1] (a więc \sum_{s \in S} p(s) = 1), i X:S \to \mathbb{R}. Przypomnijmy że wartość oczekiwana zmiennej X to

E X = \sum_{s \in S}  p(s) \cdot X(s)

Jeśli S = \{ s_1, \ldots , s_m \}, będziemy używać notacji p_i=p(s_i), x_i=X(s_i). W takim zapisie E X =  p_1 x_1  + \ldots + p_m x_m. Od razu zauważmy, że E X nie zależy od tych x_i, dla których p_i=0. Mówimy, że X jest stała, jeśli p_i > 0 zachodzi tylko dla jednej wartości i.


Twierdzenie (Nierówność Jensena)

Jeśli f:[a,b] \to \mathbb{R} jest funkcją wypukłą, to dla każdej zmiennej losowej X:S \to [a,b],
E f(X) \geq f (E X).
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 |S|. Przypadek |S|=1 jest trywialny, a dla |S|=2 nierówność możemy zapisać w postaci
p_1 f(x_1) + p_2 f(x_2) \geq (>) f ( p_1 x_1 + p_2 x_2)

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

Niech S=\{s_1, \ldots, s_m\} i załóżmy, że twierdzenie jest spełnione dla dowolnych zmiennych losowych nad S’ o ile |S'|\le m-1. Bez utraty ogólności możemy założyć, że p_m<1 Niech p_i' = \frac{p_i}{1-p_m} dla i = 1,\ldots ,m-1. Wtedy

\aligned \sum_{i=1}^{m} p_i \, f(x_i) &= p_m f (x_m) + (1 - p_m) \sum_{i=1}^{m-1}  p_i' f(x_i)\\ &\geq p_m f (x_m) + (1 - p_m) f \left( \sum_{i=1}^{m-1} p_i' \, x_i  \right)\\ &\geq f \left( p_m x_m + (1 - p_m) \sum_{i=1}^{m-1} p_i'\,  x_i \right)\\ &= f \left( \sum_{i=1}^{m} p_i x_i \right) \endaligned

Zauważmy, że użyliśmy dwukrotnie hipotezy indukcyjnej: po pierwsze dla zmiennej losowej wyznaczonej przez prawdopodobieństwa p_1', \ldots , p_{m-1}' i wartości x_1, \ldots , x_{m-1}, po drugie dla zmiennej losowej wyznaczonej przez prawdopodobieństwa p_m, 1-p_m, i wartości x_m oraz \sum_{i=1}^{m-1} p_i' x_i.

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 x_i=C dla wszystkich i = 1, \ldots , m-1 dla których p_i' \neq 0, i ponadto jeśli p_m>0 to x_m = \sum_{i=1}^{m-1} p_i' x_i = C - a więc X jest stała. image:End_of_proof.gif


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

0 \log_r 0 = 0 \log_r \frac{1}{0} = 0

Jest to uzasadnione przejściami granicznymi: lim_{x \to 0^+} x \log_r x =  \lim_{x \to 0^+} - x \log_r \frac{1}{x} = \lim_{y \to \infty} - \frac{\log_r y}{y} = 0.

W dalszej części wykładu przydatna będzie funkcja x \log_r x. Na podstawie lematu powyżej łatwo pokazać, że dla r>1 funkcja ta jest ściśle wypukła na przedziale [0,\infty), mamy bowiem:

\left( x \log_r x \right)'' = \left(\log_r x + x \cdot  \frac{1}{x} \cdot \log_r e \right)' =  \frac{1}{x} \cdot \log_r e > 0


Lemat [Złoty]

Niech 1  =  \sum_{i=1}^q x_i \geq \sum_{i=1}^q y_i, gdzie x_i\ge 0 i y_i> 0 dla i=1, \ldots, q i niech r>1. Wtedy
\sum_{i=1}^q x_i \cdot \log_r \frac{1}{y_i}\geq \sum_{i=1}^q x_i \cdot \log_r \frac{1}{x_i}
i równość zachodzi tylko wtedy, gdy x_i=y_i dla i=1, \ldots, q.

Dowód

Załóżmy najpierw, że \sum_{i=1}^q y_i = 1. Wtedy

\mathit{Lewa} - \mathit{Prawa} = \sum_{i=1}^q x_i \cdot \log_r \frac{x_i}{y_i} = \sum_{i=1}^q y_i \cdot \left( \frac{x_i}{y_i} \right)  \cdot \log_r \frac{x_i}{y_i}

Korzystając z nierówności Jensena dla funkcji x \log_r x (na [0,\infty), tzn. na dowolnym [0,M], gdzie M < \infty) i zmiennej losowej, która przyjmuje wartości \left(\frac{x_i}{y_i} \right) z prawdopodobieństwami y_i, dostajemy

\sum_{i=1}^q y_i \cdot \left(\frac{x_i}{y_i} \right)  \cdot \log_r \frac{x_i}{y_i} \geq \log_r \sum_{i=1}^q y_i \cdot \left( \frac{x_i}{y_i} \right) = 0.

A zatem \mathit{Lewa} \geq \mathit{Prawa}. Ponieważ funkcja x \log_r x jest ściśle rosnąca, równość może zachodzić tylko dla stałej zmiennej losowej. Ponieważ y_i>0 i \sum_{i=1}^q x_i  = \sum_{i=1}^q y_i, implikuje to, że x_i=y_i dla i=1, \ldots, q.

Założmy teraz, że \sum_{i=1}^q y_i < 1. Dodajmy y_{q+1} = 1 -  \sum_{i=1}^q y_i oraz x_{q+1}=0. Analogicznie do poprzedniego przypadku uzyskamy

\sum_{i=1}^q x_i \cdot \log_r \frac{1}{y_i} = \sum_{i=1}^{q+1} x_i \cdot \log_r \frac{1}{y_i} \geq \sum_{i=1}^{q+1} x_i \cdot \log_r \frac{1}{x_i} = \sum_{i=1}^{q} x_i \cdot \log_r \frac{1}{x_i}
Zauważmy, że w tym przypadku nie może być równości, gdyż implikowałoby to x_{q+1}=y_{q+1}. image:End_of_proof.gif

Entropia

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

\sum_{i=1}^{m}  p(s_i) \cdot \log_2  \frac{1}{p(s_i)}.

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 s_i wynosi \ell(s_i). Z nierówności Krafta mamy \sum_{i=1}^{m} \frac{1}{2^{\ell (s_i)}} \leq 1. Aplikując Złoty Lemat dla x_i=p(s_i) oraz y_i = \frac{1}{2^{\ell (s_i)}} dostajemy

\sum_{i=1}^{m}  p(s_i) \cdot \ell (s_i) \geq \sum_{i=1}^{m}  p(s_i) \cdot \log_2  \frac{1}{p(s_i)}


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


Definicja [Entropia Shannona]

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

\aligned H_r (S) & = \sum_{s \in S} p (s) \cdot  \log_r \frac{1}{p(s)}\\  & = - \sum_{s \in S} p (s) \cdot  \log_r {p(s)} \endaligned

Innymi słowy, H_r(S) jest wartością oczekiwaną zmiennej losowej zdefiniowanej na S jako s \mapsto \log_r \frac{1}{p(s)}.

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

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:

\sum_{s \in S} p (s) \cdot f \circ p(s)

  • wybranie jako tej funkcji f = \log, co zapewne jest najistotniejsze.
Ernst Heinrich Weber (1795–1878)
Enlarge
Ernst Heinrich Weber (1795–1878)
Gustav Fechner (1801–1887)
Enlarge
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

\partial P \approx \frac{ \partial S}{S}

Co po scałkowaniu daje

P \approx \log S

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 H_r(S)\ge 0 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
H_r(S) \le \log_r|S|
i równość ma miejsce wtedy i tylko wtedy gdy p(s)=\frac{1}{|S|} dla wszystkich s \in S.

Dowód

Korzystając ze Złotego Lematu dla x_i=p(s_i) i y_i=\frac{1}{|S|}, otrzymujemy
\sum_{s \in S} p (s) \cdot  \log_r \frac{1}{p(s)} \leq \sum_{s \in S} p (s) \cdot  \log_r |S| = \log_r |S|
z równością dokładnie dla p(s)=\frac{1}{|S|}. image:End_of_proof.gif