第十六讲典则相关分析CCACCA动机: cov(uTx, vTy) = uTZxyv = max!ccaCCA结果: cov(x,y) = Zxy = cov(, n) =diagonal
第十六讲 典则相关分析CCA 1 CCA动机: cov( 𝐮 ⊤𝐱, 𝐯 ⊤𝐲) = 𝐮 ⊤ Σ𝐱𝐲𝐯 = max! CCA结果: cov 𝐱, 𝐲 = Σ𝐱𝐲 cca cov 𝛏, 𝛈 =diagonal
Recap奇异值分解(SVD，Singularvaluedecomposition）SVD定理l：任何秩为r的n×p矩阵X有奇异值分解X=UDVT,其中D=diag(…a,)，≥...≥,>0为Tx或xTx的非o特征根UTU=I,TV=I,其中Uxr=(u..u,),Vxr=(vi..v,）的列向量分别是XTX或XIX非O特征根对应的正交单位特征向量。有时，将U，V扩张成正交矩阵应用起来更方便：奇异值分解Xxn=UxDVT中，若将U,V补全为正交方阵U,V,D补UV正交阵情形D全为与X大小相同的矩阵D则奇异值分解可表示为IXP0Xmp=UmmDmxpPTpxp其中Uu,分别是n,p阶正交矩阵
2 或 非 特征根对应的正交单位特征向量。 其中 的列向量分别是 其中 为 或 的非 特征根 定理 ：任何秩为 的 矩阵 有奇异值分解 奇异值分解 ， ： 0 , , ( ,., ), ( ,., ) diag( ,., ), . 0 0 , , 1 (SVD Singular value decomposition) 1 1 1 1 X X X X U U I V V I U V D X X X X X UDV r n p X r r q r r p r r r r r r T T T T T T T u u v v 其中 分别是 阶正交矩阵。 全为与 大小相同的矩阵 ，则奇异值分解可表示为 奇异值分解 中，若将 补全为正交方阵 补 , ~ , ~ ~ ~ ~ 0 0 ~ 0 , ~ , ~ , U V n p X U D V D X D X U D V U V U V D p p n p n n n p n p n p n r r r T T 有时，将𝑈, 𝑉扩张成正交矩阵应用起来更方便： SVD 𝑈, 𝑉正交 阵情形 Recap
最小二乘奇异值分解的最优性：定理2：平方误差意义下，Xk=UkDkVT=k-1u;v是X的最优秩k逼近：min,IW-X =Xk-XI =Zr=k+1irank(w)=k其中Uk=(u1,.,uk),Vk=(v1,,Vk）分别是XXT，XTX前k个共同最大特征根对应的特征向量。注意当k≥r时，上述误差等于o，此时X=Xk=UkDkVT，这样我们从逼近的角度证明了SVD（定理15.2的证明过程实质上并没有应用定理15.1）SVD正X=UDVT="VA,uvi交对角化Ji=UTXV = D uTXvi =/ai, u,Xv; = 0, 1≤i±j≤r3
3 奇异值分解的最优性： 定理2：平方误差意义下，𝑋𝑘 = 𝑈𝑘𝐷𝑘𝑉𝑘 ⊤ = σ𝑖=1 𝑘 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤是 𝑋 的 最优秩 𝑘 逼近： min 𝑟𝑎𝑛𝑘 𝑊 =𝑘 𝑊 − 𝑋 𝐹 2 = 𝑋𝑘 − 𝑋 𝐹 2 = σ𝑖=𝑘+1 𝑟 𝜆𝑖 其中 𝑈𝑘 = 𝐮1, . , 𝐮𝑘 , 𝑉𝑘 = 𝐯1, . , 𝐯𝑘 分别是 𝑋𝑋⊤ ，𝑋 ⊤𝑋 前 𝑘 个 共同最大特征根对应的特征向量。 注意当 𝑘 ≥ 𝑟 时，上述误差等于0，此时 𝑋 = 𝑋𝑘 = 𝑈𝑘𝐷𝑘𝑉𝑘 ⊤，这 样我们从逼近的角度证明了SVD （定理15.2的证明过程实质上并 没有应用定理15.1） SVD⇔正 交对角化 𝑋 = 𝑈𝐷𝑉 ⊤ = 𝑖=1 𝑟 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤ ⇔ 𝑈 ⊤𝑋𝑉 = 𝐷 ⇔ 𝐮𝑖 ⊤𝑋𝐯𝑖 = 𝜆𝑖 , 𝐮𝑖 ⊤𝑋𝐯𝑗 = 0, 1 ≤ 𝑖 ≠ 𝑗 ≤ 𝑟 最小二乘
我们将在典则相关分析、配列、聚类中用到双线性函数uTAV双线性函数极大化的极大化问题，该问题与奇异值分解的最优性有关。定理3.假设矩阵Xnxp的秩为r，其奇异值分解为X=UDVT，其中U = (u1,., ur), V = (vi,.,vr), D = diag(a1,..,a),入1≥≥入r>0,考虑极大化max..uTxv(*)Ilul/={/v=1(1)当u=u1，V=Vi时(*)达到最大，最大值等于最大奇异值a1(2)对任何k≤r,限制ulu1,,uk-1,vvi,.,Vk-1,则在u=ukV=Vk时(*)达到最大,最大值等于/ak证明1：（1）由Cauchy-Schwartz不等式uTXV≤VuTuVVTXTXV=VVTXTXV≤/a当V=V1时后一个等号成立，当uαXv时前一个等号成立，此时，uαXviαu1.(2)证明类似。4
4 定理3. 假设矩阵 𝑋𝑛×𝑝 的秩为 𝑟，其奇异值分解为 𝑋 = 𝑈𝐷𝑉 ⊤, 其中 𝑈 = (𝐮1, . , 𝐮𝑟), 𝑉 = (𝐯1, . , 𝐯𝑟), 𝐷 = 𝑑𝑖𝑎𝑔 𝜆1, . , 𝜆𝑟 , 𝜆1 ≥ ⋯ ≥ 𝜆𝑟> 0, 考虑极大化 max 𝐮 = 𝐯 =1 𝐮 ⊤𝑋𝐯 (∗) (1) 当 𝐮 = 𝐮1， 𝐯 = 𝐯1时(*)达到最大，最大值等于最大奇异值 𝜆1； (2) 对任何 𝑘 ≤ 𝑟, 限制 𝐮 ⊥ 𝐮1, . , 𝐮𝑘−1, 𝐯 ⊥ 𝐯1, . , 𝐯𝑘−1, 则在 𝐮 = 𝐮𝑘， 𝐯 = 𝐯𝑘 时 (*)达到最大, 最大值等于 𝜆𝑘. 证明1： (1) 由Cauchy-Schwartz不等式 𝐮 ⊤𝑋𝐯 ≤ 𝐮⊤𝐮 𝐯 ⊤𝑋⊤𝑋𝐯 = 𝐯 ⊤𝑋⊤𝑋𝐯 ≤ 𝜆1 当 𝐯 = 𝐯1 时后一个等号成立，当 𝐮 ∝ 𝑋𝐯 时前一个等号成立， 此时， 𝐮 ∝ 𝑋𝐯1 ∝ 𝐮1. (2)证明类似。 双线性函 数极大化 我们将在典则相关分析、配列、聚类中用到双线性函数 𝐮 ⊤𝐴𝐯 的极大化问题，该问题与奇异值分解的最优性有关
证明2（拉格朗日乘子法）令n1m2(uTu - 1):f(u,v) = uTXv22令%= Xv- n2u = 0, %= XTu - n1V= 0, 即avauXv= n2u, Xtu = niv故u,v是奇异值分解中的一对特征向量，且uTXv=n1=n2最大为/a，故u=u，v=V1。证明3:A=UDVT，令a=UTu,b=T,因为UUT≤I,则a=uUUu≤uu=1|b所以uAv=uUDVv=a'Db=ablab,/,0若约束，，则U=(OU)TVv其中U,=(u.u),V,=(.k),则uAv=ab,,≤，等等。5
5 证明2（拉格朗日乘子法）令 𝑓 𝐮, 𝐯 = 𝐮 ⊤𝑋𝐯 − 𝜂1 2 𝐯 ⊤𝐯 − 1 − 𝜂2 2 (𝐮 ⊤𝐮 − 1)， 令 𝜕𝑓 𝜕𝐮 = 𝑋𝐯 − 𝜂2𝐮 = 0, 𝜕𝑓 𝜕𝐯 = 𝑋 ⊤𝐮 − 𝜂1𝐯 = 0, 即 𝑋𝐯 = 𝜂2𝐮，𝑋 ⊤𝐮 = 𝜂1𝐯 故 𝐮, 𝐯 是奇异值分解中的一对特征向量，且 𝐮 ⊤𝑋𝐯 = 𝜂1= 𝜂2 最大为 𝜆1，故 𝐮 = 𝐮1， 𝐯 = 𝐯1。 其中 则 ，等等。 若约束 ， ，则 ， ， 所以 证明 ： 令 因为 则 2 2 1 2 1 2 1 1 1 1 1 1 1 1 ( ,., ), ( ,., ), , 0 (0, ), | | || || 1 || || 1, 3 , , , , i i k i k k i i k i i i i k i i p U V A a bV U U V A UDV D a b a b UU A UDV U V UU I u u v v u v v u u v v u u v u v u v a b a u u u u b a u b v T T T T T T T T T T T T T T T T
推论1.假设矩阵A，的秩为r，其奇异值分解A=UDVTD=diag(/...a,),≥...≥,>0.则对任何k≤r，PRpxkQRxk, PTP=QTQ=Ik,maxtrPTAQ =trUTAVk,P,o其中U,=(u..u),V=(vi.)分别为U,V的前k列。证明：记P=(P…Pk)Q=(q.,qk),trPTAQ=p,Aq,，应用定理3即得。i=16
6 其中 分别为 的前 列。 ， ， 则对任何 ， 推论 假设矩阵 的秩为 其奇异值分解 ( ,., ), ( ,., ) , max , diag( ,., ), . 0. , 1. , , 1 1 , 1 1 U V U V k trP AQ trU AV Q R P P Q Q I D k r P R A r A UDV k k k k k k P Q k q k p k r r q p u u v v T T T T T 证明：记 ( ,., ), ( ,., ), ，应用定理3即得。 1 1 1 i k i P p pk Q q qk trP AQ pi Aq T T
典则相关分析（CCA）典则相关分析（ccA：Canonicalcorrelationanalysis）研究两个随机向量之间的相关性，它试图在两个向量内部分别发现最能代表两组之间相关性的线性组合。CCA由H.Hotelling提出。例1.140个七年级学生进行了4项测试，X1 = reading speed, x2 =reading power;Yi = arithmetic speed, Y2 = arithmetic power;相关系数矩阵如下：XiX2y2yi(1.000.630.240.06)t41.00J0.07-0.06专1.000.42J11.00y2(口阅读x=（αx1,x2)T与数学y=(y1,y2)T的协方差Zxy是一个矩阵，如何用一个实数度量它们之间的相关性？口如果xy高度相关，原因是什么（是因为x2与y1强相关?）
7 例1. 140 个七年级学生进行了4项测试， 𝑥1 = reading speed, 𝑥2 = reading power; 𝑦1 = arithmetic speed, 𝑦2 = arithmetic power; 相关系数矩阵如下： 典则相关分析（CCA） 典则相关分析（CCA:Canonical correlation analysis）研究两个 随机向量之间的相关性，它试图在两个向量内部分别发现最能代表 两组之间相关性的线性组合。CCA由H.Hotelling提出。 1.00 1.00 0.42 1.00 0.06 0.07 1.00 0.63 0.24 0.06 2 1 2 1 1 2 1 2 ， yx yy xx xy y y x x x x y y 阅读 𝐱 = (𝑥1, 𝑥2) ⊤ 与数学 𝐲 = (𝑦1, 𝑦2) ⊤ 的协方差 Σ𝐱𝐲 是一个矩阵，如 何用一个实数度量它们之间的相关性？ 如果 𝐱, 𝐲 高度相关，原因是什么 （是因为 𝑥2与 𝑦1 强相关?）
一般地，我们考虑如下典则相关分析问题：CCA问题的提出S.0x假设valx,y在这哪些方向上相关性最大？gx1求解方向aERp，bERq使得aTx，bTy的协方差最大cov(aTx, bTy)=aTZxyb这是有意义的问题，但传统上人们经常考虑相关系数最大化求解方向aERP，bERq使得第一对典则变量aTx，bTy的相关系数最大：aT2xybcorr(aTx, bTy) max!VaTZxxa/bTZyb该问题没有唯一解。因为是研究相关系数，典则相关分析约束投影坐标方差为1：Var(aTx) = aTZxxa = 1, var(bTy) = bTZyvb = 1在该约束下极大化cov(aTx, bTy) = aTxyb。0
8 一般地，我们考虑如下典则相关分析问题： 假设var 𝐱𝑝×1 𝐲𝑞×1 = Σ𝐱𝐱 Σ𝐱𝐲 Σ𝐲𝐱 Σ𝐲𝐲 , 𝐱, 𝐲 在这哪些方向上相关性最大? 求解方向 𝐚 ∈ 𝑅 𝑝，𝐛 ∈ 𝑅 𝑞使得第一对典则变量 𝐚 ⊤𝐱，𝐛 ⊤𝐲 的相关系 数最大： corr 𝐚 ⊤𝐱，𝐛 ⊤𝐲 = 𝐚 ⊤Σ𝐱𝐲𝐛 𝐚⊤Σ𝐱𝐱𝐚 𝐛⊤Σ𝐲𝐲𝐛 = max! 该问题没有唯一解。因为是研究相关系数，典则相关分析约束投影 坐标方差为1： var(𝐚 ⊤𝐱) = 𝐚 ⊤Σ𝐱𝐱𝐚 = 1, var 𝐛 ⊤𝐲 = 𝐛 ⊤Σ𝐲𝐲𝐛 = 1 在该约束下极大化 cov 𝐚 ⊤𝐱，𝐛 ⊤𝐲 = 𝐚 ⊤Σ𝐱𝐲𝐛。 求解方向 𝐚 ∈ 𝑅 𝑝，𝐛 ∈ 𝑅 𝑞使得 𝐚 ⊤𝐱，𝐛 ⊤𝐲 的协方差最大 cov 𝐚 ⊤𝐱，𝐛 ⊤𝐲 = 𝐚 ⊤Σ𝐱𝐲𝐛 这是有意义的问题，但传统上人们经常考虑相关系数最大化. CCA问题 的提出
CCA问2ZxyXpx1cov(aTx,bTy)=aTZxybvar题框架SY优化目标：aTExybmaxaT2xxa=1,bTzyyb=1假设 A = Z×1/2x2y1/2, 其SVD: A = UDVT = Zi=1 /,uvT。xXXLxyLyy后续SVD出现的时候其中的记号含义不再一一说明A=22/2y/？eRpx的奇异值分解：.假设rank(A)=r, A=UDvT=Zr=1ya;u;vi,其中D =diag(..,)，≥≥>0为AAT，ATA的共同非O特征根,Uk=(u1,.,uk),Vk=(v1,.,Vk）分别是AAT，ATA前k个共同最大特征根对应的正交单位特征向量，UTU=VTV=Ir
9 CCA问 题框架 var 𝐱𝑝×1 𝐲𝑞×1 = Σ𝐱𝐱 Σ𝐱𝐲 Σ𝐲𝐱 Σ𝐲𝐲 ，cov 𝐚 ⊤𝐱，𝐛 ⊤𝐲 = 𝐚 ⊤Σ𝐱𝐲𝐛， 假设 𝐴 = Σ𝐱𝐱 −1/2 Σ𝐱𝐲Σ𝐲𝐲 −1/2，其SVD: 𝐴 = 𝑈𝐷𝑉 ⊤ = σ𝑖=1 𝑟 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤。 𝐴 = Σ𝐱𝐱 −1/2 Σ𝐱𝐲Σ𝐲𝐲 −1/2 ∈ 𝑅 𝑝×𝑞 的奇异值分解： 假设 𝑟𝑎𝑛𝑘(𝐴) = 𝑟, 𝐴 = 𝑈𝐷𝑉 ⊤ = σ𝑖=1 𝑟 𝜆𝑖 𝐮𝑖𝐯𝑖 ⊤ , 其中𝐷 = diag( 𝜆1, . , 𝜆𝑟)，𝜆1 ≥ ⋯ ≥ 𝜆𝑟> 0为𝐴𝐴⊤ ，𝐴 ⊤𝐴的共同非0特 征根,𝑈𝑘 = 𝐮1, . , 𝐮𝑘 , 𝑉𝑘 = 𝐯1, . , 𝐯𝑘 分别是𝐴𝐴⊤ ，𝐴 ⊤𝐴前𝑘个 共同最大特征根对应的正交单位特征向量， 𝑈 ⊤𝑈 = 𝑉 ⊤𝑉 = 𝐼𝑟 。 后续SVD出现的时候其中的记号含义不再一一说明： 优化目标： max 𝐚⊤Σ𝐱𝐱𝐚=1, 𝐛⊤Σ𝐲𝐲𝐛=1 𝐚 ⊤Σ𝐱𝐲𝐛
第1步：CCA求解过程令u = ≥ /2 a, = 2,/ b, ll = 1, I/ll= 1, 由定理3, 'yyuT/2y/2= /AmaxaT2xyb =.max.|u|=1,/v||=1最大值在u=uV=Vi处达到，此时ai=2-1/2u1,b1=Z%/2v1工我们称最优组合t= aix= u2/x, ni= bly = I2/zy为第一对典则变量，最大值入为第一典则相关系数。1S1var01Va11给定前k-1个典则变量51..,5k-1;n1,,nk-1第k步：2≤k≤r=rank(Exy)在aTx与51,,5k-1不相关、bTy与n1,,nk-1不相关以及单位方差的约束下，由定理310
10 第1步： 令𝐮 = Σ𝐱𝐱 1/2 𝐚，𝐯 = Σ𝐲𝐲 1/2 𝐛, 𝐮 = 1, 𝐯 = 1, 由定理3, max𝐚 ⊤Σ𝐱𝐲𝐛 = max 𝐮 =1, 𝐯 =1 𝐮 ⊤Σ𝐱𝐱 −1/2 Σ𝐱𝐲Σ𝐲𝐲 −1/2 𝐯 = 𝜆1 最大值在𝐮 = 𝐮1, 𝐯 = 𝐯1处达到，此时𝐚1 = Σ𝐱𝐱 −1/2 𝐮1, 𝐛1 = Σ𝐲𝐲 −1/2 𝐯1. 我们称最优组合 𝜉1 = 𝐚1 ⊤𝐱 = 𝐮1 ⊤Σ𝐱𝐱 −1/2 𝐱, 𝜂1= 𝐛1 ⊤𝐲 = 𝐯1 ⊤Σ𝐲𝐲 −1/2 𝐲 为第一对典则变量，最大值 𝜆1为第一典则相关系数。 第𝑘步：2 ≤ 𝑘 ≤ 𝑟 = 𝑟𝑎𝑛𝑘(Σ𝐱𝐲) 在 𝐚 ⊤𝐱 与 𝜉1, . , 𝜉𝑘−1 不相关、𝐛 ⊤𝐲 与𝜂1, . , 𝜂𝑘−1 不相关以及单位方差 的约束下, 由定理3 给定前𝑘 − 1个典则变量 𝜉1, . , 𝜉𝑘−1； 𝜂1, . , 𝜂𝑘−1 𝑣𝑎𝑟 𝜉1 𝜂1 = 1 𝜆1 𝜆1 1 CCA求 解过程