Confident Iterative Learning in Computational Learning Theory

Abstract

Let us assume that we have a class of sets. Now, if we have a machine that, fed information on one of these sets, tells us which set the information belonged to, then the machine underwent some sort of learning. This act of learning can happen in various forms. The aim of this thesis is to motivate, introduce and investigate some possible ways of learning. Firstly, we will motivate the basic ideas of computability theory and algorithmic learning theory. Concerning the latter theory, we will get to know some widely used learning types, the most prominent being the explanatory and behaviourally correct learning. The main aim, however, is to investigate a new type of learning, the confident iterative learning. The idea here is to merge two known concepts, namely that of the condent and iterative learner. Additionally to learning the sets of the class correctly, the first learner is required to make some, not necessarily true, guess on any other set, too. Instead of having all the information of the set at hand at every time, the second learner may only use its last hypothesis as memory on the previous calculations and information. So, we restrict its memory. Observing it, we will provide some negative as well as positive examples. We will also prove some properties the confident iterative learner possesses. This will peak at the classication theorem, where we provide a classication for certain types of classes. As last act, we will consider an even more advanced idea, namely that of the very and strongly confident learner. Here, we will focus on the behaviour on sets not belonging to the class. We will try to detect them, in one form or another. Lastly, we will focus on the possible hypotheses. We will investigate the behaviour of the confident iterative learning when choosing special kinds of hypothesis spaces.