模型评估与选择

1 统计学习三要素

方法 = 模型 + 策略 + 算法
模型：若假设空间以 $F$ 表示，决策函数(或假设)以 $f$ 表示，则 $F$ = { $f$ | $Y = f(X)$ }

其中 $Y$ 称为标记空间(或输出空间)， $X$ 称为样例集合
- 如果模型由参数控制，则又将假设空间称为参数空间
  
  $F$ = { $f|Y = f_\theta(X), \theta \in R^n$ }
  
  例如条件概率模型：
  
  $F$ = { $P|P(Y|X)$ }或 $F$ = { $P|P_\theta(Y|X), \theta \in R^n$ }

策略：通过训练获得优秀模型的准则
- 损失函数：以决策函数 $f$ 映射得到的输出值 $\hat Y$ 与真实值 $Y$ 的差距作为自变量的函数
  1. 0-1损失
    $L(Y,f(X)) = \left\{\begin{array}{rcl}1, Y \not = f(X) \\0, Y = f(X)\end{array}\right.$
  2. 平方损失函数
    $L(Y,f(X)) = (Y - f(X))^2$
  3. 绝对损失函数
    $L(Y,f(X)) = |Y - f(X)|$
  4. 对数损失函数
    $L(Y,P(Y|X)) = -logP(Y|X)$
  5. 风险函数（期望损失）：将模型的输入和输出（X,Y）视为随机变量，考虑其联合分布P(X,Y)
    $R_{exp}(f) = E_p[L(Y,f(X))] = \int_{x,y}L(y,f(x))P(x,y)dxdy$
    - 机器学习的目的是使得期望风险最小化，即
      $f^* = argminR_{exp}(f)$
    - 在 $p(x,y)$ 未知的情况下，将训练数据 $D$ = { $(x1,y1),(x2,y2),...,(x_N,y_N)$ }视为从 $(X,Y)$ 总体中抽取的一个样本，得到如下离散分布(经验分布)：
      
      $(X',Y')$ $(x1,y1)$ $(x2,y2)$ ... $(x_N,y_N)$
      
      $P$ $\frac{1}{N}$ $\frac{1}{N}$ $\frac{1}{N}$
      
      由此导出经验风险(ER)
      $R_{emp}(f) = \frac{1}{N}\Sigma_{i = 1}^{N}L(y_i,f(x_i))$
    - 经验风险最小化(ER):
      $f^*(D_N) = argmin_{f \in F}L(f,D_N) = argmin_{f \in F}\frac{1}{N}L(y_i,f(x_i))$
    - 结构风险(SR):
      $R_{sr}(f) = \frac{1}{N}\Sigma_{i = 1}^NL(y_i,f(x_i)) + \lambda J(f)$
      在有限的训练数据上用经验风险估计期望风险并不理想，需要对经验风险作一定的矫正
      
      $J(f)$ 表示模型的复杂度， $f$ 越简单，复杂度 $J(f)$ 就越小
    - 结构风险最小化
      $f^*(D_N) = argmin_{f\in F}L(f,D_N) = argmin\frac{1}{N}\Sigma_{i = 1}^NL(y_i,f(x_i)) + \lambda J(f)$
    - 定理：在二分类问题中，最优的决策函数 $f^*$ 的形式是由后验概率 $\eta(x)$ 定义的,即
      
      对任意的 $f: X \rightarrow Y$
      $R(f)-R(f^*) = E(\mathbb I[f(X) \not =f^*(X)]|2\eta(x) - 1|)$
      
      对于二分类问题 $Y$ = {0,1}, 假设 $(X,Y)$ 的联合分布由 $(\mu,\eta)$ 表示
      
      其中 $\mu$ 是 $X$ 的边缘分布， $\eta$ 是 $Y$ 的条件分布， $\eta(X) = P(Y = 1|X)$
      
      损失函数 $L(Y,f(X)) = \mathbb I[Y \not = f(X)]$
      
      于是可计算任何一个可测函数 $f$ 的风险
      $R(f) = EL(Y,f(X)) = P[Y \not = f(X)]$
      定义 $R^*$ 为最优风险， $R^* = argmin_fR(f)$
      
      定义使得风险最优的决策函数 $f^*$ （此处为后验概率）
      $f^*(X) = \left\{ \begin{array}{l} 1, \eta(X) = P(Y = 1|X) \geq 1/2 \\ 0, otherwise \end{array} \right.$
      证明：
      $\begin{array}{l}R(f) - R(f^*) \\= P[Y \not = f(X)] - P[Y \not = f^*(X)] \\= E_{X,Y}[\mathbb I[f(X) \not = Y]-\mathbb I[f^*(X)\not = Y]] \\= E_{X,Y}\{\mathbb I[f(X) \not = f^*(X)](\mathbb I[f(X) \not = Y]-\mathbb I[f^*(X)\not = Y]) \} \\= E_{X,Y}\{\mathbb I[f(X) \not = f^*(X)](\mathbb I[f(X) \not = Y] - (1 - \mathbb I[f^*(X) = Y])) \}\\= E_{X,Y}\{\mathbb I[f(X) \not = f^*(X)](2 \mathbb I[f^*(X) = Y] - 1) \} \\= E_{X}\{\mathbb I[f(X) \not = f^*(X)](2 E_{Y|X}\mathbb I[f^*(X) = Y] - 1) \} \\= E_{X}\{\mathbb I[f(X) \not = f^*(X)](2(\mathbb I[f^*(X) = 1]P(Y = 1|X)+ \mathbb I(f^*(X) = 0)P(Y = 0|X)-1)\} \\= E_{X}\{\mathbb I[f(X) \not = f^*(X)](2(\mathbb I[f^*(X) = 1]\eta(X)+ \mathbb I[f^*(X) = 0][1-\eta(X)]\}\\= E_{X}\{\mathbb I[f(X) \not = f^*(X)](2 (1/2 + |\eta(x)-1/2|) - 1) \} \\= E_{X}\mathbb[f(X) \not = f^*(X)](|2\eta(x)-1|)\end{array}$

$(X',Y')$	$(x1,y1)$	$(x2,y2)$	...	$(x_N,y_N)$
$P$	$\frac{1}{N}$	$\frac{1}{N}$		$\frac{1}{N}$

算法：学习模型的具体计算方法，例如将统计学习问题归结为最优化问题，以及梯度学习算法，深度学习算法
1. 如果最优化问题有显示解析解，则直接进行求解
2. 如果没有显示解，则应当考虑如何保证解的全局最优与高效性

2 经验误差与过拟合

假设机器学习模型为 $Y = \hat f(x)$

训练误差（training error）：在训练集上预测的结果与训练集的真实结果的差异，也称为经验误差（empirical error）
$R_{emp}(\hat f) = \frac{1}{N}\Sigma_{i=1}^NL(y_i,\hat f(x_i))$

训练误差率：分类错误的样本数 $a$ 占训练样本总数 $N$ 的比例， $1 - E$ 称为精度
$E = \frac{a}{N}$

泛化误差(genenralized error)：测试集或新样本上的预测误差
$R_{test} = \frac{1}{N_{test}}\Sigma_{i=1}^{N_{test}}L(y_i,\hat f(x_i))$

由于既没必要再拿新样本进行泛化误差计算，也不能仅依靠经验误差去估计泛化误差，那么可以从训练样本中取出部分作为新样本，并用这些样本计算出来的误差作为泛化误差的近似。这组样本被称为“测试集”，测试集上的误差称为测试误差。

2.1 留出法（hold-out）

将数据集 $D$ 划分为训练集 $S$ 和测试集 $T$ ， $D = S \cup T, S\cap T = \empty$ . 记样本量为 $N_T$ ,泛化误差表示为：
$\hat R_{test}^{HO} = \frac{1}{N_T}\Sigma_{x_i\in T}L(y_i,\hat f(x_i))$

要有足够的样本量以保证训练模型的效果
在划分时要保证数据分布的一致性，如果样本中正例和反例的比例为2:3，则训练集和测试集中的正例和反例的比例也为2:3
为降低随机划分的影响，应重复划分训练集和测试集，对得到的多次结果取平均作为最终结果
优点：打破了基于相同的数据进行训练和测试的分析，避免了训练和测试数据重叠引起的过拟合
缺点：过分依赖于某一次数据划分，划分方式直接影响着估计的精度，经验上按照1:2与1:4的比例划分测试集与训练集

2.2 交叉验证法（cross validation）

将数据划分为k个大小相似的互斥子集， $D = D_1 \cup ...\cup D_k, D_i \cap D_j = \empty, i \not = j$ ,分多次进行Hold-out

留p交叉验证估计（leave-p-out）

从 $D$ 中取 $p$ 个样例作为测试集，最多有 $C_{N}^{p}$ 种取法， $p = 1,...,N-1$ . 假设有放回地抽取/划分数据集 $C_{N}^{p}$ 次，每次测试集样本量均为 $p$ ，则留 $p$ 交叉验证泛化误差估计为
$\hat R_{test}^{LPO}(\hat f) = \frac{1}{C_{N}^{p}}\Sigma_{k=1}^{C_{N}^{p}}\frac{1}{p}\Sigma_{x_i \in T_k}L(y_i,\hat f(x_i))\\$
- 优点：留p交叉验证比多次留出给出的交叉验证的划分组合数从 $\Sigma_{p=1}^{N-1}C_{N}^{p}$ 减少到 $C_{N}^{p}$
- 缺点：对较大的样本量N，组合数计算复杂度 $C_N^p$ 仍然很大
- $p=1$ 时为留一交叉验证（leave-one-out）

RLT Repeated learning-testing

RLT只基于部分数据划分进行，选择任意大于0的K次数据划分进行泛化误差估计
- 优点：有可接受的计算开销且操作简单
- 缺点：K的大小的选择一直是这个方法的最大问题，不同文献有不同的结论，Nadeau和Bengio建议K = 15，训练和测试集的比例选择也没有一个确定的结论