Learning families of algebraic structures from informant

Information And Computation 1 (275):104590 (2020)
  Copy   BIBTEX

Abstract

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type InfEx_\iso, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx_\iso-learnable if and only if the structures can be distinguished in terms of their \Sigma^2_inf-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,038

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.
Informal Home Education: Philosophical Aspirations put into Practice.Alan Thomas & Harriet Pattison - 2012 - Studies in Philosophy and Education 32 (2):141-154.
Effective algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Model theory and machine learning.Hunter Chase & James Freitag - 2019 - Bulletin of Symbolic Logic 25 (3):319-332.
Structure Mapping for Social Learning.Stella Christie - 2017 - Topics in Cognitive Science 9 (3):758-775.

Analytics

Added to PP
2022-08-04

Downloads
8 (#1,319,469)

6 months
5 (#641,756)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Luca San Mauro
Università degli Studi di Roma La Sapienza

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references