×

Automatic learning from positive data and negative counterexamples. (English) Zbl 1377.68096

The contribution discusses learnability in the limit of language classes from positive data and limited counterexamples. In their learning scenario the learner is presented with a stream of positive examples from the language that eventually presents every member of the language. At each step, the learner can return a hypothesis, which triggers a counterexample reply provided that the hypothesis contains an element that does not belong to the language to be learned. In this case the counterexample reply returns a member of the hypothesis language that is not a member of the language to be learned according to certain criteria (any, the least according to some total order, or some particularly small counterexample according to some size). In earlier work [the first author et al., J. Comput. Syst. Sci. 78, No. 6, 1910–1927 (2012; Zbl 1250.68137)] an automatic variant of this learning scenario without the counterexamples was introduced. In the automatic learnability the learner is restricted to be automatic, which means that its computed function is a regular relation (i.e., recognized by a finite automaton). Additionally, the authors also place memory restrictions on the learner.
In the earlier work it was demonstrated that automatic learners are rather weak based on positive data alone. In the present work, this investigation is extended to the scenario that includes counterexamples. It is demonstrated that typically all automatic classes can be learned in this manner. The memory of the learner can even be restricted to the length of the longest datum seen so far without effect on the learnability. Only in the scenario in which the counterexample returned is bounded in size by the length of the longest datum seen so far a restricted learnability is observed. The authors present a characterization of the languages that can be successfully learned despite these severe restrictions. In conjunction with memory restrictions on the learner the situation becomes more involved and the authors also present results for these setups, which are still reasonably powerful.
The paper is well written and should be generally understandable by anyone with a graduate level understanding of basic automata theory. The text is generally focussed on definitions and results, but motivation is provided in the text. Since most proofs are rather constructive in nature, additional examples are not much missed.

MSC:

68Q32 Computational learning theory
68Q19 Descriptive complexity and finite models
68Q70 Algebraic theory of languages and automata

Citations:

Zbl 1250.68137
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, Dana, Inductive inference of formal languages from positive data, Inf. Control, 45, 117-135 (1980) · Zbl 0459.68051
[2] Angluin, Dana, Finding patterns common to a set of strings, J. Comput. Syst. Sci., 21, 46-62 (1980) · Zbl 0454.68108
[3] Angluin, Dana, Queries and concept learning, Mach. Learn., 2, 4, 319-342 (1988) · Zbl 1470.68050
[4] Arikawa, Setsuo; Miyano, Satoru; Shinohara, Ayumi; Kuhara, Satoru; Mukouchi, Yasuhito; Shinohara, Takeshi, A machine discovery from amino acid sequences by decision trees over regular patterns, New Gener. Comput., 11, 3, 361-375 (1993) · Zbl 0780.68099
[5] Arikawa, Setsuo; Miyano, Satoru; Shinohara, Ayumi; Shinohara, Takeshi; Yamamoto, Akihiro, Algorithmic learning theory with elementary formal systems, IEICE Trans. Inf. Syst., 75-D, 405-414 (1992)
[6] Arikawa, Setsuo; Shinohara, Takeshi; Miyano, Satoru; Shinohara, Ayumi, More about learning elementary formal systems, (Nonmonotonic and Inductive Logic, Second International Workshop. Nonmonotonic and Inductive Logic, Second International Workshop, Lecture Notes in Artificial Intelligence, vol. 659 (1991), Springer Verlag), 107-117 · Zbl 0819.68093
[7] Arikawa, Setsuo; Shinohara, Takeshi; Yamamoto, Akihiro, Learning elementary formal systems, Theor. Comput. Sci., 95, 97-113 (1992) · Zbl 0746.68069
[8] Bārzdiņš, Janis, Inductive inference of automata, functions and programs, (Proceedings of the 20th International Congress of Mathematicians. Proceedings of the 20th International Congress of Mathematicians, Vancouver (1974)). (Proceedings of the 20th International Congress of Mathematicians. Proceedings of the 20th International Congress of Mathematicians, Vancouver (1974)), Transl. Am. Math. Soc. (2), 109, 107-112 (1977), In Russian. English translation in
[9] Björklund, Johanna; Fernau, Henning; Kasprzik, Anna, Polynomial inference of universal automata from membership and equivalence queries, Inf. Comput., 246, 3-19 (2016) · Zbl 1333.68153
[10] Blum, Lenore; Blum, Manuel, Toward a mathematical theory of inductive inference, Inf. Control, 28, 2, 125-155 (1975) · Zbl 0375.02028
[11] Blumensath, Achim; Grädel, Erich, Automatic structures, (15th Annual IEEE Symposium on Logic in Computer Science. 15th Annual IEEE Symposium on Logic in Computer Science, LICS (2000), IEEE Computer Society), 51-62
[12] Brattka, Vasco; de Brecht, Matthew; Pauly, Arno, Closed choice and a Uniform Low Basis Theorem, Ann. Pure Appl. Log., 163, 8, 986-1008 (2012) · Zbl 1251.03082
[13] Brattka, Vasco; Gherardi, Guido; Hölzl, Rupert, Probabilistic computability and choice, Inf. Comput., 242, 249-286 (2015) · Zbl 1320.03071
[14] Case, John; Jain, Sanjay; Seah, Samuel; Stephan, Frank, Automatic functions, linear time and learning, Log. Methods Comput. Sci., 9, 3 (2013) · Zbl 1274.68143
[15] Case, John; Kötzing, Timo, Difficulties in forcing fairness of polynomial time inductive inference, (Algorithmic Learning Theory, Twentieth International Conference. Algorithmic Learning Theory, Twentieth International Conference, ALT 2009. Algorithmic Learning Theory, Twentieth International Conference. Algorithmic Learning Theory, Twentieth International Conference, ALT 2009, Lecture Notes in Computer Science, vol. 5809 (2009), Springer Verlag), 263-277 · Zbl 1262.68063
[16] Case, John; Lynes, Christopher, Machine inductive inference and language identification, (Nielsen, M.; Schmidt, E. M., Proceedings of the 9th International Colloquium on Automata, Languages and Programming. Proceedings of the 9th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 140 (1982), Springer Verlag), 107-115 · Zbl 0582.68047
[17] Case, John; Moelius, Samuel E., Independence results for \(n\)-ary recursion theorems, (Fundamentals of Computation Theory, Seventeenth International Symposium, FCT 2009. Proceedings. Fundamentals of Computation Theory, Seventeenth International Symposium, FCT 2009. Proceedings, Lecture Notes in Computer Science, vol. 5699 (2009), Springer Verlag), 38-49 · Zbl 1252.68075
[18] Clark, Alexander, (Towards General Algorithms for Grammatical Inference. Algorithmic Learning Theory, Twentyfirst International Conference. Towards General Algorithms for Grammatical Inference. Algorithmic Learning Theory, Twentyfirst International Conference, ALT 2010. Towards General Algorithms for Grammatical Inference. Algorithmic Learning Theory, Twentyfirst International Conference. Towards General Algorithms for Grammatical Inference. Algorithmic Learning Theory, Twentyfirst International Conference, ALT 2010, Lecture Notes in Computer Science, vol. 6331 (2010), Springer Verlag), 11-30 · Zbl 1306.68051
[19] Clark, Alexander; Yohshinaka, Ryo, Distributional learning of parallel multiple context-free grammars, Mach. Learn., 96, 1, 5-31 (2013) · Zbl 1317.68085
[20] Fernau, Henning, Even linear simple matrix languages: formal language properties and grammatical inference, Theor. Comput. Sci., 289, 1, 425-456 (2002) · Zbl 1062.68065
[21] Freivalds, Rusins; Kinber, Efim; Smith, Carl H., On the impact of forgetting on learning machines, J. ACM, 42, 6, 1146-1168 (1995) · Zbl 0891.68088
[22] Gasarch, William I.; Pleszkoch, Mark G.; Solovay, Robert, Learning via queries in \([+, <]\), J. Symb. Log., 57, 1, 53-81 (1992) · Zbl 0774.03023
[23] Gold, E. Mark, Language identification in the limit, Inf. Control, 10, 5, 447-474 (1967) · Zbl 0259.68032
[24] Gulwani, Sumit; Jha, Susmit; Tiwari, Ashish; Venkatesan, Ramarathnam, Synthesis of loop-free programs, (Proceedings of the Thirtysecond ACM SIGPLAN Conference on Programming Language Design and Implementation. Proceedings of the Thirtysecond ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDP (2011)), 62-73
[25] Hayashi, Susumu; Akama, Yohji, Limit-computable mathematics and its applications, (Computer Science Logic, Sixteenth International Workshop, CSL 2002, Eleventh Annual Conference of the EACSL, 2002. Computer Science Logic, Sixteenth International Workshop, CSL 2002, Eleventh Annual Conference of the EACSL, 2002, Lecture Notes in Computer Science, vol. 2471 (2002), Springer Verlag), 1 · Zbl 1020.03509
[26] Hayashi, Susumu; Nakata, Masahiro, Towards limit computable mathematics, (Types for Proofs and Programs, International Workshop, TYPES 2000, Selected Papers. Types for Proofs and Programs, International Workshop, TYPES 2000, Selected Papers, Lecture Notes in Computer Science, vol. 2277 (2000), Springer Verlag), 125-144 · Zbl 1054.03037
[27] Hirsh-Pasek, Kathy; Treiman, Rebecca; Schneiderman, Maita, Brown and Hanlon revisited: mothers’ sensitivity to ungrammatical forms, J. Child Lang., 11, 81-88 (1984)
[28] Ibarra, Oscar H.; Jiang, Tao, Learning regular languages from counterexamples, J. Comput. Syst. Sci., 43, 2, 299-316 (1991) · Zbl 0769.68108
[29] Jain, Sanjay; Kinber, Efim, Iterative learning from positive data and negative counterexamples, Inf. Comput., 205, 12, 1777-1805 (2007) · Zbl 1132.68035
[30] Jain, Sanjay; Kinber, Efim, Learning languages from positive data and negative counterexamples, J. Comput. Syst. Sci., 74, 4, 431-456 (2008), Special Issue: Carl Smith memorial issue · Zbl 1146.68382
[31] Jain, Sanjay; Kinber, Efim, Automatic learning from positive data and negative counterexamples, (Bshouty, Nader; Stoltz, Gilles; Vayatis, Nicolas; Zeugmann, Thomas, Algorithmic Learning Theory, 23nd International Conference. Algorithmic Learning Theory, 23nd International Conference, ALT 2012. Algorithmic Learning Theory, 23nd International Conference. Algorithmic Learning Theory, 23nd International Conference, ALT 2012, Lecture Notes in Artificial Intelligence, vol. 7568 (2012), Springer Verlag), 66-80 · Zbl 1367.68120
[32] Jain, Sanjay; Luo, Qinglong; Stephan, Frank, Learnability of automatic classes, J. Comput. Syst. Sci., 78, 1910-1927 (2012) · Zbl 1250.68137
[33] Jain, Sanjay; Ong, Yuh Shin; Pu, Shi; Stephan, Frank, On automatic families, (Arai, T.; Feng, Q.; Kim, B.; Wu, G.; Yang, Y., Proceedings of the 11th Asian Logic Conference, in Honor of Professor Chong Chitat’s 60th Birthday, 2009 (2011), World Scientific), 94-113 · Zbl 1301.03038
[34] Jantke, Klaus P., Monotonic and non-monotonic inductive inference, New Gener. Comput., 8, 349-360 (1991) · Zbl 0712.68081
[35] Jha, Susmit; Seshia, Sanjit A., A theory of formal synthesis via inductive learning, Technical report on · Zbl 1380.68124
[36] Kinber, Efim; Stephan, Frank, Language learning from texts: mind changes, limited memory and monotonicity, Inf. Comput., 123, 224-241 (1995) · Zbl 0839.68083
[37] Khoussainov, Bakhadyr; Nerode, Anil, Automatic presentations of structures, (Logical and Computational Complexity. Logical and Computational Complexity, International Workshop LCC 1994. Logical and Computational Complexity. Logical and Computational Complexity, International Workshop LCC 1994, Lecture Notes in Computer Science, vol. 960 (1995), Springer Verlag), 367-392 · Zbl 0837.03037
[38] Lange, Steffen; Nessel, Jochen, Learning erasing pattern languages with queries, Theor. Comput. Sci., 348, 1, 41-57 (2005) · Zbl 1081.68049
[39] Lange, Steffen; Nessel, Jochen; Wiehagen, Rolf, Learning recursive languages from good examples, Ann. Math. Artif. Intell., 23, 27-52 (1998) · Zbl 0913.68124
[40] Lange, Steffen; Zeugmann, Thomas, Language learning in dependence on the space of hypotheses, (Proceedings of the Sixth Annual Conference on Computational Learning Theory (1993), ACM Press), 127-136
[41] Lange, Steffen; Zilles, Sandra, Relations between gold-style learning and query learning, Inf. Comput., 203, 2, 211-237 (2005) · Zbl 1085.68072
[42] Moelius, Samuel E., Characteristics of minimal effective programming systems, (How the World Computes — Turing Centenary Conference and Eighth Conference on Computability in Europe. How the World Computes — Turing Centenary Conference and Eighth Conference on Computability in Europe, CiE 2012. How the World Computes — Turing Centenary Conference and Eighth Conference on Computability in Europe. How the World Computes — Turing Centenary Conference and Eighth Conference on Computability in Europe, CiE 2012, Lecture Notes in Computer Science, vol. 7318 (2012), Springer Verlag), 507-512 · Zbl 1357.68042
[43] Pitt, Lenny, Inductive inference, DFAs, and computational complexity. Analogical and inductive inference, (Proceedings of the Second International Workshop. Proceedings of the Second International Workshop, AII 1989. Proceedings of the Second International Workshop. Proceedings of the Second International Workshop, AII 1989, Lecture Notes in Artificial Intelligence, vol. 397 (1989), Springer Verlag), 18-44
[44] Wiehagen, Rolf, Limes-Erkennung rekursiver Funktionen durch spezielle Strategien, J. Inf. Process. Cybern. (EIK), 12, 1-2, 93-99 (1976) · Zbl 0346.02019
[45] Shinohara, Takeshi, Rich classes inferable from positive data: length-bounded elementary formal systems, Inf. Comput., 108, 175-186 (1994) · Zbl 0804.68130
[46] Wiehagen, Rolf, A thesis in inductive inference, (Dix, J.; Jantke, K.; Schmitt, P., Nonmonotonic and Inductive Logic, 1st International Workshop. Nonmonotonic and Inductive Logic, 1st International Workshop, Lecture Notes in Artificial Intelligence, vol. 543 (1990), Springer Verlag), 184-207 · Zbl 0794.03058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.