这一章主要介绍模型选择和评估相关的内容。一个模型对训练数据有强的拟合能力是远远不够的，因为我们关心的是它对于新数据的预测能力，或者说泛化能力。一个能够精确拟合任意给定数据集的模型是没有意义的，用波普尔的话讲，这样的模型是『不可证伪』的，不科学了。

书上的内容很全，但是不够细致，这一章的几篇笔记我会尽量把公式推导和证明都补上，加上对其中一些概念的补充说明。

Bias-Variance分解

预测变量(predictor) \(X\)和响应变量\(Y\)是随机变量，从联合概率分布\(P(X,Y)\)中sample得到。

训练集\(\mathcal{D}\)也是一个随机变量，我们通过\(P(\mathcal{D})\) sample出一个训练集，从这个训练集上拟合得到的\(\hat{f}\)也是一个随机变量。

对于训练集中的一个点\((x,y)\)，通过模型得到的预测值是\(\hat{y} = \hat{f}(x)\)，\(y\)与\(\hat{y}\)之间显然会存在差异，如果选用二次误差函数，loss function为

\[\begin{equation} \label{eq:loss-function} L(y,\hat{y}) = \{y - \hat{f}(x)\}^2 \end{equation}\]

先对\(x\)和\(y\)取期望：

\[\begin{equation} \label{eq:decomposition1} \begin{split} \mathbb{E}_{x,y}[L] &= \int \int \{y - \hat{f}(x)\}^2 p(x, y) dx dy \\ &= \int \int \{ \hat{f}(x) -\mathbb{E}_y[y|x] + \mathbb{E}_y[y|x] - y \}^2 p(x,y) dx dy \\ &= \int \int \left[ \{ \hat{f}(x) -\mathbb{E}_y[y|x] \}^2 + 2\{ \hat{f}(x) -\mathbb{E}_y[y|x] \} \{\mathbb{E}_y[y|x] - y \} + \{ \mathbb{E}_y[y|x] - y \}^2 \right ] p(x,y) dx dy \end{split} \end{equation}\]

其中\(\mathbb{E}_y [y \vert x] = \int yp(y \vert x) dy\)（注意对\(y\)积分后，\(\mathbb{E}_y[y \vert x]\)里已经没有\(y\)了，是\(x\)的函数）。 我们把式(\(\ref{eq:decomposition1}\))中间那一项展开，并分别对\(y\)积分：

\[\begin{align*} \int \int \hat{f}(x) \mathbb{E}_y[y|x] p(x,y) dy dx &= \int \hat{f}(x) \mathbb{E}_y[y|x] p(x) dx \\ - \int \int y \hat{f}(x) p(x,y) dy dx &= \int \int y \hat{f}(x) p(y|x) p(x) dy dx \\ &= - \int \hat{f}(x) \mathbb{E}_y[y|x] p(x) dx \\ - \int \int \{ \mathbb{E}_y[y|x] \}^2 p(x,y) dy dx &= - \int \{ \mathbb{E}_y[y|x] \}^2 p(x) dx \\ \int \int y \mathbb{E}_y[y|x] p(x,y) dy dx &= \int \int \mathbb{E}_y[y|x] y p(y|x) p(x) dy dx \\ &= \int \{ \mathbb{E}_y[y|x] \}^2 p(x) dx \end{align*}\]

可见展开的4项互相抵消，(\(\ref{eq:decomposition1}\))式中间的『cross-term』消失了。又因为：

\[\int \int \{ \hat{f}(x) -\mathbb{E}_y[y|x] \}^2 p(x,y) dx dy = \int \{ \hat{f}(x) -\mathbb{E}_y[y|x] \}^2 p(x) dx\]

（上式成立是因为\(\hat{f}(x)\)和\(\mathbb{E}_y[y \vert x]\)都仅是\(x\)的函数）

\[\begin{align*} \int \int \{ \mathbb{E}_y[y|x] - y \}^2 p(x,y) dxdy &= \int \int \{ \mathbb{E}_y[y|x] - y \}^2 p(y|x) p(x) dxdy \\ &= \int \mathbb{Var}_y(y|x) p(x) dx \end{align*}\]

于是我们得到了

\[\begin{equation} \label{eq:decomposition2} \mathbb{E}_{x,y}[L] = \int \{ \hat{f}(x) -\mathbb{E}_y[y|x] \}^2 p(x) dx + \int \mathbb{Var}_y(y|x) p(x) dx \end{equation}\]

注意上式的第二项在PRML原文的(1.90)式中被写错了，勘误里已经更正。

记住还有一个随机变量在(\(\ref{eq:decomposition2}\))式中尚未考虑，就是训练集\(\mathcal{D}\)，这个变量影响了预测函数\(\hat{f}\)，现在我们对(\(\ref{eq:decomposition2}\))式第一项里的积分项取期望：

\[\begin{align*} \mathbb{E}_\mathcal{D} \left [ \{ \hat{f}(x) -\mathbb{E}_y[y|x] \}^2 \right ] &= \mathbb{E}_\mathcal{D} \left [ \{ \hat{f}(x)- \mathbb{E}_\mathcal{D}[\hat{f}(x)] + \mathbb{E}_\mathcal{D}[\hat{f}(x)] -\mathbb{E}_y[y|x] \}^2 \right ] \\ &= \mathbb{E}_\mathcal{D} \left [ \{ \hat{f}(x) - \mathbb{E}_\mathcal{D}[\hat{f}(x)] \}^2 \right ] + \mathbb{E}_\mathcal{D} \left [ \{ \mathbb{E}_\mathcal{D}[\hat{f}(x)] - \mathbb{E}_y[y|x] \}^2 \right ] \\ &\qquad + \mathbb{E}_\mathcal{D} \left [ 2 \{ \hat{f}(x) - \mathbb{E}_\mathcal{D}[\hat{f}(x)] \} \{ \mathbb{E}_\mathcal{D}[\hat{f}(x)] - \mathbb{E}_y[y|x] \} \right ] \end{align*}\]

由于\(\{ \mathbb{E}_\mathcal{D}[\hat{f}(x)] - \mathbb{E}_y[y \vert x] \}\)对\(\mathcal{D}\)而言是常数，上式第二项就等于\(\{ \mathbb{E}_\mathcal{D}[\hat{f}(x)] - \mathbb{E}_y[y\vert x] \}^2\)；同时最后一项『cross-term』只需对\(\{ \hat{f}(x) - \mathbb{E}_\mathcal{D}[\hat{f}(x)] \}\)取期望，就把这一项消去了。最后我们得到

\[\begin{equation} \label{eq:decomposition3} \begin{split} \mathbb{E}_\mathcal{D} \mathbb{E}_{x,y} [L] &= \int \{ \mathbb{E}_\mathcal{D} [\hat{f}(x)] - \mathbb{E}_y[y|x] \}^2 p(x) dx \\ & \quad + \int \mathbb{E}_\mathcal{D} \left [ \{ \hat{f}(x) - \mathbb{E}_\mathcal{D}[\hat{f}(x)] \}^2 \right ] p(x) dx \\ & \quad + \int \mathbb{Var}_y(y|x) p(x) dx \\ &= (bias)^2 + variance + noise \end{split} \end{equation}\]

如果把\(x\)看成是已知的\(x_0\)，以及真实的响应函数\(y = f(x_0) + \epsilon\)，其中\(\mathbb{E}(\epsilon) = 0\)，\(\mathbb{Var}(\epsilon) = \sigma_{\epsilon}^2\)，那么(\ref{eq:decomposition3})式就可以写成下面的形式：

\[\begin{equation} \label{eq:decomposition4} \mathbb{E}[L] = \{ \mathbb{E}_\mathcal{D} [\hat{f}(x_0)] - f(x_0) \}^2 + \mathbb{E}_\mathcal{D} \left [ \{ \hat{f}(x_0) - \mathbb{E}_\mathcal{D}[\hat{f}(x_0)] \}^2 \right ] + \sigma_{\epsilon}^2 \end{equation}\]

这就是ESL书上的式子，被称作『expected prediction error』，这个error仅和训练集的原始数据有关（除此之外还有其他各种定义的error，后文介绍）。关键问题在于这里的期望\(\mathbb{E}[\cdot]\)其实涵盖了两部分，一部分是对训练集\(\mathcal{D}\)的期望，训练集不同导致\(\hat{f}(\cdot)\)不同；另一部分是对数据分布\((X,Y)\)的期望。这点要注意区分。

直观地解释，我们的训练集总是从样本总体中选取，每次训练集不同，拟合得到的\(\hat{f}(\cdot)\)自然也不同。假设我们不厌其烦地选了无穷多个训练集，训练得到无穷多个\(\hat{f}_i(\cdot)\)，那么这些函数会有一个平均值\(\hat{f}_0(\cdot)\)，bias衡量的是\(\hat{f}_0(\cdot)\)和真实的\(f(\cdot)\)之间的差异，而variance衡量了这一堆\(\hat{f}_i(\cdot)\)彼此之间的差异程度。

模型越复杂，平均下来对真实函数逼近得越好，bias越小；但同时受训练集选择的影响也越大，variance越大。这是一个躲不掉的trade-off。

KNN的bias-variance分解

KNN模型拟合如下：

\[\hat{f}(x) = \frac{1}{k} \sum_{l=1}^k y_{(l)}\]

由于KNN的训练集就是样本全体本身，因此除去样本\(x\)的随机性，\(\mathcal{D}\)的随机性只和\(y\)有关，也就是只和\(\epsilon\)有关了。于是

\[\begin{align*} \mathbb{E}_{\mathcal{D}}[\hat{f}(x_0)] &= \mathbb{E}_{\mathcal{D}} \left [ \frac{1}{k} \sum_{l=1}^k \{ f(x_{(l)}) + \epsilon_{(l)} \} \right ] \\ &= \frac{1}{k} \sum_{l=1}^k f(x_{(l)}) \end{align*}\] \[\begin{align*} \mathbb{Var}_\mathcal{D} [\hat{f}(x_0)] &= \mathbb{Var}_\mathcal{D} [\hat{f}(x_0)] \\ &= \mathbb{Var}_\mathcal{D} \left [ \frac{1}{k} \sum_{l=1}^k \{ f(x_{(l)}) + \epsilon_{(l)} \} \right ] \\ &= \frac{1}{k^2} \cdot k \cdot \mathbb{Var}(\epsilon) \\ &= \frac{\sigma_{\epsilon}^2}{k} \end{align*}\]

代入(\ref{eq:decomposition4})式就得到了书上的结果。

这里有同学可能要问，你刚才不是说要区分\(P(x,y)\)和\(P(\mathcal{D})\)吗，这会儿怎么把\(\epsilon\)给带进来了，为什么\(\mathbb{E}_\mathcal{D}[\cdot]\)就是\(\mathbb{E}[\epsilon_{(l)}]\)呢？

首先，\(\mathbb{E}_{x,y}\)指的是对所有参与评测的点集\(x,y\)的期望；其次，\(\mathbb{E}_\mathcal{D}\)指的是对于『造成训练结果产生差异的随机因素』取期望，下标定义了哪些是随机变量，哪些不是。

希望我解释得够清楚:)

Optimism of the Training Error Rate

现在我们来重新定义一个新的衡量Training Error的指标：

\[\begin{equation} \label{eq:extra-sample-err} \operatorname{Err}_\mathcal{D} = \mathbb{E}_{X^0, Y^0}[L(Y^0, \hat{f}(X^0))] \end{equation}\]

其中\(\hat{f}(\cdot)\)是通过一个特定的训练集\(\mathcal{D}_\tau\)训练得到的。\((X^0, Y^0)\)是新的（从\(P(X,Y)\)中sample出来的）test data，并不包含在训练集中。这个error被称为『extra-sample error』，同(\(\ref{eq:loss-function}\))式明显的不同点在于，extra-sample error不再拿训练数据做评测。如果对训练集取期望，就得到

\[\begin{equation} \label{eq:expected-extra-sample-err} \operatorname{Err} = \mathbb{E}_\mathcal{D} \mathbb{E}_{X^0, Y^0}[L(Y^0, \hat{f}(X^0))] \end{equation}\]

(\(\ref{eq:expected-extra-sample-err}\))式是我们评测模型优劣的终极指标，如果要给个名字，不妨称其为『expected extra-sample error』吧。这个指标average了training set和test set，很多其他常用的指标都是以尽可能好地近似(\(\ref{eq:expected-extra-sample-err}\))式为目标的。

现在我们再来看一个最土的error：

\[\begin{equation} \label{eq:training-err} \overline{\operatorname{err}} = \frac{1}{N} \sum_{i=1}^N L(y_i, \hat{f}(x_i)) \end{equation}\]

这就是在训练集上对训练误差取平均，被称为『training error』。由于一个定义在测试集上，一个定义在训练集上，因此显然\(\overline{\operatorname{err}}\)一定比\(\operatorname{Err}_\mathcal{D}\)小。由于extra-sample error通常不容易估计（因为需要一个test set），我们再定义一个新的error指标：

\[\begin{equation} \label{eq:in-sample-err} \operatorname{Err}_{in} = \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{Y^0} [L(Y_i^0, \hat{f}(x_i))] \end{equation}\]

这回又得仔细定义一下哪些是随机变量，哪些不是。上式仍然假定\(\hat{f}(\cdot)\)是通过特定的训练集\(\mathcal{D}_\tau\)习得，\(x_i\)均来自训练集，但\(Y_i^0\)表示对每一个\(x_i\)，观测到新的响应（通过\(Y_i^0 = f(x_i) + \epsilon\)）。因此这些\(Y_i^0\)和训练集中的\(y_i\)可能就不一样了。我们把这一指标称作『in-sample error』，因为这个指标仍然是定义在训练集上的。很显然这个指标也一定大于\(\overline{\operatorname{err}}\)

好了，现在终于可以引出optimism的定义了：

\[\begin{equation} \label{eq:optimism} \begin{split} \operatorname{op} &\equiv \operatorname{Err}_{in} - \overline{\operatorname{err}} \\ &= \frac{1}{N} \sum_{i=1}^N \left( \mathbb{E}_{Y^0} [L(Y_i^0, \hat{f}(x_i))] - L(y_i, \hat{f}(x_i) \right) \end{split} \end{equation}\]

注意\(\hat{f}(\cdot)\)是一个和训练集\(\mathcal{D}\)相关的随机变量，如之前一贯的做法，我们对训练集取期望。但是和(\(\ref{eq:in-sample-err}\))式对\(\operatorname{Err}_{in}\)的定义保持一致，在这里我们认为训练集本身，即\(x_i\)，是固定的，而训练集的输出\(y_i\)存在随机因素，于是对训练集取期望实际是对训练集中的\(y\)取期望。定义：

\[\omega \equiv \mathbb{E}_y(\operatorname{op})\]

如果使用squared loss function，可以证明：

\[\begin{align*} \omega &= \frac{1}{N}\sum_{i=1}^N \left ( \mathbb{E}_y \mathbb{E}_{Y^0} [(Y_i^0 - \hat{y}_i)^2] - \mathbb{E}_y [(y_i - \hat{y}_i)^2] \right ) \\ &= \frac{1}{N}\sum_{i=1}^N \left ( \mathbb{E}_y \mathbb{E}_{Y^0}[(Y_i^0)^2 - 2Y_i^0 \hat{y}_i + \hat{y}_i^2] - \mathbb{E}_y [y_i^2 - 2y_i\hat{y}_i + \hat{y}_i^2] \right ) \\ &= \frac{1}{N}\sum_{i=1}^N \left ( \mathbb{E}_{Y^0}[(Y_i^0)^2] - 2\mathbb{E}_{Y^0}[Y_i^0] \mathbb{E}_y [\hat{y}_i] + \mathbb{E}_y\hat{y}_i^2 - \mathbb{E}_y y_i^2 + 2 \mathbb{E}_y [y_i \hat{y}_i] - \mathbb{E}_y \hat{y}_i^2 \right ) \\ &= \frac{1}{N}\sum_{i=1}^N \left ( \mathbb{E}_{Y^0}[(Y_i^0)^2] - \mathbb{E}_y y_i^2 + 2\mathbb{E}_y[y_i \hat{y}_i] - 2\mathbb{E}_{Y^0}[Y_i^0] \mathbb{E}_y [\hat{y}_i] \right ) \\ &= \frac{2}{N}\sum_{i=1}^N \left ( \mathbb{E}[y_i \hat{y}_i] - \mathbb{E}[y_i] \mathbb{E}[\hat{y}_i] \right) \\ &= \frac{2}{N} \sum_{i=1}^N \mathbb{Cov} (\hat{y}_i, y_i) \end{align*}\]

这样就得到了书上的结论。其中\(y_i\)是一个随机变量是因为我们之前假设了训练集的随机因素来自于其输出\(y_i\)，而\(\mathbb{E}_{Y^0}[Y_i^0]\)和\(\mathbb{E}_y[y_i]\)相等是因为它们来自同一个分布（\(y_i\)是训练集中的值，\(Y_i^0\)是用相同的\(x_i\)重新sample出来的新值）。

我把这个重要关系抄一下：

\[\begin{equation} \label{eq:in-sample-relation} \mathbb{E}_y(\operatorname{Err}_{in})=\mathbb{E}_y(\overline{\operatorname{err}}) + \frac{2}{N} \sum_{i=1}^N \mathbb{Cov} (\hat{y}_i, y_i) \end{equation}\]

\(C_p\)和AIC

书上表示，对于一些简单情况，可以证明：

\[\begin{equation} \label{eq:cov-relation} \sum_{i=1}^N \mathbb{Cov} (\hat{y}_i, y_i) = d\sigma_{\epsilon}^2 \end{equation}\]

\(d\)是数据的维数。用原文的话说，这个关系holds exactly for linear models with additive errors and squared error loss, and approximately for linear models and log-likelihoods. In particular the formula does not hold in general for 0-1 loss (Efron, 1986), although many authors nevertheless use it in that context. 我自己试证了一下，没有证出来，回头再来补吧。

我们无法得知训练集的精确期望，只能估计(\(\ref{eq:in-sample-relation}\))式，于是引出了\(C_p\)统计量的定义：

\[C_p = \overline{\operatorname{err}} + 2\cdot \frac{d}{N}\hat{\sigma_\epsilon}^2\]

其中\(\hat{\sigma_\epsilon}^2\)是对\(\sigma_\epsilon^2\)的估计，可以通过\(\frac{1}{N}\|y_i - \hat{f}(x_i) \|_2^2\)得到。

AIC是一个基于log-likelihood loss function的更一般的统计量，在一些特殊分布的情况下和\(C_p\)有相同的形式。AIC的定义式如下

\[\operatorname{AIC} = -\operatorname{loglik} + 2d\]

其中\(\operatorname{loglik}=\sum_{i=1}^N \log P_{\hat{\theta}}(y_i)\)是对似然函数的最大估计。这两个指标刻画了in-sample optimism，\(C_p\)和AIC越小，说明bias-variance的trade-off做得越好。

重访自由度

在第五章中（可参看书上5.14式，以及我之前对第五章的笔记）我们知道，若有\(\hat{\mathbf{y}} = S\mathbf{y}\)，那么我们可以定义模型的自由度

\[\operatorname{df} = \operatorname{trace}(S)\]

对于additive-error model \(Y=f(X) +\epsilon\)，根据(\(\ref{eq:cov-relation}\))式，可以得到

\[\operatorname{df} = \frac{\sum_{i=1}^N \mathbb{Cov}(\hat{y}_i, y_i)}{\sigma_{\epsilon}^2}\]

（数据维数\(d\)可以看作自由度）这样我们就得到了自由度更一般的定义。