Learning and Consistency

Authors: Rolf Wiehagen and Thomas Zeugmann

Source: “Algorithmic Learning for Knowledge-Based Systems,” (K.P. Jantke and S. Lange, Eds.), Lecture Notes in Artificial Intelligence 961, pp. 1 - 24, Springer-Verlag 1995.

Abstract.

In designing learning algorithms it seems quite reasonable to construct them in such a way that all data the algorithm already has obtained are correctly and completely reflected in the hypothesis the algorithm outputs on these data. However, this approach may totally fail. It may lead to the unsolvability of the learning problem, or it may exclude any efficient solution of it.

Therefore we study several types of consistent learning in recursion-theoretic inductive inference. We show that these types are not of universal power. We give ``lower bounds'' on this power. We characterize these types by some versions of decidability of consistency with respect to suitable ``non-standard'' spaces of hypotheses.

Then we investigate the problem of learning consistently in polynomial time. In particular, we present a natural learning problem and prove that it can be solved in polynomial time if and only if the algorithm is allowed to work inconsistently.