Robust learning methods and data compression

Klassisch wird der Aufwand zur Lösung algorithmischer Probleme durch die worst-case Komplexität gemessen und es wird gefordert bzw. angenommen, daß das Problems exakt zu lösen ist und die Eingabedaten fehlerfrei vorliegen. Für viele Optimierungsproblemen kann es keine exakten worst-case effizienten Lösungsverfahren geben, falls komplexitätstheoretische Vermutungen wie P 54 .... zutreffen. Deshalb sind auch die average-case Komplexität und approximative Lösungsverfahren von Interesse. Für das Sortieren von Daten, für Informationsübertragung in Netzen sowie beim algorithmischen Lernen Boolescher Funktionen haben wir hierzu in der ersten Projektphase Untersuchungen begonnen und wollen diese weiterführen. Daneben sollen auch online und Sicherheitsaspekte berücksichtigt werden. Bei manchen Anwendungen - etwa bei der Verarbeitung molekularbiologischer Daten - ist die Situation dadurch erschwert, daß die Eingabedaten mit Fehlern behaftet sind. Es sollen algorithmische Methoden entwickelt werden, die unter derartigen inpräzisen Bedingungen dennoch eine effiziente und robuste Problemlösung ermöglichen. Für das Shortest-Common-Superstring-Problem sowie das Lernen relevanter Attribute ist derartiges bereits geschehen. Ein längerfristiges Ziel ist es, bei kombinatorischen Problemen Eigenschaften zu finden, die zu der notwendigen Eingabepräzision korrelieren.

Im Vergleich zum Wissensstand bei Antragstellung dieses Projektes können wir bislang folgende Erkenntnisse aufführen. Das robuste Lernen relevanter Attribute wurden umfassende Ergebnisse erzielt. Weitere Resultate in diesem Bereich werden Methoden benötigen, die weit über das Projektziel hinaus gehen. Beispielsweise werden für untere Schranken Härteergebnisse zur Average-Komplexität von Kodierungsproblemen benötigt, eine der schwierigsten Herausforderungen der Komplexitätstheorie. Zur Verbesserungen der oberen Laufzeitschranken wird es unumgänglich sein, neue strukturelle Eigenschaften Boolescher Funktionen auszunutzen, die erst noch zu erforschen sind. Im Bereich der Grammatik-basierten Komprimierung wurden erste Robustheitsergebnisse erzielt. Darüber hinaus wurde ein Beitrag dazu geleistet die Problematik bei der Bestimmung von Approximationsgüten besser zu verstehen. Schließlich haben wir wesentliche Fortschritte bei der komplexitätstheoretischen Klassifizierung optimaler Grammatik-basierter Komprimierung binärer Strings erzielt. Das Grundproblern auf diesem Gebiet besteht darin, dass die algorithmische Verarbeitung hierarchischer Strukturen bisher nicht sehr gut verstanden ist und es keine Standardmethoden zur Analyse gibt. Zum Thema "Minimale UND-Schaltkreise" konnten unter anderem untere und obere Approximationstichranken sowie Fixed-Parameter-Eigenschaften bewiesen werden. Eine Verallgemeinerung dieses Problems führt zu einer vereinheitlichten Sicht von UND-Schaltkreisen. Grammatik-basierter Kompression und Additionsketten. Eine Präzisierung übergreifender Modelle und Begriffe ist nach wie vor schwierig. Umfassende Ergebnisse konnten vor allem im Bereich des Algorithmischen Lernens erzielt werden. Hier ist der Begriff des Lernens anhand fehler behafteter Daten jedoch bereits in einer Vielzahl an Modellierungen ausgeprägt.