Strukturen durch Lernen klassifizieren

Der Begriff der Klassifikation formalisiert die Idee von Ähnlichkeit zwischen mathematischen Objekten. Eine Klasse von Strukturen zu klassifizieren, bedeutet die Objekte in der Klasse modulo einer Äquivalenzrelation zu identifizieren, typischerweise anhand von Wissen über die strukturellen, algebraischen oder algorithmischen Eigenschaften der betrachteten Objekte. In der berechenbaren Strukturtheorie existieren mehrere etablierte Ansätze, Strukturen zu klassifizieren. In diesem Projekt schlagen wir eine neue Richtung vor, um unendliche Strukturen on-the-fly zu klassifizieren, d.h. während wir nur einen endlichen Teil des betrachteten Objekts sehen. Angenommen wir haben eine endliche oder unendliche Ansammlung von unendlichen mathematischen Objekten. Weiters nehmen wir an, dass wir über eines dieser Objekte Schritt für Schritt Informationen erhalten. In jedem Schritt sehen wir ein neues, endliches Teilstück an Informationen über die Struktur. Das Ziel ist es dann, zu bestimmen um welches der Objekte es sich handelt, und das nach nur endlich vielen Schritten, d.h. ohne zu warten, bis die vollständige Struktur bekannt ist. Wir klassifizieren, oder lernen, die Klasse, wenn wir nach endlich vielen Schritten die korrekte Struktur identifizieren können. Diese Aufgabe ist nicht trivial, nicht einmal für den Fall, dass wir nur zwei Strukturen in der Klasse haben: es existieren zweielementige Klassen, die nicht lernbar sind und zweielementige Klassen, die lernbar sind. Für die Formalisierung des Frameworks und die Beantwortung der aufkommender Fragen, kombinieren wir die Begriffe, Ansätze und Methoden aus der berechenbaren Strukturtheorie und der algorithmischen Lerntheorie. Je nachdem wie wir die Parameter, wie Informationsquelle, Konvergenzverhalten, zugrundeliegende Äquivalenzrelation usw., setzten, bekommen wir unterschiedliche Arten der Klassifikation, oder des Lernens. Das Hauptziel des Projektes ist es, diese Arten der on-the-fly-Klassifikation zu charakterisieren, abhängig von den gewählten Parametern. Wir wollen auch natürliche Beispiele für Klassen von Strukturen finden, die lernbar unter manchen Parametern und nicht lernbar unter anderen Parametern sind. Wir wollen also die verschiedenen Arten von Lernen unterscheiden, indem wir Klassen finden, die in einem Framework lernbar sind und in einem anderen nicht. Weiters wollen wir verstehen, wie viel Rechenleistung notwendig ist, um verschiedene Klassen auf verschiedene Arten zu klassifizieren.