最优传输论文（九）：Multi-source Domain Adaptation via WJDOT论文原理

摘要
本文提出了一种新的多源域领域自适应方法，加权联合分布最优传输（WJDTO，Weighted Joint Distribution Optimal Transport），用于解决跨域自适应问题。该方法通过加权调整源域的权重，利用源域的多样性，同时找到源分布和目标分布之间的最优运输，并优化源域的重新加权。WJDTO在理论上提供了泛化界，并通过数值实验验证了其在模拟数据和真实数据集上的有效性。与现有方法相比，WJDTO在性能和方差方面表现更优。此外，该方法通过重新加权源域样本，能够更有效地利用源域数据。未来研究方向包括引入正则化和同时估计嵌入函数。
关键词
最优传输、领域自适应、多源域、加权联合分布最优传输、泛化界、性能评估
引言
多源域领域自适应（MSDA）是机器学习中的一个重要研究方向，旨在解决源域和目标域分布不同时的自适应问题。传统的多源域领域自适应方法主要关注于通过联合分布的重新加权或特征提取来降低泛化误差。然而，这些方法在实际应用中可能存在以下问题：1）泛化界不够紧，导致性能不稳定；2）对目标域标签的依赖性较强，难以在无标签的情况下进行训练。
方法
加权联合分布最优传输（WJDTO）
WJDTO是一种基于最优传输理论的多源域领域自适应方法，其核心思想是通过加权调整源域的权重，利用源域的多样性，同时找到源分布和目标分布之间的最优运输。具体步骤如下：
重新加权源域：对每个源域分配一个权重α_s，使得所有源域的加权和与目标域分布接近。
最优运输优化：通过求解加权联合分布的最优运输问题，找到源分布和目标分布之间的最优映射。
分类器优化：在优化过程中，同时训练分类器，使其能够适应目标域的分布。
泛化界
WJDTO提供了泛化界，表明通过优化加权联合分布的最优运输，可以有效降低泛化误差。具体而言，泛化误差可以表示为：

ε{\text{泛化}} ≤ ε{\text{训练}} + \text{泛化界项}

其中，ε_{\text{训练}}是训练集上的误差，泛化界项由源域和目标域的分布差异决定。
实验
模拟数据集
在模拟数据集上，WJDTO通过加权调整源域的权重，能够更有效地利用源域数据，并在性能和方差方面优于其他方法。此外，WJDTO的权重分配结果表明，估计的权重趋向于稀疏，并且将更多的质量放在具有相似角度的源域上。
实际数据集
在Caltech-Office数据集上，WJDTO在性能和方差方面优于其他方法。此外，WJDTO的权重分配结果表明，估计的权重趋向于稀疏，并且将更多的质量放在具有相似角度的源域上。
结论
WJDTO是一种有效的多源域领域自适应方法

目录

• 引言
• 原理阐述
• 摘要
  • 概述
  • 最优运输与域适应理论
  • 多源域适应：加权JDOT方法（WJDOT）

• • 基于多源域适应的一般化界限

  • 加权联合分布的最优运输问题

    • Numerical experiments

  • Conclusion

前言

本文为我最优传输 系列中的第九篇，该专栏致力于记录本人攻读研究生期间与最优传输相关的论文原理及复现工作。本专栏主要聚焦于阐述最优传输论文的原理，论文的具体翻译及复现代码可在文章的GitHub仓库中找到。

原理阐述

摘要

• 多源域自适应问题。
• 本文用于应对Covariate shift和Target shift问题。
• 本文不寻求在源域和目标域之间找到一个不变量表示（representation invariant），而是通过微调源域权重来利用多源域分布的多样性。
• 我们提出的方法命名为加权联合分布最优传输（WJDOT），旨在同时实现源分布与目标分布基于最优传输的对齐，并对源分布进行重新加权。我们探讨了该方法的理论基础，并提供了一个概念上简单的算法。数值实验表明，该方法在模拟数据集和真实数据集上表现最佳。

介绍

• 本文发表于2020年的arXiv。
• 本文的作者从一个崭新的角度来试图完成多源域的领域自适应。作者不是在源域和目标域之间寻找潜在的表示不变量（representation invariant），而是利用了源域分布的多样性，根据手头的任务来调整其权重。
• 作者的模型：Weighted Joint Distribution Optimal Transport (WJDOT)，旨在同时找到一个基于最优传输的源和目标分配之间的对齐和源域的新的权重 。
• 在多源域领域自适应（MSDA）方面，涌现了很多解决办法。例如，[13,14]提供了如何使用代理度量(如假设的准确性)组合多个来源预测器的理论保证 。该方法在假设目标分布可以写成源分布的凸组合的前提下，可以实现目标域上的低误差预测 。其他最近的方法[15,16,17]寻找一个唯一的假设，使其误差在所有源域上的凸组合 最小化，并提供该假设在目标域上的误差的理论边界 。这些保证通常涉及到一些取决于每个源分布和目标分布之间的距离的术语，建议使用对抗学习[16,18,19]或力矩匹配（Moment Matching）[15]找到源和目标之间特征分布尽可能接近的嵌入 。然而，当源/目标边界之间的距离如图1所示很小时，就不可能找到保持嵌入判别的方法，其中源之间的旋转阻止了[20]中理论上的不变嵌入的存在（这句话并不是特别明白 ）。
• 而在本文，作者的角度与上述常见方法不同。作者没有寻找所有源分布都与目标分布相似的潜在表示，而是使用源分布的多样性，寻找与目标距离最小的源的联合分布的凸组合（a convex combination of the joint distribution of sources with minimal distance to the target one,），而不是参考一个代理度量（proxy measure），比如源预测器的准确性 。在推导了包含该距离的目标的新泛化界之后，作者提出优化Wasserstein距离，该距离定义在特征/标签产品空间上 ，类似于[10]中提出的，但是距离是在目标域和标记源的加权和之间。
• 作者的方法的一个独特的特点是，权值与分类函数是同时学习的，这允许我们基于源和目标在特征和输出空间中的相似性来分配质量（mass，其实就是根据相似度设置概率向量）。
• 所谓凸组合：设向量\{x_i\},i=1,…,n，如果有实数λ_i>=0，且\displaystyle\sum^n_{i=1}λ_i=1，则称\displaystyle\sum^n_{i=1}λ_ix_i为向量\{x_i\}的一个凸组合。
• 符号定义：S设置为源域的数量，每个源域都有对应的特征和标签。假设存在一个可微的嵌入函数（differentiable embedding function）：g： X → G，G是嵌入空间（embedding space），假设所有的输入分布都在这个嵌入空间。假设p_s是源域s的真实分布，p^{T}是目标域的真实分布，被包含在乘积空间G×Y，其中Y是标签空间。在实践中我们只获得源域有限数量\{N_s\}^S_{S = 1}的样本来获得经验源域分布p'_s = (1/Ns) \displaystyle\sum_{i = 1}^{N_s}δ_{g (x^i_s),y^i_s}。在目标域我们只能使用特征空间中有限数量的未标记样本得到µ' = (1/N) \displaystyle\sum_{i = 1}^{N}δ_{g(x^i)},即经验目标域边缘分布。给定一个损失函数L和一个联合分布p，函数f的期望损失定义为ε_p(f) = E_{(x,y)∞p}[L(y,f(x)]。

Optimal Transport and Domain Adaptation

在本节中，作者回顾了最优运输问题和Wasserstein距离的概念，这些内容在其方法中扮演了核心角色。随后，阐述了如何在联合配送最优运输(JDOT)框架中运用这些概念进行域调整，这将是本方法的关键。关于OT问题的回顾，我就不赘述了，因为每篇论文都会对此进行介绍。**Joint Distribution Optimal Transport (JDOT)：**该框架下，公式如下：

\text{JDOT} = \arg\min_{\gamma} \mathcal{L}(\gamma)

其中，\gamma代表联合分布，\mathcal{L}(\gamma)为损失函数。

可以通过涉及联合概率分布，不使用边缘概率分布来实现目标。即为下述问题：

然而，目标域的真实标签不可获取，因此我们采用预测值来进行估计，从而构建经验概率分布，即
p'^f=(1/N)\displaystyle\sum^N_{i=1}δ_{g(x^i),f(g(x^i))}
最终的优化目标即为：

其中，损失函数为D()=β||g(x_1) − g(x_2)||^2+L(y_1,f(g(x_2)))，其中参数β用于平衡特征损失和标签损失。随后，我们将其扩展至深度学习框架中，参考文献[11]（**该论文也十分经典，讲解： ）介绍了一种有效的随机优化方法，该方法同时估计了嵌入函数g和分类器f。

作者指出，优化问题本质上涉及到了联合嵌入和标签分布（joint embedding/label distribution），而现有的大多数DA方法一般性而言主要关注边缘分布。

Multi-source DA with Weighted JDOT (WJDOT)

在本节中，作者提出了一个新的基于源分布权重的MSDA问题的上界。随后，详细阐述了WJDTO优化问题，并提出了一种基于该问题的求解算法。最后，重点分析了WJDTO与现有方法之间的关系。

Generalization bound for multi-source DA

领域适应的理论极限已获得充分研究与理解，基于[27]的研究，该理论指出若目标分布与源分布差异过大，适应则不可能实现。然而，在MSDA框架下，可借助源域的多样性，仅选择与目标分布较为接近的源域数据，从而实现更优的泛化性能。为此，ML[13]研究了相关假设，具体而言，该假设认为目标分布是源分布的凸组合。以下引理将阐述该方法的理论基础。

其中h对应于输入到结果的映射（此处符号f被标记），而H则构成h（即f）的集合。p^α=\displaystyle\sum^S_{s=1}α_sp_s表示对S个概率分布的耦合，其中α_s属于凸组合，D_{TV}(p^α,p^T)表示两个概率分布之间的距离。

ε_D用于衡量预测结果与真实结果之间的差异，因此，我们希望找到一个能够约束损失的上界。这使得ε_D成为一个衡量损失上界的工具。通过约束损失的期望，我们能够得到一个损失期望的上界，这为理论分析提供了依据，同时在优化过程中，我们不断调整和优化这个上界。

其中f_D是真实的映射，上式缩写：

其中B是泛化界generalization bound，
再重新看引理下的公式：

这个简单的不等式（其证明见附录）揭示了，目标泛化的核心要素在于在联合源分布中构建一个误差较小的函数f，并且这一构建过程需要确保该组合与目标分布保持高度契合（即源分布的凸组合应与目标域高度相似）。值得注意的是，这一发现同样适用于单源DA问题，验证了近期研究中发现的仅依赖边际分布可能不够充分的观点[28]。

（在继续之前，先看看定理1的证明 ）然后给出引理1的证明：

其中

就是期望的公式，p是概率密度。

尽管该引理为多源域自适应提供了一种简单而系统性的指导原则，然而，该方法无法应用于训练过程，因为其假设目标域中的标签是已知的。然而，在本文中，我们构建了一个适用于现实场景的泛化边界，该边界在实际应用中并不依赖于目标域标签。通过自标记策略，我们能够弥补标签缺失的问题。

受到引理1结果的启发，该研究者在此基础上构建了一个跨领域学习的理论框架。该方法建立在如下核心思想的基础上：通过假设标签函数f来弥补目标标签的不足。该函数定义了联合分布p^{f，其中通过搜索f，使得p}f与源分布的加权组合得以对齐。在此基础上，我们引入了一系列泛化界。

定理1：

H为映射函数集合，假设输入空间满足对所有f ∈ H，有|f(x) − f(x')| ≤ M，并考虑以下相似性测度的定义：
Λ(p^α, p^T) = \min_{f∈H}ε_pα(f) + ε_{p^T}(f)，该测度量化真实目标分布与源分布之间的“最优”组合差异。当目标标签无法获取时，无法最小化Λ(p^α, p^T)，但可最小化关于f和α的W_D(p^α,p^f)。根据下述定理，通过引入样本复杂性到瓦瑟斯坦距离中，可细化上述界限。

值得注意的是，有趣的是，边界中的1/N_s比率由权重α_s决定，这意味着即使某个源的采样质量较差，只要权重α_s较小，其影响也不会显著。上述两个定理表明，通过优化预测值和源分布的权重α，可以类似于JDOT损失的项来最小化泛化误差。这就是我们建议在以下方面所做的工作。

需要改写的内容

当时阅读joint distribution optimal transportation for domain adaptation相关内容时，对这一部分理解不够透彻，只要知道它提供了泛化界即可。PS，感觉这篇文章在理论层面上与上文差别不大，大概只是主要关注了多源域的组合。

Weighted Joint distribution OT problem

• WJDTOptimizationProblem: 该研究的策略致力于实现两个分布的对齐，其中一个是通过函数f生成的分布p^f，另一个是通过凸组合\sum_{s=1}^S α_s p'_s得到的分布。该研究将多源适应问题建模为一个数学优化问题，通过寻找最优函数f，使得生成的分布与目标分布达到最佳对齐。

这里的优化目标是α和f，见下图：

左边展示了四个源域的分布情况，每个领域分为两个类别。中间左侧的图表展示了二维空间中源域和目标域的样本分布情况，其中目标域样本未标注，因此显示为黑色。中间右侧应用了最优权重α=[0,0.5,0.5,0]，这意味着只有源域2和3具有非零权重，这是因为它们在Wasserstein距离上最接近目标分布。右图展示了分类器预测的标签。

Optimization algorithm 最优化算法：首先，这个最优化问题（8） 可以借鉴之前那篇论文中的方法，即采用分块坐标下降法。该算法在文献中是这样描述的：

主要体现在依次固定一个变量，然后优化另一个变量。然而，作者通过研究表明，当引入权重α后，容易陷入表现欠佳的局部最优解。为了克服上述问题，作者采用了基于分类器f的参数θ和源域权重α 的交替投影梯度下降算法（算法名称）：

关于该方法，网上的相关信息较为匮乏，我对此仍存诸多疑问，后续将进行补充。需要注意的是，最小化W距离是一个关键点，同时我们还必须考虑转移矩阵r。joint distribution optimal transportation for domain adaptation的文章则探讨了r和f的结合使用，采用了坐标下降法。然而，本文在此基础上引入了另一个参数α。但值得注意的是，我们并未同时使用三个参数进行坐标下降，而是首先固定了另外两个参数，仅对r进行优化，这实际上是一个OT问题，此前我们已经讨论过许多解决方案。具体来说，我们首先固定了另外两个参数，仅对r进行优化，这实际上是一个OT问题，此前我们已经讨论过许多解决方案。随后，我们固定了r，对α和f进行了投影梯度下降优化（因为坐标下降法在此场景下表现不够理想）。

作者提及时，WJDOT与JDOT具有相似性，但WJDOT将JDOT扩展至多源域领域自适应问题（MSDA）。具体而言，作者指出，实现WJDOT在MSDA中存在两种方法。第一种方法建议将所有源域样本均匀地组合成一个源域分布，其中每个源域的权重α保持一致。这种分布被用于JDOT，但这种做法忽略了源域与目标域之间的距离，强行将它们统一处理。第二种方法则建议，对每个源域分布分别计算JDOT，然后求和。值得注意的是，WJDOT的实现依赖于样本的权重，在源域内这些权重是共享的。这与领域适应方法中的重要性加权经验风险最小化（IWERM） [31] 类似，IWERM主要用于解决协变量偏移（Covariate shift）问题。然而，WJDOT在这一方面与IWERM存在显著区别，即我们仅估计α中相对较少的权重，这在统计估计上更为高效。此外，作者强调，JCPOT [30] 方法虽然在处理目标转移方面与WJDOT存在差异，但其核心目标与WJDOT相似。JCPOT仅利用特征余量（feature marginals）来估计类别的比例，而WJDOT则通过优化联合嵌入/标签空间（joint embedding/label space）中的瓦瑟斯坦距离来同时估计比例和分类器。这种差异使得WJDOT在处理目标转移时具有独特的优势。最后，作者指出，尽管WJDTO在实现上依赖于样本的权重，但这种权重的估计在高维空间中面临挑战，因为连续密度的估计在高维空间中是一个极具难度的问题。

Numerical experiments

在本节中，作者首先阐述了WJDOT的具体实现方案。随后，对所提出的该方法进行了评估，并将其与当前最先进的MSDA方法进行了对比，具体涵盖了模拟数据和真实数据。WJDOT的实际实现：在所有的数值实验中，作者采用了基于算法1的WJDOT方案进行求解。值得注意的是，嵌入g的估计在本研究中被纳入了分析框架，具体通过多任务学习框架实现。

f_s本质上是一个标签分类损失函数。换句话说，作者将g的生成任务单独进行预训练，而非将其与域适应任务同时纳入模型训练。

• 然后作者提到另一个重要的任务是如何进行参数验证和早期停止（early stop），在无监督的数据采集中，由于缺乏用于验证的目标样本，这一直是一个难题。为了克服这个问题，作者使用估计的输出 f(X)和它们在目标数据上的估计聚类质心之间的平方误差之和(sum of squared errors，SSE)。
• Compared methods： 作者将它的方法与下面的MSDA方法进行比较，其中两种方法是JDOT公式的不明显的扩展。其中CJDOT法将所有的源样本连接成一个源分布。MJDOT正好对应第二种方法，对于所有的源域都优化该式\displaystyle\sum _s W(p_s,p^f)。对于这两种方法，作者使用上面提到的SSE方法进行提前止损。重要性加权经验风险最小化(Importance Weighted Empirical Risk Minimization，IWERM) [31]，这是ERM的一种变体，其中样本通过目标和源密度的比率加权，最小化每个源的IWERM目标之和（minimizing the sum of the IWERM objective for each sources）。DCTN是[18]的深层混合网络，其中对抗学习被用来学习特征提取器、领域鉴别器和源分类器。领域鉴别器提供多个源-目标特定的困惑分数（perplexity scores），用于加权源特定的分类器预测并产生目标估计。最后，M^3SDA是在[15]中为MSDA提出的矩匹配方法，其中嵌入是通过对准源和目标分布的矩来学习的。请注意，在DCTN和M^3SDA中，嵌入学习是方法的核心，因此它们对于固定的嵌入g是不可行的。因此，我们仅在必须估计g时才与这些方法进行比较。然后作者训练了一个baseline，就是专门使用源域的数据进行训练一个分类器，使得其在多个源域数据上的表现做好，这个方法是为了检测这个源域分类器是否具有对域的鲁棒性，是不是能在目标域上表现良好（当然基本是不可能的，不过这也是一种对比实验，就相当于不使用任何域适应手段，看看仅仅对源域训练分类器能否在目标域表现良好，基本可以作为最差模型 ）。既然提供了“最差的”情况，当然还要准备最好的模型，就是将目标域样本及标签 也加入到训练过程中，即baseline+target，其中target部分训练一个分类器仅仅用于目标域样本及标签，当然这容易过拟合，因为目标域样本及标签不多。因为最后这两种方法是有标签的（即baseline和baseline+target），所以我们使用验证集，比例为7:2:1。
• Simulated data： 我们考虑一个类似于图1所示的分类问题，但是有3个类，即Y = {0，1，2}。对于源域和目标域，作者是这样生成数据的：

作者进行了多组实验，以考察多种参数的影响，如源域数量、源样本数量以及目标样本数量等。随后，作者在图2中展示了精度图，其中左边的源域数量为3，同时满足N_s=N=300，而右边的源域数量为30，如图所示。

WJDTO在性能和方差方面显著优于所有竞争方法，即使是在有限源数量的情况下。值得注意的是，WJDTO甚至能够超越Target，这得益于它能够访问更多的样本信息。WJDTO的另一个关键点是通过模型获得了可用于解释的权重α。从图2可以看出，估计的权重趋向于具有稀疏性，并且将更多的权重分配给了具有相似角度的源。

Object recognition： Caltech-Office 数据集将图像划分为四个不同的领域：Amazon、Caltech [37]、Webcam 和 DSLR。这些领域之间的来源差异主要归因于背景的存在与否、光照条件的差异以及噪声等因素。研究者采用了预训练的DeCAF模型[38]的第七层输出作为嵌入函数G，类似于文献[9]中的方法，嵌入空间G属于R^4096。

值得注意的是，文献中指出，经过训练，最终只有一个源域的权重被赋予了非零值，具体数值为1，其余源域的权重均为0。其中，能够最接近目标域的源域，即权重非零的域，正是表现出最佳性能的那个域。在实际编码过程中，这一现象得到了验证。基于梯度下降算法，最终仅保留了损失函数最小的源域，其权重值为1，其余源域的权重均为0。在实际编码过程中，这一现象得到了验证。

Conclusion

作者指出，未来的工作计划包括研究α的正则化，并将采用WJDOT这一技术来同时估计嵌入g，而非采用多任务学习进行预训练。