计算机视觉中svd

2016-09-02 10:13:43 u012521552 阅读数 4115
  • 极线几何

    掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法,了解RANSAC的基本思想

    1825人学习 CSDN就业班
    免费试看

计算机视觉和图像处理框架


一、概述

图像处理即传感器将图像信号转换为数字信号,再利用计算机对其进行加工处理的过程。其涉及到的方法主要有图像变换、图像编码、图像去噪、图像增强、图像恢复、图像分割、特征提取、图像识别等。
计算机视觉是一门研究如何让机器(计算机)像人一样看并理解周围世界的学科,其基本理论和研究方法,旨在从图像或者其他数据中获得相关信息。
从直观的角度看,我们可以说计算机视觉处理视频,图像处理处理图像,而视频由图像构成,当然这个说法只能用作理解,不够严谨。二者更科学的区别是计算机视觉重点研究映射到单幅图像或者多幅图像上的三维场景,如三维重建就是计算机视觉研究的内容;图像处理主要研究一个二维的数字图像,主要针对的是像素级的操作,例如提高对比度、边缘提取、几何变换等。
计算机视觉和图像处理有很大的交叉,之前我也会把机器学习和模式识别也加入到交叉部分,现在我倒觉得,把这两门学科总结为像数学和英语那样为基础服务更合适。

二、计算机视觉基本流程

一个信息处理系统,总对应着一个或多个Input和Output,计算机视觉系统也不例外,输入为从三维世界中采集到的数据,输出为系统对信息的理解。无外乎就以下几个部分:
1、数据采集(输入)
2、预处理: 去噪、增强
3、特征提取;
4、检测/跟踪/分割;
5、高级操作(分类、识别等)(输出)
关于图像检测与识别的区分:
目标检测:首先我们已经知道目标是什么,然后去图像中定位它的位置。(人脸检测、行人检测、车辆检测等)
图像识别:简单的说,是图像再认,从成千上万张图像中找到认识的那一张,犹如我们在大街上遇到一个一个人,然后就会去搜索我们见过的所有人,‘哦!我见过他’,如果再加上‘哦!我见他趟在天安门的水晶棺里!’,那么就等于识别系统识别到了一个图像的id和路径,这就是图像识别的过程,(对于一个从来没有出现过的目标,计算机是无法进行再认的,人也不行)。其处理过程主要包括:图像输入、预处理、特征提取、特征分类、匹配。
计算机视觉中的识别:是计算机视觉系统处理的高级过程,从再认的角度上讲,它们是一样的,然而出发点和‘识别’过程是不同的两个方面,计算机视觉中的识别重点在某一个领域内,比如行人行为识别(拥抱、指路、打架、偷车等),那么这个系统我们研究的就是人,车辆行为识别(是否酒驾、是否超速等),那就是一个交通监控系统,我们需要定义一个行为:什么是拥抱(偷车)或者什么是酒驾;而图像识别旨在从某一个库中去‘匹配’一个相同或者相似的图像(当然匹配的是特征)。

三、基本图像处理与分析

基于计算机视觉系统的整条主线,总结一下现有的一些理论和方法。
图像采集:(摄像机标定和矫正)
预处理:(去噪、增强、金字塔等)
特征提取:(BRIEF、颜色和直方图特征、FAST特征、Harris特征、HOG、SIFT、SURF等)
检测:(背景建模、特征+分类器(SVM、Adaboost、Random forest)、显著性监测等)
跟踪:(Mean-shift、TLD、粒子滤波、卡尔曼)
高级操作:(BOW)
上述主要介绍了整个系统中常用到的一些方法和理论,当然计算机视觉和图像处理的内容远不止这些,下面列一些主要的领域,然后再补充一点模式识别的内容:
人脸检测、人脸识别、目标检测和跟踪、OCR、阴影检测、场景理解、SLAM、视频监控等。

四、为我所用

最后主要总结一下能够为计算机视觉使用的一些理论和方法。
机器学习:用摄像机模拟人眼,cpu模拟人脑,对于‘白痴’cpu,告诉它学习的方法也就显得自然了。
模式识别:理论极强的一门学科,和ML、CV相辅相成,基于神经网络的DL大红大紫
Boosting、clustering、CS(Compressive Sensing)、DT(Decision Trees)、DP(Dynamical Programimg)、EM、GM(Graphical Model)、HMM、ICA、PCA、RF(random forest)、RANSAC、SVD(Singular Value Decomposition)、稀疏表示、SVM、小波、NN
英语:谁让我们落后于人家呢,师夷长技以制夷
数学:一切美好的基石,数学分析、概率、统计、矩阵、最优化等
计算机基础理论和方法:可能像组成原理、体系结构、操作系统、编译原理对算法研究帮助不大,不过数据结构和基本算法的作用却是相当大的,如果是做工程,前面的基础知识就显得很重要了。
产品:为什么提到产品,因为工业不等于研究,要想自己喜欢的学科真正能够服务于大众,理论和实际必须要结合起来。

2017-04-16 23:23:00 weixin_30349597 阅读数 20
  • 极线几何

    掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法,了解RANSAC的基本思想

    1825人学习 CSDN就业班
    免费试看

All the information in this passage is from  course (ROBOTICS:PERCEPTION,made by university of pennsylvania) on Coursera. If by any chance it violates the rights, I will delete it upon notification as soon as possible.

So today we will start talking about D squared, and single value decomposition. D squared is a very important concept
used many times in our engineering world. It was used for example by Gauss. In his calculation of the orbits,
of earth around the sun. In computer vision D square is used in many, many different cases. 

 

 

What we'll study through a sequence of examples?First, we're going to take a detour. So, a computation known as singular value decomposition or SVD. It is one of the most useful tools you will encounter in our computation of vision problems in the next few lectures. Singular value decomposition, is a way of taking a matrix a, and decomposing to three separate components. So matrix A, could be of many forms, it comes from many different reasons, and physical meanings. The end results is we have a matrix a of size m, by n. Given any matrix of A, which you can think of as a transformation themselves. We can decompose this matrix, into three components U, D, and V transpose, meaning that U, multiplied by D, multiplied by V transpose will reconstruct the matrix exactly. And this is a very interesting fact. Like any matrix A can be decomposed in this following fashion. 

And the U matrix that we have has a particular property. U matrix, can be thought of columns, and each columns with U, has a property that take a half part between themself equal to one, meaning that each column, the U, is a norm of one. Furthermore, if I take two columns U, and take that part out of them, the answer is zero, meaning the U's are constructed, such that all the columns, are perpendicular to each other. Second perpendicular to first, third perpendicular to both first, and second. Such you can think of the U's, essentially basis function, spanning the same space, as the columns of A. 

Similarly, the draws of the V transpose, also had the following form that takes any draws of the V transpose will have perpendicular vectors. Or mathematically, one could write, U transposed times U equal to I and V transposed V equal to I. So that's, the first fact of
the singular value decomposition. That a matrix A can decompose into a set of column vectors U perpendicular to each other, a diagonal matrix D, and a set of rogue perpendicular vectors V transposed. And multiplying the three matrices, reconstruct the matrix A exactly. And we can always do this. In the math lab, this is a function called SVD.

 The second, a fact of this decomposition is that the singular value matrix is diagonal forms. Meaning the elements are zero, and the non-zero elements sits, on the diagonal.  And one can always sort it, from large to small. So sigma one, larger than sigma two, all the way bigger than zero. So all the values on diagonals are positive, or zero. We will see cases when the last element is zero, or several of the elements are zero. The U matrix is going to be the size of same, as A and by n. The diagonal matrix singular value matrix is size, m by m, and the V transposed matrix is size m by m. 

 We can think of the U matrix, as set of basis. For example, if A is made of curve, and since this space where every column of A is a curve, we can think of the U matrix enclose the basis function, where the first base is, for example, is a horizontal curve, and the second basis function is a curve going down. And the third basis encode a curve going up, and down. Then we can think of the matrix V together with the singular value D, provides a coefficient for every column A. So, the coefficient of the beta1, beta2, beta3. So through a scaling of a beta1, beta2, beta3, it provides a reconstruction in column of A, which is represented by a curve here. As such we can think of U is basis, the columns of V transpose provide us the addresses. Multiply to the scale factor, give us the beta1 to beta n.

 

So, the first factor we can think of is SVD, as transforming matrix A, into it's basis function, and the transformed addresses. So let's just think of this painting by Mondrian, what is the SVD of this painting? Well first of all, what is this painting? The painting in our world is in fact a matrix. Where rows, and columns are pixels. And Mondrian, paintings are very good illustration of this basis, because all the Mondrian paintings are made of rows, and columns. So let's take this Mondrian painting, and first convert a colored image to a gray skull image, shown on the top left. Right here use the colormap jet in the matlab illustration, where red indicated bright pixels, blue means dark pixels. So this is a Mondrian in the black, and white world, but illustrated in the colormap jet. And we were take SVD of this image, which is made of thousands rows, many thousand columns, we see that we can construct SVD of this matrix. And to reconstruct from it a U matrix. And here, I illustrated only the first four columns of the U to highlight what it looks like. So first note, the first columns are almost uniforming it's values. The second column we can see, has some positive value which indicated in orange, and some negative values indicated in blue. As such, you can see that this perpendicular to the first column. In the image, what it's capturing, it's saying that Mondrian paintings are made of two halves.On the top half, which are one color, and the bottom part of the image is another color. Move out to the third column of U, we see, again, is made of some value, positive mean indicated in red, blue indicating the negative values. Again, this vector is perpendicular, to the first two columns. And again if you look at this picture, what it is indicating is telling us the Mondrian paintings for this picture has several rows have the same color, hence we have a basis vector with uniform color in it. Now just take in the four columns of SVD of this picture I can reconstruct this picture by taking the first four columns of U. The first four by four matrix of a singular value matrix D, and the four rows of V. And reconstructing the matrix through the matrix multiplication is shown in the bottom right. As you can see, this is not exactly the same but it's a very close approximation than where we started. As such, we can think of SVD is a process of simplifying what's in the matrix, very large matrix and then using a set of basis functions, illustrating U and using a set of addresses in V. 

 If I were to take more rows and more columns view matrix but not all of them. For example, I only take the first 20 columns of the U matrix, I can reconstruct the Mondrian painting fairly closely. In the center at what I've shown here is the log of the singular values. As you can see, the log of a single values drop off pretty rapidly, indicating that many dimensions in the basis function has a scale factor near 0. And we're going to use this factor for many different cases. And we're going to use this for using SVD as a clean up process of cleaning up a matrix. Or we can use this factor to approximate a large dimensional matrix with a few basis functions. So now let's look at Gauss himself in rows and columns. So Gauss is not painted by Mondrian so he has many orientations edges horizontal, not lines with horizontal vertical directions, but nonetheless we can take Gauss' image as a matrix and reconstruct itself. So on the middle we have a Gauss image reconstructed with more basis functions and the right we see a Gauss image reconstruct with a few vectors. And this is shown in grayscale. As you can see, it still captured the structure of his face fairly reasonably with on a few basis functions. And this is because many rows and many columns of this image are redundant, they are not exactly the same but it can be represented by a few basis vectors. 

 

 

So this is a look at a picture as a matrix where there are thousands rows and thousands of columns. One can also look at a picture as a vector by taking all of the rows, all of the columns and stacking them into one, long vector. So if I have a 1000 by 1000 image, that would be a vector of a million dimension long. This is illustrating here images not as a matrix, but image as a vector. As such that I can take many, many pictures, many, many pictures of people's face for example. Each one forms a vector and I can stack the vector together each one, 1 million direction long, 1 dimensional long, and then maybe thousand peoples, we have a million by thousand matrix. I can take a single value decomposition with that matrix that gives me a set of basic function U, and it reshape the use back to the image space. And this is what happens when we do that. On the left we have a set of images of the face. Each one stretch into vector space, placed column-wise next to each other. We computed SVD of this matrix, and we take the first few columns of U, and reshape back to the image space. And this is called eigenfaces, as you can see those eigenfaces capture different characteristics of the face. For example some capture the hair, some capture the mouth. And from those basis functions, one can re-express our faces as addresses in those spaces. 

 

 

 Here is a set of images captured by an artist for people in Berlin. On the left we have the first basis function for the man. On the right we have a first basis picture of the woman. Taking a view of eigenvectors as well as addresses, we can see here are three faces reconstructed by the same eigenvector or use different coefficients on this eigenvector. So, here we show different ethnic group it will show you by this eigenvector, address from one point address space to another point address space. Here we have a different eigenvector corresponding to the age changes. Again, as we change the address on this eigenvectors faces transform itself. So now we are seeing eigenvectors, singular value vectors, as our basis functions and as such that we can think of it as our basis functions and their addresses and together they reconstructed the matrix or in this case image for me. Once we have decomposed a matrix A into a singular value decomposition, U times D times V transpose, we can also understood the concept of rank and row space. A rank of matrix A is simply defined as the number of the non-zero singular values in the matrix D. So we call that r, rank of A equal to r. The number of elements non-zero on the diagonal. And r is going to be less than equal to the dimension of m or n. The null space is corresponding to exactly those elements associated with singular values equal to zero. So if the rank is r, then the columns in V or rows in V transpose associated with those dimensions where single value is 0, are the null space. So we take the columns, from r plus one all the way to n. If r is the rank, r plus one to n columns of V is the null space of A. And we have the following property that A Times the nullspace V, r plus one to n, equal to 0. 

 

 

转载于:https://www.cnblogs.com/Hummm/p/6720781.html

2016-10-24 22:58:49 shenziheng1 阅读数 44420
  • 极线几何

    掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法,了解RANSAC的基本思想

    1825人学习 CSDN就业班
    免费试看

1.前言

第一次接触奇异值分解还是在本科期间,那个时候要用到点对点的刚体配准,这是查文献刚好找到了四元数理论用于配准方法(点对点配准可以利用四元数方法,如果点数不一致更建议应用ICP算法)。一直想找个时间把奇异值分解理清楚、弄明白,直到今天才系统地来进行总结。
上一次学习过关于PCA的文章,PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。特征值和奇异值在大部分人的印象中,往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面,也很少讲任何跟特征值与奇异值有关的应用背景。奇异值分解是一个有着很明显的物理意义的一种方法,它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示,这些小矩阵描述的是矩阵的重要的特性。就像是描述一个人一样,给别人描述说这个人长得浓眉大眼,方脸,络腮胡,而且带个黑框的眼镜,这样寥寥的几个特征,就让别人脑海里面就有一个较为清楚的认识,实际上,人脸上的特征是有着无数种的,之所以能这么描述,是因为人天生就有着非常好的抽取重要特征的能力,让机器学会抽取重要的特征,SVD是也一个重要的方法。在机器学习领域,有相当多的应用与奇异值都可以扯上关系,比如做feature reduction的PCA,做数据压缩(以图像压缩为代表)的算法,还有做搜索引擎语义层次检索的LSI(Latent Semantic Indexing)。
本文主要关注奇异值的一些特性,还会稍稍提及奇异值的计算。另外,本文里面有部分不算太深的线性代数的知识,如果完全忘记了线性代数,看文可能会有些困难。

2.奇异值分解详解

特征值分解和奇异值分解两者有着很紧密的关系,特征值分解和奇异值分解的目的都是一样,就是提取出一个矩阵最重要的特征。先谈谈特征值分解吧:
1 特征值
如果说一个向量v是方阵A的特征向量,将一定可以表示成下面的形式:

这时候λ就被称为特征向量v对应的特征值,一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式:

其中Q是这个矩阵A的特征向量组成的矩阵,Σ是一个对角阵,每一个对角线上的元素就是一个特征值。首先,要明确的是,一个矩阵其实就是一个线性变换,因为一个矩阵乘以一个向量后得到的向量,其实就相当于将这个向量进行了线性变换。比如说下面的一个矩阵:

 它其实对应的线性变换是下面的形式:

 因为这个矩阵M乘以一个向量(x,y)的结果是:

上面的矩阵是对称的,所以这个变换是一个对x,y轴的方向一个拉伸变换(每一个对角线上的元素将会对一个维度进行拉伸变换,当值>1时拉长,当值<1时缩短),当矩阵不是对称的时候,假如说矩阵是下面的样子:

它所描述的变换是下面的样子:

这其实是在平面上对一个轴进行的拉伸变换(如蓝色的箭头所示),在图中,蓝色的箭头是一个最主要的变化方向(变化方向可能有不止一个),如果我们想要描述好一个变换,那我们就描述好这个变换主要的变化方向就好了。反过头来看看之前特征值分解的式子,分解得到的Σ矩阵是一个对角阵,里面的特征值是由大到小排列的,这些特征值所对应的特征向量就是描述这个矩阵变化方向(从主要的变化到次要的变化排列)
当矩阵是高维的情况下,那么这个矩阵就是高维空间下的一个线性变换,这个线性变化可能没法通过图片来表示,但是可以想象,这个变换也同样有很多的变换方向,我们通过特征值分解得到的前N个特征向量,那么就对应了这个矩阵最主要的N个变化方向。我们利用这前N个变化方向,就可以近似这个矩阵(变换)也就是之前说的:提取这个矩阵最重要的特征。总结一下,特征值分解可以得到特征值与特征向量,特征值表示的是这个特征到底有多重要,而特征向量表示这个特征是什么,可以将每一个特征向量理解为一个线性的子空间,我们可以利用这些线性的子空间干很多的事情。不过,特征值分解也有很多的局限,比如说变换的矩阵必须是方阵。
 2 奇异值:
下面重点谈谈奇异值分解。特征值分解是一个提取矩阵特征很不错的方法,但是它只是对方阵而言的,在现实的世界中,我们看到的大部分矩阵都不是方阵,比如说有N个学生,每个学生有M科成绩,这样形成的一个N * M的矩阵就不可能是方阵,我们怎样才能描述这样普通的矩阵呢的重要特征呢?奇异值分解可以用来干这个事情,奇异值分解是一个能适用于任意的矩阵的一种分解的方法:
 假设A是一个N * M的矩阵,那么得到的U是一个N * N的方阵(里面的向量是正交的,U里面的向量称为左奇异向量),Σ是一个N * M的矩阵(除了对角线的元素都是0,对角线上的元素称为奇异值),V’(V的转置)是一个N * N的矩阵,里面的向量也是正交的,V里面的向量称为右奇异向量),如下图所示:

那么奇异值和特征值是怎么对应起来的呢?首先,我们将一个矩阵A的转置 * A,将会得到一个方阵,我们用这个方阵求特征值可以得到:
这里得到的v,就是我们上面的右奇异向量。此外我们还可以得到:

这里的σ就是上面说的奇异值,u就是上面说的左奇异向量。奇异值σ跟特征值类似,在矩阵Σ中也是从大到小排列,而且σ的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说,我们也可以用前r大的奇异值来近似描述矩阵,这里定义一下部分奇异值分解:

 r是一个远小于m、n的数,这样矩阵的乘法看起来像是下面的样子:


 右边的三个矩阵相乘的结果将会是一个接近于A的矩阵,在这儿,r越接近于n,则相乘的结果越接近于A。而这三个矩阵的面积之和(在存储观点来说,矩阵面积越小,存储量就越小)要远远小于原始的矩阵A,我们如果想要压缩空间来表示原矩阵A,我们存下这里的三个矩阵:U、Σ、V就好了。

3.如何计算奇异值

 奇异值的计算是一个难题,是一个O(N^3)的算法。在单机的情况下当然是没问题的,matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值,但是当矩阵的规模增长的时候,计算的复杂度呈3次方增长,就需要并行计算参与了。
其实SVD还是可以用并行的方式去实现的,在解大规模的矩阵的时候,一般使用迭代的方法,当矩阵的规模很大(比如说上亿)的时候,迭代的次数也可能会上亿次,如果使用Map-Reduce框架去解,则每次Map-Reduce完成的时候,都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型,也就是节点之间是保持通信,数据是常驻在内存中的,这种计算模型比Map-Reduce在解决迭代次数非常多的时候,要快了很多倍。
Lanczos迭代就是一种解对称方阵部分特征值的方法(之前谈到了,解A’* A得到的对称方阵的特征值就是解A的右奇异向量),是将一个对称的方程化为一个三对角矩阵再进行求解。
由于奇异值的计算是一个很枯燥,纯数学的过程,而且前人的研究成果(论文中)几乎已经把整个程序的流程图给出来了。更多的关于奇异值计算的部分,将在后面的参考文献中给出,这里不再深入,我还是focus在奇异值的应用中去。

4.奇异值分解应用

奇异值与主成分分析(PCA)
这里主要谈谈如何用SVD去解PCA的问题。PCA的问题其实是一个基的变换,使得变换后的数据有着最大的方差。方差的大小描述的是一个变量的信息量,我们在讲一个东西的稳定性的时候,往往说要减小方差,如果一个模型的方差很大,那就说明模型不稳定了。但是对于我们用于机器学习的数据(主要是训练数据),方差大才有意义,不然输入的数据都是同一个点,那方差就为0了,这样输入的多个数据就等同于一个数据了。以下面这张图为例子:


这个假设是一个摄像机采集一个物体运动得到的图片,上面的点表示物体运动的位置,假如我们想要用一条直线去拟合这些点,那我们会选择什么方向的线呢?当然是图上标有signal的那条线。如果我们把这些点单纯的投影到x轴或者y轴上,最后在x轴与y轴上得到的方差是相似的(因为这些点的趋势是在45度左右的方向,所以投影到x轴或者y轴上都是类似的),如果我们使用原来的xy坐标系去看这些点,容易看不出来这些点真正的方向是什么。但是如果我们进行坐标系的变化,横轴变成了signal的方向,纵轴变成了noise的方向,则就很容易发现什么方向的方差大,什么方向的方差小了。
 一般来说,方差大的方向是信号的方向,方差小的方向是噪声的方向,我们在数据挖掘中或者数字信号处理中,往往要提高信号与噪声的比例,也就是信噪比。对上图来说,如果我们只保留signal方向的数据,也可以对原数据进行不错的近似了。
PCA的全部工作简单点说,就是对原始的空间中顺序地找一组相互正交的坐标轴,第一个轴是使得方差最大的,第二个轴是在与第一个轴正交的平面中使得方差最大的,第三个轴是在与第1、2个轴正交的平面中方差最大的,这样假设在N维空间中,我们可以找到N个这样的坐标轴,我们取前r个去近似这个空间,这样就从一个N维的空间压缩到r维的空间了,但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。
 还是假设我们矩阵每一行表示一个样本,每一列表示一个feature,用矩阵的语言来表示,将一个m * n的矩阵A的进行坐标轴的变化,P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间,在空间中就会进行一些类似于旋转、拉伸的变化。

而将一个m * n的矩阵A变换成一个m * r的矩阵,这样就会使得本来有n个feature的,变成了有r个feature了(r < n),这r个其实就是对n个feature的一种提炼,我们就把这个称为feature的压缩。用数学语言表示就是:

但是这个怎么和SVD扯上关系呢?之前谈到,SVD得出的奇异向量也是从奇异值由大到小排列的,按PCA的观点来看,就是方差最大的坐标轴就是第一个奇异向量,方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的SVD式子:

在矩阵的两边同时乘上一个矩阵V,由于V是一个正交的矩阵,所以V转置乘以V得到单位阵I,所以可以化成后面的式子:


将后面的式子与A * P那个m * n的矩阵变换为m * r的矩阵的式子对照看看,在这里,其实V就是P,也就是一个变化的向量。这里是将一个m * n 的矩阵压缩到一个m * r的矩阵,也就是对列进行压缩,如果我们想对行进行压缩(在PCA的观点下,对行进行压缩可以理解为,将一些相似的sample合并在一起,或者将一些没有太大价值的sample去掉)怎么办呢?同样我们写出一个通用的行压缩例子:



这样就从一个m行的矩阵压缩到一个r行的矩阵了,对SVD来说也是一样的,我们对SVD分解的式子两边乘以U的转置U':

 这样我们就得到了对行进行压缩的式子。可以看出,其实PCA几乎可以说是对SVD的一个包装,如果我们实现了SVD,那也就实现了PCA了,而且更好的地方是,有了SVD,我们就可以得到两个方向的PCA,如果我们对A’A进行特征值的分解,只能得到一个方向的PCA。

5.感谢

1.感谢杜克大学 方贺好友

2.感谢博客园 王大田博主

3.感谢清华大学数学系 刘永中教授



2012-10-31 09:49:07 abcjennifer 阅读数 49917
  • 极线几何

    掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法,了解RANSAC的基本思想

    1825人学习 CSDN就业班
    免费试看

潜在语义索引(Latent Semantic Indexing)是一个严重依赖于SVD的算法,本文转载自之前吴军老师《数学之美》和参考文献《机器学习中的数学》汇总。

————————————

在自然语言处理中,最常见的两类的分类问题分别是,将文本按主题归类(比如将所有介绍亚运会的新闻归到体育类)和将词汇表中的字词按意思归类(比如将各种体育运动的名称个归成一类)。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的,让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。


分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词,或者说实词的向量,然后求这两个向量的夹角。当这两个向量夹角为零时,新闻就相关;当它们垂直或者说正交时,新闻则无关。当然,夹角的余弦等同于向量的内积。从理论上讲,这种算法非常好。但是计算时间特别长。通常,我们要处理的文章的数量都很大,至少在百万篇以上,二次回标有非常长,比如说有五十万个词(包括人名地名产品名称等等)。如果想通过对一百万篇文章两篇两篇地成对比较,来找出所有共同主题的文章,就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章,完成这一百万篇文章相关性比较就需要十五年时间。注意,要真正完成文章的分类还要反复重复上述计算。


在文本分类中,另一种办法是利用
矩阵运算中的奇异值分解(Singular Value Decomposition,简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先,我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中,每一行对应一篇文章,每一列对应一个词。


在上面的图中,M=1,000,000,N=500,000。第 i 行,第 j 列的元素,是字典中第 j 个词在第 i 篇文章中出现的加权词频(比如,TF/IDF)。读者可能已经注意到了,这个矩阵非常大,有一百万乘以五十万,即五千亿个元素。


奇异值分解就是把上面这样一个大矩阵,分解成三个小矩阵相乘,如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X,一个一百乘以一百的矩阵B,和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿,仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。


三个矩阵有非常清楚的物理含义第一个矩阵X中的每一列表示一类主题,其中的每个非零元素表示一个主题与一篇文章的相关性,数值越大越相关。最后一个矩阵Y中的每一列表示100个关键词,每个key word与500,000个词的相关性。中间的矩阵则表示文章主题keyword之间的相关性。因此,我们只要对关联矩阵A进行一次奇异值分解,w 我们就可以同时完成了近义词分类和文章的分类。(同时得到每类文章和每类词的相关性)。

比如降至2维(rank=2),则document-term的关系可以在下面二维图中展现:


 

在图上,每一个红色的点,都表示一个词,每一个蓝色的点,都表示一篇文档,这样我们可以对这些词和文档进行聚类,比如说stock 和 market可以放在一类,因为他们老是出现在一起,real和estate可以放在一类,dads,guide这种词就看起来有点孤立了,我们就不对他们进行合并了。按这样聚类出现的效果,可以提取文档集合中的近义词,这样当用户检索文档的时候,是用语义级别(近义词集合)去检索了,而不是之前的词的级别。这样一减少我们的检索、存储量,因为这样压缩的文档集合和PCA是异曲同工的,二可以提高我们的用户体验,用户输入一个词,我们可以在这个词的近义词的集合中去找,这是传统的索引无法做到的。


现在剩下的唯一问题,就是如何用计算机进行奇异值分解。这时,线性代数中的许多概念,比如矩阵的特征值等等,以及数值分析的各种算法就统统用上了。在很长时间内,奇异值分解都无法并行处理。(虽然 Google 早就有了MapReduce 等并行计算的工具,但是由于奇异值分解很难拆成不相关子运算,即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。)最近,Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法,我认为这是 Google 中国对世界的一个贡献。


最后说说个人拙见,这里我们可以把document和term(word)中间加上一层latent semantics项,那么上图中的X和Y矩阵就可以分别表示同一个latent semantics对不同document之间的相关性和同一latent semantics在不同terms之间的相关性联系。X和Y的大小分别是m*r与r*n,r为A矩阵的rank(秩),最后,B是A的r个奇异值组成的对角方阵(r*r),在谱分解中也就是A的r个特征值。



关于NLP,linear algerbra和ML的更多讨论与交流,敬请关注本博客和新浪微博Rachel Zhang




2017-07-06 15:18:50 qingcaichongchong 阅读数 3353
  • 极线几何

    掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法,了解RANSAC的基本思想

    1825人学习 CSDN就业班
    免费试看

拜读吴军老师的《数学之美》,其中第15章提到通过SVD分解可以从一堆文章中的文字集合中抽取出主题,从而将文章归类,比如从一大堆文章中抽取出体育、文学、娱乐等板块,心想真不可思议,而且SVD分解公式,A = UVW。我们知道V是一个对角矩阵,对角线上元素按主题的重要程度排序(出现次数越多越重要),简直逆天了,左思右想搞不明白

另外,经常看到一个例子,是拿SVD做图像降噪,如下图有一副图像:


经过SVD分解后,并提取V中前三个元素后,左边的噪声图像就变成右边的那个样子,可以看到噪声像素大大减少了,天哪,SVD简直无所不能,究竟什么场景能应用SVD呢,这又是什么原理呢。

后来综合考虑PCA的数学原理,渐渐对SVD的意义有所领悟了,实际上一个m*n矩阵可以理解为m个n维向量,而这n维向量中的某些向量在某种程度上存在一些相似特征,可以归为一个聚类,而聚类之间的差别比较大(这就是主题的意义),而这些聚类之间的关系是用协方差矩阵表示的:

比如有2个m维向量a,b,其协方差:


ps:实际上应该是其减去均值后的乘积,上面是我盗的图,能说明问题,我就懒得再编辑公式了

协方差表示向量的相关性,协方差越接近0,则其相关性越低。以二维空间为例,a,b的协方差实际上是a到b的投影,这个投影越接近0,则a跟b的夹角越接近90度,即接近垂直。

将a,b写成矩阵形式为:


然后我们用X乘以X的转置,并乘上系数1/m:


可以看到副对角线上的两个元素就是a,b的协方差,而这个协方差矩阵是对称矩阵,也即存在特征值分解:


我们知道P是D的特征向量集合,C是对角矩阵,对角元素是D的特征值。特征向量不相关,即其协方差为0,其就可以理解为一个主题,其重要程度当然可以用特征值提现,这是PCA的理论依据。

实际上SVD与PCA是一样的,其中间的对角矩阵的意义相同,SVD中间V元素实际上就是D的特征值开方,可以简单证明一下:

XTA = (UVW)T(UVW) = WTVTVW,即C = VTV,得证。


同理,对图像降噪而言,其向量最重要的三个主题即是:

这样,如果只保留其最重要的三个主题,就达到降噪的目的了