How Inductive Inference Strategies Discover Their Errors

Several well-known inductive inference strategies change the actual hypothesis 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 shown that this approach is not of universal power. Consequently, hypotheses are considered which "unprovably misclassify" examples, and the properties of this approach are studied. Among others, it turns out that this type is of the same power as monotonic identification. Then it 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 inference strategy to verify the incorrectness of any of its incorrect intermediate hypotheses.

Authors

• R. Freivalds
• E.B. Kinber
• R. Wiehagen

Keywords

No keywords are indexed for this paper.