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.
D.Angluin, Inductive inference of formal languages from positive data, Information and Control45 (1980), 117–135. doi:10.1016/S0019-9958(80)90285-5.
2.
G.Baliga, J.Case, W.Merkle, F.Stephan and R.Wiehagen, When unlearning helps, Information and Computation206 (2008), 694–709. doi:10.1016/j.ic.2007.10.005.
3.
J.M.Bārzdiņš, Inductive inference of automata, functions and programs, in: American Mathematical Society Translations, 1977, pp. 107–122.
4.
J.Berger, M.Böther, V.Doskoč, J.Gadea Harder, N.Klodt, T.Kötzing, W.Lötzsch, J.Peters, L.Schiller, L.Seifert, A.Wells and S.Wietheger, Learning languages with decidable hypotheses, in: Computability in Europe (CiE), 2021, pp. 12813:25–12813:37.
5.
L.Blum and M.Blum, Toward a mathematical theory of inductive inference, Information and Control28 (1975), 125–155. doi:10.1016/S0019-9958(75)90261-2.
6.
M.Blum, A machine-independent theory of the complexity of recursive functions, Journal of the ACM14 (1967), 322–336. doi:10.1145/321386.321395.
7.
L.Carlucci, J.Case, S.Jain and F.Stephan, Results on memory-limited U-shaped learning, Information and Computation205 (2007), 1551–1573. doi:10.1016/j.ic.2007.04.001.
8.
J.Case and T.Kötzing, Strongly non-U-shaped language learning results by general techniques, Information and Computation251 (2016), 1–15. doi:10.1016/j.ic.2016.06.015.
9.
J.Case and C.Lynes, Machine inductive inference and language identification, in: International Colloquium on Automata, Languages and Programming (ICALP), 1982, pp. 107–115. doi:10.1007/BFb0012761.
10.
J.Case and S.E.Moelius, U-shaped, iterative, and iterative-with-counter learning, Machine Learning72(1–2) (2008), 63–88.
11.
J.Case and S.E.Moelius, Optimal language learning from positive data, Information and Computation209 (2011), 1293–1311. doi:10.1016/j.ic.2011.07.003.
12.
V.Doskoč and T.Kötzing, Cautious limit learning, in: Algorithmic Learning Theory (ALT), 2020, pp. 117:251–117:276.
13.
M.Fulk, A Study of Inductive Inference Machines, PhD thesis, 1985.
14.
M.A.Fulk, Prudence and other conditions on formal language learning, Information and Computation85 (1990), 1–11. doi:10.1016/0890-5401(90)90042-G.
15.
E.M.Gold, Language identification in the limit, Information and Control10 (1967), 447–474. doi:10.1016/S0019-9958(67)91165-5.
16.
S.Jain, D.Osherson, J.S.Royer and A.Sharma, Systems That Learn: An Introduction to Learning Theory, 2nd edn, MIT Press, Cambridge (MA), 1999.
17.
K.Jantke, Monotonic and non-monotonic inductive inference, New Generation Computing8 (1991), 349–360. doi:10.1007/BF03037092.
18.
E.B.Kinber and F.Stephan, Language learning from texts: Mindchanges, limited memory, and monotonicity, Information and Computation123 (1995), 224–241. doi:10.1006/inco.1995.1170.
19.
T.Kötzing, Abstraction and Complexity in Computational Learning in the Limit, PhD thesis, University of Delaware, 2009.
20.
T.Kötzing, A solution to Wiehagen’s thesis, Theory of Computing Systems60 (2017), 498–520. doi:10.1007/s00224-016-9678-0.
21.
T.Kötzing and R.Palenta, A map of update constraints in inductive inference, Theoretical Computer Science650 (2016), 4–24. doi:10.1016/j.tcs.2016.07.028.
22.
T.Kötzing and M.Schirneck, Towards an atlas of computational learning theory, in: Symposium on Theoretical Aspects of Computer Science (STACS), 2016, pp. 47:1–47:13.
23.
T.Kötzing, M.Schirneck and K.Seidel, Normal forms in semantic language identification, in: Algorithmic Learning Theory (ALT), 2017, pp. 76:493–76:516.
24.
S.Lange and T.Zeugmann, Language learning in dependence on the space of hypotheses, in: Conference on Computational Learning Theory (COLT), 1993, pp. 127–136.
25.
S.Lange and T.Zeugmann, Monotonic versus non-monotonic language learning, in: Nonmonotonic and Inductive Logic, 1993, pp. 254–269. doi:10.1007/BFb0030397.
26.
S.Lange and T.Zeugmann, Incremental learning from positive data, Journal of Computer and System Sciences53 (1996), 88–103. doi:10.1006/jcss.1996.0051.
27.
S.Lange and T.Zeugmann, Set-driven and rearrangement-independent learning of recursive languages, Mathematical Systems Theory29 (1996), 599–634. doi:10.1007/BF01301967.
28.
S.Lange, T.Zeugmann and S.Kapur, Monotonic and dual monotonic language learning, Theoretical Computer Science155 (1996), 365–410. doi:10.1016/0304-3975(95)00284-7.
29.
S.Lange, T.Zeugmann and S.Zilles, Learning indexed families of recursive languages from positive data: A survey, Theoretical Computer Science397 (2008), 194–232. doi:10.1016/j.tcs.2008.02.030.
30.
D.N.Osherson, M.Stob and S.Weinstein, Learning strategies, Information and Control53 (1982), 32–51. doi:10.1016/S0019-9958(82)91097-X.
31.
D.N.Osherson and S.Weinstein, Criteria of language learning, Information and Control52 (1982), 123–138. doi:10.1016/S0019-9958(82)80025-9.
32.
H.RogersJr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge (MA), 1987.
33.
G.Schäfer-Richter, Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien, PhD thesis, RWTH Aachen University, Germany, 1984.
34.
K.Wexler and P.W.Culicover, Formal Principles of Language Acquisition, MIT Press, Cambridge (MA), 1980.
35.
R.Wiehagen, Limes-Erkennung rekursiver Funktionen durch spezielle Strategien, Journal of Information Processing and Cybernetics12 (1976), 93–99. doi:10.1016/0306-4573(76)90031-5.
36.
R.Wiehagen, A thesis in inductive inference, in: Nonmonotonic and Inductive Logic, 1991, pp. 184–207. doi:10.1007/BFb0023324.
37.
T.Zeugmann and S.Lange, A guided tour across the boundaries of learning recursive languages, in: Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, 1995, pp. 961:190–961:258.
