Aufgaben:Aufgabe 3.3: Entropie von Ternärgrößen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 68: Zeile 68:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;<u>Beide Aussagen sind richtig.</u> Setzt man <i>p</i><sub>3</sub> = 0 und formal <i>p</i><sub>1</sub> = <i>p</i> &nbsp;&#8658;&nbsp; <i>p</i><sub>2</sub> = 1 &ndash; <i>p</i>, so ergibt sich die binäre Entropiefunktion
+
'''(1)'''&nbsp; <u>Beide Aussagen sind richtig.</u> Setzt man <i>p</i><sub>3</sub> = 0 und formal <i>p</i><sub>1</sub> = <i>p</i> &nbsp;&#8658;&nbsp; <i>p</i><sub>2</sub> = 1 &ndash; <i>p</i>, so ergibt sich die binäre Entropiefunktion
 
:$$H_{\rm bin}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
 
:$$H_{\rm bin}(p) =  p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +  
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
 
  (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$
  
<b>2.</b>&nbsp;&nbsp;Man kann die binäre Entropiefunktion wegen log<sub>2</sub>(<i>x</i>) = ln(<i>x</i>)/ln(2) auch in die folgende Form bringen:
+
'''(2)'''&nbsp; Man kann die binäre Entropiefunktion wegen log<sub>2</sub>(<i>x</i>) = ln(<i>x</i>)/ln(2) auch in die folgende Form bringen:
 
:$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \left [  p \cdot {\rm ln}(p)  +  
 
:$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \left [  p \cdot {\rm ln}(p)  +  
 
  (1-p) \cdot {\rm ln}(1-p) \right ] \hspace{0.05cm}.$$
 
  (1-p) \cdot {\rm ln}(1-p) \right ] \hspace{0.05cm}.$$
Die erste Ableitung führt zum Ergebnis
+
*Die erste Ableitung führt zum Ergebnis
:$$\frac {\rm dH_{\rm bin}(p)}{\rm dp} \hspace{0.15cm} = \hspace{0.15cm} \frac{-1}{{\rm ln}(2)} \cdot \left [  {\rm ln}(p)  + p \cdot \frac{1}{p} -  
+
:$$\frac {{\rm d}H_{\rm bin}(p)}{{\rm d}p} = \frac{-1}{{\rm ln}(2)} \cdot \left [  {\rm ln}(p)  + p \cdot \frac{1}{p} -  
   {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \right ] =\\
+
   {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \right ] =
=  \hspace{0.15cm} \frac{1}{{\rm ln}(2)} \cdot \left [ {\rm ln}(1-p) - {\rm ln}(p)  \right ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
+
\frac{1}{{\rm ln}(2)} \cdot \left [ {\rm ln}(1-p) - {\rm ln}(p)  \right ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert <i>p</i> = 0.5, der zum Maximum der Entropiefunktion führt: <i>H</i><sub>bin</sub>(<i>p</i> = 0.5) = 1 bit &nbsp;&#8658;&nbsp; Lösungsvorschlag 2 ist falsch..
+
*Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert <i>p</i> = 0.5, der zum Maximum der Entropiefunktion führt: <i>H</i><sub>bin</sub>(<i>p</i> = 0.5) = 1 bit &nbsp;&#8658;&nbsp; Lösungsvorschlag 2 ist falsch.
 
+
*Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
+
:$$\frac {{\rm d}^2H_{\rm bin}(p)}{{\rm d}p^2} = \frac{1}{{\rm ln}(2)} \cdot \left
:$$\frac {\rm d^2H_{\rm bin}(p)}{\rm dp^2} = \frac{1}{{\rm ln}(2)} \cdot \left
 
 
  [  \frac{-1}{1-p}  - \frac{1}{p}    \right ] =
 
  [  \frac{-1}{1-p}  - \frac{1}{p}    \right ] =
 
\frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)}  \hspace{0.05cm}.$$
 
\frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)}  \hspace{0.05cm}.$$
Diese Funktion ist im gesamten Definitionsgebiet 0 &#8804; <i>p</i> &#8804; 1 negativ &nbsp;&#8658;&nbsp; <i>H</i><sub>bin</sub>(<i>p</i>) ist konkav &nbsp;&#8658;&nbsp; Richtig ist dementsprechend (allein) der <u>Lösungsvorschlag 1</u>.
+
*Diese Funktion ist im gesamten Definitionsgebiet 0 &#8804; <i>p</i> &#8804; 1 negativ &nbsp;&#8658;&nbsp; <i>H</i><sub>bin</sub>(<i>p</i>) ist konkav &nbsp;&#8658;&nbsp; Richtig ist allein der <u>Lösungsvorschlag 1</u>.
 
 
<b>3.</b>&nbsp;&nbsp;Richtig sind hier die <u>Aussagen 1 und 2</u>:
 
  
:* Für <i>p</i> = 0 erhält man die Wahrscheinlichkeitsfunktion <i>P<sub>X</sub></i>(<i>X</i>) = [0, 1/2, 1/2] &nbsp;&#8658;&nbsp; <i>H</i>(<i>X</i>) = 1 bit.
 
  
:* Das Maximum unter der Voraussetzung <i>p</i><sub>3</sub> = 1/2 ergibt sich für <i>p</i><sub>1</sub> = <i>p</i><sub>2</sub> = 1/4:
+
[[Datei:P_ID2756__Inf_A_3_3_ML.png|right|Drei Entropiefunktionen mit <i>M</i> = 3]]
 +
'''(3)'''&nbsp; Richtig sind hier die <u>Aussagen 1 und 2</u>:
 +
* Für <i>p</i> = 0 erhält man die Wahrscheinlichkeitsfunktion <i>P<sub>X</sub></i>(<i>X</i>) = [0, 1/2, 1/2] &nbsp;&#8658;&nbsp; <i>H</i>(<i>X</i>) = 1 bit.
 +
* Das Maximum unter der Voraussetzung <i>p</i><sub>3</sub> = 1/2 ergibt sich für <i>p</i><sub>1</sub> = <i>p</i><sub>2</sub> = 1/4:
 
:$$P_X(X) = [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm}]
 
:$$P_X(X) = [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm}]
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
{\rm Max} [H_{\rm B}(p)] = 1.5\,{\rm bit}
 
{\rm Max} [H_{\rm B}(p)] = 1.5\,{\rm bit}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
[[Datei:P_ID2756__Inf_A_3_3_ML.png|right|]]
+
*In kompakter Form lässt sich <i>H</i><sub>B</sub>(<i>p</i>) mit der Einschränkung 0 &#8804; <i>p</i> &#8804; 1/2 wie folgt darstellen:
In kompakter Form lässt sich <i>H</i><sub>B</sub>(<i>p</i>) mit der Einschränkung 0 &#8804; <i>p</i> &#8804; 1/2 wie folgt darstellen:
 
 
:$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p)  
 
:$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p)  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
<b>4.</b>&nbsp;&nbsp;Richtig sind die <u> erste und letzte Aussage</u>. Der grüne Kurvenzug beinhaltet mit <i>p</i> = 1/3 auch die Gleichverteilung aller Wahrscheinlichkeiten &#8658; Max[<i>H</i><sub>G</sub>(<i>p</i>)] = log<sub>2</sub> (3) bit. Allgemein lässt sich der gesamte Kurvenverlauf im Bereich 0 &#8804; <i>p</i> &#8804; 2/3 wie folgt ausdrücken:
+
'''(4)'''&nbsp; Richtig sind die <u> erste und letzte Aussage</u>:
 +
* Der grüne Kurvenzug beinhaltet mit <i>p</i> = 1/3 auch die Gleichverteilung aller Wahrscheinlichkeiten &#8658; Max[<i>H</i><sub>G</sub>(<i>p</i>)] = log<sub>2</sub> (3) bit. Allgemein lässt sich der gesamte Kurvenverlauf im Bereich 0 &#8804; <i>p</i> &#8804; 2/3 wie folgt ausdrücken:
 
:$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2)  
 
:$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2)  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
+
*Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
 
:$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3)
 
:$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3)
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit}
 
H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Der Lösungsvorschlag 2 ist hier somit falsch. Zum gleichen Ergebnis gelangt man über die Gleichung
+
*Der zweite Lösungsvorschlag 2 ist somit falsch. Zum gleichen Ergebnis gelangt man über die Gleichung
 
:$$H_{\rm G}(p = 0) = {1}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3)
 
:$$H_{\rm G}(p = 0) = {1}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3)
 
+{2}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot  
 
+{2}/{3} \cdot  {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot  
 
{\rm log}_2 \hspace{0.01cm} (2)
 
{\rm log}_2 \hspace{0.01cm} (2)
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Die Grafik zeigt nochmals die Ausgangsgrafik, aber nun mit Bemaßungen.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 30. Mai 2017, 13:38 Uhr

Vorgegebene Entropiefunktionen

Rechts sehen Sie die Entropiefunktionen $H_{\rm R}(p)$, $H_{\rm B}(p)$ und $H_{\rm G}(p)$, wobei „R” für „Rot” steht, „B” für „Blau” und „G” für „Grün” . Die Wahrscheinlichkeitsfunktionen lauten für alle Zufallsgrößen:

$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, p_2\hspace{0.05cm}, p_3\hspace{0.05cm}]\hspace{0.3cm}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} |X| = 3\hspace{0.05cm}.$$

Es gilt der Zusammenhang $p_1 = p$ und $p_2 = 1 - p_3- p$.

Die Wahrscheinlichkeitsfunktion einer Zufallsgröße

$$X = \{\hspace{0.05cm}x_1\hspace{0.05cm}, \hspace{0.05cm} x_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.05cm} x_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.05cm} x_{M}\hspace{0.05cm}\}$$

mit dem Symbolumfang $|X| = M$ lautet allgemein:

$$P_X(X) = [\hspace{0.05cm}p_1\hspace{0.05cm}, \hspace{0.05cm} p_2\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.1cm} ,\hspace{0.05cm} p_{\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.05cm} p_{M}\hspace{0.05cm}]\hspace{0.05cm}.$$

Die Entropie (Unsicherheit) dieser Zufallsgröße berechnet sich entsprechend der Gleichung

$$H(X) = {\rm E} \left [\log_2 \hspace{0.05cm} {1}/{P_X(X)} \right ]\hspace{0.05cm},$$

und liegt stets im Bereich $0 \le H(X) \le \log_2 \hspace{0.05cm} |X|$.

Die untere Schranke $H(X) = 0$ ergibt sich, wenn eine beliebige Wahrscheinlichkeit $p_\mu = 1$ ist und alle anderen $0$ sind. Die obere Schranke soll hier wie in der Vorlesung „Information Theory” von Gerhard Kramer an der TU München hergeleitet werden:

Obere Abschätzung für den natürlichen Logarithmus
  • Durch Erweiterung obiger Gleichung um $X|$ in Zähler und Nenner erhält man unter Verwendung von $\log_2 \hspace{0.05cm}x= \ln(x)/ln(2)$:
$$H(X) = \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [{\rm ln} \hspace{0.1cm} \frac{1}{|X| \cdot P_X(X)} \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
  • Wie aus nebenstehender Grafik hervorgeht, gilt die Abschätzung $\ln(x) \le x-1$ mit der Identität für $x=1$. Somit kann geschrieben werden:
$$H(X) \le \frac{1}{{\rm ln}(2)}\cdot {\rm E} \left [\frac{1}{|X| \cdot P_X(X)} -1 \right ] + {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$
  • In Aufgabe 3.2 wurde für den Fall$p_\mu \ne 0$ für alle $\mu$ der Erwartungswert ${\rm E} [\log_2 \hspace{0.05cm} {1}/{P_X(X)}] =|X|$ berechnet. Damit verschwindet der erste Term und man erhält das bekannte Ergebnis:
$$H(X) \le {\rm log}_2 \hspace{0.1cm}|X| \hspace{0.05cm}.$$

Hinweise:

$$H_{\rm bin}(p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$


Fragebogen

1

Welche Aussagen gelten für die rote Entropiefunktion $H_{\rm R}(p)$?

$H_{\rm R}(p)$ ergibt sich z.B. mit $p_1 = p$, $p_2 = 1- p$ und $p_3 = 0$.
$H_{\rm R}(p)$ ist identisch mit der binären Entropiefunktion $H_{\rm bin}(p)$.

2

Welche Eigenschaften weist die binäre Entropiefunktion $H_{\rm bin}(p)$auf?

$H_{\rm bin}(p)$ ist konkav hinsichtlich des Parameters $p$.
Es gilt $\text {Max} [H_{\rm bin}(p)] = 2 \ \rm bit$.

3

Welche Aussagen gelten für die blaue Entropiefunktion $H_{\rm B}(p)$?

HB(p) ergibt sich beispielsweise mit $p_1 = p$, $p_2 = 1/2- p$ und $p_3 = 1/2$.
Es gilt $H_{\rm B}(p = 0)= 1 \ \rm bit.$
Es gilt Es gilt $\text {Max} [H_{\rm B}(p)] = \log_2 \hspace{0.1cm} (3) \ \rm bit$.

4

Welche Aussagen gelten für die grüne Entropiefunktion $H_{\rm G}(p)$?

$H_{\rm G}(p)$ ergibt sich beispielsweise mit $p_1 = p$, $p_2 = 2/3- p$ und $p_3 = 1/3$.
Es gilt $H_{\rm G}(p = 0)= 1 \ \rm bit.$
Es gilt $\text {Max} [H_{\rm G}(p)] = \log_2 \hspace{0.1cm} (3) \ \rm bit$.


Musterlösung

(1)  Beide Aussagen sind richtig. Setzt man p3 = 0 und formal p1 = p  ⇒  p2 = 1 – p, so ergibt sich die binäre Entropiefunktion

$$H_{\rm bin}(p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} \hspace{0.05cm}.$$

(2)  Man kann die binäre Entropiefunktion wegen log2(x) = ln(x)/ln(2) auch in die folgende Form bringen:

$$H_{\rm bin}(p) = \frac{-1}{{\rm ln}(2)} \cdot \left [ p \cdot {\rm ln}(p) + (1-p) \cdot {\rm ln}(1-p) \right ] \hspace{0.05cm}.$$
  • Die erste Ableitung führt zum Ergebnis
$$\frac {{\rm d}H_{\rm bin}(p)}{{\rm d}p} = \frac{-1}{{\rm ln}(2)} \cdot \left [ {\rm ln}(p) + p \cdot \frac{1}{p} - {\rm ln}(1-p) - (1-p) \cdot \frac{1}{1-p} \right ] = \frac{1}{{\rm ln}(2)} \cdot \left [ {\rm ln}(1-p) - {\rm ln}(p) \right ] = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{p} \hspace{0.05cm}.$$
  • Durch Nullsetzen dieser Ableitung erhält man den Abszissenwert p = 0.5, der zum Maximum der Entropiefunktion führt: Hbin(p = 0.5) = 1 bit  ⇒  Lösungsvorschlag 2 ist falsch.
  • Durch nochmaliges Differenzieren erhält man für die zweite Ableitung:
$$\frac {{\rm d}^2H_{\rm bin}(p)}{{\rm d}p^2} = \frac{1}{{\rm ln}(2)} \cdot \left [ \frac{-1}{1-p} - \frac{1}{p} \right ] = \frac{-1}{{\rm ln}(2) \cdot p \cdot (1-p)} \hspace{0.05cm}.$$
  • Diese Funktion ist im gesamten Definitionsgebiet 0 ≤ p ≤ 1 negativ  ⇒  Hbin(p) ist konkav  ⇒  Richtig ist allein der Lösungsvorschlag 1.


Drei Entropiefunktionen mit M = 3

(3)  Richtig sind hier die Aussagen 1 und 2:

  • Für p = 0 erhält man die Wahrscheinlichkeitsfunktion PX(X) = [0, 1/2, 1/2]  ⇒  H(X) = 1 bit.
  • Das Maximum unter der Voraussetzung p3 = 1/2 ergibt sich für p1 = p2 = 1/4:
$$P_X(X) = [\hspace{0.05cm}1/4\hspace{0.05cm}, \hspace{0.05cm} 1/4\hspace{0.05cm},\hspace{0.05cm} 1/2 \hspace{0.05cm}] \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Max} [H_{\rm B}(p)] = 1.5\,{\rm bit} \hspace{0.05cm}.$$
  • In kompakter Form lässt sich HB(p) mit der Einschränkung 0 ≤ p ≤ 1/2 wie folgt darstellen:
$$H_{\rm B}(p) = 1.0\,{\rm bit} + {1}/{2} \cdot H_{\rm bin}(2p) \hspace{0.05cm}.$$

(4)  Richtig sind die erste und letzte Aussage:

  • Der grüne Kurvenzug beinhaltet mit p = 1/3 auch die Gleichverteilung aller Wahrscheinlichkeiten ⇒ Max[HG(p)] = log2 (3) bit. Allgemein lässt sich der gesamte Kurvenverlauf im Bereich 0 ≤ p ≤ 2/3 wie folgt ausdrücken:
$$H_{\rm G}(p) = H_{\rm G}(p= 0) + {2}/{3} \cdot H_{\rm bin}(3p/2) \hspace{0.05cm}.$$
  • Aus der Grafik auf der Angabenseite erkennt man auch, dass folgende Bedingung erfüllt sein muss:
$$H_{\rm G}(p = 0) + {2}/{3}= {\rm log}_2 \hspace{0.01cm} (3) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_{\rm G}(p= 0) = 1.585 - 0.667 = 0.918 \,{\rm bit} \hspace{0.05cm}.$$
  • Der zweite Lösungsvorschlag 2 ist somit falsch. Zum gleichen Ergebnis gelangt man über die Gleichung
$$H_{\rm G}(p = 0) = {1}/{3} \cdot {\rm log}_2 \hspace{0.01cm} (3) +{2}/{3} \cdot {\rm log}_2 \hspace{0.01cm} (3/2) = {\rm log}_2 \hspace{0.01cm} (3) -2/3 \cdot {\rm log}_2 \hspace{0.01cm} (2) \hspace{0.05cm}.$$