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 informacji 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 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-x1)$ 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 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 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 tylko dla jednej wartości i zachodzi $p_i>0$

Twierdzenie (Nierówność Jensena)

Jeśli $f:[a,b]\to \mathbb{ℝ}$ jest wypukłą funkcją, to dla każdej zmiennej losowej $X:S\to [a,b]$, $Ef(X)\ge f(EX)$. Jeśli dodatkowo f jest ściśle rosnąca, to powyższa nierówność jest ścisła o ile X nie 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ć żę $p_m<1$ Niech ${p_i}^{\prime }=\frac{p_i}{1-p_m}$ dla $i=1,\dots ,m-1$. Wtedy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}^{\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,\sum _{i=1}^{m-1}{p_i}^{\prime }{x}_i$.

Załóżmy teraz że f jest ściśle wypukła, i 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 rosnąca na przedziale $[0,\mathrm{\infty })$:

$\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 jeśli $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 })$), 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$.

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 z Grą w 20 pytań. Liczba pytań potrzebnych do zidentyfikowania obiektu $s_i$ wynosi co najmniej ${\log }_2\frac{1}{p(s_i)}$. Oczekiwana liczba pytań jakie musimy zadać to $\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 ta liczba pytań jest optymalna. 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ę Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 zwykle w informatyce przyjmuje się $r=2$, dlatego będziemy często pisać po prostu H na określenie $H_2$.

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

• wyliczenie wartości oczekiwanej jakiejś funkcji przy zadanym prawdopodobieństwie
• wybranie tej funkcji jako log, co być może jest najistotniejsze

Faktycznie, funkcja logarytmiczna odgrywa kluczowe znaczenie w naszej percepcji. Tak zwane prawo Webera-Fechnera głosi że odbierana przez nasze zmysły (P) zmiana bodźca (S) jest proporcjonalna nie do absolutnej, ale do procentowej 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 bogactwa. 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 równość zachodzi jedynie 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|}$.