典型关联分析.docx

典型关联分析(Canonical Correlation Analysis)
[pdf版本] 
1. 问题
在线性回归中,我们使用直线来拟合样本点,寻找n维特征向量X和输出结果(或者叫做label)Y之间的线性关系。其中,。然而当Y也是多维时,或者说Y也有多个特征时,我们希望分析出X和Y的关系。
当然我们仍然可以使用回归的方法来分析,做法如下:
假设,,那么可以建立等式Y=AX如下
其中,形式和线性回归一样,需要训练m次得到m个。
这样做的一个缺点是,Y中的每个特征都与X的所有特征关联,Y中的特征之间没有什么联系。
我们想换一种思路来看这个问题,如果将X和Y都看成整体,考察这两个整体之间的关系。我们将整体表示成X和Y各自特征间的线性组合,也就是考察和之间的关系。
这样的应用其实很多,举个简单的例子。我们想考察一个人解题能力X(解题速度,解题正确率)与他/她的阅读能力Y(阅读速度,理解程度)之间的关系,那么形式化为:
 和 
然后使用Pearson相关系数
来度量u和v的关系,我们期望寻求一组最优的解a和b,使得Corr(u, v)最大,这样得到的a和b就是使得u和v就有最大关联的权重。
到这里,基本上介绍了典型相关分析的目的。
2. CCA表示与求解
给定两组向量和(替换之前的x为,y为),维度为,维度为,默认。形式化表示如下:
是x的协方差矩阵;左上角是自己的协方差矩阵;右上角是;左下角是,也是的转置;右下角是的协方差矩阵。
与之前一样,我们从和的整体入手,定义
 
我们可以算出u和v的方差和协方差:
  
上面的结果其实很好算,推导一下第一个吧:
最后,我们需要算Corr(u,v)了
我们期望Corr(u,v)越大越好,关于Pearson相关系数,《数据挖掘导论》给出了一个很好的图来说明:
横轴是u,纵轴是v,这里我们期望通过调整a和b使得u和v的关系越像最后一个图越好。其实第一个图和最后一个图有联系的,我们可以调整a和b的符号,使得从第一个图变为最后一个。
接下来我们求解a和b。
回想在LDA中,也得到了类似Corr(u,v)的公式,我们在求解时固定了分母,来求分子(避免a和b同时扩大n倍仍然符号解条件的情况出现)。这里我们同样这么做。
这个优化问题的条件是:
Maximize 
Subject to: 
求解方法是构造Lagrangian等式,这里我简单推导如下:
求导,得
令导数为0后,得到方程组:
第一个等式左乘,第二个左乘,再根据,得到
也就是说求出的即是Corr(u,v),只需找最大即可。
让我们把上面的方程组进一步简化,并写成矩阵形式,得到
写成矩阵形式
令
那么上式可以写作:
显然,又回到了求特征值的老路上了,只要求得的最大特征值,那么Corr(u,v)和a和b都可以求出。
在上面的推导过程中,我们假设了和均可逆。一般情况下都是可逆的,只有存在特征间线性相关时会出现不可逆的情况,在本文最后会提到不可逆的处理办法。
再次审视一下,如果直接去计算的特征值,复杂度有点高。我们将第二个式子代入第一个,得
这样先对求特征值和特征向量,然后根据第二个式子求得b。
待会举个例子说明求解过程。
假设按照上述过程,得到了最大时的和。那么和称为典型变量(canonical variates),即是u和v的相关系数。
最后,我们得到u和v的等式为:
 
我们也可以接着去寻找第二组典型变量对,其最优化条件是
Maximize 
Subject to: 
其实第二组约束条件就是。
计算步骤同第一组计算方法,只不过是取的第二大特征值。
得到的和其实也满足
 即 
总结一下,i和j分别表示和得到结果
3. CCA计算例子
我们回到之前的评价一个人解题和其阅读能力的关系的例子。假设我们通过对样本计算协方差矩阵得到如下结果:
然后求,得
这里的A和前面的中的A不是一回事(这里符号有点乱,不好意思)。
然后对A求特征值和特征向量,得到
然后求b,之前我们说的方法是根据求b,这里,我们也可以采用类似求a的方法来求b。
回想之前的等式
我们将上面的式子代入下面的,得
然后直接对求特征向量即可,注意和的特征值相同,这个可以自己证明下。
不管使用哪种方法,
这里我们得到a和b的两组向量,到这还没完,我们需要让它们满足之前的约束条件
这里的应该是我们之前得到的VecA中的列向量的m倍,我们只需要求得m,然后将VecA中的列向量乘以m即可。
这里的是VecA的列向量。
因此最后的a和b为:
第一组典型变量为
相关系数
第二组典型变量为
相关系数
这里的(解题速度),(解题正确率),(阅读速度