Wednesday, December 16, 2015

Auf der Jagd nach den verlorenen Bits

In einer Zeit, in der Information eine so große Rolle spielt, sollten wir genau wissen was mit der Information in den technischen Systemen, die wir täglich verwenden, passiert. Wie viel davon geht auf ihrem Weg von der Quelle zum Empfänger verloren? Und können wir unsere Systeme so bauen, dass dieser Informationsverlust minimiert wird?

Das Smartphone-App Ihrer Bank ist sehr praktisch wenn Ihnen auf dem Weg durch die Herrengasse in Graz in einem Schaufenster ein schöner Pulli auffällt: Ein Blick auf den Kontostand genügt und Sie wissen, ob Sie sich diese sicherlich unnötige Ausgabe leisten können. Um die Sache zu vereinfachen, stellt das App negative Kontostände mit einer roten Zahl, positive mit einer schwarzen dar. Aufgrund eines merkwürdigen (und zugegebenermaßen unrealistischen) Displayfehlers sehen Sie aber nur eine blaue Zahl. Das Display hat einen wichtigen Teil der Kontoinformation zerstört.

Aber was ist Information eigentlich? Im Wesentlichen ist Information unser Wissen bzw. Unwissen über etwas Zufälliges, je nachdem ob wir die Information besitzen oder nicht. Messen lässt sich Information z.B. über die durchschnittliche Anzahl von Ja/Nein-Fragen, die gestellt werden müssen, um unser Unwissen zu beseitigen: Nehmen wir einen zufälligen Münzwurf als Beispiel, so reicht bereits eine Frage, um uns über das Ergebnis zu erkundigen: Kopf oder Zahl? Bei zwei Münzwürfen benötigen wir zwei Fragen, um beide Ergebnisse zu erfahren, bei drei Würfen drei Fragen, und so weiter. In seiner bahnbrechenden Arbeit "A Mathematical Theory of Communicationpräsentierte ClaudeE. Shannon eine mathematische Formel, um die Information eines Münzwurfes – seine Entropie – zu berechnen und definierte das Bit als Maßeinheit.

Die Information eines Münzwurfes ist genau ein Bit: man benötigt exakt eine Ja/Nein-Frage, um den Ausgang des Wurfes zu bestimmen. Anders sieht es bei einer gezinkten Münze aus die in neun von zehn Fällen Kopf zeigt. Unser (Vor-)Wissen ist größer als im Fall einer fairen Münze und "im Durchschnitt" benötigen wir weniger Fragen, um den Ausgang des Münzwurfes zu bestimmen. Konkret kann man sich das folgendermaßen veranschaulichen: Werfen wir eine faire Münze zweimal, müssten wir immer zwei Fragen stellen, um die Ergebnisse beider Würfe zu bestimmen. Werfen wir die gezinkte Münze zweimal ist in vielen Fällen eine einzige, schlau gestellte Frage ausreichend: "Zeigten beide Würfe Kopf?" Wird diese Frage bejaht (und das wird sie in 81% aller Fälle), muss eine zweite Frage mehr nicht gestellt werden. Mit Hilfe von Shannons Formel kann man zeigen, dass die Information dieses gezinkten Münzwurfes bei ca. 0.46 Bit liegt: Es reichen "durchschnittlich" etwas weniger als eine halbe Frage, um unser Unwissen über einen Münzwurf zu beseitigen, etwas weniger als eine Frage für zwei Münzwürfe und etwas weniger als eineinhalb Fragen für drei Würfe.

Wie viel Bit der Kontoinformation wurden aber durch Ihren Displayfehler zerstört? Mit dieser Frage beschäftigte ich mich im Zuge meiner Dissertation an der TU Graz, in der ich den Informationsverlust in technischen Systemen untersuchte. Da sich mit einer einzigen Frage feststellen lässt ob der Kontostand positiv oder negativ ist, kann der Informationsverlust Ihres Displays höchstens ein Bit betragen. Dass der genaue Wert im Wesentlichen von der Zufälligkeit Ihres Kontostandes abhängt ist weniger offensichtlich, aber in Hinblick auf die gezinkte Münze leicht verständlich. Wenn Sie eine sehr sparsame Person sind und immer einen kleinen Puffer auf Ihrem Konto wissen, fehlt Ihnen nicht viel Information: Sie können sehr sicher sein dass die Zahl eigentlich schwarz sein sollte und Sie sich den Pulli leisten können. Wenn Sie eine sehr verschwenderische Person sind, deren Kontostand höchstens ein paar Tage im Monat positiv ist, fehlt Ihnen auch nicht viel Information: Die Zahl ist mit hoher Wahrscheinlichkeit rot. (Den Pulli würden Sie sich in diesem Fall wahrscheinlich trotzdem kaufen.) Bewegen Sie sich allerdings zwischen diesen beiden Extremen, kann Ihr Display einen beträchtlichen Teil der Information zerstört haben – im schlimmsten Fall ein Bit.

Ein Bit ist doch nicht viel, sagen Sie? Das kommt ganz auf das Bit an! Wenn Sie wissen, dass Ihr Kontostand zwischen -5000 und 5000 € liegt, müssen Sie nach Shannons Formel rund 20 Fragen stellen, um den genauen Betrag bis auf den Cent zu erfahren. Ihr Display beantwortet 19 dieser 20 Fragen für Sie – nur leider die wichtigste nicht: Ist der Kontostand positiv oder negativ? So interessant es also ist den Informationsverlust eines Systems zu untersuchen, praktische Bedeutung bekommt diese Theorie erst unter Miteinbeziehung des Relevanzbegriffs: Welcher Anteil der verlorenen Information ist für uns relevant, und welcher irrelevant bzw. störend? Ich erweiterte die Theorie in meiner Dissertation in dieser Hinsicht und verwendete die Resultate, um zu tun, was einem Ingenieur zu tun bestimmt ist: Systeme zu bauen!

Systeme werden nach gewissen Anforderungen gebaut, um gewisse Aufgaben zu erfüllen. Ein elektronisches Filter kann zum Beispiel entworfen werden, um störendes Rauschen beim Telefonieren zu unterdrücken und dabei das relevante Sprachsignal des Gesprächspartners möglichst nicht zu beeinflussen. Historisch bedingt – und schlichtweg am einfachsten – werden Filter nach Energiekriterien entworfen: Die Energie des störenden Rauschens soll nach der Filterung so klein wie möglich sein. Gleichzeitig darf die Energie der durch das Filter hervorgerufenen Störungen im Sprachsignal nicht zu groß werden, um eine angenehme Kommunikation der Gesprächspartner zu garantieren.

Ich versuchte mit meiner Arbeit einen anderen Weg einzuschlagen: In einer Zeit, in der viele unserer Systeme Information verarbeiten oder übertragen, sollte Information als Kriterium für den Systementwurf verwendet werden. Die von Shannon entwickelte Informationstheorie besagt, dass jedes System Information nur verringern aber nicht vergrößern kann. Jene Information, die wir aus dem Lautsprecher am Smartphone hören, war zuvor in der elektromagnetischen Welle in der Luft, im digitalen Signal im Smartphone unseres Gesprächspartners und in den Schallwellen zwischen dessen Mund und dem Mikrofon. Mehr als das: In jedem dieser verarbeitenden Systeme – Mikrofon, digitale Schaltkreise, Lautsprecher – ging Information verloren. Welches Entwurfskriterium könnte also besser geeignet sein als der Informationsverlust? Auf das obige Beispiel angewendet gilt es also ein Filter zu entwerfen welches so wenig Sprachinformation wie möglich zerstört und dabei die "Information" des störenden Rauschens soweit wie möglich reduziert.

Dass ein hinsichtlich Informationsverlust entworfenes Filter besser zur Informationsübertragung geeignet ist als ein nach Energiekriterien entworfenes, dürfte Sie inzwischen nicht mehr überraschen – eine andere Methode liefert eben ein anderes Ergebnis. Nichtsdestotrotz stieß ich während meiner Dissertation in der Literatur immer wieder auf Stellen, in denen Energie mit Information gleichgesetzt wurde. So wird zum Beispiel in der Statistik seit Jahrzehnten die Hauptkomponentenanalyse eingesetzt, um die Komplexität großer Datensätze zu verringern. Dabei werden die mehrdimensionalen Datensätze transformiert und Daten mit geringer Energie verworfen. Diese Vorgehensweise wird mit der Behauptung gerechtfertigt, dass die Daten mit der größten Energie auch die meiste relevante Information beinhalten. Diese Behauptung ist nicht immer richtig (und wer am lautesten schreit, hat auch nicht immer recht): Für die Hauptkomponentenanalyse konnte ich zum Beispiel zeigen, dass sie den Informationsverlust nur dann minimiert, wenn die relevante Information in einem besonderen Zusammenhang mit den Datensätzen steht, einer Tatsache, die in der Statistik nicht immer zutrifft. Es ist höchste Zeit, umzudenken.

Neben Filterentwurf, der Hauptkomponentenanalyse und der Analyse Ihres defekten Displays gibt es natürlich eine Vielzahl weiterer Anwendungen einer Theorie des Informationsverlusts: Zum Beispiel entwickelte ich gemeinsam mit anderen Forschern eine Methode, um Markoffschen Ketten zu vereinfachen, ohne dabei Information zu zerstören. Markoffsche Ketten – Folgen von zufälligen Zahlen, die in einem statistischen Zusammenhang miteinander stehen sind wichtige mathematische Modelle und werden in der Sprachverarbeitung, als Modelle chemischer Reaktionen, in der Genetik, in der Bioinformatik und in der Warteschlangentheorie eingesetzt.

Information ist überall. Um sie nutzbar zu machen, sollten unsere technischen Systeme – Computer, Smartphones, etc. – so wenig wie möglich davon zerstören. Und selbst wenn wir es nicht schaffen sollten, diese Systeme dementsprechend zu bauen, so sollten wir zumindest wissen wie viel Information durch ungeeignet entworfene Systeme verloren geht. Die Wichtigkeit der von Shannon begründeten Informationstheorie, die ich mit meinen Resultaten zum Informationsverlust ein klein wenig ergänzen durfte, ist nicht zu unterschätzen. Es gilt heute viel mehr als je zuvor Norbert Wieners Behauptung: "Information ist Information, weder Materie noch Energie. Kein Materialismus, der dies nicht berücksichtigt, kann heute überleben."