Concept learning using complexity regularization

摘要

We apply the method of complexity regularization to learn conceptsfrom large concept classes. The method is shown to automatically findthe best balance between the approximation error and the estimationerror. In particular, the error probability of the obtained classifieris shown to decrease as 0(√(log n)) to the achievable optimum,for large nonparametric classes of distributions, as the sample size ngrows. In pattern recognition, or concept learning, the value of a{0,1}-valued random variable Y is to be predicted based upon observingan Rd-valued random variable X