7.3 主成分分析(PCA)
一、协方差矩阵
这节是介绍 SVD 在统计和数据分析中的一个主要应用,即主成分分析。例子来自于人类的基因组,脸部识别和金融,目的是理解一个大的数据矩阵(测量值)。对于
n
n
n 个样本,我们每个测量
m
m
m 次,数据矩阵
A
0
A_0
A0 就有
n
n
n 列
m
m
m 行。
从几何上来看,
A
0
A_0
A0 的列是
R
m
\textrm{\pmb R}^m
Rm 中的
n
n
n 个点,我们将每行的分量都减去该行的平均值,得到矩阵
A
A
A,这
n
n
n 个点通常聚集在一条直线或者一个平面(或
R
m
\pmb{\textrm R}^m
Rm 的其它低维子空间)附近,这个
A
A
A 称之为中心化矩阵。这条直线或平面或者其它的子空间是什么呢?
下面用图形代替数字开始,对于
m
=
2
m=2
m=2 个变量,例如年龄和身高,这
n
n
n 个点都在平面
R
2
\pmb{\textrm R}^2
R2 内,将年龄和身高分别减去它们的平均值中心化这些数据。如果
n
n
n 个中心化点(recentered points)聚集在一条直线附近,那么如何使用线性代数求得这条直线?
下面来详细的构造这个数据矩阵,先从
A
0
A_0
A0 中的测量值开始:样本数据,求每行的平均值(mean)
μ
1
,
μ
2
,
⋯
,
μ
m
μ_1,μ_2,\cdots,μ_m
μ1,μ2,⋯,μm,将第
i
i
i 行的每个元素都减去这一行的平均值
μ
i
μ_i
μi 来中心化数据,则得到的中心化矩阵
A
A
A 的每行的平均值都是零,所以 Figure 7.2 中的点
(
0
,
0
)
(0,0)
(0,0) 是这
n
n
n 个点的真正的中心。
样本协方差矩阵
:
Sample
covariance
matrix
定义为
S
=
A
A
T
n
−
1
\pmb{样本协方差矩阵:\textrm{Sample\,covariance\,matrix\,}定义为\,S=\frac{AA^T}{n-1}}
样本协方差矩阵:Samplecovariancematrix定义为S=n−1AAT
A
A
A 表示每个测量值和它所在行平均值之间的距离
a
i
j
−
μ
i
a_{ij}-μ_i
aij−μi.
(
A
A
T
)
11
(AA^T)_{11}
(AAT)11 和
(
A
A
T
)
22
(AA^T)_{22}
(AAT)22 表示距离的平方和(样本方差 sample variances:
s
1
2
,
s
2
2
\pmb{s_1^2,s_2^2}
s12,s22).
(
A
A
T
)
12
(AA^T)_{12}
(AAT)12 表示样本协方差 Sample convariance
s
12
=
(
row
1
of
A
)
⋅
(
row
2
of
A
)
\pmb{s_{12}=(\textrm{row\,1\,of}\,A)\cdot(\textrm{row\,2\,of}\,A)}
s12=(row1ofA)⋅(row2ofA).
方差是贯穿统计学的关键数字,一次考试的平均成绩
μ
=
85
μ=85
μ=85 表明这是一个不错的成绩,方差
s
2
=
25
s^2=25
s2=25(标准差
s
=
5
s=5
s=5)意味着大部分的成绩都在
80
80
80 到
90
90
90 之间,很聚集;如果样本方差
s
2
=
225
(
s
=
15
)
s^2=225(s=15)
s2=225(s=15) 则表明分数很分散。
A
A
A 两行的点积,就是数学成绩和历史成绩的点积(已经减去了平均成绩),称为协方差。协方差小于零表明一门课成绩高一门课成绩低;协方差大于零则表示两门课的成绩要么都高,要么都低。
除以
n
−
1
n-1
n−1 而不是
n
n
n 的原因是统计学的观点:平均值已经用掉了一个自由度,所以只剩下了
n
−
1
n-1
n−1 个。任何情况下,为了统计的可靠性都要让
n
n
n 是一个很大的数,由于
A
A
A 有
n
n
n 个元素,
A
A
T
AA^T
AAT 中的元素将随着
n
n
n 一起增长,而除以
n
−
1
n-1
n−1 可以保证它们的平稳增长。
【例1】六个数学和历史的分数(注意每行的平均值为零)
A
=
[
3
−
4
7
1
−
4
−
3
7
−
6
8
−
1
−
1
−
7
]
的样本方程
S
=
A
A
T
5
=
[
20
25
25
40
]
A=\begin{bmatrix}3&-4&7&\kern 7pt1&-4&-3\\7&-6&8&-1&-1&-7\end{bmatrix}\,的样本方程\,S=\frac{AA^T}{5}=\begin{bmatrix}20&25\\25&40\end{bmatrix}
A=[37−4−6781−1−4−1−3−7]的样本方程S=5AAT=[20252540]
A
A
A 的两行高度相关:
s
12
=
25
s_{12}=25
s12=25,数学成绩高于平均值其历史成绩基本也高于平均值。如果将第二行的符号都改变则会得到负的协方差
s
12
=
−
25
s_{12}=-25
s12=−25。 注意
S
S
S 的迹和行列式都是正数,
A
A
T
AA^T
AAT 是正定的。
S
S
S 的两个特征值近似为
57
57
57 和
3
3
3,所以第一个秩一部分
57
u
1
v
1
T
\sqrt{57}\boldsymbol u_1\boldsymbol v_1^T
57u1v1T 要比第二个秩一部分
3
u
2
v
2
T
\sqrt 3\boldsymbol u_2\boldsymbol v_2^T
3u2v2T 大很多。首个特征向量
u
1
\boldsymbol u_1
u1 给出了 Figure 7.2 中直线的方向。 这个特征向量近似为
u
1
=
(
0.6
,
0.8
)
\boldsymbol u_1=(0.6,0.8)
u1=(0.6,0.8) .
A
(
中心化矩阵
)
的
SVD
给出了散点图中的主方向。
\pmb{A\,(中心化矩阵)\,的\,\textrm{SVD}\,给出了散点图中的主方向。}
A(中心化矩阵)的SVD给出了散点图中的主方向。第二个奇异向量
u
2
\boldsymbol u_2
u2 垂直于
u
1
\boldsymbol u_1
u1,第二个奇异值
σ
3
≈
3
\sigma_3\approx\sqrt3
σ3≈3 度量了数据在主方向上的分散程度。如果
A
A
A 的数据点正好落在一条直线上 (沿
u
1
\boldsymbol u_1
u1 的方向),那么
σ
2
\sigma_2
σ2 将会是零,这里也就只会剩下
σ
1
\sigma_1
σ1 这一项。
二、主成分分析概要
主成分分析(Principal Component Analysis: PCA)一种理解 m m m 维数据图的一种方法, m m m 是测量变量的个数(这里是年两盒身高)。将年龄和身高减去它们的平均值( m = 2 m=2 m=2 每个变量有 n n n 个样本)得到一个 m × n m\times n m×n 的中心化数据矩阵 A A A。这与线性代数的关键联系就是 A A A 的奇异值和奇异向量,它们都来自于协方差矩阵 S = A A T n − 1 S=\displaystyle\frac{AA^T}{n-1} S=n−1AAT 的特征值 λ = σ 2 \lambda=\sigma^2 λ=σ2 和特征向量 u \boldsymbol u u.
- 数据的总方差等于所有特征值的和,也就是样本方差 s 2 s^2 s2 之和: 总方差 T = σ 1 2 + σ 2 2 + ⋯ + σ m 2 = s 1 2 + s 2 2 + ⋯ + s m 2 = trace ( 迹,即对角元素之和 ) \pmb{总方差 \,T=\sigma_1^2+\sigma_2^2+\cdots+\sigma_m^2=s_1^2+s_2^2+\cdots+s_m^2=\textrm{trace}(迹,即对角元素之和)} 总方差T=σ12+σ22+⋯+σm2=s12+s22+⋯+sm2=trace(迹,即对角元素之和)
- S S S 的第一特征向量 u 1 \boldsymbol u_1 u1 是数据分布最显著的方向,这个方向对应总方差的一部分,比例为 σ 1 2 T . \displaystyle\frac{\sigma_1^2}{T}. Tσ12.
- 下一个特征向量 u 2 \boldsymbol u_2 u2(与 u 1 \boldsymbol u_1 u1 正交)对应了更小一些的部分,比例为 σ 2 2 T \displaystyle\frac{\sigma^2_2}{T} Tσ22.
- 当对应的比例足够小时停止下来,此时得到的 R R R 个方向可以说明数据的绝大部分。原先的 n n n 个数据点都很接近由基向量 u 1 \boldsymbol u_1 u1 到 u R \boldsymbol u_R uR 所形成的 R R R 维子空间,这些基向量 u 1 , u 2 , ⋯ , u 2 \boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_2 u1,u2,⋯,u2 就是 m m m 维空间的主成分(principal components).
- R R R 是 A A A 的 “有效秩(effective rank)”,实际的秩 r r r 很可能是 m m m 或 n n n:满秩矩阵。
三、垂直最小二乘
可能很多人都不知道 Figure 7.2 中的最优直线(
u
1
\boldsymbol u_1
u1 方向上的直线)也解决了垂直最小二乘(prependicular least squares)的问题,即正交回归(orthogonal regression)问题:
各点与该直线距离的平方和是最小值。
\pmb{各点与该直线距离的平方和是最小值。}
各点与该直线距离的平方和是最小值。证明: 将每一列
a
j
a_j
aj 分解成
u
1
\boldsymbol u_1
u1 和
u
2
\boldsymbol u_2
u2 方向上的两个分量:
直角三角形
∑
j
=
1
n
∣
∣
a
j
∣
∣
2
=
∑
j
=
1
n
∣
a
j
T
u
1
∣
2
+
∑
j
=
1
n
∣
a
j
T
u
2
∣
2
(
7.3.1
)
\pmb{直角三角形}\kern 10pt\sum_{j=1}^n||\boldsymbol a_j||^2=\sum_{j=1}^n|\boldsymbol a_j^T\boldsymbol u_1|^2+\sum_{j=1}^n|\boldsymbol a_j^T\boldsymbol u_2|^2\kern 15pt(7.3.1)
直角三角形j=1∑n∣∣aj∣∣2=j=1∑n∣ajTu1∣2+j=1∑n∣ajTu2∣2(7.3.1)左侧的和是数据点
a
j
\boldsymbol a_{j}
aj(
A
A
A 的列)长度的平方,右侧的一个和是
u
1
T
A
A
T
u
1
\boldsymbol u_1^TAA^T\boldsymbol u_1
u1TAATu1,即是
a
j
\boldsymbol a_j
aj 在
u
1
\boldsymbol u_1
u1 方向上投影长度的平方和,若
u
1
\boldsymbol u_1
u1 为单位向量,则
a
j
T
u
1
\boldsymbol a^T_j\boldsymbol u_1
ajTu1 即其在
u
1
\boldsymbol u_1
u1 方向上投影的长度;同理,第二个和即是
a
j
\boldsymbol a_j
aj 在
u
2
\boldsymbol u_2
u2 方向上投影长度的平方和。所以,当我们选择特征向量
u
1
\boldsymbol u_1
u1 时,即在主成分分析(PCA)中最大化了第一个和,同时使得第二个和取得了最小值,第二个和(数据点和最优直线距离的平方和)就是垂直最小二乘解问题的最小值。
通常最小二乘法是使用到最优直线垂直距离得到了一个线性方程
A
T
A
x
^
=
A
T
b
A^TA\hat {\boldsymbol x}=A^T\boldsymbol b
ATAx^=ATb,而 PCA 通过使用垂直距离得到了一个关于
u
1
\boldsymbol u_1
u1 的特征值问题,“Total least squares 总体最小二乘” 则不仅考虑
A
A
A 也会考虑
b
\boldsymbol b
b 的相关误差,这两种是不一样的最小二乘。
四、样本相关系数矩阵
数据分析的主要工作基本都在中心化矩阵 A A A,但是 A A A 中的测量值可能有不同的单位,像英寸、磅、年和美元等,单位的改变(如英寸变为米或者年变成秒)将会对 A A A 和 S S S 的行产生重大影响。如果单位的转换是一个大问题,我们将协方差矩阵 S S S 改为相关系数矩阵 C C C: 用对角矩阵 D 重新调整 A , D A 的每行的长度都是 n − 1 . 样本相关系数矩阵 C = D A A T D n − 1 的对角线元素都是 1 用对角矩阵\,D\,重新调整\,A,DA\,的每行的长度都是\,\sqrt{n-1}.\\\pmb{样本相关系数矩阵\,C=\frac{DAA^TD}{n-1}\,的对角线元素都是\,1} 用对角矩阵D重新调整A,DA的每行的长度都是n−1.样本相关系数矩阵C=n−1DAATD的对角线元素都是1概率与数理统计中有期望协方差矩阵 V V V 和期望相关系数矩阵(对角元素均为 1 1 1),它们都用概率值代替了实际的测量值。协方差矩阵预测的是未来的测量值在它平均值周围的分散程度,而 A A A 和样本协方差矩阵 S S S 以及缩放后的相关系数矩阵 C = D S D C=DSD C=DSD 处理的都是真实数据,这些都很重要 —— 它们是统计学与线性代数中的正定矩阵和 SVD 的重要联系。
五、欧洲人的基因变异
我们可以通过研究基因组来跟踪人类的变化,而为了管理这些海量的数据,弄清楚基因变异的一个比较好的方法是利用 SNP(single-nucleotide polymorphism,单核苷酸多态性),不寻常的等位基因(来自父本和母本的 A/C/T/G 碱基对)可以根据 SNP 来计数: SNP = 0 表示相比基本碱基对没有变化:正常的基因型 SNP = 1 表示相比基本碱基对有一处变化 SNP = 2 表示相比基本碱基对都出现了变化 \begin{array}{ll}\textrm{SNP\,=\,0}&表示相比基本碱基对没有变化:正常的基因型\\\textrm{SNP\,=\,1}&表示相比基本碱基对有一处变化\\\textrm{SNP\,=\,2}&表示相比基本碱基对都出现了变化\end{array} SNP=0SNP=1SNP=2表示相比基本碱基对没有变化:正常的基因型表示相比基本碱基对有一处变化表示相比基本碱基对都出现了变化未中心化的矩阵 A 0 A_0 A0 的每一列对应一个人,每一行对应一种碱基对的 SNP,则元素大部分都是 0 0 0,有一些 1 1 1 和数量不多的 2 2 2。我们不会测试所有的 30 30 30 亿个碱基对。在将 A 0 A_0 A0 的每个元素减去它所在的行的平均值后, A A T AA^T AAT 的特征向量将会揭示一些信息。Figure 7.3 中, A A A 的第一和第二奇异值向量几乎再现了欧洲地图。
这说明:法国、德国和意大利的 SNP 是大不相同,即使是瑞士地区的法语、德语和意大利语地区的 SNP 也不相同!只有西班牙和葡萄牙惊人的混杂在一起,难以区分。通常来说,DNA 可以揭露出生地,精度在
300
k
m
300km
300km 以内(约
200
200
200 英里),如果祖父母是在不同的出生地,通常孙子的出生地在两者之间。
有意义的信息是什么呢?如果我们通过检测基因组来了解它们和疾病有什么关联,那么就一定不能够忽略地域的差异,如果不根据地理因素来修正结果,那么看起来有重大医学意义的发现可能完全是误导。混杂(Confounding)在医学基因学中是一个严重的问题,PCA 和人口基因学可以帮助解决这个问题 —— 移除那些因为地理因素但是没有医学意义的影响。
实际上,“空间统计学(spatial statistics)” 是一个棘手的领域,例如:每个
1
,
C
,
1
1,C,1
1,C,1 这样的三对角矩阵都毫无意外的受到两个相邻的全
1
1
1 对角线的影响,但是它的奇异向量可以由正弦或余弦函数描述,并且独立于
C
C
C,大部分的奇异向量可能对描述原始矩阵没有意义。
可能统计学相比于数学能够提供更多的论证?将一个大数据简化成一个小的 “
P
P
P 值(
P
−
v
a
l
u
e
P-value
P−value)” 可能有指导意义,也可能极不靠谱。
P
P
P 值在很多文献中都有出现,它表示观测值与原假设(在随机意义下)一致的概率。如果随机的抛一枚均匀的硬币五次,那么五次正面全部向上的概率是
P
=
1
32
P=\displaystyle\frac{1}{32}
P=321(如果是
5
5
5 次全部正面或反面向上,概率
P
=
2
32
P=\displaystyle\frac{2}{32}
P=322)。通常
P
P
P 值小于
0.05
0.05
0.05 会倾向于拒绝原假设 —— 或许抛硬币是一个骗局。在这里,虽说
P
P
P 值并不是统计学中最可靠的指标,但是它非常便于使用。
六、特征人脸
我们可能觉得人脸识别并不依赖于线性代数,但是 SVD 在早期广为人知的应用就是人脸识别(face recognition)。我们不压缩图像,而是识别它。
具体方法是,首先是构造一个
n
n
n 张不同类型的人脸图像组成的 “训练集(training set)”,每个图像所有的像素灰度排成一列,成为一个很长的列向量,
A
0
A_0
A0 一定要中心化:将它的每一列都减去其所在列的平均值得到
A
A
A。
A
A
A 的第一奇异向量
v
1
\boldsymbol v_1
v1 将会显示与陌生人脸最为匹配的已知人脸的组合,然后第二奇异向量
v
2
\boldsymbol v_2
v2 可以告诉我们下一个最优组合。
最后我们可能会用到
A
A
A 的
R
R
R 个从大到小排列的奇异值
σ
1
≥
σ
2
≥
⋯
≥
σ
R
\sigma_1\geq\sigma_2\ge\cdots\ge\sigma_R
σ1≥σ2≥⋯≥σR 所对应的奇异向量
v
1
,
v
2
,
⋯
,
v
R
\boldsymbol v_1,\boldsymbol v_2,\cdots,\boldsymbol v_R
v1,v2,⋯,vR,它们能够比其它的任何
R
R
R 个向量更能准确的识别陌生人脸。可能这些特征人脸(eigenfaces) 中的
R
=
100
R=100
R=100 个
A
v
1
A\boldsymbol v_1
Av1 就可以捕捉到训练集中几乎所有的图像变化,这
R
R
R 个特征人脸就生成了 “人脸空间(face space)”。
这份有效的方案是由 Matthew Turk 和 Alex Pentland 提出,它是由 Sirovich 和 Kirby 给出的一种使用 PCA 压缩人脸图像的方法发展而来。PCA 提供了一种使用代数的方法区分几何或光度相似性的机制。将首个主成分(第一奇异向量)汇集为首个特征人脸,当然要将每列的平均值再加回去,否则无法看到人脸!
注: Nature 中的一个有趣的稿件(Lee and Seung,vol. 401, 21 Oct. 1999)对比了 PCA 和 NMF(非负矩阵分解:Nonnegative Matrix Factorization),NMF 不允许在奇异向量
v
\boldsymbol v
v 中出现负元素,所以它在运算时只使用加法,这个需要更多的向量但是通常结果也更有意义!
七、特征人脸的应用
第一个使用 PCA 人脸识别的商业应用是在执法和商业部门。早期的测试是在坦帕(Tampa,美国的一个城市)举行的第
35
35
35 届超级碗(Super Bowl)橄榄球大赛中,但是受到的观众们很多抱怨,因为这项测试并没有提前通知球迷,报纸开始将这届超级碗称为 “偷窥碗(Snooper Bowl)”。最初的特征人脸思想现在应该没有继续在商业上使用(即使是秘密的)。SVD 新的应用有其它的识别问题:特征语音、特征步态、特征眼睛、特征表情等。
目前来说人脸图像空间并不是线性的,所以想要非线性的 PCA.
八、模型降阶
对于一个大型的动态问题,计算资源的花费将会非常巨大,“动态的” 意味着解
u
(
t
)
\boldsymbol u(t)
u(t) 将随时间的变化而变化。流体流动、化学反应、波传播、生物生长、电子系统等问题无处不在。模型的简化(reduced model)是要识别重要的系统状态。 对于简化后的模型我们可以用低很多的代价来计算所需要的信息。
模型简化是一个非常重要的计算方法,为了简化原始的大规模的问题,人们提出了很多很好的方法。一种简单且常用的方法就是抓拍数据流的 “快照(snapshots)”,然后将它们置于矩阵
A
A
A,找到主成分(
A
A
A 的左奇异向量),然后在它们更小一些的子空间上处理问题:
一张
快照
就是描述系统状态的一个列向量
将它当作真实状态
u
(
t
∗
)
的近似
由
n
张快照构建矩阵
A
,
它的列生成有效的状态范围
\begin{array}{l}一张\pmb{快照}就是描述系统状态的一个列向量\\将它当作真实状态 \,\boldsymbol u(t^*)\,的近似\\由\,n\,张快照构建矩阵\,A,它的列生成有效的状态范围\end{array}
一张快照就是描述系统状态的一个列向量将它当作真实状态u(t∗)的近似由n张快照构建矩阵A,它的列生成有效的状态范围先求出
A
A
A 的前
R
R
R 个左奇异向量
u
1
,
u
2
,
⋯
,
u
R
\boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_R
u1,u2,⋯,uR,它们是本征正交分解(POD:Proper Orthogonal Decomposition)的一组基,在实际中,我们选择
R
R
R 时应该满足:
方差
≈
能量
σ
1
2
+
σ
2
2
+
⋯
+
σ
R
2
占
σ
1
2
+
σ
2
2
+
⋯
+
σ
n
2
的
99
%
或
99.9
%
\pmb{方差\approx能量}\kern 15pt\sigma_1^2+\sigma_2^2+\cdots+\sigma_R^2\,占\,\sigma_1^2+\sigma_2^2+\cdots+\sigma_n^2\,的\,99\%\,或\,99.9\%
方差≈能量σ12+σ22+⋯+σR2占σ12+σ22+⋯+σn2的99%或99.9%这些向量是重构
A
A
A 中快照的最优基向量,如果这些快照选择的合适,那么
u
1
,
u
2
,
⋯
,
u
R
\boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_R
u1,u2,⋯,uR 的线性组合将会非常接近精确解
u
(
t
)
\boldsymbol u(t)
u(t),这个解是关于时间
t
t
t 和参数
p
p
p 的。最终的效果取决于这些快照!SVD 不仅可以压缩图像,也可以压缩数据。
九、互联网搜索
一般认为谷歌 Google 是通过跟踪网络链接的路径来建立搜索排名的。当链接路径经常指向同一个网站时,该网站的排名就靠前。访问频率给出了 “网站矩阵(Web matrix)” 的主要特征向量(
λ
=
1
\lambda=1
λ=1)—— 要解决的最大的特征值问题。
马尔可夫矩阵中的数据来自
30
30
30 亿个网站,它有超过
30
30
30 亿个行和列。
谷歌的很多的这种重要的技术都保密的很好,他们可能是先以一个初始特征向量来作为首轮近似,然后是快速的随机游走。为了获得更高的排名,需要有大量的来自重要网站的链接。
下面是 SVD 在网络搜索引擎中的一个应用。当搜索一个单词时,例如输入 “四个子空间”,将会得到一个按照重要性排列的网站列表。
早期提出 HITS(hyperlink-induced topic search,基于超链接的主题搜索)算法生成网站的排序列表,它是根据关键词索引找到大约
200
200
200 个网站,下面只需要查看网站之间的链接。搜索引擎更多的是基于链接而不是内容。
从上述的
200
200
200 个网站,以及所有链接到它们的网站和它们所链接的网站开始,根据链出和链入情况来确定重要性,然后依序排列:
- 权威网站:很多网络,尤其是中心节点(hubs)都链接到该网站。
- 中心节点:它的链接指向列表中的很多网站,尤其是权威网站(authorities)。
我们用数字
x
1
,
x
2
,
⋯
,
x
N
x_1,x_2,\cdots,x_N
x1,x2,⋯,xN 来排序权威网站,
y
1
,
y
2
,
⋯
,
y
N
y_1,y_2,\cdots,y_N
y1,y2,⋯,yN 排序中心节点,用数值
x
i
0
x_i^0
xi0 和
y
i
0
y_i^0
yi0 (右上角的数字表示迭代次数,不是乘方)表示网站
i
i
i 的链入和链出数。
重点是:好的权威网站有来自于重要网站(如中心节点)的链接,比如来自于大学网站的链接比来自于朋友网站的权重更大。好的中心节点链接到重要网站(如权威网站),比如到 amazon.com(亚马逊) 的链接要比 wellesleycambridge.com(某出版公司)的链接更重要。考虑到与重要网站的链接数量(用
x
0
\boldsymbol x^0
x0 和
y
0
\boldsymbol y^0
y0 描述),原始的计数
x
0
\boldsymbol x^0
x0 和
y
0
\boldsymbol y^0
y0 要更新到
x
1
\boldsymbol x^1
x1 和
y
1
\boldsymbol y^1
y1:
权威网站
:
x
i
1
=
所有
链入
i
的链接
y
i
0
之和
中心节点
:
y
i
1
=
所有
从
i
链出
的链接
x
j
0
之和
(
7.3.2
)
\begin{array}{l}\pmb{权威网站}:x_i^1=所有\pmb{链入\,i\,}的链接\,y_i^0\,之和\\\pmb{中心节点}:y_i^1=所有\pmb{从\,i\,链出}的链接\,x_j^0\,之和\end{array}\kern 15pt(7.3.2)
权威网站:xi1=所有链入i的链接yi0之和中心节点:yi1=所有从i链出的链接xj0之和(7.3.2)用矩阵语言就是
x
1
=
A
T
y
0
\boldsymbol x^1=A^T\boldsymbol y^0
x1=ATy0 和
y
1
=
A
x
0
\boldsymbol y^1=A\boldsymbol x^0
y1=Ax0,矩阵
A
A
A 的元素是
1
1
1 或
0
0
0,当
i
i
i 链接到
j
j
j 时
a
i
j
=
1
a_{ij}=1
aij=1。用图论语言描述,
A
A
A 是一个网络 “邻接矩阵(adjacency matrix)”,它是一个规模庞大的矩阵。新的
x
1
\boldsymbol x^1
x1 和
y
1
\boldsymbol y^1
y1 给出了更好的排序,但是并不是最好的。按照(7.3.2)再进一步,由
A
T
A
x
0
A^TA\boldsymbol x^0
ATAx0 和
A
A
T
y
0
AA^T\boldsymbol y^0
AATy0 得到
x
2
\boldsymbol x^2
x2 和
y
2
\boldsymbol y^2
y2:
权威网站
:
x
2
=
A
T
y
1
=
A
T
A
x
0
中心节点
:
y
2
=
A
x
1
=
A
A
T
y
0
(
7.3.3
)
\begin{array}{l}{\color{blue}权威网站}:\boldsymbol x^2=A^T\boldsymbol y^1=A^TA\boldsymbol x^0\\{\color{blue}中心节点}:\boldsymbol y^2=A\boldsymbol x^1=AA^T\boldsymbol y^0\end{array}\kern 15pt(7.3.3)
权威网站:x2=ATy1=ATAx0中心节点:y2=Ax1=AATy0(7.3.3)以上两步我们左乘了
A
T
A
A^TA
ATA 和
A
A
T
AA^T
AAT,二十步的话左乘的是
(
A
T
A
)
10
(A^TA)^{10}
(ATA)10 和
(
A
A
T
)
10
(AA^T)^{10}
(AAT)10。做幂运算时,
A
T
A
A^TA
ATA 最大的特征值
σ
1
2
\sigma_1^2
σ12 将起主导作用。 当迭代的次数足够大时,向量
x
\boldsymbol x
x 和
y
\boldsymbol y
y 将分别沿着
A
T
A
A^TA
ATA 和
A
A
T
AA^T
AAT 的特征向量
v
1
\boldsymbol v_1
v1 和
u
1
\boldsymbol u_1
u1 方向。可以通过幂方法(power method) 来计算 SVD 中的最大项。令人惊奇的是线性代数可以帮助理解网络!
十、金融中的 PCA:利率动力学
金融数学经常会用到线性代数和 PCA,下面选择一个应用:国债收益率曲线(yield curve for Treasury securities),“收益率(yield)” 是为债券或票据等支付的利息,利率取决于到期时间,对于长期债券(
3
3
3 到
20
20
20 年)利率会随时间而增加。美联储(the Federal Reserve)调整短期收益率,用以降低或刺激经济。收益曲线为风险管理员、交易员和投资者所使用。
下面是
2001
2001
2001 年
6
6
6 个交易日的数据 —— 每一列是每日的收益率。“期限(tenor)” 是到期时间,MO 表示月, YR 表示年。左边六列是利率,每天都会变化;右边的五列是日间利率差,减去每行的平均值所得,要注意单位是
0.01
%
0.01\%
0.01%。这个就是中心化矩阵
A
A
A,每行的元素相加为零。实际上应用中要考虑的是
252
252
252 个工作日,而不是这里的
5
5
5 或
6
6
6 个工作日(一年代替一周)。
由于有五列,我们可能希望有五个奇异值,但是这五个列向量加起来是零向量(因为中心化后的
A
A
A 每行加起来为零),所以
S
=
A
A
T
/
(
5
−
1
)
S=AA^T/(5-1)
S=AAT/(5−1) 只有四个非零特征值
σ
1
2
>
σ
2
2
>
σ
3
2
>
σ
4
2
\sigma_1^2>\sigma_2^2>\sigma_3^2>\sigma_4^2
σ12>σ22>σ32>σ42,其中
σ
i
\sigma_i
σi 是奇异值,总方差
T
=
σ
1
2
+
σ
2
2
+
σ
3
2
+
σ
4
2
T=\sigma_1^2+\sigma_2^2+\sigma_3^2+\sigma_4^2
T=σ12+σ22+σ32+σ42 等于
S
S
S 的迹,奇异值的
σ
i
2
\sigma_i^2
σi2 和总方差
T
T
T 的比值对应了每个主成分(
S
S
S 的每个特征向量
u
i
\boldsymbol u_i
ui):
σ
1
σ
i
2
σ
i
2
/
T
主成分
u
1
36.39
1323.9
0.7536
主成分
u
2
19.93
397.2
0.2261
主成分
u
3
5.85
34.2
0.0195
主成分
u
4
1.19
1.4
0.0008
主成分
u
5
0.00
0.0
0.0000
T
=
1756.7
‾
1.0000
‾
\begin{array}{lrrr}&\sigma_1&\sigma_i^2&\sigma_i^2/T\\主成分\,\boldsymbol u_1&36.39&1323.9&0.7536\\主成分\,\boldsymbol u_2&19.93&397.2&0.2261\\主成分\,\boldsymbol u_3&5.85&34.2&0.0195\\主成分\,\boldsymbol u_4&1.19&1.4&0.0008\\主成分\,\boldsymbol u_5&0.00&0.0&0.0000\\&&\overline{T=1756.7}&\overline{1.0000}\end{array}
主成分u1主成分u2主成分u3主成分u4主成分u5σ136.3919.935.851.190.00σi21323.9397.234.21.40.0T=1756.7σi2/T0.75360.22610.01950.00080.00001.0000从上面的结果可知,比值
σ
i
2
T
\displaystyle\frac{\sigma_i^2}{T}
Tσi2 会很快降至零,对于更大规模的问题,通常这个比值快速下降后在底部形成一个平坦的部分(靠近
σ
i
2
=
0
\sigma_i^2=0
σi2=0),准确的定位出这两部分(主要的和微不足道的主成分)之间的转折处很重要。
我们也要理解每个主成分的含义。
A
A
A 的这些奇异向量
u
i
\boldsymbol u_i
ui 是
S
S
S 的特征向量,这些向量中的元素是 “载荷(loadings)”,下面是本例中收益率曲线所对应的向量
u
1
\boldsymbol u_1
u1 到
u
5
\boldsymbol u_5
u5(其中
S
u
5
=
0
S\boldsymbol u_5=0
Su5=0):
这
5
5
5 个向量
u
i
\boldsymbol u_i
ui 是标准正交的,它们分别构成了
A
A
A 的四维列空间的基和
A
T
A^T
AT 的一维零空间的基。那么它们在金融方面有什么意义呢?
u
1
度量了
9
个不同期限收益率的日间变化的加权平均
u
2
估算长短期债券之间收益率差的日间变化
u
3
表明曲线的日间变化(短、长期债券对比中期债券)
\begin{array}{l}\boldsymbol u_1\,度量了\,9\,个不同期限收益率的日间变化的加权平均\\\boldsymbol u_2\,估算长短期债券之间收益率差的日间变化\\\boldsymbol u_3\,表明曲线的日间变化(短、长期债券对比中期债券)\end{array}
u1度量了9个不同期限收益率的日间变化的加权平均u2估算长短期债券之间收益率差的日间变化u3表明曲线的日间变化(短、长期债券对比中期债券)下图显示向量
u
1
,
u
2
,
u
3
\boldsymbol u_1,\boldsymbol u_2,\boldsymbol u_3
u1,u2,u3 在
3
3
3 个月到
20
20
20 年共九个期限上的载荷。
A
A
A 的右奇异向量
v
i
\boldsymbol v_i
vi,就是
A
T
A
A^TA
ATA 的特征向量,它有
5
5
5 个分量且正比于向量
A
T
u
A^T\boldsymbol u
ATu,表明收益率的变动和一周之内长短期利差。
总方差
T
=
1756.7
T=1756.7
T=1756.7(
S
S
S 的迹
σ
1
2
+
σ
2
2
+
σ
3
2
+
σ
4
2
\sigma_1^2+\sigma_2^2+\sigma_3^2+\sigma_4^2
σ12+σ22+σ32+σ42)也是
S
S
S 的对角元素之和,它们是
A
A
A 各行的样本方差:
s
1
2
+
s
2
2
+
⋯
+
s
9
2
=
313.3
+
225.8
+
199.5
+
172.3
+
195.8
+
196.8
+
193.7
+
178.7
+
80.8
=
1756.7
s_1^2+s_2^2+\cdots+s_9^2=313.3+225.8+199.5+172.3+195.8+196.8+193.7+178.7+80.8=1756.7
s12+s22+⋯+s92=313.3+225.8+199.5+172.3+195.8+196.8+193.7+178.7+80.8=1756.7,每个
s
i
2
s_i^2
si2 都不超过
σ
1
2
\sigma_1^2
σ12,
1756.7
1756.7
1756.7 也是
A
T
A
n
−
1
\displaystyle\frac{A^TA}{n-1}
n−1ATA 的迹:即列方差。
注意:这里的 PCA 都是处理的中心化矩阵
A
A
A 的行,在有些应用中(如金融)中,矩阵通常要先转置,那么中心化的就是
A
A
A 的列,则用
A
T
A
A^TA
ATA 表示
S
S
S 的样本协方差矩阵,此
v
i
\boldsymbol v_i
vi 是更重要的主成分。