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

防盗 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.

  • < D S , f S > <\mathcal{D}_S, f_S> <DS,fS> 表示 source domain, 前者是 source dist, 后者是 source dist. 上的 ground truth function.
  • < D T , f T > <\mathcal{D}_T, f_T> <DT,fT> 表示 target domain, 同上.
  • h : X → { 0 , 1 } h:\mathcal{X}\rightarrow \{0,1\} h:X{0,1} 表示一个从输入空间映射到二分类集合的 hypothesis.
  • 在分布 D S \mathcal{D}_S DS 上, 两个 hypotheses h h h f f f 的平均差异定义为:
    ϵ S ( h , f ) = E x ∼ D S [ ∣ h ( x ) − f ( x ) ∣ ] \epsilon_S(h,f)=\mathbf{E}_{x\sim \mathcal{D}_S}[|h(x)-f(x)|] ϵS(h,f)=ExDS[h(x)f(x)]
    由于 h h h f f f 的输出是 0 或 1, 所以只有它们输出不同时, 期望中间的部分为 1, 所以上式为两个hypotheses之间的平均差异(或 disagreements).
  • source error of h h h: ϵ S ( h ) = ϵ S ( h , f S ) \epsilon_S(h)=\epsilon_S(h,f_S) ϵS(h)=ϵS(h,fS), 也就是 h h h 在source domain 上的错误率 (generalization error).
  • empirical source error of h h h: ϵ ^ S ( h ) \hat{\epsilon}_S(h) ϵ^S(h), 也就是 h h h 在source domain 上的经验错误率 (empirical error).
  • 相同的, 在 target domain 上的 notations: ϵ T ( h , f ) , ϵ T ( h ) , \epsilon_T(h,f),\epsilon_T(h), ϵT(h,f),ϵT(h), ϵ ^ T ( h ) \hat{\epsilon}_T(h) ϵ^T(h).

4. A bound relating the source and target error

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

a) L 1 L^1 L1 Divergence

也叫 Variation Divergence, Variation Distance, TV Distance.
d 1 ( D , D ′ ) = 2 sup ⁡ B ∈ B ∣ Pr ⁡ D [ B ] − Pr ⁡ D ′ [ B ] ∣ d_1(\mathcal{D}, \mathcal{D}')=2\sup_{B\in\mathcal{B}}|\Pr_\mathcal{D}[B]-\Pr_{\mathcal{D}'}[B]| d1(D,D)=2BBsupDPr[B]DPr[B]
其中 B \mathcal{B} B 是在 D \mathcal{D} D D ′ \mathcal{D}' D 上所有可测子集的集合.
用两个很简单的一维分布来表示一下:
L1 divergence
上面两个: 红色区域和蓝色区域的面积是相等的, 因为面积就是概率. 很明显, 对于这两种情况而言, d 1 ( D , D ′ ) d_1(\mathcal{D},\mathcal{D}') d1(D,D) 就等于2倍蓝色区域面积=2倍红色面积=蓝色面积+红色面积.
下面两个: 两个分布没有重合区域, d 1 ( D , D ′ ) d_1(\mathcal{D},\mathcal{D}') d1(D,D) 等于2倍的 D \mathcal{D} D 的面积=2倍的 D ′ \mathcal{D}' D 的面积=2. 这里很容易发现, 无论 D \mathcal{D} D D ′ \mathcal{D}' D 相隔多远, 差异多大, 只要它们没有重合部分, d 1 ( D , D ′ ) d_1(\mathcal{D},\mathcal{D}') d1(D,D) 永远等于2.
从上图还能得出一个公式:
d 1 ( D , D ′ ) = ∣ ∣ D − D ′ ∣ ∣ 1 = ∫ ∣ D ( x ) − D ′ ( x ) ∣ d x d_1(\mathcal{D},\mathcal{D'}) = ||\mathcal{D}-\mathcal{D'}||_1=\int |\mathcal{D}(x)-\mathcal{D'}(x)| dx d1(D,D)=∣∣DD1=D(x)D(x)dx
其中 D ( x ) \mathcal{D}(x) D(x) 表示 D \mathcal{D} D 的 pdf.

Thm1. 对于任意一个 hypothesis h h h,
ϵ T ( h ) ≤ ϵ S ( h ) + d 1 ( D S , D T ) + min ⁡ { E D S [ ∣ f S ( x ) − f T ( x ) ∣ ] , E D T [ ∣ f S ( x ) − f T ( x ) ∣ ] } \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)|]\} ϵT(h)ϵS(h)+d1(DS,DT)+min{EDS[fS(x)fT(x)],EDT[fS(x)fT(x)]}
证明:
在这里插入图片描述
上图是文章给的证明, 前四行很好理解, 解释下最后一行:
∫ ∣ ϕ S ( x ) − ϕ T ( x ) ∣ ∣ h ( x ) − f T ( x ) ∣ d x ≤ ∫ ∣ ϕ S ( x ) − ϕ T ( x ) ∣ d x = d 1 ( D S , D T ) \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) ϕS(x)ϕT(x)∣∣h(x)fT(x)dxϕS(x)ϕT(x)dx=d1(DS,DT)
其中 ∣ h ( x ) − f T ( x ) ∣ ≤ 1 |h(x)-f_T(x)| \leq 1 h(x)fT(x)1, 而 ∫ ∣ ϕ S ( x ) − ϕ T ( x ) ∣ d x = d 1 ( D S , D T ) \int |\phi_S(x)-\phi_T(x)| dx=d_1(\mathcal{D}_S,\mathcal{D}_T) ϕS(x)ϕT(x)dx=d1(DS,DT) 在前面讲过. 这里再一次体现了前面提到的缺点, 只要不同, 无论 h , f T h,f_T h,fT 有多远 ∣ h ( x ) − f T ( x ) ∣ |h(x)-f_T(x)| h(x)fT(x)都等于1.
L 1 L^1 L1 Divergence 来做 bound 有以下两个缺点: 1) 无法从有限的样本来估计; 2) bound 很松.

b) H \mathcal{H} H Divergence

Def. 1 给定在输入空间 X \mathcal{X} X 上的两个概率分布 D \mathcal{D} D D ′ \mathcal{D'} D, H \mathcal{H} H 表示 X \mathcal{X} X上的hypothesis space, I ( h ) I(h) I(h) 为指示函数(即 x ∈ I ( h ) ⇔ h ( x ) = 1 x\in I(h)\Leftrightarrow h(x)=1 xI(h)h(x)=1). 那么, D \mathcal{D} D D ′ \mathcal{D'} D 之间的 H \mathcal{H} H divergence 为:
d H ( D , D ′ ) = 2 sup ⁡ h ∈ H ∣ Pr D [ I ( h ) ] − Pr D ′ [ I ( h ) ] ∣ 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)]| dH(D,D)=2hHsupPrD[I(h)]PrD[I(h)]
I ( h ) I(h) I(h) 可以理解为 h h h 将输入空间分类成 1 1 1 的那部分集合, i.e. I ( h ) = { x ∣ h ( x ) = 1 } I(h)=\{x|h(x)=1\} I(h)={xh(x)=1}. 所以 d H d_{\mathcal{H}} dH 就是 I ( h ) I(h) I(h) 在分布 D \mathcal{D} D D ′ \mathcal{D}' D 上的概率之差, 其中注意 sup ⁡ \sup sup over all h ∈ H h \in \mathcal{H} hH, 也就是选取令概率之差最大的那个假设 h h h.
H \mathcal{H} H Divergence 的好处是: 1) 可以使用有限的样本来估计, 也就是 d H d_{\mathcal{H}} dH 可以用 d ^ H \hat{d}_{\mathcal{H}} d^H 来近似. 文章给出了 Lemma 2 和 Lemma 1, 分别为 d ^ H \hat{d}_{\mathcal{H}} d^H 的计算公式和使用 VC dimension 作为复杂度计算 d H d_{\mathcal{H}} dH d ^ H \hat{d}_{\mathcal{H}} d^H 的 bound . 2) d H ≤ d 1 d_{\mathcal{H}} \leq d_{1} dHd1.
这里 empirical 版本的计算与估计并不重要, 使用不同的复杂度可以得到不同的 bound 方式, 所以跳过 Lemma 1,2.

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

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

h ∗ = arg ⁡ min ⁡ h ∈ H { ϵ S ( h ) + ϵ T ( h ) } λ = ϵ S ( h ∗ ) + ϵ T ( h ∗ ) h^* = \arg\min_{h\in\mathcal{H}} \{\epsilon_S(h)+\epsilon_T(h)\}\\ \lambda =\epsilon_S(h^*)+\epsilon_T(h^*) h=arghHmin{ϵS(h)+ϵT(h)}λ=ϵS(h)+ϵT(h)
然后给出一个新的 hypothesis space: H Δ H \mathcal{H}\Delta\mathcal{H} HΔH
Def.3 对于一个 hypothesis space H \mathcal{H} H, 它相对应的 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH 空间为:
g ∈ H Δ H ⇔ g ( x ) = h ( x ) ⊕ h ′ ( x ) for some  h , h ′ ∈ H g \in \mathcal{H}\Delta\mathcal{H} \Leftrightarrow g(x)=h(x)\oplus h'(x) \text{ for some } h, h'\in\mathcal{H} gHΔHg(x)=h(x)h(x) for some h,hH
举个一维输入空间的简单例子: 考虑这样的一个 hypothesis class:
H : = { h α : α ∈ R } . h α ( x ) = { 1 , x ≥ α 0 , x < α \mathcal{H}:=\{h_\alpha: \alpha\in \mathbb{R}\}.\\ h_\alpha(x)=\left\{\begin{matrix} 1, & x\geq \alpha \\ 0, & x < \alpha \end{matrix}\right. H:={hα:αR}.hα(x)={1,0,xαx<α
那么, 它相应的 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH 空间就是:
H Δ H = { g α 1 , α 2 : α 1 , α 2 ∈ R } . g α 1 , α 2 = { 1 , x ∈ ( α 1 , α 2 ) 0 , o . w . \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. HΔH={gα1,α2:α1,α2R}.gα1,α2={1,0,x(α1,α2)o.w.
这时, 将 H \mathcal{H} H Divergence 中的假设空间换成 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH 空间, 就得出了 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH Divergence. 如果按照定义从头推算一遍就是:
d H Δ H ( D S , D T ) = 2 sup ⁡ g ∈ H Δ H ∣ Pr ⁡ D S [ I ( g ) ] − Pr ⁡ D T [ I ( g ) ] ∣ = 2 sup ⁡ h , h ′ ∈ H ∣ Pr ⁡ x ∼ D S [ h ( x ) ≠ h ′ ( x ) ] − Pr ⁡ x ∼ D T [ h ( x ) ≠ h ′ ( x ) ] ∣ = 2 sup ⁡ h , h ′ ∈ H ∣ ϵ S ( h , h ′ ) − ϵ T ( h , h ′ ) ∣ 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')| dHΔH(DS,DT)=2gHΔHsupDSPr[I(g)]DTPr[I(g)]=2h,hHsupxDSPr[h(x)=h(x)]xDTPr[h(x)=h(x)]=2h,hHsupϵS(h,h)ϵT(h,h)
其中第二行是因为, I ( g ) I(g) I(g) 即为 g ( x ) = 1 g(x)=1 g(x)=1 的那部分输入空间的集合, 由 Def.3 可知, g ( x ) = 1 g(x)=1 g(x)=1 等价于 h ( x ) ≠ h ′ ( x ) h(x)\neq h'(x) h(x)=h(x), 虽然不知道具体哪个 h , h ′ h,h' h,h, 但只关心在假设空间中令概率差值最大的那两个.

这同时也十分直观的得到了 Lemma 3:
对任意两个 hypotheses h , h ′ h,h' h,h,
∣ ϵ S ( h , h ′ ) − ϵ T ( h , h ′ ) ∣ ≤ 1 2 d H Δ H ( D S , D T ) |\epsilon_S(h,h')-\epsilon_T(h,h')|\leq\frac{1}{2} d_{\mathcal{H}\Delta\mathcal{H}}(D_S,D_T) ϵS(h,h)ϵT(h,h)21dHΔH(DS,DT)
有了以上信息, 我们可以用 d H Δ H d_{\mathcal{H}\Delta\mathcal{H}} dHΔH给出 ϵ T \epsilon_T ϵT 的上界:
Thm.2: H \mathcal{H} H 为 VC-dim = d 的假设空间, U S , U T \mathcal{U}_S, \mathcal{U}_T US,UT 为来自于 D S , D T \mathcal{D}_S, \mathcal{D}_T DS,DT 的, 大小为 m ′ m' m 的样本. 那么对于任意的 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ(0,1) 和任意的 h ∈ H h\in\mathcal{H} hH , 以下不等式至少 1 − δ 1-\delta 1δ 的概率成立:

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

5. A learning bound combining source and target training data

现在考虑这样的学习模式:
训练集为 S = ( S T , S S ) S=(S_T,S_S) S=(ST,SS), 其中 S T S_T ST β m \beta m βm 个从分布 D T \mathcal{D}_T DT 中采样的实例, S S S_S SS ( 1 − β ) m (1-\beta)m (1β)m 个从分布 D S \mathcal{D}_S DS 中独立采样的实例. 学习的目标是寻找一个 h h h 以最小化 ϵ T ( h ) \epsilon_T(h) ϵT(h). 这里考虑使用 ERM, 但 Domain adaptation 任务中 β \beta β 往往很小, 所以直接最小化 target error 不合适. 作者考虑在训练过程中, 最小化 source error 和 target error 的和:
ϵ ^ α ( h ) = α ϵ ^ T ( h ) + ( 1 − α ) ϵ ^ S ( h ) \hat{\epsilon}_\alpha(h)=\alpha\hat{\epsilon}_T(h)+(1-\alpha)\hat{\epsilon}_S(h) ϵ^α(h)=αϵ^T(h)+(1α)ϵ^S(h)
其中 α ∈ [ 0 , 1 ] \alpha\in[0,1] α[0,1]. 接下来, 文章给出了两个 定理, 分别为 ϵ T ( h ) \epsilon_T(h) ϵT(h) ϵ α ( h ) \epsilon_\alpha(h) ϵα(h) 之间的bound (Lemma 4) 和 ϵ α ( h ) \epsilon_\alpha(h) ϵα(h) ϵ ^ α ( h ) \hat{\epsilon}_\alpha(h) ϵ^α(h) 之间的 bound (Lemma 5).

Lemma. 4:
对于任意一个 h ∈ H h\in\mathcal{H} hH,
∣ ϵ α ( h ) − ϵ T ( h ) ∣ ≤ ( 1 − α ) ( 1 2 d H Δ H ( D S , D T ) + λ ) |\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) ϵα(h)ϵT(h)(1α)(21dHΔH(DS,DT)+λ)
证明同样依赖于 用到 triangle inequality:
在这里插入图片描述
而且如果把 Lemma 4 左边的 ϵ α \epsilon_\alpha ϵα 展开, 再左右两边消掉 ( 1 − α ) (1-\alpha) (1α), 此时 Lemma 4 与 Thm.2 其实是等价的.

Lemma 5: 对于一个 hypothesis h h h, 如果训练样本是由 β m \beta m βm 个从分布 D T \mathcal{D}_T DT 采样的实例和 ( 1 − β ) m (1-\beta)m (1β)m 个从分布 D S \mathcal{D}_S DS 采样的实例构成的, 且这些实例被 f S , f T f_S, f_T fS,fT 打上标签. 那么, 对于任何的 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ(0,1), 下式至少有 1 − δ 1-\delta 1δ 的概率成立:
Pr ⁡ [ ∣ ϵ ^ α ( h ) − ϵ α ( h ) ∣ ≥ ϵ ] ≤ exp ⁡ [ − 2 m ϵ 2 α 2 β + ( 1 − α ) 2 1 − β ] \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}}] Pr[ϵ^α(h)ϵα(h)ϵ]exp[βα2+1β(1α)22mϵ2]
证明依赖于 Hoeffding Inequality, 我在这篇博客中给了 2) Chernoff bound, Hoeffding’s Lemma, Hoeffding’s inequality 定理的介绍和推导.
证明:
ϵ ^ α \hat{\epsilon}_{\alpha} ϵ^α 的定义和 empirical error 的定义展开, 有:
在这里插入图片描述
这个形式就很容易观察了.
X 1 , . . . , X β m X_1,..., X_{\beta m} X1,...,Xβm 表示值为 α β ∣ h ( x ) − f T ( x ) ∣ \frac{\alpha}{\beta}|h(x)-f_T(x)| βαh(x)fT(x) 的随机变量.
X β m + 1 , . . . , X m X_{\beta m + 1},..., X_{m} Xβm+1,...,Xm 表示值为 1 − α 1 − β ∣ h ( x ) − f S ( x ) ∣ \frac{1-\alpha}{1-\beta}|h(x)-f_S(x)| 1β1αh(x)fS(x) 的随机变量.
那么, 很容易计算出 ϵ ^ α ( h ) = 1 m ∑ i = 1 m X i \hat{\epsilon}_{\alpha}(h)=\frac{1}{m}\sum_{i=1}^m X_i ϵ^α(h)=m1i=1mXi , 且 E [ ϵ ^ α ( h ) ] = ϵ α ( h ) \mathbf{E}[\hat{\epsilon}_{\alpha}(h)]=\epsilon_{\alpha}(h) E[ϵ^α(h)]=ϵα(h), 所以直接应用 Hoeffding Inequality 就得到 Lemma 5 的不等式.

Thm.3: H \mathcal{H} H 为 VC-dim=d 的假设空间, U S \mathcal{U}_S US U T \mathcal{U}_T UT 为从 D S \mathcal{D}_S DS D T \mathcal{D}_T DT 采样得到的 m ′ m' m 个 unlabeled 的实例. S S S 是从 D S \mathcal{D}_S DS 采样得到的 ( 1 − β ) m (1-\beta)m (1β)m 个 labeled 的实例和 D T \mathcal{D}_T DT 采样得到的 β m \beta m βm 个 labeled 的实例的集合, 其中使用分别的 ground truth functions f S , f T f_S, f_T fS,fT 进行 labeling. 如果 h ^ = arg ⁡ min ⁡ h ∈ H ϵ ^ α \hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha h^=argminhHϵ^α, 其中训练集为 S S S, h T ∗ = arg ⁡ min ⁡ h ∈ H ϵ T h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T hT=argminhHϵT, 那么, 对于任何的 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ(0,1), 下式至少有 1 − δ 1-\delta 1δ 的概率成立:
ϵ T ( h ^ ) ≤ ϵ T ( h T ∗ ) + 4 α 2 β + ( 1 − α ) 2 1 − β 2 d log ⁡ ( 2 ( m + 1 ) ) + 2 log ⁡ 8 δ m + 2 ( 1 − α ) ( 1 2 d ^ H Δ H ( U S , U T ) + 4 2 d log ⁡ ( 2 m ′ ) + 2 log ⁡ 8 δ m ′ + λ ′ ) \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') ϵT(h^)ϵT(hT)+4βα2+1β(1α)2 m2dlog(2(m+1))+2logδ8 +2(1α)(21d^HΔH(US,UT)+4m2dlog(2m)+2logδ8 +λ)
证明文章附录中已给出, 多次应用 Lemma 4 和 5 便可推出结论.

8. Combining data from multiple sources

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

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

还是考虑使用 ERM 作为学习算法, 所以需要定义 empirical error. 由于数据来自于多个域, 所以考虑最简单的方式 - 加权, 即对任意 hypothesis h h h, 定义它的 empirical α \alpha α-weighted error:
ϵ ^ α ( h ) = ∑ j = 1 N α j ϵ ^ j ( h ) = ∑ j = 1 N α j m j ∑ x ∈ S j ∣ h ( x ) − f j ( x ) ∣ \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)| ϵ^α(h)=j=1Nαjϵ^j(h)=j=1NmjαjxSjh(x)fj(x)
True α \alpha α-weighted error:
ϵ α ( h ) = ∑ j = 1 N α j ϵ j ( h ) \epsilon_\alpha(h) = \sum_{j=1}^N \alpha_j\epsilon_j(h) ϵα(h)=j=1Nαjϵj(h)
其中, 权重为 α = ( α 1 , . . . , α N ) \alpha=(\alpha_1,...,\alpha_N) α=(α1,...,αN) ∑ α j = 1 \sum \alpha_j=1 αj=1.
为了推算出类似于 Thm.3 的结论, 文章又给出了 Lemma 6 和 Thm.4.

8.1 Uniform convergence

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

Pr ⁡ [ ∣ ϵ ^ α ( h ) − ϵ α ( h ) ∣ ≥ ϵ ] ≤ 2 exp ⁡ ( − 2 m ϵ 2 ∑ j = 1 N α j 2 β j ) \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}}) Pr[ϵ^α(h)ϵα(h)ϵ]2exp(j=1Nβjαj22mϵ2)
证明与 Lemma.5 的类似:
在每个域中定义不同的随机变量, 在 S j S_j Sj 中: 令 X j , 1 , . . . , X j , β j m X_{j,1},..., X_{j,\beta_j m} Xj,1,...,Xj,βjm 表示值为 α j β j ∣ h ( x ) − f j ( x ) ∣ \frac{\alpha_j}{\beta_j}|h(x)-f_j(x)| βjαjh(x)fj(x) 的随机变量.
然后很容易计算出 ϵ ^ α ( h ) = 1 m ∑ j = 1 m ∑ β j m i = 1 X j , i \hat{\epsilon}_{\alpha}(h)=\frac{1}{m}\sum_{j=1}^m\sum_{\beta_j m}^{i=1} X_{j,i} ϵ^α(h)=m1j=1mβjmi=1Xj,i , 且 E [ ϵ ^ α ( h ) ] = ϵ α ( h ) \mathbf{E}[\hat{\epsilon}_{\alpha}(h)]=\epsilon_{\alpha}(h) E[ϵ^α(h)]=ϵα(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 ∗ h^*_T hT) 与在 target domain 上泛化最好的 hypothesis ( h ^ \hat{h} h^). 它们在 target domain 上的错误率的差别可以通过域之间的差别( H Δ H \mathcal{H}\Delta\mathcal{H} HΔH-divergence)来表示, 不过 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH-divergence 表示的是 true error 之间的差别, 所以应用上面的Lemma.6 ( true error 与 empirical error 的差别) 可以得到结论.

Thm.4 与 Thm.5 的区别是在用 H Δ H \mathcal{H}\Delta\mathcal{H} HΔH-divergence 表示域之间的差别时, Thm.4 考虑的是每个 source dist. 与 target dist.之间的差别(不等式a), 而 Thm.5 考虑的是将多个源域分布合并成一个分布, 类似于高斯混合, 然后计算这个混合分布与 target dist. 之间的差别(不等式b).
Thm.4: H \mathcal{H} H 为 VC-dim=d 的假设空间, S j S_j Sj ( j = 1 , . . . , N j=1,...,N j=1,...,N) 为 m j = β j m m_j = \beta_j m mj=βjm 个从分布 D j \mathcal{D}_j Dj 采样的有标签的实例. 如果 h ^ = arg ⁡ min ⁡ h ∈ H ϵ ^ α ( h ) \hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha (h) h^=argminhHϵ^α(h), 其中训练集为 S = { S j } j = 1 N S=\{S_j\}_{j=1}^N S={Sj}j=1N, h T ∗ = arg ⁡ min ⁡ h ∈ H ϵ T ( h ) h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T(h) hT=argminhHϵT(h), 那么, 对于任何的 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ(0,1), 下式至少有 1 − δ 1-\delta 1δ 的概率成立:
ϵ T ( h ^ ) ≤ ϵ T ( h T ∗ ) + 2 ( ∑ j = 1 N α j 2 β j ) ( d log ⁡ ( 2 m ) − log ⁡ ( δ ) 2 m ) + ∑ j = 1 N α j ( 2 λ j + d H Δ H ( D j , D T ) ) \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)) ϵT(h^)ϵT(hT)+2(j=1Nβjαj2)(2mdlog(2m)log(δ)) +j=1Nαj(2λj+dHΔH(Dj,DT))
其中, λ j = min ⁡ h ∈ H { ϵ T ( h ) + ϵ j ( h ) } \lambda_j=\min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_j(h)\} λj=minhH{ϵT(h)+ϵj(h)} 是域 j j j与目标域的 combined error.

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

在这里插入图片描述
第二行来自于 Lemma.6(| ϵ α ( h ) − ϵ ^ α ( h ) ∣ \epsilon_\alpha(h)-\hat{\epsilon}_\alpha(h)| ϵα(h)ϵ^α(h)). 最后一行来自于 ϵ T − ϵ α ( h ) ≤ \epsilon_T-\epsilon_\alpha(h)\leq ϵTϵα(h) 不等式a.

8.3 A bound using combined divergence

与 Thm.4的描述完全相同, 区别在 8.2 中已经介绍.
Thm.5 H \mathcal{H} H 为 VC-dim=d 的假设空间, S j S_j Sj ( j = 1 , . . . , N j=1,...,N j=1,...,N) 为 m j = β j m m_j = \beta_j m mj=βjm 个从分布 D j \mathcal{D}_j Dj 采样的有标签的实例. 如果 h ^ = arg ⁡ min ⁡ h ∈ H ϵ ^ α ( h ) \hat{h}=\arg\min_{h\in\mathcal{H}} \hat{\epsilon}_\alpha (h) h^=argminhHϵ^α(h), 其中训练集为 S = { S j } j = 1 N S=\{S_j\}_{j=1}^N S={Sj}j=1N, h T ∗ = arg ⁡ min ⁡ h ∈ H ϵ T ( h ) h^*_T=\arg\min_{h\in\mathcal{H}} \epsilon_T(h) hT=argminhHϵT(h), 那么, 对于任何的 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ(0,1), 下式至少有 1 − δ 1-\delta 1δ 的概率成立:
ϵ T ( h ^ ) ≤ ϵ T ( h T ∗ ) + 2 ( ∑ j = 1 N α j 2 β j ) ( 2 d log ⁡ ( 2 ( m + 1 ) ) − log ⁡ ( 4 δ ) m ) + ( 2 γ α + d H Δ H ( D α , D T ) ) \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)) ϵT(h^)ϵT(hT)+2(j=1Nβjαj2)(m2dlog(2(m+1))log(δ4)) +(2γα+dHΔH(Dα,DT))

其中, D α \mathcal{D}_\alpha Dα 是 N 个 source dist.s 的混合分布, 混合的权重即 α \alpha α 向量, γ α = min ⁡ h ∈ H { ϵ T ( h ) + ϵ α ( h ) } \gamma_\alpha = \min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_\alpha(h)\} γα=minhH{ϵT(h)+ϵα(h)} 是 True α \alpha α-weighted error 与 target error 的和. 与不等式a 证明类似, 首先令 h ∗ = arg ⁡ min ⁡ h ∈ H { ϵ T ( h ) + ϵ α ( h ) } h^*=\arg\min_{h\in\mathcal{H}}\{\epsilon_T(h)+\epsilon_\alpha(h)\} h=argminhH{ϵT(h)+ϵα(h)}, 那么 γ α = ϵ T ( h ∗ ) + ϵ α ( h ∗ ) \gamma_\alpha = \epsilon_T(h^*)+\epsilon_\alpha(h^*) γα=ϵT(h)+ϵα(h). 基于此, 文章给了与不等式a类似的bound, 这里将其称为不等式b:
在这里插入图片描述
与不等式a 同样的证明方式. 接下来的证明也完全相同, 利用 Lemma.6.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/154575.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

轻量限制流量?阿里云轻量应用服务器月流量包收费说明

阿里云轻量应用服务器部分套餐限制月流量&#xff0c;轻量应用服务器按照套餐售卖&#xff0c;有的套餐限制月流量&#xff0c;有的不限制流量。像阿里云轻量2核2G3M带宽轻量服务器一年108元和轻量2核4G4M带宽一年297.98元12个月&#xff0c;这两款是不限制月流量的。阿里云百科…

中国植被功能型图(1km分辨率)

简介&#xff1a; 植被功能型&#xff08;PFT&#xff09;是根据植物种的生态系统功能及其资源利用方式而对宠大的植物种进行的组合&#xff0c;每一种植被功能型共享相似的植物属性&#xff0c;是将植物种的多样性简化为植物功能和结构的多样性,用以预测全球变化情景下生态系…

优盘中毒了怎么办?资料如何恢复

在现代社会中&#xff0c;优盘成为我们日常生活与工作中必备的便携式存储设备。然而&#xff0c;正是由于其便携性&#xff0c;优盘也成为病毒感染的主要目标之一。本篇文章将帮助读者了解如何应对优盘中毒的情况&#xff0c;以及如何恢复因病毒感染丢失的资料。 ▶优盘为什么…

简单好用的CHM文件阅读器 CHM Viewer Star最新 for mac

CHM Viewer Star 是一款适用于 Mac 平台的 CHM 文件阅读器软件&#xff0c;支持本地和远程 CHM 文件的打开和查看。它提供了直观易用的界面设计&#xff0c;支持多种浏览模式&#xff0c;如书籍模式、缩略图模式和文本模式等&#xff0c;并提供了丰富的功能和工具&#xff0c;如…

温度在线检测技术在电力电缆线路的应用

在电力电缆的日常运行检测中&#xff0c;针对电缆温度的状况&#xff0c;所采用的电力温度在线检测技术也得到了大范围的普及。电网系统中&#xff0c;其单位时间内可输送的电力能源受到其温度的变化影响。因此&#xff0c;采用更有效的方式实时检测电缆系统运行温度&#xff0…

Linux|qtcreator编译可执行程序双击运行

qt GUI window移植到linux参见&#xff1a;VS|vs2017跨平台编译linux&&CConsole&&QtGUI 参考&#xff1a;QtCreator修改项目的生成目录 文章目录 双击.pro文件&#xff0c;点击configureproject构建项目切换到release模式下双击打开pro文件&#xff0c;修改依赖…

WPF向Avalonia迁移(四、其他事项)

开发必备 1. Avalonia项目源代码&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;没有源代码&#xff0c;你连控件的背景色怎么改都找不着&#xff01;&#xff01; 2.下载你所使用的版本&#x…

【手写数字识别】数据挖掘实验二

文章目录 Ⅰ、项目任务要求任务描述&#xff1a;主要任务要求(必须完成以下内容但不限于这些内容)&#xff1a; II、实现过程数据集描述实验运行环境描述KNN模型决策树模型朴素贝叶斯模型SVM模型不同方法对MNIST数据集分类识别结果分析(不同方法识别对比率表及结果分析) 完整代…

李宏毅 2022机器学习 HW3 boss baseline 上分记录

作业数据是所有数据都有标签的版本。 李宏毅 2022机器学习 HW3 boss baseline 上分记录 1. 训练数据增强, private 0.760562. cross validation&ensemble, private 0.816473. test dataset augmentation, private 0.824584. resnet, private 0.865555. Image Normalizatio…

DP4054H完全兼容替代TP4054 36V 耐压 500mA 线性锂电充电芯片

产品概述&#xff1a; DP4054H是一款完整的采用恒定电流/恒定电压单节锂离子电池充电管理芯片。其SOT小封装和较少的外部元件数目使其成为便携式应用的理想器件&#xff0c;DP4054H可以适合USB 电源和适配器电源工作。由于采用了内部PMOSFET架构&#xff0c;加上防倒充电 路&am…

【微服务】RedisSearch 使用详解

目录 一、RedisJson介绍 1.1 RedisJson是什么 1.2 RedisJson特点 1.3 RedisJson使用场景 1.3.1 数据结构化存储 1.3.2 实时数据分析 1.3.3 事件存储和分析 1.3.4 文档存储和检索 二、当前使用中的问题 2.1 刚性数据库模式限制了敏捷性 2.2 基于磁盘的文档存储导致瓶…

【20】c++设计模式——>组合模式

组合模式定义 C组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;他允许将对象组合成树形结构来表示“部分-整体”的层次结构&#xff1b;在组合模式中有两种基本类型的对象&#xff1a;叶子对象和组合对象&#xff0c;叶子对象时没有子对象…

Websocket获取B站直播间弹幕教程——第二篇、解包/拆包

教程一、Websocket获取B站直播间弹幕教程 — 哔哩哔哩直播开放平台 1、封包 我们连接上B站Websocket成功后&#xff0c;要做两件事情&#xff1a; 第一、发送鉴权包。第二、发送心跳包&#xff0c;每30秒一次&#xff0c;维持websocket连接。 这两个包不是直接发送过去&…

无为WiFi的一批服务器

我们在多个地区拥有高速服务器&#xff0c;保证网速给力&#xff0c;刷片无压力 嘿嘿 <?phpinclude("./includes/common.php"); $actisset($_GET[act])?daddslashes($_GET[act]):null; $urldaddslashes($_GET[url]); $authcodedaddslashes($_GET[authcode]);he…

RxJava介绍及基本原理

随着互联网的迅猛发展&#xff0c;Java已成为最广泛应用于后端开发的语言之一。而在处理异步操作和事件驱动编程方面&#xff0c;传统的Java多线程并不总是最佳选择。这时候&#xff0c;RxJava作为一个基于观察者模式、函数式编程和响应式编程理念的库&#xff0c;为我们提供了…

30WSIP网络有源号角 50W SIP网络有源号角

30WSIP网络有源号角 50W SIP网络有源号角 SIP-7044是我司的一款SIP网络有源号角&#xff0c;具有10/100M以太网接口&#xff0c;内置有一个高品质扬声器&#xff0c;将网络音源通过自带的功放和喇叭输出播放&#xff0c;可达到功率30W。SIP-7044作为SIP系统的播放终端&#xf…

【photoshop学习】用 Photoshop 做的 15 件创意事

用 Photoshop 做的 15 件创意事 每个人总是谈论 Photoshop 的无限可能。您可以使用该程序做很多事情&#xff0c;列表几乎是无穷无尽的。 嘿&#xff0c;我是卡拉&#xff01;如果您花过一些时间使用 在线ps&#xff0c;您可能见过我&#xff08;并且注意到我提到了这一点&am…

一个完整的初学者指南Django-part1

源自&#xff1a;https://simpleisbetterthancomplex.com/series/2017/09/04/a-complete-beginners-guide-to-django-part-1.html 一个完整的初学者指南Django - 第1部分 介绍 今天我将开始一个关于 Django 基础知识的新系列教程。这是一个完整的 Django 初学者指南。材料分为七…

iPhone 15分辨率,屏幕尺寸,PPI 详细数据对比 iPhone 15 Plus、iPhone 15 Pro、iPhone 15 Pro Max

史上最全iPhone 机型分辨率&#xff0c;屏幕尺寸&#xff0c;PPI详细数据&#xff01;已更新到iPhone 15系列&#xff01; 点击放大查看高清图 &#xff01;

[ValueError: not enough values to unpack (expected 3, got 2)]

项目场景&#xff1a; 在使用opencv进行关键点识别、边缘轮廓提取的时候&#xff0c;提示以上错误。 import cv2 import numpy as npdef preprocess(image):# 进行图像预处理&#xff08;例如灰度化、高斯模糊等&#xff09;gray cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)blu…