Speaker: Ana Lucia Vargas Sandoval (ILLC)
Date and Time: Thursday, April 11th 2019, 16:30-18:00
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: On the learning with positive and with complete data
Abstract. In this talk, I will present a study that addresses the differences between learning (of classes of recursive sets of natural numbers) with positive and with complete information. In particular, concerning the framework of learning with certainty or finite identification. The difference between finite identification with positive (pfi) and with complete data (cfi), if not as huge as in the learning in the limit case, is considerable not only in power but also in character. As we will see, the structural properties and computational recursive ones bring out different flavours in this distinction. We will see that for finite families (finite classes of finite sets of natural numbers) the difference lies exactly in the fact that for positive identification the families need to be anti-chains, while in the infinite case it is less simple, being an anti-chain is no longer a sufficient condition. We will also address maximal learnable families, identifiable families with no proper extension which can be identified, first with positive information and then with complete information. We will see an example of a computable (non-canonical) anti-chain of finite languages which is not pfi and not cfi. Time permitting, we will address a conjecture of ours, namely that each pfi family has either finitely many or uncountably many maximal non-effective pfi extensions. We will finalise with some current questions we are entertaining and further ways to continue.