Teoria informacji/TI Wykład 2

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{ℝ}$ jest wypukła (na [a,b]) jeśli $\mathrm{\forall }{x}_1,x_2\in [a,b]$, $\mathrm{\forall }\lambda \in [0,1]$: $\lambda f(x_1)+(1-\lambda )f(x_2)\ge 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.

Lemat

Jeśli f jest ciągła na [a,b] i dwukrotnie różniczkowalna na (a,b) oraz $f^{″}\ge 0$ ($f^{″}>0$), to jest wypukła (ściśle wypukła).

Dowód

Załóżmy $f^{″}\ge 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^{\prime }(t_2)-f^{\prime }(t_1)=f^{″}(\tilde{t})(t_2-t_1)\ge 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))\le (1-\lambda )(f(x_2)-f(x_{\lambda }))$

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

$\lambda f^{\prime }(\widetilde{x_1})(x_{\lambda }-x_1)\le (1-\lambda )f^{\prime }(\widetilde{x_2})(x_2-x_{\lambda })$

gdzie $\widetilde{x_1}$ jest jakimś punktem w przedziale $(x_1,x_{\lambda })$, a $\widetilde{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^{\prime }(\widetilde{x_1})(x_2-x_1)\le \lambda (1-\lambda )f^{\prime }(\widetilde{x_2})(x_2-x_1)$

co jest równoważne

$f^{\prime }(\widetilde{x_1})\le f^{\prime }(\widetilde{x_2})$ A to już wynika z faktu, że f’ jest słabo rosnąca na (a,b). Dla $f^{″}>0$ rozumowanie jest analogiczne.

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{ℝ}$. Przypomnijmy że wartość oczekiwana zmiennej X to

$EX=\sum _{s\in S}p(s)\cdot X(s)$

Jeśli $S=\{s_1,\dots ,s_m\}$, będziemy używać notacji $p_i=p(s_i)$, $x_i=X(s_i)$. W takim zapisie $EX=p_1{x}_1+\dots +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{ℝ}$ jest funkcją wypukłą, to dla każdej zmiennej losowej $X:S\to [a,b]$, $Ef(X)\ge f(EX)$. 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)\ge (>)f(p_1{x}_1+p_2{x}_2)$

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

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

$\begin{array}{rl}\sum _{i=1}^m{p}_{i}f(x_i)& =p_{m}f(x_m)+(1-p_m)\sum _{i=1}^{m-1}{p_i}^{\prime }f(x_i)\\ & \ge p_{m}f(x_m)+(1-p_m)f\left(\sum _{i=1}^{m-1}{p_i}^{\prime }{x}_i\right)\\ & \ge f(p_m{x}_m+(1-p_m)\sum _{i=1}^{m-1}{p_i}^{\prime }{x}_i)\\ & =f\left(\sum _{i=1}^m{p}_i{x}_i\right)\end{array}$

Zauważmy, że użyliśmy dwukrotnie hipotezy indukcyjnej: po pierwsze dla zmiennej losowej wyznaczonej przez prawdopodobieństwa ${p_1}^{\prime },\dots ,p_{m^{\prime }-1}$ i wartości $x_1,\dots ,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}^{\prime }{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,\dots ,m-1$ dla których ${p_i}^{\prime }\ne 0$, i ponadto jeśli $p_m>0$ to $x_m=\sum _{i=1}^{m-1}{p_i}^{\prime }{x}_i=C$ - a więc X jest stała.

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: $li{m}_{x\to 0^{+}}x{\log }_{r}x=\underset{x\to 0^{+}}{\lim }-x{\log }_r\frac{1}{x}=\underset{y\to \mathrm{\infty }}{\lim }-\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,\mathrm{\infty })$, mamy bowiem:

$\left(x{\log }_{r}x\right)=({\log }_{r}x+x\cdot \frac{1}{x}\cdot {\log }_{r}e)=\frac{1}{x}\cdot {\log }_{r}e>0$

Lemat [Złoty]

Niech $1=\sum _{i=1}^q{x}_i\ge \sum _{i=1}^q{y}_i$, gdzie $x_i\ge 0$ i $y_i>0$ dla $i=1,\dots ,q$ i niech $r>1$. Wtedy $\sum _{i=1}^q{x}_i\cdot {\log }_r\frac{1}{y_i}\ge \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,\dots ,q$.

Dowód

Załóżmy najpierw, że $\sum _{i=1}^q{y}_i=1$. Wtedy

${L}{e}{w}{a}-{P}{r}{a}{w}{a}=\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,\mathrm{\infty })$, tzn. na dowolnym $[0,M]$, gdzie $M<\mathrm{\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}\ge {\log }_r\sum _{i=1}^q{y}_i\cdot \left(\frac{x_i}{y_i}\right)=0$.

A zatem ${L}{e}{w}{a}\ge {P}{r}{a}{w}{a}$. 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,\dots ,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}\ge \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}$.

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)}}\le 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)\ge \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ę $\begin{array}{rl}{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)\end{array}$

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)

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)}\le \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|}$.