Maps for learning indexable classes

Issue title: CiE 2022

Guest editors: Ulrich Berger, Johanna Franklin and Elvira Mayordomo

Article type: Research Article

Authors: Berger, Julian^{a; *} | Böther, Maximilian^b | Doskoč, Vanja^c | Gadea Harder, Jonathan^d | Klodt, Nicolas^e | Kötzing, Timo^f | Lötzsch, Winfried^g | Peters, Jannik^h | Schiller, Leonⁱ | Seifert, Lars^j | Wells, Armin^k | Wietheger, Simon^l

Affiliations: [a] Hasso Plattner Institute, University of Potsdam, Germany | [b] Hasso Plattner Institute, University of Potsdam, Germany | [c] Hasso Plattner Institute, University of Potsdam, Germany | [d] Hasso Plattner Institute, University of Potsdam, Germany | [e] Hasso Plattner Institute, University of Potsdam, Germany | [f] Hasso Plattner Institute, University of Potsdam, Germany | [g] Hasso Plattner Institute, University of Potsdam, Germany | [h] Hasso Plattner Institute, University of Potsdam, Germany | [i] Hasso Plattner Institute, University of Potsdam, Germany | [j] Hasso Plattner Institute, University of Potsdam, Germany | [k] Hasso Plattner Institute, University of Potsdam, Germany | [l] Hasso Plattner Institute, University of Potsdam, Germany

Correspondence: [*] Corresponding author. Julian.Berger@student.hpi.uni-potsdam.de.

Abstract: We study learning of indexed families from positive data where a learner can freely choose a hypothesis space (with uniformly decidable membership) comprising at least the languages to be learned. This abstracts a very universal learning task which can be found in many areas, for example learning of (subsets of) regular languages or learning of natural languages. We are interested in various restrictions on learning, such as consistency, conservativeness or set-drivenness, exemplifying various natural learning restrictions. The contribution of this work is twofold. First, we present a general result on how the hypothesis spaces may be constructed during learning, rather than beforehand. Using this result, we build on previous results from the literature and provide several maps (depictions of all pairwise relations) of various groups of learning criteria, including a map for monotonicity restrictions and similar criteria and a map for restrictions on data presentation. Furthermore, we consider, for various learning criteria, whether learners can be assumed consistent.

Keywords: Language learning in the limit, indexed family, hypothesis space, map, characteristic index

DOI: 10.3233/COM-220421

Journal: Computability, vol. 13, no. 3-4, pp. 237-261, 2024