2020 [ nach oben ]

• 
  Khazraei, Ardalan; Kötzing, Timo; Seidel, KarenLearning Half-Spaces and other Concept Classes in the Limit with Iterative Learners. CoRR 2020

  ArXiv preprint
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.
  @article{khazraeikoetzingseidel2020ItInfExhalfspaces, abstract = {In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.}, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, journal = {CoRR}, keywords = {ardalankhazraei arxiv karenseidel timokoetzing year2020}, note = {ArXiv preprint}, title = {Learning Half-Spaces and other Concept Classes in the Limit with Iterative Learners}, volume = {arXiv:2010.03227}, year = 2020 }
• 
  Kötzing, Timo; Seidel, KarenLearning Languages in the Limit from Positive Information with Finitely Many Memory Changes. CoRR 2020

  ArXiv preprint
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and its memory in form of states. The bounded memory states (\(BMS\)) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states. We give the complete map of all pairwise relations for an established collection of learning success restrictions. Most prominently, we show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. Some results carry over from iterative learning by a general lemma showing that, for a wealth of restrictions (the semantic restrictions), iterative and bounded memory states learning are equivalent. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.
  @article{kotzingseidel2020BMSstar, abstract = {We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and its memory in form of states. The bounded memory states (\(BMS\)) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states. We give the complete map of all pairwise relations for an established collection of learning success restrictions. Most prominently, we show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. Some results carry over from iterative learning by a general lemma showing that, for a wealth of restrictions (the semantic restrictions), iterative and bounded memory states learning are equivalent. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.}, author = {Kötzing, Timo and Seidel, Karen}, journal = {CoRR}, keywords = {arxiv karenseidel timokoetzing year2020}, note = {ArXiv preprint}, title = {Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes}, volume = {arXiv:2010.04782}, year = 2020 }

2019 [ nach oben ]

• 
  Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, FrankRandom Subgroups of Rationals. Mathematical Foundations of Computer Science (MFCS) 2019: 25:1-25:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup \((G,+)\) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of \((G,+)\); second, what learnability properties can one extract from \(G\) and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of \((G,+)\) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for \(G\) with respect to any generating sequence for \(G\) is not even semi-decidable, one can build a generating sequence \(\beta\) such that the word problem for \(G\) with respect to \(\beta\) is co-recursively enumerable (assuming that the set of generators of \(G\) is limit-recursive). In regard to the second question, it is proven that there is a generating sequence \(\beta\) for \(G\) such that every non-trivial finitely generated subgroup of \(G\) is recursively enumerable and the class of all such subgroups of \(G\) is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of \(G\) is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of \(G\) cannot be syntactically identified in the limit with respect to any generating sequence for \(G\). The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.
  @inproceedings{gao_et_al:LIPIcs:2019:10969, abstract = {This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup \((G,+)\) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of \((G,+)\); second, what learnability properties can one extract from \(G\) and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of \((G,+)\) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for \(G\) with respect to any generating sequence for \(G\) is not even semi-decidable, one can build a generating sequence \(\beta\) such that the word problem for \(G\) with respect to \(\beta\) is co-recursively enumerable (assuming that the set of generators of \(G\) is limit-recursive). In regard to the second question, it is proven that there is a generating sequence \(\beta\) for \(G\) such that every non-trivial finitely generated subgroup of \(G\) is recursively enumerable and the class of all such subgroups of \(G\) is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of \(G\) is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of \(G\) cannot be syntactically identified in the limit with respect to any generating sequence for \(G\). The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.}, address = {Dagstuhl, Germany}, annote = {Keywords: Martin-L{ö}f randomness, subgroups of rationals, finitely generated subgroups of rationals, learning in the limit, behaviourally correct learning}, author = {Gao, Ziyuan and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Melnikov, Alexander and Seidel, Karen and Stephan, Frank}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, keywords = {karenseidel mfcs year2019}, pages = {25:1-25:14}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Random Subgroups of Rationals}, volume = 138, year = 2019 }

2018 [ nach oben ]

• 
  Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, KarenCounting Homomorphisms to Trees Modulo a Prime. Mathematical Foundations of Computer Science (MFCS) 2018: 49:1-49:13
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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\textsc{HomsTo}H$\), 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 \($\#_p\textsc{HomsTo}H$\) is either polynomial time computable or \($\#_p\mathsf{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 \($\#_p\textsc{HomsTo}H$\) 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 one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~\($p$\).
  @inproceedings{gobel2018counting, 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\textsc{HomsTo}H$, 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 $\#_p\textsc{HomsTo}H$ is either polynomial time computable or $\#_p\mathsf{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 $\#_p\textsc{HomsTo}H$ 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 one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~$p$.}, author = {Göbel, Andreas and Lagodzinski, J. A. Gregor and Seidel, Karen}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, keywords = {andreasgoebel gregorlagodzinski karenseidel mfcs year2018}, pages = {49:1-49:13}, publisher = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Counting Homomorphisms to Trees Modulo a Prime}, volume = 117, year = 2018 }
• 
  Aschenbach, Martin; Kötzing, Timo; Seidel, KarenLearning from Informants: Relations between Learning Success Criteria. CoRR 2018

  ArXiv preprint
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Learning from positive and negative information, so-called informants, being one of the models for human and machine learning introduced by Gold [1967], is investigated. Particularly, naturally arising questions about this learning setting, originating in results on learning from solely positive information, are answered. By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data (such a learning behavior is called conservative). The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria. Moreover, we obtain an anomalous hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned. In contrast to the vacillatory hierarchy for learning from solely positive information, we observe a duality depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.
  @article{2018kötzingseidel, abstract = {Learning from positive and negative information, so-called informants, being one of the models for human and machine learning introduced by Gold [1967], is investigated. Particularly, naturally arising questions about this learning setting, originating in results on learning from solely positive information, are answered. By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data (such a learning behavior is called conservative). The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria. Moreover, we obtain an anomalous hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned. In contrast to the vacillatory hierarchy for learning from solely positive information, we observe a duality depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.}, author = {Aschenbach, Martin and Kötzing, Timo and Seidel, Karen}, journal = {CoRR}, keywords = {arxiv karenseidel timokoetzing year2018}, note = {ArXiv preprint}, title = {Learning from Informants: Relations between Learning Success Criteria}, volume = {arXiv:1801.10502}, year = 2018 }

2017 [ nach oben ]

• 
  Seidel, KarenZu mathematischen Argumentationen eines Experten aus einer semiotischen Perspektive. Beiträge zum Mathematikunterricht 2017 2017: 897-900
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In Argumentationen unter in der Forschung tätigen Mathematikern kombiniert die erklärende Person Gesten, Sprache und Zeichen und verleiht damit unter anderem den concept images der verwendeten mathematischen Begriffe Ausdruck. Im Folgenden wird der Frage nachgegangen, inwiefern eine multimodale Analyse von erklärenden Phasen in Argumentationen von Experten mit dem Fokus auf Begriffsbildungsprozessen Aufschluss geben kann über operationale und strukturelle Vorstellungen von Begriffen (Sfard, 1991).
  @conference{seidel2017argumentation, abstract = {In Argumentationen unter in der Forschung tätigen Mathematikern kombiniert die erklärende Person Gesten, Sprache und Zeichen und verleiht damit unter anderem den concept images der verwendeten mathematischen Begriffe Ausdruck. Im Folgenden wird der Frage nachgegangen, inwiefern eine multimodale Analyse von erklärenden Phasen in Argumentationen von Experten mit dem Fokus auf Begriffsbildungsprozessen Aufschluss geben kann über operationale und strukturelle Vorstellungen von Begriffen (Sfard, 1991).}, author = {Seidel, Karen}, booktitle = {Beiträge zum Mathematikunterricht 2017}, editor = {Kortenkamp, Ulrich and Kuzle, Ana}, journal = {Beiträge zum Mathematikunterricht 2017}, keywords = {karenseidel year2017}, pages = {897-900}, publisher = {WTM-Verlag}, title = {Zu mathematischen Argumentationen eines Experten aus einer semiotischen Perspektive}, volume = 2017, year = 2017 }
• 
  Hölzl, Rupert; Jain, Sanjay; Schlicht, Philipp; Seidel, Karen; Stephan, FrankAutomatic Learning from Repetitive Texts. Algorithmic Learning Theory (ALT) 2017: 129-150
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We study the connections between the learnability of automatic families of languages and the types of text used to present them to a learner. More precisely, we study how restrictions on the number of times that a correct datum appears in a text influence what classes of languages are automatically learnable. We show that an automatic family of languages is automatically learnable from fat text iff it is automatically learnable from thick text iff it is verifiable from balanced text iff it satisfies Angluin's tell-tale condition. Furthermore, many automatic families are automatically learnable from exponential text. We also study the relationship between automatic learnability and verifiability and show that all automatic families are automatically partially verifiable from exponential text and automatically learnable from thick text.
  @inproceedings{DBLP:conf/alt/HolzlJSS017, abstract = {We study the connections between the learnability of automatic families of languages and the types of text used to present them to a learner. More precisely, we study how restrictions on the number of times that a correct datum appears in a text influence what classes of languages are automatically learnable. We show that an automatic family of languages is automatically learnable from fat text iff it is automatically learnable from thick text iff it is verifiable from balanced text iff it satisfies Angluin's tell-tale condition. Furthermore, many automatic families are automatically learnable from exponential text. We also study the relationship between automatic learnability and verifiability and show that all automatic families are automatically partially verifiable from exponential text and automatically learnable from thick text.}, author = {H{{ö}}lzl, Rupert and Jain, Sanjay and Schlicht, Philipp and Seidel, Karen and Stephan, Frank}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {alt frankstephan karenseidel philippschlicht ruperthoelzl sanjayjain year2017}, pages = {129-150}, title = {Automatic Learning from Repetitive Texts}, year = 2017 }
• 
  Kötzing, Timo; Schirneck, Martin; Seidel, KarenNormal Forms in Semantic Language Identification. Algorithmic Learning Theory (ALT) 2017: 493-516
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We consider language learning in the limit from text where all learning restrictions are semantic, that is, where any conjecture may be replaced by a semantically equivalent conjecture. For different such learning criteria, starting with the well-known TxtGBc-learning, we consider three different normal forms: strongly locking learning, consistent learning and (partially) set-driven learning. These normal forms support and simplify proofs and give insight into what behaviors are necessary for successful learning (for example when consistency in conservative learning implies cautiousness and strong decisiveness). We show that strongly locking learning can be assumed for partially set-driven learners, even when learning restrictions apply. We give a very general proof relying only on a natural property of the learning restriction, namely, allowing for simulation on equivalent text. Furthermore, when no restrictions apply, also the converse is true: every strongly locking learner can be made partially set-driven. For several semantic learning criteria we show that learning can be done consistently. Finally, we deduce for which learning restrictions partial set-drivenness and set-drivenness coincide, including a general statement about classes of infinite languages. The latter again relies on a simulation argument.
  @inproceedings{DBLP:conf/alt/KotzingSS17, abstract = {We consider language learning in the limit from text where all learning restrictions are semantic, that is, where any conjecture may be replaced by a semantically equivalent conjecture. For different such learning criteria, starting with the well-known TxtGBc-learning, we consider three different normal forms: strongly locking learning, consistent learning and (partially) set-driven learning. These normal forms support and simplify proofs and give insight into what behaviors are necessary for successful learning (for example when consistency in conservative learning implies cautiousness and strong decisiveness). We show that strongly locking learning can be assumed for partially set-driven learners, even when learning restrictions apply. We give a very general proof relying only on a natural property of the learning restriction, namely, allowing for simulation on equivalent text. Furthermore, when no restrictions apply, also the converse is true: every strongly locking learner can be made partially set-driven. For several semantic learning criteria we show that learning can be done consistently. Finally, we deduce for which learning restrictions partial set-drivenness and set-drivenness coincide, including a general statement about classes of infinite languages. The latter again relies on a simulation argument.}, author = {Kötzing, Timo and Schirneck, Martin and Seidel, Karen}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {alt karenseidel martinschirneck timokoetzing year2017}, pages = {493-516}, title = {Normal Forms in Semantic Language Identification}, year = 2017 }

2013 [ nach oben ]

• 
  Koepke, Peter; Räsch, Karen; Schlicht, PhilippA minimal Prikry-type forcing for singularizing a measurable cardinal. The Journal of Symbolic Logic 2013: 85-100
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Recently, Gitik, Kanovei and the first author proved that for a classical Prikry forcing extension the family of the intermediate models can be parametrized by \(P(\omega)/finite\). By modifying the standard Prikry tree forcing we define a Prikry-type forcing which also singularizes a measurable cardinal but which is minimal, i.e. there are \emph{no} intermediate models properly between the ground model and the generic extension. The proof relies on combining the rigidity of the tree structure with indiscernibility arguments resulting from the normality of the associated measures.
  @article{DBLP:journals/jsyml/KoepkeRS13, abstract = {Recently, Gitik, Kanovei and the first author proved that for a classical Prikry forcing extension the family of the intermediate models can be parametrized by \(P(\omega)/finite\). By modifying the standard Prikry tree forcing we define a Prikry-type forcing which also singularizes a measurable cardinal but which is minimal, i.e. there are \emph{no} intermediate models properly between the ground model and the generic extension. The proof relies on combining the rigidity of the tree structure with indiscernibility arguments resulting from the normality of the associated measures.}, author = {Koepke, Peter and Räsch, Karen and Schlicht, Philipp}, journal = {The Journal of Symbolic Logic}, keywords = {jsl karenseidel year2013}, number = {01}, pages = {85-100}, publisher = {Cambridge Univ Press}, title = {A minimal Prikry-type forcing for singularizing a measurable cardinal}, volume = 78, year = 2013 }