Trading Monotonicity Demands versus Efficiency
Authors: Steffen Lange and Thomas Zeugmann
Source: Bulletin of Informatics and Cybernetics
27, No. 1, 1995, 53 - 83.
Abstract.
The present paper deals with the learnability of indexed families
of uniformly recursive languages from positive data. We consider the
influence of three monotonicity demands and their dual counterparts
to the efficiency of the learning process.
The efficiency of learning is measured in dependence on the number
of mind changes a learning algorithm is allowed to perform.
The three notions of (dual) monotonicity reflect different formalizations of the
requirement that the learner has to produce better and better (specializations)
generalizations when fed more and more data on the target concept.
We distinguish between exact learnability ( has to be inferred
with respect to ), class preserving learning (
has to be inferred with respect to some suitably chosen enumeration of all the
languages from ), and class comprising inference
( has to be learned with respect to some suitably chosen
enumeration of
uniformly recursive languages containing at least all the languages from
).
In particular, we prove that a relaxation of the relevant (dual) monotonicity
requirement may result in an arbitrarily large speed-up. However,
whether or not such a speed-up may be achieved crucially depends on the set of
allowed hypothesis spaces as well as of the (dual) monotonicity demands
involved.
©Copyright 1995, Research Association of Statistical Sciences
|