Categories

Calendar

July 2019
M T W T F S S
« Jun    
1234567
891011121314
15161718192021
22232425262728
293031  

浅谈流形学习

总觉得即使是“浅谈”两个字,还是让这个标题有些过大了,更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了,想起来要扯一下这个话题,也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉,不过如果并不是想要进行严格的理论推导的话,也可以从许多直观的例子得到一些感性的认识,正好我也就借这个机会来简单地谈一下这个话题吧,或者说至少是我到目前为止对这它的认识。

这两个词,在谈 Manifold 之前,不妨先说说 Learning ,也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科,因为每当它的一个子领域发展得像模像样之后,就立马自立门户,从此和 AI “再无瓜葛”了,而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪,比如说数学,分门别类总算是够多了吧?可以不管怎么分,大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢?我觉得这里有很大一部分是它自身定位的问题。

反正现在我是不太清楚 AI 是做什么的,不知道其他人到底清楚不清楚。Wikipedia 上说

Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it.

可是这相当于一个 tautology ,因为到底什么又是 the intelligence of machines 呢?一开始的时候,大牛们都野心勃勃,而且好像也是信心满满,就好像曾经广泛认为“牛顿定理揭示了宇宙真理,科学剩下的事情只要按照公式来做计算就可以了”一样,大家可能觉得,不出几十年,人类就可以不用思考,交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”,什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是,到头来,AI 到底是什么,这还是一个问题,或者说,AI 在一开始定了一个过高的目标,几十年后,发现情况并不像当年那么乐观,却又有些下不了台了。

这个时候,AI 的一些旁枝或者子领域果断放下面子,丢掉了那个近乎玄幻的目标,逐渐发展成为“正常”的学科,所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思,一个广义的 AI ,包括了所有相关的以及派生的领域,另一个则是狭义的或者经典的 AI ,专门指那些仍然在执着地追求着真正的“智能”的部分,或者说得不好听一点,就是剩下的部分。

Machine Learning 作为离家出走的典型,虽然名字里带了 Learning 一个词,让人乍一看觉得和 Intelligence 相比不过是换了个说法而已,然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了,其实有时候觉得和应用数学或者更通俗的数学建模有些类似,通常我们会有需要分析或者处理的数据,根据一些经验和一些假设,我们可以构建一个模型,这个模型会有一些参数(即使是非参数化方法,也是可以类似地看待的),根据数据来求解模型参数的过程,就叫做 Parameter Estimation ,或者 Model Fitting ,但是搞机器学习的人,通常把它叫做 Learning (或者,换一个角度,叫 Training)——因为根据数据归纳出一个有用的模型,这和我们人类“学习”的过程还是挺类似的吧。不过,如果抛开无聊的抠字眼游戏的话,我们可以看到,Machine Learning 已经抛弃了“智能”的高帽子,它的目的就是要解决具体的问题——而并不关心是否是通过一种“智能”的方式类解决的。

说到这里,其实我们构造模型就类似于写一个类,数据就是构造函数的参数,Learning 就是构造函数运行的过程,成功构造一个对象之后,我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了,另一些情况还会使用得到的模型(对象)对后来的数据进行一些处理,通常会是 Inferencing 。到这个时候,又有些像统计里的东西了,所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的,不过两派人从不同的角度来看待同样的问题。而且,也确实有 Statistical Learning 这么一个说法存在的,可以把他看成是 Machine Learning 的一个子领域(或者是一个分子或者甚至就是 Machine Learning 本身)。

到这里,如果你还没有因为不断地抠字眼而烦躁的话,我已经忍无可忍了。所以,我就假定你已经了解了什么叫 Learning ,或者是已经恶心到懒得去了解了。于是我们转入下一个话题:流形,也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑?这是因为球面是一个很典型的流形的例子,而地球就是一个很典型的“球面”啦(姑且当作球面好啦)。

有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”,不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像,所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布,可以把它看成一个二维平面,这是一个二维的欧氏空间,现在我们(在三维)中把它扭一扭,它就变成了一个流形(当然,不扭的时候,它也是一个流形,欧氏空间是流形的一种特殊情况)。

所以,直观上来讲,一个流形好比是一个 d 维的空间,在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是,流形并不是一个“形状”,而是一个“空间”,如果你觉得“扭曲的空间”难以想象,那么请再回忆之前一块布的例子。如果我没弄错的话,广义相对论似乎就是把我们的时空当作一个四维流(空间三维加上时间一维)形来研究的,引力就是这个流形扭曲的结果。当然,这些都是直观上的概念,其实流形并不需要依靠嵌入在一个“外围空间”而存在,稍微正式一点来说,一个 d 维的流形就是一个在任意点出局部同胚于(简单地说,就是正逆映射都是光滑的一一映射)欧氏空间 \textcal{R}^d实际上,正是这种局部与欧氏空间的同胚给我们带来了很多好处,这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决,因为和地球的尺度比起来,我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球,走几步就要绕一圈的感觉,看来界王不仅要体力好(那上面重力似乎是地球的十倍),而且脑力也要好,初中学的必须是黎曼几何了!

那么,除了地球这种简单的例子,实际应用中的数据,怎么知道它是不是一个流形呢?于是不妨又回归直观的感觉。再从球面说起,如果我们事先不知道球面的存在,那么球面上的点,其实就是三维欧氏空间上的点,可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是,它们允许出现的位置受到了一定的限制,具体到球面,可以可以看一下它的参数方程:

\displaystyle\begin{aligned}
x &= x_0 + r \sin \theta \; \cos \varphi \\
y &= y_0 + r \sin \theta \; \sin \varphi \qquad (0 \leq \varphi \leq 2\pi \mbox{ and } 0 \leq \theta \leq \pi )\\
z &= z_0 + r \cos \theta
\end{aligned}

可以看到,这些三维的坐标实际上是由两个变量 \theta\varphi 生成的,也可以说成是它的自由度是二,也正好对应了它是一个二维的流形。有了这样的感觉之后,再来看流形学习里经常用到的人脸的例子,就很自然了。下图是 Isomap 论文里的一个结果:

这里的图片来自同一张人脸(好吧,其实是人脸模型),每张图片是 64×64 的灰度图,如果把位图按照列(或行)拼起来,就可以得到一个 4096 维的向量,这样一来,每一张图片就可以看成是 4096 维欧氏空间中的一个点。很显然,并不是 4096 维空间中任意一个点都可以对应于一张人脸图片的,这就类似于球面的情形,我们可以假定所有可以是人脸的 4096 维向量实际上分布在一个 d 维 (d < 4096) 的子空间中。而特定到 Isomap 的人脸这个例子,实际上我们知道所有的 698 张图片是拍自同一个人脸(模型),不过是在不同的 pose 和光照下拍摄的,如果把 pose (上下和左右)当作两个自由度,而光照当作一个自由度,那么这些图片实际只有三个自由度,换句话说,存在一个类似于球面一样的参数方程(当然,解析式是没法写出来的),给定一组参数(也就是上下、左右的 pose 和光照这三个值),就可以生成出对应的 4096 维的坐标来。换句话说,这是一个嵌入在 4096 维欧氏空间中的一个 3 维流形。 实际上,上面的那张图就是 Isomap 将这个数据集从 4096 维映射到 3 维空间中,并显示了其中 2 维的结果,图中的小点就是每个人脸在这个二维空间中对应的坐标位置,其中一些标红圈的点被选出来,并在旁边画上了该点对应的原始图片,可以很直观地看出这两个维度正好对应了 pose 的两个自由度平滑变化的结果。 就我目前所知,把流形引入到机器学习领域来主要有两种用途:一是将原来在欧氏空间中适用的算法加以改造,使得它工作在流形上,直接或间接地对流形的结构和性质加以利用;二是直接分析流形的结构,并试图将其映射到一个欧氏空间中,再在得到的结果上运用以前适用于欧氏空间的算法来进行学习。 这里 Isomap 正巧是一个非常典型的例子,因为它实际上是通过“改造一种原本适用于欧氏空间的算法”,达到了“将流形映射到一个欧氏空间”的目的。 :) Isomap 所改造的这个方法叫做 Multidimensional Scaling (MDS) ,MDS 是一种降维方法,它的目的就是使得降维之后的点两两之间的距离尽量不变(也就是和在原是空间中对应的两个点之间的距离要差不多)。只是 MDS 是针对欧氏空间设计的,对于距离的计算也是使用欧氏距离来完成的。如果数据分布在一个流形上的话,欧氏距离就不适用了。

让我们再回到地球——这个在三维空间中的二维流形,假设我们要在三维空间中计算北极点和南极点的距离,这很容易,就是两点相连的线段的长度,可是,如果要在这个流形上算距离就不能这样子算了,我们总不能从北极打个洞钻到南极去吧?要沿着地球表面走才行,当然,如果我随便沿着什么路线走一遍,然后数出总共走了多少步作为距离,这是不成的,因为这样一来如果我沿着不同的路线走,岂不是会得到不同的距离值?总而言之,我们现在需要一个新的定义在地球表面(流形)上的距离度量,理论上来说,任意满足测度的 4 个条件的函数都可以被定义为距离,不过,为了和欧氏空间对应起来,这里选择一个直线距离的推广定义。

还记得初中学的“两点之间,线段最短”吗?现在,我们反过来说,把线段的概念推广一下,变成“两点之间最短的曲线是线段”,于是流形上的距离定义也就等同于欧氏空间了:流形上两个点之间的距离就是连接两个点的“线段”的长度。虽然只是置换了一个概念,但是现在两者统一起来了,不过,在流形上的线段大概就不一定是“直”的了(于是直线也变成不一定是“直”的了),通常又称作是“测地线”。对于球面这个简单的流形来说,任意一条线段必定是在一个“大圆”上的,于是球面上的直线其实都是一些大圆,也造成了球面这个流形上没有平行线等一系列尴尬的局面(任意两条直线均相交),如果你看过一些数学科普八卦类的书,应该会回忆起不少东西啦!

回到 Isomap ,它主要做了一件事情,就是把 MDS 中原始空间中距离的计算从欧氏距离换为了流形上的测地距离。当然,如果流形的结构事先不知道的话,这个距离是没法算的,于是 Isomap 通过将数据点连接起来构成一个邻接 Graph 来离散地近似原来的流形,而测地距离也相应地通过 Graph 上的最短路径来近似了。如下图所示:

这个东西叫做 Swiss Roll ,姑且把它看作一块卷起来的布好了。图中两个标黑圈的点,如果通过外围欧氏空间中的欧氏距离来计算的话,会是挨得很近的点,可是在流形上它们实际上是距离很远的点:红色的线是 Isomap 求出来的流形上的距离。可以想像,如果是原始的 MDS 的话,降维之后肯定会是很暴力地直接把它投影到二维空间中,完全无视流形结构,而 Isomap 则可以成功地将流形“展开”之后再做投影。

除了 Isomap 之外,Manifold Embedding 的算法还有很多很多,包括 Locally Linear Embedding 、Laplacian Eigenmaps 、Hessian Eigenmaps 、Local Tangent Space Alignment、Semidefinite Embedding (Maximum Variance Unfolding) 等等等等。哪个好哪个坏也不好说,它们都各有特点,而且也各自有不少变种。网上有一个 Matlab 的 demo ,给出了几种流行的 manifold embedding 算法在一些 synthetic manifold 上的结果和对比,可以有一个直观的认识。

另一方面是改造现有算法使其适合流形结构甚至专门针对流形的特点来设计新的算法,比较典型的是 graph regularized semi-supervised learning 。简单地说,在 supervised learning 中,我们只能利用有 label 的数据,而(通常都会有很多的)没有 label 的数据则白白浪费掉。在流形假设下,虽然这些数据没有 label ,但是仍然是可以有助于 Learn 出流形的结构的,而学出了流形结构之后实际上我们就是对原来的问题又多了一些认识,于是理所当然地期望能得到更好的结果喽。

当然,所有的这些都是基于同一个假设,那就是数据是分布在一个流形上的(部分算法可能会有稍微宽松一些的假设),然而 real world 的数据,究竟哪些是分别在流形上的呢?这个却是很难说。不过,除了典型的 face 和 hand written digit 之外,大家也有把基于流形的算法直接用在诸如 text 看起来好像也流形没有什么关系的数据上,效果似乎也还不错。

话说回来,虽然和实际应用结合起来是非常重要的一个问题,但是也并不是决定性的,特别是对于搞理论方面的人来说。我想,对于他们来说,其实也像是在做应用啦,不过是把数学里的东西应用到机器学习所研究的问题里来,而且其中关系错综复杂,图论、代数、拓扑、几何……仿佛是十八路诸侯齐聚一堂,所以让我总觉得要再花 500 年来恶补数学才行呀!

不过我表示可以理解其中存在的潜在的 happy 之处,就好比你玩游戏,先玩了《天地劫:神魔至尊传》,然后再玩《天地劫序章:幽城幻剑录》的时候,会发现里面的人物、剧情逐渐地联系起来,也许甚至只是在一个地方出现过的一个完全不起眼的配角,当你再在另一地方突然看到他是,一系列的线索瞬间被联系起来,全局的画面渐渐浮现,那种 happy 的感觉,大概就是所谓的“拨云见日”了吧! :D

所以呀,这些东西其实都是差不多的,有时候想想那些泰斗站在顶峰上“一览众山小”的感觉,那种“融会贯通”的感觉,真是让人各种羡慕呀!无奈就只好去爬爬老和山北高峰来体验体验了。 :p

最后是总结:所谓 Machine Learning 里的 Learning ,就是在建立一个模型之后,通过给定数据来求解模型参数。而 Manifold Learning 就是在模型里包含了对数据的流形假设。嗯,还有什么?还有就是,我画的坐在楼兰古城城墙上的冰璃,一点都不像…… >_< 幽城迷不要砍我…… Update 2011.02.28: 根据留言里的信息,“流形”这个中文词取自文天祥的“天地有正气,杂然赋流形”,这个词第一次作为当前的数学意义使用是由北大数学系的一位老教授江泽涵老先生。老先生是我国代数拓扑学的开拓者。还是 caszgh 同学的导师的大学时代的老师。 ^_^

119 comments to 浅谈流形学习

  • 相当棒的文章。流行学习浙大好像有个数学系的教授挺牛

  • maxint

    写得风趣,画得也蛮好的啊(没玩过游戏)

  • 赞。我想全文转载。可以么?

  • xiaohanyu

    深入浅出,但是还看不太懂。

  • Pepper

    哈哈,数学确实有其独特的魅力

  • eVulcanon

    夸张夸张,洋洋洒洒写了那么多,哈哈。流形这个中文名字不晓得是谁取的,还是英文好理解:Many folds。

  • liwang

    写的真是好!不知师兄现在做的怎么样?可以交流下么?我的Email:wl820609@163.com

  • 写的真好!我记得我在上数据挖掘的时候周志华老师给我们提过Manifold Learning,也用了那张isomap的图,当时就没感觉,现在倒有感觉了!

  • Chrysalis

    唉.. 又膜拜到了~

  • loveisp

    流形思想是不错,不过局限性也不小。一是由于其非线性而无法得到一组简洁的基表示,因此实用性大打折扣,我至今不明白流形学习出来的东西除了能看看这流形代表什么然后表示赞许与欣慰之外还能干吗;二是局部性依赖于所选特征,拿isomap来说,如果所选的特征是关于pose的,那出来的流形就是pose上的,如果所选的是illumination,流形就是illumination,太主观了,lle之类亦是如此。文中isomap对pose的结果图看起来不错,那无非是图像本身比较简单,而且直接比较就蕴涵着pose上的变化,换个复杂点的数据集结果远没有这么好;三是各种方法太多了,但看多了有点审美疲劳,看着都挺有道理,什么测地线、局部线性、局部邻接、局部切线,局部这局部那,是能学到不少trick,但是总感觉不是正途,有点像前几年fld那堆各种子空间的水文。总的来说,流形学习似乎还需要长时间的发展和完善才能有所突破,不知道博主和其他朋友怎么看?

    • 你说得挺有道理的,流形的这些方法,要说实用性,我也不知道目前是否真的有大规模或者工业应用,也许 laplacian face 之类的用于人脸识别是有点吧,但是其他更加 fancy 的方法就不一定了。然而也并不能说这个东西就没有价值,他们是在这个特定的背景下解决这样的问题,至于我们目前还没有碰到这样的问题或者还没有大规模工业化来解决这类问题或者是目前的算法还不够好,这些都只能说是一个有待发展和完善的地方吧。

      灌水这个东西,到处都有吧,也不单单是流形学习了。而且方法各种各样琳琅满目也并不一定都是没有意义,每次前进一小步,即使证明这条路行不通,也是一个进步,毕竟不可能每篇文章都是划时代的啊。 :)

  • douya

    ymymymymymymymymymymym!

  • […] by pluskid, on 2010-05-29, in Machine Learning 17 comments […]

  • ywdsar

    今天看一篇文章,用流形理论进行目标分类。想了解一下流形是什么东东,用Google一搜,就搜到了你的这篇介绍。讲得很清楚,谢谢了!
    有个问题还想请教一下:用流形概念来降低待分析数据的维数,必须对数据的生成过程及特点有先验了解吗?还是可以自动地从数据中提炼出所需的低维特征?

    • 嗯,通常都需要知道一些东西,比如流形的维度之类的,虽然也有专门用于估计流形的维度的算法,不过,总的来说,感觉流形的东西还是在理论里研究的比较多,还没有真正能大范围应用到实际问题中。如果只是针对某一个数据集,通过 cross-validation 等方法多少也是都能估计出感兴趣的一些参数的。

  • caszgh

    流形这个词是取自
    文天祥的“天地有正气,杂然赋流形”
    这个词在汉语中赎于此种意义第一次使用是北大数学系的一个老教授,这个教授是我导师大学时代的老师,导师今年70多岁了,估计北大的那位老教授也已经作古了,在此深表敬佩与怀念!

  • Ian

    流形学习是非线性降维,如何解决训练集和之外数据的映射是一个open problem(注:我的理解LPP是子空间算法,属于线性降维的一种,对应于流形学习的LE)。通常的做法是根据算法准则,定义kernel矩阵进行映射,但是对于一些流形学习算法,kernel矩阵的定义并不是一件容易的事情。因此如何有效解决流形学习OOS问题是一个需要关注的。

  • Ian

    对,但是如何定义kernel矩阵并不是一件容易的事情,我那个paper的introduction里有讨论。One limitation of this family of
    algorithms is that the design of data dependent kernel matrices
    for various manifold learning algorithms is a nontrivial
    task. For example, compared with LE, it is not that straightforward to define the data dependent kernel matrix for LLE and it still remains unclear how to define
    the kernel matrices for other manifold learning algorithms, i.e., LTSA.

  • Ian

    比如Bengio的paper里,LE的kernel矩阵定义就比较好理解,LLE的就很牵强,而对于LTSA,目前好像没人能给出kernel矩阵。你可以看看这个论文http://www.dcd.zju.edu.cn/~yyang/AAAI2010manifold.pdf

    • 你说的“定义”是指要把它的 explicit formula 写出来吗?我觉得没有必要啊,只要满足 kernel 矩阵的性质(对称啊,正定啊什么的)就可以看成一个 valid 的 kernel 矩阵了,至于怎么得到这个 kernel 矩阵可以从不同的出发点,比如 MVU 那样子干脆直接用 learning 的办法去学这个 kernel 矩阵。但是话说回来,你说的这一点也确实是,如果不知道一个形式的话,要做 out of sample extension 就不容易了。

      现在好像连不上 DCD 的网站呢,你这篇文章叫什么名字?我去 google 上搜一下看其他地方有没有下载的。

  • Ian

    是这样的,manifold learning都可以理解成KPCA,不同的流形学习算法对应不同的kernel matrix。因为算法不同,kernel矩阵当然不同。如果kernel矩阵一样,那所有的流形学习算法输出不就一样了?Local and Global Regressive Mapping for Manifold Learning with Out-of-Sample Extrapolation

    • 也有像 Non-Isometric Manifold Learning 这样的专门就是学习一个流形的表示,然后就可以在流形外做 extrapolation 了,不过计算切空间,复杂度是比较高的呀。拜读了你那个 paper ,比较好玩哈哈,感觉有点像 LTSA+Kernel Regression 合并到一起同时优化。

  • caszgh

    是北京大学的江泽涵老教授。今天我问的导师,他是第一个提出这个词语的人。

  • caszgh

    这下面是我老师刚才给我的资料:大家看看吧,网上也能找到的

    黎曼开始了关于延展性,维数,以及将 延展性数量化的讨论。他给了这些多度延展的量(几何对象)一个名称,德文写作 mannigfaltigkeit, 英文翻译为 manifold,英文字面意思可以理解为 “多层”,中国第一个拓扑学家江泽涵把这个词翻译为 “流形”,取自文天祥《正气歌》,“天地有正气,杂然赋流形”,而其原始出处为《易经》,“大哉乾元,万物资始,乃统天。云行雨施,品物流形。” 这个翻 译比英文翻译更加符合黎曼的原意,即多样化的形体。。。。。

  • 曾鸣聪

    啊,谢谢kid,我一直都在疑惑我们这种这么几何这么数学的东西是怎么用到计算机里面的……不过这么抽象的东西,在计算机里如何表达呢?
    以及,沈一兵的那本《整体微分几何初步》建议还是不要看…我有看到你的豆瓣里写正在读呢……

    • 我见过的计算机里关于流形的表达,最常见的就是 graph ,在流形上 sampling 一些点,然后构造一个 neighborhood graph ,相当于流形的一个离散近似。而实际解决具体问题的时候,得到的输入都是一些离散的数据点,所以这种处理方法很多。理论方面有很多研究离散情况当点数趋向于无穷的时候收敛到连续情况的工作。比如在 Graph 上的 Laplacian 收敛到对应 Manifold 上的 Laplace-Beltrami Operator ,等等……

      还有一种表达就是用切空间来表达。这个可以描述为一个函数,就是给定一个点,映射为该点处的切空间。另外,在计算机相关的问题中流形都是被表示为一个高维欧氏空间的子流形的,所以一个切空间其实就是高维空间中一个低维的 affine subspace ,用矩阵就可以表示了。

      其他貌似在图形学之类的里面有那些低维流形的一些表示方法,这个我也不是很了解。

      ps: 那本书因为我一直在上那个课啊,也没有办法,虽然考虑过中途换个老师,但是这样前面和后面就接不上头了,比较麻烦。于是准备先凑合一下。顺便问一下泛函分析有没有什么推荐的书啊?

  • 曾鸣聪

    微分几何那门课不值得一上(仅指我们学校的微分几何),看完光滑流形,黎曼几何以后自己算几个例子(John Lee的黎曼几何里有几个不错的例子)那门课的内容就过去了……
    泛函分析我一下还真想不起来有什么“标准”的第一次阅读教材。Rudin有一本但是听过口味很重,适合重读的时候看,然后我们的老师有推荐一个日本人Yosida写的泛函分析,但是不知道如何(我们上泛函课的老师是日系的),最后E.M.Stein的普林斯顿大学分析系列丛书第四本泛函分析据说出版了,但是我目前还没有见到(即便电子版也没有),这套书的前三本《傅里叶分析》,《复分析》,《实分析》都是非常好的书,我觉得在看泛函之前对实分析应该有基本的了解(不过这套书可能你用不上,前两本的重头戏都是用分析的工具去研究数论,第三本的后面在用实分析去研究分形理论)。
    ———————–
    你说离散近似,大约是不是这样:一个流形如果是紧的,那么我们可以用有限个坐标卡去覆盖它,然后转移函数可以用它的泰勒展开去表达?(不过这样有很严重的问题,光滑函数的泰勒展开不一定收敛)把一个点映射成它的切空间是个很有趣的想法,粗略想一下这个信息应该是足以刻画整个嵌入流形的。
    求更多的科普和更多有趣的想法啊~~~求讲座啊~~~~

    • 你说的是这本?《Functional Analysis: An Introduction to Further Topics in Analysis》,确实似乎是刚出,电子版和影印版什么的都没有。实分析我看过一点,不过这个学期没有那个课呢。主要是我本科的时候没有听过数学系的课,养成的那一套思维模式都和数学系那种完全格格不入,所以我现在正在痛苦转化中,于是觉得平时去旁听一下各种课应该也多少有些好处的。其实除了研究中要用到的之外,对现代数学的这些精彩的架构也让我叹为观止啊,挺感兴趣的,不过这个坑实在太大了,要学的东西好多好多。不过倒是好像从来就对数论不太感兴趣。

      关于离散近似的问题,我觉得应该不是你说的那样,实际上,在机器学习中,“把流形表示出来”并不是问题的最终目的,“在流形上学习”才是最终目的。也就是说,有一些方法可以在不显式地表示流形的坐标卡、转移函数等等的情况下,来进行分析。举一个最 naive 的例子,比如求测地线长度,如果用一个 point-cloud graph 来“表示”一个流形的话,那么只要计算 graph 上的两点间最短路径,就可以得到一个测地线长度的近似了。

      事实上,如果把问题都看成欧氏空间中的子流形的问题,就会具体得多。比如流形上的函数,实际上我可以用外围欧氏空间中的坐标来给他赋予一个全局的“表达式”,这样在表示上就不用在局部用转移函数跳来跳去。然后由于机器学习中很多是在学习一个“函数”,流形学习中,这个函数是定义在流形上的,我们可以通过流形上的一些泛函或者 operator 来研究流形上函数的性质,而这些泛函或者 operator 本身就可以具有离散形式的近似,而不必要根据流形的定义中把整个光滑结构、黎曼度量之类的全部刻画出来之后再来得到相应的刻画。例如很常用的一个 Operator 是 Laplace-Beltramy Operator (黎曼几何课的时候也讲了,不过到那里的时候我已经听不懂了,看来这个课以后还得再重新去听的),离散可以用 Laplacian Matrix 来做。有一本《Spectral Graph Theory》可以参考。

      如果感兴趣,可以找一些相关的论文来看,比如有个博士论文 geometrical aspects of statistical learning theory ,搜一下就有下载。你浏览一下应该就知道为什么我要学黎曼几何和泛函分析了。

      ps: 还有一些 Lie Group 用在 Vision 里的,不过这个我不是很了解。另外,Grassmann Manifold 也是应用非常广泛。

  • 居然是pluskid的博客…好久没见:-)

  • N年前某中学论坛认识, 川木**

    • 啊!难道是 k12 那个论坛?!我对上面的 ID 都不太记得了。 :D 前一阵子还突然想起来去那里看一下,发现一个人都不认识了。那可真是好多好多年了!我学了 4 年的计算机,倒是收获不小,但是现在要反过来补很多数学,正在非常艰苦地补习呢,哈哈!你现在是什么情况?在读研?

    • 哈哈!原来你现在是那里的版主啊! :D
      居然会这样碰到故人,真神奇!这个世界太小啦!

  • 曾鸣聪

    《Functional Analysis: An Introduction to Further Topics in Analysis》是这一本。
    原来计算机里可以用图来近似流形啊,我没想到过呢。不过我记得数学里有类似的想法,他们在做代数拓扑的时候貌似有用一个拓扑空间的“神经”,也是像图一样的网格状的东西去研究这个空间本身的性质,不过我只是听人提起过,自己还没有读到相关的东西……
    我一直觉得我们的老师讲Laplacian的那里口味太重了,我自己看的其它参考书在这里全都是用抽象的方式进行定义的,而不是疯狂地做局部坐标卡……我一直觉得微分几何这里有两套体系,一套是我们上课的那种,在局部坐标下拼死拼活,另一套是从一个更加整体且抽象的角度去看各种性质,因为我比较懒,而且记性和算功都不好,所以我会更喜欢后者……

    • 据说局部坐标系这套方法是很有“中国特色”的?据说陈省身很推崇这套方法?好像在外文的书里确实比较少见到一大坨一大坨的局部坐标展开呢。

  • 曾鸣聪

    从我目前读到的书来看,除了中国的教材,还有就是俄罗斯有一套《现代几何学》在大量使用局部坐标计算,而且计算强度要比中国教材还猛烈些。
    据说确实是陈省身他们老一辈的数学家很推崇这套东西,而且老师上课似乎说过,在几何上好像中国分南北派,浙江这边蛮爱局部坐标的,好像北大那边就抽象一点……
    现在看起来,一些重要的结论,两者都可以做到。但是有趣的是,有时候抽象的书在某些地方也会使用局部坐标来说明问题,而即使是我们的书,也有不得不借助抽象的方法的时候……仿佛有的时候局部坐标的计算就是问题的实质,有的时候这种计算却会掩盖住实质……很多地方我也还没搞清楚呢。

    • 总之是互补的关系吧,不管偏向哪边太走极端了总是不行。

      还有就是似乎所有老师都总是在强调学的时候只要看一本书,不要乱七八糟的看很多书,但是好像我看到好多人都喜欢同时看好几本书。这个似乎是学生和老师意见分歧比较大的地方。其实我自己也喜欢同时看几本,也算是一种互补,因为有的时候这里没看明白的可以从另外的地方看明白吧。

      • (插入你们的讨论…)
        我比较同意大部分老师的看法: focus在一本书上. 至少在数学上, 在学习阶段, 先掌握好一个”门派”的”技艺”, 会事半功倍. 同时念一个subject下的很多书对我比较可能产生的结果是: 每种招式都练过, 遇到敌人都用不出..

        • 嗯,你说得也有道理。不过要做到这一点也确实不容易。特别是书本都比较少有完美的,有时候碰到晦涩或者甚至有误的地方的话,就会受到一些诱惑想去参考其他的书。

  • 现在大三了…
    想问一下, 看完文章感觉似乎把流形引进主要是作为一种方便的描述machine learning的语言, 不知流行本身有关的纯数学结果是否有应用呢?

    • 啊,你比我低好多届啊,哈哈。

      不知道你说的村数学结果是指什么?所谓描述 machine learning 的语言,其实就是一种模型吧,数学不是都是这样的吗?在应用的时候被作为一个模型,要这个模型可行,或者说这样做“有道理”,肯定是需要一些数学上的结论的吧。但是至于“纯”数学的结论是指什么我就不清楚了,光滑流形相关的东西我还在学,不知道你能否举个例子,哪种算纯数学上的结论?

      • 比如说会期待连通闭曲面的分类这样的结果”有用”吗?
        我不是做几何方面的, 但是感觉几何里的大部分内容都是ineffective的, 用在计算机领域上感觉有点奇怪…

        • 这个是依赖的吧,比如如果流形能够有一个 global chart 的话,就是很好的。实际上有很大一类的流形学习算法探讨的就是怎么把流形 embedding 到欧氏空间中,这里和数学上说的那个 embedding 不一样,这里的 embedding 是指把 n 维流形映射到同维度的欧氏空间中,同时希望保持一些几何、拓扑性质。但是一个直观的例子就是二维球面肯定没有办法展开为一个平面的。

          不过问题还在于在机器学习的问题中,大部分情况我们得到的“流形”实际上就是一堆点,所以我们事先也并不知道它的几何或者拓扑是怎么样的,这些都要通过数据去推测或者建模拟合出来。

    • 粗略地讲,我觉得机器学习无非就是分类或者回归,更粗略来讲也就是找一个最优的函数 $f: \mathbb{R}^d\rightarrow \mathbb{R}$。那么流形学习就是说把原来欧氏空间中学习扩充到流形中,也就是找 $f: \mathcal{M}\rightarrow \mathbb{R}$ 。所以说流形的性质和结论肯定是需要用到的,至于哪部分有用,哪部分没有用,哪部分是纯数学的哪部分不是,这个就一时说不清楚了。

  • loyal_baby

    很赞。有个问题,想请教一下,拉普拉斯特征映射和马尔科夫是什么关系啊?

  • loyal_baby

    图里面不是有一个马尔科夫随机游动模型嘛?它和拉普拉斯矩阵什么关系呢?

    • 你好,形如 $L=I-D^{-1}W$ 可以用 Markov Random Walk 来解释,这里的聚类过程和一个随机游走有关,其中 $P=I-L$ 是这个随机游走的 transition matrix 。具体请参见 Ulrike von Luxburg 的 A tutorial on Spectral Clustering

  • loyal_baby说的那个马尔科夫应该是在统计上深一点的《随机过程》方面做贡献比较多吧?
    今天听了个博士的答辩,做流形学习,然后google了一下“流形”就找到楼主的博客,文章写的很好呀!

  • gaochuwuyu

    博主你好,我是学工科的研一学生,最近在看流形学习相关的文章,对数学上的概念术语认识不够,看到这篇终于对流形学习有了一个大概的认识,非常感谢分享呵呵!
    但是还是有些地方理解不到呢:
    1、如果将流形看做一个d维空间在m维空间扭曲的结果(这里的d维和m维都是指的欧式空间吧?),那形成的这个流形是d维流形呢还是m维流形呢?就像是平面上的一块布(2维欧式空间也是一个2维流形),在3维欧式空间中扭曲之后形成的依然是2维流形呢还是就变成了一个三维流形了呢,地球、人脸图像这样的流形又是怎样的空间在怎样的空间中扭曲的结果呢。空间想象力实在是不够,敬请博主指教!
    2、还有就是现实中的各种高维数据,需要怎样的条件下才能将其假设为一个流形呢?谢谢博主啦!

  • gaochuwuyu

    谢谢博主,对于球面这样一个2维流形又会是怎样一个2维空间在3维欧式空间的扭曲呢(希望博主不要厌烦O(∩_∩)O)

    • 没有看明白你的意思,球面就是一个二维流形,它和二维平面是不同胚的,但是它们维度是相同的,这并不矛盾。直观来说,在不撕破的情况下,你没有办法把一个球面展开成一个平面。

  • gaochuwuyu

    谢谢啦^_^

  • 讲得真清楚,数学小白拜谢~

    另,错字:于是 Isomap 通过数据点连接起来

  • 薄荷

    请问一下,各种流形学习的方法都有对流形本身性质的一些假设,那么在用具体数据进行学习的时候是否要现对数据集本身做一些研究,判断是否满足该学习算法的要求呢?

  • 薄荷

    那怎么分析呢?具体有哪些方法?我看到有些论文上给出了某种特别的流形的定义,说在这样的流形下有某种算法,那我总不能根据流形本身的定义来判断我所用的数据集是否处于这样一个特殊的流形上吧.你说能做相应的分析最好,那就是说不做这样的分析也可以的,那如果刚好所用的数据集不在这样一个流形上,那效果应该就不好了吧。最近刚接触关于流形学习这方面的东西,很多不懂啊。

    • 根据流形的定义来进行分析不是挺好的么?

      我的意思是说,你可以直接把算法用上,如果效果很好的话,很有可能就是这个数据很符合流形假设啦(当然也有可能是其他巧合的原因导致效果很好)。不过实际中不一定运气总是很好的。

  • 薄荷

    看到前面有个人说有些流形学习算法如isomap,LLE如果选取的特征是pose,出来的流形也是pose,我不是很明白这是怎么做到的。能详细说一下不?

  • 薄荷

    还有想请问一下ISOmap那篇文章,为什么最后不直接让降维后的data之间的距离逼近其原来的测地距离?最后一步中的那个目标函数是什么意思呢?

  • gaochuwuyu

    您好,想请教下:一个d维流形是一个任意点处局部同胚于欧氏空间的空间,那么对于流形空间,其和欧氏空间有什么本质的区别呢,为什么要创造出流形这样一个概念呢?

    • 你好,虽然在局部同胚于欧氏空间,但是全局并不一定能同胚,最简单的例子是球面,它在全局不能同胚于任何 $\mathbb{R}^n$ (球面是紧的,而 $\mathbb{R}^n$ 不紧)。

      笼统地来讲,可以说欧氏空间性质实在太好了,但是要求太高了,经常得不到满足,所以有许多更宽泛的空间。常见的最宽泛的应该数拓扑空间了吧,要求最低,只要有一组拓扑即可。但是可以想像,要求越低,能够得到的优良性质就越少,流形可以说是介于两个极端中的一种常见的空间结构,而且也比较有用。

  • Orange

    我想问一下,做这些模式识别的是不是要很强的数学功底。

    • 一般都需要的吧,不过如果做很实际的问题或者系统之类的,能够熟悉算法什么的,或者有各个方面的人可以合作的话,应该也不一定要很强才能做。

  • lhyl

    你好,最近看了些关于流形的文章,感觉不是很明白,看了博主的文章终于有点感觉了,真是太感谢了!我有个问题想问问,数据是否是流形该怎么判断。我最近在做笔迹鉴别的降维,是先对128*128的笔迹图片使用gabor变换提取出80维的特征,然后对这80的向量进行降维,可我实在想不明白这些数据是不是流形的?有没有一种方法来验证?

    • 你好,这个问题不好回答,实际上来说,流形是一个连续的概念,而数据点总是离散的和有限的,所以说这个问题实际上是没法验证的。不过可以有一些先验知识来假定它是不是流形,还有就是可以干脆直接用上流形的方法,如果效果好的话,那就好了!

  • lhyl

    感谢博主的回复!我想再问一下,如果我事先知道数据之间的类别信息,那么计算所有数据点之间的欧式距离,对于某一点,它与和它同类的数据点之间的距离小于与它异类数据点的距离,如果对于所有数据点都这样,是不是就能说这些数据不是流形的,这样想有没有问题?假设同类数据是相互靠近的,不同类的数据是相互远离的

    • 不一定啊,其实很多流形学习的算法只要要求数据大致分布在流形上或者流形附近就可以了,或者更宽松的只要要求数据只是由少数几个变量或因素来控制的就可以了。你说的这种情况,同类的靠近,不同类的远离,可以去看一下 Linear Discriminate Analysis ,也就是做类似的事情。

  • xwz

    你好,最近我也刚开始看一些流行学习的东西,但觉得好多概念还是很抽象,博主应该在这方面研究了很久吧,实在很佩服。想问一下博主,假如对多个不同维度的点,可不可以把它们统一降到同一的维度呢?

  • mojianxs

    您好,感谢您奉献这么好的文章,我是门外汉,想请教您一个问题。
    已知流形M上的点集A,流形N上的点集B,假设点集可以充分反映流形结构,怎样由这些点集计算流形的相似度,即区分这两个流形?
    流形学习中有没有成熟的方法?

    • 你好,如果是线性流形(Linear Subspace)的话,是有专门的方法来计算 linear subspace 之间的距离的,参考 Grassmann Manifold ,两个子空间可以看成是 Grassmann Manifold 上的两个点,距离可以通过计算测地线距离来得到,好像叫做 Projection Distance ,有矩阵形式的公式可以算的。

      至于 general 的流形,我就不太清楚了。

  • KIDE

    楼主,你好,很感谢你的这篇文章让我对流形入了门。我现在在做模式识别中语音这一块,我现在有几个问题没想明白,麻烦大神指教下,先谢了~1.ISOMAP算法只是一个降维算法,对么?2.而且现在貌似只能降到2维?3.这个算法从高维降低到低维的映射关系有体现么?(我用Matlab做的,用的是网上很经典的Isomap算法,看完这个算法后,我只是感觉他就是一种降维算法,同时它没有体现出那种高维到低维的映射函数)。

    • 你好,Isomap 可以降到任意维度,不止是 2 维。Isomap 没有给出映射函数,也就是说对于新的点如何进行同样的降维结果,是不能直接从 Isomap 算法得到的。

  • 楼主科普得不错,让我看到了几何和拓扑在机器学习中的应用,很有趣。将数据归于流形之上,再给其一个微分结构,我们就可以用研究微分流形的方法来研究数据了,然后那些Ricci Flow之类的概念才可以引进吧。这是我猜测的,不知道是否正确。

  • KIDE

    楼主你好,又来了,呵呵,很感谢你的指点,对我帮助很大,其实我当时也不明白,ISOMAP算法既然基础是MDS,MDS理论上是可以降低到任何维的,可为什么网上现在的ISOMAP算法(MATLAB)代码只是能降低到2维,楼主有找到降低到任意维的MATLAB代码么。这次来麻烦楼主,主要是我还有2个问题需要请教。第一,既然ISOMAP算法只是一种降维方法,不能体现高维降低到低维的映射关系,那么这个映射关系是怎么确定的?有现成的理论还是仍处于探索阶段,是不是随着降低维数的不同,其理论体系(指映射关系)都需要单独建立(即2维的映射关系需要一套理论,3维的映射关系又需要一套理论…..)第二,楼主在文章中说到在图像识别中的运用,那么到底这个ISOMAP算法是运在哪个阶段,一般模式识别就这么几个阶段吧,去噪、特征提取、训练识别,如果可以的话,麻烦楼主大大能多讲一点这个ISOMAP算法到底是怎么用在图像上的,小弟我最近看论文看的有点发懵,忘指点,多谢~

    • 你好,isomap 官方网站提供的代码就可以降到任意维度,请仔细看一下代码。映射关系作为一个 nonlinear map 并没有被 isomap 显式地求出来,并不是说不存在。降维大致可以归到数据预处理的步骤。

  • KIDE

    楼主你好,受益匪浅,先说声谢谢。我想问下你在文章中举得图像例子,是看成了看成了698(图片数量)乘以4096(每张图片的像素点)的数据么,然后用流形降维到698乘以3的数据?如果不是的话,能麻烦你详细说一下降维之前的数据和降维之后的数据是什么样的?

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>