Chapter 1 supervised learning formulations¶

1.1 supervised learning¶

假设我们有一个样本空间 $\mathcal{X}$，以及这些样本对应的标签构成的输出空间 $\mathcal{Y}$，我们希望找到一个映射 $h$，将这些样本正确的映射到他们的标签上，这就是监督学习的主要目的。自然地，我们要评价这个映射的好坏，于是引入了损失函数$l:\mathcal{Y} \times \mathcal{Y} \to \mathbb{R}$。损失函数是针对一个映射在某一对标签上定义的，也就是说，对于一个模型（也就是我们考虑的映射），我们的的损失函数的值可以这样表示$l(h(x), y)$，然后注意我们考虑的是这个模型对整体的样本的效果，所以我们需要统计损失函数在整个样本空间上的期望，我们称之为期望损失（expected loss / expected risk）： $$ L(h) \triangleq\mathbb{E}_{(x,y) \sim P}[l(h(x),y)] \tag{1.1} $$

1.1.1 Hypothesis class¶

现在我们考虑一个问题，在我们上面给出的期望损失计算的前提下，我们是否能够训练出一个映射$h$，使得$L(h)$的值为0？答案是基本不太可能，因为要能够描述一个函数，我们往往需要一些参数，一般参数越多，优化（或者说训练）这些参数计算量越大，在我们现有的计算能力内，无法去优化有近乎无穷个参数的函数，这意味着我们没法表示世界上所有的函数。所以我们把我们想要考虑的函数作为我们hypothesis class，比如 $\mathcal{H} = \left\{ h : h_\theta (x) = \theta^Tx,\theta \in \mathbb{R}^d\right\}$. 相应的，我们去修改我们上面定义的期望损失如下 $$ E(h) \triangleq L(h) - \inf_{g\in\mathcal{H}} L(g) $$

1.2 Empirical risk minimization¶

但是不管我们要计算的是$L(h)$还是$E(h)$，我们总是要能够计算$\mathbb{E}_{(x,y) \sim P}[l(h(x),y)]$，但是毕竟我们现实生活中想要解决的问题对应的概率分布$P$是连续的，而且常常是未知的，所以我们其实没有办法真的计算这个期望。那么学过统计学咱们就知道，我们也许可以通过抽样，得到这个值的一个良好近似。于是我们的思路就从这里出发，最直接的想法就是在我们的训练集上计算一个平均的损失，称之为empirical risk，用来替代expected loss $$ \hat{L}(h_\theta) \triangleq \frac{1}{n} \Sigma_{i=1}^{n}l((h_\theta(x_i), y_i), \theta). \tag{1.2} $$ 那么empirical risk minimization 就是在假设类的范围内找到最优的那个$\theta$，让$\hat{L}(h_\theta)$的值最小。 $$ \theta = \arg\min_{\theta \in \Theta} \hat{L}(h_\theta) $$ 注意这里的$\Theta$对应的就是假设类中的参数的取值集合。

这当然是一个很直接的想法，但是这个想法是否合理呢？我们在学统计学的时候就已经学习过一些估计量的评价标准，比如无偏性。如果我们认为，我们在训练集中取出的样本点都是独立同分布的（$(x_i, y_i) \stackrel{\text{iid}}\sim P$），那么我们很容易得到这个估计是无偏的（提示：根据期望的线性以及独立同分布期望相同两个性质就能证明）

如果我们要维护我们的信仰，坚信这个empirical risk是一个好的估计，无偏性当然是一个很有力的证据。但是这还不够，如果一个估计量仅仅是无偏，但是相对于真实值可能波动很大的情况下（比如真实值为0，估计量有0.5的概率是100,0.5的该率是-100），那这个估计仍然是不太好的。所以我们要寻找更加有力的论证，很自然的想法就是证明这个估计量和我们真实值的差距能够被bound在一个固定的范围内，这就是我们接下来研究的关键。