子空间算法

问题描述：设X1,X2,...,Xp为训练样本，每个Xi为M维矢量，要求一个N×M的矩阵A，使得：

Y N \times 1 = A N \times M X M \times 1

A N \times M = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ a 1 a 2 . . . a N ⎤ ⎦ ⎥ ⎥ ⎥ ⎥

当

N≪M时，这是一种降维算法。这里主要介绍两种降维算法：PCA与LDA。PCA是无监督的降维算法，计算出X变化最大的前N个方向并将X向这些方向投影，得到一个N维的向量Y。LDA是有监督的算法，根据类别标记找到最大化类间差异，最小化类内差异的方向。

主成分分析法（Principle Component Analysis）

将不同的样本投影到某一个方向上，若这些样本投影后具有较大的差异，则比较易于分类。所以我们要找这样一个方向a，使得X向a投影之后得到的Y的方差最大。

求第一个方向a1

假设我们找到了前N个满足上述要求的方向：a1,a2,...,aN，每个ai都是一个1×M维的矢量。
设训练样本有P个，对方向a1，有：
y1=a1X1,y2=a2X2,...,yp=a1Xp
上述问题要求：

M a x i m i z e : E (a 1) = \sum i = 1 p (y i - y ¯) 2

因为

y ¯ = 1 p \sum i = 1 p y i = 1 p \sum i = 1 p a 1 X i = a 1 X ¯

所以

E (a 1) = \sum i = 1 p (a 1 X i - a 1 X ¯) 2 = \sum i = 1 p (a 1 (X i - X ¯)) 2 = \sum i = 1 p [a 1 (X i - X ¯)] [a 1 (X i - X ¯)] T = a 1 \sum i = 1 p (X i - X ¯) (X i - X ¯) T a T 1 = a 1 Σ a T 1

其中，

Σ=∑pi=1(Xi−X¯)(Xi−X¯)T为协方差矩阵。优化问题化为：

M a x i m i z e : E (a 1) = a 1 Σ a T 1

S u b j e c t t o : a 1 a T 1 = 1

这个约束条件是因为方向的模可以认为是1。
用拉格朗日乘子法求解：

M (a 1) = E (a 1) + λ (a 1 a T 1 - 1)

\partial M \partial a 1 = Σ a T 1 - λ a T 1 = 0

Σ a T 1 = λ a T 1

所以，

aT1是

Σ的特征向量，

λ是

Σ的特征值。

E (a 1) = a 1 (Σ a T 1) = a 1 (λ a T 1) = λ a 1 a T 1 = λ

所以，要最大化

E(a1)，就是要最大化

λ，

aT1为

Σ最大的特征值所对应的特征向量。

求第二个方向a2

求解a2时，要保证a2与a1正交，优化问题是：

M a x i m i z e : E (a 2) = a 2 Σ a T 2

S u b j e c t t o : a 2 a T 2 = 1

a 1 a T 2 = a 2 a T 1 = 1

同样用拉格朗日乘子法可以求得

a2是

Σ第二大的特征值所对应的特征向量。
…

算法总结

1输入X1,X2,...,Xm
2Σ=∑pi=1(Xi−X¯)(Xi−X¯)T
3求Σ的特征值和特征向量：
λ1,λ2,...,λN,对应的特征向量，a1,a2,...,aN
4变换矩阵：

$A N \times M = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ a 1 a 2 . . . a N ⎤ ⎦ ⎥ ⎥ ⎥ ⎥$
计算Y:
$Y N \times 1 = A N \times M X M \times 1$

思考

问题：Σ的特征值中不为0的有多少？
- 若对称阵Σ的秩为r，则不为0的特征值有r个
- 一个N×1的向量与一个N×1的向量相乘，所得N×N的矩阵，秩最多是多少？答案是1。
- 一个秩为r1的矩阵加上一个秩为r2的矩阵，秩最多为r1+r2.
可知Σ的秩最多为m-1个，其中m是训练样本的个数。这是因为：(Xi−X¯)(Xi−X¯)T的秩为1，而X1−X¯,X2−X¯,...,Xm−X¯最多有m-1个是互相独立的。
综上，Σ的特征值中不为0的数目≤min(N,m−1)

线性判别分析（Linear Discriminant Analysis）

线性判别分析是一种有监督的降维算法。它的最优准则是：类间距离大，类内距离小。
以二分类问题为例，LDA问题可以描述成：

对 m 个 M 维 的 输 入 向 量 X 1, X 2, . . ., X m, 找 到 一 个 矩 阵 W ， 使 得 X ̃ = W X

首先，计算

X̃ 的数学期望：

μ 1 ~ = 1 N 1 = \sum X ̃ ϵ C 1 X ̃ ， μ 2 ~ = 1 N 2 = \sum X ̃ ϵ C 2 X ̃

方差:

稀疏表达（Sparse Representation）

稀疏表达问题可以描述为：对Y=AX,已知Y和A，求X。