TCS-TR-A-17-82

Date: Sat Nov 4 19:16:59 2017

Title: On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

Authors: Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science Hokkaido University N-14, W-9 Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. The present paper deals with the inductive inference of recursively enumerable languages from positive data (also called text). It introduces the learning models of verifiability and comparability. The input to a verifier is an index e and a text of the target language L, and the learner has to verify whether or not the index e input is correct for the target language L. A comparator receives two indices of languages from the target class ℒ as input and has to decide in the limit whether or not these indices generate the same language. Furthermore, standardisability is studied, where a standardiser receives an index j of some target language L from the class ℒ, and for every L∈ ℒ there must be an index e such that e generates L and the standardiser has to map j to e. Additionally, the common learning models of explanatory learning, conservative explanatory learning, and behaviourally correct learning are considered. For almost all learning models mentioned above it is also appropriate to consider the number of times a learner changes its mind. In particular, if no mind change occurs then we obtain the finite variant of the models considered. Occasionally, also learning with the help of an oracle is taken into consideration. The main goal of the present paper is to figure out to what extent verifiability, comparability, and standardisability are helpful for the inductive inference of classes of recursively enumerable languages. Here we also distinguish between indexed families, one-one enumerable classes, and recursively enumerable classes. Our results are manyfold, and an almost complete picture is obtained. In particular, for indexed families and recursively enumerable classes finite comparability, finite standardisability, and finite verifiability always imply finite learnability. If at least one mind change is allowed, then there are differences, i.e., comparability or verifiability imply conservative explanatory learning, but standardisability does not; still explanatory learning can be achieved.