Probably Almost Discriminative Learning

摘要

This paper develops a new computational model for learning stochastic rules, called PAD (Probably Almost Discriminative)-learning model, based on statistical hypothesis testing theory. The model deals with the problem of designing a discrimination algorithm to test whether or not any given test sequence of examples of pairs of (instance, label) has come from a given stochastic rule P*. Here a composite hypothesis \(\tilde P\)is unknown other than it belongs to a given class \(\mathcal{C}\)