Foundations of Machine Learning: Rademacher complexity and VC-Dimension(1)
前面两篇文章中，我们在给出PAC-learnable定理时，都有一个前提假设，那就是 Hypothesis set 是有限的。但很明显，在实际中的假设集大都是无限的，比如上一篇文章中介绍的与坐标轴对齐的矩阵的例子，其 Hypothesis set 就是无限的。
假设我们也用上一章的方法来分析，最后得到的上界中含有无穷大的项$log|H|$, 显然这没有什么意义。 于是我们必须用其他的方法来衡量无限的假设集。换句话说，当 Hypothesis set 越大， 那么他的复杂度就越高, 但当 Hypothesis set 为无限大， 那么我们应该另外找一些有限的指标来衡量模型的复杂度。这就是我们本章要解决的问题。
实际上，去衡量这种复杂度有很多方法， 在接下去的两篇文章中，我们介绍其中的三种。 第一个是 Rademacher complexity， 第二个是 Growth function， 第三个是 VC-dimension。
（一） Rademacher Complexity
这里我们仍然用H表示假设集， h表示假设集中的元素。 但这里我们不再像前面文章那样使用0-1损失函数， 而是用更一般的损失函数$L:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}$。 对每一个假设$h:\mathcal{X}\rightarrow\mathcal{Y}$, 与之的关联的一个函数$g:\mathcal{X}\times\mathcal{Y}\rightarrow L(h(x),y)$，所有$g$ 的集合记为 G ，于是对于每一个H， 都有于之相关联的G。所以对H的分析转换到对G的分析。
Rademacher complexity 的思想：通过去衡量一个假设对随机噪声的拟合程度好坏来评估这个函数族的复杂度。
定义 2.1 Empirical Rademacher Complexity 令G为一个从Z到$[a,b]$的映射函数集合，$S=(z_1,z_2,...,z_m)$为大小为m的固定样本，其中$z_i\in Z$。那么相对于样本S，函数族G的Empirical Rademacher Complexity定义为：
\begin{equation*}\widehat{\mathfrak{R}}_S(G)=\mathop{E}\limits_{\sigma}[\sup\limits_{g\in G}\frac{1}{m}\sum _{i=1}^m\sigma_ig(z_i)]\end{equation*}
其中$\sigma=(\sigma_1,\sigma_2,...,\sigma_m)^T$，且$\sigma_i$是取值为$\{+1,-1\}$独立均匀随机变量。我们称随机变量$\sigma_i$为Rademacher变量。
对于这个定义注意以下几点：
- 样本$S=(z_1,z_2,...,z_m)=((x_1,y_1),(x_2,y_2),...,(x_m,y_m))$。
- $g(z_i)$ 表示用于之对应的假设 h 来预测$y_i$所产生的错误。
- Rademacher 变量是个取$\{-1,+1\}$ 两个值的均匀随机变量，上述的期望就是基于这个均匀随机变量的分布来求的。
- 可以将上述式子写成：$\widehat{\mathfrak{R}}_S(G)=\mathop{E}\limits_{\sigma}[\sup\limits_{g\in G}\frac{\sigma g_s}{m}]$。
- 越复杂的函数族G可以产生更多不同的$g_s$，因此平均的说能更好的拟合随机噪声。
定义 2.2 Rademacher Complexity 令D为产生样本的分布。对任意的整数$m>1$，G的Rademacher Complexity是Empirical Rademacher Complexity的期望，其中的期望是基于样本根据分布采样而来的：
$$\mathfrak{R}_m(G)=\mathop{E} \limits _{S\sim D^m}[\widehat{\mathfrak{R}}_S(G)]$$
为了下面的定理证明，需要先介绍McDiarmid概率不等式。
McDiarmid不等式：令$(x_1,...,x_m)\in \mathcal{X}^m$为独立随机变量的集合，假设存在$c_1,...,c_m>0$，使得$f:\mathcal{X}\rightarrow R$满足以下条件：
$$|f(x_1,...,x_i,...,x_m)-f(x_1,...,x_i',...,x_m)|\leq c_i,$$
对所有的$i\in[1,m]$以及任意的点$x_1,...,x_m,x_i'\in\mathcal{X}$都成立。令$f(S)$ 表示 $f(x_1,...,x_m)$，那么对所有的$\varepsilon>0$，下面的不等式成立：
$$Pr[f(S)-E[f(S)]\geq \epsilon]\leq exp(\frac{-2\epsilon^2}{\sum_{i=1}^mc_i^2})$$
$$Pr[f(S)-E[f(S)]\leq -\epsilon]\leq exp(\frac{-2\epsilon^2}{\sum_{i=1}^mc_i^2})$$
定理 2.1 令G为从Z到$[0,1]$的映射函数族。那么对任意的$\delta>0$，至少以概率$1-\delta$，以下的不等式对所有的$g\in G$都成立：
$$E[g(z)]\leq\frac{1}{m}\sum_{i=1}^m g(z_i)+2\mathfrak{R}_m(G)+\sqrt{\frac{log\frac{1}{\delta}}{2m}},$$
$$E[g(z)]\leq\frac{1}{m}\sum_{i=1}^m g(z_i)+2\mathfrak{\widehat{R}}_S(G)+3\sqrt{\frac{log\frac{2}{\delta}}{2m}}.$$
证明： 我们分成八个步骤来证明这个定理。
- 对任意样本$S=(z_1,...,z_m)$和任意$g\in G$，用$\widehat{E}_S[g]$表示g在任意样本S下的empirical average： $$\widehat{E}_S[g]=\frac{1}{m}\sum_{i=1}^m g(z_i).$$
- 我们在样本集合上定义一个函数$\Phi:\mathcal{X}^m \rightarrow \mathbb{R}$,记为： $$\Phi(S)=\sup\limits_{g\in G}(E[g]-\widehat{E}_S[g]).$$
- 令$S,S'$为两个大小为m的样本，这两个样本中只有一个点不同，例如$S=(z_1,...,z_{m-1},z_m),S'=(z_1,z_2,...,z_{m-1},z_m')$
- 根据最大值的差一定不超过差的最大值，可得 \begin{eqnarray*}\Phi(S')-\Phi(S) &=& \sup\limits_{g\in G}(E[g]-\widehat{E}_{S'}[g])-\sup\limits_{g\in G}(E[g]-\widehat{E}_S[g]) \\&\leq& \sup\limits_{g\in G}(E[g]-\widehat{E}_{S'}[g]-E[g]+\widehat{E}_S[g] ) \\ &=& \sup\limits_{g\in G}(\widehat{E}_S[g]-\widehat{E}_{S'}[g]) \\&=& \sup\limits_{g\in G}\frac{g(z_m)-g(z_m')}{m} \\&\leq& \frac{1}{m}\end{eqnarray*}
同理，我们也可以得到$\Phi(S)-\Phi(S') \leq \frac{1}{m}$, 因此 $$|\Phi(S)-\Phi(S')|\leq \frac{1}{m}$$ - 应用McDiarmid第一个不等式，有 $$Pr[\Phi(S)-E[\Phi(S)]\geq \epsilon]\leq exp(\frac{-2\epsilon^2}{1/m})$$
令$\delta=exp(-2m\epsilon^2)\Rightarrow \epsilon=\sqrt{\frac{log\frac{1}{\delta}}{2m}}$，即以下不等式至少以$1-\delta$概率成立： $$\Phi(S)\geq E[\Phi(S)]+\sqrt{\frac{log\frac{1}{\delta}}{2m}}$$ - 求$E[\Phi(S)]$的上界。 \begin{align}\mathop{E}_S[\Phi(S)] &= \mathop{E}_S[\sup_{g\in G}(E[g]-\widehat{E}_S(g))] \nonumber \\ &= \mathop{E}_S[\sup_{g\in G}\mathop{E}_{S'}[\widehat{E}_{S'}(g)-\widehat{E}_{S}(g)]] \label{equ:3} \\ &\leq \mathop{E}_{S,S'}[\sup_{g\in G}\widehat{E}_{S'}[g]-\widehat{E}_S(g)] \label{equ:4} \\&= \mathop{E}_{S,S'}[\sup_{g\in G} \frac{1}{m}\sum_{i=1}^m(g(z_i')-g(z_i))] \label{equ:5} \\&= \mathop{E}_{\sigma,S,S'}[\sup_{g\in G} \frac{1}{m}\sum_{i=1}^m\sigma_i(g(z_i')-g(z_i))]\label{equ:6} \\&\leq \mathop{E}_{\sigma,S'}[\sup_{g\in G} \frac{1}{m}\sum_{i=1}^m\sigma_ig(z_i')]+\mathop{E}_{\sigma,S}[\sup_{g\in G} \frac{1}{m}\sum_{i=1}^m-\sigma_ig(z_i)] \label{equ:7} \\&= 2\mathop{E}_{\sigma,S}[\sup_{g\in G} \frac{1}{m}\sum_{i=1}^m\sigma_ig(z_i)] \label{equ:8} \\&= 2\mathfrak{R}_m(G) \nonumber\end{align}
其中，
式子\ref{equ:3}成立是因为$E(g)=\mathop{E}\limits_{S'}[\widehat{E}_{S'}(g)]$,类似于$\mathcal{R}(h)=E[\widehat{\mathcal{R}}(h)]$;
式子\ref{equ:4}成立是因为sup函数是凸的，应用Jensen's inequality可得(简单的说就是，若f为凸，则$f(E(x))\leq E[f(x)]$);
式子\ref{equ:5}是根据$\widehat{E}_s(g)$的定义；
式子\ref{equ:6}是因为，引进 Rademacher variable 不改变式子\ref{equ:5}的值。如当$\sigma_i=1$时，值不改变；当$\sigma_i=-1$时，由于我们是对所有$S,S'$求期望，故可通过对换$S,S'$得到相 同的值；
式子\ref{equ:7} 成立是因为$\sup(u+v)\leq \sup(u)+ \sup(v)$;
式子\ref{equ:8} 成立是因为$\sigma_i$ 与 $-\sigma_i$ 有相同的分布。 - 所以， \begin{eqnarray*}& & E[g]-\widehat{E}_S[g] \leq \Phi(S) \leq E[\Phi(S)]+\sqrt{\frac{log\frac{1}{\delta}}{2m}} \\&\leq& 2\mathfrak{R}_m(G)+\sqrt{\frac{log\frac{1}{\delta}}{2m}}\end{eqnarray*}
$\Longrightarrow$
\begin{align*}E[g] &\leq \widehat{E}_S[g] + 2\mathfrak{R}_m(G)+\sqrt{\frac{log\frac{1}{\delta}}{2m}} \nonumber\\&= \frac{1}{m}\sum_{i=1}^mg(z_i) + 2\mathfrak{R}_m(G)+\sqrt{\frac{log\frac{1}{\delta}}{2m}} \nonumber\end{align*} - 现在证明第二个不等式。
根据定义2.1，将样本S 改变一点，则 $\widehat{\mathfrak{R}}_S(G)$将至多改变$\frac{1}{m}$, 且$E[\widehat{\mathfrak{R}}_S(G)] = \mathfrak{R}_m(G)$。将 $\widehat{\mathfrak{R}}_S(G)$看作McDiarmid不等式中的$f(s)$，应用McDiarmid不等式中的第二个不等式有， $$Pr[\widehat{\mathfrak{R}}_S(G)-\mathfrak{R}_m(G)\leq -\epsilon]\leq exp(-2\epsilon^2 m)$$
令$\frac{\delta}{2}=exp(-2\epsilon^2m) \Rightarrow \epsilon=\sqrt{\frac{log\frac{1}{\delta}}{2m}} $。所以至多以$\frac{\delta}{2}$的概率$\mathfrak{R}_m(G)>\widehat{\mathfrak{R}}_S(G)+\sqrt{\frac{log\frac{1}{\delta}}{2m}}$成立。 另外，由以上证明的第5步可知（将$\delta$换成$\frac{\delta}{2}$）：至多以$\frac{\delta}{2}$概率$\Phi(S)\geq E[\Phi(S)] + \sqrt{\frac{log\frac{2}{\delta}}{2m}}$。所以至多以$\delta$概率以上式子至少有一个成立，即至少以$1-\delta$概率以上式子同时不成立： \begin{align*}\Phi(S) &\leq E[\Phi(S)] + \sqrt{\frac{log\frac{2}{\delta}}{2m}} \\&\leq 2\mathfrak{R}_m(G) + \sqrt{\frac{log\frac{2}{\delta}}{2m}} \\&\leq 2\widehat{\mathfrak{R}}_S(G) + 3\sqrt{\frac{log\frac{2}{\delta}}{2m}}\end{align*}
$\Longrightarrow$
$$E[g(z)]\leq \frac{1}{m}\sum_{i=1}^mg(z_i) + 2\widehat{\mathfrak{R}}_S(G) + 3\sqrt{\frac{log\frac{2}{\delta}}{2m}}$$
我们把上面的结果应用到0-1损失函数，得到以下的引理。
引理 2.1 令H为取值为$\{-1,+1\}$的函数族，令G为与H相对应的且损失函数为0-1损失的函数族：$G=\{(x,y)\rightarrow\mathbb{I}(h(x)\neq y):h\in H\}$。对任意的样本$S=((x_1,y_1),...,(x_m,y_m))$，以下等式成立：
$$\widehat{\mathfrak{R}}_S(G)=\frac{1}{2}\widehat{\mathfrak{R}}_{S_\mathcal{X}}(H).$$
证明：对于任何一个样本$S=((x_1,y_1),...,(x_m,y_m))\subseteq \mathcal{X}\times\{-1,+1\}$, 根据定义：
\begin{align*}\widehat{\mathfrak{R}}_S(G) &= \mathop{E}_{\sigma} [\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m\sigma_i\mathbb{I}(h(x_i)\neq y_i)] \\&= \mathop{E}_{\sigma}[\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m\sigma_i\frac{1-y_ih(x_i)}{2}] \\&= \frac{1}{2}\mathop{E}_{\sigma}[\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m(\sigma_i-\sigma_iy_ih(x_i))] \\&= \frac{1}{2}\mathop{E}_{\sigma}[\frac{1}{m}\sum_{i=1}^m\sigma_i + \sup_{h\in H}-\sigma_iy_ih(x_i)] \\&= \frac{1}{2}\mathop{E}_{\sigma}[\frac{1}{m}\sup_{h\in H}-\sigma_iy_ih(x_i)] \\&= \frac{1}{2}\mathop{E}_{\sigma}[\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m\sigma_ih(x_i)] \\&= \frac{1}{2}\widehat{\mathfrak{R}}_{S_\mathcal{X}}(H)\end{align*}
其中，$\sigma_i$与$-\sigma_iy_i$的分布是一样的。证毕！
将定理 2.1 和引理 2.1 应用于二分类的$0-1$损失，可知：
$$\widehat{\mathcal{R}}(h)=\frac{1}{m}\sum_{i=1}^m\mathfrak{1}_{(h(x_i)\neq y_i)}=\frac{1}{m}\sum_{i=1}^mg(x_i)=\widehat{E}_S[g]$$
$$\mathcal{R}(h)=E[\widehat{\mathcal{R}}(h)]=\mathop{E}_S[\widehat{E}_S[g]]=E[g(z)]$$
故可得以下定理：
定理 2.2 Rademacher complexity 界——二分类情况
令H为取值为$\{-1,+1\}$的函数族，令D为输入空间$\mathcal{X}$上的分布。那么，对于任意的$\delta>0$，在根据D采样且大小为m的样本S上，以概率$1-\delta$以下的不等式对任意的$h\in H$都成立：
$$\mathcal{R}(h)\leq \widehat{\mathcal{R}}(h)+\mathfrak{R}_m(H)+\sqrt{\frac{log\frac{1}{\delta}} {2m} },$$
$$\mathcal{R}(h)\leq \widehat{\mathcal{R}}(h)+\widehat{\mathfrak{R}}_S(H)+3\sqrt{\frac{log\frac{2}{\delta}} {2m} }.$$
注意，定理中$\widehat{\mathfrak{R}}_S(H)=\mathop{E}_\sigma[\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m\delta_ih(x_i)]$, $\mathfrak{R}_m(H)=\mathop{E}_{S\backsim D^m}[\widehat{\mathcal{R}}_S(H)]$。
这个定理指出了在基于Rademacher Complexity下二分类错误的界。另外，根据第二个式子，只要我们计算出$\widehat{\mathfrak{R}}_S(H)$的值就可以计算出$\mathcal{R}(h)$的界，但实际上$\widehat{\mathcal{R}}_S(H)$的计算等价与经验风险最小化问题。即：
$$\widehat{\mathfrak{R}}_S(H)=\mathop{E}_\sigma[\sup_{h\in H}\frac{1}{m}\sum_{i=1}^m-\delta_ih(x_i)]=-\mathop{E}_\delta[\inf_{h\in H}\frac{1}{m}\sum_{i=1}^m\delta_ih(x_i)].$$
由上式可知，对于一个固定的$\delta$，计算上式等价于empirical risk minimization 问题，因此属于NP问题。