Grundbegriffe der Informationstheorie (Entropie und Quellencodierungstheorem)
Weitz / HAW Hamburg
https://www.youtube.com/watch?v=qpC6LHHpwHY

Transkript (automatisch erstellt)

0:00 in diesem video wird es um informationstheorie gehen natürlich kann ich in einem kurzen video nicht die gesamte informationstheorie
0:08 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
0:19 daten komprimieren können und was die grenzen weil solches verfahren sind dafür werden wir mit zunächst mal zwei beispiel dateien arbeiten
0:28 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
0:39 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
0:51 bmp datei das sind auch absichtlich ungefähr 65 millionen konten diesem fall auch gut erklären warum das genauso viele sind
1:00 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
1:14 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
1:23 dass wir daraus ein zip-archiv machen weiß ich das noch nie gemacht haben dafür brauchen sie nicht mein programm zu installieren
1:31 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
1:40 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
1:49 können dieses bild mit irgend einem grafikprogramm öffnen bis dann wieder abspeichern aber nicht in dem format bmp sondern zum beispiel
1:59 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
2:08 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
2:18 der kompression der für uns wesentliche unterschied ist dass in dem fall rechts es sich um eine sogenannte verlust behaftete kompression handelt aber
2:30 vielleicht vorher noch mal ein anderer auch nicht ganz unwesentlicher unterschied beide bilddateien rechts die bnp datei und die jpeg datei kann ich
2:38 mit normalen programm einfach öffnen und mehr ansehen die beiden dateien links die ursprüngliche text datei und die
2:45 zip-datei unterscheiden sich die textdatei kann ich mit einem texteditor mir anschauen die zip datei muss sich erst wieder
2:52 auspacken bevor ich sie mir mit einem texteditor anschauen kann aber dafür uns wesentliche unterschied ich habe eben
2:58 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
3:07 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
3:17 da handelt es sich um eine kompression bei der ich wenn ich das zip-archiv wieder auspacken die originaldatei exakt wird für bild
3:25 wieder zurückbekommen wir wollen uns in diesem video nur mit verlust freier kompression beschäftigen es gibt in diesem kanal auch videos die
3:33 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
3:42 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
3:52 programm mache ich weiter als sechseinhalb millionen zufällig ausgewählte bytes auf die festplatte zu schreiben das heißt wir haben eine
3:58 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
4:05 textdatei und die größe der komprimierten also getippten textdatei das machen wir mit der datei randomly wir eben erzeugt haben auch dann wenn
4:14 sie das zum ersten mal machen wird sie das ergebnis überraschen die rezepte datei random zip ist nicht nur nicht kleiner als das
4:24 original sondern sehr großer wahrscheinlichkeit sogar größer ist als original von kompression kann also hier überhaupt keine rede sein
4: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
4:41 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
4:51 machen können und wir wollen das mal ganz vorsichtig mathematisch formulieren mathematische soll das bedeuten gibt es eine initiative abbildung die jeder
5:00 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
5:10 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
5:19 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
5:27 dieses verfahren zwei verschiedene dateien auf dieselbe datei abgebildet werden dann kann ich natürlich unmöglich beide wäre konstruieren also es muss
5:34 eine induktive abbildung sein sie soll dateien abbilden auf dateien die nicht größer sind und diese bedingung wird auf jeden fall von der
5:44 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
5:51 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
6:00 nicht mal das geht das kann man sich ganz leicht überlegen ich habe dazu eben ein kleines schaubild gemacht wenn sie sich zum beispiel
6:06 ü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
6:15 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
6:24 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
6:38 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
6:48 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
6:56 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
7:05 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
7:14 43 bit groß war rutscht auf ein weiterhin liegenden ring zum beispiel auf den ring prodi 42 bilddateien liegen das heißt
7:23 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
7:33 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
7:42 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
7:49 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
7:58 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
8:09 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
8:16 kann man den dateien irgendwie ansehen dass sie nicht komprimiert sind und so weiter dafür noch mal ein anderes kleines experiment
8:24 ich habe diese dateien damit der befohlen gearbeitet haben durch ein kleines selbst geschrieben das an
8:29 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
8:39 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
8:50 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
8:58 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
9:07 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
9:15 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
9:24 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
9:35 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
9:45 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
9:53 maske format immer 8 bit verwendet und bestimmte 8 bit muster kommen häufiger vor als andere darum bekommen wir halt eine im
10:01 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
10:10 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
10:19 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
10:28 nochmals die viren dann werden sie sehen dass das was da rauskommt wieder wie schon bei der rennen datei nicht kleiner sondern sogar bis
10:37 größer ist das original ist das heißt wir können die nicht nochmal komprimieren und nochmal komprimieren und nochmal komprimieren was ja
10:43 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
10:51 ich habe ja mal ein paar vage formulierte hypothesen aufgeschrieben ist natürlich etwas gewagt nach drei so kleinen experimenten schon prothesen
11:00 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
11:09 gleicher wahrscheinlichkeit verteilt sind kann man gar nicht komprimieren zweite hypothese eine datei die mit einem entsprechenden programm schon mal
11:17 effizient komprimiert wurde kann man nicht noch weiter komprimieren in dem sinne dass sie noch kleiner wird jedenfalls nicht verlustfrei und was wir
11:25 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
11:34 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
11:42 solchen fragen unter anderem beschäftigt sich die sogenannte informationstheorie die informationstheorie ist wenn sie so wollen das kind von claude shannon
11:52 das ist ein amerikanischer mathematiker der im zwanzigsten jahrhundert gelebt hat und der in vielen bereichen sehr prägend war für die informationstheorie
12:00 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
12:11 über die wir heute reden wollen er hat aber noch andere wegweisende dinge veröffentlicht ich nenne hier nur zwei beispiele
12:18 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
12:26 auf über das wir auch schon gesprochen haben und seine masterarbeit 1930 heißt es symbolik analysis of leland switching circuit
12:34 das war im prinzip die erste mathematische theorie von binären logische schaltkreise aufbauen darf zwischen ergeben also ein sehr
12:43 vielseitiger und wegweisender wissenschaftler der übrigens nebenbei nachdem was man so über ihn gehört auch ein sehr lustiger und interessanter
12:53 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
13:01 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
13:11 pragmatische fragen gestellt und in dieser informationstheorie sind fragen die er sich zum beispiel gestellt hat wie kann man informationen
13:20 quantifizieren kann man den informationsgehalt irgendwie messen wie eine physikalische größe sowie kraft oder geschwindigkeit oder so was andere
13:31 fragen die man sich natürlich auch stellen könnte sind was ist informationen eigentlich und kann man vielleicht auch die bedeutung in den
13:37 inhalt von informationen durch zahlen darstellen das sind fragen die in der informationstheorie gar nicht behandelt
13:44 werden also das ist keine alle umfassende theorie der information wie der name vielleicht ausdrückt sondern ist es eher eine ingenieur mäßige
13:52 theorie in der es um die fragen geht die da oben stehen bevor wir uns mit den begriffen der informationstheorie vertraut machen noch
14:00 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
14:09 kann man sie danach wieder auspacken und bekommt die originaldatei ohne änderungen verlustfrei zurück das heißt es ist keine informationen verloren
14:18 gegangen also informations gehalten muss etwas anderes sein als datenmenge denn die datenmenge ist das komprimieren
14:26 reduziert wurden aber die informationen die in die datei steckte ist irgendwie erhalten geblieben weil wir sie hier wieder zurückbekommen
14:33 können das war die erste folge legen und für die zweite vollbelegung stellen sie sich vor sie sitzen in einer quizshow
14:39 und sie sollen einen bundeskanzler erraten es gab bisher in deutschland acht bundeskanzler ich habe dir mal aufgeschrieben mit
14:47 ihrem nachnamen und mit ihrem geburtsjahr und sie sollen also jetzt erraten welcher gemeint ist und ihnen werden zwei verschiedene informationen
14:56 angeboten zur auswahl und sie sollen wir jetzt sagen welche informationen für sie wertvoller ist die eine information diese bekommen ist der
15:04 name des gesuchten kanzlers enthält den buchstaben r ich habe das hier mal markiert das gilt für sechs von den acht bundeskanzlerin
15:11 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
15:19 geboren das gilt nur für zwei von diesen kanzlern wenn sie es ein bisschen drüber nachdenken dann werden die meisten leute
15:26 wahrscheinlich sagen dass die zweite information wertvoller ist und der grund dafür dass die zweite information wertvoller ist es der dass sie ein
15:34 ereignis beschreibt das eine geringere wahrscheinlichkeit hat als die erste information wenn wir also davon ausgehen dass alle acht kanzler mit gleicher
15:43 wahrscheinlichkeit vorkommen können dann ist die wahrscheinlichkeit dafür dass der gesuchte kanzler also der ausgewählte im 19 jahrhundert geboren
15:50 wurde wesentlich geringer als die wahrscheinlichkeit dafür dass der zufällig ausgewählte kanzler im nachnamen den buchstaben r hat also wir
15:58 können uns merken mit die wahrscheinlichkeit geringer es ist der informationsgehalt höher darum wird der informationsgehalt
16:04 manchmal auch überraschungs wert genannt die grundidee die shannon nun verfolgt hat ist das eher information als funktion der wahrscheinlichkeit
16:15 dargestellter darum unsere vor überlegungen geben in seinem paper dessen titel ich am anfang zitiert habe spricht er von einer
16:24 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
16:32 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
16:42 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
16:49 endlichen menge von zeichen zu tun die man typischerweise vorbild nennt diese menge nennt man meistens groß sigma und wir würden jetzt
16:57 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
17:07 wahrscheinlichkeit auftreten also wir sagen das zeichen xi tritt mit einer wahrscheinlichkeit die auf und wir setzten zwei dinge voraus erstens haben
17:16 all diese zeichen tatsächlich eine positive wahrscheinlichkeit kann es von denen hat die wahrscheinlichkeit 0 denn das würde bedeuten dass es nie
17:22 auftritt dann können wir gleich weglassen und alle wahrscheinlichkeiten zusammen ergeben genau 1 das heißt es kommt immer garantiert ein weiteres
17:30 zeichen stellen sie sich vielleicht wirklich einfach so im telegrafen vor in dem regelmäßig irgendwelchen morsezeichen gesendet werden
17:37 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
17:47 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
17:57 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
18:07 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
18:15 fuhren beispiele gesehen mit der wahrscheinlichkeit verteilung die videos stehen haben ganz simples beispiel ich habe hier einen dreizeiler
18:21 in python geschrieben dieses programm gibt einfach immer 0 und einzeln raus und entscheidet mit hilfe eines zufallszahlengenerator spot null
18:29 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
18:39 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
18:46 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
18:56 entsprechend komma 7 ein anderes beispiel ein bisschen näher an der anwendung für eine quelle könnte einen text sein
19:05 ich habe ihn bei mir eine tabelle genommen in der die buchstaben häufigkeiten in deutschen texten aufgeführt ist zum beispiel der
19:14 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
19:24 weiter ich habe da oben darüber geschrieben ist dieses modell realistisch können wir uns einen text wenn unsere quelle zum
19:30 beispiel ein buch ist wirklich vorstellen als eine folge von buchstaben mit einer bestimmten wahrscheinlichkeit ankommen und die antwort ist nein das
19:40 können wir natürlich nicht in einem typischen deutschen text werden die einzelnen buchstaben nicht unabhängig voneinander vorkommen das war
19:48 ja gerade die definition von gedächtnis loser quelle zum beispiel werden bestimmte abfolgen von buchstaben wahrscheinlicher als andere sein hinter
19:55 einem kommt zum beispiel viel häufiger 1 n als ein anderer buchstabe darum wäre abgesehen davon dass wir hier gar nicht
20:03 über leerzeichen und satzzeichen und so weiter gesprochen haben oder auch groß- und kleinschreibung ignoriert haben die ist nicht unbedingt ein adäquates modell
20:11 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
20:18 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
20:26 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
20:34 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
20:41 jeden zeichen seinen informationsgehalt zuordnen das schreibt man normalerweise mit einem großen i also 1 bei unseren zeichen das
20:50 wäre jetzt zum beispiel auf der letzten folie einer von den 26 buchstaben gewesen soll eine informationsgehalt zugeordnet
20:56 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
21:03 informationen als funktion der wahrscheinlichkeit darstellen darum schreibt man häufig in der informationstheorie auch nicht groß wie
21:11 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
21:18 wahrscheinlichkeit sondern der informationsgehalt des zeichens aber wir werden diese konventionen auch übernehmen dabei immer eingedenk dessen
21:26 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
21:37 was ganz sinnvoll klingt ist informationen wird akkumuliert also wenn ich neue informationen bekomme dann kommt sie zu der alten dazu das bedeutet
21:46 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
21:54 weniger informationen als vorher habe und so funktioniert hier nicht also informationen kann nicht negativ sein denn es kommt wenn überhaupt immer nur
22:01 was dazu die zweite sache die auch ziemlich sinnvoll klingt ist dass diese funktion die den informationsgehalt bestimmt stetig von dem
22:09 wahrscheinlichkeiten abhängen soll das bedeutet ja nur das ist ja nur eine mathematische formulierung davon dass wenn sich die wahrscheinlichkeit nur ein
22:16 ganz bisschen ändert der informationsgehalt sich auch nur ein ganz bisschen ändern soll alles andere wäre glaube ich nicht
22:22 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
22:31 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
22:40 können sie jetzt wieder informationen bekommen stellen sie sich vor sie bekommen zunächst die information a beim ersten
22:47 wurf kam eine eins heraus das hilft ihnen natürlich schon weil jetzt bestimmte augen zahlen als gesamtsumme gar nicht mehr herauskommen können
22:57 dann bekommen sie eine zweite information gesagt beim zweiten wurf kamen auch eine 1 heraus das hilft ihnen auch weil sie
23:04 jetzt noch mehr darüber wissen was überhaupt noch rauskommen kann als gesamt augenzahl und was nicht rauskommen können also was man hier
23:11 jetzt sagen kann ist sie haben eigentlich informationen bekommen egal wie sie informationen an messen und information b und konnten die
23:18 zusammenzählen sie haben ganz also die summe dieser beiden informationen dann informationsgehalt wenn sie aber stattdessen die folgenden
23:26 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
23:36 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
23:45 der informationen sozusagen in der ersten schon drin steckt sie können also jetzt nicht einfach den informationsgehalt dieser beiden
23:51 einzelinformationen addieren und wenn sie jetzt darüber nachdenken was der grund ist warum man den informationsgehalt der ersten beiden
23:58 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
24:06 ereignisse die der beschrieben werden sind stochastik unabhängig und die anderen beiden nicht und das ist die entscheidende dritte forderung die wir
24:14 stellen an die informationsfunktion wenn ich unabhängige ereignisse habe dann soll sich deren informationsgehalt addieren bei abhängigen ereignissen bei
24:24 stochastische abhängigen ereignissen muss das nicht unbedingt so sein also diese drei forderungen die hier jetzt orangen geschrieben sind werden
24:31 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
24:40 also von den wahrscheinlichkeiten auf nicht negative reale zahlen das soll also der informationsgehalt sein der da rauskommt sie soll stetig sein und die
24:48 dritte forderung war dass ich unabhängige informationsgehalt addieren kann das ist das was ich als formel hingeschrieben habe ich von p1 p2 solle
24:59 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
25:09 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
25:17 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
25:24 aussehen die haben die formen logarithmisch von der wahrscheinlichkeit mal irgendein faktor wobei irgendwann eine negative
25:32 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
25:40 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
25:48 funktionen aus was die alle gemeinsam haben ist dass bei der wahrscheinlichkeit 1 der informationsgehalt 0 ist wenn ein
25:56 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
26:03 sonne auch informationsgehalt ist 0 und nach links je unwahrscheinlicher ein ereignis wird desto mehr steigt der informationsgehalt an
26:11 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
26:20 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
26:31 ereignisse die rauskommen können kopf oder zahl und beide sind gleich wahrscheinlich beide haben die wahrscheinlichkeit ein halb und im
26:39 gewissen sinne ist dass die kleinste informationseinheit die es überhaupt gibt kopf oder zahl das können sie nicht weiter aufteilen
26:46 darum möchte man haben dass die wahrscheinlichkeit ein halb den informationsgehalt wert 1 bekommt das wäre die orange kurve die da unten
26:56 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
27:06 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
27:13 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
27:21 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
27:33 jedenfalls die offizielle maßeinheit für den informationsgehalt häufig wird allerdings leider in bit gemessen was nicht ganz richtig ist wir
27:42 haben ja vorhin schon gesehen informationsgehalt ist nicht dasselbe wie datenmenge darum ist es ein bisschen unglücklich den informationsgehalt in
27:49 bit anzugeben es wäre besser man würde den informationsgehalt in shannon angeben um zu unterscheiden zwischen datenmenge im
27:56 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
28:05 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
28:15 definiert haben wieder wie es ursprünglich gedacht war es funktionen der einzelnen zeichen nicht als funktion der wahrscheinlichkeiten sehen dann ist
28:23 das eine zufalls variable und eine zufalls variable hat einen erwartungswert und der erwartungswert ist ja so was wie der mittlere zu
28:32 erwartende wert das heißt mit den erwartungswert dieser zufalls variabler ausrechnen dann bekommen wir den mittleren zu erwarten informationsgehalt
28:39 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
28:48 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
28:53 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
29:04 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
29:13 sein entscheidendes jedenfalls dieser wert wird gleich noch eine große rolle spielen wir wollen jetzt mal an einem beispiel diesen wert ausrechnen
29:21 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
29:30 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
29:40 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
29:52 dass ungefähr 4,06 rauskommt als entropie dieser quelle die bedeutung dieses wertes kann man erkennen an der ganz wesentlichen
30:02 aussage aus dem ursprünglichen text von shannon an dem so genannten quellen codierung theorie ich werde das quellen codierung theorien
30:10 gibt es nicht mathematisch formulieren und es nur an diesem beispiel versuchen zu formulieren und natürlich ist das keine exakte
30:17 formulierung und ich möchte noch mal darauf hinweisen nicht strapazieren sozusagen als kleingedrucktes noch mal hin
30:22 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
30:30 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
30:40 und silben sondern wir stehen das einfach so vor dass die buchstaben mit bestimmten wahrscheinlichkeit reinkommen wenn dem so ist dann sagt das quellen
30:51 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
31:00 solche texte so komprimieren kann dass man im durchschnitt nur unwesentlich mehr als 406 bitter grad die entropie pro buchstaben auf der festplatte
31:10 verbraucht nochmals im vergleich wir haben 26 buchstaben und wenn man 26 buchstaben einfach irgendwie kodieren würden so was ähnliches wie ascii dann
31:19 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
31:27 ungefähr 4,0 6 aus die genaue mathematische formulierung ist eigentlich so etwas wie eine grenzwert formulierung die besagt man kann an die
31:36 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
31:44 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
31:53 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
32:03 vorkommen das ist im prinzip die idee der entropie codiert zweite aussage des krokodils theorem es ist besser geht es aber nicht
32:12 unter den voraussetzungen die unten im kleingedruckten stehen kann es keinen verlustfreien kompression algorithmus geben der auf beliebige deutsche texte
32:20 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
32:29 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
32:38 die entropie ein ganz wesentlicher wert das ist eigentlich so der wesentliche und wichtigste grundgedanke der informationstheorie natürlich steckt
32:46 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
32:53 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
33:01 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
33:10 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
33:20 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
33:31 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
33:38 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
33:49 geworden und wenn wir die analyse die wir vorher gemacht haben mit den datenpaketen mit dieser datei team machen dann sehen wir
33:57 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
34:06 das rührt an bestimmte mathematische fragen über die ich hier nichts weiter sagen will da ist zum beispiel die ungelöste frage
34:13 ob die eine sogenannte normale zahl ist für uns ist momentan nur wichtig wenn wir mit den mitteln der informationstheorie an diese datei
34:22 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
34:30 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
34:38 dieses julia programm ist ja auch eine bestimmte art und weise die datei zu komprimieren wenn ich ihnen diese eine million nachkommastellen schicken will
34:47 kann ich ihnen stattdessen ja auch das programm schicken und sie können mit hilfe dieses programms die eine million nachkommastellen rekonstruieren
34:55 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
35:05 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
35:14 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
35:23 an risen vielleicht haben sie ja selbst lust sich damit weiter zu beschäftigen