Zum Inhalt springen

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Grundbegriffe der Informationstheorie (Entropie und Quellencodierungstheorem)

Weitz / HAW Hamburg35:28 39.155 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 249 Zeilen
Herunterladen
  1. in diesem video wird es um informationstheorie gehen natürlich kann ich in einem kurzen video nicht die gesamte informationstheorie
  2. aufbereiten also wird es in erster linie darum gehen die grundideen vorzustellen und als aufhänger werden wir uns mit der frage beschäftigen wie man eigentlich
  3. daten komprimieren können und was die grenzen weil solches verfahren sind dafür werden wir mit zunächst mal zwei beispiel dateien arbeiten
  4. ich habe auch us angegeben falls sie das selbst ausprobieren wollen die erste datei ist einfach eine große textdatei in der sehr viel englischer text aus dem
  5. projekt gutenberg drin ist das sind ungefähr 65 millionen breit und als zweites ein bild was ich irgendwann mal geschossen habe das ist gespeichert als
  6. bmp datei das sind auch absichtlich ungefähr 65 millionen konten diesem fall auch gut erklären warum das genauso viele sind
  7. das hat eine auflösung von 1800 x 1200 pixeln und jeder pixel verbraucht 3 byd für die drei farben rot grün und blau und jetzt ist die frage wie kann man
  8. diese dateien kleiner kriegen es soll ja um datenkompression gehen und wir schauen uns mal zwei möglichkeiten an die eine ist dass man mit der textdatei
  9. dass wir daraus ein zip-archiv machen weiß ich das noch nie gemacht haben dafür brauchen sie nicht mein programm zu installieren
  10. man kann zum beispiel in windows mit einem rechtsklick auf die datei klicken und dann auswählen ich glaube das sind ein zip-archiv und dann bekommen wir
  11. eine datei die deutlich kleiner ist also ganz grob ungefähr nur ein drittel der ursprünglichen größe hat mit dem bild kann man noch was anderes machen sie
  12. können dieses bild mit irgend einem grafikprogramm öffnen bis dann wieder abspeichern aber nicht in dem format bmp sondern zum beispiel
  13. als jpeg und wenn sie dieses bild als jpeg abspeichern dann werden sie sehen dass der platzgewinn auf der festplatte sogar noch größer ist da
  14. ist pi mal daumen die komprimierte datei nur noch ein sechstel so groß wie die originaldatei es handelt sich allerdings um zwei sehr unterschiedliche verfahren
  15. der kompression der für uns wesentliche unterschied ist dass in dem fall rechts es sich um eine sogenannte verlust behaftete kompression handelt aber
  16. vielleicht vorher noch mal ein anderer auch nicht ganz unwesentlicher unterschied beide bilddateien rechts die bnp datei und die jpeg datei kann ich
  17. mit normalen programm einfach öffnen und mehr ansehen die beiden dateien links die ursprüngliche text datei und die
  18. zip-datei unterscheiden sich die textdatei kann ich mit einem texteditor mir anschauen die zip datei muss sich erst wieder
  19. auspacken bevor ich sie mir mit einem texteditor anschauen kann aber dafür uns wesentliche unterschied ich habe eben
  20. schon mal angefangen das zu sagen es rechts findet eine verlust- behauptete komprimierung stadt das bedeutet wenn ich nur die jpeg datei habe kann ich mit
  21. deren hilfe das original die bmp dateien nicht wieder rekonstruieren das was auf der linken seite passiert ist für uns in diesem video entscheidend
  22. da handelt es sich um eine kompression bei der ich wenn ich das zip-archiv wieder auspacken die originaldatei exakt wird für bild
  23. wieder zurückbekommen wir wollen uns in diesem video nur mit verlust freier kompression beschäftigen es gibt in diesem kanal auch videos die
  24. erklären wie das auf der rechten seite funktioniert warum diese jpeg-bilder so viel kleiner als die original bilder sind aber darum soll es hier nicht gehen
  25. ok dritte beispiel datei wir werden uns eine datei ungefähr derselben größe wie die beiden vorherigen erzeugen mit einem kleinen programm das hier steht dieses
  26. programm mache ich weiter als sechseinhalb millionen zufällig ausgewählte bytes auf die festplatte zu schreiben das heißt wir haben eine
  27. dritte datei die ungefähr so groß ist wie die anderen beiden und die wollen wir auch komprimieren hier noch mal links im vergleich die
  28. textdatei und die größe der komprimierten also getippten textdatei das machen wir mit der datei randomly wir eben erzeugt haben auch dann wenn
  29. sie das zum ersten mal machen wird sie das ergebnis überraschen die rezepte datei random zip ist nicht nur nicht kleiner als das
  30. original sondern sehr großer wahrscheinlichkeit sogar größer ist als original von kompression kann also hier überhaupt keine rede sein
  31. und die frage die man sich jetzt stellen muss ist ist dieses verfahren vielleicht schlecht gibt es bessere verfahren oder gibt es hier grundsätzliche probleme
  32. also ich habe die frage mal so formuliert gibt es ein verfahren mit dem man jede datei egal wie sie aussieht verlustfrei komprimieren kann also klar
  33. machen können und wir wollen das mal ganz vorsichtig mathematisch formulieren mathematische soll das bedeuten gibt es eine initiative abbildung die jeder
  34. datei de eine andere datei die habe ich dann f von d genannt zuordnet so dass es von d zumindest niemals größer als de ist das ist ja eben bei dieser random
  35. datei passiert wir würden vielleicht gar nicht erwarten dass jede datei kleiner wird und zumindest erwarten dass sie nicht größer werden ist eben passiert
  36. ist vielleicht fragen sie sich warum da in ihr tief steht in jeck tief muss natürlich da stehen damit es ein verlustfreies verfahren ist wenn durch
  37. dieses verfahren zwei verschiedene dateien auf dieselbe datei abgebildet werden dann kann ich natürlich unmöglich beide wäre konstruieren also es muss
  38. eine induktive abbildung sein sie soll dateien abbilden auf dateien die nicht größer sind und diese bedingung wird auf jeden fall von der
  39. identität erfüllt das heißt wir brauchen gar keinen verfall überlassen sie dateien einfach so wie sie sind das war natürlich auch ein bisschen wenig darum
  40. verlangen wir auch wieder ganz ganz vorsichtig es würde uns reichen wenn zumindest eine einzige datei kleiner ist als sie vorher war und wir werden sie
  41. nicht mal das geht das kann man sich ganz leicht überlegen ich habe dazu eben ein kleines schaubild gemacht wenn sie sich zum beispiel
  42. überlegen wie viele verschiedene dateien es gibt die aus genau drei bits bestehen dann werden sie sehen dass das genau zwei hoch 3 also acht verschiedene
  43. dateien sind und wenn sie sich überlegen wie viel dateien aus genau auf ihr witz bestehen dann wenn das genau 24 also 16 parteien seien und so weiter daraus
  44. folgt dann zum beispiel dass die anzahl der verschiedenen dateien die aus drei bit oder weniger bestehen genau 20 + 21 22 23 also zwei hoch 4 - 115 ist und
  45. entsprechend so ist dieses schaubild hier gemeint also zum beispiel in den grünen ring sollen alle dateien liegen die aus genau 41 biz bestehen in dem
  46. orangen rink liegen alle dateien die auf genau 42 blitz bestehen in dem blauen ring kann die dateien die auf genau 43 will zu bestehen und so weiter
  47. und jeder ding muss nach dem was man es eben überlegt haben immer doppelt so viel fläche wieder nicht kleinere haben wenn jetzt eine einzige datei auf eine
  48. datei abgebildet wird die kleiner ist als sie selbst war dann konnte das zum beispiel so aussehen wie dass dieser rot weil hier andeutet eine datei die vorher
  49. 43 bit groß war rutscht auf ein weiterhin liegenden ring zum beispiel auf den ring prodi 42 bilddateien liegen das heißt
  50. diese datei wäre durch unser verfahren ein bild kleiner geworden aber wir haben uns ja immer schon überlegt dass der orange ring zusammen mit allen darin
  51. alle dateien auf nimmt die 42 bit oder weniger haben und da ist eigentlich kein platz mehr das heißt wenn diese rote datei dann
  52. nach innen rutscht dann muss irgendeine andere dateien nach außen rutschen denn sonst hätten wir keine inaktiven abbildung mehr das heißt in dem moment
  53. wo wir so einen verfahren haben wir das hier durch diese abbildung f beschrieben ist es ist unmöglich dass sie in die aktiv sein kann wenn tatsächlich auch
  54. nur eine einzige datei kleiner würde das bedeutet die antwort auf die frage wie wir am anfang gestellt haben ist es kann so ein für jede datei funktionierendes
  55. komprimierungsverfahren nicht geben und wir wollen es jetzt im rest des videos überlegen was denn der grund dafür ist dass das nicht geht was sind die grenzen
  56. kann man den dateien irgendwie ansehen dass sie nicht komprimiert sind und so weiter dafür noch mal ein anderes kleines experiment
  57. ich habe diese dateien damit der befohlen gearbeitet haben durch ein kleines selbst geschrieben das an
  58. die programm geschickt das können sie auch einfach selbst schreiben oder sich auf meiner website herunterladen dafür werden die 6,5 millionen byd die
  59. weder haben in lauter paket der a 24 bit zerlegt und dann schauen wir in diese bit pakete jeweils rein und zählen wie viele von diesen blitz einzeln sind in
  60. manchen paketen wird gar kein bild 1 seien in manchen werden zum beispiel 11 1 1 sein und in manchen werden die höchste zahl die mögliches 24 sein
  61. das ergebnis tragen wir in einem staat diagramm auf sowie hier und sie sehen wir haben eine schöne gleichmäßige kurve und wenn sie kurz nachdenken dass das ja
  62. zufällig erzeugt war dann werden sie darauf kommen dass das was wir hier sehen eine biene mira verteilung sein muss im wesentlichen das bedeutet wenn
  63. wir eine genügend große datei haben und eine genügend vereine unterteilung und dann kommt hier im prinzip so was wie eine kurve raus daran kann man sozusagen
  64. erkennen dass diese datei zufällig erzeugte ganz grob gesagt wenn wir uns stattdessen die genauso große textdatei anschauen dann bekommen natürlich nicht
  65. so eine schöne gleichmäßige kurve raus weil diese daten ja auch nicht zufällig sind dass die dateien nicht so zufällig verteilt aussehen dass wir hier keine
  66. gaus kurve haben hat verschiedene gründe es liegt zum beispiel daran dass texte auf eine bestimmte art gespeichert werden für jeden buchstaben wenn diese
  67. maske format immer 8 bit verwendet und bestimmte 8 bit muster kommen häufiger vor als andere darum bekommen wir halt eine im
  68. vergleich zu grün unregelmäßig aussehen der kurve das überraschende was man am anfang auch nicht unbedingt erwartet ist wenn ich diese datei jetzt mit dem zip
  69. programm verpackt und dann analysiere dann bekommt wieder etwas was fast wie meine ursprüngliche kurve aussieht für die rennen datei das heißt das
  70. zip-archiv sieht so aus als wäre die datei zufällig erzeugt wurden und noch etwas weiteres wenn sie diese datei beck zieht jetzt nehmen und die
  71. nochmals die viren dann werden sie sehen dass das was da rauskommt wieder wie schon bei der rennen datei nicht kleiner sondern sogar bis
  72. größer ist das original ist das heißt wir können die nicht nochmal komprimieren und nochmal komprimieren und nochmal komprimieren was ja
  73. irgendwie auch logisch ist und das hier nie aufhören das passt zu dem was wir uns vorher schon über die grenzen des komprimieren überlegt haben
  74. ich habe ja mal ein paar vage formulierte hypothesen aufgeschrieben ist natürlich etwas gewagt nach drei so kleinen experimenten schon prothesen
  75. aufzustellen aber man könnte ich jetzt die folgenden ideen haben und eine datei in der die bits und bytes zufällig was immer das genau bedeuten mag und mit
  76. gleicher wahrscheinlichkeit verteilt sind kann man gar nicht komprimieren zweite hypothese eine datei die mit einem entsprechenden programm schon mal
  77. effizient komprimiert wurde kann man nicht noch weiter komprimieren in dem sinne dass sie noch kleiner wird jedenfalls nicht verlustfrei und was wir
  78. an den kurven eben gesehen haben man könnte vermuten dass in einer bestimmten art und weise durch das komprimieren die datei zufälliger gemacht wird das würde
  79. auch zu der erste hypothese passen wenn die datei schon zufällig ist kann man sie halt nicht komprimieren weil man sie nicht mehr zufälliger machen können mit
  80. solchen fragen unter anderem beschäftigt sich die sogenannte informationstheorie die informationstheorie ist wenn sie so wollen das kind von claude shannon
  81. das ist ein amerikanischer mathematiker der im zwanzigsten jahrhundert gelebt hat und der in vielen bereichen sehr prägend war für die informationstheorie
  82. ging eigentlich alles los mit einem artikel von gender mathematik theory of communication 1948 erschienen ist und in dem unter anderem die dinge drin stehen
  83. über die wir heute reden wollen er hat aber noch andere wegweisende dinge veröffentlicht ich nenne hier nur zwei beispiele
  84. es gibt einmal den artikel communication die präsenz auf neues der auf fast zur gleichen zeit geschrieben wurde da taucht zum beispiel das ab das theorem
  85. auf über das wir auch schon gesprochen haben und seine masterarbeit 1930 heißt es symbolik analysis of leland switching circuit
  86. das war im prinzip die erste mathematische theorie von binären logische schaltkreise aufbauen darf zwischen ergeben also ein sehr
  87. vielseitiger und wegweisender wissenschaftler der übrigens nebenbei nachdem was man so über ihn gehört auch ein sehr lustiger und interessanter
  88. mensch wahr er hat eine ganze reihe von sehr spaßigen apparaten erfunden vielleicht versuchen sie zum beispiel mal auf youtube nach dem begriff wie
  89. rote mit maschinen zu suchen das ist auch etwas was er entwickelt hat schön war mathematiker aber auch ingenieur und als ingenieur hat er sich auch ganz
  90. pragmatische fragen gestellt und in dieser informationstheorie sind fragen die er sich zum beispiel gestellt hat wie kann man informationen
  91. quantifizieren kann man den informationsgehalt irgendwie messen wie eine physikalische größe sowie kraft oder geschwindigkeit oder so was andere
  92. fragen die man sich natürlich auch stellen könnte sind was ist informationen eigentlich und kann man vielleicht auch die bedeutung in den
  93. inhalt von informationen durch zahlen darstellen das sind fragen die in der informationstheorie gar nicht behandelt
  94. werden also das ist keine alle umfassende theorie der information wie der name vielleicht ausdrückt sondern ist es eher eine ingenieur mäßige
  95. theorie in der es um die fragen geht die da oben stehen bevor wir uns mit den begriffen der informationstheorie vertraut machen noch
  96. zwei vor überlegungen was ich wohne ja schon gesagt habe wenn man eine datei als zip-archiv verpackt und sie damit deutlich kleiner macht im allgemeinen
  97. kann man sie danach wieder auspacken und bekommt die originaldatei ohne änderungen verlustfrei zurück das heißt es ist keine informationen verloren
  98. gegangen also informations gehalten muss etwas anderes sein als datenmenge denn die datenmenge ist das komprimieren
  99. reduziert wurden aber die informationen die in die datei steckte ist irgendwie erhalten geblieben weil wir sie hier wieder zurückbekommen
  100. können das war die erste folge legen und für die zweite vollbelegung stellen sie sich vor sie sitzen in einer quizshow
  101. und sie sollen einen bundeskanzler erraten es gab bisher in deutschland acht bundeskanzler ich habe dir mal aufgeschrieben mit
  102. ihrem nachnamen und mit ihrem geburtsjahr und sie sollen also jetzt erraten welcher gemeint ist und ihnen werden zwei verschiedene informationen
  103. angeboten zur auswahl und sie sollen wir jetzt sagen welche informationen für sie wertvoller ist die eine information diese bekommen ist der
  104. name des gesuchten kanzlers enthält den buchstaben r ich habe das hier mal markiert das gilt für sechs von den acht bundeskanzlerin
  105. bei denen talk nirgendwo im nachnamen einen eher auf die zweite informationen die sie bekommen können ist der gesuchte kanzler wurde im neunzehnten jahrhundert
  106. geboren das gilt nur für zwei von diesen kanzlern wenn sie es ein bisschen drüber nachdenken dann werden die meisten leute
  107. wahrscheinlich sagen dass die zweite information wertvoller ist und der grund dafür dass die zweite information wertvoller ist es der dass sie ein
  108. ereignis beschreibt das eine geringere wahrscheinlichkeit hat als die erste information wenn wir also davon ausgehen dass alle acht kanzler mit gleicher
  109. wahrscheinlichkeit vorkommen können dann ist die wahrscheinlichkeit dafür dass der gesuchte kanzler also der ausgewählte im 19 jahrhundert geboren
  110. wurde wesentlich geringer als die wahrscheinlichkeit dafür dass der zufällig ausgewählte kanzler im nachnamen den buchstaben r hat also wir
  111. können uns merken mit die wahrscheinlichkeit geringer es ist der informationsgehalt höher darum wird der informationsgehalt
  112. manchmal auch überraschungs wert genannt die grundidee die shannon nun verfolgt hat ist das eher information als funktion der wahrscheinlichkeit
  113. dargestellter darum unsere vor überlegungen geben in seinem paper dessen titel ich am anfang zitiert habe spricht er von einer
  114. quelle die zeichen sendet das ist eine abstraktion so eine quelle die zeichen setzt kann alles mögliche sein das kann ein telegraph sein der
  115. morsezeichen sendet das kann ein smartphone sein dass bilder über das wlan verschickt das kann eine datei sein die auf einem usb stick gespeichert ist
  116. das kann auch ein buch sein in dem die zeichen dann buchstaben sind das heißt wir haben es wie man es in der informatik auch häufig macht mit einer
  117. endlichen menge von zeichen zu tun die man typischerweise vorbild nennt diese menge nennt man meistens groß sigma und wir würden jetzt
  118. diese n zeichen die wir da haben x1 x2 und so weiter bis xl nennen und die entscheidende vorstellung ist nun dass diese zeichen alle mit einer bestimmten
  119. wahrscheinlichkeit auftreten also wir sagen das zeichen xi tritt mit einer wahrscheinlichkeit die auf und wir setzten zwei dinge voraus erstens haben
  120. all diese zeichen tatsächlich eine positive wahrscheinlichkeit kann es von denen hat die wahrscheinlichkeit 0 denn das würde bedeuten dass es nie
  121. auftritt dann können wir gleich weglassen und alle wahrscheinlichkeiten zusammen ergeben genau 1 das heißt es kommt immer garantiert ein weiteres
  122. zeichen stellen sie sich vielleicht wirklich einfach so im telegrafen vor in dem regelmäßig irgendwelchen morsezeichen gesendet werden
  123. damit haben wir im prinzip eine zufalls variable definiert die den ich hier mal groß und diese zu fass variable kann als werte annehmen die zeichnung aus dem
  124. alphabet und die wahrscheinlichkeit dafür dass dann die zufalls variabel das zeichen xi annimmt ist anhalt gerade so wie es darum steht und eine gedächtnis
  125. lose quelle ist dann nach shannon einfach eine folge von zufalls variablen die unabhängig voneinander sind das ist die bedeutung von gedächtnis los in
  126. diesem fall und die alle dieselbe verteilung iks haben das heißt es kommt zeichnen um zeichnen um zeichen aus dieser quelle raus quellen haben wir
  127. fuhren beispiele gesehen mit der wahrscheinlichkeit verteilung die videos stehen haben ganz simples beispiel ich habe hier einen dreizeiler
  128. in python geschrieben dieses programm gibt einfach immer 0 und einzeln raus und entscheidet mit hilfe eines zufallszahlengenerator spot null
  129. oder eins ausgibt die funktionen random gibt wählt zufällig eine zeit zwischen 0 und 1 aus und wenn diese zahl kleiner als 0 3 es gibt meine funktionen 0
  130. zurück und sonst gibt sie eine 1 zurück das wäre so eine quelle ein beispiel für so eine quelle das alphabet würde in diesem fall nur
  131. aus zwei zeichen bestehen x10 x2 ist eins und so wer das geschrieben haben wäre die wahrscheinlichkeit p1 0,3 die wahrscheinlichkeit p2 wir dann
  132. entsprechend komma 7 ein anderes beispiel ein bisschen näher an der anwendung für eine quelle könnte einen text sein
  133. ich habe ihn bei mir eine tabelle genommen in der die buchstaben häufigkeiten in deutschen texten aufgeführt ist zum beispiel der
  134. buchstabe e kommt mit einer häufigkeit von 17,4 prozent vor der buchstabe q sehr selten mit einer häufigkeit von 0,02 prozent und so
  135. weiter ich habe da oben darüber geschrieben ist dieses modell realistisch können wir uns einen text wenn unsere quelle zum
  136. beispiel ein buch ist wirklich vorstellen als eine folge von buchstaben mit einer bestimmten wahrscheinlichkeit ankommen und die antwort ist nein das
  137. können wir natürlich nicht in einem typischen deutschen text werden die einzelnen buchstaben nicht unabhängig voneinander vorkommen das war
  138. ja gerade die definition von gedächtnis loser quelle zum beispiel werden bestimmte abfolgen von buchstaben wahrscheinlicher als andere sein hinter
  139. einem kommt zum beispiel viel häufiger 1 n als ein anderer buchstabe darum wäre abgesehen davon dass wir hier gar nicht
  140. über leerzeichen und satzzeichen und so weiter gesprochen haben oder auch groß- und kleinschreibung ignoriert haben die ist nicht unbedingt ein adäquates modell
  141. aber wie es mit allen modellen so ist die frage ist ob man das modell nicht trotzdem gebrauchen kann also vielleicht ist dieses hier ein
  142. bisschen zu einfach aber die idee der gedächtnis losen quelle lässt sich für viele anwendungen sehr gut gebrauchen und was man auch dazusagen muss es gibt
  143. auch modelle in der informationstheorie für quellen die nicht gedächtnis los sind in denen die zeichen also nicht alle unabhängig voneinander kommen aber
  144. so weit werden wir dieses video nicht die gut was wir jetzt machen möchten beziehungsweise das was shannon in seinem paper gemacht hat wir möchten
  145. jeden zeichen seinen informationsgehalt zuordnen das schreibt man normalerweise mit einem großen i also 1 bei unseren zeichen das
  146. wäre jetzt zum beispiel auf der letzten folie einer von den 26 buchstaben gewesen soll eine informationsgehalt zugeordnet
  147. um dieser informationsgehalt soll von seiner wahrscheinlichkeit abhängen das war ja das was wir ihnen schon mal auf der folie stehen hatten wir wollen
  148. informationen als funktion der wahrscheinlichkeit darstellen darum schreibt man häufig in der informationstheorie auch nicht groß wie
  149. von xi also von dem zeichen sondern große von p i das nicht so ganz richtig ist das ist ja nicht der informationsgehalt der
  150. wahrscheinlichkeit sondern der informationsgehalt des zeichens aber wir werden diese konventionen auch übernehmen dabei immer eingedenk dessen
  151. was eigentlich gemeint ist und jetzt stellen wir ein paar forderungen die wir für sinnvoll halten an diese funktion groß sie was hätten wir gerne das erste
  152. was ganz sinnvoll klingt ist informationen wird akkumuliert also wenn ich neue informationen bekomme dann kommt sie zu der alten dazu das bedeutet
  153. dieser wert der da rauskommt große von xi kann nicht negativ sein denn das würde bedeuten dass wenn ich neue information bekomme ich dann nach
  154. weniger informationen als vorher habe und so funktioniert hier nicht also informationen kann nicht negativ sein denn es kommt wenn überhaupt immer nur
  155. was dazu die zweite sache die auch ziemlich sinnvoll klingt ist dass diese funktion die den informationsgehalt bestimmt stetig von dem
  156. wahrscheinlichkeiten abhängen soll das bedeutet ja nur das ist ja nur eine mathematische formulierung davon dass wenn sich die wahrscheinlichkeit nur ein
  157. ganz bisschen ändert der informationsgehalt sich auch nur ein ganz bisschen ändern soll alles andere wäre glaube ich nicht
  158. sinnvoll und für die dritte forderung das ist dann auch die letzte noch mal eine kleine weitere vor überlegung stellen sich wieder ein spiel vor
  159. es wurden drei würfel geschmissen oder ein wofür wurde dreimal geschmissen und sie sollen die augenzahl erraten und wie eben bei dem quiz mit den kanzlern
  160. können sie jetzt wieder informationen bekommen stellen sie sich vor sie bekommen zunächst die information a beim ersten
  161. wurf kam eine eins heraus das hilft ihnen natürlich schon weil jetzt bestimmte augen zahlen als gesamtsumme gar nicht mehr herauskommen können
  162. dann bekommen sie eine zweite information gesagt beim zweiten wurf kamen auch eine 1 heraus das hilft ihnen auch weil sie
  163. jetzt noch mehr darüber wissen was überhaupt noch rauskommen kann als gesamt augenzahl und was nicht rauskommen können also was man hier
  164. jetzt sagen kann ist sie haben eigentlich informationen bekommen egal wie sie informationen an messen und information b und konnten die
  165. zusammenzählen sie haben ganz also die summe dieser beiden informationen dann informationsgehalt wenn sie aber stattdessen die folgenden
  166. informationen bekommen hätten zunächst dieselbe information a wie vorher beim ersten wurf kam eine eins heraus und dann als zweite informationen die gesamt
  167. augenzahl ist kleiner als 15 dann wenn sie da ein bisschen darüber nachdenken ist die zweite information nicht mehr so viel wert weil ein teil
  168. der informationen sozusagen in der ersten schon drin steckt sie können also jetzt nicht einfach den informationsgehalt dieser beiden
  169. einzelinformationen addieren und wenn sie jetzt darüber nachdenken was der grund ist warum man den informationsgehalt der ersten beiden
  170. informationen a und b agieren kann und den von rund 10 nicht dann werden sie hoffentlich darauf kommen dass ist an folgendem liegt die beiden ersten
  171. ereignisse die der beschrieben werden sind stochastik unabhängig und die anderen beiden nicht und das ist die entscheidende dritte forderung die wir
  172. stellen an die informationsfunktion wenn ich unabhängige ereignisse habe dann soll sich deren informationsgehalt addieren bei abhängigen ereignissen bei
  173. stochastische abhängigen ereignissen muss das nicht unbedingt so sein also diese drei forderungen die hier jetzt orangen geschrieben sind werden
  174. wir jetzt mathematisch formulieren das hat dann auch gemacht das heißt was wir suchen ist also diese funktion die bildet ab vom intervall 01
  175. also von den wahrscheinlichkeiten auf nicht negative reale zahlen das soll also der informationsgehalt sein der da rauskommt sie soll stetig sein und die
  176. dritte forderung war dass ich unabhängige informationsgehalt addieren kann das ist das was ich als formel hingeschrieben habe ich von p1 p2 solle
  177. die von p1 plus ii von p2 sein 41 mal p2 heißt gerade wenn zwei ereignisse unabhängig sind kann ich ihre wahrscheinlichkeiten multiplizieren so
  178. und wenn sie hier jetzt mal gucken dann sehen sie eigentlich dass sie so eine funktion schon mal gesehen haben die diese bedingung erfüllt man kann
  179. mathematisch beweisen dass ist nur eine ganz bestimmte klasse von funktionen gibt die all diese forderungen erfüllt das sind nämlich funktionen die so
  180. aussehen die haben die formen logarithmisch von der wahrscheinlichkeit mal irgendein faktor wobei irgendwann eine negative
  181. zahl ist vielleicht denken sie mal kurz darüber nach warum a negativ sein muss ich hoffe das ist klar warum das so sein muss
  182. so also so muss diese funktion aus sehen was noch nicht klar ist welchen wert soll haben je nachdem welchen wert sie für annehmen kommen da unterschiedliche
  183. funktionen aus was die alle gemeinsam haben ist dass bei der wahrscheinlichkeit 1 der informationsgehalt 0 ist wenn ein
  184. ereignis auf jeden fall eintritt dann bringt es ihnen nichts wenn ihnen das jemand sagt das wussten sie schon das ist so als würde jemand sagen morgen die
  185. sonne auch informationsgehalt ist 0 und nach links je unwahrscheinlicher ein ereignis wird desto mehr steigt der informationsgehalt an
  186. die frage ist wie wählen wir a und da haben sie tatsächlich eine bestimmte freiheit eigentlich konzept festlegen wie sie erwählen wollen und der übliche
  187. wert der in der theorie genommen wird wird mit folgender begründung genommen stellen sie sich vor sie schmeißen eine münze dann gibt es zwei mögliche
  188. ereignisse die rauskommen können kopf oder zahl und beide sind gleich wahrscheinlich beide haben die wahrscheinlichkeit ein halb und im
  189. gewissen sinne ist dass die kleinste informationseinheit die es überhaupt gibt kopf oder zahl das können sie nicht weiter aufteilen
  190. darum möchte man haben dass die wahrscheinlichkeit ein halb den informationsgehalt wert 1 bekommt das wäre die orange kurve die da unten
  191. markiert ist und wenn sie das ausrechnen was danach ist dann bekommen sie raus die funktionen die sie suchen ist die von pelé ist - zweier loga rhythmus von
  192. p das ist die funktion die ich ändern auch definiert hat als die funktion für den informations und was da jetzt raus kommt der
  193. informationsgehalt das sollte ja sie einen sinn sich etwas sein das man wie einen physikalischen welt messen kann darum ist es sinnvoll dem auch einen
  194. namen zu geben eine einheit die einheit die man heutzutage dafür typischerweise nimmt ist zu ehren von shannon dh die von p gibt werte in shannon aus das ist
  195. jedenfalls die offizielle maßeinheit für den informationsgehalt häufig wird allerdings leider in bit gemessen was nicht ganz richtig ist wir
  196. haben ja vorhin schon gesehen informationsgehalt ist nicht dasselbe wie datenmenge darum ist es ein bisschen unglücklich den informationsgehalt in
  197. bit anzugeben es wäre besser man würde den informationsgehalt in shannon angeben um zu unterscheiden zwischen datenmenge im
  198. bild und informationsgehalt kennen aber sie werden viele texte finden in denen der informationsgehalt in mit gemessen wird so jetzt können wir zum mittleren
  199. informationsgehalt der wie wir sehen werden noch eine wichtige rolle spielen wird was könnte damit gemeint sein wenn wir unsere funktion die wir eben
  200. definiert haben wieder wie es ursprünglich gedacht war es funktionen der einzelnen zeichen nicht als funktion der wahrscheinlichkeiten sehen dann ist
  201. das eine zufalls variable und eine zufalls variable hat einen erwartungswert und der erwartungswert ist ja so was wie der mittlere zu
  202. erwartende wert das heißt mit den erwartungswert dieser zufalls variabler ausrechnen dann bekommen wir den mittleren zu erwarten informationsgehalt
  203. unseres alphabets und weil das so wichtig ist bekommt das auch einen namen man nennt das die entropie der quelle ich habe nochmal in klammern zur
  204. erinnerung dazu geschrieben wir reden hier nur über gedächtnis lose quellen wenn die nicht gedächtnis los sind wird das alles noch ein bisschen
  205. komplizierter für unsere zwecke reicht das also dieser wert wird entropie der quelle genannt und wird geschrieben habe von iks oder wenn sie ganz vorn ich
  206. ausdrücken wollen sollten sie eigentlich sagen etwa von iks weil dieses haar gar keiner ist es sieht nur so aus dass sie eigentlich ein großes griechisches etwa
  207. sein entscheidendes jedenfalls dieser wert wird gleich noch eine große rolle spielen wir wollen jetzt mal an einem beispiel diesen wert ausrechnen
  208. wenn wir unser alphabet von vorhin nehmen dann müssen wir jetzt durch alle 26 buchstaben gehen von jedem die wahrscheinlichkeit nehmen also vom mit
  209. dem die wahrscheinlichkeit 0,065 1 das multiplizieren wir mit den zweier logarithmisch dieser wahrscheinlichkeit das machen wir auch für b 0,01 89 und so
  210. weiter und diese 26 produkte addieren wir alle und dann noch - davor dann kommt am ende raus ungefähr 4,0 6 was nützt uns das jetzt wenn wir wissen
  211. dass ungefähr 4,06 rauskommt als entropie dieser quelle die bedeutung dieses wertes kann man erkennen an der ganz wesentlichen
  212. aussage aus dem ursprünglichen text von shannon an dem so genannten quellen codierung theorie ich werde das quellen codierung theorien
  213. gibt es nicht mathematisch formulieren und es nur an diesem beispiel versuchen zu formulieren und natürlich ist das keine exakte
  214. formulierung und ich möchte noch mal darauf hinweisen nicht strapazieren sozusagen als kleingedrucktes noch mal hin
  215. das was ich jetzt sage gilt nur unter der vereinfachenden voraussetzung dass wir uns nur und großbuchstaben kümmern es gibt keine wort zwischen rom und
  216. satzzeichen und so weiter und dass wir uns texte als gedächtnis lose quellen vorstellen das heißt wir wissen nichts über wörter und folgen von buchstaben
  217. und silben sondern wir stehen das einfach so vor dass die buchstaben mit bestimmten wahrscheinlichkeit reinkommen wenn dem so ist dann sagt das quellen
  218. codierung theorien zwei dinge aus in denen jeweils die entropie eine große rolle spielt erstens gesagt ist es gibt ein verlustfreies verfahren mit dem man
  219. solche texte so komprimieren kann dass man im durchschnitt nur unwesentlich mehr als 406 bitter grad die entropie pro buchstaben auf der festplatte
  220. verbraucht nochmals im vergleich wir haben 26 buchstaben und wenn man 26 buchstaben einfach irgendwie kodieren würden so was ähnliches wie ascii dann
  221. bräuchten wir auf jeden fall fünf bit weil die nächstgrößere zweier potenzieller 32 ist aber dass quellen codierung theorie und sagt man kommt mit
  222. ungefähr 4,0 6 aus die genaue mathematische formulierung ist eigentlich so etwas wie eine grenzwert formulierung die besagt man kann an die
  223. 4,06 beliebig gut dran kommen im durchschnitt verfahren die so was machen dann mache ich vielleicht mal ein separates video drüber nennt man
  224. entropie kodierung und wenn sie so wollen waren schon die ersten telegrafen geräte die entropie codierung verwendet haben wenn sie sich mal das morse
  225. alphabet anschauen dann werden sie sehen dass buchstaben die häufig vorkommen wie zb e einen wesentlich kürzeren morsecode haben als buchstaben die nicht so häufig
  226. vorkommen das ist im prinzip die idee der entropie codiert zweite aussage des krokodils theorem es ist besser geht es aber nicht
  227. unter den voraussetzungen die unten im kleingedruckten stehen kann es keinen verlustfreien kompression algorithmus geben der auf beliebige deutsche texte
  228. anwendbar ist mit der wahrscheinlichkeit verteilung von den letzten folie und der die resultierende dateien im mittel immer mit weniger als 40 6 bit pro
  229. buchstabe komprimiert also sie sehen wenn es darum geht was kann man überhaupt komprimieren und bis zu welcher grenze ist das möglich dann ist
  230. die entropie ein ganz wesentlicher wert das ist eigentlich so der wesentliche und wichtigste grundgedanke der informationstheorie natürlich steckt
  231. dann noch viel mehr drin aber wenn sie das hier verstanden haben dann wissen sie schon mal worum es eigentlich geht und zum schluss noch ein ganz anderer
  232. gedanke der eigentlich nur als anregung gedacht ist falls sie sich mit solchen fragen näher beschäftigen wollen ich habe in einem anderen video erklärt wie
  233. man beliebig viele nachkommastellen von pi ausrechnen können und ich habe da auch hingewiesen auf ein programm auf meiner website dass eine million binäre
  234. nachkommastellen von pi ausgerechnet sie können sich das auch als datei herunterladen siehe die url rechts das heißt sie laden sich eine datei herunter
  235. die eine größe von ungefähr 130 tausend beitrag das bekommen sie wenn sie zwei hoch 20 bit durch acht teilen und diese datei können sie auf ihren rechner
  236. packen und sie können diese datei als zip-archiv verpacken und sie werden etwas sehen was sie schon mal bei unsere zufälligen datei
  237. beachtet haben die verpackte datei ist sogar ein bisschen größer ist als original auf meinem rechner sind zum beispiel aus 131 1072 bei 131 1214 bei
  238. geworden und wenn wir die analyse die wir vorher gemacht haben mit den datenpaketen mit dieser datei team machen dann sehen wir
  239. wieder so eine schöne kurven ähnliche verteilung die darauf hindeutet dass diese zahlen im prinzip mehr oder weniger zufällig in der datei stehen
  240. das rührt an bestimmte mathematische fragen über die ich hier nichts weiter sagen will da ist zum beispiel die ungelöste frage
  241. ob die eine sogenannte normale zahl ist für uns ist momentan nur wichtig wenn wir mit den mitteln der informationstheorie an diese datei
  242. herangehen dann sieht das so aus als wäre diese dateien nicht komprimiert jetzt kommt aber ein ganz anderer gedanke diese datei wurde ja mit einem
  243. programm erzeugt von dem ich hier die ersten paar zeilen mal hin geschrieben habe das ist dass julia programm das ich von meiner website herunterladen können
  244. dieses julia programm ist ja auch eine bestimmte art und weise die datei zu komprimieren wenn ich ihnen diese eine million nachkommastellen schicken will
  245. kann ich ihnen stattdessen ja auch das programm schicken und sie können mit hilfe dieses programms die eine million nachkommastellen rekonstruieren
  246. dieses programm verbraucht aber nur 1000 beide und nicht 130000 breit und das ist doch auch eine bestimmte art und weise eine datei zu komprimieren sie mit einem
  247. programm wie auch immer zu rekonstruieren das ist ein themenkomplex denen man kann morgen rauch komplexität nennt genannten nach dem großen chor auf
  248. den wir schon im zusammenhang mit der stochastik gesprochen haben und wie ich finde auch ein sehr spannendes feld aber ich wollte das wie gesagt hier nur mal
  249. an risen vielleicht haben sie ja selbst lust sich damit weiter zu beschäftigen