迁移成分分析(TCA)方法简介

浏览: 2185

问题背景

机器学习中有一类非常有效的方法叫做降维(dimensionality reduction),用简单的话来说就是,把原来很高维度的数据(比如数据有1000多列)用很少的一些代表性维度来表示(比如1000多维用100维来表示)而不丢失关键的数据信息。这些降维方法多种多样,比如:主成分分析(PCA,principal component analysis)、局部线性嵌入(LLE,locally linear embedding)、拉普拉斯特征映射(Laplacian eigen-map)等。这些方法的过程大体都是一个大的矩阵作为输入,然后输出一个小矩阵。那么在迁移学习中,有没有这样的方法,通过降维来达到数据维度减少,而且能达到迁移学习目的呢?答案是显然的,就是我们要说的迁移成分分析(TCA,transfer component analysis)。看,名字就跟PCA很像。

TCA最早是由香港科技大学杨强教授团队提出,首次出现在AAAI-09上,后来整理丰富成了一篇期刊文章,发表在11年的IEEE Trans. Neural Network(现在这个期刊名字后面多了and Learning System)上。这个方法是迁移学习领域经典性的文章,从2011年到现在接近6年过去,在Google scholar上引用量为569次,并且在持续增长。

简介

TCA属于基于特征的迁移学习方法。那么,它做了一件什么事呢?用通俗的语言来说,跟PCA很像:PCA是一个大矩阵进去,一个小矩阵出来,TCA呢,是两个大矩阵进去,两个小矩阵出来。从学术角度讲,TCA针对domain adaptation问题中,源域和目标域处于不同数据分布时,将两个领域的数据一起映射到一个高维的再生核希尔伯特空间。在此空间中,最小化源和目标的数据距离,同时最大程度地保留它们各自的内部属性。直观地理解就是,在现在这个维度上不好最小化它们的距离,那么我就找个映射,在映射后的空间上让它们最接近,那么我不就可以进行分类了吗?

我一直强调,任何问题都要看它的本质,TCA本质是什么呢?完成迁移学习的要求。迁移学习的要求是什么呢?让源域和目标域距离尽可能小呗。

方法

有许多种方法都在试图减小源域和目标域的距离,那么,TCA的贡献在哪里?以我的理解,TCA将这个计算距离的方法变得通用而简单,这就是它最大的贡献。下面我以自己的理解介绍TCA方法的基本流程。

假设

任何方法都基于一定的假设。胡适说过,大胆假设,小心求证。但是他那个时候没有计算机,我们搞计算机的人则是,大胆假设,更大胆求证。为啥?我们就算失败了也没有什么嘛,最多把电脑搞崩溃了我再重装系统么。所以,搞学术一定不要怕假设。假设是学术成功的基石呢!

TCA的假设是什么呢?很简单:源域和目标域的边缘分布是不一样的,也就是说,P(X_S) \ne P(X_T),所以不能直接用传统的机器学习方法。但是呢,TCA假设存在一个特征映射$\phi$,使得映射后数据的分布P(\phi(X_S)) \approx P(\phi(X_T)),更进一步,条件分布P(Y_S | \phi(X_S)) \approx P(Y_T | \phi(X_T))。这不就行了么。好了,我们现在的目标是,找到这个合适的$\phi$,一作映射,这事就解决了。

具体

但是世界上有无穷个这样的\phi,也许终我们一生也无法找到这样的\phi。庄子说过,吾生也有涯,而知也无涯,以有涯随无涯,殆已!我们肯定不能通过穷举的方法来找\phi的。那么怎么办呢?

回到迁移学习的本质上来:最小化源域和目标域的距离。好了,我们能不能先假设这个\phi是已知的,然后去求距离,看看能推出什么呢?

更进一步,这个距离怎么算?世界上有好多距离,从欧氏距离到马氏距离,从曼哈顿距离到余弦相似度,我们需要什么距离呢?TCA利用了一个经典的也算是比较“高端”的距离叫做最大均值差异(MMD,maximum mean discrepancy)。这个距离的公式如下:

dist(X'_{src},X'_{tar})= \begin{Vmatrix} \frac{1}{n_1} \sum \limits_{i=1}^{n_1} \phi(x_{src_i}) - \frac{1}{n_2}\sum \limits _{i=1}^{n_2} \phi(x_{tar_i}) \end{Vmatrix}_{\mathcal{H}}

看着很高端(实际上也很高端)。MMD是做了一件什么事呢?简单,就是求映射后源域和目标域的均值之差嘛。

事情到这里似乎也没什么进展:我们想求的\phi仍然没法求。

TCA是怎么做的呢,这里就要感谢矩阵了!我们发现,上面这个MMD距离平方展开后,有二次项乘积的部分!那么,联系在SVM中学过的核函数,把一个难求的映射以核函数的形式来求,不就可以了?于是,TCA引入了一个核矩阵K

K=\begin{bmatrix}K_{src,src} & K_{src,tar}\\K_{tar,src} & K_{tar,tar}\end{bmatrix}

以及L:

L_{ij}=\begin{cases} \frac{1}{{n_1}^2} & x_i,x_j \in X_{src},\\ \frac{1}{{n_2}^2} & x_i,x_j \in X_{tar},\\ -\frac{1}{n_1 n_2} & \text{otherwise} \end{cases}

这样的好处是,直接把那个难求的距离,变换成了下面的形式:

trace(KL)-\lambda trace(K)

trace是矩阵的迹,用人话来说就是一个矩阵对角线元素的和。这样是不是感觉离目标又进了一步呢?

其实这个问题到这里就已经是可解的了,也就是说,属于计算机的部分已经做完了。只不过它是一个数学中的半定规划(SDP,semi-definite programming)的问题,解决起来非常耗费时间。由于TCA的第一作者Sinno Jialin Pan以前是中山大学的数学硕士,他想用更简单的方法来解决。他是怎么做的呢?

他想出了用降维的方法去构造结果。\widetilde{K}=({K}{K}^{-1/2}\widetilde{W})(\widetilde{W}^{\top}{K}^{-1/2}{K})={K}WW^{\top}{K}

这里的W矩阵是比K更低维度的矩阵。最后的W就是问题的解答了!

求解

好了,问题到这里,整理一下,TCA最后的优化目标是:

\begin{split} \min_W \quad& \text{tr}(W^\top KLKW) + \mu \text{tr}(W^\top W)\\ \text{s.t.} \quad & W^\top KHKW = I_m \end{split}

这里的$H$是一个中心矩阵,H = I_{n_1 + n_2} - 1/(n_1 + n_2)\mathbf{11}^\top.

这个式子下面的条件是什么意思呢?那个min的目标我们大概理解,就是要最小化源域和目标域的距离,加上W的约束让它不能太复杂。那么下面的条件是什么呢?下面的条件就是要实现第二个目标:维持各自的数据特征。TCA要维持的是什么特征呢?文章中说是variance,但是实际是scatter matrix,就是数据的散度。就是说,一个矩阵散度怎么计算?对于一个矩阵A ,它的scatter matrix就是AHA^\top。这个H就是上面的中心矩阵啦。

解决上面的优化问题时,作者又求了它的拉格朗日对偶。最后得出结论,W的解就是的前m个特征值!简单不?数学美不美?然而,我是想不出的呀!

小结

好了,我们现在总结一下TCA方法的步骤。输入是两个特征矩阵,我们首先计算L和H矩阵,然后选择一些常用的核函数进行映射(比如线性核、高斯核)计算K,接着求({K}L{K}+\mu I)^{-1}{K}H{K}的前m个特征值。仅此而已哦。然后,得到的就是源域和目标域的降维后的数据,我们就可以在上面用传统机器学习方法了。

总结

怎么样,到此为止我们把TCA方法介绍完了。我们回顾一下,它的最核心工作是什么呢?我认为有两点:一是把问题转化成数学问题转化得很彻底;二是最优化求解方法很厉害。我们能从中学习什么呢?求解问题的方法感觉是学不来了,我们又不是数学出身。我们只能照猫画虎,学习人家对问题的转化方式,怎么就能很好地把一个问题转化成数学表示?这也是机器学习和人工智能相关方向研究生最重要的能力!关于TCA的Python和Matlab代码可以参考我的Github:jindongwang/transferlearning

最后说一个TCA的优缺点。优点是实现简单,方法本身没有太多的限制,就跟PCA一样很好用。缺点就是,尽管它绕开了SDP问题求解,然而对于大矩阵还是需要很多计算时间。主要消耗时间的操作是,最后那个伪逆的求解以及特征值分解。在我的电脑上(i7-4790CPU+24GB内存)跑2000*2000的核矩阵时间大概是20秒。

References

[1] TCA原版文章:S. J. Pan, I. W. Tsang, J. T. Kwok and Q. Yang, "Domain Adaptation via Transfer Component Analysis," in IEEE Transactions on Neural Networks, vol. 22, no. 2, pp. 199-210, Feb. 2011.doi: 10.1109/TNN.2010.2091281

[2] Scatter matrix: Scatter matrix | Wikiwand

推荐 0
本文由 焯焯先生 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册