Reliable and Useful Learning

Abstract

Reliable and probably useful learning from examples, proposed by Rivest and Sloan, is a variant of Valiant's concept learning framework. We show that having different sources for positive and negative examples makes reliable learning easier than having just one source for labeled examples. We also show that the class of boolean monomials and the class of rectangles are not reliably learnable from a polynomial number of either kind of examples. This demonstrates that reliable learning is much more difficult than normal Valiant-style learning. On the positive side we prove that symmetric concepts can be learned reliably from a polynomial number of examples.