神奇的数学.doc

神奇的数学 一直以来对于数学的神奇性都是从一些简单的公式上体会到的，而对于其用途、各学科的跨连方面展现出来的神奇却难有机会去体验。这两天一直在和实验室同学讨论图形、矩阵、谱聚类、流形等方面的知识，到今天为止将各个关节打通，将它们的所有东西串联起来的时候心中顿生极爽的感觉，头一次发现各个学科之间的联系竟然是那么自然又神奇。1. 图 Graph 首先我们来看“图”。图是由点以及连接点的边所组成，我们可以将它看作是世间万物联系的表达。“点”代表具体的对象，“边”代表了每两个元素之间的联系。联系有强有弱，体现在边的权重 (Weight) 可大可小一样。这个概念很简单，但是它对于现实世界的描述却是很生动，因为“联系”的性质和度量大小可以由具体的学科和环境来确定。2. 矩阵 Matrix 我们如何来表示图呢？大家一下子就能想起线性代数里面的“矩阵”。每个矩阵由行和列所组成，那么可以把每行或每列对应为图上的一个点，矩阵点坐标下的元素值表达为这两点之间的边的权重。根据有向图或者无向图，矩阵可能是对称的或者非对称的。假设图含有 n 个点，那么对应的 n*n 矩阵就被称作是邻接矩阵 (Adjacency Matrix)。3. 谱 Spectrum 学习过线性代数的朋友都知道特征值 (eigenvalue) 和特征向量 (eigenvector) 的概念。粗糙地讲，对于一个矩阵M来说，如果存在列向量 v 和实数 a ，使得 M * v = a * v，那么 a 便是矩阵的特征值，v 则是对应的特征向量。从形式上看，矩阵M对特征向量 v 的变换就如同把 v 沿着原来的方向拉长(或者缩减)为原来的a倍。多个特征值 a1, a2, . 和对应的特征向量 v1, v2, .组成了矩阵M的特征对(eigenpair)空间。如果有任意一个列向量X，它能分解成为v1, v2, . 特征向量的线性组合的话，即 X = x1*v1+x2*v2+.，那么矩阵 M 对 X 的变换 M*X = M*(x1*v1+x2*v2+.) = x1*a1*v1 + x2*a2*v2 + . 。这等同于说M将X分解成为各个特征向量的组合。 回想一下物理学的“谱”的概念。我们说光谱，指的是把任何一条光线按照频率范围分解成为多个分量，分量之间的频率带互不重叠。任何两条色彩不同的光线都可以分解成为这些分量的线性组合，但是组合的系数必然不同。频谱的概念也非常类似，只不过是把各个频率基本分量进行线性叠加而已，频谱不同，那么各个分量所占据的比例就不同。 所以，矩阵 M 对列向量 X 的操作，就好像是先把 X 分解成为基本向量的线性组合，这些基本分量便是 M 的各个特征向量，M 对 X 操作便分解成为了对自己的各个特征向量的操作。所以在很多学科中，特征向量便被称作是“谱”了。以前并不知道这个概念是如何来的，一头雾水，经过这种理解便觉得恍然大悟。创造这个名字的人一定是个通晓物理的数学家，概念借用的手法堪称神来之笔。4. 图分割 Graph Partition “图分割”在数学界和计算机理论界存在很多的应用。它指的是把一个图分割成为多个紧密联系的部分，保证每个部分内部要联系紧密，而部分与部分之间则联系很少，甚至没有任何联系。这好像和常规意义下的“聚簇”概念非常相似？对，你想的一点没错，我们会在下面讲述“谱聚类”，它就是因此衍生出来的方法。但是需要提醒大家注意的是，这里“联系”二字的概念有着丰富的内涵，正是它与“距离”二字的不同，使其和普通“球形分割”和常规聚簇的概念泾渭分明。 因为可以把图 G 表示成为矩阵 M 了，那么图分割的结果便是将矩阵 M 重新组织后能达到沿对角线(附近)的元素上有值，而其他部分的值要么为零，要么很小。这些沿对角线周围的元素又可以被严格分成 k 个小方块，分别对应着图 G 分割出来的 k 个子图。这些子图内部元素紧密结合，但是子图之间互相独立，联系很少。 刚才我们提到，矩阵M的特征向量空间中，每两个特征向量之间在很大概率上是互相正交的，也便是说它们都是矩阵 M 的基本分量且两两之间联系很少，那么一个大胆的设想便是：图 G 的一个分割子图与相关矩阵的一个特征分量之间是否存在着微妙的联系呢？ 理论上已经证明，“谱”的概念将“图分割”和“矩阵特征向量”两个看似毫不相关的东西巧妙地联姻起来了。当然二者之间的关系并不是特别直接，而是需要对矩阵 M 进行一下变换使之成为一个“Laplacian Matrix”，特征向量也是针对它而说的。看似远不着边的两个东西，如今居然神奇地结合在一块。这也让我们想到，数学上面很多概念刚被提出来时也许只是看到了它的某些应用和功能，绝对没有想到日后还能从这个概念里发掘出如此丰富的宝藏。这样的事例在数学界数不胜数，“特征向量”又为这些历史添上了生动的一笔。5. 谱聚类 Spectral Clustering “Clustering”的目的是将 n 个数据点分成 k 个簇，使得每个簇内部的点之间非常相似而不同簇之间的点差异较大。一般而言，人们总是根据两点之间的 distance 为分簇的依据。比如说点o 与 点p 之间距离很近，但是 点o 与 点q 之间距离很远，那么 o 和 p 可能被聚簇到一块，而 q 却单独成簇。这是通常情况的做法。现在问题来了，考虑这么一种情况：点o、q之间距离虽然很远，但是它们二者之间一直都有一些距离很近的中间结点联系起来，比如说 o-e-f-g-q，虽然始点到终点之间距离很远但是中间每两个结点之间距离很近，形成一个连续的带状，而 点o 和 点p 之间虽然很近，但是二点中间却没有点将二者联系起来，即它们在两个互不联系的带状里，那么我们应该如何聚簇呢？ 为了方便理解，我们考虑一下北京的交通图。把三环和四环上的每个石墩看做是一个数据点，石墩之间的距离就是数据点的 distance。那么按照我们的常理，应该把三环上的所有点聚簇成一个组，四环上的所有点聚成一个组。尽管三环上的某些点会离对面的四环上的另外一些点很接近，也不能把它们聚簇到一组中来。这便是谱聚类的一个示例。 谱聚类来源于“图分割”理论，把每个数据点当作是图上的一个点，要把数据点们分成 k 个簇，等同于把图分割成 k 个子图，因此要寻找出相关矩阵的特征值和特征向量。这种聚类方法又被称为是“谱聚类”。我们把思维跳出来，想想谱聚类和常规聚类的不同点在什么地方呢？为什么谱聚类必须和特征向量联系起来，而常规聚类只关心点点之间的距离就可以了呢？这源于二者聚簇的目的不一样。谱聚类中更多关心的是点与点之间的“沟通”与“联系”，只要能通过第3个或者第4个中间节点联系起二者，那么这二者间就存在着相对较强的联系，可以被认为它们处于一个“社交圈子”或者“社会关系的网络”之中。传统的聚簇方案基于直线距离，距离近的便被认为是一个圈子，远的就不被认为一个圈子。在谱聚类中看重点与点之间的连续性和相关性，这与特征向量的概念何其相似！6. 流形 Manifold 流形的一个应用是基于谱聚类的思想。谱聚类中分割而来的一个聚簇，其形状可能是极其不规则的，内部两点之间也可能相隔很远，但是总是可以通过该簇内部的联系，将距离很远的点连接起来。比如说，尽管学生“张三”不认识“王二”，但是“李四”却都认识“张三”和“王二”，因此，“王二”得到学校要放假的消息，就不难通过“李四”传到他不认识的“张三”那里。这里面三个人就形成了一个带状簇，或者说流形结构。依靠这种认识，我们将能在一个流形内传递各种信息，最终使得流形内每个点达到非常均衡的稳态，得到的信息量是同样的。 如何才能使得消息的传递最终会是一个收敛的结果而不至于发散到无法控制的地步呢？我们一会再讲。7. Markov 过程 Markov 过程指的是，明天状态的取值只和今天的状态有关，而和昨天的无关。即，在状态转移矩阵 M 给定的情况下，当第 t 次迭代的取值确定后，第 t+1 次迭代后的值也便确定了。用下面的这个式子来表达: s(t+1) = M * s(t) 。在很多实际问题中，我们想知道这样一直迭代下去的结果会是什么样的？有没有可能是收敛的呢？ 假设结果是收敛的，并且收敛到了状态结果S，那么上面的式子在 t 趋近于无穷时可以得到 S = M * S, 也就是说矩阵 M 存在一个特征值为1，S 就是 1 对应的特征向量。这是可能的吗？ 我们来看由于列向量 s(t) = Mt * s(0) ，由于 s(0) 可以表达成为M的特征向量的线性组合，即 s(t) = Mt * (x1*v1+x2*v2+x3*v3 + .) = x1*v1 + x2* a2t *v2 + x3* a3t *v3 + . 。其中 v1 便是 1 对应的特征向量，在迭代过程中不会变化而成为稳态收敛结果，如果其余的特征值 a2, a3, . 绝对值都 1 的话，那么后面各项都将收敛于 0 。因此问题归结于概率转移矩阵的 dominant eigenvalue 是否是 1 且其余的 eigenvalue 绝对值都小于 1. 数学上已经证明在一定条件下，这样的结果是完全可以达到的。前提条件之一便是：矩阵 M 对应的图上，每两个点之间都是存在连通路径的，也就是说该图必须是一个连通图，任何两点之间都能找到一条路径将它们二者连接起来，用更加数学化的语言来说，矩阵 M 必须是“不可约”的。这很好理解，要达到全局的稳定状态，那么不能存在一些点之间是无法传播信息和沟通的。另外，由于状态转移矩阵 M 的每行元素值之和等于 1，结合前提条件，就很容易得知存在最大的特征值 1 。8. HITS, PageRank, Manifold, 矩阵的收敛性 对互联网有所了解的朋友都知道，PageRank 和 HITS 在对网页进行排名时，无论其结果是否依赖于查询值，排名都是一个稳态的收敛值。我们先来看 HITS 。 HITS 中每个网页有两个值，一个叫 Authority, 一个叫 Hub, 不过二者地位等同，我们分析一个即可。HITS 中采用了相互加强的原理，最终 Authority 值都是初始值和链接结构矩阵 M 来决定的。Authority(t) = (M M)t * Authority(0)，其中 M 指的是M的转置矩阵。由于 M M 是一个对称的半正定矩阵，通过幂方法很容易证明其收敛性。不过看到这里，你也许会问 HITS 算法的收敛性证明好像和刚才所讲的没什么关系？确实没什么关系，但是我们将它列出来是因为这节的主题是矩阵收敛性，在这方面 HITS 算法是一个非常典型的例子，又是一个不同寻常的例子，因为它的转移矩阵是对称的半正定矩阵 。如果转移矩阵是一个一般的矩阵呢？什么情况下会达到多次迭代后收敛的状态呢？ PageRank 和 Manifold 中的矩阵并不具备特殊性，它们是两个典型的常规矩阵收敛的案例。我们知道 Google 创始人在提出 PageRank 的时候对转移矩阵 M 做出了两个改动，一个为那些光进不出的“悬停节点”附上了极小的正数值，第二个是给每个元素都加上了一个极小的正数值。这样的做法保证了每行元素值和为 1 ，又使得每个元素值都为正用来保证矩阵的“不可约”性。同样的道理，在 Manifold 中也必须对原始的近似度矩阵进行规则化，使得满足这两个条件。这和 Markov 状态转换中矩阵 M 的两个条件是一模一样的。三者的收敛性求证之路归结到一条道路上来了根据线性代数学上的 Perron-Frobenius 定理，容易知道存在最大的特征值1，同时它们必定会收敛。这样我们就给出了矩阵收敛的通用法则。 总结： 说到此处，应该对本文做一个简单的总结了。我们发现了图、矩阵、特征空间、谱、聚簇、流形学习、以 PageRank 为代表的矩阵收敛性问题中存在的联系。深度发掘一下，是“特征向量”概念的提出，带出来内部丰富的抽象内容。它不光是基本分量，同样代表了内部紧密联系，外部差异很大的部分，通过它我们可以将图形分割出来，我们也可以在它对应的结构内部传递消息，状态转换，在满足一定条件下总