On learning for families of algebraic structures
Abstract
We survey the recent results on algorithmic learning for families of countable algebraic structures. Within this framework, at each step a learner obtains a finite amount of data about a given countable structure S (which is supposed to be learned), and then the learner outputs a conjecture describing the isomorphism type of S. If the sequence of conjectures converges to the correct answer, then the learning procedure is successful. The paper discusses the results connecting learnability with syntactic properties of structures S. We also give some results on the new approach to learnability which uses equivalence relations on the Cantor space.
Keywords
algorithmic learning theory,
inductive inference,
computable structure,
infinitary formulas,
Borel equivalence relation
Supporting agencies: The work is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.
About the Author
N. A. Bazhenov
Sobolev Institute of Mathematics
Russian Federation
Russian Federation
Nikolay Alekseevich Bazhenov
4 Acad. Koptyug Avе., Novosibirsk 630090
References
1. H. Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30 (1), 49–57 (1965).
2. E.M. Gold, Language identification in the limit, Inf. Control 10 (5), 447–474 (1967). DOI: https://doi.org/10.1016/S0019-9958(67)91165-5
3. S. Jain, D. Osherson, J.S. Royer, A. Sharma, Systems that learn: An introduction to learning theory, MIT Press, Cambridge, Massachusetts, 1999.
4. S. Lange, T. Zeugmann, S. Zilles, Learning indexed families of recursive languages from positive data: A survey, Theor. Comput. Sci. 397 (1–3), 194–232 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.030
5. T. Zeugmann, S. Zilles, Learning recursive functions: A survey, Theor. Comput. Sci. 397 (1–3), 4–56 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.021
6. F. Stephan, Y. Ventsov, Learning algebraic structures from text, Theor. Comput. Sci. 268 (2), 221–273 (2001). DOI: https://doi.org/10.1016/S0304-3975(00)00272-3
7. W. Merkle, F. Stephan, Trees and learning, J. Comput. Syst. Sci. 68 (1), 134–156 (2004). DOI: https://doi.org/10.1016/j.jcss.2003.08.001
8. V. S. Harizanov, F. Stephan, On the learnability of vector spaces, J. Comput. Syst. Sci. 73 (1), 109–122 (2007). DOI: https://doi.org/10.1016/j.jcss.2006.09.001
9. Z. Gao, F. Stephan, G. Wu, A. Yamamoto, Learning families of closed sets in matroids, in: M. J. Dinneen, B. Khoussainov, A. Nies (eds.), Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012 (Lect. Notes Comput. Sci. 7160), Springer, Berlin, 120–139 (2012). DOI: https://doi.org/10.1007/978-3-642-27654-5_10
10. E. Fokina, T. K¨otzing, L. San Mauro, Limit learning equivalence structures, Proc. Mach. Learn. Res. (PMLR) 98, 383–403 (2019).
11. N. Bazhenov, E. Fokina, L. San Mauro, Learning families of algebraic structures from informant, Inf. Comput. 275, article id 104590 (2020). DOI: https://doi.org/10.1016/j.ic.2020.104590
12. N. Bazhenov, L. San Mauro, On the Turing complexity of learning finite families of algebraic structures, J. Log. Comput. 31 (7), 1891–1900 (2021). DOI: https://doi.org/10.1093/logcom/exab044
13. N. Bazhenov, V. Cipriani, L. San Mauro, Learning algebraic structures with the help of Borel equivalence relations, Theor. Comput. Sci. 951, article id 113762 (2023). DOI: https://doi.org/10.1016/j.tcs.2023.113762
14. N. Bazhenov, V. Cipriani, L. San Mauro, Calculating the mind change complexity of learning algebraic structures, in: U. Berger, J.N.Y. Franklin, F. Manea, A. Pauly (eds.), Revolutions and Revelations in Computability, 18th Conference on Computability in Europe, CiE 2022 (Lect. Notes Comput. Sci. 13359), Springer, Cham, 1–12 (2022).
15. R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN: 3-540-15299-7
16. S.S. Goncharov, Yu.L. Ershov, Constructive Models, Springer, New York, 2000.
17. C.J. Ash, J.F. Knight, Computable structures and the hyperarithmetical hierarchy (Stud. Logic Found. Math. 144), Elsevier Science B.V., Amsterdam, 2000.
18. S. Gao, Invariant descriptive set theory, CRC Press, Boca Raton, FL, 2009.
19. C. Glymour, Inductive inference in the limit, Erkenntnis, 22, 23–31 (1985). DOI: https://doi.org/10.1007/978-94-017-1456-3_2
20. E. Martin, D. Osherson, Elements of scientific inquiry, MIT Press, Cambridge, 1998.
21. V. Kanovei, Borel equivalence relations: Structure and classification, AMS, Providence R.I., 2008.
22. G. Hjorth, Borel equivalence relations, in: M. Foreman, A. Kanamori (eds.), Handbook of set theory, Springer, Heidelberg, 297–332 (2010).
23. L.A. Harrington, A.S. Kechris, A. Louveau, A Glimm–Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (4), 903–928 (1990). DOI: https://doi.org/10.2307/1990906
24. W. Calvert, D. Cummins, J.F. Knight, S. Miller, Comparing Classes of Finite Structures, Algebra and Logic 43 (6), 374–392 (2004). DOI: https://doi.org/10.1023/B:ALLO.0000048827.30718.2c
25. J.F. Knight, S. Miller, M. Vanden Boom, Turing computable embeddings, J. Symb. Log. 72 (3), 901–918 (2007).
26. S. Coskey, J.D. Hamkins, R. Miller, The hierarchy of equivalence relations on the natural numbers under computable reducibility, Computability, 1 (1), 15–38 (2012). DOI: https://doi.org/10.3233/COM-2012-004
Review
For citations:
Bazhenov N.A. On learning for families of algebraic structures. Mathematics and Theoretical Computer Science. 2023;1(3):3-21. (In Russ.)
Views:
211
Email this article 