Learning Concepts Incrementally with Bounded Data Mining

Authors: John Case, Sanjay Jain, Steffen Lange and Thomas Zeugmann

Abstract. Important refinements of incremental concept learning from positive data considerably restricting the accessibility of input data are studied. Let c be any concept; every infinite sequence of elements exhausting c is called positive presentation of c. In all learning models considered the learning machine computes a sequence of hypotheses about the target concept from a positive presentation of it. With iterative learning, the learning machine, in making a conjecture, has access only to its previous conjecture and the latest datum coming in. In k-bounded example-memory inference (k is a priori fixed) the learner is allowed to access, in making a conjecture, only its previous hypothesis, its memory of up to k data items it has already seen, and the latest datum coming in. In the case of k-feedback identification, the learning machine, in making a conjecture, has access only to its previous conjecture, the latest datum coming in, and, on the basis of this information, it can compute k items and query the database of previous data to find out, for each of the k items, whether or not it is in the database (k is again a priori fixed). In all cases, the sequence of conjectures has to converge to a hypothesis correctly describing the target concept.

Our results are manyfold. An infinite hierarchy of successively more powerful feedback learners in dependence on the number k of queries allowed to be asked is established. However, the hierarchy collapses to 1-feedback inference if only indexed families of infinite concepts are considered, and, moreover, its learning power is then equal to unrestricted incremental learning; however, the hierarchy remains infinite for concept classes of only infinite r.e. concepts. Both k-feedback inference and k-bounded example-memory identification are more powerful than iterative learning but, surprisingly, incomparable to one another. Furthermore, there are cases where redundancy in the hypothesis space is shown to be a resource increasing the learning power of iterative learners. Finally, of the important class of unions up to k pattern languages is shown to be iteratively inferable.