HOW INDUCTIVE INFERENCE STRATEGIES DISCOVER THEIR ERRORS

Several well-known inductive inference strategies change the actual hy pothesis only when they discover that it ''provably misclassifies'' an example seen so far. This notion is made mathematically precise, and its general power is characterized. In spite of its strength, it is sh own that this approach is not of universal power. Consequently, hypoth eses are considered which ''unprovably misclassify'' examples, and the properties of this approach are studied. Among others, it turns out t hat this type is of the same power as monotonic identification. Then i t is shown that universal power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is allowed. Finally, a universal method is presented, enabling an inductive infere nce strategy to verify the incorrectness of any of its incorrect inter mediate hypotheses. (C) 1995 Academic Press, Inc.