Robuste Lernverfahren und Datenkomprimierung
Final Report Abstract
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.
Publications
- J. Arpe, B. Manthey, Approximability of Minimum AND-Circuits. In L. Arge, R. Freivalds (Hrsg.), Proc. SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 2006, Lecture Notes in Comput. Science 4059, 292-303.
- J. Arpe, R, Reischuk, When Does Greedy Learning of Relevant Attributes Succeed? - A Fourier-based Characterization. Technical Report ECCC TR06-065, Electronic Colloquium on Computational Complexity, Mai 2006.
- J. Arpe, R. Reischuk, Learning Juntas in the Presence of Noise. In J.-Y. Cai, S. Cooper, and A. Li (Hrsg.), Proc. Theory and Applications of Models of Computation, Third Annual Conference, TA MC 2006, Beijing, China, May 2006, Lecture Notes in Computer Science 3959, 387-398, 2006.
- 14. Theorietag der GI-Fachgruppe "Automaten und Formale Sprachen", Caputh bei Potsdam, September 2004. vollständige Version als Technischer Bericht SIIM-TR-A-Ö4-14, Schriftenreihe der Institute für Informatik und Mathematik, Universität zu Lübeck, 2004.
- J. Arpe, Learning Concepts with Few Unknown Relevant Attributes from Noisy Data. Dissertation, Institut für Theoretische Universität, Universität zu Lübeck, August 2006.
- J. Arpe, R. Reischuk, Learning Juntas in the Presence of Noise. Theoretical Computer Science 384 (Special Issue), 2007, 2-21.
- J. Arpe, R. Reischuk, On the Complexity of Optimal Grammar-Based Compression. In J. Storer, M. Cohn (Hrsg.), Proc. Data Compression Conference, 28-30 March 2006, Snowbird, Utah, 173-182, IEEE Computer Society, 2006.
- J. Case, S. Jain, R. Reischuk, F. Stephan, T. Zeugmann, Learning a Subclass of Regular Patterns in Polynomial Time, Theoretical Computer Science 364 (Special Issue), 2006, 115-131.
