MODEL THEORY AND MACHINE LEARNING

DOI10.1017/BSL.2018.71MaRDI QIDQ5240809zbMATH OpenOpenAlexFDO

Authors Hunter Chase, James Freitag

Publication date 29 October 2019

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.06566

zbMATH Keywords

machine learningmodel theory

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Applications of model theory (03C98) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: About 25 years ago, it came to light that a single combinatorial property determines both an important dividing line in model theory (NIP) and machine learning (PAC-learnability). The following years saw a fruitful exchange of ideas between PAC learning and the model theory of NIP structures. In this article, we point out a new and similar connection between model theory and machine learning, this time developing a correspondence between emph{stability} and learnability in various settings of emph{online learning.} In particular, this gives many new examples of mathematically interesting classes which are learnable in the online setting.

Recommendations

• scientific article; zbMATH DE number 939032
• Model theory
• scientific article; zbMATH DE number 5296405
• scientific article; zbMATH DE number 53151
• Model theory
• scientific article; zbMATH DE number 798660
• scientific article; zbMATH DE number 44997
• Mathematical theories of machine learning: theory and applications
• scientific article; zbMATH DE number 6528605
• Model learning as a satisfiability modulo theories problem

Cites work

• Classification theory and the number of non-isomorphic models
• Compression schemes, stable definable families, and o-minimal structures
• Elimination of quantifiers for modules
• Externally definable sets and dependent pairs
• scientific article; zbMATH DE number 554994 (Why is no real title available?)
• scientific article; zbMATH DE number 858680 (Why is no real title available?)
• scientific article; zbMATH DE number 3349995 (Why is no real title available?)
• Model theory and complex geometry
• Model theory for metric structures
• Notes on the stability of separably closed fields
• The weighted majority algorithm
• Vapnik-Chervonenkis Classes of Definable Sets

Cited in

(15)

• Regular partitions of gentle graphs
• scientific article; zbMATH DE number 6528605 (Why is no real title available?)
• scientific article; zbMATH DE number 798660 (Why is no real title available?)
• THICKET DENSITY
• MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES
• Machine learning and the continuum hypothesis
• On uniform definability of types over finite sets for NIP formulas
• Machine Learning and Invariant Theory
• Enhancing deep learning algorithm accuracy and stability using multicriteria optimization: an application to distributed learning with MNIST digits
• Model theory and agnostic online learning via excellent sets
• The amalgamation property for automorphisms of ordered abelian groups
• Applications of littlestone dimension to query learning and to compression
• The unstable formula theorem revisited via algorithms
• Sunflowers in set systems of bounded dimension
• Applications of Littlestone dimension to query learning and to compression

This page was built for publication: MODEL THEORY AND MACHINE LEARNING

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5240809)