Differences

This shows you the differences between two versions of the page.

--- keynote:lesson03 [2010/04/08 11:46]
10921013
+++ keynote:lesson03 [2010/04/29 22:52]
11021002
@@ Line 33: / Line 33: @@
 ==== 3.1.5 主成分分析法与奇异值分解 ====
 奇异值分解是线性代数中一种重要的矩阵分解，在信号处理、统计学等领域有重要应用。奇异值分解在某些方面与对称矩阵或Hermite矩阵基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性，但还是有明显的不同。对称阵特征向量分解的基础是谱分析，而奇异值分解则是谱分析理论在任意矩阵上的推广。奇异值分解在统计中的主要应用为主成分分析（PCA），它是一种数据分析方法，用来找出大量数据中所隐含的“模式”,它可以用在模式识别，数据压缩等方面。PCA算法的作用是把数据集映射到低维空间中去。 数据集的特征值（在SVD中用奇异值表征）按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量张成空间为降维后的空间。
+  * 奇异值分解
+令$\widehat{X}$ 为一个居中的N×P维数据矩阵（设N>P）\[ X = \left[ \begin{array}{c|c|ccc}x_{0,0} & x_{1,0} & x_{2,0} & \cdots & x_{N-1,0}\\x_{0,1} & x_{1,1} & x_{2,1} & \cdots & x_{N-1,1}\\\vdots  & \vdots  & \vdots  & \ddots & \vdots\\x_{0,p-1} & x_{1,p-1} & x_{2,p-1} & \cdots & x_{N-1,p-1}\end{array} \right]_{N×p} = USV \] 即为$\widehat{X} $的奇异值分解，其中：
+  * U是N×p 的正交阵，称作左奇异向量。
+  * V是p×p 的正交阵，称作右奇异向量。
+  * S是对角阵，其中，$d_1>=d_2>=\cdots >=d_p>=0$，称为奇异值。
+奇异值分解总是存在的，并针对符号唯一。V的列即为主元，且$Z_j=U_jd_j$
+  * Eckart-Young定理
+令$S_q$ 为除了最前面的q个对角线元素之外的元素全为0的矩阵。则$\widehat{X_q}=US_qV^T$ 满足$\min_{rank(\widehat{X_q})=q} \big\Vert\widehat{X}-\widehat{X_q}\big\Vert$
+  * 主元分析例子-Eigenfaces(G. D. Finlayson, B. Schiele & J. Crowley.  Comprehensive colour image normalization. ECCV 98 pp. 475~490)
+{{:keynote:pca1.jpg|}} {{:keynote:pca2.jpg|}}
+  * PCA与降维
+通过奇异值分解进行空间变换：$X->Y$，形成从p维到q维的变换，其中p>>q，之后进行重现并计算误差。
 ==== 3.1.6 主成分分析法的不足 ====
-只适用于一般的离散数据集，对于非线性数据集不适用。
+.只适用于一般的离散数据集，对于非线性数据集不适用。
+.虽然如此，PCA 方法还是在许多领域（例如人脸识别）得到广泛应用，此外，也有提出使用 Kernel 方法扩展 PCA 的算法，亦即先将原始数据从特征空间映射到一个高维空间中，消除其非线性的性质，然后在这样的空间中应用 PCA ，亦即 KernelPCA 方法（参见 Scholkopf, B. and Smola, A. and Muller, K.R., //Kernel principal component analysis//, Artificial Neural Networks—ICANN'97）。
+除了 KernelPCA 之外，另一种将 PCA 用在非线性数据分析的方法是使用 LocalPCA ，现在比较热的流形学习中对于数据分布在一个低维流形上的假设实际上就是假定了数据在一个足够小的局部领域内是程线性的，这也正式 PCA 用武的地方，因此，在局部范围内使用 PCA 来分析流形结构也就成了一个顺理成章的事情。比如，在 tangent space learning 中，算法的目的是得出 manifold 的切空间，而如果使用局部方法的话，在一个流行局部的切空间其实就可以直接通过对局部 sample 进行 PCA 分解而求得。
+<note important>Extended by  --- //[[pluskid@gmail.com|张驰原]] 2010/04/26 14:28//</note>
+.以下是对课件的补充和扩展（介绍RPCA及其在CVPR2010人脸图像上的应用）：
+不适用于非高斯噪声污染的数据集。\\
+设数据$m\times n$矩阵$M=L+S$，$L$为潜在的低秩矩阵，$S$噪声矩阵。如果$S$非高斯噪声，例如稀疏且幅值不定的噪声，那么PCA将失效。\\
+{{:keynote:pca_done_well.jpg|}}\\
+{{:keynote:pca_fail.jpg|}}\\
+此时，宜用改进的模型RPCA(Robust PCA)。
+RPCA通过以下目标函数求解：
+<jsmath>\min_{L,S}\|L\|_{*}+\lambda \|S\|_{l_{1}} \;\; s.t. \; M=L+S</jsmath>
+$\lambda$是权重参数，通常设为$\lambda=\frac{1}{\sqrt{\max\{m,n\}}}$。 $\|\cdot\|_{*}$为核范数，即矩阵奇异值之和。$\|\cdot\|_{l_{1}}$为一范数，即矩阵元素绝对值之和。\\
+此凸函数具有唯一最小值。使用ALM(Augmented Lagrange Multiplier)求解，最小化增强的拉格朗日函数：
+<jsmath>\min_{L,S,Y}l(L,S,Y)=\min_{L,S,Y}\|L\|_{*}+\lambda \|S\|_{l_{1}}+ tr\{Y^{T}(M-L-S)\}+\frac{\mu}{2}\|M-L-S\|_{F}^{2}</jsmath>
+$\mu$为另一权重，可取值$\mu=nm/(4\|M\|_{1})$。$\|\cdot\|_{F}$为Frobenius范数，即矩阵元素平方和开根号。
+通过迭代计算求最优值:\\
+.初始化：$S_{0}=Y_{0}=0$，$k=0$\\
+.while $\|M-L-S\|_{F}>10^{-7}\|M\|_{F}$ do\\
+.  $L_{k+1}=D_{1/\mu}(M-S_{k}-Y_{k}/\mu)$\\
+.  $S_{k+1}=S_{\lambda/\mu}(M-L_{k+1}+Y_{k}/\mu)$\\
+.  $Y_{k+1}=Y_{k}+\mu (M-L_{k+1}-S_{k+1})$\\
+.  $k=k+1$\\
+.end while\\
+.输出$L,S$\\
+对于标量$x$，函数$S_{a}(x)=sgn(x)max\{|x|-a,0\}$，即截断操作。当输入为矩阵时，对每一元素独立操作。函数$D_a(X)$也是截断操作，但作用于矩阵奇异值：设矩阵$X$的SVD分解为$X=U\Sigma V^{T}$，那么$D_a(X)=US_{a}(\Sigma)V^{T}$。
+对RPCA做一些修改，可用于人脸对齐与去噪。这是RPCA研究团队一篇CVPR2010的工作：\\
+Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images. To appear in CVPR, June 2010.\\
+{{:keynote:rals.jpg|}}\\
+(a)算法输入40张同一人不同光照、遮挡，姿势和表情的图片。(b)-(d)为算法输出，算法同时完成对齐(b)、提取真实人脸（c）和分离噪声（异物）(d)。算法主要思路为寻找一组几何变换$\tau$使对齐后的图像$Dº\tau$能被分解为低秩成分和稀疏噪声。
+ <note important> --- //[[fancij@139.com|胡振方]] 2010/04/27 21:50//</note>
 ===== 3.2 非线性降维算法 =====
@@ Line 117: / Line 171: @@
 ==== 3.2.3 BoostMap ====
-  * Unordered List Item设计目标-大幅度降低图像数据库系统的获取时间
+  * 设计目标-大幅度降低图像数据库系统的获取时间
     嵌入（Embedding）被描述为一个机器学习任务，AdaBoost方法用来把多个简单的1维嵌入结合成为一个d维的嵌入；按照与一个查询对象的相似程度获得所有DB对象的排序。
-  * Unordered List Item主要想法
+  * 主要想法
     数据集S，距离函数D：S×S→ $R^1$
     {{:keynote:boostmap1.jpg|}}
     要点：D可能计算复杂；D可能不满足三角不等式。
   * 问题定义
-    嵌入被看做分类器，如果a与b或c接近，给出对a,b,c的估计。其中X为对象集，$D\le x$ 为距离函数。\[ \begin{equation} P\le x(q,x\le 1,x\le 2)= \{ \begin{array} 1 if D\le x(q,x\le 1)<D\le x(q,x\le 2)\\0 if D\le x(q,x\le 1)=D\le x(q,x\le 2)\\-1 if D\le x(q,x\le 1)>D \le x(q,x\le 2)\\ \end{array} \end{equation} \]
+    嵌入被看做分类器，如果a与b或c接近，给出对a,b,c的估计。其中X为对象集，$D\le x$ 为距离函数。\[ \begin{equation} P_x(q,x _1,x_2)=\left\{\begin{array}{cl}1 & \textrm{if }D_x(q,x_1)<D_x(q,x_2)\\0 & \textrm{if }D_x(q,x_1)=D_x(q,x_2)\\-1 & \textrm{if }D_x(q,x_1)>D_x(q,x_2)\end{array}\right. \end{equation} \] \[ (即近似函数P(r:x,y) = sgn(D(y,r)-D(x,r)))\] 找到一个嵌入$F:X→R^d$ 和一个测度$D_{R^d}$ \[ \tilde{F}(q,x_1,x_2)=D_{R^d}(F(q),F(x_2))-D_{R^d}(F(q),F(x_1)),\] 用来评价任意三元组。
-  *
+  * 例子：一些关于"北美城市”的近似函数
+     {{:keynote:boostmap2.jpg|}}
+  * BoostMap的输出
+输出是一个分类器：$ H = /sum_{j=1}^dα_j\tilde{F}_j$ 最终输出是一个嵌入$ F:X→R^d$ 和一个距离测度$ D:R^d×R^d→R^d$ \[ \begin{equation} F(x)=(F_1(x),\ldots,F_d(x))\end{equation}\]  \[ D_{R^d}\left((u_1,\ldots,u_d),(v_1,\ldots,v_d)\right)=\sum_{j=1}^d(α_j\big| u_j-v_j\big|)\]

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools