Showing posts with label personal experience. Show all posts
Showing posts with label personal experience. Show all posts

Wednesday, September 12, 2018

A Visit from Marek Smieja

This week I had a nice visit from Marek Smieja, Assitant Professor at the Group of Machine Learning Research at Jagiellonian University in Krakov.

Marek presenting some of his most recent results - you can find the paper on arXiv (and in the upcoming proceedings of this year's edition of NIPS!)

I first met Marek in 2012 on the terrace of Lausanne Palace Hotel - and if that doesn't make a good start for a story then I don't know what does. Drinks in our hands, we were discussing the exciting talks we have heard during the first few days of the IEEE Information Theory Workshop held at EPF Lausanne. Back then Marek and I were working both on information dimension, but we already had the idea that we will soon move towards machine learning.

Fast forward to 2015, when Marek invited me to visit Poland to attend the first edition of Theoretical Foundations of Machine Learning. A year or so later, Marek and I started working on a method for semi-supervised clustering, mixing ideas from model-based clustering and the information bottleneck principle. We have stayed in contact ever since, but this week was the first time we met again since raising glasses on this terrace in 2012. (Marek could not attend the conference in 2015.) Needless to say, I was really happy when he announced that he will be able to visit me at the Know-Center.

Marek in front of the Uhrturm, one of Graz' main attractions.

During two intensive days in Know-Centers "Small Meeting Room" we brought each other up to date regarding our current research projects, found a topic on which we may collaborate in the near future, and defined a student project with the aim to combine Markov aggregation and semi-supervised clustering. I'm looking forward to continuing this year-long academic relationship with Marek!

PS: If you have some hot results on the theory of machine learning ready, you may want to submit it to TFML 2019. Deadline is November 30th.

Thursday, August 16, 2018

Santa Fe Institute Spring 2018 Complexity Challenge

At the end of my Schroedinger fellowship I decided to treat myself with participating in the Santa Fe Institute Spring 2018 Complexity Challenge. I've been a fan of the SFI as long as I've known what it does, and I've seen the most impressive papers published by authors affiliated with SFI.



The challenge itself was an agent-based model with rewards, i.e., it was closely connected to partially-observable Markov decision processes and game theory. In my solution, (which earned me an honorable mention) I took neither approach but just played around a bit with strategies I chose ad hoc. Despite this, I was amazed by the rich diversity of behavior I observed. It took me some 40 work hours but it was totally worth the effort. Thanks heaps to the organizers of the challenge, and congrats to the winners -- I hope I get the chance to participate again at some later time!

Monday, February 26, 2018

Talk at "International Zurich Seminar on Information and Communication"

Just coming back from Zurich, where I attended the Int. Zurich Seminar. Being there for the fourth time in a row, it felt like a class reunion :). I was speaking about a joint work with Tobi Koch on the information dimension of multivariate Gaussian processes (see below for the slides). The work is on arXiv here and here, and Tobi and I discussed a roadmap for more results to come - stay tuned!


By the way, the IZS publishes its submissions on an ETH server that is free to access for everyone and that does not require to transfer copyrights from the authors to the publisher. This is not only open access at its best, but also gives you a chance to look at the amazing papers presented in Zurich.

Friday, January 26, 2018

Talk at "Advanced Topics in Discrete Mathematics"

I was recently giving a talk in the "Advanced Topics in Discrete Mathematics" series organized by the doctoral program on discrete mathematics. In case you missed it, be glad that you did: I went overtime quite a bit. You can obtain the slide by clicking on the image below.

Wednesday, January 17, 2018

My Story with Polar Codes Comes to an End

I have long been wondering whether polar codes are fractal, found out that they are in 2015, and put a paper on arXiv. The story that began in 2010 finally comes to end -- the paper is now published!

I submitted the paper to the IEEE Transactions on Information Theory, where it was under review for 18 months. I was told that the two reviewers thought the paper collects a few "interesting and cute mathematical observations", but that it does not tell us anything about the relevant code properties such as error probabilities or code complexity. I was further told that if I could "add a convincing application", then the paper could get to a second review round.

I withdrew the paper and submitted it to Entropy, and open-access journal published by MDPI, in October 2017. I received reviews within less than two months. Four of the five reviewers were inclined to accept the paper after some revision, while the fifth reviewer insisted to reject the paper (and probably still does) because of its missing connection to real-world codes. It is worth mentioning that the review process was not only much faster than the one for the IEEE Transactions on Information Theory, but that I also got high-quality reviews: Some of the reviewers went through the math in detail, made corrections and suggestions for improvement that led to generalizing some of the results. This shows that a proper, high-quality review process cannot be used to justify long review cycles.

Monday, January 9, 2017

New Features for WhatsApp & Co?

This was originally intended as a submission to the Science Park Graz idea contest (that's why it's in German) - but then I thought that the idea is not innovative enough, even though I would love to see those features in WhatsApp or Hangouts. Who knows, maybe Google is reading this ;).


Zwei Use Cases, an denen WhatsApp, Facebook & Co scheitern

Use Case 1: Wochenendausflug mit Freunden teilen

Du verbringst das Wochenende in München und möchtest deinen Freunden zuhause ein paar Fotos vom Marienplatz, der Allianz-Arena und dem Olympiaturm schicken. Du könntest die Fotos auf Facebook, Instagram oder Google+ teilen. Jene deiner Freunde, die diese sozialen Netzwerke selten nutzen, könnten diese Fotos verpassen weil der Newsfeed in der Zwischenzeit von anderen Neuigkeiten überschwemmt wurde. Du könntest deine Fotos deinen Freunden per WhatsApp schicken - vielleicht existiert sogar schon eine passende Gruppe. Aber einerseits werden deine Freunde mit mehreren Benachrichtigungen belästigt, andererseits fühlen sie sich vielleicht dazu verpflichtet, auf deine Fotos mit Kommentaren zu reagieren. Der Abend im Hofbräuhaus wird so schnell zum Message-Marathon.

Use Case 2: Weihnachtswünsche und einen Jahresrückblick an Bekannte schicken

Du möchtest entfernten Bekannten (ehemalige ArbeitskollegInnen, entfernte Familienmitglieder, etc.) ein frohes Fest wünschen und sie wissen lassen, was im vergangenen Jahr bei dir passiert ist. Was du zu sagen hast sprengt den Rahmen der durchschnittlichen WhatsApp-Nachricht, und Facebook und Google+ sind dir zu öffentlich - zudem besteht das große Risiko, dass deine Bekannten die Nachricht aus den im letzten Use Case genannten Gründen gar nicht bekommen.

Detailbeschreibung

Um diese Use Cases abzudecken, bietet das App verschiedene Features, die über die Spezifikationen der derzeit verfügbaren Messaging-Apps hinausgehen. Zur besseren Übersicht sind die neuartigen Features (wie zum Beispiel Nachrichtentypen, Gruppenrollen und Gruppeneinstellungen) fett markiert.

Darstellung

Die Darstellung ähnelt WhatsApp bzw. den Abos von Youtube: Der Startbildschirm listet die Gruppen auf, in denen man Mitglied ist und gibt mit einer Zahl neben dem Gruppennamen die Anzahl der neuen Nachrichten in der Gruppe an. Bei Touch auf den Gruppennamen kommt man zum Gruppenchat, der wieder WhatsApp ähnelt. Ein wesentlicher Unterschied sind zwei neue Nachrichtentypen (Stories und Textnachrichten im eReader-Stil, siehe unten), die im Gruppenchat nur kompakt als Überschrift angezeigt werden. Alle Nachrichten haben außerdem eine Fußzeile mit der Anzahl von Likes bzw. Kommentaren (siehe unten). Das App hat außerdem ein Webinterface welches vor allem für das Verfassen längerer Nachrichten hilfreich ist.

Gruppenrollen

Neben dem Gruppenadministrator und dem Gruppenmitglied, die es auch in WhatsApp und anderen Messaging-Gruppen gibt, gibt es auch Leser, also eine rein passive Gruppenrolle.

  • Gruppenadministrator: Legt die Gruppeneinstellungen fest; lädt Mitglieder in die Gruppe ein und teilt ihnen Gruppenrollen zu
  • Gruppenmitglied: Teilt Nachrichten mit anderen Gruppenmitgliedern bzw. kommentiert und liked Nachrichten anderer Gruppenmitglieder
  • Leser: Passive Teilnahme; kann ggf. Nachrichten lesen, kommentieren und liken, aber keine neuen Nachrichten teilen

Nachrichtentypen

Das App erlaubt neben Textnachrichten im Sprechblasenstil natürlich auch das Teilen von Fotos, Videos, Dokumenten und Internetlinks. Ein besonderes Feature sind Textnachrichten im eReader-Stil. Dieser Nachrichtentypus ist für lange Textnachrichten ausgelegt und ermöglicht ein angenehmes Lesen durch Umblättern statt Scrollen. Außerdem gibt es Stories, also Nachrichten, die über einen längeren Zeitraum geschrieben werden und mit Fotos oder Videos versehen sind. Stories werden vom Gruppenmitglied wie normale Nachrichten geschrieben und abgeschickt, erreichen die anderen Gruppenteilnehmer aber nicht sofort. Erst wenn die Story als abgeschlossen markiert wurde, erscheinen alle kumulierten Nachrichten im Gruppenchat.
Auf Nachrichten kann auf dreierlei Art reagiert werden: Einerseits durch eine neue Nachricht -- ganz im Stile von WhatsApp. Andererseits können Nachrichten kommentiert und geliked werden -- ganz im Stile von Social Networks wie Facebook oder Google+.

Gruppeneinstellungen

Die Gruppeneinstellungen werden vom Gruppenadministrator festgelegt. Sie regeln unter anderem

  • Welche Nachrichtentypen dürfen in der Gruppe verwendet werden?
  • Gibt es Mindestgrößen für Stories bzw. Textnachrichten im eReader-Stil?
  • Welche Nachrichtentypen führen zu Push-Benachrichtigungen (es sei denn, das Gruppenmitglied hat Push-Benachrichtigungen für diese Gruppe deaktiviert)?
  • Wie darf auf Nachrichten reagiert werden? Sind Kommentare erlaubt? Gibt es die Möglichkeit zu liken?

Individuelle Einstellungen

Ferner gibt es Einstellungen, die jeder Nutzer für sich selbst festlegen kann. Dazu gehört unter anderem die Deaktivierung von Push-Benachrichtigungen und natürlich die Schriftgröße von Textnachrichten im eReader-Format. Außerdem kann jeder Nutzer entscheiden, wer Kommentare auf Nachrichten sehen kann: Alle Mitglieder einer Gruppe, oder nur der Verfasser der Nachricht. Die Reihenfolge der Gruppenliste ist ebenfalls anpassbar. So können die Gruppen nach der Anzahl oder Aktualität ungelesener Nachrichten, nach der Rolle des Nutzers in der jeweiligen Gruppe oder nach einer selbst gewählten Priorisierung geordnet sein. Nutzer können ferner entscheiden, wie sie in Gruppen hinzugefügt werden wollen: Hinzufügen ohne Bestätigung, Hinzufügen mit Bestätigung durch Nachricht oder Hinzufügen durch persönlichen Kontakt (z.B. über NFC-Transfer oder Fotografieren eines QR-Codes am Bildschirm des Gruppenadministrators). Diese Einstellungen sind für jede Gruppenrolle, die dem Nutzer zugeteilt werden soll, und für ausgewählte einladende Personen separat möglich. So erlaube ich zum Beispiel vertrauten Kontakten, mich zu jeder Gruppe als Leser hinzuzufügen, in der sie Gruppenadministrator sind; als Gruppenadministrator möchte ich nur hinzugefügt werden, wenn ich andere Gruppenadministratoren der selben Gruppe persönlich treffe.

Zurück zu den Use Cases

Use Case 1: Wochenendausflug mit Freunden teilen

Als Gruppenadministrator legst du eine Gruppe mit deinen Freunden als Gruppenmitgliedern an. Du erlaubst nur den Nachrichtentypus Stories und verbietest Kommentare - liken ist erlaubt. Die Push-Benachrichtigung ist aktiviert.
Im Laufe des Wochenendes schickst du mehrere Fotos an diese Gruppe. Deine Freunde bekommen am Sonntagabend die Benachrichtigung, dass du eine Story geteilt hast. Sie haben die Möglichkeit, die Fotos anzuschauen und zu liken, aber die Gruppeneinstellung verbietet Kommentare. Niemand ist verpflichtet, dir zu antworten -- wer es dennoch will, findet sicher einen Weg dazu (z.B. eine Direktnachricht oder SMS).

Use Case 2: Weihnachtswünsche und einen Jahresrückblick an Bekannte schicken

Als Gruppenadministrator legst du eine Gruppe mit deinem Bekanntenkreis als Lesern an. Du deaktivierst die Push-Benachrichtigung, erlaubst aber Kommentare.
Du schreibst im Webinterface deine Nachricht und schickst sie als Textnachricht im eReader-Stil an die Gruppe. Deine Leser sehen beim nächsten Öffnen der App einen roten Punkt vor dem Gruppennamen am Hauptbildschirm. Wenn sie die Nachricht öffnen, sehen sie keine scrollbare Nachricht, sondern eine Anzeige im eReader-Format: Durch Berühren des Bildschirms wird die Seite umgeblättert. Da die Option von dir aktiviert wurde, können deine Bekannten deine Nachricht kommentieren. Sie können dabei selbst entscheiden, ob alle Leser oder nur du das Kommentar sehen können.

Thursday, September 8, 2016

My First Lecture in Numbers

It's done! The semester is over and I graded the last student of my lecture "Information-Theoretic System Analysis and Design". It was a great experience, and I thank Gerhard Kramer for offering me this opportunity. I also owe Lars, my colleage, more than a few drinks for taking care of most of the problem classes, and my colleagues Andrei and Ali for interesting discussions and comments about the course material. And I also thank my students, who bore with me until the end of the semester, and who were never tired of asking interesting questions -- I think I've never had such an engaged, excited audience.

Here's the course in numbers:
  • (I think) I held 14 lectures. Lars and I shared 6 problem classes.
  • I spend roughly 200 hours preparing course notes, lecturing, correcting deliverables, etc.
  • In the problem classes, students calculated 11 problems in front of their peers. The remaining 7 problems were done by Lars.
  • We had 1 exam and 2 mandatory homework assignments, weighed 50%-25%-25%.
  • Both homeworks had 9 problems.
  • We had 8 regular students with (as far as I know) 8 different nationalities, originating from 2 continents.
  • 7 of these students took the exam and delivered the 2 homework exercises. The average grade of this course was 1.35.
  • The course notes totaled to 102 pages, containing 8 chapters, 40 worked examples, and 62 end-of-chapter problems.
  • 6 students finished the course evaluation. An excerpt is shown below.
Course Evaluation (in parts)
And here are some lessons I learned:
  • My PhD thesis is far from complete.
  • There is never enough time to prepare course notes. Even though the course was based on my PhD thesis, it was hard work to prepare the results in an understandable manner.
  • You have to make sure that the description of homework problems is precise and complete.
  • Don't get confused by registration numbers. 30+ students registered for the course, but in the first lecture less than 10 showed up. Apparently (so I was told), many students register for a course to get the course notes on Moodle.
  • Students prefer a script that they can get printed at the Fachschaft. Putting chapters online a few days before the lecture is ok, but a script is better.
  • It's good not to have a sttrict course syllabus if's the first time you give the course. You never how exactly how much time you have to spend at a given topic, so it's better to leave room for changes. Still, it's a good idea to have at least a rough sketch of what topics you want to cover.

Monday, June 20, 2016

The “I” in IT

This article has been published in the June issue of the Information Theory Society Newsletter, as this month's student column (students are always encouraged to send us their thoughts and ideas!). I gratefully acknowledge Gerhard Kramer's help in improving this article.

Have you ever asked yourself whether IT is the right field of science for you? I never did, but I guess IT wondered more than once whether I am the right person to work on its problems. Here’s my story.

I’m currently a postdoc at the Institute for Communications Engineering, Technical University of Munich, Germany. In this regard, my story has a happy ending, something I wouldn’t have dreamed of years ago. When I started my PhD at Graz University of Technology, Austria, I hadn’t heard a lecture on IT yet. My supervisor and I nevertheless decided to attempt developing a “theory for deterministic information processing”, or what we called it back then. I knew entropy from communications engineering and thought that I could get all the necessary information from Chapter 2 of the “Elements”. I later read Chapter 4 for stochastic processes and even resorted to more detailed results, such as those from Kolmogorov and Pinsker, when I tried taking limits of random variables. Nevertheless, phrases like “a sequence of codes” never appeared in my work. Probably the rest of my remaining scientific credibility would be lost if I told you how many of my papers got rejected - so I won’t. I will tell you, though, what most reviewers agreed on: That the information-theoretic quantities I introduced to characterize deterministic systems lack an operational characterization. That was a valid criticism, and I learned what an operational characterization is only a few months before I obtained my PhD. Relating to IEEE Spectrum’s article on Claude Shannon, I despaired that I had “jumped on the bandwagon without really understanding” (Slepian) and contributed to the “widespread abuse” (Pierce) of IT by other fields.

However, since then I have discovered that this kind of “abuse” is successful in scientific fields outside IT. For example, nonlinear adaptive filters are trained using an error entropy, Rényi and Cauchy-Schwarz divergences are used for learning and classification, and the information-bottleneck method enjoys widespread use in clustering. To the best of my knowledge, only few of these works accompany their objective functions with an operational characterization - mutual information is “just” a nonlinear measure of statistical dependence, and entropy is “just” a statistic that captures more than the error signal’s variance. Remarkably, these heuristic methods often show superior performance. Hence, at least in these other fields, the works are scientifically justified by experiment. (OK, I admit that this is a feeble attempt to justify my work a posteriori. As more self-justification, the Aims & Scope of the IEEE Transactions on Information Theory does state that the journal aims to publish theoretical and experimental papers.)

Should I, therefore, try to publish in other fields and transactions? Probably. My supervisor, suggested more than once that I should spread the word, trying to convince scientists in signal processing to use higher-order statistics, i.e., IT quantities. I haven’t listened, though, because I feel at home in the IT community, and I would not want to miss meeting my IT friends regularly at our annual events. Even in hindsight, I would rather submit to orthodox pressure and provide operational characterizations rather than to publish in a different community. In the future, I hope that I can do both.

That is my decision. As the IT society, we all must decide: what are our traditions (really) and how strong shall we hold on to them? Especially when dealing with future directions of IT, as mentioned in arXiv:1507.05941, how should we contribute to make our quantities be used in fields such as signal processing, control theory, and machine learning? Or should we not? For example, should we propose clustering algorithms using IT quantities, or should we rather focus on deriving asymptotic limits for the clustering problem? You, as a PhD student, must make your own decision: Are you sufficiently “in IT” so as to be accepted by the community? If your research topic is on the border between IT and another field, in which direction do you want to go?

Tuesday, January 26, 2016

Writing for Wikipedia: Results of a Teaching Experiment

Some time ago I wrote an entry on a teaching experiment I wanted to conduct at TUM: As part of their graduate seminar, students have to get familiar with a scientific topic, present its core aspects in front of their peers, and write a LaTeX article summarizing again the main points. To get truly sustainable results, I asked the students to prepare their articles as if they wrote for Wikipedia. In other words, the target audience is the interested layperson, and while one should not shy away from presenting math, it should be accompanied by motivating examples and easy explanation.

And here are the results of this teaching experiment:
  • Of the eight topics we offered, seven were taking, of which four were particularly suitable to become a Wikipedia article; two more could at least be added as subsections.
  • Three of the suitable topics were very well prepared; so well, that we immediately recommended uploading them to Wikipedia.
  • Since uploading was voluntary, only two of these three articles now appear on Wikipedia: An article on SUDOKU codes and another one on Information Dimension.
  • The official course evaluation (six students participated), asking roughly 20 Likert-type questions, revealed that the course scored better than the department average over all graduate seminars (with one exception: students mentioned that there was not enough time to fulfill all tasks).
  • Students also seemed to like the Wikipedia experiment: In an unofficial course evaluation, I asked eight Likert-type questions (5 = fully agree, 1 = do not agree at all; 7 students participated). The results showed that students found writing for Wikipedia motivating (average score: 4.29), that they liked writing the article first in LaTeX (5), that they would not really want to write it directly in Wikipedia (2.29), and that they learned a lot about both scientific writing and LaTeX (4.43 each). They did not learn too much about writing for Wikipedia, though (3.93).
Not sure if this qualifies as a successful teaching experiment or not - in any case, there are several things I took away from conducting the experiment:
  • If you tell students to write for Wikipedia, tell them how to do it! We had a short lecture on scientific writing, but for the present case this should have been complemented by a 30 minute talk on how to write for Wikipedia.
  • If you tell students to write for Wikipedia, make sure the topics are all suitable: What if a student does a very good job on a ridiculously narrow topic that can never make it into a Wikipedia article?
  • Students need time. Five weeks are not enough to get familiar with a topic and prepare a well-written summary. Students should also be allowed to work on that during their winter break (that doesn't mean that they should do it - but they should be able to choose).
  • During the preparation for the course, I found that there is actually more difference between a Wikipedia article and a scientific manuscript than I expected: Not only is the IMRAD structure not applicable, there is not abstract either, and also the writing style is entirely different: While in scientific manuscripts we try to write lively by including "we" as often as possible, a "we" would appear out of place in a Wikipedia article. The most challenging part, however, is the lead section: These few sentences right after the heading should deliver all relevant information of the article - "For many, it may be the only section that they read. A good lead section cultivates the reader's interest in reading more of the article, but not by teasing the reader or hinting at content that follows." Living up to these expectations is often too hard for scientists (it is for me), so how can we expect it from students?
Concluding, I hope I can repeat that experiment at a later time. Next time, three Wikipedia articles should be the absolute minimum!

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."

Friday, October 2, 2015

Writing for Wikipedia: A Teaching Experiment

Writing reports and presenting results is an important part in an engineer's life, hence teaching these skills is an important (implicit or explicit) part in engineering curricula. At my former affiliation, SPSC at Graz University of Technology, we were teaching the course "Verfassen wissenschaftlicher Arbeiten" to bachelor's students in their fifth semester, preparing them for the challenging task of writing and presenting their bachelor's thesis. There, the approach was (roughly) as follows:
  • Students grouped in pairs or triples and chose a topic related to the scientific process (e.g., writing good introductions, writing abstracts, giving a scientific presentation, plagiarism and literature searches, etc.).
  • They had to give a presentation on this topic, teaching their colleagues the respective skills (flipped classroom).
  • They chose a simple topic from signal processing (e.g., filter design) and wrote a four-page scientific LaTeX article presenting the topic as if it was their own invention.
Let me stress that again: Students should not write a review or a summary, but a scientific paper with a "novel" contribution. Why? Because that's what they have to do when they stay in academia.

Here, at the LNT of Technische Universitaet Muenchen, the offered Gradiate Seminar Mobile Communications and Coding is a very similar course (albeit for master's students): The expected outcomes are again presentation and writing skills, together with acquiring knowledge in a particular field inside communications and coding. In the last years, the approach was as follows:
  • Each student chose a scientific topic and had to write a four-page scientific LaTeX article summarizing the core aspects (in the structure of a scientific paper).
  • Students had to present these core aspects in a 20 minutes presentation.
The difference is apparent: Students at LNT had to write and present summaries rather than writing papers claiming original contribution. Why? Probably because that's what they have to do when they will NOT stay in academia.

But both approaches have one thing in common: Guess what happens to these four-page articles the students write. Nothing. I strongly doubt that any of our students every took a look at their paper after the end of the course. That does not mean that these articles are useless. They are not only formal requirements to achieve the degree, but they are valuable stepping stones for acquiring important skills: writing scientifically, learning about communications or signal processing, etc. In other words, the student must so to speak throw away the ladder, after he has climbed up on it.

In an effort to reduce the number of ladders thrown away, my colleague last semester required the students to copy their articles into a wiki accessible only for registered members. This was an amazing idea, one that made the seminar much more sustainable than it was before, and browsing through last year's student wiki articles gave me a good idea about what the students are capable of. Nevertheless, while the ladders are not thrown away now, they are still neatly locked up in a room in the basement.

This winter term, in which I am co-responsible for the course, I'd like to go one step further: Of all the ladders the students climb in this term, together with my colleagues we will select the most useful ones and try to make them fit for others to climb: The best student articles should end up as articles on Wikipedia. The idea is not new, as there have been several studies investigating the success of this method (for example, this one; for the supplementary material you need a subscription).

I'm not sure if we will succeed in this. Honestly, I would not want to write a Wikipedia article. But of the eight topics we are going to provide, at least four will be appropriate for an article, and at least two others could extend existing articles. Just to give you an example: As of Septemer 23rd, 2015, there is no Wikipedia article on information dimension. If such an article appears in Wikipedia by the end of January 2016, then the teaching experiment will have been successful. I'll keep you posted!

Tuesday, September 8, 2015

My Story with Polar Codes

It was the end of August 2010, and the weather was unusually good in Dublin. During the breaks at the IEEE Information Theory Workshop we could easily go outside, sit in the grass, and discuss the previous talks. Well, some people discussed, some just listened. Since this was my first conference in information theory (I did not even have a paper there, my boss allowed me to go there without actively participating -- an opportunity I am extremely grateful for), I clearly belonged to the second group. But then, already on the second day, there were some talks I felt comfortable with: Erdal Arikan gave a lecture on Polar Codes, a new coding technique he invented recently. What followed were several talks related to polar coding, including talks from Emmanuel Abbe (who was my main source of inspiration for my investigation of the fractality of polar codes), Tanaka (who looked at the polar coding procedure from a stochastic dynamical system point-of-view), Ido Tal and Alexander Vardy (whose code construction technique was extremely useful in proving fractality), and Eran Hof. While I did not understand a lot from his talk, I owe Eran big time: Being a total noob, I did not know anybody at this conference, and he was so kind to introduce the "big players" to me. That was absolutely necessary, because during one of the breaks I approached Sergio Verdu and asked him about the polar code construction technique he just presented. Well, apparently I confused him with Alexander Vardy (I have no idea why). Anyways, although this was one of the best conferences I've ever been to (an excursion to Castle Malahide, Whiskey tasting at Jameson's, a Riverdance show during the conference dinner, a pleasant stay at a cute little hotel, great weather, nice people, and all this together with my back-then-future-wife), this was just the beginning of my interest in polar coding.

It was in November 2011 when I presented my first paper at an information theory-related conference, the ISWCS in Aachen (during one of the short coffee breaks I met Gerhard Kramer, my current boss, for the first time; I also met Georg Böcherer, just finishing his PhD and winning the best paper award). As usual for these conferences, the first day featured tutorials in the afternoon. One of these tutorials was on polar codes, held by Emmanuel Abbe. I still have the printed handouts; one of the few paper documents I moved from Graz to Munich. It was an unforgettable experience, partly because of the awesome presentation and Emmanuel's great didactic skills, partly because of Emmanuel's lively discussion with the audience (particularly with Tor Aulin). And this great impressions led me to think about possible research directions on the train ride home to Graz. In a document called "Resarch Ideas.txt" I wrote
If a channel (one of the partitioned channels) is already very good (close to perfect), is it possible to assume all its descendant channels to be good? [...] Can we use this to find an approximation of a "good" polar code?
And then nothing happened for quite some time, as I continued my PhD research on information loss in deterministic systems. All this time, these polar codes stayed in the back of my mind and came to the front whenever I attended a conference (there were ALWAYS talks on polar codes). But time went by fast, I finished my PhD and -- totally unexpected -- started working at the Institute for Communications Engineering in Munich, becoming a member of Gerhard's lab and Georg's colleague. Some months there, not much research done (I was busy writing project proposals), the whole lab took a skiing trip to the alps in South Tirol, disguised under the title "Joint Conference on Communications and Coding". Well, in fact we did more research than skiing, something which I am quite grateful for (there are some very embarrassing photos of me trying cross-country skiing...). Instead of presenting work already done, I presented open problems, among them some ideas about polar codes. The preparation for the talk inspired me to write a blog article, and soon after that all the questions in this article were answered. Emmanuel suggested via email to extend the analysis to Reed-Muller codes, which was completed almost equally fast. It was one of the very few lucky streaks I had in my research career so far, and still some open questions pester me.

Although I am not sure if any of the obtained results is useful, I'm extremely happy to have these things out of my mind (and in a paper on arXiv). I could also present these results at the NEWCOM# Emerging Topics Workshop in Cambridge. One of the participants of this workshop was Erdal Arikan, the father of polar codes, and the very same person we were sitting next to during the whiskey tasting event at Jameson's in Dublin five years ago.