典型关联分析(Canonical Correlation Analysis)

一.CCA的引入

      在一般的线性回归中,我们寻找n维特征向量自变量和应变量之间的线性关系。那么如果应变量也是多维的情况下,我们怎么寻找它们之间的线性关系呢?形式化地描述这个问题: \pmb{X}d \times n的矩阵,其中每一行代表n个特征的数据(或者说n元变量);同理\pmb{Y}d \times m的矩阵,每一行代表一个m个特征的数据;寻找\pmb{X}\pmb{Y}之间的线性关系。为了后面的阅读方便,用下标表示行,用上标表示列。比如用\pmb{x}_i表示矩阵\pmb{X}的第i行,即第i个变量实例;\pmb{x}^j表示矩阵\pmb{X}的第j列,即第j个特征。

      对于上述问题,我们仍然可以使用回归的方法来分析, 即求出一个矩阵A(n \times m), 使得

(1)   \begin{eqnarray*} \pmb{Y} = \pmb{X} \pmb{A} \end{eqnarray*}

这种做法实际上是训练了m个线性回归模型:\pmb{y}^j = \pmb{X}\pmb{a}^j,j=1,...,m。这种做法的缺点是虽然\pmb{Y}中的每一个特征都和\pmb{X}的所有特征有关联, 但\pmb{Y}的特征之间没有关联。

      为了解决这个问题,我们继续考察应变量只有一维的情况。应变量\pmb{y}只有一位的情况下, 我们的线性回归目标学习一个向量\pmb{a}。以该向量系数为权重,\pmb{X}特征的线性组合为\pmb{X}\pmb{a}。学习过程应最小化应变量\pmb{y}和该线性组合\pmb{X}\pmb{a}的差值。这时我们可能想到,\pmb{Y}也是多维情况下,我们可不可以相应地设置另一个向量\pmb{b}, 使得\pmb{X}\pmb{a}\pmb{Y}\pmb{b}之间的差值最小呢?你认为我要说可以?答案是可不以。囧里个囧。为什么不可以呢?因为不管什么情况,\pmb{a}=\pmb{0},\pmb{b}=0的情况下,\pmb{X}\pmb{a}\pmb{Y}\pmb{b}之间的差值一定最小(都等于0了嘛)。但我们把目标改变下,不再最小化它们之间差值,而是最大化它们之间相关性,这个问题就解决了。我们用Pearson相关系数衡量相关性,则我们的目标如下:

(2)   \begin{eqnarray*} max \quad pearson(\pmb{u},\pmb{v}) = \frac{cov(\pmb{u}, \pmb{v})}{var(\pmb{u})var(\pmb{v})} \end{eqnarray*}

其中\pmb{u} = \pmb{X}\pmb{a},\pmb{v} = \pmb{Y}\pmb{b}。为了方便起见,文章后面也用\pmb{u}\pmb{v}表示各自的线性组合。

      这样就引入了典型相关性分析(CCA)。CCA期望寻求一组最优的解\pmb{a},\pmb{b},使得Corr(\pmb{u},\pmb{v})最大。

二.CCA的求解

      用\Sigma_{x,x}表示\pmb{X}的协方差矩阵,\Sigma_{y,y}表示\pmb{X}的协方差矩阵,\Sigma_{x,y}表示\pmb{X}\pmb{Y}的协方差矩阵。\pmb{u}\pmb{v}的方差和协方差可以用下面的公式表示:

(3)   \begin{eqnarray*} cov(\pmb{u},\pmb{v}) &=& E[(\pmb{x}\pmb{a}-\pmb{\bar{x}}\pmb{a})^T(\pmb{y}\pmb{b}-\pmb{\bar{y}}\pmb{b})] = \pmb{a}^TE[(\pmb{x}-\pmb{\bar{x}})^T(\pmb{y}-\pmb{\bar{y}})]\pmb{b} =    \pmb{a}^{T}\Sigma_{x,y}\pmb{b} \nonumber\\ var(\pmb{u}) &=& \pmb{a}^{T}\Sigma_{x,x}\pmb{a} \nonumber\\ var(\pmb{v}) &=& \pmb{b}^{T}\Sigma_{y,y}\pmb{b} \nonumber \end{eqnarray*}

其中\bar{\pmb{x}}表示均值。因此,最大化Pearson系数,实质上是最大化\frac{\pmb{a}\Sigma_{x,x}\pmb{b}}{\sqrt{\pmb{a}\Sigma_{x,x}\pmb{a}}\sqrt{\pmb{b}\Sigma_{y,y}\pmb{b}}}。为了避免\pmb{a}\pmb{b}同时扩大相同倍数,依然是最优解的情况,我们固定分母然后最大化分子,得到以下优化问题:

(4)   \begin{eqnarray*} &Maximize & \quad \pmb{a}^T\Sigma_{x,y}\pmb{b} \nonumber\\ &Subject  &  \quad \pmb{a}^T\Sigma_{x,x}\pmb{a} = 1 \nonumber \\ &&\quad  \pmb{b}^T\Sigma_{y,y}\pmb{b} = 1 \end{eqnarray*}

      求解方法是构造Lagrangian等式,

(5)   \begin{eqnarray*} \ell(\pmb{a},\pmb{b},\lambda_1,\lambda_2) = \pmb{a}^T\Sigma_{x,y}\pmb{b} - \lambda_1(\pmb{a}^T\Sigma_{x,x}\pmb{a} - 1) - \lambda_2(\pmb{b}^T\Sigma_{y,y}\pmb{b} - 1) \nonumber  \end{eqnarray*}

      对Lagrangian求导并令导数为0,得

(6)   \begin{eqnarray*} \Sigma_{x,y}\pmb{b} - \lambda_1 \Sigma_{x,x}\pmb{a} = 0  \\ \Sigma_{y,x}\pmb{a} - \lambda_2 \Sigma_{y,y}\pmb{b} = 0  \\ \end{eqnarray*}

公式(4),左乘\pmb{a}^T,并结合\pmb{a}^T\Sigma_{x,x}\pmb{a} = 1, 我们很容易得到\lambda_1 = \pmb{a}^T\Sigma_{x,y}\pmb{b}。同理我们得到\lambda_2 = \pmb{a}^T\Sigma_{x,y}\pmb{b}。即\lambda_1 = \lambda_2是优化问题(x)要最大化的目标。

      利用\lambda_1=\lambda_2, 将公式(5)带入公式(4)得

(7)   \begin{eqnarray*} \Sigma_{x,x}^{-1}\Sigma_{x,y}\Sigma_{y,y}^{-1}\Sigma_{y,x}\pmb{a} = \lambda_1^2\pmb{a} \end{eqnarray*}

这里假设\Sigma_{x,x}^{-1},\Sigma_{y,y}^{-1}都是可逆的。式子(xx)可以看成求矩阵\Sigma_{x,x}^{-1}\Sigma_{x,y}\Sigma_{y,y}^{-1}\Sigma_{y,x}的特征向量和特征值。

三.Kernel Canonical Correlation Analysis(KCCA)

      上述的CCA是对线性关系建模的,但是很多时候线性关系不能充分表达变量之间的关系。一个很好的思路是将之映射到高维空间, 在高维空间用线性关系对原始空间非线性关系建模。有了这个思路,我们就可以发展出非线性版本CCA了。我们将数据\pmb{X}\pmb{Y}分别用映射函数\psi\phi映射到不同的高维空间。这时候在高维空间的线性组合

(8)   \begin{eqnarray*} \pmb{u} = \psi(\pmb{X})\pmb{a}  \qquad \pmb{v} = \phi(\pmb{Y})\pmb{b} \nonumber \\ \end{eqnarray*}

然后用第二节介绍的方法求出。但是我们迅速发现一个问题,当高维空间的维度很大甚至无限时,计算会变得非常耗时甚至不可能。

      为了解决这个问题,就必须引入核函数。核函数被定义为变量映射到高维空间之后的内积, 记为k(\pmb{x}_i,\pmb{x}_j) = \psi(\pmb{x}_i)^T\psi(\pmb{y}_j)。对于多个变量\pmb{X},一般用核矩阵\pmb{K}_x来表示变量之间的核函数:\pmb{K}_x(i,j) = k(\pmb{x_i},\pmb{x_j})。举个例子,有两个三元变量\pmb{x}_i =[x_i^1,x_i^2,x_i^2]^T\pmb{x}_j = [x_j^1,x_j^2,x_j^3]^T,同时映射函数\psi(\pmb{x})  = [x_i^1x_i^1,x_i^1x_i^2,...,x_i^3x_i^3]^T, 此时核函数如下所示:

(9)   \begin{eqnarray*} k(\pmb{x}_i,\pmb{x}_j) = \psi(\pmb{x}_i)^T\psi(\pmb{x}_j) = (\pmb{x}_i^T\pmb{x}_j)^2 \end{eqnarray*}

我们发现这个核函数不需要显式地映射到高维空间之后再计算,而是可以方便的计算出来。实际上,人们发现了很多核函数可以不需要显式地映射到高维空间之后再计算。如果我们用技巧让CCA算法只涉及变量的内积,将变量内积替换为可以方便计算的核函数,CCA算法就可以方便地运行在高维空间上了。

      我们来让高维空间的CCA算法只涉及高维空间变量内积的技巧有两部分。1)对高维空间上的变量实例的均值为0,也就是让\frac{1}{n}\sum_{i=1}^{d}\psi(\pmb{x}_i) = 0\frac{1}{n}\sum_{i=1}^{d}\phi(\pmb{y}_i) = 0。对于常用的核函数,要实现这点只需要对原始数据集进行去中心化:\pmb{x}^i = \pmb{x}^i - \frac{1}{n}\sum_{i=1}^{d}\pmb{x}_i\pmb{y}^i = \pmb{y}^i - \frac{1}{n}\sum_{i=1}^{d}\pmb{y}_i。2)引入一个假设:所有原始空间映射到高维空间的变量实例\psi(\pmb{x}_i),i=1,...d,可以作为一组基生成一个高维空间的子空间, CCA要学习的向量\pmb{a}应该在这个子空间中。

(10)   \begin{eqnarray*} \pmb{a} = \sum_{i=1}^{d} \beta_i \psi(\pmb{x}_i) = \psi(\pmb{X})^T\pmb{\beta} \nonumber\\ \end{eqnarray*}

其中\beta_i\pmb{x}_i的系数,而\pmb{\beta}是这些系数的维度为d的向量,同理\pmb{b} =  \phi(\pmb{Y})^T\pmb{\gamma}

      引入了核函数和上述两个技巧之后,我们就在高维空间可以求解CCA了。此时我们的优化目标依然是,通过固定分母最大化分子,从而最大化Pearson相关系数。

(11)   \begin{eqnarray*} &Maximize & \quad cov(\pmb{u},\pmb{v}) \nonumber\\ &Subject  &  \quad var(\pmb{u}) = 1 \nonumber \\ &&\quad  var(\pmb{v}) = 1 \nonumber \end{eqnarray*}

下面我们来推导CCA,其中第1行到第2行是因为去中心化,第3行到第4行是因为技巧2所推出的公式。

(12)   \begin{eqnarray*} cov(\pmb{u},\pmb{v}) &=& E\{[\psi(\pmb{x})\pmb{a}-\frac{1}{n}\sum_{i=1}^{d}\psi(\pmb{x}_i)\pmb{a}]^T[\phi(\pmb{y})\pmb{b}-\frac{1}{n}\sum_{i=1}^{d}\phi(\pmb{y}_i) \pmb{b}]\} \nonumber\\ &=& \pmb{a}^TE[\psi(\pmb{x})^T\phi(\pmb{y})]\pmb{b} \nonumber\\ &=& \pmb{a}^{T}\psi(\pmb{X})^T\phi(\pmb{Y})\pmb{b} \nonumber\\ &=&  \pmb{\beta}^T\psi(\pmb{X})\psi(\pmb{X})^T\phi(\pmb{Y})\phi(\pmb{Y})^T\pmb{\gamma} \nonumber \\ &=& \pmb{\beta}^T\pmb{K}_{x}\pmb{K}_y\pmb{\gamma} \nonumber \end{eqnarray*}

同理可求得var(\pmb{u}) = \pmb{\beta}^T\pmb{K}_x\pmb{K}_x\pmb{\beta},var(\pmb{v}) = \pmb{\gamma}^T\pmb{K}_y\pmb{K}_y\pmb{\gamma}。这样就可以用第二节介绍的方法求解了。

四.Deep Canonical Correlation Analysis (DCCA)

      KCCA实质上是先将原始的数据\pmb{x}\pmb{y}映射到高维空间,然后在高维空间跑CCA。那么一个很自然的想法。如果用两个(深层)神经网络将数据\pmb{x}\pmb{y}非线性地映射到隐空间,然后在隐空间跑CCA。那效果会不会好些呢?因此有人紧跟deep learning潮流,在文献[2]中,用了下面的结构。

dcca

      这个方法要跑起来,就必须求出corr(\pmb{H}_1,\pmb{H}_2)的梯度,其中\pmb{H}_1\pmb{x}在隐空间的表示,\pmb{H}_2\pmb{y}的表示。

(13)   \begin{eqnarray*} \frac{\partial corr(\pmb{H}_1,\pmb{H}_2) }{\partial \pmb{H}_1} = \frac{1}{m-1}(2 \triangledown_{11} \hat{\pmb{H}_1} + \triangledown_{12}\hat{\pmb{H}_2}) \end{eqnarray*}

其中\hat{\pmb{H}_1}(\hat{\pmb{H}_2})是白化后的\pmb{H}_1(\pmb{H}_2)。令UDV' = \hat{\Sigma}_{11}^{-1/2}\hat{\Sigma}_{1,2}\hat{\Sigma}_{22}^{-1/2},有\triangledown_{12} = \hat{\Sigma}_{11}^{-1/2} UV'\hat{\Sigma}_{22}^{-1/2}以及\triangledown_{11} = -\frac{1}{2}\hat{\Sigma}_{11}^{-1/2} UDU'\hat{\Sigma}_{11}^{-1/2}

参考文献
      1 典型关联分析(Canonical Correlation Analysis)http://www.cnblogs.com/jerrylead/archive/2011/06/20/2085491.html
      2 Andrew, Galen, et al. "Deep canonical correlation analysis." Proceedings of the 30th International Conference on Machine Learning. 2013.

此条目发表在算法荟萃分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。