一、第一篇 监督学习

第一章 统计学习及监督学习概论

定理1.1–泛化误差上界

• 泛化误差：（generalization error）

  若学习到的模型为 $\hat{f}$ ,则用这个模型对未知数据集预测的误差称为泛化误差，它表现的是模型对未知数据的预测能力,事实上泛化误差就是所学习到的模型的期望风险
  $$\begin{array}{rl}{R}_{\exp }(\hat{f})& =E_P[L(Y,\hat{f}(X))]\\ & ={\int }_{\mathcal{X}\times \mathcal{Y}}L(y,\hat{f}(x))P(x,y)\mathrm{d}x\mathrm{d}y\end{array}$$

• 期望风险：
  $$R(f)=E[L(Y,f(x))]$$

• 经验风险:
  $$\hat{R}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i))$$

• 泛化误差上界定理

  定理 $1.1$ (泛化误差上界) 对二类分类问题, 当假设空间是有限个函数的集合 F = { f 1 , f 2 , ⋯   , f d } \mathcal{F}=\left\{f_{1}, f_{2}, \cdots, f_{d}\right\} F={f1​,f2​,⋯,fd​} 时, 对任意一个函数 $f\in \mathcal{F}$, 至少以概率 $1-\delta ,0<\delta <1$, 以下 不等式成立:
  $$R(f)⩽\hat{R}(f)+\epsilon (d,N,\delta )$$
  其中,
  $$\epsilon (d,N,\delta )=\sqrt{\frac{1}{2N}\left(\log d+\log \frac{1}{\delta }\right)}$$
  d为假设空间中备选模型的数量，N为样本数量

• Hoeffiding不等式

  设有随机变量 $x_1,x_2,...,x_n$ 的独立随机变量序列，$S_n=\sum _{i=1}^N{x}_i$是独立随机变量之和，$E(S_n)=E(\sum _{i=1}^N{x}_i)$为随机变量和的期望,$x_i\in [a_i,b_i]$(x取值在$a_i$和$b_i$之间)，则对任意$t>0$,以下不等式成立
  $$P\left(S_n-E\left(S_n\right)⩾t\right)⩽e^{\left(\frac{-2t^2}{\sum _{i=1}^n{\left(b_i-ai\right)}^2}\right)}$$
  或者
  $$P\left(E\left(S_n\right)-S_n⩾t\right)⩽e^{\left(\frac{-2t^2}{\sum _{i=1}^n{\left(b_i-ai\right)}^2}\right)}$$
  在这里$(b_i-a_i{)}^2$可以看成是常数

---

二分类问题泛化误差上界定理证明

• 二分类问题，有随机变量 $x_1,x_2,...,x_n$ 的独立随机变量序列，$S_n=\sum _{i=1}^n{x}_i$,如果其损失函数取值区间为$[0,1]$,即$x_i\in [0,1]$, $\bar{X}$是独立变量的均值，即 $\bar{X}=\frac{S_n}{n}=\frac{1}{N}\sum _{i=1}^N{X}_i$，那么$E({\bar{X}}_n)=\frac{1}{n}E(S_n)$,则有以下公式成立
  $$P({\bar{X}}_n-E({\bar{X}}_n)\ge t)=P(\frac{S_n}{n}-\frac{E(S_n)}{n}\ge t)=P(S_n-E(S_n)\ge nt)$$
  那么根据Hodffding不等式
  $$\begin{array}{rl}P({\bar{X}}_n-E({\bar{X}}_n)\ge t)& =P(S_n-E(S_n)\ge nt)\\ & \le e^{\left(\frac{-2n^2{t}^2}{\sum _{i=1}^n{\left(b_i-ai\right)}^2}\right)}\end{array}$$
  因为$(b_i-a_i{)}^2$可看成常数（在这里是0）所以后面的小于等于实际上为$e^{-n}$阶，当n趋于无穷打时候，$e^{-n}$是趋于0的，即当样本量很大的时候，该随机变量均值到均值期望之间大于等于一个数（t）的概率是很小的（趋于0的）。

  从分类问题的模型假设空间$\mathcal{F}$( F = { f 1 , f 2 , ⋯   , f d } \mathcal{F}=\left\{f_{1}, f_{2}, \cdots, f_{d}\right\} F={f1​,f2​,⋯,fd​}是个有限集合)中任选一个备选模型f，其训练集经验风险为
  $$\hat{R}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i))$$
  测试集期望风险为：
  $$R(f)=E[L(Y,f(x))]$$
  则利用上面转换的公式，将 t 换成 $ϵ$ ,区间取值[a,b]换成[0,1],则幂函数上的指数变为$-\frac{2N^2{ϵ}^2}{N}=-2N{ϵ}^2$
  $$P(R(f)-\hat{R}(f)⩾\epsilon )⩽\exp \left(-2N{\epsilon }^2\right)$$
  上述公式为从假设空间中任选的一个模型，假设空间中共有d个备选模型，我们并不知道我们未来将要使用哪个模型，我们期望这d个备选模型在训练集上的经验风险$\hat{R}(f)$和测试集上的期望风险$R(f)$之间的差值都不打，即我们期望这两个风险之间的差值大于等于某个数（比如这里的$ϵ$,原则上这个数要足够小）的概率要非常低，即在假设空间中至少存在一个模型满足这个条件,用以下公式来表达：
  P ( ∃ f ∈ F : R ( f ) − R ^ ( f ) ⩾ ε ) = P ( ⋃ f ∈ F { R ( f ) − R ^ ( f ) ⩾ ε } ) ⩽ ∑ f ∈ F P ( R ( f ) − R ^ ( f ) ⩾ ε ) ⩽ d e ( − 2 N ε 2 ) \begin{aligned} P(\exists f \in \mathcal{F}: R(f)-\hat{R}(f) \geqslant \varepsilon) &=P ( \bigcup_{f \in \mathcal{F}}\{R(f)-\hat{R}(f) \geqslant \varepsilon\} ) \\ & \leqslant \sum_{f \in \mathcal{F}} P(R(f)-\hat{R}(f) \geqslant \varepsilon) \\ & \leqslant d e^{(-2 N \varepsilon^{2})} \end{aligned} P(∃f∈F:R(f)−R^(f)⩾ε)​=P(f∈F⋃​{R(f)−R^(f)⩾ε})⩽f∈F∑​P(R(f)−R^(f)⩾ε)⩽de(−2Nε2)​
  这样我们考虑对立事件就是：任取一个模型，两个风险之间的差值都要以一个很大的概率小于某一个足够小的数$ϵ$

  ,等价的, 对任意 $f\in \mathcal{F}$, 有
  $$P(\forall f\in \mathcal{F}：R(f)-\hat{R}(f)<\epsilon )⩾1-d\exp \left(-2N{\epsilon }^2\right)$$
  令
  $$\delta =d{e}^{(-2N{\epsilon }^2)}$$
  则
  $$P(R(f)<\hat{R}(f)+\epsilon )⩾1-\delta$$
  即至少以概率 $1-\delta$ 有 $R(f)<\hat{R}(f)+\epsilon$

  其中
  $$\begin{array}{rl}\delta & =d{e}^{(-2N{ϵ}^2)}\\ \ln \delta & =\ln d-2N{ϵ}^2\\ 2N{ϵ}^2& =\ln d-\ln n\\ 2N{ϵ}^2& =\ln d+\ln \frac{1}{\delta }\\ ϵ& =\sqrt{\frac{1}{2N}\left(\log d+\log \frac{1}{\delta }\right)}\end{array}$$

以上讨论的只是假设空间包含有限个函数情况下的泛化误差上界，对一半的假设空间要找到泛化误差界就没有那么简单了

---

极大似然估计和贝叶斯估计(掷硬币问题)

• 极大似然估计

  在掷硬币实验中用1表示出现正面向上，用0表示出现反面向上,即
  $$x_i=\{\begin{array}{r}1,正面出现\\ 0,反面出现\end{array}$$
  估计出现正面向上的概率为 $\theta$,反面出现向上的概率为$1-\theta$，$x_i \sim B(1.,\theta) $,概率分布函数为
  $$P(X=x)={\theta }^x(1-\theta {)}^{1-x}=\{\begin{array}{rl}P(x=0)& =1-\theta \\ P(x=1)& =\theta \end{array}$$
  似然函数：
  $$\begin{array}{rl}L(\theta )& =P(X_1=x_1|\theta )\ast \cdots \ast P(X_n=x_n|\theta )\\ & =\prod _{i=1}^n{\theta }^{x_i}(1-\theta {)}^{1-x_i}\end{array}$$
  对数似然函数：
  $$\begin{array}{rl}\ln L(\theta )& =\ln \prod _{i=1}^n{\theta }^{x_i}(1-\theta {)}^{1-x_i}\\ & =\sum _{i=1}^n\left[\ln {\theta }^{x_i}+\ln (1-\theta {)}^{1-x_i}\right]\\ & =\sum _{i=1}^n{x}_i\ln \theta +\sum _{i=1}^n(1-x_i)\ln (1-\theta )\\ & =\sum _{i=1}^n{x}_i\ln \theta +(n-\sum _{i=1}^n{x}_i)\ln (1-\theta )\end{array}$$
  目标：$max\ln L(\theta )$

  对$\theta$求偏导
  $$\frac{\partial \ln L(\theta )}{\partial \theta }=\frac{\sum _{i=1}^n{x}_i}{\theta }-\frac{n-\sum _{i=1}^n{x}_i}{1-\theta }$$
  令偏导数等于0，则
  $$\frac{\sum _{i=1}^n{x}_i}{\theta }=\frac{n-\sum _{i=1}^n{x}_i}{1-\theta }$$
  求出
  $$\hat{\theta }=\frac{1}{n}\sum _{i=1}^n{x}_i$$

• 贝叶斯估计

  假设已知先验概率为$\beta$分布
  $$\pi (\theta )=\frac{\Gamma (\alpha +\beta )}{\Gamma (\alpha )\Gamma (\beta )}{\theta }^{\alpha -1}(1-\theta {)}^{\beta -1}$$
  求后验概率$P(\theta |x_1,x_2,...,x_n)$
  $$\begin{array}{rl}P(\theta |x_1,x_2,...,x_n)& =\frac{P(\theta ,x_1,x_2,...,x_n)}{P(x_1,x_2,...,x_n)}\\ & =\frac{\pi (\theta )\ast p(x_1|\theta )\ast \cdots \ast p(x_n|\theta )}{\int P(\theta ,x_1,x_2,...,x_n)d\theta }\\ & \propto \pi (\theta )\ast p(x_1|\theta )\ast \cdots \ast p(x_n|\theta )\\ & ={\theta }^{\alpha -1}(1-\theta {)}^{\beta -1}\ast \ln \prod _{i=1}^n{\theta }^{x_i}(1-\theta {)}^{1-x_i}\\ & ={\theta }^{\sum x_i+\alpha -1}\ast (1-\theta {)}^{n-\sum x_i+\beta -1}\end{array}$$
  备注：

  1. 因为$\int P(\theta ,x_1,x_2,...,x_n)d\theta$已将$\theta$积分挤掉了，所以与其无关，为一个常数;
  2. $\propto$ ：正比于；
  3. $\frac{\Gamma (\alpha +\beta )}{\Gamma (\alpha )\Gamma (\beta )}$ 也是一个常数不考虑；
  4. ${\theta }^{\sum x_i+\alpha -1}\ast (1-\theta {)}^{n-\sum x_i+\beta -1}$是参数为$\sum x_i+\alpha -1,n-\sum x_i+\beta -1$的$\beta$分布

  此时$L(\theta )$：
  $$L(\theta )={\theta }^{\sum x_i+\alpha -1}\ast (1-\theta {)}^{n-\sum x_i+\beta -1}$$
  对数似然：
  $$\ln L(\theta )=(\sum _{i=1}^n{x}_i+\alpha -1)\ln \theta +(n-\sum _{i=1}^n{x}_i+\beta -1)\ln (1-\theta )$$
  对$\theta$求偏导 :
  $$\frac{\partial \ln L(\theta )}{\partial \theta }=\frac{\sum _{i=1}^n{x}_i+\alpha -1}{\theta }-\frac{n-\sum _{i=1}^n{x}_i+\beta -1}{1-\theta }$$
  令偏导数等于0，则
  $$\frac{\sum _{i=1}^n{x}_i+\alpha -1}{\theta }=\frac{n-\sum _{i=1}^n{x}_i+\beta -1}{1-\theta }$$
  求出：
  $$\hat{\theta }=\frac{\sum _{i=1}^n{x}_i+\alpha -1}{n+\alpha +\beta -2}$$

• 极大似然和贝叶斯总结

  1. 对比极大似然$\theta$估计值$\hat{\theta }=\frac{1}{n}\sum _{i=1}^n{x}_i$和贝叶斯估计值$\hat{\theta }=\frac{\sum _{i=1}^n{x}_i+\alpha -1}{n+\alpha +\beta -2}$,当样本n趋于无穷大的时候，两者$\theta$的估计值是区域一致的；
  2. 贝叶斯估计中会给出参数的先验信息，当样本n足够大的时候，我们先前的先验信息和样本信息比就微不足道了，所以就近似于只用所有样本信息去估计$\theta$所得到的结果；
  3. 考虑极端情况下，n=1，通过极大似然估计，结果是0，或者是1，但是在贝叶斯估计中，若样本n=1，那么贝叶斯估计结果就是$\frac{\alpha }{\alpha +\beta -1}$或者$\frac{\alpha -1}{\alpha +\beta -1}$,这是样本量雄安的时候，贝叶斯估计的优势所在。

---

推导正太分布均值的极大似然估计和贝叶斯估计

• 问题：

  推导下述正太分布均值的极大似然估计和贝叶斯估计，数据$x_1,x_2,...,x_n$来自正太分布$\mathcal{N}(\mu ,{\sigma }^2)$,其中${\sigma }^2$已知：

  1. 根据样本$x_1,x_2,...,x_n$写出$\mu$的极大似然估计
  2. 假设$\mu$的先验分布是$\mathcal{N}(0,{\tau }^2)$,根据样本$x_1,x_2,...,x_n$写出$\mu$的贝叶斯估计

• 1、根据样本$x_1,x_2,...,x_n$写出$\mu$的极大似然估计

  样本的概率密度函数 $f(x_i)=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(x_i-\mu {)}^2}{2{\sigma }^2}\right)i=1,2,.....,n$

  似然函数：
  $$\begin{array}{rl}L(x_i;\mu )& =\prod _{i=1}^{n}f(x_i;\mu )\\ & =(\sqrt{2\pi }\sigma {)}^{-n}\ast \exp \left(-\frac{1}{2{\sigma }^2}\sum _{i=1}^n(x_i-\mu {)}^2\right)\end{array}$$
  对数似然函数：
  $$\begin{array}{rl}\ln L(x_i;\mu )& =-n\ln (\sqrt{2\pi }\sigma )-\frac{1}{2{\sigma }^2}\sum _{i=1}^n(x_i-\mu {)}^2\\ \Rightarrow \frac{\partial \ln L(x_i;\mu )}{\partial \mu }& =\frac{1}{{\sigma }^2}\sum _{i=1}^n(x_i-\mu )\\ & =\frac{1}{{\sigma }^2}(\sum _{i=1}^n{x}_i-n\mu )\\ 令\frac{1}{{\sigma }^2}(\sum _{i=1}^n{x}_i-n\mu )& =0\\ \Rightarrow \hat{\mu }& =\frac{1}{n}\sum _{i=1}^n{x}_i\end{array}$$

• 假设$\mu$的先验分布是$\mathcal{N}(0,{\tau }^2)$,根据样本$x_1,x_2,...,x_n$写出$\mu$的贝叶斯估计

  先验分布$f(\mu )=\frac{1}{\sqrt{2\pi }\tau }\exp \left(-\frac{{\mu }^2}{2{\tau }^2}\right)i=1,2,.....,n$
  $$\begin{array}{rl}P(\mu |x_1,x_2,...,x_n)& =\frac{P(\mu ,x_1,x_2,...,x_n)}{P(x_1,x_2,...,x_n)}\\ & =\frac{f(\mu )\ast p(x_1|\mu )\ast \cdots \ast p(x_n|\mu )}{\int P(\mu ,x_1,x_2,...,x_n)d\mu }\\ & \propto f(\mu )\ast p(x_1|\mu )\ast \cdots \ast p(x_n|\mu )\\ & =\frac{1}{\sqrt{2\pi }\tau }\exp \left(-\frac{{\mu }^2}{2{\tau }^2}\right)\ast \prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(x_i-\mu {)}^2}{2{\sigma }^2}\right)\end{array}$$
  此时$L(\theta )$：
  $$L(\theta )=\frac{1}{\sqrt{2\pi }\tau }\exp \left(-\frac{{\mu }^2}{2{\tau }^2}\right)\ast \prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(x_i-\mu {)}^2}{2{\sigma }^2}\right)$$
  对数似然：
  $$\begin{array}{rl}\ln P(\mu |x_1,x_2,...,x_n)& =-\ln \sqrt{2\pi }\tau -\frac{{\mu }^2}{2{\tau }^2}-n\ln (\sqrt{2\pi }\sigma )-\frac{1}{2{\sigma }^2}\sum _{i=1}^n(x_i-\mu {)}^2\\ \Rightarrow \frac{\partial \ln P(\mu |x_1,x_2,...,x_n)}{\partial \mu }& =-\frac{\mu }{{\tau }^2}+\frac{1}{{\sigma }^2}\sum _{i=1}^n(x_i-\mu )\\ & =\frac{1}{{\sigma }^2}(\sum _{i=1}^n{x}_i-n\mu )-\frac{\mu }{{\tau }^2}\\ 令\frac{1}{{\sigma }^2}(\sum _{i=1}^n{x}_i-n\mu )-\frac{\mu }{{\tau }^2}& =0\\ \Rightarrow \frac{1}{{\sigma }^2}(\sum _{i=1}^n{x}_i-n\mu )& =\frac{\mu }{{\tau }^2}\\ \Rightarrow \hat{\mu }& =\frac{{\tau }^2\sum _{i=1}^2{x}_i}{{\sigma }^2+n{\tau }^2}\\ & =\frac{\sum _{i=1}^2{x}_i}{n+\frac{{\sigma }^2}{{\tau }^2}}\end{array}$$
  当n较小时候，贝叶斯估计比极大似然估计要准确一些

---