霍夫丁界
若$r.v.$ $X_1,X_2,…,X_N$相互独立，且$X_i$的均值为$\mu _i$，次高斯参数为$\sigma _i$，则对任意的$\epsilon >0$都有：
$$
Pr\left[ \sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] \le exp\left\{ -\frac{\epsilon ^2}{2\sum_{i=1}^n{\sigma _{i}^{2}}} \right\}
$$
$Proof:$由定理$X_1+X_2$是$\sqrt{\sigma _{1}^{2}+\sigma _{2}^{2}}$-次高斯的$r.v.$，故$\sum_{i=1}^n{X_i}$是$\sqrt{\sum_{i=1}^n{\sigma _{i}^{2}}}$-次高斯的；
且有$\mathbb{E}\left[ \sum_{i=1}^n{X_i} \right] =\sum_{i=1}^n{\mathbb{E}\left[ X_i \right]}=\sum_{i=1}^n{\mu _i}$，由次高斯随机变量的切诺夫界为：
$$
Pr\left( \left( X-\mu \right) \ge \epsilon \right) \le e^{-\frac{\varepsilon ^2}{2\sigma ^2}},\forall \epsilon >0
$$
故有：
$$
Pr\left[ \sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] \le exp\left\{ -\frac{\epsilon ^2}{2\sum_{i=1}^n{\sigma _{i}^{2}}} \right\}
$$
设$r.v.$ $X_1,X_2,…,X_N$相互独立，且$X_i\in \left[ a_i,b_i \right] ,\forall i\in \left[ n \right] $，则有：
$$
Pr\left[ \sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] \le exp\left\{ -\frac{2\epsilon ^2}{\sum_{i=1}^n{\left( b_i-a_i \right) ^2}} \right\}
$$
$Proof:$由$X_i\in \left[ a_i,b_i \right] ,\forall i\in \left[ n \right]$，易知$X_i$的$\frac{b_i-a_i}{2}$-次高斯的；
代入霍夫丁界即可证明！
设$r.v.$ $X_1,X_2,…,X_N$相互独立，且$X_i\in \left[ a_i,b_i \right] ,\forall i\in \left[ n \right] $，则有：
$$
Pr\left[ \frac{1}{n}\sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] \le exp\left\{ -\frac{2n^2\epsilon ^2}{\sum_{i=1}^n{\left( b_i-a_i \right) ^2}} \right\}
$$
$Proof:$由于
$$
Pr\left[ \frac{1}{n}\sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] =Pr\left[ \sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge n\epsilon \right]
$$
当$b_1=b_2=…=b_n, a_1=a_2=…=a_n$时有：
$$
Pr\left[ \frac{1}{n}\sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon \right] \le exp\left\{ -\frac{2n^2\epsilon ^2}{\sum_{i=1}^n{\left( b_i-a_i \right) ^2}} \right\} =exp\left\{ -\frac{2n\epsilon ^2}{\left( b-a \right) ^2} \right\}
$$
机器学习中的集中不等式
本部分内容主要参考《西瓜书》第十二章的计算学习理论、前面几篇文章提到的切尔诺夫界的应用和南本此部分的讲义，主要说明其在有监督学习中的应用，因为假设了独立同分布，不独立同分布的需要用到鞅的概念，想深入学习可以参考以下视频：
因为精力有限我就不做深入学习了。
给定一个二分类问题的训练数据集：
$$
S_n=\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,…\left( x_n,y_n \right) \right\}
$$
其中$x_i\in \mathcal{X}\subseteq \mathbb{R}^d$表示第$i$个训练样本的特征，$x_i\in \mathcal{Y}=\left\{ 0,1 \right\} $表示第$i$个训练样本的标签，假定$\mathcal{D}$是空间$\mathcal{X}\times \mathcal{Y}$的一个未知不可见的联合分布，且给定数据集$S_n$均为在分布$\mathcal{D}$中独立采样得到。
给定某分类器$f\rightarrow \left\{ 0,1 \right\} $，通过$n$条训练数据的训练，其在错误率为：
$$
\hat{R}\left( f,S_n \right) =\frac{1}{n}\sum_{i=1}^n{\mathbb{I}\left( f\left( x_i \right) \ne y_i \right)}
$$
估计$f$在$\mathcal{D}$上的分类错误率，即泛化误差：
$$
R\left( f,\mathcal{D} \right) =E_{\left( x,y \right) \sim \mathcal{D}}\left( \mathbb{I}\left( f\left( x \right) \ne y \right) \right) =\underset{\left( x,y \right) \sim \mathcal{D}}{Pr}\left[ f\left( x \right) \ne y \right]
$$
由于$\mathcal{D}$不可知故无法直接计算$R\left( f,\mathcal{D} \right)$，但在已知$S_n$和$\hat{R}\left( f,S_n \right)$的情况下可以通过它们来估计$R\left( f,\mathcal{D} \right)$。
设随机变量$X_i=\mathbb{I}\left[ f\left( x_i \right) \ne y_i \right] ,i\in \left[ n \right] $，根据有监督学习的独立同分布假设可知$X_1,X_2,…X_n$是独立同分布的随机变量。令$p=E\left[ X_i \right]$，则有$X_i$~$Ber\left( p \right) $。
故相当于估计参数$p$，记$\hat{R}\left( f,S_n \right)=\hat{p}$，$X=\sum_{i=1}^n{X_i}$可以得到：
$$
\underset{S_n\sim \mathcal{D}}{Pr}\left[ \left| \hat{R}\left( f,S_n \right) -R\left( f,\mathcal{D} \right) \right|\ge \epsilon \right] =Pr\left[ \left| \hat{p}-p \right|\ge \delta \right]
$$
$$
=Pr\left( p 不属于 \left[ \hat{p}-\delta ,\hat{p}+\delta \right] \right) =Pr\left( p+\delta <\hat{p} \right) +Pr\left( p-\delta >\hat{p} \right)
$$
$$
=Pr\left( np+n\delta < n\hat{p} \right) +Pr\left( np-n\delta > n\hat{p} \right)
$$
$$
=Pr\left( np\left( 1+\frac{\delta}{p} \right) < X \right) +Pr\left( np\left( 1-\frac{\delta}{p} \right) > X \right)
$$
此时根据泊松试验的切尔诺夫界可以得到：
$$
Pr\left[ \left| \hat{p}-p \right|\ge \delta \right] \le =exp\left\{ -n\delta ^2/2 \right\} +exp\left\{ -n\delta ^2/3 \right\}
$$
即泛化误差$p$有至少$1-exp\left\{ -n\delta ^2/2 \right\} -exp\left\{ -n\delta ^2/3 \right\} $的概率落在区间$\left[ \hat{p}-\delta ,\hat{p}+\delta \right]$当中。
引用切尔诺夫界同样的记号开始推理，易知$X_i$是$\frac{1}{2}$-次高斯的，可以得到：
$$
\underset{S_n\sim \mathcal{D}}{Pr}\left[ \left| \hat{R}\left( f,S_n \right) -R\left( f,\mathcal{D} \right) \right|\ge \epsilon \right] =Pr\left[ \left| \hat{p}-p \right|\ge \epsilon \right]
$$
$$
=Pr\left[ \left| n\hat{p}-np \right|\ge n\epsilon \right] =Pr\left[ \left| \sum_{i=1}^n{X_i}-\sum_{i=1}^n{p} \right|\ge n\epsilon \right]
$$
$$
=Pr\left[ \frac{1}{n}\left| \sum_{i=1}^n{X_i}-\sum_{i=1}^n{p} \right|\ge \epsilon \right]
$$
代入霍夫丁界的推理 2 可以得到：
$$
Pr\left[ \left| \hat{p}-p \right|\ge \epsilon \right] \le 2exp\left\{ -2n^2\epsilon ^2 \right\} \le 2exp\left\{ -2n\epsilon ^2 \right\}
$$
令$\delta =2e^{-2n\epsilon^2}$，易有$\epsilon =\sqrt{\frac{ln\left( 2 / \delta \right)}{2n}}$，回代可得：
$$
Pr\left[ \left| \hat{p}-p \right|\ge \epsilon \right] \le 2exp\left\{ -2n\epsilon ^2 \right\} \Rightarrow Pr\left[ \left| \hat{p}-p \right|\ge \epsilon \right] \le \delta \Rightarrow
$$
$$
Pr\left[ \left| \hat{p}-p \right|\le \epsilon \right] \ge 1-\delta \Rightarrow Pr\left( \hat{p}-\epsilon \le p\le \hat{p}+\epsilon \right)
$$
综上，泛化误差$p$有至少$1-\delta $的概率落在区间：
$$
\hat{p}-\sqrt{\frac{ln\left( 2 / \delta \right)}{2n}}\le p\le \hat{p}+\sqrt{\frac{ln\left( 2 / \delta \right)}{2n}}
$$
