什么是流形

关于统计流形学习处理高维数据1.什么是流形？根据维基百科上的解释：Inmathematics,(speciallyindifferentialgeometryandtopology),amanifoldisatopologicalspacethatinasmallenoughscaleresemblestheEuclideanspaceofaspecificdimension,calledthedimensionofthemanifold.因此，一个直线或者一个曲线是一个一维流形，一个平面或者球面是二维流形，依次类推到高维空间。有时候经常会在paper里看到“嵌入在高维空间中的低维流形”，不过高维的数据对于我们这些低维生物来说总是很难以想象，所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布，可以把它看成一个二维平面，这是一个二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。所以，直观上来讲，一个流形好比是一个d维的空间，在一个m维的空间中(md)被扭曲之后的结果。流形并不是一个“形状”，而是一个“空间”。当然，这些都是直观上的概念，其实流形并不需要依靠嵌入在一个“外围空间”而存在，稍微正式一点来说，一个d维的流形就是一个在任意点出局部同胚于（简单地说，就是正逆映射都是光滑的一一映射）欧氏空间除了简单的例子，在实际的应用中的数据，我们怎么知道它是不是一个流形呢？于是不妨又回归直观的感觉。再从球面说起，如果我们事先不知道球面的存在，那么球面上的点，其实就是三维欧式空间上的点，可以用一个三元组来表示其坐标。可以看一下它的参数方程：000sincossinsincosxxryyrzzr（02，0）可以看到，这些三维的坐标实际上是由两个变量和生成的，因此自由度是二，对应了一个二维的流行。下面再来看看流形学习里经常用到的人脸的例子，下图是Isomap论文里的一个结果：每张人脸图是一个64x64的灰度图，可以将其看成一个4096维的向量，这样一来，每一张图片就可以看成是4096维欧式空间中的一个点，当然并不是该4096维空间中每个点都可以对应一张人脸图（就像球面上要受到限制一样）。我们可以假定所有可以对应到人脸的向量实际上分布在一个d维（d4096）的子空间中。如图所示，如果把pose(上下和左右)看作两个自由度，则这就是一个嵌入在4096维欧式空间中的一个2维流行。2.关于MDS和Isomap上一节人脸的例子就是一个非常典型的例子，Isomap实际上是通过改造一种原本适用于欧式空间的算法，达到了将流形映射到欧式空间的目的。Isomap所改造的方法叫做MultidimensionalScaling(MDS).MDS是一种降维方法，它的目的就是使得降维之后的点两两之间的距离尽量不变（也就是和在原始空间中对应的两个点之间的距离要差不多）。只是MDS是针对欧式空间设计的，对于距离的计算也是使用欧式距离来完成的。如果数据分布在一个流形上的话，欧式距离就不适用了。就像在地球上，要从南极到达北极，欧式距离就是两点之间，直线最短，但是总不能在地球之间打个洞穿过去吧，必须要用到测地距离，即曲线的长度。先说一下这个MDS降维方法，维基百科对MDS算法的定义：AnMDSalgorithmstartswithamatrixofitem-itemsimilarities,thenassignsalocationtoeachiteminN-dimensionalspacewhereNisspecifiedapriopri..可以这样认为：MDS算法的输入是矩阵D：111212122212nnnnnnddddddddd，whereijdisthedistancebetweeniandj然后对输入矩阵D进行处理：22211121212nnnnijijijmjijiijiajaaddddxxnnn，用矩阵来表示就是1112TTnnnnBIeeDIeenn，I为n维的单位矩阵111，e为长度为n元素均为1的向量1,11.令1TnnnHIeen,则变换可看作212HDH。我们可以知道矩阵B是半正定的对称矩阵，可以进行奇异值分解，将其进行奇异值分解后假设TBVV，令xV，则TBxx，可求出其特征向量，并取前d个向量作为降维后的维数。在对MDS算法的大概有了了解之后，再看维基百科上对Isomap的定义：Instatistics,Isomapisoneoftheseveralwidelyusedlow-dimensionalembeddingmethods,wheregeodesicdistancesonaweightedgraphareincorporatedwiththeclassicalscaling(metricmultidimensionalscaling).简单的说，MDS算法是在知道高维向量两两相似度的情况下对高维向量进行的降维，而这个相似度就用欧式距离来度量的（在欧式空间中常用到），因此MDS算法在流行上就不适用了，所以Isomap就将这个输入的欧式距离矩阵经过处理变成了测地距离矩阵。然后再在该矩阵上进行运算。关于这个测地距离，也困扰了我很久，再次引用维基百科上的描述：Isomapdefinesthegeodesicdistancetobethesumoftheedgeweightsalongtheshortestpathbetweentwonodes(e.gcomputedusingDijistra’salgorithm).我是这样理解的：假如有三个点A,B,C，A和B之间的距离为1l,B和C之间的距离2l，A和C之间的距离为3l，则从A到达C的就可以通过先经历1l再经过2l，可能比3l短。因此A和C的距离可记为1l+2l，而抛弃掉3l。因此在距离矩阵中，通过各种计算绕啊绕，找到从i到j的最短距离来取代以前的直接欧式距离，最后就得到了测地距离矩阵，这个距离可能不是传统意义上直接的pointtopoint.Dijistra算法接触计算机的人都不陌生，想想这个算法在网络中寻找路由时候的用法，将其类推到这里（不知道理解的对不对）。因此Isomap主要做了一件事，就是把MDS原始空间中距离的计算从欧式距离换为了流形上的测地距离。在算法上就是对输入的矩阵D用某种算法（如dijistra算法）进行计算，得到新的距离矩阵'D，然后再用MDS算法对这个矩阵处理来达到降维的目的。3.Isomap在PDF降维上的应用上面我们说的Isomap算法输入的NxN矩阵是任意两点之间的欧式距离，因此Isomap是将一堆数据中每个数据点都降到了d维。就像上面提到的人脸图的例子，每个图都是一个4096维的向量，降维之后每个点都可以用二维坐标来代表。但是，如果像我们的应用中，一个图像提取了N个关键点，每个关键点是一个128维的向量，这里一个图像应该只能算是有N个向量的数据集了，这时为了计算数据集之间的距离，就得求的数据集的PDF,然后再计算PDF之间的距离，这时降维的结果就是把每个PDF降到了d维，这时一副图像可能就只需要用一个维数很低的PDF来表示了。（不知道我的想法对不对呢？）就像那个FINE算法可视化白血病的例子上说的，每个病人有5000个样本，每个样本有5个特征，就好像我们每幅图像有N（假设500好了）个关键点，每个关键点有128个特征，看上去是一样的。这个过程应该可以看作：一堆图像-一堆（假设n维的）PDF一个表示PDF之间信息距离的矩阵降维后成了一堆只有d维的PDF—一个d维PDF代表一个图像。一堆图像一堆PDF（n维）聚类学习信息距离矩阵计算各PDF之间的fisher信息距离新的PDF（d维）Isomap降维一个PDF对应一个图像，一个图像由d维的PDF表示了如果原始数据已经被表示成了PDF，那么Isomap中输入的距离矩阵就必须是PDF之间的距离矩阵了，这个距离可以由传说中的fisher信息距离来计算，同样输入后，再算出以fisher信息距离为基础的测地矩阵，再通过MDS降维（MDS只要知道两两之间的关系就可以降维，当然也可以降PDF关系之间的维了）。4.fisher信息距离和我遇到的问题fisher信息距离给了一个计算公式，就是有参数的那个(,)px的公式，顺便可以再提一下，这里就是决定流形维数的参数，就像那个人脸图例子中的pos(上下，左右)一样，但是给一堆乱七八糟的数据，谁会知道它们之间有啥联系受什么参数的影响的，所以这个公式基本上是计算不出来的。然后还有三个近似公式11212()(||)()log()xpxKLpppxdpx21212(,)(()())HxDpppxpxd1212(,)2arccos().()CxDpppxpxd杯具的是我连这三个公式也不会算，因为根据我们的预想，每幅图像求出的PDF应该是概率在码书上的分布，即x是一个个离散的128维的向量，怎么求呢？假设两个PDF分别为12(,)Nppp和'''12(,)Nppp，N为PDF的维数11212()(||)()log()xpxKLpppxdpx能推出='1.logniiiippp吗？？同理21212(,)(()())HxDpppxpxd'21()Niiipp?1212(,)2arccos().()CxDpppxpxd'12arccos.Niiipp?我到现在也没有想明白，不知道那个Carter.K.M是怎么算的。除了这个理论上的问题以外，在具体的程序实现上也遇到了困难，现在MDS和Isomap算法都有开源代码，但是都是老外用matlab实现的，在阅读时很费劲，常常看不懂，考虑我要不要学习下matlab编程。