@phdthesis{Seidel2021, author = {Seidel, Karen}, title = {Modelling binary classification with computability theory}, doi = {10.25932/publishup-52998}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-529988}, school = {Universit{\"a}t Potsdam}, pages = {viii, 120}, year = {2021}, abstract = {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).}, language = {en} } @article{GoebelLagodzinskiSeidel2021, author = {G{\"o}bel, Andreas and Lagodzinski, Gregor J. A. and Seidel, Karen}, title = {Counting homomorphisms to trees modulo a prime}, series = {ACM transactions on computation theory : TOCT / Association for Computing Machinery}, volume = {13}, journal = {ACM transactions on computation theory : TOCT / Association for Computing Machinery}, number = {3}, publisher = {Association for Computing Machinery}, address = {New York}, issn = {1942-3454}, doi = {10.1145/3460958}, pages = {1 -- 33}, year = {2021}, abstract = {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.}, language = {en} } @book{JennekRotherToschetal.2022, author = {Jennek, Julia and Rother, Stefanie and Tosch, Frank and Wendland, Mirko and Kludt, Steffen and Krauskopf, Karsten and Kitschke, Dorothea and Maar, Verena and Knigge, Michel and Gn{\"a}dig, Susanne and Seidel, Astrid and Siehr, Karl-Heinz and Wienecke, Maik and G{\"u}nther, Claudia-Susanne and Reitz-Koncebovski, Karen and KloĢˆpping, Peter M. and K{\"u}choll, Denise and Lazarides, Rebecca and Westphal, Andrea and Scherreiks, Lynn and Kuhr, Linda and Wilbert, J{\"u}rgen and Gronostaj, Anna and Vock, Miriam and Zaruba, Nicole and Ahlgrimm, Frederik and Link, J{\"o}rg-Werner and K{\"o}rner, Dorothea and Barseghyan, Anahit and Glowinski, Ingrid}, title = {Professionalisierung in Praxisphasen}, series = {Potsdamer Beitr{\"a}ge zur Lehrerbildung und Bildungsforschung}, journal = {Potsdamer Beitr{\"a}ge zur Lehrerbildung und Bildungsforschung}, number = {2}, editor = {Jennek, Julia}, publisher = {Universit{\"a}tsverlag Potsdam}, address = {Potsdam}, isbn = {978-3-86956-508-8}, issn = {2626-3556}, doi = {10.25932/publishup-50096}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-500964}, publisher = {Universit{\"a}t Potsdam}, pages = {321}, year = {2022}, abstract = {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{\"u}nf Pflichtpraktika. W{\"a}hrend die Ziele der Praktika klar beschrieben sind, sind die tats{\"a}chlichen Lernerfolge nicht immer klar - ebenso wenig, wie die Begleitung der Praktika aussehen muss, um die Studierenden bestm{\"o}glich zu unterst{\"u}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{\"a}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{\"u}r zahlreiche Ansatzpunkte. Schulpraktika sind nicht nur ein zentraler und von Studierenden hoch gesch{\"a}tzter Bestandteil des Studiums, sondern werden auch zunehmend f{\"u}r die Bildungsforschung interessant. Fragen nach der Kompetenzentwicklung, Selbsteinsch{\"a}tzungen und der Entwicklung der Reflexionsf{\"a}higkeit von Studierenden stehen dabei ebenso im Fokus wie die Einsch{\"a}tzung der universit{\"a}ren Begleitung und der Einbindung ins weitere Studium. Der vorliegende Band versammelt Studien von Wissenschaftlerinnen und Wissenschaftler der Universit{\"a}t Potsdam, die die f{\"u}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{\"a}sentierten Ergebnisse bilden eine gute Grundlage, um die Praktika in Potsdam und an anderen Standorten weiterzuentwickeln.}, language = {de} }