0%

拉德马赫复杂度

发表于 更新于 分类于

前言: 本文主要讲了拉德马赫复杂度(Rademacher complexity), 主要参考了Understanding machine learning一书26章.

首先应当接触以下几个概念:

  • 样本空间: 对于监督学习而言为带标签的样本\((x,y)\)的取值空间\(Z=(\mathcal{X}, \mathcal{Y})\), 学习的目标是映射\(f: \mathcal{X}\to\mathcal{Y}\), 以用于产生对新样本\(x_{new}\)的标签的可靠预测\(f(x_{new})\). p.s.对无监督学习而言为不带标签的样本\(x\)的取值空间\(\mathcal{X}\), 学习目标为对\(\mathcal{X}\)的可靠分类.
  • 目标函数: 通常记为\(f\), 即上述监督学习中所说的映射\(f\). 对于分类问题就是我们希望得到的真实的分类函数.
  • 训练集: 通常记为\(S\), 由定义在样本空间\(Z=(\mathcal{X}, \mathcal{Y})\)上的概率分布\(\mathcal{D}\)抽样得到 \[S=\{(x_{1},y_{1}),....,(x_{m},y_{m})\}\]
  • 学习算法: 通常记为\(A\), 即我们构建的、能从数据中学到东西的学习算法, 期望其能从假设类中返回良好的假设.
  • 假设类: 通常记为\(\mathcal{H}\), 对目标函数\(f\)的假设构成的空间, 学习器从中选择.
  • 预测器(predictor): 或者说分类器(classifier)、假设(hypothesis), 通常记为\(h\), 即学习器输出的一个函数:\(h:\mathcal{X}\to\mathcal{Y}\), 且应当和目标函数\(f\)有相近的函数值.
  • 损失函数: 通常记为\(l(h, (x, y))\), 其定义在预测器\(h\)和单个样本\((x, y)\)上. 对于二分类问题, 一个常用的损失函数为\(l(h, (x, y))=I\{y\neq h(x)\}\), 即分对了就为0, 分错了就为1.
  • 训练误差: 通常记为\(L_{S}(h)\), 其定义为预测器\(h\)在训练集\(S\)上的平均损失\[L_{S}(h)=\frac{1}{m}\sum_{i=1}^m l(h, (x_i, y_i))\]
  • 泛化误差: 通常记为\(L_{\mathcal{D}}(h)\), 其定义为预测器\(h\)在\((\mathcal{X}, \mathcal{Y})\)上的平均损失\[\mathbb{E}_{(x, y)\sim (\mathcal{X}, \mathcal{Y})}l(h, (x, y))\]
  • \(\varepsilon\)-代表性样本: 一个训练集被称为\(\varepsilon\)-代表性样本(定义在域\(Z\), 假设类\(\mathcal{H}\), 损失函数\(l\)和分布\(\mathcal{D}\)上), 如果满足\[\sup_{h\in\mathcal{H}}|L_{S}(h)-L_{\mathcal{D}}(h)|\le\varepsilon\]

接着应当知道如下基本事实:

如果\(S\)是\(\varepsilon/2\)-代表性样本, 那么在ERM准则下它是\(\varepsilon\)-一致的, 即\[L_{\mathcal{D}}(ERM_{\mathcal{H}}(S))\le \min_{h\in\mathcal{H}}L_{\mathcal{D}}(h)+\varepsilon\]

拉德马赫复杂度

回顾之前针对二分类问题建立的VC bound:\[ \sup_{h\in\mathcal{H}}\left|L_{S}(h)-L_{\mathcal{D}}(h)\right|\le \sqrt{\frac{8}{m}\log\left(\frac{4}{\delta}\right)+\frac{8d_{\mathcal{H}}}{m}\log\left(\frac{2em}{d_\mathcal{H}}\right)} \]注意到要定义训练误差与泛化误差必须要定义损失函数, 损失函数实际上选定了二分类问题的常用的损失函数0-1损失: \(l(h, (x, y))=I\{y\neq h(x)\}\); 因此上述VC bound又可以写作:\[ \sup_{f\in\mathcal{F}}\left|L_{S}(f)-L_{\mathcal{D}}(f)\right|\le \sqrt{\frac{8}{m}\log\left(\frac{4}{\delta}\right)+\frac{8d_{\mathcal{H}}}{m}\log\left(\frac{2em}{d_\mathcal{H}}\right)} \]这里的\(\mathcal{F}\)定义为\[l \circ \mathcal{H}=\{z\mapsto l(h, z):h\in\mathcal{H}\}\] 相应的\(L_{S}(f)=\frac{1}{m}\sum_{i=1}^m f(z_i)\), \(L_{\mathcal{D}}(f)=\mathbb{E}_{z\sim \mathcal{D}}f(z)\), 当然这里的\(l\)已经固定为0-1损失. 定义训练集\(S\)在\(\mathcal{F}\)上的代表性为:\[Rep_{\mathcal{D}}(\mathcal{F}, S)\doteq\sup_{f\in\mathcal{F}}(L_{\mathcal{D}}(f)-L_{S}(f))\]一般来说, 训练误差\(L_{S}\)能通过优化达到一个非常接近于0的数值, 比如这篇文章说明了用梯度下降训练ResNet能在多项式时间内达到0训练误差, 即达到全局最优; 泛化误差\(L_{\mathcal{D}}\)则会略大于训练误差. 显然当\(S\)越能代表\(\mathcal{D}\), 上数值会越接近于0. 现在想要仅仅依靠训练集\(S\)本身去估计其代表性, 一个自然地想法是将\(S\)分成两个不相交的子集\(S=S_1\cup S_2\), \(S_1\)作为验证集, \(S_2\)作为训练集, 此时训练集代表性的一个近似为:\[\sup_{f\in\mathcal{F}}(L_{\mathcal{S_1}}(f)-L_{S_2}(f))\]再设多元随机变量\[\sigma=(\sigma_1, \sigma_2,...,\sigma_m)\in\{\pm 1\}^m\] 并按如下方式取定随机变量的值\(S_1=\{z_i:\sigma_i=1\}\), \(S_2=\{z_i:\sigma_i=-1\}\), 上式可写成更简单的形式:\[\frac{1}{m}\sup_{f\in\mathcal{F}}\sum_{i=1}^m \sigma_i f(z_i)\] 此时随机变量的不同的取值代表不同的验证集和训练集的组合, 拉德马赫复杂度定义为上式近似对随机变量\(\sigma\)的期望:\[R(\mathcal{F}\circ S)\doteq\frac{1}{m}\mathop{\mathbb{E}}_{\sigma\sim\{\pm 1\}^m} [\sup_{f\in\mathcal{F}}\sum_{i=1}^m \sigma_i f(z_i)]\]可以证明, 在期望意义下, 集合\(S\)的代表性不超过2倍的拉德马赫复杂度\[\mathop{\mathbb{E}}_{S\sim\mathcal{D}^m}[Rep_{\mathcal{D}}(\mathcal{F}, S)]\le 2\mathop{\mathbb{E}}_{S\sim\mathcal{D}^m}[R(\mathcal{F}\circ S)]\]证明见Understanding machine learning一书引理26.2.

数据相关界

首先来看一个重要的不等式, 有限偏差集中不等式, 又称McDiarmid 不等式, 这个不等式可见维基, 这个不等式可用来推出一个与训练集\(S\)相关的界:

假设对所有的\(z\)和\(h\in\mathcal{H}\), \(|l(h, z)|\le c\), 那么以至少\(1-\delta\)的概率, 对所有的\(h\in\mathcal{H}\)有\[L_{\mathcal{D}}(h)-L_{S}(h)\le 2\mathop{\mathbb{E}}_{S\sim\mathcal{D}^m}[R(l \circ \mathcal{H}\circ S)]+c\sqrt{\frac{2\log(2/\delta)}{m}}\]以至少\(1-\delta\)的概率, 对所有的\(h\in\mathcal{H}\)有\[L_{\mathcal{D}}(h)-L_{S}(h)\le 2R(l \circ \mathcal{H}\circ S)+4c\sqrt{\frac{2\log(4/\delta)}{m}}\] 以至少\(1-\delta\)的概率, 对所有的\(h\in\mathcal{H}\)有\[L_{\mathcal{D}}(ERM_{\mathcal{H}}(S))-L_{\mathcal{D}}(h)\le 2R(l \circ \mathcal{H}\circ S)+5c\sqrt{\frac{2\log(8/\delta)}{m}}\]

有兴趣的朋友不妨试着去推一推, 上述1, 2的界的推导类似于西瓜书定理12.5, 唯一不同的是这里满足在常数为\(2c/m\)下的有界偏差条件, 而西瓜书直接为1; 第三个不等式则是多一步霍夫丁不等式.

  • 注意到第2, 3个界实际上由具体的训练集\(S\)计算出来的, 因此这两个界被称为是数据相关界, 这也是与VC bound最大的不同之处.
  • 第二个界可以用来评估当前分类器\(h\)在实际数据集\(\mathcal{D}\)上的表现, 即\(L_{\mathcal{D}}(h)\).
  • 第三个界可以用来评估利用ERM原则得到的分类器\(h\)与理论最佳分类器的实际差距, 因此希望这个界越小越好; 显然假设类\(\mathcal{H}\)越复杂, 这个界越大, 因此某种意义上这个界能用来评估假设类\(\mathcal{H}\)的优劣.

拉德马赫复杂度的性质

首先给出拉德马赫复杂度的更一般化定义: 给定一个向量集合\(A\in\mathbb{R}^m\) \[R(A)\doteq\frac{1}{m}\mathop{\mathbb{E}}_{\sigma\sim\{\pm 1\}^m} [\sup_{a\in A}\sum_{i=1}^m \sigma_i a_i]\]这里例举拉德马赫复杂度的几条性质, 具体见Understanding machine learning一书26章:

  • A的凸包与A具有一样的拉德马赫复杂度.
  • 一个有限集合的拉德马赫复杂度随着集合大小增长而对数增长.
  • 如果给集合A作用一个Lipschitz连续的函数, 并不会增大其拉德马赫复杂度.

线性类的拉德马赫复杂度

本节给出两个线性的假设类的拉德马赫复杂度, 假定\(x\)的维数为\(n\):

  • \(\mathcal{H}_1=\{x\mapsto<\omega, x>:\Vert\omega\Vert_1\le 1\}\)
  • \(\mathcal{H}_2=\{x\mapsto<\omega, x>:\Vert\omega\Vert_2\le 1\}\)

\(\mathcal{H}_1\circ S\)定义为\(\{(<\omega, x_i>, i=1...,m):\Vert\omega\Vert_1\le 1\}\), \(\mathcal{H}_2\circ S\)类似的定义, 有如下两个结果, 证明见[UML]一书引理26.10、26.11:

  • \(R(\mathcal{H}_1\circ S) \le \max_i\Vert x_i\Vert_{\infty}\sqrt{\frac{2\log(2n)}{m}}\)
  • \(R(\mathcal{H}_2\circ S) \le\frac{\max_i\Vert x_i\Vert_2}{\sqrt{m}}\)

p.s. 此外还有软硬间隔SVM的泛化误差界的推导, 见26.3, 26.4; 另一种度量集合复杂度的方法为覆盖数, 见27章.