526互联

【论文笔记】A theory of learning from different domains

发布时间 2023-10-11 03:43:55作者: 李斯赛特

防盗 https://www.cnblogs.com/setdong/p/17756127.html
domain adaptation 领域理论方向的重要论文. 这篇笔记主要是推导文章中的定理, 还有分析定理的直观解释. 笔记中的章节号与论文中的保持一致.

1. Introduction

domain adaptation 的设定介绍:
有两个域, source domain 与 target domain.
source domain: 一组从 source dist. 采样的带有标签的数据.
target domain: 一组从 target dist. 采样的无标签的数据, 或者有很少的数据带标签.
其中 source dist. \(\neq\) target dist.
目标: 学习一个能在 target domain上表现得好的模型.
(第二节跳过)

3. A rigorous model of domain adaptation

首先关注二分类问题. 这节主要是给出了本文中用到的一些notations.

  • \(<\mathcal{D}_S, f_S>\) 表示 source domain, 前者是 source dist, 后者是 source dist. 上的 ground truth function.
  • \(<\mathcal{D}_T, f_T>\) 表示 target domain, 同上.
  • \(h:\mathcal{X}\rightarrow \{0,1\}\) 表示一个从输入空间映射到二分类集合的 hypothesis.
  • 在分布 \(\mathcal{D}_S\) 上, 两个 hypotheses \(h\) 与 \(f\) 的平均差异定义为:

\[ \epsilon_S(h,f)=\mathbf{E}_{x\sim \mathcal{D}_S}[|h(x)-f(x)|] \]

由于 \(h\) 与 \(f\) 的输出是 0 或 1, 所以只有它们输出不同时, 期望中间的部分为 1, 所以上式为两个hypotheses之间的平均差异(或 disagreements).

  • source error of \(h\): \(\epsilon_S(h)=\epsilon_S(h,f_S)\), 也就是 \(h\) 在source domain 上的错误率 (generalization error).
  • empirical source error of \(h\): \(\hat{\epsilon}_S(h)\), 也就是 \(h\) 在source domain 上的经验错误率 (empirical error).
  • 相同的, 在 target domain 上的 notations: \(\epsilon_T(h,f),\epsilon_T(h),\) 和\(\hat{\epsilon}_T(h)\).

4. A bound relating the source and target error

现在, 想要分析一个在 source domain上训练的分类器在 target domain上的 generalization error (即 \(\epsilon_T(h)\)) 是多少. 这个值肯定无法计算出来, 所以最直观的想法就是用 source error (即 \(\epsilon_S(h)\)) 和 两个域之间的差异来 bound target error.
那么用什么来表示两个域之间的差异呢? 文章首先用 \(L^1\) Divergence 表示这个差异, 并给出了用\(L^1\) Divergence 的 bound.
但是 \(L^1\) Divergence 有很多缺点, 所以作者提出了第二种方法来表示域之间的差异 -- \(\mathcal{H}\) Divergence, 为了给出相应的 bound, 又将 \(\mathcal{H}\) Divergence 扩展成 \(\mathcal{H}\Delta\mathcal{H}\) Divergence.

a) \(L^1\) Divergence

也叫 Variation Divergence, Variation Distance, TV Distance.

\[d_1(\mathcal{D}, \mathcal{D}')=2\sup_{B\in\mathcal{B}}|\Pr_\mathcal{D}[B]-\Pr_{\mathcal{D}'}[B]| \]

其中 \(\mathcal{B}\) 是在 \(\mathcal{D}\) 和 \(\mathcal{D}'\) 上所有可测子集的集合.
用两个很简单的一维分布来表示一下:

上面两个: 红色区域和蓝色区域的面积是相等的, 因为面积就是概率. 很明显, 对于这两种情况而言, \(d_1(\mathcal{D},\mathcal{D}')\) 就等于2倍蓝色区域面积=2倍红色面积=蓝色面积+红色面积.
下面两个: 两个分布没有重合区域, \(d_1(\mathcal{D},\mathcal{D}')\) 等于2倍的 \(\mathcal{D}\) 的面积=2倍的 \(\mathcal{D}'\) 的面积=2. 这里很容易发现, 无论 \(\mathcal{D}\) 与 \(\mathcal{D}'\) 相隔多远, 差异多大, 只要它们没有重合部分, \(d_1(\mathcal{D},\mathcal{D}')\) 永远等于2.
从上图还能得出一个公式:

\[d_1(\mathcal{D},\mathcal{D'}) = ||\mathcal{D}-\mathcal{D'}||_1=\int |\mathcal{D}(x)-\mathcal{D'}(x)| dx \]

其中 \(\mathcal{D}(x)\) 表示 \(\mathcal{D}\) 的 pdf.

Thm1. 对于任意一个 hypothesis \(h\),

\[\epsilon_T(h)\leq \epsilon_S(h) + d_1(\mathcal{D}_S, \mathcal{D}_T)+\min \{\mathbf{E}_{\mathcal{D}_S}[|f_S(x)-f_T(x)|],\mathbf{E}_{\mathcal{D}_T}[|f_S(x)-f_T(x)|]\} \]

证明:

\[\int |\phi_S(x)-\phi_T(x)| |h(x)-f_T(x)|dx \leq \int |\phi_S(x)-\phi_T(x)| dx=d_1(\mathcal{D}_S,\mathcal{D}_T) \]

其中 \(|h(x)-f_T(x)| \leq 1\), 而 \(\int |\phi_S(x)-\phi_T(x)| dx=d_1(\mathcal{D}_S,\mathcal{D}_T)\) 在前面讲过. 这里再一次体现了前面提到的缺点, 只要不同, 无论\(h,f_T\) 有多远 \(|h(x)-f_T(x)|\)都等于1.
用 \(L^1\) Divergence 来做 bound 有以下两个缺点: 1) 无法从有限的样本来估计; 2) bound 很松.

b) \(\mathcal{H}\) Divergence

Def. 1 给定在输入空间 \(\mathcal{X}\) 上的两个概率分布 \(\mathcal{D}\) 和 \(\mathcal{D'}\), \(\mathcal{H}\) 表示 \(\mathcal{X}\)上的hypothesis space, \(I(h)\) 为指示函数(即\(x\in I(h)\Leftrightarrow h(x)=1\)). 那么, \(\mathcal{D}\) 和 \(\mathcal{D'}\) 之间的 \(\mathcal{H}\) divergence 为:

\[d_{\mathcal{H}}(\mathcal{D},\mathcal{D}')=2\sup_{h\in\mathcal{H}}|\text{Pr}_\mathcal{D}[I(h)]-\text{Pr}_{\mathcal{D}'}[I(h)]| \]

\(I(h)\) 可以理解为 \(h\) 将输入空间分类成 \(1\) 的那部分集合, i.e. \(I(h)=\{x|h(x)=1\}\). 所以 \(d_{\mathcal{H}}\) 就是 \(I(h)\) 在分布 \(\mathcal{D}\) 和 \(\mathcal{D}'\) 上的概率之差, 其中注意 \(\sup\) over all \(h \in \mathcal{H}\), 也就是选取令概率之差最大的那个假设 \(h\).
\(\mathcal{H}\) Divergence 的好处是: 1) 可以使用有限的样本来估计, 也就是 \(d_{\mathcal{H}}\) 可以用 \(\hat{d}_{\mathcal{H}}\) 来近似. 文章给出了 Lemma 2 和 Lemma 1, 分别为 \(\hat{d}_{\mathcal{H}}\) 的计算公式和使用 VC dimension 作为复杂度计算 \(d_{\mathcal{H}}\) 与 \(\hat{d}_{\mathcal{H}}\) 的 bound . 2) \(d_{\mathcal{H}} \leq d_{1}\).
这里 empirical 版本的计算与估计并不重要, 使用不同的复杂度可以得到不同的 bound 方式, 所以跳过 Lemma 1,2.

c) \(\mathcal{H}\Delta\mathcal{H}\) Divergence

首先给出一个定义:
Def. 2: \(h^*\) 为 ideal joint hypothesis, 它最小化了源域和目标域的联合误差(combined error). 用 \(\lambda\) 表示相对应的combined error:

\[h^* = \arg\min_{h\in\mathcal{H}} \{\epsilon_S(h)+\epsilon_T(h)\}\\ \lambda =\epsilon_S(h^*)+\epsilon_T(h^*) \]

然后给出一个新的 hypothesis space: \(\mathcal{H}\Delta\mathcal{H}\)
Def.3 对于一个 hypothesis space \(\mathcal{H}\), 它相对应的 \(\mathcal{H}\Delta\mathcal{H}\) 空间为:

\[g \in \mathcal{H}\Delta\mathcal{H} \Leftrightarrow g(x)=h(x)\oplus h'(x) \text{ for some } h, h'\in\mathcal{H} \]

举个一维输入空间的简单例子: 考虑这样的一个 hypothesis class:

\[\mathcal{H}:=\{h_\alpha: \alpha\in \mathbb{R}\}.\\ h_\alpha(x)=\left\{\begin{matrix} 1, & x\geq \alpha \\ 0, & x < \alpha \end{matrix}\right. \]

那么, 它相应的 \(\mathcal{H}\Delta\mathcal{H}\) 空间就是:

\[\mathcal{H}\Delta\mathcal{H}=\{g_{\alpha_1,\alpha_2}:\alpha_1,\alpha_2\in\mathbb{R}\}.\\ g_{\alpha_1,\alpha_2}=\left\{\begin{matrix} 1, & x\in(\alpha_1,\alpha_2)\\ 0, & o.w. \end{matrix}\right. \]

这时, 将 \(\mathcal{H}\) Divergence 中的假设空间换成 \(\mathcal{H}\Delta\mathcal{H}\) 空间, 就得出了 \(\mathcal{H}\Delta\mathcal{H}\) Divergence. 如果按照定义从头推算一遍就是:

\[d_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)=2\sup_{g \in \mathcal{H}\Delta\mathcal{H}} |\Pr_{\mathcal{D}_S}[I(g)]-\Pr_{\mathcal{D}_T}[I(g)]|\\ =2\sup_{h,h' \in \mathcal{H}} |\Pr_{x\sim\mathcal{D}_S}[h(x)\neq h'(x)]-\Pr_{x\sim\mathcal{D}_T}[h(x)\neq h'(x)]|\\ =2\sup_{h,h' \in \mathcal{H}} |\epsilon_S(h,h')-\epsilon_T(h,h')| \]

其中第二行是因为, \(I(g)\) 即为 \(g(x)=1\) 的那部分输入空间的集合, 由 Def.3 可知, \(g(x)=1\) 等价于 \(h(x)\neq h'(x)\), 虽然不知道具体哪个 \(h,h'\), 但只关心在假设空间中令概率差值最大的那两个.

这同时也十分直观的得到了 Lemma 3:
对任意两个 hypotheses \(h,h'\),

\[|\epsilon_S(h,h')-\epsilon_T(h,h')|\leq\frac{1}{2} d_{\mathcal{H}\Delta\mathcal{H}}(D_S,D_T) \]

有了以上信息, 我们可以用\(d_{\mathcal{H}\Delta\mathcal{H}}\)给出 \(\epsilon_T\) 的上界:
Thm.2: \(\mathcal{H}\) 为 VC-dim = d 的假设空间, \(\mathcal{U}_S, \mathcal{U}_T\) 为来自于 \(\mathcal{D}_S, \mathcal{D}_T\) 的, 大小为 \(m'\) 的样本. 那么对于任意的 \(\delta\in(0,1)\) 和任意的 \(h\in\mathcal{H}\) , 以下不等式至少 \(1-\delta\) 的概率成立:

\[\epsilon_T(h)\leq\epsilon_S(h)+\frac{1}{2}{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)+\lambda \]

同样的, 先忽略 empircal 的那部分. \({d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)\) 表示了两个域的分布之间的差异, 同时与 \(\mathcal{H}\) 有关. \(\lambda\) 表示的是 \(\mathcal{H}\) 在两个域上最小的联合错误率, 其实也蕴含了两个域分布之间的关系, 同时又与 \(\mathcal{H}\) 有关. 所以 \(\epsilon_T(h)-\epsilon_S(h)\) 用 \({d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)\) 和 \(\lambda\) 进行 bound 很合理.
证明十分简单, 主要就是用到 triangle inequality, 文章中也给出了完整的证明过程, 这里就不粘贴了.

5. A learning bound combining source and target training data

现在考虑这样的学习模式:
训练集为 \(S=(S_T,S_S)\), 其中 \(S_T\) 为 \(\beta m\) 个从分布 \(\mathcal{D}_T\) 中采样的实例, \(S_S\) 为 \((1-\beta)m\) 个从分布 \(\mathcal{D}_S\) 中独立采样的实例. 学习的目标是寻找一个 \(h\) 以最小化 \(\epsilon_T(h)\). 这里考虑使用 ERM, 但 Domain adaptation 任务中 \(\beta\) 往往很小, 所以直接最小化 target error 不合适. 作者考虑在训练过程中, 最小化 source error 和 target error 的和:

\[\hat{\epsilon}_\alpha(h)=\alpha\hat{\epsilon}_T(h)+(1-\alpha)\hat{\epsilon}_S(h) \]

其中 \(\alpha\in[0,1]\). 接下来, 文章给出了两个 定理, 分别为 \(\epsilon_T(h)\) 与 \(\epsilon_\alpha(h)\) 之间的bound (Lemma 4) 和 \(\epsilon_\alpha(h)\) 与 \(\hat{\epsilon}_\alpha(h)\) 之间的 bound (Lemma 5).

Lemma. 4:
对于任意一个 \(h\in\mathcal{H}\),

\[|\epsilon_\alpha(h)-\epsilon_T(h)|\leq(1-\alpha)\left(\frac{1}{2} d_{\mathcal{H}\Delta\mathcal{H}}(D_S,D_T)+\lambda \right) \]

证明同样依赖于 用到 triangle inequality:

而且如果把 Lemma 4 左边的 \(\epsilon_\alpha\) 展开, 再左右两边消掉 \((1-\alpha)\), 此时 Lemma 4 与 Thm.2 其实是等价的.

Lemma 5: 对于一个 hypothesis \(h\), 如果训练样本是由 \(\beta m\) 个从分布 \(\mathcal{D}_T\) 采样的实例和 \((1-\beta)m\) 个从分布 \(\mathcal{D}_S\) 采样的实例构成的, 且这些实例被 \(f_S, f_T\) 打上标签. 那么, 对于任何的 \(\delta\in(0,1)\), 下式至少有 \(1-\delta\) 的概率成立:

\[\Pr[|\hat{\epsilon}_\alpha(h)-\epsilon_\alpha(h)|\geq \epsilon]\leq\exp[\frac{-2m\epsilon^2}{\frac{\alpha^2}{\beta}+\frac{(1-\alpha)^2}{1-\beta}}] \]

证明依赖于 Hoeffding Inequality, 我在这篇博客中给了 2) Chernoff bound, Hoeffding's Lemma, Hoeffding's inequality 定理的介绍和推导.
证明:
按 \(\hat{\epsilon}_{\alpha}\) 的定义和 empirical error 的定义展开, 有:

这个形式就很容易观察了.
令 \(X_1,..., X_{\beta m}\) 表示值为 \(\frac{\alpha}{\beta}|h(x)-f_T(x)|\) 的随机变量.
令 \(X_{\beta m + 1},..., X_{m}\) 表示值为 \(\frac{1-\alpha}{1-\beta}|h(x)-f_S(x)|\) 的随机变量.
那么, 很容易计算出 \(\hat{\epsilon}_{\alpha}(h)=\frac{1}{m}\sum_{i=1}^m X_i\) , 且 \(\mathbf{E}[\hat{\epsilon}_{\alpha}(h)]=\epsilon_{\alpha}(h)\), 所以直接应用 Hoeffding Inequality 就得到 Lemma 5 的不等式.

Thm.3: \(\mathcal{H}\) 为 VC-dim=d 的假设空间, \(\mathcal{U}_S\) 和 \(\mathcal{U}_T\) 为从 \(\mathcal{D}_S\) 和 \(\mathcal{D}_T\) 采样得到的 \(m'\) 个 unlabeled 的实例. \(S\) 是从 \(\mathcal{D}_S\) 采样得到的 \((1-\beta)m\) 个 labeled 的实例和 \(\mathcal{D}_T\) 采样得到的 \(\beta m\) 个 labeled 的实例的集合, 其中使用分别的 ground truth functions \(f_S, f_T\) 进行 labeling. 如果 \(\hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha\), 其中训练集为 \(S\), \(h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T\), 那么, 对于任何的 \(\delta\in(0,1)\), 下式至少有 \(1-\delta\) 的概率成立:

\[\epsilon_T(\hat{h})\leq \epsilon_T(h^*_T)+4\sqrt{\frac{\alpha^2}{\beta}+\frac{(1-\alpha)^2}{1-\beta}} \sqrt{\frac{2d\log(2(m+1))+2\log\frac{8}{\delta}}{m}}+2(1-\alpha)(\frac{1}{2}\hat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{U}_S,\mathcal{U}_T)+4\sqrt{\frac{2d\log(2m')+2\log\frac{8}{\delta}}{m'}}+\lambda') \]

证明文章附录中已给出, 多次应用 Lemma 4 和 5 便可推出结论.

8. Combining data from multiple sources

前几节的结论都是基于一个 source domain 和一个 target domain, 接下来将结论扩展到多个 source domain 的情景.
Several Domain adaptation 设定:

  • 有 N 个 source domains: \(<\mathcal{D}_j, f_j>\), 其中 \(j=1,...,N\).
  • target domain: \(<\mathcal{D}_T, f_T>\), 它也许是或也许不是 N 个 source domains 中的一员.
  • 训练集: \(S=(S_1,...,S_N)\), 其中 \(S_j\) 为 \(m_j = \beta_j m\) 个从分布 \(\mathcal{D}_j\) 采样的有标签的实例, \(\sum \beta_j=1\).
  • 学习目标: 训练一个模型, 使其在 target domain 上表现得好.

还是考虑使用 ERM 作为学习算法, 所以需要定义 empirical error. 由于数据来自于多个域, 所以考虑最简单的方式 - 加权, 即对任意 hypothesis \(h\), 定义它的 empirical \(\alpha\)-weighted error:

\[\hat{\epsilon}_\alpha(h)=\sum_{j=1}^N \alpha_j\hat{\epsilon}_j(h)\\ =\sum_{j=1}^N \frac{\alpha_j}{m_j}\sum_{x\in S_j}|h(x)-f_j(x)| \]

True \(\alpha\)-weighted error:

\[\epsilon_\alpha(h) = \sum_{j=1}^N \alpha_j\epsilon_j(h) \]

其中, 权重为 \(\alpha=(\alpha_1,...,\alpha_N)\) 且 \(\sum \alpha_j=1\).
为了推算出类似于 Thm.3 的结论, 文章又给出了 Lemma 6 和 Thm.4.

8.1 Uniform convergence

这个定理忽略了域之间的差距问题, 只考虑 \(\alpha\) 与 \(\beta\) 的设定对 |empirical - true| 的影响, 文章中将 \(\alpha_j\) 与 \(\beta_j\) 称为 \(S_j\) 的 quality 与 quantity.
Lemma.6: \(S_j\) (\(j=1,...,N\)) 为 \(m_j = \beta_j m\) 个从分布 \(\mathcal{D}_j\) 采样的有标签的实例. \(\alpha\)为任意的权重向量. 对于某些固定的 hypothesis \(h\) 和任意的 \(\delta\in(0,1)\), 下式至少有 \(1-\delta\) 的概率成立:

\[\Pr[|\hat{\epsilon}_\alpha(h)-\epsilon_\alpha(h) |\geq \epsilon]\leq 2\exp (\frac{-2m\epsilon^2}{\sum_{j=1}^N \frac{\alpha_j^2}{\beta_j}}) \]

证明与 Lemma.5 的类似:
在每个域中定义不同的随机变量, 在 \(S_j\) 中: 令 \(X_{j,1},..., X_{j,\beta_j m}\) 表示值为 \(\frac{\alpha_j}{\beta_j}|h(x)-f_j(x)|\) 的随机变量.
然后很容易计算出 \(\hat{\epsilon}_{\alpha}(h)=\frac{1}{m}\sum_{j=1}^m\sum_{\beta_j m}^{i=1} X_{j,i}\) , 且 \(\mathbf{E}[\hat{\epsilon}_{\alpha}(h)]=\epsilon_{\alpha}(h)\), 所以直接应用 Hoeffding Inequality 就得到 Lemma 6 的不等式.

8.2 A bound using pairwise divergence

Thm.4 与 Thm.5 考虑两个 hypotheses 的差别, 分别为用ERM 最小化 empirical \(\alpha\)-weighted error 得到的 hypothesis (\(h^*_T\)) 与在 target domain 上泛化最好的 hypothesis (\(\hat{h}\)). 它们在 target domain 上的错误率的差别可以通过域之间的差别(\(\mathcal{H}\Delta\mathcal{H}\)-divergence)来表示, 不过 \(\mathcal{H}\Delta\mathcal{H}\)-divergence 表示的是 true error 之间的差别, 所以应用上面的Lemma.6 ( true error 与 empirical error 的差别) 可以得到结论.

Thm.4 与 Thm.5 的区别是在用 \(\mathcal{H}\Delta\mathcal{H}\)-divergence 表示域之间的差别时, Thm.4 考虑的是每个 source dist. 与 target dist.之间的差别(不等式a), 而 Thm.5 考虑的是将多个源域分布合并成一个分布, 类似于高斯混合, 然后计算这个混合分布与 target dist. 之间的差别(不等式b).
Thm.4: \(\mathcal{H}\) 为 VC-dim=d 的假设空间, \(S_j\) (\(j=1,...,N\)) 为 \(m_j = \beta_j m\) 个从分布 \(\mathcal{D}_j\) 采样的有标签的实例. 如果 \(\hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha (h)\), 其中训练集为 \(S=\{S_j\}_{j=1}^N\), \(h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T(h)\), 那么, 对于任何的 \(\delta\in(0,1)\), 下式至少有 \(1-\delta\) 的概率成立:

\[\epsilon_T(\hat{h})\leq \epsilon_T(h^*_T)+2\sqrt{(\sum_{j=1}^N\frac{\alpha_j^2}{\beta_j})(\frac{d\log(2m)-\log(\delta)}{2m})}+\sum_{j=1}^N\alpha_j(2\lambda_j+d_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_j,\mathcal{D}_T)) \]

其中, \(\lambda_j=\min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_j(h)\}\) 是域\(j\)与目标域的 combined error.

首先令 \(h_j^*\) 表示域 \(j\) 与目标域的 ideal joint hypothesis, 所以 \(\lambda_j=\epsilon_T(h_j^*)+\epsilon_j(h_j^*)\). 在绝对值内加一项再减一项, 然后将绝对值符号移到外面, 在利用\(h^*\) 的定义与 Lemma.3就得到了图中的结论. 上面的不等式(记为不等式a)适用于所有的 \(h\in\mathcal{H}\), 所以同样适用于 \(\hat{h}\in\mathcal{H}\):

第二行来自于 Lemma.6(|\(\epsilon_\alpha(h)-\hat{\epsilon}_\alpha(h)|\)). 最后一行来自于\(\epsilon_T-\epsilon_\alpha(h)\leq\) 不等式a.

8.3 A bound using combined divergence

与 Thm.4的描述完全相同, 区别在 8.2 中已经介绍.
Thm.5 \(\mathcal{H}\) 为 VC-dim=d 的假设空间, \(S_j\) (\(j=1,...,N\)) 为 \(m_j = \beta_j m\) 个从分布 \(\mathcal{D}_j\) 采样的有标签的实例. 如果 \(\hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha (h)\), 其中训练集为 \(S=\{S_j\}_{j=1}^N\), \(h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T(h)\), 那么, 对于任何的 \(\delta\in(0,1)\), 下式至少有 \(1-\delta\) 的概率成立:

\[\epsilon_T(\hat{h})\leq \epsilon_T(h^*_T)+2\sqrt{(\sum_{j=1}^N\frac{\alpha_j^2}{\beta_j})(\frac{2d\log(2(m+1))-\log(\frac{4}{\delta})}{m})}+(2\gamma_\alpha +d_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_\alpha,\mathcal{D}_T)) \]

其中, \(\mathcal{D}_\alpha\) 是 N 个 source dist.s 的混合分布, 混合的权重即 \(\alpha\) 向量, \(\gamma_\alpha = \min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_\alpha(h)\}\) 是 True \(\alpha\)-weighted error 与 target error 的和. 与不等式a 证明类似, 首先令\(h^*=\arg\min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_\alpha(h)\}\), 那么 \(\gamma_\alpha = \epsilon_T(h^*)+\epsilon_\alpha(h^*)\). 基于此, 文章给了与不等式a类似的bound, 这里将其称为不等式b:

与不等式a 同样的证明方式. 接下来的证明也完全相同, 利用 Lemma.6.