Informationen und Download

Meine Diplomarbeit habe ich 2009 eingereicht. Sie trägt den Titel „Fast-optimale Rate für adaptive Schätzer in einem Regressionsproblem“.

Download

Über die Arbeit

Im folgenden möchte ich versuchen, den Inhalt der Arbeit so verständlich wie möglich darzulegen.

In der Regression oder Ausgleichsrechnung geht es grob gesagt darum, sich als moderner Hellseher zu betätigen. Man betrachtet zwei Zahlengrößen X und Y, die auf unbekannte Art und Weise voneinander abhängen. X könnte z.B. der Preis sein, zu dem ich ein bestimmtes Produkt anbiete und Y könnte der daraus resultierende monatliche Absatz sein. Intuitiv ist uns allen klar, dass X und Y voneinander abhängen: Man wird vermuten, dass umso weniger Produkte verkauft werden, je höher der Preis ist. Aber auch das muss nicht unbedingt so sein: „Was nichts ist, kostet nichts.“
Sei es, wie es sei, wir wollen auf jeden Fall eine Art finden, wie wir Y ausrechnen können, wenn wir X kennen. Wir suchen also eine Funktion f mit Y=f(X). Anders herum nennen wir f(X) einen Schätzer für Y.
Erschwerend kommt allerdings dazu, dass die Zahl Y zufällig ist. Natürlich nicht komplett zufällig, aber es werden kaum in jedem Monat dieselbe Anzahl Produkte verkauft werden, vielmehr wird diese Zahl schwanken.
Ein klassischer Hellseher würde jetzt einfach behaupten, dass er die Funktion f kenne und eine Menge Geld kassieren, aber wir sind Wissenschaftler! Und was machen Wissenschaftler in einem solchen Fall? Sie machen eine Stichprobe. Z.B. machen wir eine Umfrage und schauen nach, wie viele Leute unser Produkt zu einem bestimmten Preis kaufen würden. Zu Preisen x1, x2, x3, …, xn erhalten wir so Verkaufszahlen y1, y2, y3, …, yn. Das könnte z.B. so aussehen:
Mit dieser Stichprobe haben wir nun etwas in der Hand, auf das wir unsere Vermutungen stützen können: Man könnte z.B. sagen, dass die Punkte alle recht genau auf einer Geraden liegen. In einem solchen Fall würde man sagen, dass f(x)=mx+b gilt und dann m und b so bestimmen, dass es „am besten passt“ (so etwas nennt sich Regressionsgerade). Unser Problem reduziert sich also darauf zwei Zahlen m und b zu schätzen.

Vielleicht ahnen Sie schon, dass man eine Menge Humbug ausrechnet, wenn die unbekannte Funktion f nun doch keine Gerade sein sollte. Das Problem kann man beheben, indem man annimmt, dass f eine Parabel ist oder eine Funktion noch höheren Grades, z.B.

f(x)=ax³+bx²+cx+d

Wenn man das tut, reicht es also immer aus, endlich viele Parameter a, b, … zu schätzen. So etwas nennt man daher einen parametrischen Schätzer. Man hat dabei aber immer das Problem, dass man in der Praxis einfach nicht weiß, welchen Grad die zu schätzende Funktion f hat.

In unserem Beispiel oben ist f in Wirklichkeit eine quadratische Funktion. Wir liegen also mit unserer Schätzung ziemlich daneben:
Im Bild ist die rote Linie unsere Schätzung und die blaue Linie die wahre Funktion. In einigen Bereichen liegen diese sehr stark auseinander.
Wir können dieses Problem umgehen, wenn wir sogenannte nicht-parametrische Schätzer verwenden.

Wenn man sich einmal auf ein solches Verfahren eingeschossen hat, kann man folgende Überlegung anstellen: Je größer ich meine Stichprobe mache, desto besser sollte meine Schätzung für die unbekannte Funktion f sein. Andersherum formuliert sollte mein Schätz-Fehler [Y-f(X)]² immer kleiner werden, je größer meine Stichprobe wird (das Quadrat ist nur dafür da, damit Y-f(X) nicht negativ wird). Für n gegen unendlich sollte also der Fehler gegen null konvergieren, d.h., sich immer weiter der Null annähern.

Nun reicht es aber für die Praxis nicht aus, zu wissen, dass der Fehler gegen null konvergiert, denn Stichproben kosten Geld und große Stichproben kosten verdammt viel Geld. Es ist also wichtig zu wissen, wie schnell der Fehler gegen null geht. Dies nennt man die Rate der Konvergenz. Der Mathematiker C. Stone hat 1977 bewiesen, dass der Fehler nicht schneller als n^(-2p/(2p+d)) gegen null konvergieren kann. Hierbei ist d die Dimension von X (in unserem Beispiel ist X eine Zahl und kein Vektor, daher ist hier d=1) und p ist der Glattheitsgrad der unbekannten Funktion f, d.h. die Funktion f ist p-mal differenzierbar (es gibt die p-te Ableitung). Denken Sie hierüber nicht zu viel nach, denn selbst wenn Sie wissen was eine Ableitung ist, kennen Sie höchstwahrscheinlich nur Funktionen, die unendlich oft abgeleitet werden können.
Wenn wir annehmen, dass unsere unbekannte Funktion unendlich oft abgeleitet werden kann, d.h. p=unendlich, sagt uns das Ergebnis von Stone, dass der Fehler nicht schneller als 1/n gegen null gehen kann. D.h., bei einer Stichprobe von 100 ist der Fehler immer noch größer als 1/100 (das erscheint jetzt wenig, aber leider wird diese 1/100 noch mit irgendeiner unbekannten, möglicherweise großen Zahl multipliziert).

Nun ist aber das Problem, dass Stone zwar gezeigt hat, dass es nicht schneller gehen kann als obiger Ausdruck, nicht aber, dass man diese Rate auch wirklich erreichen kann.

Diesem Problem haben sich die drei Autoren Michael Kohler, Adam Krzyzak und Dominik Schäfern angenommen und in einem Artikel im Magazin Bernoulli behaupteten Sie, dass Sie einen Schätzer gefunden haben, der die von Stone angegebene Rate fast erreicht. „Fast“ heißt in diesem Fall, dass noch ein Logarithmus in der Formel vorkommt, aber vielleicht wissen Sie noch aus der Schulzeit, dass der Logarithmus eine der Funktionen ist, die am langsamsten wächst (z.B. ist log(10000)=5). Für die Praxis spielt dieser Faktor also keine Rolle.

Meine Aufgabe bestand darin, den Beweis der Autoren auf Fehler zu untersuchen und bestehende Beweislücken zu schließen. Dafür musste ich mich tief in die sogenannte Vapnik-Chervonenkis-Theorie und die Theorie der gleichmäßigen Gesetze der großen Zahl einarbeiten. Das Ergebnis war, dass ich tatsächlich einen Fehler gefunden habe, der nicht zu reparieren gewesen ist. Dies können Sie im Detail in meiner Arbeit nachlesen.