Hypothesis Filtering: A Practical Approach to Reliable Learning

Abstract

This paper shows how to take virtually any learning algorithm and turn it into one which is accurate and reliable to an arbitrary degree. The transformation is accomplished by appending a filter that performs a statistical test to the learning algorithm. The filter only outputs hypotheses that pass the test. The test takes time which is polynomial in the desired accuracy and reliability levels and is independent of the learning algorithm and the complexity of its domain. Distribution-free statistical theory is used to prove that the filter works. We describe the application of the filter to concept learning, and to SE, a system which learns control knowledge by clustering its data. The significance of hypothesis filtering is two fold. First, filters may be used to evaluate and compare the performance of a wide range of learning algorithms. Second, applying hypothesis filtering to inductive learning algorithms demonstrates that the algorithms can be made arbitrarily reliable, and provably so.