基于核概念的KCCA算法
1、由CCA算法过渡至KCCA算法2、KCCA算法的原理与推导
1、由CCA算法过渡至KCCA算法
典型相关分析（CCA）算法是一种标准的统计技术，用于寻找两个最大相关的随机向量的线性投影。CCA算法是一个计算两个多维变量相关性的强大方法,但如果两个变量间存在非线性相关的关系,CCA算法也许在此时会失效。为了克服CCA算法的这个弊端,KCCA算法通过引入”kernel trick”的概念改进CCA算法。
2、KCCA算法的原理与推导
传统的CCA算法的目标是找寻一对方向向量
w
x
w_x
wx和
w
y
w_y
wy 以使得多维变量
X
X
X、
Y
Y
Y在这对方向上的投影
w
x
T
X
w_x^T X
wxTX和
w
y
T
Y
w_y^T Y
wyTY之间的相关性
ρ
(
x
,
y
)
ρ(x,y)
ρ(x,y)最大化。
ρ
(
X
,
Y
,
w
x
,
w
y
)
=
w
x
T
X
Y
T
w
y
T
w
x
T
X
X
T
w
x
T
w
y
T
Y
Y
T
w
y
T
(1)
ρ(X,Y,w_x,w_y)=\frac{w_x^TXY^Tw_y^T}{\sqrt{w_x^TXX^Tw_x^T}\sqrt{w_y^TYY^Tw_y^T}}\tag{1}
ρ(X,Y,wx,wy)=wxTXXTwxT
wyTYYTwyT
wxTXYTwyT(1)
而当两个多维变量X、Y之间存在非线性相关性时,KCCA算法通过将变量X映射至希尔伯特空间
Φ
Φ
Φ(Hibert Space,详细见有关希尔伯特空间定义的讨论)。
Φ
:
R
n
x
→
F
,
x
→
Φ
(
x
)
(2)
\Phi:R^{n_x}\rightarrow{F},x\rightarrow{\Phi{(x)}}\tag{2}
Φ:Rnx→F,x→Φ(x)(2) 此时,相关性函数变成了如下(3)式所示:
ρ
(
Φ
(
x
)
,
y
;
w
Φ
(
x
)
,
w
y
)
ρ(\Phi(x),y;w_{\Phi(x)},w_y)
ρ(Φ(x),y;wΦ(x),wy)
=
w
Φ
(
x
)
T
Φ
(
x
)
Y
T
w
y
T
w
Φ
(
x
)
T
Φ
(
x
)
(
Φ
(
x
)
)
T
w
Φ
(
x
)
T
w
y
T
Y
Y
T
w
y
T
(3)
=\frac{w_{\Phi(x)}^T{\Phi(x)}Y^Tw_y^T}{\sqrt{w_{\Phi(x)}^T{\Phi(x)}({\Phi(x)})^Tw_{\Phi(x)}^T}\sqrt{w_y^TYY^Tw_y^T}}\tag{3}
=wΦ(x)TΦ(x)(Φ(x))TwΦ(x)T
wyTYYTwyT
wΦ(x)TΦ(x)YTwyT(3)
因此,KCCA算法的目标等同于找寻
w
Φ
(
x
)
w_{Φ(x)}
wΦ(x)和
w
y
w_y
wy来在下(4)式约束中最大化
w
Φ
(
x
)
Φ
(
X
)
Y
T
w
y
w_Φ(x) Φ(X)Y^T w_y
wΦ(x)Φ(X)YTwy。
w
Φ
(
x
)
T
Φ
(
x
)
(
Φ
(
x
)
)
T
w
Φ
(
x
)
T
=
w
y
T
Y
Y
T
w
y
T
=
1
(4)
w_{\Phi(x)}^T{\Phi(x)}({\Phi(x)})^Tw_{\Phi(x)}^T=w_y^TYY^Tw_y^T=1\tag{4}
wΦ(x)TΦ(x)(Φ(x))TwΦ(x)T=wyTYYTwyT=1(4)
根据前人总结,存在方向向量
α
Φ
(
x
)
α_{Φ(x)}
αΦ(x)使得:
w
Φ
(
x
)
=
(
Φ
(
X
)
)
α
Φ
(
x
)
(5)
w_{Φ(x)}=(Φ(X))α_{Φ(x)}\tag{5}
wΦ(x)=(Φ(X))αΦ(x)(5)
假设
k
(
x
i
,
x
j
)
k(x_i,x_j)
k(xi,xj)是一个核函数,它能够在希尔伯特空间中由下述点积式表示。
(
k
)
i
j
=
k
(
x
i
,
x
j
)
=
⟨
Φ
(
X
i
)
,
Φ
(
X
j
)
⟩
=
(
Φ
(
X
i
)
)
T
Φ
(
X
j
)
(6)
(k)_{ij}=k(x_i,x_j) = \langle\Phi(X_i),\Phi(X_j)\rangle=(\Phi(X_i))^T\Phi(X_j)\tag{6}
(k)ij=k(xi,xj)=⟨Φ(Xi),Φ(Xj)⟩=(Φ(Xi))TΦ(Xj)(6)
由此,我们得到了一个N×N的矩阵K(该矩阵也称之为Gram矩阵, Gram矩阵是两两向量的内积组成，所以Gram矩阵可以反映出该组向量中各个向量之间的某种关系,详情见格拉姆矩阵详细解读),其具体可以写为:
K
=
(
Φ
(
X
)
)
T
Φ
(
X
)
(7)
K=({\Phi(X)})^T{\Phi(X)}\tag{7}
K=(Φ(X))TΦ(X)(7)
结合(4)、(5)、(7)式,我们可以得到:
w
Φ
(
x
)
Φ
(
X
)
Y
T
w
y
=
α
Φ
(
x
)
T
K
Y
T
w
y
(8)
w_{Φ(x)} Φ(X)Y^T w_y=α_{Φ(x)}^TKY^Tw_y\tag{8}
wΦ(x)Φ(X)YTwy=αΦ(x)TKYTwy(8)
w
y
T
Y
Y
T
w
y
T
=
w
Φ
(
x
)
T
Φ
(
x
)
(
Φ
(
x
)
)
T
w
Φ
(
x
)
=
α
Φ
(
x
)
T
K
K
α
Φ
(
x
)
(9)
w_y^TYY^Tw_y^T=w_{Φ(x)}^TΦ(x)(Φ(x))^Tw_{Φ(x)}=α_{Φ(x)}^TKKα_{Φ(x)}\tag{9}
wyTYYTwyT=wΦ(x)TΦ(x)(Φ(x))TwΦ(x)=αΦ(x)TKKαΦ(x)(9)
至此,解决KCCA问题等同于找寻
α
Φ
(
x
)
α_{Φ(x)}
αΦ(x)和
w
y
w_y
wy在如下约束中最大化目标值，即
max
α
Φ
(
x
)
,
w
y
α
Φ
(
x
)
T
K
Y
T
w
y
s
.
t
.
w
y
T
Y
Y
T
w
y
T
=
α
Φ
(
x
)
T
K
K
α
Φ
(
x
)
=
1
{\underset{α_{Φ(x)},{w_y}}{\operatorname {max} }}\ α_{Φ(x)}^T KY^T w_y\ \ \ s.t.\ \ \ w_y^TYY^Tw_y^T=α_{Φ(x)}^TKKα_{Φ(x)}=1
αΦ(x),wymax αΦ(x)TKYTwy s.t. wyTYYTwyT=αΦ(x)TKKαΦ(x)=1
为了求解该问题,引入拉格朗日算子,构建拉格朗日式为:
L
(
α
Φ
(
x
)
,
w
y
,
λ
,
μ
)
L(α_{Φ(x)},w_y,λ,μ)
L(αΦ(x),wy,λ,μ)
=
α
Φ
(
x
)
T
K
Y
T
w
y
−
λ
(
α
Φ
(
x
)
T
K
K
α
Φ
(
x
)
−
1
)
/
2
−
μ
(
w
y
T
Y
Y
T
w
y
T
−
1
)
=α_{Φ(x)}^TKY^Tw_y-λ(α_{Φ(x)}^TKKα_{Φ(x)} - 1)/2-μ(w_y^TYY^Tw_y^T - 1)
=αΦ(x)TKYTwy−λ(αΦ(x)TKKαΦ(x)−1)/2−μ(wyTYYTwyT−1)
对拉格朗日式中的
α
Φ
(
x
)
α_{Φ(x)}
αΦ(x)和
w
y
w_y
wy分别求偏导,并使得偏导式为0,由此我们可以得到:
∂
L
∂
α
Φ
(
x
)
=
K
Y
T
w
y
−
λ
K
K
α
Φ
(
x
)
=
0
(10)
\frac{\partial L}{\partial α_{Φ(x)}}=KY^Tw_y-λKKα_{Φ(x)}=0\tag{10}
∂αΦ(x)∂L=KYTwy−λKKαΦ(x)=0(10)
∂
L
∂
α
Φ
(
x
)
=
Y
K
α
Φ
(
x
)
−
μ
Y
Y
T
w
y
=
0
(11)
\frac{\partial L}{\partial α_{Φ(x)}}=YKα_{Φ(x)}-μYY^Tw_y=0\tag{11}
∂αΦ(x)∂L=YKαΦ(x)−μYYTwy=0(11) 解得
μ
=
λ
,
w
y
=
(
Y
Y
T
)
−
1
Y
K
μ
α
Φ
(
x
)
(12)
μ=λ,w_y=\frac{(YY^T)^{-1} YK}{μ} α_{Φ(x)}\tag{12}
μ=λ,wy=μ(YYT)−1YKαΦ(x)(12)
由此得:
K
Y
T
(
Y
Y
T
)
−
1
Y
K
α
Φ
(
x
)
=
λ
2
K
K
α
Φ
(
x
)
(13)
KY^T (YY^T)^{-1} YKα_{Φ(x)}=λ^2 KKα_{Φ(x)}\tag{13}
KYT(YYT)−1YKαΦ(x)=λ2KKαΦ(x)(13)
如果格拉姆矩阵K满秩,则(13)式两端同左乘
K
−
1
K
−
1
K^{-1} K^{-1}
K−1K−1,得:
K
−
1
Y
T
(
Y
Y
T
)
−
1
Y
K
α
Φ
(
x
)
=
λ
2
α
Φ
(
x
)
(14)
K^{-1}Y^T (YY^T)^{-1} YKα_{Φ(x)}=λ^2 α_{Φ(x)}\tag{14}
K−1YT(YYT)−1YKαΦ(x)=λ2αΦ(x)(14)
然而,在大多数情况下,由于
K
K
K是一个中心化的格拉姆矩阵,故K通常为奇异矩阵(行列式值为0,非满秩)。为了解决这个问题,一个可行的方案是引入一个正则化矩阵
N
K
I
N_K I
NKI重解(14)式中的特征方程,其中,
I
I
I为一个单位矩阵,而
N
K
N_K
NK是一个较小的常数。
(
K
+
N
K
I
)
−
1
Y
T
(
Y
Y
T
)
−
1
Y
K
α
Φ
(
x
)
=
λ
2
α
Φ
(
x
)
(15)
(K+N_KI)^{-1}Y^T (YY^T)^{-1} YKα_{Φ(x)}=λ^2 α_{Φ(x)}\tag{15}
(K+NKI)−1YT(YYT)−1YKαΦ(x)=λ2αΦ(x)(15)
该方案虽然可行,但是正则化矩阵的选取会很大程度上影响KCCA算法的性能。为了进一步克服选取正则化矩阵带来影响的弊端,本文中提出了一个基于特征值分解的改进版KCCA算法。事实上,最大的特征值由下列的瑞利商(Rayleigh quotient)给出:
λ
2
=
α
Φ
(
x
)
T
K
Y
T
(
Y
Y
T
)
−
1
Y
K
α
Φ
(
x
)
α
Φ
(
x
)
T
K
K
α
Φ
(
x
)
(16)
λ^2=\frac{α_{Φ(x)}^TKY^T (YY^T)^{-1} YKα_{Φ(x)}}{α_{Φ(x)}^TKKα_{Φ(x)}}\tag{16}
λ2=αΦ(x)TKKαΦ(x)αΦ(x)TKYT(YYT)−1YKαΦ(x)(16)
令
W
=
Y
T
(
Y
Y
T
)
−
1
Y
W=Y^T (YY^T)^{-1} Y
W=YT(YYT)−1Y,则(16)式可被写为:
λ
2
=
α
Φ
(
x
)
T
K
W
K
α
Φ
(
x
)
α
Φ
(
x
)
T
K
K
α
Φ
(
x
)
(17)
λ^2=\frac{α_{Φ(x)}^TKWKα_{Φ(x)}}{α_{Φ(x)}^TKKα_{Φ(x)}}\tag{17}
λ2=αΦ(x)TKKαΦ(x)αΦ(x)TKWKαΦ(x)(17)
因此,解决KCCA等同于找寻
α
Φ
(
x
)
α_{Φ(x)}
αΦ(x)最大化(17)式中的瑞利商,这也等同于求解广义判别分析(generalized discriminant analysis,GDA)中的最优值问题。
参考资料与文献:
有关希尔伯特空间定义的讨论——知乎格拉姆矩阵详细解读——CSDN博客Wenming Zheng, Xiaoyan Zhou, Cairong Zou and Li Zhao, “Facial expression recognition using kernel canonical correlation analysis (KCCA),” in IEEE Transactions on Neural Networks, vol. 17, no. 1, pp. 233-238, Jan. 2006, doi: 10.1109/TNN.2005.860849.