Abstract
A broad class of prediction problems can be framed as the problem of inferring an unknown classification rule from labeled data. In the well-studied case of binary classification rules, this amounts to learning an unknown Boolean function f given a set of labeled data points of the form (x,f(x)). A great deal of effort in computational learning theory has been expended on studying what types of classification rules can be learned from labeled data, and under what circumstances such learning can be performed by computationally efficient algorithms. We will give an overview of some aspects of the state of the art in this area, with a special focus on learning from noisy and partial data.