A Primer on Domain Adaptation Th

作者: 馒头and花卷 | 来源:发表于2020-05-04 19:30 被阅读0次

Pirmin Lemberger, Ivan Panico, A Primer on Domain Adaptation
Theory and Applications, 2019.

概

机器学习分为训练和测试俩步骤, 且往往假设训练样本的分布和测试样本的分布是一致的, 但是这种情况在实际中并不一定成立. 作者就prior shift, covratie shift, concept shift, subspace mapping 四种情形给出相应的'解决方案".

主要内容

符号说明

$\mathbf{x} \in \mathcal{X} \subset \mathbb{R}^p$ : 数据
$y \in \mathcal{Y}=\{\omega_1,\ldots, \omega_k\}$ : 类别标签
$S=\{(\mathbf{x}_1,y_1), \ldots(\mathbf{x_m}, y_m)\}$ : 训练样本
$h \in \mathcal{H}:\mathcal{X} \rightarrow \mathcal{Y}$ : 拟合函数/分类器
$\hat{y}=h(\mathbf{x})$ :预测
$\ell: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}$ : 损失函数
$R[h]:= \mathbb{E}_{(\mathbf{x}, y) \sim p}[\ell(y, h(\mathbf{x})]$ : risk
$\hat{R}[h]:= \frac{1}{m} \sum_{i=1}^m [\ell(y_i, h(\mathbf{x}_i)]$ : 经验风险函数
$p_S$ : 训练数据对应的分布
$p_T$ : 目标数据对应的分布
$\hat{p}$ :近似的分布

Prior shift

$p_S(\mathbf{x}|y)=p_T(\mathbf{x}|y)$ 但 $p_S(y) \not = p_T(y)$ . (如, 训练的时候，对每一类, 我们往往选择相同数目的样本以求保证类别的均衡).

在这里插入图片描述

假设根据训练样本 $S$ 和算法 $A$ ，我们得到了一个近似后验分布 $\hat{p}_S(y|\mathbf{x})$ , 且近似的先验分布 $\hat{p}_S(y=\omega_k)=m_k/|S|$ , 并同样假设 $\hat{p}_S(\mathbf{x}|y)=\hat{p}_T(\mathbf{x}|y)$ , 有
$\tag{9} \hat{p}_T(\omega_k|\mathbf{x})= \frac{\hat{w}(\omega_k)\hat{p}_S(\omega_k|\mathbf{x})}{\sum_{k'=1}^K\hat{w}(\omega_{k'})\hat{p}_S(\omega_{k'}|\mathbf{x})}, \hat{w}(\omega_k):=\frac{\hat{p}_T(\omega_k)}{\hat{p}_S(\omega_k)}.$

倘若我们知道 $\hat{p}_T(\omega_k), k=1,\ldots, K$ , 那么我们就直接可以利用(9)式来针对目标数据集了, 而这里的真正的难点在于, 如果不知道, 应该怎么办.

假设, 我们的目标数据集的样本数据为 $\mathbf{x}_1', \ldots, \mathbf{x}_m'$ , 则我们的目标是求出 $\hat{p}_T(\omega_k|\mathbf{x}')$ , 有
$\tag{10} \hat{p}_T(\omega_k)=\sum_{i=1}^m \hat{p}_T(\omega_k,\mathbf{x}_i')=\frac{1}{m} \sum_{i=1}^m \hat{p}_T(\omega_k|\mathbf{x}_i'),$
其中在最后一个等号部分, 我们假设了 $p(\mathbf{x}_i')=\frac{1}{m}$ , 这个假设并非空穴来风, 我们可以从EM算法角度去理解.

于是, 很自然地, 我们可以利用交替迭代求解
$\tag{11} \hat{p}_T^{(s)}(\omega_k|\mathbf{x}')= \frac{\hat{w}(\omega_k)\hat{p}_S(\omega_k|\mathbf{x}')}{\sum_{k'=1}^K\hat{w}(\omega_{k'})\hat{p}_S(\omega_{k'}|\mathbf{x}')}, \hat{w}(\omega_k):=\frac{\hat{p}_T^{(s)}(\omega_k)}{\hat{p}_S(\omega_k)}. \\ \hat{p}_T^{(s+1)}(\omega_k)=\frac{1}{m} \sum_{i=1}^m \hat{p}_T^{(s)}(\omega_k|\mathbf{x}_i').$

注: 在实际中, 由于各种因素, 这么做反而画蛇添足, 起到反效果, 我们可以通过假设检验来判断是否接受.

在这里插入图片描述

其趋向于 $\chi^2_{(K-1)}$ 对于足够多地样本.

Covariate shift

$p_S(y|\mathbf{x})=p_T(y|\mathbf{x})$ , 但是 $p_S(\mathbf{x})\not = p_T(\mathbf{x})$ .

A covariate shift typically occurs when the cost or the difficulty of picking an observation with given features x strongly impacts the probability of selecting an observation (x, y) thus making it practically impossible to replicate the target feature distribution $p_T(\mathbf{x})$ in the training set.

在这里插入图片描述

我们所希望最小化,
$\tag{14,15} R_T[h]:= \mathbb{E}_{p_T}[\ell(h(\mathbf{x})),y)] =\mathbb{E}_{p_S}[w(\mathbf{x})\ell(h(\mathbf{x})),y)].$
在实际中, 若我们有 $w(\mathbf{x})=p_T(\mathbf{x})/p_S(\mathbf{x})$ 或者其一个估计 $\hat{w}(\mathbf{x})$ , 我们最小化经验风险
$\tag{16} \hat{R}_{S, w} [h]:= \frac{1}{m} \sum_{i=1}^m w(\mathbf{x}_i) \ell(h(\mathbf{x}_i),y_i).$

注: 以下情况不适合用(16):

$p_S(\mathbf{x}_i)=0$ 但是 $p_T(\mathbf{x})_i \not=0$ ;
$p_S, p_T$ 二者差距很大, 使得 $w$ 波动很大.

即 $p_S$ 最好是选取范围和 $p_T$ 近似, 这些是根据下面的理论结果的到的:

在这里插入图片描述
(17)有的可信度.

$\hat{w}$

显然, 解决(16)的关键在于 $\hat{w}:=\hat{p}_T(\mathbf{x})/\hat{p}_S(\mathbf{x})$ , 有很多的概率密度估计方法(如核密度估计(KDE)), 但是在实际应用中, 这种估计可能会导致不可控的差的结果.

一个策略是直接估计 $\hat{w}$ , 而非分别估计 $\hat{p}_T, \hat{p}_S$ :

期望均方误差 $\mathbb{E}_{p_S}[(\hat{w}-p_T/p_S)^2]$ (怎么玩?);
KL散度 $\mathbf{KL}(p_T \| \hat{w}p_S)$ (怎么玩?);
最大平均差异(maximum mean discrepancy, MMD).

KMM

选择kernel $K(\mathbf{x}, \mathbf{y})$ , 相当于将 $\mathbf{x}$ 映入一个希尔伯特空间(RKHS), $\mathbf{x} \rightarrow \Phi_{\mathbf{x}}$ , 其内积为 $\langle \Phi_{\mathbf{x}}, \Phi_{\mathbf{y}} \rangle=K(\mathbf{x}, \mathbf{y})$ . 则MMD定义为:
$(\mathrm{MMD}[\alpha, \beta])^2:=\|\mathbb{E}_{\mathbf{x} \sim \alpha} [\Phi_{\mathbf{x}}]-\mathbb{E}_{\mathbf{x} \sim \beta} [\Phi_{\mathbf{x}}]\|^2= \|\mathbb{E}_{\mathbf{x} \sim \alpha} [\Phi_{\mathbf{x}}]\|^2-2\langle \mathbb{E}_{\mathbf{x} \sim \alpha} [\Phi_{\mathbf{x}}],\mathbb{E}_{\mathbf{x} \sim \beta} [\Phi_{\mathbf{x}}] \rangle+ \|\mathbb{E}_{\mathbf{x} \sim \beta} [\Phi_{\mathbf{x}}]\|^2.$

则令 $\alpha=\hat{w}\hat{p}_S, \beta=\hat{p}_T$ 则

在这里插入图片描述

其中, , .

在实际中, 求解下面的优化问题
$\begin{array}{rc} \min_w & \frac{1}{2} \hat{w}^T K\hat{w} - k^T\hat{w} \\ \mathrm{s.t.} & \hat{w}(\mathbf{x}_i) \in [0,B], \\ & |\frac{1}{m_S} \sum_{i=1}^{m_S} \hat{w}(\mathbf{x}_i) -1| \le \epsilon. \end{array}$
第一个条件为了保证 $\hat{p}_S,\hat{p}_T$ 之间差距不大, 第二个条件是为了保证概率的积分为1的性质.

Concept shift

$p_S(y|\mathbf{x})\not= p_T(y|\mathbf{x})$ ， $p_S(\mathbf{x})=p_T(\mathbf{x})$ . 其往往是在时序系统下, 即分布 $p$ 与时间有关.

周期性地利用新数据重新训练模型;
保留部分旧数据, 结合新数据训练;
加入权重;
引入有效的迭代机制;
检测偏移, 并作出反应.

在这里插入图片描述

Subspace mapping

训练数据为 $\mathbf{x}$ , 而目标数据为 $\mathbf{x}'=T(\mathbf{x})$ , 且 $p_T(T(\mathbf{x}), y) = p_S(\mathbf{x},y)$ ，且 $T$ 是未知的.

我们现在的目标是找到一个有关

Wasserstein distance

以离散情形为例, 介绍,
$\alpha := \sum_{i=1}^m \alpha_i \delta_{\mathbf{z}_i},$
其中 $\delta_{\mathbf{z}}$ 表示狄拉克函数.
$T \alpha := \sum_{i=1}^m \alpha_i \delta_{T(\mathbf{z}_i)},$
则, 自然地, 我们希望
$\arg \min_{T, T\alpha = \beta} \mathbb{E}_{\mathbf{z} \sim \alpha} [c(\mathbf{z}, T(\mathbf{z}))],$
其中 $c(\cdot, \cdot)$ 是我们给定的一个损失函数, 这类问题被称为 Monge 问题.

在这里插入图片描述

但是呢, 这种方式找 $T$ 非常困难, 于是有了一种概率替代方案,
$\tag{30} \gamma := \sum_{i,j} \gamma_{ij} \delta_{\mathbf{z}_i,\mathbf{z}_j'}$
为以离散概率分布, 则
$\tag{33} \mathbb{E}_{(\mathbf{z},\mathbf{z}') \sim \gamma}[c(\mathbf{z},\mathbf{z}')]:=\sum_{i,j} \gamma_{i,j}c(\mathbf{z}_i,\mathbf{z}_j),$
$\tag{34} \mathcal{L}_c (\alpha, \beta) := \min_{\gamma \in U(\alpha, \beta)} \mathbb{E}_{(\mathbf{z}, \mathbf{z}') \sim \gamma}[c(\mathbf{z}, \mathbf{z}')]$
衡量了从分布 $\alpha$ 变换到分布 $\beta$ 的难易程度, 其中
$U(\alpha, \beta):=\{ \gamma: \sum_{j=1}^s \gamma_{ij} =\alpha_i, \sum_{i=1}^r \gamma_{ij} = \beta_j\},$
注意这实际上是一个事实, 因为 $\alpha, \beta$ 是其联合分布 $\gamma$ 的边缘分布.

而Wasserstein distance实际上就是
$\tag{35} W_p(\alpha,\beta) := [\mathcal{L}_{d^p} (\alpha, \beta)]^{1/p}, c(\mathbf{z},\mathbf{z}')=[d(\mathbf{z},\mathbf{z}')]^p, p\ge1.$
$d$ 为一距离.

应用于 subspace mapping

策略一:
$\alpha=\hat{p}_S(\mathbf{x}), \beta=\hat{p}_T(\mathbf{x}')$ , 通过(34)可以找到一个 $\gamma$ , 再利用 $\gamma$ 把训练数据 $S$ 映射到 $\hat{p}_T$ 分布上, 再利用新的训练数据重新训练模型. (? 如何利用 $\gamma$ 变换呢?)

注:为了防止 $(\mathbf{x}_i,y_i),(\mathbf{x}_j,y_j), y_i \not =y_j$ 变换到同一个新数据, 需要添加一个惩罚项.

策略二:
$\alpha=\hat{p}_S(\mathbf{x},y), \beta=\hat{p}_T (\mathbf{x}',y')$ , 但是 $y'$ 我们是不知道的, 所以用 $h(\mathbf{x}')$ 代替, 且
$\hat{p}_T^h(\mathbf{x}',y'):= \hat{p}_T(\mathbf{x}') \delta_{y'=h(\mathbf{x}')},$
于是
$\tag{37} h_{OT} := \arg \min_{h \in \mathcal{H}} W_1(\hat{p}_S, \hat{p}_T^h),$

即
$\tag{38} h_{OT} = \arg \min_{h \in \mathcal{H}} \min_{\gamma \in U(\hat{p}_S, \hat{p}_T^h)} \sum_{i,j} \gamma_{ij} d((\mathbf{x}_i,y_i),(\mathbf{x}_j', h(\mathbf{x}_j'))).$
其中
$d((\mathbf{x},y),(\mathbf{x}', y')) := \lambda \rho(\mathbf{x},\mathbf{x}') + \ell(y,y').$
在实际使用中, 视实际情况而定, 加入惩罚项
$\tag{39} h_{OT} = \arg \min_{h \in \mathcal{H}} \min_{\gamma \in U(\hat{p}_S, \hat{p}_T^h)} \big(\sum_{i,j} \gamma_{ij} [ \lambda \rho(\mathbf{x}_i,\mathbf{x}_j') + \ell(y_i,h(\mathbf{x}_j'))] + \epsilon \mathrm{reg}[h] \big).$

Prior shift 的EM解释

考虑联合概率 $p_{\theta}(\mathbf{x}_1, \ldots, \mathbf{x}_m; \mathbf{z}_1,\ldots, \mathbf{z}_m)$ , 其中 $\mathbf{z}_i,i=1,\ldots, m$ 为隐变量, $\mathbf{x}_i, i=1,\ldots,m$ 为观测变量，EM算法步骤如下:

E步: $\mathbb{E}_{\mathbf{z}}[\log p_{\theta}(\mathbf{x}_1, \ldots, \mathbf{x}_m; \mathbf{z}_1,\ldots, \mathbf{z}_m)]$ (下面是离散情况)

在这里插入图片描述

M步:

在这里插入图片描述

Prior shift中, $\theta:= [p_T(\omega_1), \ldots, p_T(\omega_K)]^{\mathrm{T}}$ , 隐变量 $\mathbf{z}_i:=(z_{i1},\ldots, z_{iK})$ 为 $y_i \in \{\omega_1,\ldots, \omega_K\}$ 的one-hot-encodings. 则