一文了解基于复杂网络的机器学习_飞道的博客

一文了解基于复杂网络的机器学习

2020-09-07 11:41 425人阅读评论(0)

作者：莫凡

来源：华章计算机（hzbook_jsj）

机器学习是一门有趣的学科，它本身就是一门交叉学科，同时又继续与新的学科交叉，不断产生新的分支，就像是时时推出新口味的碳酸饮料，让贪婪的味蕾跃跃欲试。早前我走进一家便利店，看到架上摆着一款新品，名叫“咖啡可乐”，虽然已经有几位朋友提醒说这款饮料味道一言难尽，可是最终还是按捺得住试一试的冲动。咖啡可乐的味道当然见仁见智，但那种新品尝鲜的好奇与喜悦，大家一定都能感受得到。那么今天，我们也尝鲜一款机器学习的新品——基于复杂网络的机器学习。

基于复杂网络的机器学习方法，顾名思义，是复杂网络和机器学习交叉得到的新分支，要了解清楚这个新分支，首先得从复杂网络说起。我们知道，机器学习里面已经有不少网络，大家最熟悉的应该是神经网络。神经网络的玩法很多，譬如增加网络层数，变成深度神经网络，也即深度学习。那这个复杂网络，大家可能就会猜了，是不是也是某类神经网络的变种，这个“复杂”又究竟指的什么呢？

复杂网络和神经网络无关，它本身是一门独立的学科，名字就叫“复杂网络”（Complex Newworks）。复杂网络的“复杂”，要从图论说起。图论，是专门研究图的数学分支，我曾经在介绍图神经网络时提到过图论(点我查看：有图有真相——图神经网络到底是什么？)，大家都反映说，感觉图论很难，光是“图论”这两个字，平时极少接触，一听心里就犯怵。其实，在计算机科学中，图和树一样，是一种常用的数据结构，而图论虽然是一门数学分支，但它的起源，却远不是大家想象的一群搞数学的老头子关在黑屋子里憋出来的高深理论，反而总要带着一点挥之不去的中二气质。

中二是一种难以解释的神秘力量，人在中二力量的驱使下，往往会做出许多让人迷惑的行为。我也不例外，以前特别爱干的一件事，就是挑战马路牙子。什么意思呢？就是放着宽阔的人行道不走，非要跑到人行道和马路交界那条细细的马路牙子，要求像走独木桥一样只能在马路牙子上面行走，脚不能触碰到两边的马路和人行道，这就是挑战马路牙子。非常的中二吧，可是图论的起源问题，和挑战马路牙子实在是半斤八两。

图论最早起源于哥尼斯堡七桥问题，或者简称七桥问题。别看名字挺像回事，我一介绍你就知道，这个问题可以说是异常的中二。哥尼斯堡是欧洲的一座城市，按现在的行政区划，属于俄罗斯。哥尼斯堡市内分布有七座桥，这七座桥把哥尼斯堡市切分成了四个区。后来，不知道是谁在中二力量的驱使下提出了一个异常中二的要求：能不能挑战一下这七座桥，找到一条路径把这七座桥全走一遍，同时要求每座桥只能走一次。这就是图论祖师爷级的哥尼斯堡七桥问题。

虽然这个问题异常中二，但确实吸引了不少吃瓜群众乐此不疲地尝试想要挑战成功，其中就有一位经常入选数学教材封面的男人——欧拉。欧拉不一般，别人挑战七桥问题，也就是茶余饭后用脚走走，欧拉不是，他专门研究了哥尼斯堡市的地图，然后设计了一套抽象理论，把七桥问题抽象成点和边的关系问题，最后证明了这个中二问题无解，真可谓是不一般的中二。而这套中二理论后来不断发展壮大，成为一条热门的数学分支，大家还专门给它起了一个相当正经的名字，没错，就是图论。别看图论现在西装革履，但研究的重点仍然是点和边的各种关系，这就是当年留下来的深深的中二烙印。

图论的研究重点是图，而复杂网络不妨简单认为是图的plus升级版，所以，复杂网络理论原封不动地继承了图论的各种定义和方法，也就不足为奇。也许你会感觉不理解，既然已经有了图论这条热门分支，为什么还要再横生枝节？

原因是复杂。

不是说原因很复杂，没法讲清楚，而是说原因就是两个字，复杂。我们人类一直以来都在思索一个问题：我们所在的究竟是一个怎样的世界。这个问题看似简单，但却引得无数人皓首穷经，建立了无数的理论想要尝试解答，而且还不断有新的理论加入其中，复杂网络就是其中之一。

复杂网络里的“网络”，往往指得是现实世界的网络，譬如说社交网络，譬如说金融网络，又譬如说流行病传播网络，妈妈常说，现实世界很复杂，所以，这些源自于现实世界的网络，除了网络规模都特别大以外，往往都有一个共同特点，那就是复杂。

这也导致了一个有趣的现象，介绍复杂网络的教材，一般会分为两个部分，第一个部分介绍图论的相关内容，这是复杂网络的基础，第二个部分介绍复杂网络的各种理论模型，这才是复杂网络理论的本体，一本书读完下来，感觉像是在读经济学的教材，第一个部分讲的是微观经济学，而第二部分则讲的是宏观经济学。虽然不能说微观经济学和宏观经济学是两套相对独立的理论，但总感觉像是有一把无形的利刃“咔嚓”一下，把一套理论从哪里开始分成了两个部分。读复杂理论的相关教材时，不妨注意一下这个现象。

也许你会觉得，复杂网络研究的都是那些非常宏大、一般人很少接触的专业对象，它的研究成果也和日常生活没啥关系，用处不大。其实不然，复杂网络的许多研究，我们不但听过，甚至还可能很熟。

我举一个例子，小世界网络理论。最强大脑有过一项挑战，叫“点灯小世界”，游戏规则就是从小世界理论而来。这个小世界网络理论正是复杂网络中的一个重要的网络模型。简单来说，小世界网络理论，就是指现实世界的一些网络表现出了小世界性。

什么叫小世界性呢？用图论的术语来解释，就是大多数节点可以通过少量的几条边到达特定的一个节点。

这么说了一串，你看了肯定挠头，是不是反而更加坚定了“复杂网络果然与我无关”的念头？别急，小世界理论是一个很大的研究领域，里面还有许许多多的理论，有一个理论，只要我说出名字，大家一定都会长“哦”一声表示听过。这个理论，就是社交网络中非常有名的“六度分离理论”。六度分离理论已经被营销号写烂了，甚至搞出了很多谣言，说这个理论是由Facebook发现的，这是不对的。

六度分离理论是对现实世界提出得一个假设，内容十分好懂，说的是世界上不管哪个国家哪个地区，任意选定两个人，从他俩各种的朋友圈出发，只需要经过六个中间人即可联系到对方。简单来说，就是你的朋友圈的朋友圈的朋友圈的朋友圈的朋友圈的朋友圈的朋友圈里，一定会有一个我......嗯听起来实在太糟糕了，换个别人也是可以的，譬如说乘风破浪的某位姐姐。

六度分离理论提出得非常早，1909年就有人提出了咱们这个世界是“六度分离”的猜想，而到了1967年，哈佛大学的一名心理学家第一次对这个猜想做了验证，验证的方法很简单，他选定了一个人，当然不是名人，是一个叫布朗的波士顿股票经纪人，然后找到阿拉斯加的一群人把信寄给他。寄信的方式稍微特别一点，不是扔进邮筒，而是通过身边“可能认识布朗”的朋友。当然了，住在阿拉斯加的人自然没谁认识这么一位没啥名气的波士顿股票经纪人，但最终的结果是通过5.5个中间人，大家都把信寄给了这位布朗先生。

世界，比大家想象的要小多了，这就是小世界性。前面说到Facebook，Facebook虽然不是六度分离理论的提出者，但也作了一点贡献。什么贡献呢？它把六度分离进一步减少，现在是4.5度分离理论，也就是说，地球上任意选定的两个人，中间只隔着不到5位中间人就能发生联系，这就是为什么我们老说，现在说共住地球村。

我最早接触复杂网络，是从SIR模型开始的。SIR是一款在流行病传播学上非常有名的模型，SIR分别代表了传播网络中节点的三种角色，S表示易感者，I表示感染者，R表示康复者，通过计算SIR模型的动力学过程，能够推演流行病在传播网络上的传播情况，简单来说，就是最终会感染多少人，什么时候会出现拐点。在2020年的战疫期间，我相信许多研究机构一定对这两个问题进行了反复的研究，他们所使用的众多手段中，应该就包含有这款SIR模型。

SIR模型还根据现实世界的传播情况，衍生了许多的变种，譬如说SIS模型，总体上可以说就是SIR模型的翻版，但对一个规则进行了调整：在SIR模型中，传播节点一旦康复，就默认获得免疫能力，不会在变成易感者。这个假设前提对于肺结核等流行病是不成立的。而SIS模型正是更改了这一假设，在SIS模型中，康复者仍然又可以变成易感者。不难想象，这条规则调整看似简单，但同样能够给传播网络带来截然不同的变化，颇有点狼人杀的各种变异版的意思。

多说一句，SIR模型虽然发源于流行病传播学，但这款模型的应用非常广，绝非卫生界所独占，许多社交网络信息的传播同样可以使用SIR模型，譬如说朋友圈谣言的传播研究，很多论文就是基于SIR模型或者变种模型来完成。

最后我们聊一聊基于复杂网络的机器学习。

经过前面的介绍，相信大家对于复杂网络究竟是什么，以及能够做什么，有了一点基础的认识。但一个疑惑打消了，另一个疑惑就升了起来：复杂网络研究的是网络，这和机器学习能有什么关系？

确实。我第一次看到基于复杂网络的机器学习论文时，感到非常惊讶，当时我对复杂网络和机器学习都有一些了解，所以我无论如何也想象不到。复杂网络的那些理论，如何才能用于研究机器学习的那些有监督学习和无监督学习的问题呢？

破题的关键，在于构建网络。

对于机器学习，我在《机器学习算法的数学解析与Python实现》介绍说，数据是机器学习的燃料。机器学习各种模型的运行，严重依赖于数据集。数据集就是很多样本数据的集合，回忆一下，我们一般是用向量来存储一条样本数据的信息，《机器学习算法的数学解析与Python实现》还专门拿了电子表格来作对比。

基于向量的数据能不能转化为基于网络的数据？

答案是可以的。基于向量的数据是一个一个的点，而基于网络的数据则是有点有边，要解决这个问题，关键在于如何构建边。这里的“边”也不是随便画画就行，表示的是两个点之间的关系。只要找到两个样本点数据之间的关系，就能构建边了。在机器学习中，相似性是我们非常关心的一类关系，而且有大量成熟的数学工具，能够用于度量两个点之间的相似性，譬如欧氏距离，又譬如说曼哈顿距离，这些数学工具我都在《机器学习算法的数学解析与Python实现》的KNN模型一章中进行了介绍，利用这些数学工具，我们就能度量两个样本点之间的关系，从而完成了边的构建。

基于网络的数据还有另一种情况，前面我们讨论的是本身没有关系的数据集，而有一些数据集，譬如说社交网络数据集，不同的样本点数据本身就自带有某种关系，对于这样的数据集要转化成基于网络的数据集，那就更为容易了。

现在，既然我们已经能够将普通的基于向量的数据，转化为基于网络的数据，而复杂网络理论所研究的正是各种基于网络的数据，自然就能够将复杂网络中的各种模型迁移到机器学习上来。当然，话虽如此，真要把模型从复杂网络迁移到机器学习，其中还需要对模型算法根据机器学习的特点进行各种调整，不过总的来说，复杂网络的理论用于解决机器学习方面的问题，在理论上是没有问题的。

为什么要使用复杂网络来解决机器学习问题？

前面我们解决了将复杂网络理论迁移到机器学习领域的问题，但这自然而然会引申出第二个问题，为什么要迁移过来？是为了艺术而艺术，还是有什么额外好处？这个问题无论你是翻论文还是看教材，得到的答案一定是第二个，有额外的好处。不过，我觉得两者兼有。学术研究也是追求趣味性的，也和我那贪婪的味蕾一样，喜好尝鲜，放着复杂理论这么好的理论，不在其它热门领域，譬如说机器学习领域搞点新东西，这还对得起观众老爷们那些蠢蠢欲动的味蕾吗？

当然，额外的好处也是有的，有很多。在哪里呢？就在构建基于网络的数据这里。机器学习似乎正朝着基于网络的数据方向发展，这其中很重要的原因，我想是有监督学习的发展遇到了瓶颈。给数据打标签是有监督学习的一项常见的工作，也是一项颇费人力的工作，学界和工业界都在不断思索着，机器学习应该如何摆脱对标签数据的依赖，哪怕能够减少一点依赖也好。

不依赖标签数据，那就是无监督学习，减少一点依赖，那就是半监督学习，而基于网络的无监督学习和半监督学习，正是当前的正在被积极探索的前沿研究方向，复杂网络在这些方面具有先天优势，很自然地就被吸收借鉴进来。

那是不是复杂网络在有监督学习方面就没有用武之地了呢？不是，使用复杂网络模型同样可以完成分类之类的经典有监督学习任务，不过，因为有监督学习任务往往都有比较充足的标签数据，供复杂网络发挥的余地不大，总的来说在这方面的研究相对较少。

就我看到的情况来说，确实有一些研究人员把复杂网络的模型直接搬进这些领域，不过总有一点削足适履的感觉，更主流的做法是借助复杂网络中的一些思想和数学工具，从而设计出一些全新的模型。

复杂网络是一门有趣的学科，所以，喜好尝鲜的同学自然不应该错过基于复杂网络的机器学习。想更系统地了解复杂网络和复杂网络在机器学习这方面的理论知识，我推荐阅读《基于复杂网络的机器学习方法》，此前我了解相关内容，一直都是靠翻看零散的论文，这本书是我见到的第一本系统介绍这方面内容的教材，而且对有监督学习、无监督学习和半监督学习，都给出了具体的应用案例。

下次再聊。

作者简介：

莫凡,网名木羊同学。娱乐向机器学习解说选手，《机器学习算法的数学解析与Python实现》作者，前沿技术发展观潮者，擅长高冷技术的“白菜化”解说，微信公众号“睡前机器学习”，个人知乎号“木羊”。

RECOMMEND