Classifying different criteria for learning algebraic structures
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909372221751296 |
|---|---|
| author | Bazhenov, Nikolay Cipriani, Vittorio Jain, Sanjay Mauro, Luca San Stephan, Frank |
| author_facet | Bazhenov, Nikolay Cipriani, Vittorio Jain, Sanjay Mauro, Luca San Stephan, Frank |
| contents | In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a learner is given larger and larger fragments of a structure from a given target family and is required to output an hypothesis about the structure's isomorphism type. So far researchers focused on $\mathbf{Ex}$-learning, in which the learner is asked to eventually stabilize to the correct hypothesis, and on restrictions where the learner is allowed to change the hypothesis a fixed number of times. Yet, other learning paradigms coming from classical algorithmic learning theory remained unexplored. We study the "learning power" of such criteria, comparing them via descriptive-set-theoretic tools thanks to the novel notion of $E$-learnability. The main outcome of this paper is that such criteria admit natural syntactic characterizations in terms of infinitary formulas analogous to the one given for $\mathbf{Ex}$-learning in [6]. Such characterizations give a powerful method to understand whether a family of structure is learnable with respect to the desired criterion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22933 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Classifying different criteria for learning algebraic structures Bazhenov, Nikolay Cipriani, Vittorio Jain, Sanjay Mauro, Luca San Stephan, Frank Logic 68Q32, 03E15 In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a learner is given larger and larger fragments of a structure from a given target family and is required to output an hypothesis about the structure's isomorphism type. So far researchers focused on $\mathbf{Ex}$-learning, in which the learner is asked to eventually stabilize to the correct hypothesis, and on restrictions where the learner is allowed to change the hypothesis a fixed number of times. Yet, other learning paradigms coming from classical algorithmic learning theory remained unexplored. We study the "learning power" of such criteria, comparing them via descriptive-set-theoretic tools thanks to the novel notion of $E$-learnability. The main outcome of this paper is that such criteria admit natural syntactic characterizations in terms of infinitary formulas analogous to the one given for $\mathbf{Ex}$-learning in [6]. Such characterizations give a powerful method to understand whether a family of structure is learnable with respect to the desired criterion. |
| title | Classifying different criteria for learning algebraic structures |
| topic | Logic 68Q32, 03E15 |
| url | https://arxiv.org/abs/2410.22933 |