2022 [ nach oben ]

Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
[ BibTeX ] [ URL ] [ Download ]
 
@inproceedings{bother2022whats, abstract = {Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.}, author = {Böther, Maximilian and Kißig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias}, booktitle = {International Conference on Learning Representations (ICLR)}, keywords = {iclr karenseidel martintaraz maximilianboether ottokissig sarelcohen tobiasfriedrich year2022}, title = {What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization}, year = 2022 }

2021 [ nach oben ]

Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, Karen Counting Homomorphisms to Trees Modulo a PrimeACM Transactions on Computation Theory 2021
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@article{gobel2021counting, 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}, editor = {O'Donnell, Ryan}, journal = {ACM Transactions on Computation Theory}, keywords = {andreasgoebel gregorlagodzinski karenseidel toct year2021}, month = {sep}, number = 3, title = {Counting Homomorphisms to Trees Modulo a Prime}, volume = 13, year = 2021 }

Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Towards a Map for Incremental Learning in the Limit from Positive and Negative InformationComputability in Europe (CiE) 2021: 273–284
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@inproceedings{khazraei2021towards, 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. Prior research investigating the impact of additional requirements on iterative learners left many questions open, especially in learning from informant, where the input is binary labeled.}, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {ardalankhazraei cie karenseidel timokoetzing year2021}, pages = {273-284}, title = {Towards a Map for Incremental Learning in the Limit from Positive and Negative Information}, year = 2021 }

Kötzing, Timo; Seidel, Karen Learning Languages in the Limit from Positive Information with Finitely Many Memory ChangesComputability in Europe (CiE) 2021: 318–329
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@inproceedings{kotzing2021learning, abstract = {We investigate learning collections of languages from texts by an inductive inference machine with access to the current datum and a bounded memory in form of states. Such a bounded memory states (\(\mathbf{BMS}\)) learner is considered successful in case it eventually settles on a correct hypothesis while exploiting only finitely many different states.}, author = {Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {cie karenseidel timokoetzing year2021}, pages = {318-329}, title = {Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes}, year = 2021 }

2020 [ nach oben ]

Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Learning Half-Spaces and other Concept Classes in the Limit with Iterative LearnersCoRR 2020
[ BibTeX ] [ URL ] [ Download ]
 
@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, Karen Learning Languages in the Limit from Positive Information with Finitely Many Memory ChangesCoRR 2020
[ BibTeX ] [ URL ] [ Download ]
 
@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, Frank Random Subgroups of RationalsMathematical Foundations of Computer Science (MFCS) 2019: 25:1–25:14
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@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 ]

Aschenbach, Martin; Kötzing, Timo; Seidel, Karen Learning from Informants: Relations between Learning Success CriteriaCoRR 2018
[ BibTeX ] [ Download ]
 
@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 }

Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, Karen Counting Homomorphisms to Trees Modulo a PrimeMathematical Foundations of Computer Science (MFCS) 2018: 49:1–49:13
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@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 }

2017 [ nach oben ]

Seidel, Karen Zu mathematischen Argumentationen eines Experten aus einer semiotischen PerspektiveBeiträge zum Mathematikunterricht 2017 2017: 897–900
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@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 }

Kötzing, Timo; Schirneck, Martin; Seidel, Karen Normal Forms in Semantic Language IdentificationAlgorithmic Learning Theory (ALT) 2017: 493–516
[ BibTeX ] [ URL ] [ Download ]
 
@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 }

Hölzl, Rupert; Jain, Sanjay; Schlicht, Philipp; Seidel, Karen; Stephan, Frank Automatic Learning from Repetitive TextsAlgorithmic Learning Theory (ALT) 2017: 129–150
[ BibTeX ] [ URL ] [ Download ]
 
@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 }

2013 [ nach oben ]

Koepke, Peter; Räsch, Karen; Schlicht, Philipp A minimal Prikry-type forcing for singularizing a measurable cardinalThe Journal of Symbolic Logic 2013: 85–100
[ BibTeX ] [ DOI ] [ Download ]
 
@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 }