probably almost discriminative learning
This paper develops a new computational model for learning stochastic rules (i.e. conditional probabilities over the set of labels for given instances) on the basis of statistical hypothesis testing theory, and derives bounds on sample complexities required for learning. The model deals with the problem of determining whether or not a given class of stochastic rules is probably almost discriminatively (PAD) learnable in the sense that one can discriminate, with low computational complexity and with high probability, between any pair of stochastic rules in that class by testing from which member of the pair a given test sequence has originated. In the proposed model, we construct new discrimination functions on the basis of the minimum description length (MDL) principle. We then derive upper bounds on the smallest training sample size and test sample size required by those discrimination functions in order to guarantee that for any pair of rules in a given class, two types of error probabilities are respectively less than &dgr; 1 and &dgr; 2 provided the distance between the two rules to be discriminated is not less than &egr;. As corollaries, we derive sample size bounds for PAD-learning of stochastic decision lists with at most k literals in each term and of stochastic decision trees with at most k log n depth ( k is fixed). A sufficient condition for polynomial-time PAD learnability of any given class is also given in terms of the existence of an algorithm approximating the minimum description length.
probability learning paper computer modeling model rules label statistics test theory sampling class computational complexity sequence training size order types errors distance decision tree log algorithm approximation polynomial timing