#!/usr/bin/env python
# coding: utf-8

# # 第九讲：经验风险最小化
# 
# # 第六部分：学习理论（Learning Theory）
# 
# ## 1. 偏差/方差权衡（Bias/variance tradeoff）
# 
# 最早在我们学习线性回归的时候，我们就进行了关于选择拟合一个简单模型（如$y=\theta_0+\theta_1x$），还是选择拟合一个复杂模型（$y=\theta_0+\theta_1x+\cdots+\theta_5x^5$）的讨论，仍旧是这幅图：
# 
# <img src="./resource/chapter09_image01.png" width="800" alt="" align=center />
# 
# 结果发现，拟合一个五阶多项式（右图）并不是一个好的选择。而且，尽管这个五阶多项式在对训练集中的样本特征$x$（比如实用面积）做出预测$y$（比如公寓租金）时做的非常好，我们也并不看好它对不再训练集中样本的预测结果。换句话说，模型从训练集中学到的知识并不能很好的*泛化（generalize）*到其他房屋租赁样本中。我们说一个假设的**泛化误差（generalization error）**就是指该假设对于不在训练集中样本预测的期望误差（我们在后面会给出正式的定义）。
# 
# 最左和最右的图片都存在较大的泛化误差，但是这两个模型的问题却并不相同。如果$y$与$x$并不是线性关系，那么如果我们使用线性模型去拟合训练集，即使训练集很大，线性模型也不能精确的捕捉到数据的结构特征。非正式的定义模型的**偏差（bias）**：即模型的预测值与样本实际值之间的差距，偏差越大则约偏离真实数据，即使拟合的训练集很大（如无限的训练集）。因此，对于左图，其线性模可能型存在欠拟合问题（即不能捕捉到数据呈现出的特征）。
# 
# 除了偏差，泛化误差还有另一个组成部分——模型拟合过程的**方差（variance）**。比如右图中的五阶多项式，这个模型很有可能只反映出了我们这个有限训练集中的数据特征，但并不能反映出不在训练集中的更广泛的$y$与$x$的关系。我们的训练集中可能存在比平均价格更高或更低的样本，于是当我们拟合这些“具有欺骗性的”数据时，也有可能得到一个泛化误差很大的模型。在这种情况下，我们称模型具有较大的方差，也就是预测值的变化范围或离散程度较大。（方差越大，数据分布越分散。在课程中我们不再给出关于偏差与方差的形式化定义，尽管这两个概念在诸如线性回归的算法中有明确定义，但在分类问题中这些概念的定义却有好几个不同的提议，而且尚未达成共识。）
# 
# 参见[Understanding the Bias-Variance Tradeoff](http://scott.fortmann-roe.com/docs/BiasVariance.html)：
# 
# <img src="./resource/chapter09_image02.png" width="500" alt="" align=center />
# 
# 通常，我摸在偏差与方差间都会做出权衡。如果我们的模型过于简单，只有很少的几个参数，那么它可能存在着较大的偏差（但是方差较小）；如果过于复杂而含有非常多的参数，那么模型可能会存在较大的方差（但是偏差较小）。对于上面的这个例子，使用二次函数拟合的效果优于一阶或五阶多项式。
# 
# ## 2. 序言
# 
# 本节我们会对学习理论有一个大致了解，除了启发和深入理解机器学习，这部分讨论还将加强我们对学习理论直观概念，也会介绍一些学习算法在不同设置下最佳应用的经验。同时还将尝试解答这几个问题：
# * 首先，我们能否形式化偏差与方差间的权衡过程？
# 
#     这个问题也将引出关于模型选择方法的讨论，比如算法自动确定使用几阶多项式进行拟合。
# * 其次，在机器学习中我们真正关心的是模型的泛化误差，但是大多数学习算法只对训练集做拟合，那么我们如何从“对训练集有着很好拟合的模型”中得知它的泛化误差？
# 
#     我们尤其想知道，能否将“模型关于训练集的误差”同“模型的泛化误差”联系起来？
# * 最后一个问题，是否存在能够证明学习算法将会有效的条件？
# 
# 我们从两个非常有用的引理说起：
# 
# **引理**，联合界（the union bound）：令$A_1,A_2,\cdots,A_k$为$k$个不同的事件（并不要求独立），则有：
# 
# $$
# P(A_1\cup\cdots\cup A_k)\leq P(A_1)+\cdots+P(A_k)
# $$
# 
# 在概率论中，联合界通常当做公理来使用（所以我们不会尝试证明这个式子），不过它很符合直觉：$k$个事件中任意一些事件发生的概率至多为这$k$个事件各自发生的概率之和（用文氏图表示更加自然）。
# 
# （在符号的使用习惯上，如果我们对符号$a$加上了$\hat a$，则这个“帽子”符号通常表示对原符号的估计，比如后面的$\hat\varepsilon$就是用来近似估计泛化误差$\varepsilon$，而后面的$\hat h$就是对真正的假设函数$h$的估计。）
# 
# **引理**，霍夫丁不等式（Hoeffding inequality），$Z_1,\cdots,Z_m$是服从$\mathrm{Bernoulli}(\phi)$的独立同分布（IID）的随机变量，即$P(Z_i=1)=\phi,P(Z_i=0)=1-\phi$。令$\hat\phi=\frac{1}{m}\displaystyle\sum_{i=1}^mZ_i$，这是一个通过变量均值去估计变量期望的量，再令$\gamma\gt0$，则有：
# 
# $$
# P\left(\lvert\phi-\hat\phi\rvert\gt\gamma\right)\leq2\exp\left(-2\gamma^2m\right)
# $$
# 
# 这个引理（在机器学习中也叫作切诺夫界，Chernoff bound）告诉我们，如果用$\hat\phi$（即$m$个服从$\mathrm{Bernoulli}(\phi)$的随机变量的平均值）作为参数$\phi$的估计，那么若$m$越大，则我们离参数实际值越接近。也就是说，假设有一枚不均匀的硬币，掷这枚硬币面朝上的概率为$\phi$，如果我们掷$m$次硬币，然后计算面朝上的比例，那么掷的次数越多，则这个比例作为参数$\phi$估计的可信度越高。
# 
# 仅通过这两个引理，我们就可以推导出一些关于学习理论的深层次的至关重要的结论。
# 
# 为了使后面的论述更简洁，我们先将注意力限定在$y\in\{0,1\}$的二元分类问题上。我们在这里讨论的结论都可以推广到包括回归、多元分类等问题中。
# 
# 假设有一组大小为$m$的训练集$S=\left\{\left(x^{(i)},y^{(i)}\right);i=1,\cdots,m\right\}$，其中的样本$\left(x^{(i)},y^{(i)}\right)$服从某个独立同分布的概率分布$\mathcal{D}$。对于假设函数$h$，我们定义**训练误差（training error）**（在学习理论中也称为**经验风险（empirical risk）**或**经验误差（empirical error）**）为：
# 
# $$
# \hat\varepsilon(h)=\frac{1}{m}\sum_{i=1}^m1\left\{h\left(x^{(i)}\right)\neq y^{(i)}\right\}
# $$
# 
# 其实就是$h$对训练集误分类的比例。如果想要明确表示$\hat\varepsilon(h)$是基于训练集$S$的，那么可以写作$\hat\varepsilon_S(h)$。我们定义泛化误差为：
# 
# $$
# \varepsilon(h)=P_{(x,y)\sim\mathcal{D}}(h(x)\neq y)
# $$
# 
# 这个式子表示，如果从分布$\mathcal{D}$中再取出一个新的样本$(x,y)$，$h$会将其误分类的概率。
# 
# 应该留意的是，我们一直假设训数据是从分布$\mathcal{D}$中取出的，而分布$\mathcal{D}$正是我们将要（通过泛化误差定义式）用假设函数$h$评估的对象。这也有时候会作为**PAC**假设中的一条。（PAC是probably approximately correct的缩写，通常译为可能近似正确，它是学习理论已经证明的一套理论框架中的一些列假设。其中最重要的是关于同一个分布的训练以及测试的假设，以及关于独立抽取训练样本的假设。）
# 
# 考虑线性分类的设置，令$h_\theta(x)=1\left\{\theta^Tx\geq0\right\}$，那么用什么方法拟合参数$\theta$比较合理呢？其中一种实现是通过最小化训练误差得到：
# 
# $$
# \hat\theta=\mathrm{arg}\operatorname*{max}_{\theta}\hat\varepsilon(h_\theta)
# $$
# 
# 我们称这个算法为**经验风险最小化（ERM: empirical risk minimization）**，而由学习算法得出的假设函数为$\hat h=h_{\hat\theta}$。经验风险最小化通常被认为是最基础的学习算法，它也是本节关注的焦点算法。（ERM本身是一个非凸优化问题，诸如逻辑回归和支持向量机等算法也可以被看做是一种凸性近似的经验风险最小化算法。）
# 
# 在深入学习理论的过程中，我们要学会不纠结于假设某些特定的参数化法或该不该使用线性分类器等问题。对于本讲要证明的结论来说，我们不再把学习算法当做是一组参数的选取过程，而应该把它当做是选择一个函数的过程。定义学**假设类（hypothesis class）$\mathcal{H}$**是所有分类器的集合，而我们的学习算法会从中选择分类器。对于线性分类器，$\mathcal{H}=\left\{h_\theta:h_\theta(x)=1\left\{\theta^Tx\geq0\right\},\theta\in\mathbb{R}^{n+1}\right\}$是所有判别边界是线性的分类器集合，其中的每一个成员$h_\theta$都是从$\mathcal{X}$（输入域）到$\{0,1\}$的函数。更广泛的，比如我们在学习神经网络，则我们可以令$\mathcal{H}$为表示神经网络架构的所有分类器的集合。
# 
# 现在可以将经验风险最小化看做是一类函数$\mathcal{H}$中的一个最小化函数，算法将在这一类函数中选择一个假设：
# 
# $$
# \hat h=\mathrm{arg}\operatorname*{min}_{h\in\mathcal{H}}\hat\varepsilon(h)
# $$
# 
# （这里给出的$\hat h$与前面的$\hat\theta$是等价的，只是不同思路下的不同表达。）
# 
# ## 3. 若$\mathcal{H}$是有限的
# 
# 我们从一个具有“由$k$个假设构成的有限假设类$\mathcal{H}=\{h_1,\cdots,h_k\}$”的学习问题开始讲起。因此$\mathcal{H}$只是$k$个从$\mathcal{X}$映射到$\{0,1\}$的函数组成的集合，而经验风险最小化将从这$k$个函数中选择训练误差最小的一个。
# 
# 我们想要给$h$的泛化误差加上保证条件，分为两步：
# * 我们先要证明对于所有$h$，都有$\hat\varepsilon(h)$（训练误差）是$\varepsilon(h)$（泛化误差）的可靠估计（这样我们就可以通过降低训练误差来减小泛化误差了）；
# * 接下来证明$\hat h$的泛化误差存在一个上界。
# 
# 假设我们从中选了$h_i\in\mathcal{H}$，考虑一个如下定义的伯努利随机变量$Z$：抽取样本$(x,y)\sim\mathcal{D}$，然后令$Z=1\left\{h_i(x)\neq y\right\}$，即抽取一个样本，然后用$Z$来表示$h_i$是否误分类了样本，同样的有$Z_j=1\left\{h_i\left(x^{(j)}\right)\neq y^{(i)}\right\}$，即$h_i$是否误分类了第$i$个样本（很明显$Z_j\in\{0,1\}$是一个伯努利分布，根据泛化误差的定义有$P(Z_j=1)=\varepsilon(h_i)$，其期望由$h_i$的泛化误差给出）。由于我们的训练集是$\mathcal{D}$上的独立同分布，所以$Z$和$Z_j$具有相同的分布。
# 
# 可以看出对于随机抽取的样本，被误分类的概率为$\varepsilon$（这正是$Z$和$Z_j$的预期值）。而且，训练误差可以写作：
# 
# $$
# \hat\varepsilon(h_i)=\frac{1}{m}\sum_{i=1}^mZ_j
# $$
# 
# $h_i$的训练误差$\hat\varepsilon(h_i)$就是$m$个随机变量$Z_j$的平均值，它们是从伯努利分布中抽取的期望为$\varepsilon(h_i)$的独立同分布的随机变量。带入霍夫丁不等式有：
# 
# $$
# P\left(\left\lvert \varepsilon(h_i)-\hat\varepsilon(h_i)\right\rvert\gt\gamma\right)\leq2\exp\left(-2\gamma^2m\right)
# $$
# 
# 这表明对于我们选择的特定$h_i$，当$m$足够大时，训练误差与泛化误差非常接近的概率也会变大。不过我们不仅仅想保证这个特定的$h_i$下$\varepsilon(h_i)$与$\hat\varepsilon(h_i)$（很大概率）非常接近，我们想要证明这对所有的$h\in\mathcal{H}$同时成立。
# 
# 将事件$\left\lvert \varepsilon(h_i)-\hat\varepsilon(h_i)\right\rvert\gt\gamma$记为$A_i$，我们已经证明了对任意$A_i$都有$P(A_i)\leq2\exp\left(-2\gamma^2m\right)$。因此，使用联合界有：
# 
# $$
# \begin{align}
# P\left(\exists h\in\mathcal{H}.\ \left\lvert\varepsilon(h_i)-\hat\varepsilon(h_i)\right\rvert\gt\gamma\right)&=P\left(A_1\cup\cdots\cup A_k\right)\\
# &\leq\sum_{i=1}^kP(A_i)\\
# &\leq\sum_{i=1}^k2\exp\left(-2\gamma^2m\right)\\
# &=2k\exp\left(-2\gamma^2m\right)
# \end{align}
# $$
# 
# （第一个等式左边为“$\mathcal{H}$中存在某函数$h_i$使得其泛化误差与训练误差的差值大于$\gamma$”的概率。）
# 
# 同时用$1$减去不等式两边的量：
# 
# $$
# \begin{align}
# P\left(\lnot\exists h\in\mathcal{H}.\ \left\lvert\varepsilon(h_i)-\hat\varepsilon(h_i)\right\rvert\gt\gamma\right)&=P\left(\forall h\in\mathcal{H},\ \left\lvert\varepsilon(h_i)-\hat\varepsilon(h_i)\right\rvert\leq\gamma\right)\\
# &\geq1-2k\exp\left(-2\gamma^2m\right)
# \end{align}
# $$
# 
# （$\lnot$表示“逻辑否”，即事件“$\mathcal{H}$中不存在某函数$h_i$使得其泛化误差与训练误差的差值大于$\gamma$”，也就是事件“$\mathcal{H}$中任意函数$h_i$使得其泛化误差与训练误差的差值不大于$\gamma$”。）也就是说，对于所有$h\in\mathcal{H}$，有$\varepsilon(h)$与$\hat\varepsilon(h)$之间的差值小于$\gamma$的概率至少为$1-2k\exp\left(-2\gamma^2m\right)$，也叫作*一致收敛（uniform convergence）*结果，因为这是所有$h\in\mathcal{H}$同时成立的界限（一致收敛暗示了当$m$很大时，$\mathcal{H}$中所有的$\hat\varepsilon(h_i)$都将同时收敛于$\varepsilon(h_i)$，此时训练误差将会非常接近泛化误差 ）。
# 
# 上面的计算结果指出，给定的$m,\gamma$将会确定事件“对于某些$h\in\mathcal{H},\ \left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\gt\gamma$”发生概率的界限。这里涉及三个值$m,\gamma$以及误差的概率。于是，我们就可以利用任意两个值确定第三个值的界限。
# 
# * 比如，对于给定的$\gamma$和某个$\delta\gt0$，$m$至少得取多大才能保证事件“训练误差与泛化误差之差在$\gamma$以内”的概率至少为$1-\delta$？可以令$\delta=2k\exp\left(-2\gamma^2m\right)$然后解出$m$，那么如果$m\geq\frac{1}{2\gamma^2}\log\frac{2k}{\delta}$，则对于任意$h\in\mathcal{H}$，有事件“$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq\gamma$”发生的概率至少为$1-\delta$。（等价的有，对于某些$h\in\mathcal{H}$，事件$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\gt\gamma$发生的概率为至多为$\delta$）。这个界限指出了为了保证一个特定的误差，至少需要多少训练样本。对于给定的算法，为了保证特定的误差级别，所需要的训练集的大小$m$称为该算法的**样本复杂度界（sample complexity bound）**。
# 
#     这个界限的关键性质在于，算法为保证误差所需的训练集大小与$k$的对数相关，也就是$\mathcal{H}$中假设的个数的对数（$m$与$\log k$成正比，而$\log k$的增长速度是非常慢的。另外，从经验上讲，对数函数是增长速度最慢的函数之一，在计算机科学中通常有$\forall k,\ \log k\leq30$。也就是说，即使在假设类中增加很多假设，所需的样本也不会增加多少）。在后面的讲解中，这是一个很重要的性质。
# 
# * 类似的，我们也可以固定$m,\delta$的取值，从上面的等式中解出$\gamma$。如果要保证$1-\delta$的概率，在给定的训练集包含$m$个样本时，对于所有的$h\in\mathcal{H}$，有$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq\underbrace{\sqrt{\frac{1}{2m}\log\frac{2k}{\delta}}}_{\gamma}$。
# 
# 我们队第一部分的证明就到这里，可以看出训练误差一致收敛于泛化误差的可能性很高。接下来是第二部分的证明。
# 
# 现在，我们假设一致收敛已经确定，即对于所有$h\in\mathcal{H}$要使$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq\gamma$，我们能够证明哪些关于$\hat h$的泛化误差$\varepsilon(\hat h)$的结论？这里的$\hat h=\mathrm{arg}\displaystyle\operatorname*{min}_{h\in\mathcal{H}}\hat\varepsilon(h)$是经验风险最小化选取的假设。
# 
# 定义$h^*=\mathrm{arg}\displaystyle\operatorname*{min}_{h\in\mathcal{H}}\varepsilon(h)$为$\mathcal{H}$中最能够满足条件的假设函数。注意到$h^*$是我们能从$\mathcal{H}$中找到的最好的（泛化误差最小的）假设函数（也就是我们不可能在$\mathcal{H}$中找到比$h^*$做得更好的函数，那么用我们的算法与$h^*$作比较就具有了实际意义），所以，与$h^*$对比误差有：
# 
# $$
# \begin{align}
# \varepsilon(\hat h)&\leq\hat\varepsilon(\hat h)+\gamma\\
# &\leq\hat\varepsilon(h^*)+2\gamma\\
# &\leq\varepsilon(h^*)+2\gamma
# \end{align}
# $$
# 
# 第一个式子来自$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq\gamma$（一致收敛假设）。第二个式子中，$\hat h$是我们选来能够最小化$\hat\varepsilon(h)$的假设函数，那么对所有$h$都有$\hat\varepsilon(\hat h)\leq\hat\varepsilon(h)$，所以对特定的$h^*$也就有$\hat\varepsilon(\hat h)\leq\hat\varepsilon(h^*)$。第三个式子仍然使用一致收敛假设证明了$\hat\varepsilon(h^*)\leq\varepsilon(h^*)+\gamma$。于是，这个不等式证明：如果有一致收敛假设，则$\hat h$的泛化误差比至多比$\mathcal{H}$中最好的假设函数多$2\gamma$。
# 
# 把上面的推导总结在一个定理中：
# 
# **定理**，令$\lvert\mathcal{H}\rvert=k$，对于给定$m,\delta$，当事件“训练误差与泛化误差之差小于$\gamma$”的概率不小于$1-\delta$时，有：
# 
# $$
# \varepsilon(\hat h)\leq\underbrace{\left(\operatorname*{min}_{h\in\mathcal{H}}\varepsilon(h)\right)}_{\varepsilon(h^*)}+2\underbrace{\sqrt{\frac{1}{2m}\log\frac{2k}{\delta}}}_{\gamma}
# $$
# 
# 也就是将$\gamma$换成了根号项，用的是事件“训练误差与泛化误差之差小于$\gamma$”的概率不小于$1-\delta$下一致收敛时得到的结论。另外，需要注意这个结论也告诉我们$\varepsilon(h)$至多比$\varepsilon(h^*)=\displaystyle\operatorname*{min}_{h\in\mathcal{H}}\varepsilon(h)$大$2\gamma$。
# 
# 这同样也印证了前面关于模型选择时的偏差/方差权衡的讨论。比如，我们原有一个假设类$\mathcal{H}$，现在考虑换到另一个更大的假设类$\mathcal{H}'\supseteq\mathcal{H}$下（举个例子，我们原来的$\mathcal{H}$为所有线性函数的假设类，在加入了更多特征后有$\mathcal{H}'$为二次函数构成的假设类，而线性函数构成的假设类是二次函数构成的假设类的子集）。如果我们换到$\mathcal{H}'$（也就是二次函数假设类），则$\varepsilon(h^*)$将会减小（因为我们这次从一个更大的函数集合中选择最小化泛化误差的函数，所以能够得到的新函数，可能是个二次函数，一定不会被原来的函数效果差）。于是，非正式的说，通过学习使用更大的假设类，偏差可能就会降低。但是，如果$k$增大，$\gamma$项就会增大。于是，非正式的说，当我们选用更大的假设类时，方差也会随之上升。（整个过程说明，如果我们切换到一个更大的假设类中，那么我们得到一个使泛化误差更小的假设函数的希望就会增加，但代价是找到的函数不能精确拟合训练集的概率也会增加。我们可以非正式的将第一项对应为偏差，而将第二项对应为方差。）
# 
# 在给定$\gamma,\delta$的情况下，我们可以向前面一样解出$m$，从而得到样本复杂度界限：
# 
# **推论**，令$\lvert\mathcal{H}\rvert=k$，对于给定的$\gamma,\delta$，如果要保证$\varepsilon(\hat h)\leq\displaystyle\operatorname*{min}_{h\in\mathcal{H}}\varepsilon(h)+2\gamma$成立，并且在事件“训练误差与泛化误差之差小于$\gamma$”的概率至少为$1-\delta$时，需要满足：
# 
# $$
# \begin{align}
# m&\geq\frac{1}{2\gamma^2}\log\frac{2k}{\delta}\\
# &=O\left(\frac{1}{\gamma^2}\log\frac{k}{\delta}\right)
# \end{align}
# $$
# 
# 下一讲会将讨论$\mathcal{H}$是无限的情况，我们也会从上面这个式子开始说起。