Reproducing Kernel Hilbert Space in Domain Adaptation

Reproducing Kernel Hilbert Space
Domain Adaptation：各种分布距离
- 基于对抗的方法
- 基于核方法的MMD距离
Multi-Source Federated Domain Adaptation
Reference

在A Brief Introduction to Domain Adaptation一文中，我们讨论了Domain Adaptation的数学基础和基本公式，即数据在目标域上的误差，可以由数据在源域上的经验误差，源域与目标域在特征空间上的经验距离估计，以及一个与数据量以及模型容量有关的参数来给定:

$\epsilon_{T}(h)\leq \hat{\epsilon}_{S}(h)+\lambda(\epsilon_{S},\epsilon_{T}) + \hat{d}_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T) +\text{Const}(d,m) \tag{1}$

在实际应用中， $\lambda\text{与Const}$ 是我们无法支配的参数。现有模型思路往往是在最小化源域经验误差 $\hat{\epsilon_{S}}(h)$ 时，构造损失函数最小化模型在特征空间上的差距 $\hat{d_{\mathcal{H}}}(\mathcal{D_S},\mathcal{D_T})$ 。依据对 $\hat{d_\mathcal{H}}$ 进行度量与优化的不同方法，Domain Adaptation模型可以分为以下两类:

基于对抗训练的模型
基于MMD距离的模型

其中，前者通过优化J-S Divergency来对 $\mathcal{A}-\text{distance}$ 作出估计，而后者则通过核方法(kernel method)构造源域与目标域分布的假设检验，计算MMD距离以估计 $\hat{d}_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)$ 。本文的主要目的是在再生希尔伯特核空间(Reproducing Kernel Hilbert Space)，依据特征空间的度量选择，构建起这些方法的联系。本文主要按以下顺序展开：首先，我们构建Reproducing Kernel Hilbert Space的相关定义，并结合Domain Adaptation的论文，介绍几个常用的Kernel。然后，我们从最基本的 $\mathcal{A}-\text{distance}$ 概念出发，探索不同的Domain Adaptation方法所依据度量的异同，并简要介绍Wasserstein GAN的基本概念。最后，我们比较不同的Domain Adaptation方法的有效性，并顺势推导出我们组所做联邦域迁移工作的数学表达。

本文主要参考资料为

此外，我们还在叙述中引用了一些文章，我们并不完全采用它们的叙述逻辑，但是也同样在文末列出参考文献。

Reproducing Kernel Hilbert Space

在本节中，我们介绍内积，希尔伯特空间，以及再生Hilbert核空间的相关概念。在介绍这些概念之前，我们援引Gretton中的相关例子，简要介绍一下核方法以及它的重要性。

RKHS-Example

上图描述了核函数的两个例子。核函数，是一种将输入特征映射到更高维空间，以使得它在高维空间线性可分的函数。当然，也并非所有核函数都会将特征映射到更高维空间。如文本例子中采用的word-to-vector方法，将文本转化为词频向量，从而让两个本文可以区分开。因此，我们找核函数的目的，就是找到一个将输入映射到某种可分空间的函数。我们用数学语言对这种函数进行表达： RKHS-Space 简单来说，核函数可以理解为一种距离函数，它定义了任意样本空间 $\mathcal{X}$ 上两个样本 $x_{1}, x_{2}$ 的”距离”，这种距离通过将样本映射到某个希尔伯特空间，然后通过计算内积得到。核方法的好处在于其对样本空间 $\mathcal{X}$ 没有任何限定，这就给出了对离散输入数据，如图像，音频，文本等相似度计算的方法。注意到我们常用的内积一般就是逐点相乘相加，因此如果我们将 $\phi(x)$ 展开成向量表达

$\phi(x)= [\hat{\phi}_1(x),\ldots,\hat{\phi}_p(x)]_{1\times p}\tag{2}$

那么，内积可以写成求和的形式，这种形式是非常常用的证明技巧:

$k(x,x')=\sum_{i=1}^{p}\hat{\phi}_i(x)\hat{\phi}_i(x')$

如果核函数是无穷维的，那么只要 $\Vert \phi(\cdot)\Vert_2^2\leq \infty$ ，我们也可以写成

$k(x,x')=\sum_{i=1}^{\infty}\hat{\phi}_i(x)\hat{\phi}_i(x')$

给定一个核函数后，我们可以对它进行推广，简单而言，核函数相乘，相加，进行可以泰勒展开的变换，都可以得到新的核函数，即以下四条定理：

RKHS-Theory

通过这四条定理，我们可以得到无数的核。比如，通过这四条定理，我们可以证明， $\exp(-\frac{\Vert x-x’\Vert_2^2}{\gamma^2})$ 是一个kernel，证明过程如下:

$\Vert x-x'\Vert_2^2 = \langle x,x\rangle + \langle x',x'\rangle -2 \langle x,x' \rangle$

因此

$\exp(-\frac{\Vert x-x'\Vert_2^2}{\gamma^2}) = \exp(-\frac{\Vert x\Vert _2^2+\Vert x'\Vert _2^2}{\gamma^2})\exp(\frac{2\langle x,x' \rangle}{\gamma^2})$

其中，对于固定的一组 $\exp(-\frac{\Vert x\Vert _2^2+\Vert x’\Vert _2^2}{\gamma^2})$ ，我们认为它是一个常数(比如模型的正则化约束)，而 $\exp(\frac{2\langle x,x’ \rangle}{\gamma^2})$ 是一个kernel，因此我们得到了一个指数核。

给定一个到希尔伯特空间的映射 $\phi$ ，我们可以唯一确定一个核 $k(x,x’):\mathcal{X}\times \mathcal{X} \rightarrow \mathbb{R}$ 。那么，如果给定一个映射 $k(x,x’)$ ，我们是否能说它就是一个kernel呢？按照定义而言，最直觉的方法就是把kernel对应的 $\phi$ 给挖出来。但是，这个 $\phi$ 往往很难找，同时，一个kernel可能会对应多个 $\phi$ ，因此，我们急需一个更简单的定理来对是否是核进行判断，这就有了正定定理：

RKHS-PD

这个定理就是说，内积一定是正定的，而对于一个函数 $k(x,x’)$ ，如果它的Gram矩阵是正定的，那么一定可以找到一个Hilbert空间，以及一个对应的映射 $\phi$ ，使得它是一个核。Gretton教程中，对一些著名kernel进行了分解，得到了 $\phi$ 的坐标基形式(如 $(2)$ 中所述)，包括基于傅里叶变换的kernel以及RBF kernel。我们上文中提到，kernel的作用是找到一个希尔伯特空间，使得该空间上的数据可分。对于RBF kernel而言，它的映射 $\phi$ 所对应的是无穷维希尔伯特空间，那么我们选择空间的某些维度，当然就可以使得它线性可分。利用这种性质，我们可以构造一类基于核的线性映射 $f(x)$ ，它满足

$f(x)=\sum_{j=1}^{p}f_{j}\hat{\phi}_j(x)=\langle f,\phi(x) \rangle$

其中 $f\text{是}\phi(x)$ 前的系数。对于这类线性映射，我们可以构造它们的回归模型为

$\min_{f\in \mathbb{R}^p}\sum_{i=1}^{N}(y-\langle f,\phi(x) \rangle)^2+ \lambda \Vert f\Vert_2^2 \tag{3}$

而在优化过程中，我们往往可以将求 $\phi(x)$ 这个苦差事变成求 $\langle\phi(x_i),\phi(x_j)\rangle$ ，此时就可以直接采用计算核函数以及对应的gram矩阵来解决。注意，就算我们采用了无穷维核，即 $\phi(x)\in \mathbb{R}^{\infty}$ ，我们的计算过程中也仍然无需触碰无穷维。以上文的核岭回归问题为例，一般我们最终计算所得的其实是每个样本所支撑的系数 $\alpha_i$ ，即

$f=\sum_{i=1}^{N}\alpha_i\phi(x_i)$

此时对 $f(x)$ 的计算可以利用核函数进行，即

$f(x)=\sum_{i=1}^N\alpha_ik(x,x_i)$

在上述基于核函数的回归问题求解中，我们发现，对每一个样本点 $x$ ，我们可以利用核函数 $k$ ，”再生”出一种从输入空间 $\mathcal{X}$ 到实数域 $\mathbb{R}$ 上的新函数：

$k(\cdot,x)=\langle\phi(\cdot),\phi(x)\rangle:\mathcal{X}\rightarrow\mathbb{R}$

这个函数是以样本点 $x$ 作为支撑的，而核所具有的这种性质就叫做再生性质。如果我们更广泛地考虑一类泛函空间 $\mathcal{H}$ ， $\mathcal{H}$ 为非空样本集合 $\mathcal{X}$ 到实数域 $\mathbb{R}$ 的所有映射的空间，对于给定的核 $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ ，如果这个空间满足如下性质，我们称它为Reproducing Kernel Hilbert Space，同时称 $k$ 为这个空间的Reproducing Kernel:

$\forall x \in \mathcal{X}, k(\cdot,x)\in \mathcal{H}$ ,
$\forall x \in \mathcal{X},\forall f\in {H},f(x)=\langle f,\phi(x) \rangle$

为了方便起见，我们采用一些记号

$f(x)=\langle f(\cdot),k(\cdot,x) \rangle_{\mathcal{H}}$

此时，我们可以将 $k(x,y)$ 扩展到这个空间上

$k(x,y)=\langle(k(\cdot,x),k(\cdot,y))\rangle_{\mathcal{H}}$

Domain Adaptation：各种分布距离

在第一节中，我们介绍了Kernel以及Reproducing Kernel Hilbert Space的相关概念。这些概念描述了一个故事，即样本之间可以通过核函数度量距离，而这个距离是样本在更高维空间上的投影。此外，我们可以对这个更高维空间构造平面区分样本点。而Domain Adaptation的目的则是希望模型所习得的特征”无法被区分”，我们可以用Reproducing Kernel Hilbert Space的概念构造距离完成这一目的。Domain Adaptation最原始的公式是

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

其中

$d_1(\mathcal{D}_S,\mathcal{D}_T) = 2 \sup_{B\subset \mathcal{X}}\vert \Pr_{\mathcal{D}_S}(B)-\Pr_{\mathcal{D}_T}(B)\vert$

该距离被称作为Total Variation，我们在Wasserstein Distance一章中介绍过，它具有closed form，但是需要知道分布函数的具体形式才能计算，因此，我们提出了第二种表达形式，即 $\mathcal{H}-\text{distance}$ 以及它的变种 $\mathcal{H\Delta H}-\text{distance}$

$d_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)=2 \sup_{h\in \mathcal{H}}\vert \Pr_{\mathcal{D}_S}(I(h))-\Pr_{\mathcal{D}_T}(I(h))\vert \tag{4}$

$d_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T) = 2\sup_{h,h'\in \mathcal{H}}\vert E_{\mathcal{D}_S}\vert h(\mathbf{x})-h'(\mathbf{x})\vert- E_{\mathcal{D}_T}\vert h(\mathbf{x})-h'(\mathbf{x})\vert \vert \tag{5}$

这两种距离的优化目标都是 $\mathcal{H}$ 空间上的泛函，而优化方法可以分为两类：基于对抗的方法与基于核函数的方法。

基于对抗的方法

寻找 $(4),(5)$ 两式在Domain Adaptation场景下的最优解过程与训练对抗生成网络(GAN)是有相似性质的。首先，我们可以把(4)等价变形为

$d_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)=2 \sup_{h\in \mathcal{H}}\mathbf{E}_{x\in \mathcal{D}_S}h(x) -\mathbf{E}_{x\in \mathcal{D}_T}h(x)$

这就是Wasserstein GAN的损失函数，因此，我们可以把域迁移问题看作是一个对抗生成的过程，其输入的潜变量 $z$ 是来自源域和目标域的不同样本，将从样本空间到分类特征空间的映射看作是生成器，然后构造判别器 $h\in \mathcal{H}$ ，通过Min-Max训练方法令特征空间层面 $\Pr(S),\Pr(T)$ 分布一致。用同样的方法，我们可以将 $(5)$ 变形为

$d_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T) = 2\sup_{h,h'\in \mathcal{H}} \mathbf{E}_{\mathcal{D}_S} (h(\mathbf{x})-h'(\mathbf{x}))- \mathbf{E}_{\mathcal{D}_T} (h(\mathbf{x})-h'(\mathbf{x}))$

此时，只需要构造两个分类判别器，在判别器层面让它们彼此特征远离，在生成器层面让它们的特征接近，这就是[1]中所用的思想。

基于核方法的MMD距离

在第一节中，我们介绍了核方法。简单而言，一个核对应着一个函数 $\phi$ ，这个函数可能将低维数据映射到无穷维(RBF Kernel)，使得数据在高维空间可分。利用这一点，我们可以构造MMD距离，从而绕过不稳定的对抗部分。通过构造Reproducing Kernel Hilbert Space(RKHS)，令我的函数空间 $\mathcal{H}$ 足够复杂，那么我就可以直接进行Min部分，直接让源域特征和目标域特征尽量接近，MMD距离就是在这种思路下导出的。

首先，我们以RKHS为基础，介绍一下kernel mean embedding的概念。对于一个给定的reproducing kernel $k(x,x’)=\langle\phi(x),\phi(x’)\rangle$ ，kernel mean embedding旨在给出映射 $\phi$ 在某一数据分布函数 $\mathbb{P}(x)$ 的”期望映射函数”：

$\phi(\mathbb{P})=\mu_{\mathbb{P}}=\int_{\mathcal{X}}k(\cdot,x) d\mathbb{P}(x)$

注意 $\phi(\mathbb{P})=\mu_{\mathbb{P}}$ 本身也是一个属于 $\mathcal{X}\rightarrow \mathbb{R}$ 的映射，我们结合分布的概念，依据目标核 $k(x,x’)$ 给出了”映射函数的期望”。这个期望当然可以通过有限数据点计算，即

$\hat{\mu_{\mathbb{P}}}=\frac{1}{N}\sum_{i=1}^N k(\cdot,x_i)$

现在将我们的目光转向 $d_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)$ 在RKHS空间下的等价形式

$d_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T) = \sup_{h\in \mathcal{H}}\mathbf{E}_{x\in \mathcal{D}_S}f(x)-{E}_{x\in \mathcal{D}_T}f(x)\tag{6}$

利用RKHS的特性

$h(x)=\langle h(\cdot),k(\cdot,x)\rangle$

我们将 $(6)$ 写成

$d_{\mathcal{H}}(\mathcal{D}_S,\mathcal{D}_T)=\sup_{h\in \mathcal{H}}\langle h,\int_{X}k(\cdot,x) d\mathbb{P}_S(x)\rangle-\langle h,\int_{X}k(\cdot,x) d\mathbb{P}_T(x)\rangle$

不失一般性，我们对 $h\text{加上约束}\Vert h\Vert_2^2\leq 1$ ，得到最终形式为

$\text{MMD}(\mathcal{D}_S,\mathcal{D}_T)=\sup_{\Vert h\Vert_2^2\leq 1}\langle h,\mu_{\mathbb{P}_S}-\mu_{\mathbb{P}_T}\rangle$

为了利用核的性质，我们采用平方距离，即

$\text{MMD}^2(\mathcal{D}_S,\mathcal{D}_T)=\mathbf{E}_{x,x'\sim \mathcal{D}_S}k(x,x')+\mathbf{E}_{x,x'\sim \mathcal{D}_T}k(x,x')-2\mathbf{E}_{x,x'\sim \mathcal{D}_S,\mathcal{D}_T}k(x,x')\tag{7}$

[2,3]都是用 $(7)$ 来进行的域迁移，方法都是在特征层上利用RBF Kernel计算MMD距离，计算复杂度通过一些方法可以降低到o(n)，同时，MMD距离可以纳入域适应的基本公式

$\epsilon_{T}(h)\leq \epsilon_{S}(h)+\lambda(\epsilon_{S},\epsilon_{T}) + 2*\text{MMD}(\mathcal{D}_S,\mathcal{D}_T)+\text{Const}(d,m)$

无独有偶，MMD距离同样被用在了GAN的训练上[4]，从而取代了discriminator，但是实际效果并不好。

Multi-Source Federated Domain Adaptation

联邦域迁移领域遇到的主要问题是中间特征无法通信，这样就无法直接计算MMD距离。我们的MSFDA模型提出了利用模型中BatchNorm部分的running mean与running var来对MMD距离进行优化。

如果我们采用二次内积核，即

$k(x,x')=(\langle x,x' \rangle+1)^2$

代入 $(7)$ ，我们可以得到距离的等价形式为

$\text{MMD}^2(\mathcal{D}_S,\mathcal{D}_T) =(\mathbf{E}_{\mathcal{D}_S}[x]-\mathbf{E}_{\mathcal{D}_T}[x])^2+(\mathbf{E}_{\mathcal{D}_S}[x^2]-\mathbf{E}_{\mathcal{D}_T}[x^2])^2$

即要求源域与目标域上特征的均值方差一致。我们采用的方法是，每个Client在每个训练Epoch后，采集模型中所有BatchNorm部分所得的running mean与running var，然后我们将所有Client的running mean与running var用联邦平均算法，结合我们用Shapley Value计算出的权重进行加权平均，并分发到每一个源域上。因为running mean与running var采用momentum进行更新，因此在下一个Epoch的前一半部分，模型都可以看作是固定均值方差，要求在当下的均值方差下正则化的特征仍然能减少分类任务损失。我们发现，在实际使用中，这种方法的效果很好，在效果上等价于直接计算MMD特征。

Reference

[1] Maximum Classifier Discrepancy for Unsupervised Domain Adaptation

[2] Learning Transferable Features with Deep Adaptation Networks

[3] Moment Matching for Multi-Source Domain Adaptation

[4] Training generative neural networks via Maximum Mean Discrepancy optimization