本文解读的是迁移学习的第一篇理论性的文章：《Analysis of Representation for Domain Adaptation》。笔者水平有限，对于解读有错误或不合理的地方还请批评指正！
一般的机器学习都假设训练集和测试集来自同一分布，但实际上在大多数情况下，我们有带标签的源域数据集（目标域不带标签，或者很少部分带标签），希望能训练一个分类器在一个分布不同的目标域上也能取得很好的泛化能力，这就是domain adaptation领域自适应（以下简称DA）。在什么情况下我们能调整一个在源域上训练的分类器，使其能用在目标域上？从直觉上想，一个好的特征表示是关键因素。这篇文献从理论上形式化了这种直觉，给出了domain adaptation的泛化边界，用到了PAC计算学习理论。这篇文献关注的是目标域无标签的情况。
相关符号含义
$\chi$：样本实例集合
$\cal Z$：特征空间
$\cal D$：在$\chi$上的一个分布
$f$：$\chi \to [0, 1]$，$f(x)$代表$x$的标签是1的概率
$\cal R$：表示函数，将实例映射到特征$\cal R: \cal X \to \cal Z$
${\cal D}_S$：源域样本分布
${\cal \tilde{D}}_S$：源域样本在特征空间$\cal Z$上的感应（induced）分布
${\cal D}_T$：目标域样本分布
${\cal \tilde{D}}_T$：目标域样本在特征空间$\cal Z$上的感应分布
$h$：预测函数，从特征空间$\cal Z$到$[0, 1]$
$\epsilon_S(h)$：$h$关于$\cal D_T$的期望误差
${\rm sup}$：上确界
${\rm inf}$：下确界
一般学习问题与DA的形式化
学习问题的定义
一个学习问题被两个参数所确定：在$\chi$上的一个分布$\cal D$，和目标函数（可能是随机的）$f: {\cal X} \to [0, 1]$（本文考虑二分类问题）。表示函数将样本实例映射到特征空间，$\cal R: \cal X \to \cal Z$。表示函数指示了在$\cal Z$上的一个分布，从$\cal Z$到$[0, 1]$的目标函数$\tilde{f}(z)$如下所示：
$$Pr_{\tilde{\cal D}}[B]=Pr_{\cal D} [{\cal R ^ {-1}} (B)]$$
$$\tilde{f}(z)=E_{\cal D}[f(x)|{\cal R}(x)=z]$$
对于任意的$A\subseteq Z$，使得${\cal R ^ {-1}} (B)$是$\cal D$可测量的。也就是说，在分布$\tilde{\cal D}$下的事件$B$的概率，是在分布$\cal D$下，$B$在表示函数$\cal R$的逆下的概率。$z$的标签是1的概率，也就是$\tilde{f}(z)$的值，是用$z$表示的实例$x$的概率的平均值（期望）。注意，即使$f(x)$不是随机函数，$\tilde{f}(z)$也可能是随机函数，这是因为表示函数$\cal R$可以将不同的被$f$标记实例映射到同一个特征表示。
总结一下，这里的学习问题是这样定义的：有个固定的但未知的分布$\cal D$和目标函数$f$，我们选择一个合适的表示函数$\cal R$和合适的假设类${\cal H} \subseteq \lbrace g: {\cal Z}\to \lbrace0, 1\rbrace \rbrace$，去估计标记函数$f$。
DA问题的定义
“域”的含义是实例集$\cal X$的分布$\cal D$。我们假设有两个域，源域（source domain）和目标域（target domain）。${\cal D}_S$是源域样本分布，${\cal \tilde{D}}_S$是源域样本在特征空间$\cal Z$上的感应分布。同样的含义，我们同${\cal D}_T$和${\cal \tilde{D}}_T$表示目标域。$f: {\cal X} \to [0, 1]$是标记规则函数，在源域和目标域上都适用，$\tilde{\cal f}$是$f$在$\cal R$下的感应。
预测函数$h$将特征空间$\cal Z$映射到$[0, 1]$。我们用$\epsilon_S(h)$表示$h$和$f$不一致的概率：
$$
\begin{aligned}
\epsilon_{S}(h) &=\mathrm{E}_{\mathbf{z} \sim \tilde{\mathcal{D}}_{S}}\left[\mathrm{E}_{y \sim \tilde{f}(\mathbf{z})}[y \neq h(\mathbf{z})]\right] \\
&=\mathrm{E}_{\mathbf{z} \sim \tilde{\mathcal{D}}_{S}}|\tilde{f}(\mathbf{z})-h(\mathbf{z})|
\end{aligned}
$$
相似地，我们用$\epsilon_T(h)$表示$h$相对于${\cal D}_T$的期望误差。
DA的泛化边界
DA的各种方法适用带标签的源域数据训练分类器，它会在目标域数据集上有泛化误差。这个泛化误差包括两项：
- 分类器在源域数据集上的误差边界
- 感应的源域边缘分布${\cal D}_S$和感应的目标域边缘分布${\cal D}_T$之间的差异性
文中说一个自然的想法是使用$L_1$或者变分距离来表示这种差异性，但是这种变分距离在实数域分布之间无法通过有限的样本计算得到。作者在这里采用了$\cal A$-距离来表示这种差异性。给定一个域$\cal X$和一个$\cal X$上的子集$\cal A$，$\cal D$和${\cal D}^{\prime}$是在$\cal X$上的概率分布，这两个分布的$\cal A$-距离定义为：
$d_{\mathcal{A}}\left(\mathcal{D}, \mathcal{D}^{\prime}\right)=2 \sup_{A \in \mathcal{A}}\left|\operatorname{Pr}_{\mathcal{D}}[A]-\operatorname{Pr}_{\mathcal{D}^{\prime}}[A]\right|$
为了使用$\cal A$-距离，我们需要限定$f$的复杂度。如果说下式成立，那么我们说${\tilde f:{\cal Z} \to [0, 1]}$关于${\tilde {\cal D}_S}$和${\tilde {\cal D}_T}$是$\lambda$-接近于$\cal H$的：
$$\mathop {\rm inf}_{h \in {\cal H}}[\epsilon_S(h)+\epsilon_T(h)] \leq \lambda$$
Theorem 1：
${\cal R}$是从$\cal X$到$\cal Z$的表示函数，$\cal H$是VC维为$d$的假设类空间，如果$m$条随机样本是从应用了${\cal R}$函数的${\cal D}_S$分布上独立同分布地采样得到，其标签由$f$标记，那么对于每个$h \in {\cal H}$，下式至少以$1-\delta$的概率成立：
$$
\epsilon_{T}(h) \leq \hat{\epsilon}_{S}(h)+\sqrt{\frac{4}{m}\left(d \log \frac{2 e m}{d}+\log \frac{4}{\delta}\right)}+d_{\mathcal{H}}\left(\tilde{\mathcal{D}}_{S}, \tilde{\mathcal{D}}_{T}\right)+\lambda
$$
边界取决于$d_{\cal H}({\tilde {\cal D}_S},{\tilde {\cal D}_T})$，这里选择$\cal A$-距离，因为我们可以从有限个样本中估计它。
Theorem 2：
${\cal R}$是从$\cal X$到$\cal Z$的表示函数，$\cal H$是VC维为$d$的假设类空间，如果$m$条随机样本是从应用了${\cal R}$函数的${\cal D}_S$分布上独立同分布地采样得到，其标签由$f$标记；并且 ${\tilde {\cal U}_S}$ 和${\tilde {\cal U}_T}$ 是从 ${\tilde {\cal D}_S}$ 和 ${\tilde {\cal D}_T}$ 上采样得到的无标签样本，都分别有 $m^{\prime}$ 个，那么对于每个 $h \in {\cal H}$，下式至少以 $1-\delta$ 的概率成立：
$\epsilon_{T}(h) \leq \hat{\epsilon}_{S}(h)+\frac{4}{m} \sqrt{\left(d \log \frac{2em}{d}+\log \frac{4}{\delta}\right)}+\lambda+d_{\mathcal{H}}\left(\tilde{\mathcal{U}}_{S}, \tilde{\mathcal{U}}_{T}\right)+4 \sqrt{\frac{d \log \left(2 m^{\prime}\right)+\log \left(\frac{4}{\delta}\right)}{m^{\prime}}}$
之前我们假设$\lambda$对于合理的$\cal R$是足够小的，所以上式中第一项和第四项是主要的，表示函数$\cal R$直接影响了他们。第一项是经验训练误差，第四项是域之间的$\cal A$-距离。我们可以看出一个好的表示函数$\cal R$对于降低训练误差和$\cal A$-距离是至关重要的。
$\cal A$-距离的计算
前面说明了$\cal A$-距离是可以通过有限多样本估计出来的。而且$\cal A$-距离和学习一个分类器$h$紧密相关，这个分类器是区分样本来自于哪个分布。假设我们有两个分别从${\tilde {\cal D}_S}$和${\tilde {\cal D}_T}$上采样得到的样本集${\tilde {\cal U}_S}$和${\tilde {\cal U}_T}$，它们分别有${\tilde m^{\prime}}$个，分类器$h$就是要将 ${\tilde {\cal U}_S}$ 和 ${\tilde {\cal U}_T}$ 区别开。$h$的误差为：
$\operatorname{err}(\mathrm{h})=\frac{1}{2 \mathrm{m}^{\prime}} \sum_{\mathrm{i}=1}^{2 \mathrm{m}^{\prime}}\left|\mathrm{h}\left(\mathbf{z}_{\mathrm{i}}\right)-\mathrm{I}_{\mathrm{z}_{\mathrm{i}} \in \tilde{\mathcal{U}}_{\mathrm{S}}}\right|$
是在${\tilde {\cal U}_S}$上的指示函数。不幸的是，即使是估计任意分布的最优超平面分类器的误差，也是NP难问题。而我们选择通过最小化误差的凸上限来估计最优超平面分类器，则$\cal A$-距离通过下式计算：
$d_{A}\left(\tilde{\mathcal{U}}_{S}, \tilde{\mathcal{U}}_{T}\right)=2\left(1-2 \min_{h^{\prime} \in \mathcal{H}} \operatorname{err}\left(\mathrm{h}^{\prime}\right)\right)$
值得注意的是，这并没有为我们提供目标域错误的有效上限，但它仍然为我们提供了有关领域自适应表示的有用方面。
实验
这部分作者使用的数据集是语音标记数据集，从金融领域（source domain）到生物领域（target domain）。先选择表示函数$\cal R$，再用$\cal R$得到表示训练一个分类器。本文使用的都是线性映射，包括identity映射、随机映射和SCL（structural correspondence learning）。原始数据的维数为$d^{\prime}$，这里将其映射至$d$维空间。
随机映射使用随机映射矩阵$P \in {\Bbb R}^{d \times d^{\prime}}$，$P$从${\cal N}(0, 1)$中独立同分布地采样得到。Johnson-Lindenstrauss定理保证了只要$d$足够大，随机映射可以很好地接近原始高维空间里的距离。SCL时一种启发式DA方法，首先选择一个在所有域中出现频率最高的“中心”特征，然后其他特征用这些“特征”表示，最后使用共现计数矩阵的低秩近似作为投影矩阵P。
实验结果如下两个图所示：
图1(a)是使用SCL后两个域之间的可视化，图1(a)是使用随机映射后两个域的可视化，使用近似线性鉴别器来鉴别不同的域。图1(b)是使用SCL后不同类别的可视化。对比图1(a)和图1(b)，关于域的分类器表现得很差，而类别分类器表现得比较好。域分类器表现得差即误差$err(h)$很大，根据前文section3 $\cal A$-距离的计算公式，那么$\cal A$-距离很小。类别分类器的表现得好，经验分类误差比较小。这说明SCL找到了一个比较好的表示使得经验分类误差和$\cal A$-距离都很小。从图2(b)看，identity映射的类别经验分类误差$\hat {\epsilon}_{S}(h)$ 很小（在带标签的训练数据上的经验误差，也就是源域，这里使用 Huber loss 作为损失，损失越小经验误差越小），但$\cal A$-距离很大，导致目标域的分类误差比较大（即表格中的Error列）。随机映射的 $\cal A$-距离虽然很小，但经验误差很大，导致目标域分类误差很大。只有SCL的经验误差和$\cal A$-距离都很小，最后目标域分类误差也是其中最小的。这些结果也正验证了Theorem 2，Theorem 2说 $\epsilon_{T}(h)$取决于公式中的第一项和第四项，即经验训练误差和域之间的$\cal A$-距离，只有两者皆小才能达到较低的目标域分类误差。而SCL在两者都得到了较小的值，所以它的目标域分类误差是最小的。