Incremental Maximization of Non-Instance-Averaging Utility Functions with Applications to Knowledge Discovery Problems

Abstract

Data-independent sample bounds are known to grossly overestimate the amount of data needed for most individual problem instances. This has led to significant recent interest in sequential algorithms which also give precise guarantees about the quality of results, but determine the amount of data needed based on characteristics of the actual problem instance at hand, and thus need significantly fewer examples. In this paper, we present a practical sequential sampling algorithm which (a) is capable of quickly identifying the n best hypotheses and (b) works for all utility functions that can be estimated with bounded error. The algorithm thus can be used not only for predictive learning, but also for tasks such as association rule finding or subgroup discovery. Our experiments with two real-world domains show that our algorithm can be orders of magnitude faster than non-sequential sampling algorithms.