Learning algebraic structures with the help of Borel equivalence relations. (English) Zbl 07661889
Summary: We study algorithmic learning of algebraic structures. In our framework, a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. We prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation \(E_0\) of eventual agreement on reals. This motivates a novel research program, that is, using descriptive set theoretic tools to calibrate the (learning) complexity of nonlearnable families. Here, we focus on the learning power of well-known benchmark Borel equivalence relations (i.e., \( E_1, E_2, E_3, Z_0\), and \(E_{s e t}\)).
MSC:
| 03E15 | Descriptive set theory |
| 03C57 | Computable structure theory, computable model theory |
| 68Q32 | Computational learning theory |
Keywords:
inductive inference; algorithmic learning theory; computable structures; Borel equivalence relations; continuous reducibilityReferences:
| [1] | Ash, Chris J.; Knight, Julia F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144 (2000), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam · Zbl 0960.03001 |
| [2] | Bazhenov, Nikolay; Cipriani, Vittorio; San Mauro, Luca, Calculating the mind change complexity of learning algebraic structures, (Berger, Ulrich; Franklin, Johanna N. Y.; Manea, Florin; Pauly, Arno, Revolutions and Revelations in Computability (2022), Springer International Publishing: Springer International Publishing Cham), 1-12 · Zbl 07627913 |
| [3] | Bazhenov, Nikolay; Fokina, Ekaterina; San Mauro, Luca, Learning families of algebraic structures from informant, Inf. Comput., 275, Article 104590 pp. (2020) · Zbl 1496.68162 |
| [4] | Nikolay Bazhenov, Benoit Monin, Luca San Mauro, Rafael Zamora, On the computational content of the theory of Borel equivalence relations, Oberwolfach Preprint OWP-2021-06 (2021). |
| [5] | Bazhenov, Nikolay; San Mauro, Luca, On the Turing complexity of learning finite families of algebraic structures, J. Log. Comput., 31, 7, 1891-1900 (2021) · Zbl 07423157 |
| [6] | Calvert, W.; Cummins, D.; Knight, J. F.; Miller, S., Comparing classes of finite structures, Algebra Log., 43, 6, 374-392 (2004) · Zbl 1097.03026 |
| [7] | Camerlo, Riccardo; Gao, Su, The completeness of the isomorphism relation for countable Boolean algebras, Trans. Am. Math. Soc., 353, 2, 491-518 (2001) · Zbl 0960.03041 |
| [8] | Coskey, Samuel; Hamkins, Joel David; Miller, Russell, The hierarchy of equivalence relations on the natural numbers under computable reducibility, Computability, 1, 1, 15-38 (2012) · Zbl 1325.03049 |
| [9] | de Brecht, Matthew; Yamamoto, Akihiro, Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data, Theor. Comput. Sci., 411, 7-9, 976-985 (2010) · Zbl 1187.68306 |
| [10] | de Brecht, Matthew; Yamamoto, Akihiro, Topological properties of concept spaces (full version), Inf. Comput., 208, 4, 327-340 (2010) · Zbl 1192.68428 |
| [11] | Ershov, Yu. L.; Goncharov, S. S., Constructive Models (2000), Kluwer Academic/Plenum Publishers: Kluwer Academic/Plenum Publishers New York · Zbl 0954.03036 |
| [12] | Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca, Limit learning equivalence structures, (Garivier, Aurélien; Kale, Satyen, Proceedings of the 30th International Conference on Algorithmic Learning Theory. Proceedings of the 30th International Conference on Algorithmic Learning Theory, Chicago, Illinois, 22-24 Mar 2019. Proceedings of the 30th International Conference on Algorithmic Learning Theory. Proceedings of the 30th International Conference on Algorithmic Learning Theory, Chicago, Illinois, 22-24 Mar 2019, Proceedings of Machine Learning Research, vol. 98 (2019)), 383-403, PMLR |
| [13] | Friedman, Harvey; Stanley, Lee, A Borel reducibility theory for classes of countable structures, J. Symb. Log., 54, 3, 894-914 (1989) · Zbl 0692.03022 |
| [14] | Gao, Su, Invariant Descriptive Set Theory (2009), CRC Press: CRC Press Boca Raton, FL · Zbl 1154.03025 |
| [15] | Glymour, Clark, Inductive inference in the limit, Erkenntnis, 22, 23-31 (1985) |
| [16] | Gold, E. Mark, Language identification in the limit, Inf. Control, 10, 5, 447-474 (1967) · Zbl 0259.68032 |
| [17] | Gao, Ziyuan; Stephan, Frank; Wu, Guohua; Yamamoto, Akihiro, Learning families of closed sets in matroids, (Dinneen, Michael J.; Khoussainov, Bakhadyr; Nies, André, Computation, Physics and Beyond - International Workshop on Theoretical Computer Science. Computation, Physics and Beyond - International Workshop on Theoretical Computer Science, WTCS 2012. Computation, Physics and Beyond - International Workshop on Theoretical Computer Science. Computation, Physics and Beyond - International Workshop on Theoretical Computer Science, WTCS 2012, Lecture Notes in Computer Science, vol. 7160 (2012), Springer: Springer Berlin), 120-139 · Zbl 1353.68150 |
| [18] | Hjorth, Greg, Borel equivalence relations, (Handbook of Set Theory (2010), Springer), 297-332 · Zbl 1198.03055 |
| [19] | Harrington, L. A.; Kechris, A. S.; Louveau, A., A Glimm-Effros dichotomy for Borel equivalence relations, J. Am. Math. Soc., 3, 4, 903-928 (1990) · Zbl 0778.28011 |
| [20] | Harizanov, Valentina S.; Stephan, Frank, On the learnability of vector spaces, J. Comput. Syst. Sci., 73, 1, 109-122 (2007) · Zbl 1178.68297 |
| [21] | Kanoveĭ, Vladimir Grigor’evich, Borel Equivalence Relations: Structure and Classification, vol. 44 (2008), American Mathematical Soc. · Zbl 1155.03035 |
| [22] | Knight, Julia F.; Miller, Sara; Vanden Boom, Michael, Turing computable embeddings, J. Symb. Log., 72, 3, 901-918 (2007) · Zbl 1123.03026 |
| [23] | Lange, Steffen; Zeugmann, Thomas; Zilles, Sandra, Learning indexed families of recursive languages from positive data: a survey, Theor. Comput. Sci., 397, 1-3, 194-232 (2008) · Zbl 1146.68387 |
| [24] | Marker, David, Lectures on Infinitary Model Theory, Lecture Notes in Logic., vol. 46 (2016), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1356.03004 |
| [25] | Mekler, Alan H., Stability of nilpotent groups of class 2 and prime exponent, J. Symb. Log., 46, 4, 781-788 (1981) · Zbl 0482.03014 |
| [26] | Miller, Russell, Computable reducibility for Cantor space, (Structure and Randomness in Computability and Set Theory (2021), World Scientific: World Scientific Singapore), 155-196 · Zbl 1528.03177 |
| [27] | Martin, Eric; Osherson, Daniel, Elements of Scientific Inquiry (1998), MIT Press · Zbl 0957.03021 |
| [28] | Merkle, Wolfgang; Stephan, Frank, Trees and learning, J. Comput. Syst. Sci., 68, 1, 134-156 (2004) · Zbl 1072.68092 |
| [29] | Martin, Eric; Sharma, Arun; Stephan, Frank, Unifying logic, topology and learning in parametric logic, Theor. Comput. Sci., 350, 1, 103-124 (2006) · Zbl 1086.68066 |
| [30] | Putnam, Hilary, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Log., 30, 1, 49-57 (1965) · Zbl 0193.30102 |
| [31] | Soare, Robert I., Turing Computability. Theory and Applications (2016), Springer: Springer Berlin · Zbl 1350.03001 |
| [32] | Stephan, Frank; Ventsov, Yuri, Learning algebraic structures from text, Theor. Comput. Sci., 268, 2, 221-273 (2001) · Zbl 0983.68156 |
| [33] | Zeugmann, Thomas; Zilles, Sandra, Learning recursive functions: a survey, Theor. Comput. Sci., 397, 1-3, 4-56 (2008) · Zbl 1146.68443 |
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.
