Karen Seidel

• We investigate models for incremental binary classification, an example for supervised online learning. Our starting point is a model for human and machine learning suggested by E.M.Gold. In the first part, we consider incremental learning algorithms that use all of the available binary labeled training data in order to compute the current hypothesis. For this model, we observe that the algorithm can be assumed to always terminate and that the distribution of the training data does not influence learnability. This is still true if we pose additional delayable requirements that remain valid despite a hypothesis output delayed in time. Additionally, we consider the non-delayable requirement of consistent learning. Our corresponding results underpin the claim for delayability being a suitable structural property to describe and collectively investigate a major part of learning success criteria. Our first theorem states the pairwise implications or incomparabilities between an established collection of delayable learning successWe investigate models for incremental binary classification, an example for supervised online learning. Our starting point is a model for human and machine learning suggested by E.M.Gold. In the first part, we consider incremental learning algorithms that use all of the available binary labeled training data in order to compute the current hypothesis. For this model, we observe that the algorithm can be assumed to always terminate and that the distribution of the training data does not influence learnability. This is still true if we pose additional delayable requirements that remain valid despite a hypothesis output delayed in time. Additionally, we consider the non-delayable requirement of consistent learning. Our corresponding results underpin the claim for delayability being a suitable structural property to describe and collectively investigate a major part of learning success criteria. Our first theorem states the pairwise implications or incomparabilities between an established collection of delayable learning success criteria, the so-called complete map. Especially, the learning algorithm can be assumed to only change its last hypothesis in case it is inconsistent with the current training data. Such a learning behaviour is called conservative. By referring to learning functions, we obtain a hierarchy of approximative learning success criteria. Hereby we allow an increasing finite number of errors of the hypothesized concept by the learning algorithm compared with the concept to be learned. Moreover, we observe a duality depending on whether vacillations between infinitely many different correct hypotheses are still considered a successful learning behaviour. This contrasts the vacillatory hierarchy for learning from solely positive information. We also consider a hypothesis space located between the two most common hypothesis space types in the nearby relevant literature and provide the complete map. In the second part, we model more efficient learning algorithms. These update their hypothesis referring to the current datum and without direct regress to past training data. We focus on iterative (hypothesis based) and BMS (state based) learning algorithms. Iterative learning algorithms use the last hypothesis and the current datum in order to infer the new hypothesis. Past research analyzed, for example, the above mentioned pairwise relations between delayable learning success criteria when learning from purely positive training data. We compare delayable learning success criteria with respect to iterative learning algorithms, as well as learning from either exclusively positive or binary labeled data. The existence of concept classes that can be learned by an iterative learning algorithm but not in a conservative way had already been observed, showing that conservativeness is restrictive. An additional requirement arising from cognitive science research %and also observed when training neural networks is U-shapedness, stating that the learning algorithm does diverge from a correct hypothesis. We show that forbidding U-shapes also restricts iterative learners from binary labeled data. In order to compute the next hypothesis, BMS learning algorithms refer to the currently observed datum and the actual state of the learning algorithm. For learning algorithms equipped with an infinite amount of states, we provide the complete map. A learning success criterion is semantic if it still holds, when the learning algorithm outputs other parameters standing for the same classifier. Syntactic (non-semantic) learning success criteria, for example conservativeness and syntactic non-U-shapedness, restrict BMS learning algorithms. For proving the equivalence of the syntactic requirements, we refer to witness-based learning processes. In these, every change of the hypothesis is justified by a later on correctly classified witness from the training data. Moreover, for every semantic delayable learning requirement, iterative and BMS learning algorithms are equivalent. In case the considered learning success criterion incorporates syntactic non-U-shapedness, BMS learning algorithms can learn more concept classes than iterative learning algorithms. The proofs are combinatorial, inspired by investigating formal languages or employ results from computability theory, such as infinite recursion theorems (fixed point theorems).…
• Wir untersuchen Modelle für inkrementelle binäre Klassifikation, ein Beispiel für überwachtes online Lernen. Den Ausgangspunkt bildet ein Modell für menschliches und maschinelles Lernen von E.M.Gold. Im ersten Teil untersuchen wir inkrementelle Lernalgorithmen, welche zur Berechnung der Hypothesen jeweils die gesamten binär gelabelten Trainingsdaten heranziehen. Bezogen auf dieses Modell können wir annehmen, dass der Lernalgorithmus stets terminiert und die Verteilung der Trainingsdaten die grundsätzliche Lernbarkeit nicht beeinflusst. Dies bleibt bestehen, wenn wir zusätzliche Anforderungen an einen erfolgreichen Lernprozess stellen, die bei einer zeitlich verzögerten Ausgabe von Hypothesen weiterhin zutreffen. Weiterhin untersuchen wir nicht verzögerbare konsistente Lernprozesse. Unsere Ergebnisse bekräftigen die Behauptung, dass Verzögerbarkeit eine geeignete strukturelle Eigenschaft ist, um einen Großteil der Lernerfolgskriterien zu beschreiben und gesammelt zu untersuchen. Unser erstes Theorem klärt für dieses Modell dieWir untersuchen Modelle für inkrementelle binäre Klassifikation, ein Beispiel für überwachtes online Lernen. Den Ausgangspunkt bildet ein Modell für menschliches und maschinelles Lernen von E.M.Gold. Im ersten Teil untersuchen wir inkrementelle Lernalgorithmen, welche zur Berechnung der Hypothesen jeweils die gesamten binär gelabelten Trainingsdaten heranziehen. Bezogen auf dieses Modell können wir annehmen, dass der Lernalgorithmus stets terminiert und die Verteilung der Trainingsdaten die grundsätzliche Lernbarkeit nicht beeinflusst. Dies bleibt bestehen, wenn wir zusätzliche Anforderungen an einen erfolgreichen Lernprozess stellen, die bei einer zeitlich verzögerten Ausgabe von Hypothesen weiterhin zutreffen. Weiterhin untersuchen wir nicht verzögerbare konsistente Lernprozesse. Unsere Ergebnisse bekräftigen die Behauptung, dass Verzögerbarkeit eine geeignete strukturelle Eigenschaft ist, um einen Großteil der Lernerfolgskriterien zu beschreiben und gesammelt zu untersuchen. Unser erstes Theorem klärt für dieses Modell die paarweisen Implikationen oder Unvergleichbarkeiten innerhalb einer etablierten Auswahl verzögerbarer Lernerfolgskriterien auf. Insbesondere können wir annehmen, dass der inkrementelle Lernalgorithmus seine Hypothese nur dann verändert, wenn die aktuellen Trainingsdaten der letzten Hypothese widersprechen. Ein solches Lernverhalten wird als konservativ bezeichnet. Ausgehend von Resultaten über Funktionenlernen erhalten wir eine strikte Hierarchie von approximativen Lernerfolgskriterien. Hierbei wird eine aufsteigende endliche Zahl von \emph{Anomalien} (Fehlern) des durch den Lernalgorithmus vorgeschlagenen Konzepts im Vergleich zum Lernziel erlaubt. Weiterhin ergibt sich eine Dualität abhängig davon, ob das Oszillieren zwischen korrekten Hypothesen als erfolgreiches Lernen angesehen wird. Dies steht im Gegensatz zur oszillierenden Hierarchie, wenn der Lernalgorithmus von ausschließlich positiven Daten lernt. Auch betrachten wir einen Hypothesenraum, der einen Kompromiss zwischen den beiden am häufigsten in der naheliegenden Literatur vertretenen Arten von Hypothesenräumen darstellt. Im zweiten Teil modellieren wir effizientere Lernalgorithmen. Diese aktualisieren ihre Hypothese ausgehend vom aktuellen Datum, jedoch ohne Zugriff auf die zurückliegenden Trainingsdaten. Wir konzentrieren uns auf iterative (hypothesenbasierte) und BMS (zustandsbasierte) Lernalgorithmen. Iterative Lernalgorithmen nutzen ihre letzte Hypothese und das aktuelle Datum, um die neue Hypothese zu berechnen. Die bisherige Forschung klärt beispielsweise die oben erwähnten paarweisen Vergleiche zwischen den verzögerbaren Lernerfolgskriterien, wenn von ausschließlich positiven Trainingsdaten gelernt wird. Wir vergleichen verzögerbare Lernerfolgskriterien bezogen auf iterative Lernalgorithmen, sowie das Lernen von aussschließlich positiver oder binär gelabelten Daten. Bereits bekannt war die Existenz von Konzeptklassen, die von einem iterativen Lernalgorithmus gelernt werden können, jedoch nicht auf eine konservative Weise. U-shapedness ist ein in den Kognitionswissenschaften beobachtetes Phänomen, demzufolge der Lerner im Lernprozess von einer bereits korrekten Hypothese divergiert. Wir zeigen, dass iterative Lernalgorithmen auch durch das Verbieten von U-Shapes eingeschränkt werden. Zur Berechnung der nächsten Hypothese nutzen BMS-Lernalgorithmen ergänzend zum aktuellen Datum den aktuellen Zustand des Lernalgorithmus. Für Lernalgorithmen, die über unendlich viele mögliche Zustände verfügen, leiten wir alle paarweisen Implikationen oder Unvergleichbarkeiten innerhalb der etablierten Auswahl verzögerbarer Lernerfolgskriterien her. Ein Lernerfolgskriterium ist semantisch, wenn es weiterhin gilt, falls im Lernprozess andere Parameter ausgegeben werden, die jeweils für die gleichen Klassifikatoren stehen. Syntaktische (nicht-semantische) Lernerfolgskriterien, beispielsweise Konservativität und syntaktische Non-U-Shapedness, schränken BMS-Lernalgorithmen ein. Um die Äquivalenz der syntaktischen Lernerfolgskriterien zu zeigen, betrachten wir witness-based Lernprozesse. In diesen wird jeder Hypothesenwechsel durch einen später korrekt klassifizierten Zeugen in den Trainingsdaten gerechtfertig. Weiterhin sind iterative und BMS-Lernalgorithmen für die semantischen verzögerbaren Lernerfolgskriterien jeweils äquivalent. Ist syntaktische Non-U-Shapedness Teil des Lernerfolgskriteriums, sind BMS-Lernalgorithmen mächtiger als iterative Lernalgorithmen. Die Beweise sind kombinatorisch, angelehnt an Untersuchungen zu formalen Sprachen oder nutzen Resultate aus dem Gebiet der Berechenbarkeitstheorie, beispielsweise unendliche Rekursionstheoreme (Fixpunktsätze).…