线性判别分析(Linear Discriminant Analysis)
对于给定的标记数据(xi,ci),其中xi∈Rn,ci∈{0,1},此时设计一个分类器(Classifier),将这两类数据分开,另外这两类数据线性可分(存在一个超平面Σ1,将这两类数据分开,也就是说存在一个与超平面垂直的超平面Σ2,使所有的数据投影(Projection)到它上面,并且同样可分),如下图所示:
![简述LDA,PCA,SVD原理推导及其简单应用 简述LDA,PCA,SVD原理推导及其简单应用](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzM3Mi85Yzc4ZWQ0MTZmNmExZWQzNmQ2NjcxMWU2NzAxYmNkYy5wbmc=)
假定Σ2表示为w,则将数据X投影到n−1维超平面上,为可视化,我们设为1维,即
yi=wTxi
那么我们可以找到阈值
y0,当
yi≥y0为
C1类,否则为
C2类。
我们假定
C1有数据点
N1个,
C2有
N2个,则投影后的
类内均值及
松散度(Scatter)为,
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪m1=1N1∑i=1N1wTxi,m2=1N2∑i=N1+1N1+N2wTxi⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪s21=∑i=1N1(yi−m1)2,s22=∑i=N1+1N1+N2(yi−m2)2
那么目标函数为,
J(w)=(m1−m2)2s21+s22⟹J(w)=wTA1wwTA2w
其中,
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪A1=(m′2−m′1)(m′2−m′1)T,A2=∑i=1N1(xi−m′1)(xi−m′1)T+∑i=N1+1N1+N2(xi−m′2)(xi−m′2)T,m′1=1N1∑i=1N1xim′2=1N2∑i=N1+1N1+N2xi
Tip:至于常量已知矩阵
A1和
A2的上式推导也比较简单,只需利用
m1=wTm′1及
m2=wTm′2即可
记下来的任务就是求取
w,即,
∂J(w)∂w=∂∂w(wTA1wwTA2w)=0⟹A1w(wTA2w)=A2w(wTA1w)
说明只需A1w与A2w同向即可,又A1w=(m′2−m′1)(m′2−m′1)Tw≡λ(m′2−m′1),即只需w与A−12(m′2−m′1)同向即可
主成分分析(Principal Component Analysis)
要点就是使样本点在某个方向上的投影具有最大方差,如下图所示,
![简述LDA,PCA,SVD原理推导及其简单应用 简述LDA,PCA,SVD原理推导及其简单应用](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzgyMi82YTY5ZDVkOGZiYjk2YTQ1YzY1NjkzZTBjMDdkY2JmNi5wbmc=)
对于具有n个特征的m个样本,可以得到一个样本集矩阵,
A=⎛⎝⎜⎜⎜⎜⎜a11 a12 ⋯ a1na21 a22 ⋯ a2n ⋮ ⋮ ⋱ ⋮am1 am2 ⋯ amn⎞⎠⎟⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜⎜aT1aT2 ⋮aTm⎞⎠⎟⎟⎟⎟⎟
寻找样本集的
主方向u,将样本集投影到某个方向上,以此计算出
m个投影点的
方差,并认为
方差最大的方向就为主方向。我们假定样本集是
去均值化的,则样本点集在某个方向上的投影为,
A⋅u=⎛⎝⎜⎜⎜⎜⎜a11 a12 ⋯ a1na21 a22 ⋯ a2n ⋮ ⋮ ⋱ ⋮am1 am2 ⋯ amn⎞⎠⎟⎟⎟⎟⎟⋅u=⎛⎝⎜⎜⎜⎜⎜aT1aT2 ⋮aTm⎞⎠⎟⎟⎟⎟⎟⋅u=⎛⎝⎜⎜⎜⎜⎜aT1uaT2u ⋮aTmu⎞⎠⎟⎟⎟⎟⎟
则向量A⋅u的方差Var(A⋅u)=(Au−E)T(Au−E)=(Au)TAu=uTATAu
其中,
E={1m∑mi=1aTiu}m,也就是投影点的期望组成m维列向量
因此,目标函数为,
J(u)=uTATAu, Subject to: ||u||2=1
则Lagrange function为,
L(u)=uTATAu−λ(uTu−1)
令∂L(u)∂u=0⟹(ATA)u=λu,我们得出
方向向量u即为方阵ATA的特征向量,而λ即为它的特征值,也为投影点集在这个方向(特征向量)上的方差。这个过程实质上也是特征值分解(方阵)的过程,后面我们分析更加一般的矩阵分解,奇异值分解(不一定为方阵),这样我们将方阵
ATA的特征值由大到小进行排序,我们选择比较大的特征值
λi(
通常最大的10%的特征值之和就占所有特征值之和的99%)所对应的特征向量
vi作为
主成分来近似表示原始矩阵,而且这些向量之间均是线性无关的,甚至正交的,这样也就达到了降维(Dimensionality Reduction)的目的。
奇异值分解(Singular Value Decomposition)
若A是m×n的矩阵,那么ATA就为n×n的方阵,那么,由(ATA)vi=λivi,令,
⎧⎩⎨⎪⎪δi=λi−−√ui=1δiAvi⟹A=UΣVT,这个过程只需反代回去即可验证
后者就为奇异值分解SVD。上式中若为复数域,则为A=UΣVH,U和V为酉矩阵,Σ为所有奇异值组成的对角矩阵
一般地,
ATA=VΣHUHUΣVH=VΣHΣVH
AAT=UΣVHVΣHUH=UΣHΣUH
因此
U的列向量
ui(左奇异向量)为
AAH的特征向量,
V的列向量
vi(右奇异向量)为
AHA的特征向量,
Σ的对角元为
ΣHΣ或
ΣΣH的特征值的平方根
直观上,奇异值分解将矩阵分解成若干个秩一矩阵之和,即,
A=σ1u1vH1+σ2u2vH2+⋯+σrurvHr
其中
uivHi都是秩为1的矩阵,对这些奇异值进行排序,
σ1≥σ2≥⋯≥σr>0,这样我们
选择比较大的特征值,而使较小的特征值为0(也就是舍去它们),就可以通过这些奇异值及其对应的奇异向量还原矩阵。
当然,SVD还可用于求矩阵伪逆(M-P),数据压缩,个性化推荐等等
主要参考文献
- Machine Learning:A Probabilistic Perspective,Kevin P. Murphy, The MIT Press, 2012
- Prof. Andrew Ng, Machine Learning, Stanford University
- Pattern Recognition and Machine Learning Chapter 10, Christopher M. Bishop, Springer-Verlag, 2006