CS761 Spring 2013 Advanced Machine Learning Statistical Learning Theory

Consider a family of binary classifiers G = {g: X 7 → {−1, 1}}. G can be either probabilistic models or not, such as decision trees, neural nets, SVMs, logic rules, the groundhog family of Punxsutawney Phil, a tank full of Paul the Octopus ’ relatives, etc. Each g ∈ G predicts the label y = g(x) from input x. Importantly, assume an unknown but fixed joint distribution p(x, y) from which the training and future test items are sampled. Now consider the 0-1 loss. This leads to the risk of g R(g) = E(g(x) 6 = y). F The expectation is over (x, y) ∼ p. g(x) 6 = y takes value in {0, 1}. The “test set error ” in practice is an unbiased estimate of the risk. Our ultimate goal is to pick g ∈ G so that the risk is minimized. It is important to understand three fundamental limits on how low the risk can go: 1. Since p(y | x) may not be “crisp”, there is a Bayes risk lower bound on any classifier. Let η(x) = E(Y | X = x) = 2p(y = 1 | x) − 1. Then the Bayes classifier is B(x) = sign(η(x)). It achieves the minimum risk over all measurable functions R(B) = infg R(g) (Note the inf is not restricted to G). This risk is known as the Bayes risk R(B) = E ( 1−|η(x)|2). 2. It is possible that B / ∈ G. For example, G may consists of all linear classifiers but B may hav