传统的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)=wxTXXTwxTwyTYYTwyTwxTXYTwyT(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)TwyTYYTwyTwΦ(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)
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)TKYTwys.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)
λ
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)中的最优值问题。
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.
