Basic elements of statistical decision theory and statistical  (Page 4/5)

Statistical learning methods are based on developing decision rules or estimators based only on a collection of training examples, ratherthan predetermined probability models. Statistical learning methods are often said to be distribution-free , since they do not assume particular probability models. The canonical set-up for statisticallearning is as follows. We begin with a collection of training examples, ${\left\{(X_i,Y_i)\right\}}_{i=1}^n$ , which are assumed to be independently and identically distributed according to an unknown probability distribution $P_{X,Y}(x,y)$ . If we knew $P_{X,Y}(x,y)$ , then we could compute a desired risk function and design an optimal decision rule using the methods described above. Inessence, the training examples give us a glimpse at the underlying distribution, but our knowledge of it is far from complete. We cannotexactly compute a risk function, and therefore we cannot derive a corresponding optimal decision rule.

There are at least two ways to proceed at this point. One possibility is to use the training examples to estimate the joint probabilitydistribution, and then use this estimate to derive an decision rule. Unfortunately, the (general-purpose) problem of estimating adistribution is often more difficult from a limited pool of data than is the problem of designing a specific-purpose decision rule. Forthis reason, a second possibility is more commonly favored in practice. Rather than estimating the complete distribution, one canuse the training examples to directly design a decision rule. More precisely, perhaps the most common approach is to use the trainingexamples to compute an estimate of the desired risk function.

Suppose that we are interested in minimizing a particular risk function. Recall that the risk is the expected value of a chosen lossfunction. Let $\ell (\widehat{Y},Y)$ denote the loss, and let $f\left(X\right)$ denote a candidate decision function, mapping observations to predictions about $Y$ (i.e., $\widehat{Y}=f\left(X\right)$ ). The empirical risk function is constructed from the training examples as follows:

This is simply the average loss of the decision rule $f$ over the set of training examples. Note that since the training examples areindependent and identically distributed, the expected value of the empirical risk is equal to the true risk $R\left(f\right)=E\left[\ell \right(f\left(X\right),Y\left)\right]$ . Moreover, we known (according to the law of large numbers) that theempirical risk tends to the true risk as the size of the training sample increases. These facts lend support to the idea of choosing adecision rule to minimize the empirical risk.

Empirical risk minimization (ERM) is just this process. Given a collection of possible decision rules, say $\mathcal{F}$ , ERM selects a decision rule according to

The selected rule, ${\widehat{f}}_n$ , obviously depends on the given set of training examples, and therefore it is itself a random quantity. Thetheoretically optimal counterpart to ${\widehat{f}}_n$ is the decision rule that minimizes the true risk

The central problem in statistical learning is to quantify how close ${\widehat{f}}_n$ performs relative to $f^{*}$ . Note that $R\left(f^{*}\right)\le R\left({\widehat{f}}_n\right)$ , since $f^{*}$ minimizes the true risk. Thus, one way to gauge the performance of ${\widehat{f}}_n$ relative to $f^{*}$ is to show that there exists small positive values $ϵ$ and $\delta$ such that with probability at least $1-\delta$ we have