Teoria informacji/TI Wykład 5: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:18, 11 wrz 2023

Entropia warunkowa i informacja wzajemna

Definicja [Entropia zmiennej losowej]

Jeśli $X : S \to 𝒳$ jest zmienną losową, określamy jej entropię jako

H_{r} (X) = \sum_{t \in 𝒳} p (X = t) \cdot \log_{r} \frac{1}{p (X = t)}

Innymi słowy, $H_{r} (X)$ jest równe wartości oczekiwanej

H_{r} (X) = E (\log_{r} \frac{1}{p (X)})

zmiennej losowej określonej na S, zdefiniowanej przez $s \mapsto \log_{r} \frac{1}{p (X = X (s))}$ .

Rzeczywiście,

\sum_{t \in 𝒳} p (X = t) \cdot \log_{r} \frac{1}{p (X = t)} = \sum_{t \in 𝒳} \sum_{X (s) = t} p (s) \cdot \log_{r} \frac{1}{p (X = t)}

= \sum_{s \in S} p (s) \cdot \log_{r} \frac{1}{p (X = X (s))}

Umowa notacyjna. Jeśli z kontekstu będzie wynikało, o jakich zmiennych losowych jest mowa, często będziemy pomijać nazwy zmiennych i odwoływać się wprost do ich wartości, pisząc zamiast $X = a$ po prostu a. Przykładowo będziemy pisać p(x|y) zamiast $p (X = x | Y = y)$ , $p (x \land y)$ zamiast $p ((X = x) \land (Y = y))$ itp.

Definicja [Entropia warunkowa]

Niech

A : S \to 𝒜

,

B : S \to ℬ

będą dwiema zmiennymi losowymi. Dla

b \in ℬ

określamy

H_{r} (A | b) = \sum_{a \in 𝒜} p (a | b) \cdot \log_{r} \frac{1}{p (a | b)}

i ogólnie

H_{r} (A | B) = \sum_{b \in ℬ} p (b) H_{r} (A | b)

. Powyższą wartość nazywamy entropią warunkową A od B

Zauważmy, że jeśli A i B są niezależne, to w powyższej formule $p (a | b) = a$ , a więc $H_{r} (A | B) = A$ . Z drugiej strony, $H_{r} (A | A) = 0$ . Ogólnie dla dowolnej funkcji $φ : 𝒜 \to ℬ$ mamy

H_{r} (φ (A) | A) = 0

Rzeczywiście, jeśli $p (A = a) > 0$ to $p (φ (A) = φ (a) | A = a) = 1$ , i w konsekwencji $\log_{r} \frac{1}{p (φ (A) = φ (a) | A = a)} = 0$ .

Entropia łączna. Będziemy również rozważać pary (A,B) jako jedną zmienną losową $(A, B) : S \to 𝒜 \times ℬ$ ,

(A, B) (s) = (A (s), B (s))

Prawdopodobieństwo, że ta zmienna przyjmie wartość (a,b), wynosi $p ((A, B) = (a, b)) = p ((A = a) \land (B = b))$ , co zapisujemy w skrócie jako $p (a \land b)$ . To prawdopodobieństwo w ogólności jest inne niż $p (a) \cdot p (b)$ . Jeśli dla dowolnych $a \in 𝒜, b \in ℬ$ $p (a \land b) = p (a) \cdot p (b)$ , mówimy że zmienne losowe A i B są niezależne.

Entropia $H_{r} (A, B)$ wprost z definicji wynosi

H_{r} (A, B) = \sum_{a \in 𝒜, b \in ℬ} p (a \land b) \cdot \log_{r} \frac{1}{p (a \land b)}

Jeśli A i B są niezależne, to

\log_{r} \frac{1}{p (A, B)} = \log_{r} \frac{1}{p (A)} + \log_{r} \frac{1}{p (B)}

Z liniowości wartości oczekiwanej dostajemy wtedy

H_{r} (A, B) = H_{r} (A) + H_{r} (B)

W ogólnym przypadku możemy udowodnić:

Twierdzenie

Dla dowolnych A i B zachodzi

H_{r} (A, B) \leq H_{r} (A) + H_{r} (B)

i równość zachodzi jedynie gdy A i B są niezależne.

Dowód

Rozpiszemy prawą stronę tak, żebyśmy mogli użyć Złotego Lematu. Użyjemy w tym celu oczywistych równości

$p (a) = \sum_{b \in ℬ} p (a \land b)$ i $p (b) = \sum_{a \in 𝒜} p (a \land b)$ .

\begin{aligned} H_{r} (A) + H_{r} (B) & = \sum_{a \in 𝒜} p (a) \log_{r} \frac{1}{p (a)} + \sum_{b \in ℬ} p (b) \log_{r} \frac{1}{p (b)} \\ = \sum_{a \in 𝒜} \sum_{b \in ℬ} p (a \land b) \log_{r} \frac{1}{p (a)} + \sum_{b \in ℬ} \sum_{a \in 𝒜} p (a \land b) \log_{r} \frac{1}{p (b)} \\ = \sum_{a \in 𝒜, b \in ℬ} p (a \land b) \log_{r} \frac{1}{p (a) p (b)} \end{aligned}

Ważne, że powyższe wyrażenie jest dobrze zdefiniowane, bo gdy $p (a) = 0$ lub $p (b) = 0$ , to również $p (a \land b) = 0$ .

Oznaczmy chwilowo

(𝒜 \times ℬ)^{+} = {(a, b) : p (a) > 0 i p (b) > 0}

Mamy wtedy

\sum_{(a, b) \in (𝒜 \times ℬ)^{+}} p (a \land b) = \sum_{(a, b) \in (𝒜 \times ℬ)^{+}} p (a) \cdot p (b) = 1

.

Używając Złotego Lematu dla $x = p (a \land b)$ , $y = p (a) \cdot p (b)$ dla wszystkich $(a, b) \in (𝒜 \times ℬ)^{+}$ otrzymujemy

\begin{aligned} H_{r} (A, B) & = \sum_{(a, b) \in (𝒜 \times ℬ)^{+}} p (a \land b) \log_{r} \frac{1}{p (a \land b)} \\ \leq \sum_{(a, b) \in (𝒜 \times ℬ)^{+}} p (a \land b) \log_{r} \frac{1}{p (a) p (b)} \\ = H_{r} (A) + H_{r} (B) \end{aligned}

Dodatkowo równość zachodzi wyłącznie wtedy, gdy

p (a \land b) = p (a) \cdot p (b)

dla wszystkich

(a, b) \in (𝒜 \times ℬ)^{+}

(czyli w ogóle dla wszystkich

a \in 𝒜, b \in ℬ

. Inaczej - wiemy już, że niezależność A i B implikuje tutaj równość.

Definicja [Informacja]

Wartość

I (A; B) = H_{r} (A) + H_{r} (B) - H_{r} (A, B)

nazywamy informacją wzajemną zmiennych A i B.

Komentarz Powyższą definicję łatwo zrozumieć w odniesieniu do Gry w 20 pytań. Przypuścmy, że mamy zidentyfikować obiekt, który jest parą (a,b), gdzie a i b są wartościami zmiennych losowych A i B. Jeśli A i B są niezależne, najlepsze co możemy zrobić to zidentyfikować niezależnie a i b. Tym samym gramy w dwie niezależne gry „pytania o a” i „pytania o b” (co odpowiada równości $H_{r} (A, B) = H_{r} (A) + H_{r} (B)$ ). Jeśli jednak A i B są zależne, możemy wykorzystać tę wzajemną informację do zmniejszenia liczby pytań.

Dla zwiększenia czytelności tekstu, od tej pory będziemy zwykle omijać dolny indeks r, pisząc H, I, itp. Wszędzie tam, gdzie nie napisano inaczej, wszystkie twierdzenia odnoszą się do przypadku dowolnego $r > 1$ . Bez utraty ogólności czytelnik może założyć r=2.

Komentarz Przekształcając definicję informacji analogicznie jak w ostatnim dowodzie, otrzymujemy:

I (A; B) = \sum_{a \in 𝒜, b \in ℬ} p (a \land b) (\log \frac{1}{p (a) p (b)} - \log \frac{1}{p (a \land b)})

W takiej postaci widać, że informacja jest pewną miarą odległości pomiędzy faktycznym rozkładem zmiennej (A;B), a jej rozkładem gdyby A i B były niezależne.

Warto zauważyć, że powyższa suma jest nieujemna, choć niektóre składniki $(\log \frac{1}{p (a) p (b)} - \log \frac{1}{p (a \land b)})$ mogą być ujemne.

Istnieje odpowiednik równości $H (A, B) = H (A) + H (B)$ , który stosuje się do zmiennych zależnych:

Fakt [Zasada łańcuchowa]

Dla dowolnych A i B zachodzi

H (A, B) = H (A | B) + H (B)

Dowód

Obliczamy:

\begin{aligned} H (A, B) & = \sum_{a \in 𝒜, b \in ℬ} p (a \land b) \cdot \log \frac{1}{p (a \land b)} \\ = \sum_{a \in 𝒜} \sum_{b \in ℬ} p (a | b) p (b) \cdot \log \frac{1}{p (a | b) p (b)} \\ = \sum_{a \in 𝒜} \sum_{b \in ℬ} p (a | b) p (b) \cdot (\log \frac{1}{p (a | b)} + \log \frac{1}{p (b)}) \\ = \sum_{b \in ℬ} p (b) \cdot \sum_{a \in 𝒜} p (a | b) \cdot \log \frac{1}{p (a | b)} + \sum_{b \in ℬ} p (b) \log \frac{1}{p (b)} \cdot \sum_{a \in 𝒜} p (a | b) \\ = H (A | B) + H (B) \end{aligned}

Używając zasady łańcuchowej, możemy wyliczać informację na różne sposoby:

I (A; B) = H (A) - H (A | B) = H (B) - H (B | A)

Kolejną rzeczą, jaką możemy zauważyć, to że $I (A; B) \leq \min {H (A), H (B)}$

Łatwo możemy też uogólnić zasadę łańcuchową na przypadek $n \geq 2$ zmiennych $A_{1}, A_{2}, \dots, A_{n}$

\begin{aligned} H (A_{1}, \dots, A_{n}) & = H (A_{1} | A_{2}, \dots, A_{n}) + H (A_{2}, \dots, A_{n}) \\ = H (A_{1} | A_{2}, \dots, A_{n}) + H (A_{2} | A_{3}, \dots, A_{n}) + H (A_{3}, \dots, A_{n}) \\ = \sum_{i = 1}^{n} H (A_{i} | A_{i + 1}, \dots, A_{n}) \end{aligned}

(przyjmujemy konwencję $H (A | \emptyset) = H (A)$ )

Bardziej wyrafinowane uogólnienie możemy uzyskać stosując entropię warunkową:

Fakt [Warunkowa zasada łańcuchowa]

Dla dowolnych A, B i C zachodzi

H (A, B | C) = H (A | B, C) + H (B | C)

Dowód

Dla dowolnego

c \in 𝒞

rozwijamy

\begin{aligned} H (A, B | c) & = \sum_{a \in 𝒜, b \in ℬ} p (a \land b | c) \cdot \log \frac{1}{p (a \land b | c)} \\ = \sum_{a, b} p (a | b \land c) \cdot p (b | c) \cdot (\log \frac{1}{p (a | b \land c)} + \log \frac{1}{p (b | c)}) \\ = \sum_{b} p (b | c) \cdot \sum_{a} p (a | b \land c) \cdot \log \frac{1}{p (a | b \land c)} + \sum_{b} p (b | c) \cdot \log \frac{1}{p (b | c)} \cdot \underset{= 1}{\underset{⏟}{\sum_{a} p (a | b \land c)}} \end{aligned}

W powyższym wyliczeniu sumy po a i b obejmują te wartości, dla których odpowiednie prawdopodobieństwa zależne są zdefiniowane ( $p (x | y)$ (nie jest określone jeśli $p (y) = 0$ ).

Używamy tu łatwego faktu, że jeśli $p (a \land b | c) > 0$ , to

p (a \land b | c) = \frac{p (a \land b \land c)}{p (c)} = \frac{p (a \land b \land c)}{p (b \land c)} \cdot \frac{p (b \land c)}{p (c)} = p (a | b \land c) \cdot p (b | c)

Uśredniając po $p (c)$ dostajemy:

\begin{aligned} H (A, B | C) & = \sum_{c \in 𝒞} p (c) \cdot H (A, B | c) \\ = \sum_{c} p (c) \cdot \sum_{b} p (b | c) \cdot \sum_{a} p (a | b \land c) \cdot \log \frac{1}{p (a | b \land c)} + \sum_{c} p (c) \cdot \sum_{b} p (b | c) \cdot \log \frac{1}{p (b | c)} \\ = \underset{= H (A | B, C)}{\underset{⏟}{\sum_{b, c} p (b \land c) \cdot \sum_{a} p (a | b \land c) \cdot \log \frac{1}{p (a | b \land c)}}} + \underset{= H (B | C)}{\underset{⏟}{\sum_{c} p (c) \cdot \sum_{b} p (b | c) \cdot \log \frac{1}{p (b | c)}}} \end{aligned}

Definicja [Informacja warunkowa]

Definiujemy informację wzajemną A i B warunkowaną przez C jako

\begin{aligned} I (A; B | C) & = H (A | C) + H (B | C) - \underset{= H (A | B, C) + H (B | C)}{\underset{⏟}{H (A, B | C)}} \\ = H (A | C) - H (A | B, C) \end{aligned}

I wreszcie, informację wzajemną A, B i C definiujemy jako:

R (A; B; C) = I (A; B) - I (A; B | C)

Łatwo sprawdzimy, że ta definicja jest rzeczywiście symetryczna, tzn. nie zależy od kolejności A, B i C:

\begin{aligned} I (A; C) - I (A; C | B) = H (A) - H (A | C) - (H (A | B) - H (A | B, C)) \\ = \underset{= I (A; B)}{\underset{⏟}{H (A) - H (A | B)}} - \underset{= I (A; B | C)}{\underset{⏟}{H (A | C) - H (A | B, C)}} \end{aligned}

Należy jednak pamiętać, że w przeciwieństwie do $I (A; B)$ i $I (A; B | C)$ , zdefiniowana powyżej $R (A; B; C)$ może mieć ujemną wartość.

Zależności pomiędzy wartościami $H (X), H (Y), H (Z), H (X, Y), H (X, Y | Z), I (X; Y), I (X; Y | Z), R (X; Y; Z)$ itd. można przedstawić w postaci diagramu:

Teoria informacji/TI Wykład 5: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:18, 11 wrz 2023

Entropia warunkowa i informacja wzajemna

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-===Entropia zależna i informacja wzajemna===
+===Entropia warunkowa i informacja wzajemna===
 {{definicja|[Entropia zmiennej losowej]|entropia2|
 Jeśli <math>X: S \to {\mathcal X}</math> jest zmienną losową, określamy jej entropię jako
-:<math>H_r (X) = \sum_{t \in {\mathcal X}} p (X = t) \cdot \log_r \frac{1}{p (X = t)}</math>}}
+<center><math>H_r (X) = \sum_{t \in {\mathcal X}} p (X = t) \cdot \log_r \frac{1}{p (X = t)}</math></center>}}
 Innymi słowy, <math>H_r(X)</math> jest równe wartości oczekiwanej
-:<math>H_r (X) = E \left( \log_r \frac{1}{p (X)} \right)</math>
+<center><math>H_r (X) = E \left( \log_r \frac{1}{p (X)} \right)</math></center>
-gdzie ''p(X) '' jest zmienną losową na ''S'' zdefiniowaną jako <math>p(X): s \mapsto p (X = X(s))</math>
+zmiennej losowej określonej na ''S'', zdefiniowanej przez <math>s \mapsto \log_r  \frac{1}{p (X = X(s))}</math>.
-:<math>\sum_{t \in {\mathcal X}} p (X = t) \cdot \log_r \frac{1}{p (X = t)} = \sum_{t \in {\mathcal X}} \sum_{X(s) = t} p(s) \cdot \frac{1}{p (X = t)} = \sum_{s \in S}  p(s) \cdot \frac{1}{p (X = X(s))}</math>
-''Umowa notacyjna'' Jeśli zmienne losowe o których mowa będą wynikały z kontekstu, często będziemy omijać zapis <math>X=a</math> i pisać po prostu ''a''. Przykładowo będziemy pisać ''p(x|y) '' zamiast <math>p(X=x|Y=y)</math>, <math>p(x \and y)</math> zamiast <math>p((X=x) \and (Y=y))</math> itp.
+Rzeczywiście,
+<center><math>\sum_{t \in {\mathcal X}} p (X = t) \cdot \log_r \frac{1}{p (X = t)} = \sum_{t \in {\mathcal X}} \sum_{X(s) = t} p(s) \cdot \log_r  \frac{1}{p (X = t)}</math></center>
-{{definicja|[Entropia zależna]|entropia_zależna| Niech <math>A : S \to {\mathcal A}</math>,<math>B : S \to {\mathcal B}</math> będą dwiema zmiennymi losowymi. Dla <math>b \in {\mathcal B}</math> określamy
-:<math>H_r (A | b) = \sum_{a \in {\mathcal A}} p(a|b) \cdot \log_r \frac{1}{p (a|b)}</math>
+<center><math>= \sum_{s \in S}  p(s) \cdot \log_r  \frac{1}{p (X = X(s))}</math></center>
+''Umowa notacyjna.'' Jeśli z kontekstu będzie wynikało, o jakich zmiennych losowych jest mowa, często będziemy pomijać nazwy zmiennych i odwoływać się wprost do ich wartości, pisząc zamiast <math>X=a</math> po prostu ''a''. Przykładowo będziemy pisać ''p(x|y) '' zamiast <math>p(X=x|Y=y)</math>, <math>p(x \wedge y)</math> zamiast <math>p((X=x) \wedge (Y=y))</math> itp.
+{{definicja|[Entropia warunkowa]|entropia_warunkowa| Niech <math>A : S \to {\mathcal A}</math>,<math>B : S \to {\mathcal B}</math> będą dwiema zmiennymi losowymi. Dla <math>b \in {\mathcal B}</math> określamy
+<center><math>H_r (A | b) = \sum_{a \in {\mathcal A}} p(a|b) \cdot \log_r \frac{1}{p (a|b)}</math></center>
 i ogólnie
-:<math>H_r (A | B) = \sum_{b \in {\mathcal B}} p(b) H_r (A | b)</math>.
+<center><math>H_r (A | B) = \sum_{b \in {\mathcal B}} p(b) H_r (A | b)</math>.</center>
-Powyższą wartość nazywamy '''entopią zależną A od B'''}}
+Powyższą wartość nazywamy '''entropią warunkową A od B'''}}
-Zauważmy że jeśli ''A'' i ''B'' są niezależne, to w powyższej formule <math>p(a|b)=a</math> a więc <math>H_r(A|B)=A</math>. Z drugiej strony <math>H_r(A|A)=0</math>. Ogólnie dla dowolnej funkcji <math>\varphi : {\mathcal A} \to  {\mathcal B}</math> mamy
+Zauważmy, że jeśli ''A'' i ''B'' są niezależne, to w powyższej formule <math>p(a|b)=a</math>, a więc <math>H_r(A|B)=A</math>. Z drugiej strony, <math>H_r(A|A)=0</math>. Ogólnie dla dowolnej funkcji <math>\varphi : {\mathcal A} \to  {\mathcal B}</math> mamy
-:<math>H_r (\varphi ( A) | A) = 0</math>
+<center><math>H_r (\varphi ( A) | A) = 0</math></center>
 Rzeczywiście, jeśli <math>p(A=a)>0</math> to <math>p (\varphi ( A) = \varphi (a) | A = a ) = 1</math>, i w konsekwencji <math>\log_r \frac{1}{p (\varphi ( A) = \varphi (a) | A = a )} = 0</math>.
-'''Entropia produktowa'''
+'''Entropia łączna.'''
 Będziemy również rozważać pary ''(A,B) '' jako jedną zmienną losową <math>(A,B): S \to {\mathcal A} \times {\mathcal B}</math>,
-:<math>(A,B) (s) = \left( A(s), B(s) \right)</math>
+<center><math>(A,B) (s) = \left( A(s), B(s) \right)</math></center>
-Prawdopodobieństwo że ta zmienna przyjmie wartość ''(a,b)'' wynosi <math>p \left( (A,B) = (a,b) \right) = p \left( (A = a) \wedge (B = b) \right)</math>, co zapisujemy w skrócie jako <math>p(a \and b)</math>. To prawdopodobieństwo w ogólności jest inne niż <math>p(a) \cdot p(b)</math>. Jeśli dla dowolnych <math>a \in {\mathcal A}, b \in {\mathcal B}</math>
-:<math>p(a \and b) = p(a) \cdot p(b)</math>,
-zmienne losowe ''A'' i ''B'' są niezależne.
+Prawdopodobieństwo, że ta zmienna przyjmie wartość ''(a,b)'', wynosi <math>p \left( (A,B) = (a,b) \right) = p \left( (A = a) \wedge (B = b) \right)</math>, co zapisujemy w skrócie jako <math>p(a \wedge b)</math>. To prawdopodobieństwo w ogólności jest inne niż <math>p(a) \cdot p(b)</math>. Jeśli dla dowolnych <math>a \in {\mathcal A}, b \in {\mathcal B}</math>
+<math>p(a \wedge b) = p(a) \cdot p(b)</math>, mówimy że zmienne losowe ''A'' i ''B'' są niezależne.
 Entropia <math>H_r(A,B)</math> wprost z definicji wynosi
-:<math>H_r (A,B) = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b) \cdot \log_r \frac{1}{p( a \wedge b)}</math>
+<center><math>H_r (A,B) = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b) \cdot \log_r \frac{1}{p( a \wedge b)}</math></center>
 Jeśli ''A'' i ''B'' są niezależne, to
-:<math>\log_r \frac{1}{p (A,B)} = \log_r \frac{1}{p (A)} + \log_r \frac{1}{p (B)}</math>
+<center><math>\log_r \frac{1}{p (A,B)} = \log_r \frac{1}{p (A)} + \log_r \frac{1}{p (B)}</math></center>
 Z liniowości wartości oczekiwanej dostajemy wtedy
-:<math>H_r (A,B) = H_r (A) + H_r (B)</math>
+<center><math>H_r (A,B) = H_r (A) + H_r (B)</math></center>
@@ Linia 52: / Linia 58: @@
-{{twierdzenie||do_produktowej|
+{{twierdzenie||do_łącznej| Dla dowolnych A i B zachodzi
-:<math>H_r (A,B) \leq H_r (A) + H_r (B)</math>
+<center><math>H_r (A,B) \leq H_r (A) + H_r (B)</math></center>
 i równość zachodzi jedynie gdy ''A'' i ''B'' są niezależne.}}
-'''Dowód'''
+{{dowod||| Rozpiszemy prawą stronę tak, żebyśmy mogli użyć Złotego Lematu. Użyjemy w tym celu oczywistych równości
-Rozpiszemy prawą stronę tak żebyśmy mogli użyć Złotego Lematu. Użyjemy w tym celu oczywistych równości <math>p(a) =\sum_{b \in {\mathcal B}} p( a \wedge b) </math> i <math>p(b) = \sum_{a \in {\mathcal A}} p( a \wedge b)</math>.
+<math>p(a) = \sum_{b \in {\mathcal B}} p( a \wedge b)</math> i <math>p(b) = \sum_{a \in {\mathcal A}} p( a \wedge b)</math>.
-<math>H_r (A) + H_r (B) = \sum_{a \in {\mathcal A}} p (a) \log_r \frac{1}{p(a)}
+<center><math>\begin{align}
-+ \sum_{b \in {\mathcal B}} p(b) \log_r \frac{1}{p(b)}</math>
+H_r (A) + H_r (B) & = \sum_{a \in {\mathcal A}} p (a) \log_r \frac{1}{p(a)}
-::<math>= \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p( a \wedge b) \log_r \frac{1}{p(a)}
++ \sum_{b \in {\mathcal B}} p(b) \log_r \frac{1}{p(b)}\\
-+ \sum_{b \in {\mathcal B}} \sum_{a \in {\mathcal A}} p( a \wedge b) \log_r \frac{1}{p(b)} </math>
+& = \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p( a \wedge b) \log_r \frac{1}{p(a)}
-::<math>= \sum_{a \in {\mathcal A}, b \in {\mathcal B}}  p( a \wedge b) \log_r \frac{1}{p(a)p(b)}</math>
++ \sum_{b \in {\mathcal B}} \sum_{a \in {\mathcal A}} p( a \wedge b) \log_r \frac{1}{p(b)}\\
+& = \sum_{a \in {\mathcal A}, b \in {\mathcal B}}  p( a \wedge b) \log_r \frac{1}{p(a)p(b)}
+\end{align}
+</math></center>
-Ważne że powyższe wyrażenie jest dobrze zdefiniowane, bo gdy <math>p(a)=0</math> lub  <math>p(b)=0</math>, to również <math>p(a \and b)=0</math>.
+Ważne, że powyższe wyrażenie jest dobrze zdefiniowane, bo gdy <math>p(a)=0</math> lub  <math>p(b)=0</math>, to również <math>p(a \wedge b)=0</math>.
 Oznaczmy chwilowo
-:<math>({\mathcal A} \times {\mathcal B})^{+} = \{ (a,b) : p(a) > 0 \mbox{ i } p(b) > 0 \}</math>
+<center><math>({\mathcal A} \times {\mathcal B})^{+} = \{ (a,b) : p(a) > 0 \mbox{ i } p(b) > 0 \}</math></center>
 Mamy wtedy
-:<math>\sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) = \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p(a)\cdot p(b)= 1</math>.
+<center><math>\sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) = \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p(a)\cdot p(b)= 1</math>.</center>
-Używając Złotego Lematu dla <math>x=p(a \and b)</math>, <math>y=p(a)\cdot p(b)</math> dla wszystkich <math>(a,b) \in ({\mathcal A} \times {\mathcal B})^{+}</math> otrzymujemy
+Używając [[Teoria informacji/TI Wykład 2#złoty|Złotego Lematu]] dla <math>x=p(a \wedge b)</math>, <math>y=p(a)\cdot p(b)</math> dla wszystkich <math>(a,b) \in ({\mathcal A} \times {\mathcal B})^{+}</math> otrzymujemy
-<math>H_r (A,B) = \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) \log_r \frac{1}{p( a \wedge b)} </math>
+<center><math>\begin{align}
-::<math>\leq \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) \log_r \frac{1}{p(a)p(b) }</math>
+H_r (A,B) & = \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) \log_r \frac{1}{p( a \wedge b)}\\
-::<math>= H_r (A) + H_r (B)</math>
+& \leq \sum_{ (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}} p( a \wedge b) \log_r \frac{1}{p(a)p(b) }\\
+& = H_r (A) + H_r (B)
+\end{align}
+</math></center>
-Dodatkowo równość zachodzi wyłącznie gdy <math>p(a \and b) = p(a) \cdot p(b)</math> dla wszystkich <math> (a,b) \in ({\mathcal A} \times {\mathcal B})^{+}</math> (czyli w ogóle dla wszystkich <math> a \in {\mathcal A}, b \in {\mathcal B}</math>. W drugą stronę, wiemy już że niezależność A i B implikuje tutaj równość.
+Dodatkowo równość zachodzi wyłącznie wtedy, gdy <math>p(a \wedge b) = p(a) \cdot p(b)</math> dla wszystkich <math>(a,b) \in ({\mathcal A} \times {\mathcal B})^{+}</math> (czyli w ogóle dla wszystkich <math>a \in {\mathcal A}, b \in {\mathcal B}</math>. Inaczej - wiemy już, że niezależność A i B implikuje tutaj równość.}}
-QED.
 {{definicja|[Informacja]|informacja|Wartość
+<center><math>I(A;B) = H_r (A) + H_r (B) - H_r (A,B)</math></center>
-<math>I(A;B) = H_r (A) + H_r (B) - H_r (A,B)</math>
 nazywamy '''informacją wzajemną''' zmiennych A i B.}}
-'''Komentarz''' Powyższę definicję łatwo zrozumieć w odniesieniu do ''Gry w 20 pytań''. Przypuścmy że mamy zidentyfikować obiekt który jest parą (a,b) gdzie a i b są wartościami zmiennych losowych A i B. Jeśli A i B są niezależne, najlepsze co możemy zrobić to zidentyfikować niezależnie a i b. Tym samym gramy w dwie niezależne gry „pytania o a” i „pytania o b” (co odpowiada równości <math>H_r (A,B) = H_r (A) + H_r (B)</math>). Jeśli jednak A i B są zależne, możemy wykorzystać tę wzajemną informację do zmniejszenia liczby pytań.
+'''Komentarz''' Powyższą definicję łatwo zrozumieć w odniesieniu do ''Gry w 20 pytań''. Przypuścmy, że mamy zidentyfikować obiekt, który jest parą (a,b), gdzie a i b są wartościami zmiennych losowych A i B. Jeśli A i B są niezależne, najlepsze co możemy zrobić to zidentyfikować niezależnie a i b. Tym samym gramy w dwie niezależne gry „pytania o a” i „pytania o b” (co odpowiada równości <math>H_r (A,B) = H_r (A) + H_r (B)</math>). Jeśli jednak A i B są zależne, możemy wykorzystać tę wzajemną informację do zmniejszenia liczby pytań.
+Dla zwiększenia czytelności tekstu, od tej pory będziemy zwykle omijać dolny indeks r, pisząc H, I, itp. Wszędzie tam, gdzie nie napisano inaczej, wszystkie twierdzenia odnoszą się do przypadku dowolnego <math>r>1</math>. Bez utraty ogólności czytelnik może założyć r=2.
-Dla zwiększenia czytelności tekstu, od tej poty będziemy zwykle omijać dolny indeks r, pisząc H, I, itp. Wszędzie tam gdzie nie napisano inaczej, wszystkie twierdzenia odnoszą się do przypadku dowolnego <math>r>1</math>. Bez utraty ogólności czytelnik może założyć r=2.
 '''Komentarz''' Przekształcając definicję informacji analogicznie jak w ostatnim dowodzie, otrzymujemy:
+<center><math>I(A;B) = \sum_{a \in {\mathcal A}, b \in {\mathcal B}}  p( a \wedge b) \left( \log  \frac{1}{p(a)p(b) } - \log  \frac{1}{p( a \wedge b)} \right)</math></center>
-<math>I(A;B) = \sum_{a \in {\mathcal A}, b \in {\mathcal B}}  p( a \wedge b) \left( \log  \frac{1}{p(a)p(b) } - \log  \frac{1}{p( a \wedge b)} \right)</math>
+W takiej postaci widać, że informacja jest pewną miarą odległości pomiędzy faktycznym rozkładem zmiennej (A;B), a jej rozkładem gdyby A i B były niezależne.
-W takiej postaci widać że informacja jest pewną miarą odległości pomiędzy faktycznym rozkładem zmiennej (A;B), a jej rozkładem gdyby A i B były niezależne.
-Warto zauważyć że powyższa suma jest nieujemna, choć niektóre składniki <math>\left( \log  \frac{1}{p(a)p(b) } - \log  \frac{1}{p( a \wedge b)} \right)</math> mogą być ujemne.
+Warto zauważyć, że powyższa suma jest nieujemna, choć niektóre składniki <math>\left( \log  \frac{1}{p(a)p(b) } - \log  \frac{1}{p( a \wedge b)} \right)</math> mogą być ujemne.
@@ Linia 107: / Linia 114: @@
-{{fakt|[Zasada łańcuchowa]|łańcuch|
+{{fakt|[Zasada łańcuchowa]|łańcuch| Dla dowolnych A i B zachodzi
+<center><math>H(A,B)=H(A|B)+H(B)</math></center>}}
-<math>H(A,B)=H(A|B)+H(B)</math>}}
-'''Dowód''' Obliczamy:
-<math>H  (A,B) = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b)  \cdot \log  \frac{1}{p( a \wedge b)}</math>
-::<math>= \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p(a|b) p(b)
-\cdot \log  \frac{1}{p(a|b) p(b)} </math>
-::<math>= \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p(a|b) p(b)
-\cdot \left( \log  \frac{1}{p(a|b)}  +  \log  \frac{1}{p(b)} \right) </math>
-::<math>= \sum_{b \in {\mathcal B}}  p(b) \cdot \sum_{a \in {\mathcal A}}
-p(a|b) \cdot \log  \frac{1}{p(a|b)} + \sum_{b \in {\mathcal B}} p(b) \log  \frac{1}{p(b)} \cdot \sum_{a \in {\mathcal A}}  p(a|b) </math>
-::<math>= H(A|B) + H(B) </math>
+{{dowod||dw_łańcuch|Obliczamy:
-QED.
+<center><math>\begin{align}
+H(A,B) & = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b)  \cdot \log  \frac{1}{p( a \wedge b)}\\
+& = \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p(a|b) p(b) \cdot \log  \frac{1}{p(a|b) p(b)} \\
+& = \sum_{a \in {\mathcal A}}  \sum_{b \in {\mathcal B}} p(a|b) p(b) \cdot \left( \log  \frac{1}{p(a|b)}  +  \log  \frac{1}{p(b)} \right)\\
+& = \sum_{b \in {\mathcal B}}  p(b) \cdot \sum_{a \in {\mathcal A}} p(a|b) \cdot \log  \frac{1}{p(a|b)} + \sum_{b \in {\mathcal B}} p(b) \log  \frac{1}{p(b)} \cdot \sum_{a \in {\mathcal A}}  p(a|b) \\
+& = H(A|B) + H(B)
+\end{align}
+</math></center>}}
 Używając zasady łańcuchowej, możemy wyliczać informację na różne sposoby:
-<math>I(A;B)=H(A)-H(A|B)=H(B)-H(B|A)</math>
+<center><math>I(A;B)=H(A)-H(A|B)=H(B)-H(B|A)</math></center>
-Kolejną rzeczą jaką możemy zauważyć to <math>I(A;B) \leq \min \{H(A), H(B)\}</math>
+Kolejną rzeczą, jaką możemy zauważyć, to że <math>I(A;B) \leq \min \{H(A), H(B)\}</math>
 Łatwo możemy też uogólnić zasadę łańcuchową na przypadek <math>n \ge 2</math> zmiennych <math>A_1, A_2, \ldots , A_n</math>
-<math>H(A_1, \ldots , A_n ) = H(A_1 | A_2, \ldots , A_n ) + H(A_2, \ldots , A_n ) </math>
+<center><math>\begin{align}
-::<math>=H(A_1 | A_2, \ldots , A_n ) + H(A_2 | A_3 , \ldots , A_n) + H(A_3, \ldots , A_n)</math>
+H(A_1, \ldots , A_n ) & = H(A_1 | A_2, \ldots , A_n ) + H(A_2, \ldots , A_n ) \\
+& = H(A_1 | A_2, \ldots , A_n ) + H(A_2 | A_3 , \ldots , A_n) + H(A_3, \ldots , A_n)\\
-::<math>= \sum_{i = 1}^n H(A_i | A_{i+1} , \ldots , A_n) </math>
+& = \sum_{i = 1}^n H(A_i | A_{i+1} , \ldots , A_n)
+\end{align}
-(przyjmujemy konwencję <math>H(A|\emptyset)=A</math>)
+</math></center>
-Bardziej wyrafinowane uogólnienie możemy uzyskać stosując entropię zależną:
-{{fakt|[Zależna zasada łańcuchowa]|łańcuch2|
-<math>H(A,B|C)=H(A|B,C)+H(B|C)</math>}}
-'''Dowód''' Mamy:
-<math>H  (A,B | c)= \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b | c)  \cdot \log  \frac{1}{p( a \wedge b| c )}</math>
-::<math>= \sum_{a, b} p (a | b \wedge c) \cdot p(b|c) \cdot \left( \log  \frac{1}{p (a | b \wedge c)} + \log  \frac{1}{p (b|c) } \right) </math>
-::<math>= \sum_{b}  p(b|c) \cdot \sum_{a} p (a | b \wedge c) \cdot \log  \frac{1}{p (a | b \wedge c)} + \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) } \cdot \underbrace{\sum_{a} p (a | b \wedge c)}_{1}</math>
-W powyższym wyliczeniu sumy po a i b obejmują te wartości, dla których odpowiednie prawdopodobieństwa zależne są zdefiniowane (p(x|y) nie jest określone jeśli p(y)=0). Używamy tu łatwego faktu, że jeśli <math>p(a \and b|c)>0</math>, to
-:<math>p ( a \wedge b | c) = \frac{ p(a \wedge b \wedge c)}{p( c)}= \frac{ p(a \wedge b \wedge c)}{ p (b \wedge c)} \cdot \frac{p (b \wedge c)}{p(c)} = p (a | b \wedge c) \cdot p(b|c)</math>
-Uśredniając po p(c) dostajemy:
-<math>H  (A,B | C) = \sum_{c \in {\mathcal C}} p(c) \cdot H  (A,B | c) </math>
-::<math>= \sum_{c}  p(c) \cdot \sum_{b}  p(b|c) \cdot \sum_{a} p (a | b \wedge c)
-\cdot \log  \frac{1}{p (a | b \wedge c)} + \sum_{c}  p(c) \cdot \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) } </math>
-::<math>= \underbrace{\sum_{b,c} p(b \wedge c) \cdot \sum_{a} p (a | b \wedge c) \cdot \log  \frac{1}{p (a | b \wedge c)}}_{H(A| B,C)} + \underbrace{\sum_{c} p(c)  \cdot \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) }}_{H (B | C)}</math>
+(przyjmujemy konwencję <math>H(A|\emptyset)=H(A)</math>)
-QED.
+Bardziej wyrafinowane uogólnienie możemy uzyskać stosując entropię warunkową:
-Czytelnik może teraz łatwo pokazać że:
-:<math>H  (A,B |C) \leq H  (A|C) +  H  (B|C) </math>
+{{fakt|[Warunkowa zasada łańcuchowa]|łańcuch2|Dla dowolnych A, B i C zachodzi
+<center><math>H(A,B|C)=H(A|B,C)+H(B|C)</math></center>}}
-i równość zachodzi wtedy i tylko wtedy gdy A i B są ''niezależne w odniesieniu do C'', czyli
+{{dowod||dw_łańcuch2|Dla dowolnego <math>c \in \mathcal{C}</math> rozwijamy
-:<math>p (A = a \wedge B = b | C = c) = p (A = a | C = c) \cdot p (B = b | C = c)</math>
+<center><math>\begin{align}
+H(A,B| c) & = \sum_{a \in {\mathcal A}, b \in {\mathcal B}} p ( a \wedge b | c)  \cdot \log  \frac{1}{p( a \wedge b| c )}\\
+& = \sum_{a, b} p (a | b \wedge c) \cdot p(b|c) \cdot \left( \log  \frac{1}{p (a | b \wedge c)} + \log  \frac{1}{p (b|c) } \right)\\
+& = \sum_{b}  p(b|c) \cdot \sum_{a} p (a | b \wedge c) \cdot \log  \frac{1}{p (a | b \wedge c)} + \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) } \cdot \underbrace{\sum_{a} p (a | b \wedge c)}_{=1}
+\end{align}
+</math></center>
-(dowód na ćwiczeniach)
+W powyższym wyliczeniu sumy po a i b obejmują te wartości, dla których odpowiednie prawdopodobieństwa zależne są zdefiniowane (<math>p(x|y)</math> (nie jest określone jeśli <math>p(y)=0</math>).
+Używamy tu łatwego faktu, że jeśli <math>p(a \wedge b|c)>0</math>, to
+<center><math>p ( a \wedge b | c) = \frac{ p(a \wedge b \wedge c)}{p( c)}= \frac{ p(a \wedge b \wedge c)}{ p (b \wedge c)} \cdot \frac{p (b \wedge c)}{p(c)} = p (a | b \wedge c) \cdot p(b|c)</math></center>
-{{definicja|[Informacja zależna]|inf_zależna|
+Uśredniając po <math>p(c)</math> dostajemy:
-Definiujemy '''informację wzajemną A i B w odniesieniu do C''' jako
+<center><math>\begin{align}
+H(A,B|C) & = \sum_{c \in {\mathcal C}} p(c) \cdot H  (A,B | c)\\
+& = \sum_{c}  p(c) \cdot \sum_{b}  p(b|c) \cdot \sum_{a} p (a | b \wedge c)
+\cdot \log  \frac{1}{p (a | b \wedge c)} + \sum_{c}  p(c) \cdot \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) }\\
+& = \underbrace{\sum_{b,c} p(b \wedge c) \cdot \sum_{a} p (a | b \wedge c) \cdot \log  \frac{1}{p (a | b \wedge c)}}_{=H(A| B,C)} + \underbrace{\sum_{c} p(c)  \cdot \sum_{b}  p(b|c) \cdot \log  \frac{1}{p (b|c) }}_{=H (B | C)}
+\end{align}
+</math></center>}}
-<math> I(A;B |C) = H(A |C) + H(B|C) - \underbrace{H(A,B|C)}_{H(A|B,C) + H(B|C)}</math>
-::<math>= H(A |C) - H(A|B,C)</math>
-I wreszcie, ''informacją wzajemną A, B i C'' definiujemy jako:
+{{definicja|[Informacja warunkowa]|inf_warunkowa|
+Definiujemy '''informację wzajemną A i B warunkowaną przez C''' jako
+<center><math>\begin{align}
+I(A;B |C) & = H(A |C) + H(B|C) - \underbrace{H(A,B|C)}_{=H(A|B,C) + H(B|C)} \\
+& = H(A |C) - H(A|B,C)
+\end{align}
+</math></center>
-:<math>R(A;B;C)=I(A;B)-I(A;B)|C)</math>}}
+I wreszcie, '''informację wzajemną A, B i C''' definiujemy jako:
-Łatwo sprawdzimy że ta definicja jest rzeczywiście symetryczna, tzn nie zależy od kolejności A, B i C:
+<center><math>R(A;B;C)=I(A;B)-I(A;B|C)</math></center>}}
-<math>I(A;C) - I(A;C|B) = H(A) - H(A|C) - \left( H (A|B) - H(A| B,C) \right) </math>
+Łatwo sprawdzimy, że ta definicja jest rzeczywiście symetryczna, tzn. nie zależy od kolejności A, B i C:
-::<math>= \underbrace{H(A) - H (A|B)}_{I(A;B)} - \underbrace{ H(A|C) -  H(A| B,C)}_{ I(A;B |C)}</math>
+<center><math>\begin{align}
+I(A;C) - I(A;C|B) = H(A) - H(A|C) - \left( H (A|B) - H(A| B,C) \right) \\
+& = \underbrace{H(A) - H (A|B)}_{=I(A;B)} - \underbrace{ H(A|C) -  H(A| B,C)}_{=I(A;B |C)}
+\end{align}
+</math></center>
-Należy jednak pamiętać że w przeciwieństwie do I(A;B) i I(A;B|C), zdefiniowana powyżej R(A;B;C) może mieć '''ujemną''' wartość.
+Należy jednak pamiętać, że w przeciwieństwie do <math>I(A;B)</math> i <math>I(A;B|C)</math>, zdefiniowana powyżej <math>R(A;B;C)</math> może mieć '''ujemną''' wartość.
-Zależności pomiędzy wartościami H(X), H(Y), H(Z), H(X,Y), H(X,Y|Z), I(X;Y), I(X;Y|Z), R(X;Y;Z) itd. można przedstawić w postaci diagramu:
+Zależności pomiędzy wartościami <math>H(X), H(Y), H(Z), H(X,Y), H(X,Y|Z), I(X;Y), I(X;Y|Z), R(X;Y;Z)</math> itd. można przedstawić w postaci diagramu:
-[[Grafika:Venn4.png]]
+<center>[[Grafika:Venn4.png|300px]]</center>