Title: The Simplest Kind of Learning

Abstract: In this talk I will focus on finite identifiability which,
in a certain order of things, can be considered to be the simplest
kind of learning. To finitely identify a concept means to be able to
recognise it with certainty after receiving some finite amount of data
consistent with this concept. Such a finite sample that suffices for
finite identification is called definite finite tell-tale set
(DFTT). I will start with the characterisations of finite
identifiability provided in 1992 by Mukouchi and, independently, by
Lange and Zeugmann. These characterisations are in the style of Gold’s
identifiability and Angluin’s finite tell-tales. In the main part of
the talk I will recall the results obtained (for positive data) by
Gierasimczuk and de Jongh (2013), which where developed further (for
the case of complete data) by de Jongh and Vargas Sandoval (2018).

Even though this concept of learning is very simple, it turned out to
be very useful as a starting point in understanding long-term dynamics
of updates in Dynamic (Epistemic) Logic, for which a discrete and
exact approach to learning is very adeqaute (see Gierasimczuk 2009,
Dégremont and Gierasimczuk 2011).  Finite identifiability has also
proved instrumental in setting up the new framework for exact learning
of action models in Dynamic Epistemic Logic (Bolander and Gierasimczuk
2018).

References:
- Mukouchi, Y.: Characterization of finite identification. In: AII’92:
Proceedings of the International Workshop on Analogical and Inductive
Inference, Springer-Verlag (1992) 260–267.
- Lange, S., Zeugmann, T.: Types of monotonic language learning and their
characterization. In: COLT’92: Proceedings of the 5th Annual ACM Conference on
Computational Learning Theory, ACM (1992) 377–390.
- Gierasimczuk, N., Learning by Erasing in Dynamic Epistemic Logic, A.H.
Dediu, A.M. Ionescu, and C. Martin-Vide (Eds.): LATA 2009, LNCS 5457, pp.
362-373, 2009.
- Gierasimczuk, N., Bridging Learning Theory and Dynamic Epistemic Logic,
Synthese 169 (2009), pp. 371-384.
- Dégremont, C., Gierasimczuk, N.: Finite identification from the viewpoint of
epistemic update. Information and Computation 209(3) (2011) 383–396.
- Gierasimczuk, N. and de Jongh, D., On the Complexity of Conclusive Update,
The Computer Journal 56(3):365-377, 2013.
- Bolander, T. and Gierasimczuk, N., Learning to Act: Qualitative Learning of
Deterministic Action Models, Journal of Logic and Computation, Volume 28,
Issue 2, 2018, Pages 337-365.
- De Jongh, D., and Vargas Sandoval A., Finite Identification with Positive
and with Complete Data, International Tbilisi Symposium on Logic, Language,
and Computation, TbiLLC 2018: Language, Logic, and Computation, pp 42-63.