Wir untersuchen Modelle für inkrementelle bin ̈are Klassifikation, eine Art maschinelles Lernen. Beispielsweise könnte die Aufgabe des Lernalgorithmus darin bestehen, einen Klassifikator zum Aussortieren von Spam-E-Mails auszugeben. Im Verlauf der Zeit werden dem Lernalgorithmus immer mehr E-Mails mit bekanntem Label (Spam/nicht Spam) übergeben, sodass er den aktuellen Klassifikator stets an diese Trainingsdaten anpasst. Da der Algorithmus m ̈oglichst für jeden Nutzer einen passenden Spamfilter ausgeben soll, suchen wir also einen Lernalgorithmus für die Klasse aller Spam-Klassifikatoren. Den Ausgangspunkt unserer Untersuchungen bildet ein Modell für menschliches und maschinelles Lernen von E. M. Gold.
Im ersten Teil dieser Arbeit untersuchen wir Lernalgorithmen, welche zu jedem Zeitpunkt für die Berechnung des Klassifikators die gesamten bis dahin gesehenen Trainingsdaten heranziehen. Wir können annehmen, dass der Lernalgorithmus immer eine Ausgabe produziert. Weiterhin beeinflusst die Pr ̈asentationsreihenfolge der Trainingsdaten die grundsätzliche Lernbarkeit nicht.
Wir untersuchen auch konsistente Lernprozesse, in denen sich zu jedem Zeitpunkt der ausgegebene Klassifikator an die Label der Trainingsdaten halten muss. Diese zusätzliche Anforderung kann nicht immer erfüllt werden. Mit anderen Worten gibt es Machine Learning Fragestellungen, für die zwar ein erfolgreicher Lernalgorithmus existiert, jedoch kein konsistenter erfolgreicher Lernalgorithmus gefunden werden kann.
Von verschiedenen Forschungsgruppen wurden weitere zusätzliche Anforderungen vorgeschlagen und untersucht. Wir klären für eine etablierte Auswahl solcher Lernerfolgskriterien, wie sich diese paarweise zueinander verhalten. Insbesondere können wir annehmen, dass der inkrementelle Lernalgorithmus den Klassifikator nur dann ver ̈andert, wenn die aktuellen Trainingsdaten dieser letzten Hypothese widersprechen. Ein solches Lernverhalten wird als konservativ bezeichnet.
Darauf folgend beweisen wir formal die intuitiv einleuchtende Behauptung, dass mehr Konzeptklassen gelernt werden können, wenn die geforderte Approximationsgüte im Lernerfolgskriteriums geringer ist. Im Gegensatz zur oszillierenden Hierarchie, wenn der Lernalgorithmus von ausschließlich positiven Daten lernt, ergibt sich eine Dualität abhängig davon, ob das Oszillieren zwischen korrekten Klassifikatoren als erfolgreiches Lernen angesehen wird.
Im zweiten Teil der Arbeit modellieren wir effizientere Lernalgorithmen. Bezogen auf unser Beispiel nutzen diese zur Berechnung des Klassifikators die aktuelle gelabelte E-Mail, haben jedoch keinen unmittelbaren Zugriff auf die zurückliegenden Trainingsdaten. Wir konzentrieren uns auf hypothesenbasierte und zustandsbasierte Lernalgorithmen, die im Folgenden genauer beschrieben werden.
Hypothesenbasierte Lernalgorithmen nutzen den letzten Klassifikator und die aktuelle gelabelte E-Mail, um den neuen Klassifikator zu berechnen. Wir vergleichen Lernerfolgskriterien bezogen auf iterative Lernalgorithmen. Ein weiteres wichtiges Beispiel ist U-shapedness, ein in den Kognitionswissenschaften beobachtetes Phänomen. Ein Lernprozess enthält einen U-Shape, falls ein für den Nutzer optimaler Klassifikator zwischenzeitlich verworfen wird, jedoch der Lernalgorithmus später erneut eine korrekte Ausgabe produziert. Wir zeigen, dass hypothesenbasierte Lernalgorithmen durch das Verbieten von U-Shapes eingeschränkt werden.
Zustandbasierte Lernalgorithmen berechnen den neuen Klassifikator ausgehend vom aktuellen Datum und den aktuellen Parametern (Zustand) des Lernalgorithmus. Beispielsweise werden bei einem klassischen Gradientenverfahren stets die neuen Parameter des Klassifikators ausgehend von den vorhergehenden Parametern berechnet, während die Hyperparameter konstant bleiben. Wir leiten für zustandsbasierte Lernalgorithmen alle paarweisen Beziehungen der oben erwähnten Auswahl von Lernerfolgskriterien her.
Konservativität und syntaktische Non-U-Shapedness schr ̈anken zustandsbasierte Lernalgorithmen ein. Weiterhin sind hypothesen- und zustandsbasierte Lernalgorithmen für einen Großteil der untersuchten Lernerfolgskriterien äquivalent. Ist syntaktische Non-U-Shapedness Teil des Lernerfolgskriteriums, können zustandbasierte Lernalgorithmen mehr Konzeptklassen lernen, als hypothesenbasierte Lernalgorithmen. Es ist also im Allgemeinen nicht möglich aus den Parametern den zugehörigen Klassifikator zu rekonstruieren.
Wir belegen die behaupteten Äquivalenzen und Separationen durch formale mathematische Beweise. Insbesondere nutzen wir unendliche Fixpunktsätze aus der Berechenbarkeitstheorie.
