TY - THES A1 - Seidel, Karen T1 - Modelling binary classification with computability theory T1 - Binäre Klassifikation modellieren mit Berechenbarkeitstheorie N2 - 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 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). N2 - 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 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). KW - Binary Classification KW - Recursion KW - U-Shaped-Learning KW - Simulation KW - Binäre Klassifikation KW - Rekursion KW - U-Förmiges Lernen KW - Simulation Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-529988 ER - TY - JOUR A1 - Göbel, Andreas A1 - Lagodzinski, Gregor J. A. A1 - Seidel, Karen T1 - Counting homomorphisms to trees modulo a prime JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery N2 - Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #(p) HOMSTOH, the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree H and every prime p the problem #pHOMSTOH is either polynomial time computable or #P-p-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of #pHOMSTOH are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p. These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p. KW - Graph homomorphisms KW - modular counting KW - complexity dichotomy Y1 - 2021 U6 - https://doi.org/10.1145/3460958 SN - 1942-3454 SN - 1942-3462 VL - 13 IS - 3 SP - 1 EP - 33 PB - Association for Computing Machinery CY - New York ER - TY - BOOK A1 - Jennek, Julia A1 - Rother, Stefanie A1 - Tosch, Frank A1 - Wendland, Mirko A1 - Kludt, Steffen A1 - Krauskopf, Karsten A1 - Kitschke, Dorothea A1 - Maar, Verena A1 - Knigge, Michel A1 - Gnädig, Susanne A1 - Seidel, Astrid A1 - Siehr, Karl-Heinz A1 - Wienecke, Maik A1 - Günther, Claudia-Susanne A1 - Reitz-Koncebovski, Karen A1 - Klöpping, Peter M. A1 - Kücholl, Denise A1 - Lazarides, Rebecca A1 - Westphal, Andrea A1 - Scherreiks, Lynn A1 - Kuhr, Linda A1 - Wilbert, Jürgen A1 - Gronostaj, Anna A1 - Vock, Miriam A1 - Zaruba, Nicole A1 - Ahlgrimm, Frederik A1 - Link, Jörg-Werner A1 - Körner, Dorothea A1 - Barseghyan, Anahit A1 - Glowinski, Ingrid ED - Jennek, Julia T1 - Professionalisierung in Praxisphasen BT - Ergebnisse der Lehrerbildungsforschung an der Universität Potsdam T3 - Potsdamer Beiträge zur Lehrerbildung und Bildungsforschung N2 - Schulpraktika bilden die zentrale Grundlage der Lehrerbildung in Potsdam. Bereits im Potsdamer Modell der Lehrerbildung (1993) sind sie festgehalten, seit der Integration des Schulpraktikums (Praxissemesters) 2008 absolvieren alle Potsdamer Lehramtsstudierenden fünf Pflichtpraktika. Während die Ziele der Praktika klar beschrieben sind, sind die tatsächlichen Lernerfolge nicht immer klar – ebenso wenig, wie die Begleitung der Praktika aussehen muss, um die Studierenden bestmöglich zu unterstützen. Auch die Integration in weitere Lehrveranstaltungen des Studiums ist ein noch offenes Feld, das weiterer Betrachtung verdient. Die unterschiedliche Ausrichtung der Potsdamer Praktika, Perspektivwechsel im Orientierungs-/Integriertem Eingangspraktikum, Selbstreflektion im Praktikum in pädagogisch-psychologischen Handlungsfeldern, Unterricht als Profession in den Fachdidaktischen Tagespraktika, Anwendung von Diagnostik im psychodiagnostischen Praktikum und die Synthese all dessen im Schulpraktikum, bieten dafür zahlreiche Ansatzpunkte. Schulpraktika sind nicht nur ein zentraler und von Studierenden hoch geschätzter Bestandteil des Studiums, sondern werden auch zunehmend für die Bildungsforschung interessant. Fragen nach der Kompetenzentwicklung, Selbsteinschätzungen und der Entwicklung der Reflexionsfähigkeit von Studierenden stehen dabei ebenso im Fokus wie die Einschätzung der universitären Begleitung und der Einbindung ins weitere Studium. Der vorliegende Band versammelt Studien von Wissenschaftlerinnen und Wissenschaftler der Universität Potsdam, die die fünf Pflichtpraktika im Lehramtsstudium unter unterschiedlichen Blickwinkel beforschen. Besonders hervorzuheben ist, dass die Wissenschaftlerinnen und Wissenschaftler aus unterschiedlichen Disziplinen stammen und somit die Praktika mit verschiedenen Instrumenten und aus unterschiedlichen Blickwinkeln betrachten. Die präsentierten Ergebnisse bilden eine gute Grundlage, um die Praktika in Potsdam und an anderen Standorten weiterzuentwickeln. T3 - Potsdamer Beiträge zur Lehrkräftebildung und Bildungsforschung - 2 KW - Lehrkräftebildung KW - Schulpraktikum KW - Lehramtsstudium KW - Berufspraktische Studien KW - Praxissemester Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-500964 SN - 978-3-86956-508-8 SN - 2626-3556 SN - 2626-4722 IS - 2 PB - Universitätsverlag Potsdam CY - Potsdam ER -