Funktionsapproximation anhand eingeschränkter Information

Eine Funktion beschreibt einen Zusammenhang zwischen einer Einflussgröße und einer Zielgröße. Hierbei kann es sich um alle möglichen messbaren Größen handeln, beispielsweise die morgige Höchsttemperatur in Wien in Abhängigkeit verschiedenster Wetterdaten von heute, oder auch die Wahrscheinlichkeit, dass eine gegebene Fotoaufnahme auf Hautkrebs hindeutet. Der genaue Zusammenhang zwischen Einfluss- und Zielgröße ist in der Regel unbekannt. Wir wollen diesen Zusammenhang möglichst genau erlernen. In anderen Worten: Wir wollen die Funktion approximieren. Auf Basis unserer Approximation können wir dann Prognosen für die Zukunft treffen. Um den Zusammenhang zu erlernen, stehen uns gewisse Daten zur Verfügung. In einigen Fällen können wir diese Daten aktiv sammeln und Messungen durchführen, die uns möglichst viel über die unbekannte Funktion verraten. In anderen Fällen haben wir nur eingeschränkten Einfluss auf die Messungen oder müssen mit einer bereits vorhandenen Datensammlung vorliebnehmen. Dieses Projekt beschäftigt sich mit der Frage, inwieweit diese Einschränkungen bei der Datenerhebung zu einer schlechteren Prognose führen. Beispielsweise stellt sich in überraschend vielen Fällen heraus, dass zufällig erhaltene Daten fast genauso gut sind, wie die Daten komplizierter und sorgfältig ausgewählter Messungen. Unter anderem dieses Phänomen wollen wir genauer untersuchen. Hierbei beschäftigen wir uns vor allem mit den mathematischen Modellen und Hintergründen. Wir untersuchen die obige Fragestellung für möglichst allgemeine und abstrakte Klassen von Funktionen, so dass die erzielten Forschungsergebnisse für möglichst viele Anwendungen nützlich sind.

Funktionen beschreiben wie sich eine messbare Größe durch verschiedene Einflussgrößen bestimmt. Die genaue Abhängigkeit ist in den meisten Anwendungen unbekannt, sodass es notwendig ist, die unbekannte Funktion zu approximieren. Dies geschieht auf der Grundlage von Modellannahmen einerseits und endlich vielen Daten andererseits. Die Daten können z.B. durch physikalische Messungen oder Computerprogramme gewonnen werden. Oft können die Messungen nicht frei gewählt werden und die Informationsgewinnung ist in ein oder anderer Weise eingeschränkt. Ziel dieses Projektes war es, die Qualität eingeschränkter Information und somit die Auswirkungen dieser Einschränkung zu studieren. Drei Arten von Einschränkungen wurden betrachtet: 1. Die Güte der Approximation ist meist gut verstanden, wenn wir Zugriff auf allgemeine lineare Messungen haben (z.B. Fourierkoeffizienten). In der Praxis ist dies oft nicht der Fall und wir können nur Funktionswerte abfragen. Wie viel wir durch diese Einschränkung verlieren, hängt davon ab, wie wir den Fehler (also den Abstand zwischen unserer Approximation und der unbekannten Funktion) messen. Wir konnten die Frage in mindestens zwei wichtigen Fällen beantworten: Für den mittleren quadratischen Fehler und für den uniformen Fehlers. Ersterer verlangt eine gute Approximation im Durchschnitt und zweiterer fordert eine gute Approximation in jedem einzelnen Punkt. In beiden Situationen konnten wir eine allgemeine Bedingung angeben, unter welcher die Einschränkung beinahe keinerlei negative Auswirkungen auf den Fehler hat. Ist die Bedingung dagegen nicht erfüllt, so kann die Einschränkung den Fehler erheblich vergrößern. In diesem Fall geben wir eine obere Schranke für den größtmöglichen Verlust. 2. In einigen Anwendungen lassen sich nicht einmal die Punkte frei wählen, an welchen wir Information über die Funktionswerte erhalten. Wir studierten die Situation, in welcher wir Daten an zufälligen und identisch verteilen Punkten erhalten. Dabei identifizierten wir viele Situationen, in welchen derartige Daten praktisch genauso informativ wie Funktionswerte an optimal gewählten Beobachtungspunkten sind. Schon ein logarithmisches Oversampling kompensiert den Verlust durch diese Einschränkung. Die resultierenden Algorithmen sind in einigen Fällen sogar besser als jeder andere bekannte Algorithmus (z.B. Smolyaks Algorithmus). Es stellte sich zudem heraus, dass diese Art Information bereits ausreicht, um den Fluch der Dimensionen für eine große Klasse von (ungewichteten) Approximationsproblemen zu widerlegen. 3. Die dritte Art der Einschränkung betrifft die adaptive Informationsgewinnung. Im Allgemeinen kann es vorteilhaft sein, die Messungen adaptiv durchzuführen, also die Parameter der folgenden Messungen anhand der bereits gewonnen Daten zu wählen. Dies ist jedoch oft nicht möglich und es müssen dieselben Messpunkte für jeden Input verwendet werden. Im Projekt wurde der Verlust durch die Einschränkung von adaptiver zu nicht-adaptiver Information studiert. Tatsächlich konnten wir sogar den maximalen Verlust begrenzen, der entsteht, wenn wir uns von adaptiven Algorithmen, die Zufallszahlen verwenden dürfen, auf nicht-adaptive Algorithmen ohne Zufallszahlen beschränken. Ein Fortschritt unserer Analyse liegt auch darin, dass die Modellklasse keine Symmetrie aufweisen muss.