Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-25T03:02:11.787Z Has data issue: false hasContentIssue false
  • English
  • Français

MODEL THEORY AND MACHINE LEARNING

Published online by Cambridge University Press:  15 February 2019

HUNTER CHASE  and
JAMES FREITAG
HUNTER CHASE
Affiliation:
DEPARTMENT OF MATHEMATICS UIC, CHICAGO IL, USA E-mail: [email protected]: [email protected]
JAMES FREITAG
Affiliation:
DEPARTMENT OF MATHEMATICS UIC, CHICAGO IL, USA E-mail: [email protected]: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 stability and learnability in various settings of online learning. In particular, this gives many new examples of mathematically interesting classes which are learnable in the online setting.

Keywords

03C9897P20model theorymachine learning
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 25 , Issue 3 , September 2019 , pp. 319 - 332
Copyright
Copyright © The Association for Symbolic Logic 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Baur, W., Elimination of quantifiers for modules . Israel Journal of Mathematics, vol. 25 (1976), no. 1, pp. 64–70.CrossRefGoogle Scholar
Ben-david, S., Pál, D., and Shalev-shwartz, S., Agnostic online learning, Proceedings of the 22nd Annual Conference on Learning Theory COLT, 2009.Google Scholar
Bhaskar, S., Thicket density, arXiv preprint, 2017, arXiv:1702.03956.Google Scholar
Blum, L., Generalized algebraic structures: A model theoretical approach, Ph.D. thesis, MIT, 1968.Google Scholar
Chernikov, A. and Simon, P., Externally definable sets and dependent pairs. Israel Journal of Mathematics, vol. 194 (2013), no. 1, pp. 409–425.CrossRefGoogle Scholar
Guingona, V., Nip theories and computational learning theory, https://tigerweb.towson.edu/vguingona/NIPTCLT.pdf.Google Scholar
Johnson, H. R. and Laskowski, M. C., Compression schemes, stable definable families, and o-minimal structures. Discrete & Computational Geometry , vol. 43 (2010), no. 4, pp. 914–926.CrossRefGoogle Scholar
Laskowski, M. C., Vapnik-Chervonenkis classes of definable sets. Journal of the London Mathematical Society, vol. 2 (1992), no. 2, pp. 377–384.CrossRefGoogle Scholar
Littlestone, N., Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, vol. 2 (1988), no. 4, pp. 285–318.CrossRefGoogle Scholar
Littlestone, N. and Warmuth, M. K., The weighted majority algorithm. Information and computation, vol. 108 (1994), no. 2, pp. 212–261.CrossRefGoogle Scholar
Livni, R. and Simon, P., Honest compressions and their application to compression schemes, Conference on Learning Theory, 2013, pp. 77–92.Google Scholar
Marker, D., Messmer, M., and Pillay, A., Model Theory of Fields, A. K. Peters/CRC Press, Natick, MA, 2005.CrossRefGoogle Scholar
Moosa, R., Model theory and complex geometry. Notices of the AMS, vol. 57 (2010), no. 2, pp. 230–235.Google Scholar
Poizat, B., Stable Groups, Mathematical Surveys and monographs, vol. 87, American Mathematical Society, Providence, RI, 1987.Google Scholar
Rakhlin, A., Sridharan, K., and Tewari, A., Online learning: Beyond regret, Proceedings of the 24th Annual Conference on Learning Theory, 2011, pp. 559–594.Google Scholar
Robinson, A., On the concept of a differentially closed field. Bulletin of the Research Council of Israel Section F, vol. 8F (1959), pp. 113–128.Google Scholar
Sela, Z., Diophantine geometry over groups viii: Stability, arXiv preprint, 2006, arXiv:math/0609096.CrossRefGoogle Scholar
Shelah, S., Classification Theory and the Number of Nonisomorphic Models, Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland, New York, 1978.Google Scholar
Wood, C., Notes on the stability of separably closed fields. The Journal of Symbolic Logic, vol. 44 (1979), no. 3, pp. 412–416.CrossRefGoogle Scholar
Yaacov, I. B., Berenstein, A., Henson, C. W., and Usvyatsov, A., Model theory for metric structures. Retrieved from https://faculty.math.illinois.edu/∼henson/ cfo/mtfms.pdf, 2006.Google Scholar
Zilber, B., Model theory and algebraic geometry, Proceedings of the 10th Easter Conference on Model Theory, Humboldt Universitat, 1993, pp. 93–117.Google Scholar