2020 [ to top ]

• 
  Doskoč, Vanja; Kötzing, Timo Cautious Limit Learning. Algorithmic Learning Theory (ALT) 2020
  [ Abstract ] [ BibTeX ] [ Download ]
   
  We investigate language learning in the limit from text with various \(\textit{cautious}\) learning restrictions. Learning is \(\textit{cautious}\) if no hypothesis is a proper subset of a previous guess. While dealing with a seemingly natural learning behaviour, cautious learning does severely restrict explanatory (syntactic) learning power. To further understand why exactly this loss of learning power arises, Kötzing and Palenta (2016) introduced weakened versions of cautious learning and gave first partial results on their relation. In this paper, we aim to understand the restriction of cautious learning more fully. To this end we compare the known variants in a number of different settings, namely full-information and (partially) set-driven learning, paired either with the syntactic convergence restriction (explanatory learning) or the semantic convergence restriction (behaviourally correct learning). To do so, we make use of normal forms presented in Kötzing et al. (2017), most notably strongly locking and consistent learning. While strongly locking learners have been exploited when dealing with a variety of syntactic learning restrictions, we show how they can be beneficial in the semantic case as well. Furthermore, we expand the normal forms to a broader range of learning restrictions, including an answer to the open question of whether cautious learners can be assumed to be consistent, as stated in Kötzing et al. (2017).
  @inproceedings{doskoc2020cautious, abstract = {We investigate language learning in the limit from text with various \(\textit{cautious}\) learning restrictions. Learning is \(\textit{cautious}\) if no hypothesis is a proper subset of a previous guess. While dealing with a seemingly natural learning behaviour, cautious learning does severely restrict explanatory (syntactic) learning power. To further understand why exactly this loss of learning power arises, Kötzing and Palenta (2016) introduced weakened versions of cautious learning and gave first partial results on their relation. In this paper, we aim to understand the restriction of cautious learning more fully. To this end we compare the known variants in a number of different settings, namely full-information and (partially) set-driven learning, paired either with the syntactic convergence restriction (explanatory learning) or the semantic convergence restriction (behaviourally correct learning). To do so, we make use of normal forms presented in Kötzing et al. (2017), most notably strongly locking and consistent learning. While strongly locking learners have been exploited when dealing with a variety of syntactic learning restrictions, we show how they can be beneficial in the semantic case as well. Furthermore, we expand the normal forms to a broader range of learning restrictions, including an answer to the open question of whether cautious learners can be assumed to be consistent, as stated in Kötzing et al. (2017).}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {alt timokoetzing vanjadoskoc year2020}, title = {Cautious Limit Learning}, year = 2020 }
• 
  Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020
  [ BibTeX ]
   
  @inproceedings{doskoc2020nonmonotone, author = {Doskoč, Vanja and Friedrich, Tobias and Göbel, Andreas and Neumann, Aneta and Neumann, Frank and Quinzan, Francesco}, booktitle = {European Conference on Artificial Intelligence (ECAI)}, keywords = {andreasgoebel anetaneumann ecai francescoquinzan frankneumann tobiasfriedrich vanjadoskoc year2020}, title = {Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings}, year = 2020 }

2018 [ to top ]

• 
  Doskoč, Vanja Confident Iterative Learning in Computational Learning Theory. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2018: 30-42
  [ Abstract ] [ BibTeX ] [ Download ]
   
  In inductive inference various types of learning have emerged. The main aim of this paper is to investigate a new type of learning, the confident iterative learning. Given a class to be learnt, the idea here is to merge the following two concepts. For confidence, we require the learner to converge on any set, however, it only needs to be correct on the sets in the class. To be iterative, we restrict the learner’s memory on previ- ous inputs and calculations to its last hypothesis. Investigating the new learner, we will provide negative and positive examples, as well as some properties the confident iterative learner possesses. This will peak at a classification theorem for certain types of classes. Next, we will introduce and compare different types of confidence, focus- ing on the learner’s behaviour on sets outside of the class. Lastly, we will focus on the possible hypotheses. Introducing learning with respect to hypothesis spaces, we will provide examples witnessing that exact, class preserving and class comprising learning are different.
  @conference{doskoc2018confident, abstract = {In inductive inference various types of learning have emerged. The main aim of this paper is to investigate a new type of learning, the confident iterative learning. Given a class to be learnt, the idea here is to merge the following two concepts. For confidence, we require the learner to converge on any set, however, it only needs to be correct on the sets in the class. To be iterative, we restrict the learner’s memory on previ- ous inputs and calculations to its last hypothesis. Investigating the new learner, we will provide negative and positive examples, as well as some properties the confident iterative learner possesses. This will peak at a classification theorem for certain types of classes. Next, we will introduce and compare different types of confidence, focus- ing on the learner’s behaviour on sets outside of the class. Lastly, we will focus on the possible hypotheses. Introducing learning with respect to hypothesis spaces, we will provide examples witnessing that exact, class preserving and class comprising learning are different.}, author = {Doskoč, Vanja}, booktitle = {Current Trends in Theory and Practice of Computer Science (SOFSEM)}, keywords = {sofsem vanjadoskoc year2018}, pages = {30-42}, title = {Confident Iterative Learning in Computational Learning Theory}, year = 2018 }