原创 王志鹏、刘易明 2024-12-25 22:53 北京
如何定义复杂网络中的因果涌现
导语
复杂网络中的因果涌现是指对于一个复杂网络来说,在合适的粗粒化处理之后能得到一个宏观的网络,该网络能够比原始网络展现出更强的因果特性,即有效信息(Effective Information,简称EI)更高,则称原始网络发生了因果涌现。复杂网络是一种用图的方式建模复杂系统的模型,广泛应用于多种领域。这些网络通常由大量节点和具有一定随机性的连边组成,节点可以代表个体或元素,而边则代表它们之间的相互作用或联系。因果涌现理论最初是由Erik Hoel[1]等人提出,该理论使用有效信息来量化离散马尔科夫动力学系统的因果性强弱。2020 年,Klein 等人[2]尝试将因果涌现的概念扩展到复杂网络上,核心思路是将复杂网络上的随机游走模型视作一个马尔科夫链,从而应用有效信息比较粗粒化后的更宏观尺度的网络和原始网络上的有效信息(EI)有何变化,当粗粒化网络(宏观尺度)比原始网络 (微观尺度)具有更高的EI时,则说明该网络发生了因果涌现。
近年来,张江老师带领研究组开始聚焦基于新兴 AI 技术进行数据驱动的自动建模研究,并立志破解复杂系统的涌现之谜。我们希望创建一个叫做“复杂AI次方”的开放实验室,实现思想共享、资源共享、跨学科交叉,共同为复杂系统自动建模而奋进。欢迎对复杂系统自动建模领域有热情,且认可这个领域发展前景的朋友一起来合作,促进这一领域的快速发展。
关键词:因果涌现,复杂网络,有效信息,复杂系统
王志鹏、刘易明 | 作者
张江、王志鹏、刘易明 | 审校
目录
1. 方法概述
2. 基本理论
2.1 基本思想
2.2 随机游走动力学
2.3 定义有效信息
2.3.1 网络实例
2.4 粗粒化复杂网络
2.4.1 粗粒化算法
2.4.1.1 贪婪算法
2.4.1.2 谱分解方法
2.4.1.3 梯度下降方法
2.5 定义复杂网络中的因果涌现
3. 数值结果
3.1 人工网络
3.2 真实网络
4. 应用
4.1 在元胞自动机上的应用
4.2 在生物网络上的应用
1. 方法概述
2013年,Erik Hoel等人首次提出了因果涌现理论[1],并使用有效信息(Effective Information, EI)来量化离散马尔科夫动力学系统的因果性强弱。2020年Klein等人尝试将因果涌现理论拓展到复杂网络[2]上。这一扩展的主要思路为将复杂网络转变为一个马尔科夫链,从而可以直接应用Erik Hoel等人的原始方法来判断因果涌现。具体地,Klein等人的方法包括如下几个步骤:
1. 定义复杂网络上的动力学:引入随机游走子(Random Walker),该随机游走子可以沿着网络的连边随机跳转,从而构建该随机游走子的马尔科夫链(其中随机游走子的所有可能状态对应为复杂网络上的所有节点,而状态间的转移概率数值可以定义为每条有向连边的权值占比,即该边上的权重占该节点所有出边的权重的比例);
2. 定义复杂网络上的有效信息:基于随机游走子的概率转移矩阵计算有效信息,如此便可以将原本刻画马尔科夫链的有效信息指标扩展到复杂网络上;
3. 粗粒化复杂网络(即将所有网络上的节点进行分组,转化为一系列宏观节点,并将连边也进行归并)得到宏观的复杂网络,并保证该转化后的网络满足动力学一致性,即保证粗粒化完以后的网络具有与原始网络相似的随机游走动力学;
4. 对比微观网络和粗粒化后的宏观网络的有效信息,判断因果涌现是否发生,并计算因果涌现强度数值。
2. 基本理论
2.1 基本思想
如何将Erik Hoel的因果涌现理论应用到复杂网络上?首先,Erik Hoel的理论是针对离散状态马尔科夫链进行展开的。因此,Klein等人需要将复杂网络转变为马尔科夫链。基本思想是,给网络赋予一套随机游走动力学,从而得到马尔科夫链和转移矩阵。其次,Hoel理论中的核心是有效信息指标,那么对该理论做延展的时候,也需要讨论一个网络的有效信息应该如何计算。再次,因果涌现现象是必须借助粗粒化策略来展现的,因此,Klein等人还要考虑如何粗粒化一个复杂网络。下面,本词条分别进行介绍。
2.2 随机游走动力学
由于因果涌现理论量化的是系统的动力学,对于离散马尔科夫动力学来说就是转移概率矩阵(Transitional Probability Matrix,简称TPM)。然而对于复杂网络来说,给定一个已知网络,并不具有动力学,所以需要人为定义一套网络上的动力学。Klein等人借助随机游走子的概念,在网络上定义了一个随机游走动力学,该动力学可以被自然地用马尔科夫链来进行表示,并且该马尔科夫链的状态就对应了网络上的节点,而状态转移概率矩阵也可以自然地用网络的邻接矩阵的某种变换而得到。
具体的,假设我们考虑一个连通图G,邻接矩阵为
这里,
因此,我们可以直接定义一个马尔科夫链,其状态空间为
2.3 定义有效信息
对于一般的N个状态的马尔科夫链,其概率转移矩阵为:
这里,
下面,我们把这个公式套用到复杂网络上的随机游走子定义的马尔科夫链上
(1)
其中
这两项分别是:
1. 确定性为
2. 网络的非简并性为:
除此之外,1式还可以用有效信息的原始定义,即do干预形式的互信息来理解。在初始时刻,我们假设随机游走子的初始状态分布为:
这相当于游走子会等概率地分布在所有网络节点上,这种初始分布相当于我们对随机游走子的初始分布进行了do干预,把该分布干预为了均匀分布。计算在这个do干预下的t=1时刻和初始时刻两状态分布的互信息,我们同样可以得到1式。
1式就是任意复杂网络G的有效信息的定义式。
2.3.1 网络实例
首先,为了直观地看到网络的拓扑结构和有效信息、确定性、简并性等各个网络指标值之间的关系,下图展示了6种特殊的人工网络,并列出了:确定性、简并性以及有效信息EI值。下图展示的6个图中,有向环形网络(第一个图)的确定性最高,简并性最低,因此有效信息最大,而有向全连通图(第三个图)的确定性和简并性都最小,因此有效信息也最小,其余四个图的有效信息介于这两个图之间。
此外,下面展示了五种经典的人工网络(完全图、星型图、环形图、BA (无标度网络)、ER (随机网络))的确定性和简并性的大小分布,如下图所示,星型网络的确定性最高但是简并性也最高,因此有效信息也最低。同样完全图的确定性和简并性都最小,因此有效信息也最低。其余三个图的确定性较高,简并性较低,因此有效信息也较大。
2.4 粗粒化复杂网络
为了识别复杂网络中的因果涌现,需要对原始网络做粗粒化,而粗粒化操作通常需要有两个步骤:
1. 对原始网络的节点进行分组;
2. 根据节点分组,对网络的节点和相应的连边进行归并,从而得到一个宏观网络。
最后,通过比较宏观网络与微观网络的有效信息,判断能否发生因果涌现。
其中,节点分组的目的是确定哪些原始网络的节点应该被归并为一个宏观节点;而网络的归并的目的是根据分组和原网络的结构而得到一个更小的粗粒化的网络,但却并不丢失原始网络主要特征。
在Klein等人的论文[2],以及Griebenow 等人[3]的文献中,作者们主要提出了三种粗粒化网络的方法,包括:贪婪算法、谱分解方法以及梯度下降方法。这三种方法最大的不同就在于节点分组方案的不同,至于如何归并节点和网络则除了梯度下降方法以外,另外两个都采用了相同的处理手段,即高阶依赖项建模(HOMs)[4],其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性。
Klein等人[2]相当于使用贪婪算法对节点进行分组,但实质上该方法将分组和归并合并在一起执行了。这种方法对于大规模网络来说效率很低。所以,后来Griebenow[3]又提出了一种基于谱分解的方法来对原始网络节点进行分组,并将这种方法应用于偏好依附网络。相较于贪婪算法以及梯度下降算法,谱分解算法的计算时间更少,同时找到的宏观网络也更好(EI更大)。
下面我们分别详细介绍这些粗粒化方法:
2.4.1 粗粒化算法
2.4.1.1 贪婪算法
该方法并不明显区分分组和归并,而是把两个步骤合并到了一起。
输入:具有N个节点的网络
1. 初始化一个节点的集合V,将V中的每个节点所属的马尔可夫毯(这是一个节点的集合,既包括该节点的父节点、子节点以及子节点的其他父节点)也加入集合中;
2. 遍历G中的节点(如果节点已经被合并成宏观节点则跳过),直到所有的节点遍历一遍停止;
3. 初始化一个队列
4. 初始时
5. 分别尝试将
1)执行网络归并算法,尝试归并网络(具体方法参考网络归并),并计算新网络的EI;
2)如果归并后的网络的EI增加了且满足粗粒化后的宏观网络与原始网络保持动力学一致性(具体方法参考动力学的一致性检验),就将这两个节点归并到一起组成新的宏观节点
3)将
4)EI没增加则继续尝试与队列中的其他节点进行归并,直至队列中的节点都归并过,返回步骤2。
时间复杂度:
缺点:
1. 时间复杂度比较高,不适合对规模大的网络进行粗粒化
2.4.1.2 谱分解方法
该方法是将原始网络对应的转移矩阵做特征值分解,并使用这些特征向量来对节点进行聚类,之后再归并网络。
输入:原始包含
1. 针对邻接矩阵与特征向量集合
。
2. 构建新的有偏的特征向量集合(新的网络节点数量为
3. 依据
1)如果节点
2)否则将两个节点间的相似度设为无穷大∞(可以设个比较大的值,如10000)
4. 基于相似度矩阵
5. 根据聚类方案,归并根据网络归并方法(参见网络归并)得到宏观网络
时间复杂度:
缺点:
1. 对规模大的网络进行粗粒化时,对转移矩阵进行特征值分解的计算复杂度也较高;
2. 聚类算法所需的距离超参
2.4.1.3 梯度下降方法
该方法的核心是将粗粒化方案写成一个分组矩阵,同时将这个分组矩阵参数化,这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积,并由此计算EI。之后,使用自动微分方法执行梯度下降算法从而优化分组矩阵,以使得EI最大化。
输入:包含
1. 针对一个含有
2. 根据微观网络和分组矩阵构建宏观网络
3. 使用带动量的梯度下降方法优化
时间复杂度:
缺点:
1. 初始化分组矩阵的选择,多次重复实验会得到不一样的结果;
2. 依赖神经网络的超参,如学习率、迭代次数等。
2.5 定义复杂网络中的因果涌现
有了每个网络的EI度量值,以及如何对任意的复杂网络进行粗粒化的方案,我们便可以给出复杂网络上因果涌现的具体量化了。
给定一个微观网络
3. 数值结果
2020年Klein等人在论文[2]中分析了随机(ER)、偏好依赖(PA)等人工网络,以及生物、社会、信息和技术4类真实网络的有效信息(EI)以及因果涌现(CE)。
3.1 人工网络
为了进一步探究人工网络随着模型参数和网络规模的变化,EI和CE如何变化,作者选取了两种经典网络ER(随机网络)和PA(偏好依赖网络)进行实验:
1)对于ER网络:有效信息的大小只依赖连接概率
2)对于PA网络:当偏好参数
3.2 真实网络
对于真实网络来说,生物网络因为具有很大的噪声,所以有效性()最低,而技术类型网络是更稀疏、非简并的网络,因此,平均效率更高,节点关系更加具体,所以其有效性也最大,如图a所示。通过有效的粗粒化能去除系统的噪声,相较于技术类型网络,生物网络因果涌现最显著,如图b所示。
4. 应用
4.1 在元胞自动机上的应用
Varley等人[5]尝试将上述方法应用到元胞自动机系统中,将每个状态看成一个节点,每个状态会确定的得到下一个状态,从而构成一条有向边,最终可以构建一个有向的确定性网络。文中选择256种中的88个独特的离散元胞自动机,分为四类:静态的、周期性的、混沌的和复杂的,数据也横跨8个尺度,从5个元胞(
3. 存在17个规则对应第三、第四类元胞自动机,其中
4. 相同规则的元胞自动机在不同的尺寸下得到的CE结果大致相同;
4.2 在生物网络上的应用
进一步,Klein 等人将复杂网络中的因果涌现方法扩展到了更多的生物网络中。前文已经指出,生物网络具有更大的噪音,这使得我们很难理解其内部的运作原理,这种噪音一方面来自系统的固有噪音,另一方面是由于测量或观察引入的。Klein 等[6]进一步探索了生物网络中的噪声、简并性和确定性三者之间的关系以及具体含义,得出了一些有趣的结论。
例如,基因表达网络中的高确定性可以理解为一个基因几乎肯定会导致另一个基因的表达。同时生物系统在进化过程中也普遍存在高简并性现象。这两个因素共同导致,目前人们尚不清楚应该在何种尺度上分析生物系统才能更好理解它们的功能。Klein 等[7]分析了超过 1800 个物种的蛋白质相互作用网络,发现宏观尺度的网络具有更小的噪音和简并性,同时与不参与宏观尺度的节点相比,组成宏观尺度网络中的节点更具有弹性。因此,生物网络为了适应进化的要求,需要演化出宏观尺度以提高确定性来增强网络弹性以及提高信息传输的有效性。
Hoel 等在文章[8]中借助有效信息理论进一步研究了生物系统中的因果涌现。作者将有效信息应用到基因调控网络上,以识别最能提供信息的心脏发育模型从而控制哺乳动物的心脏发育。通过量化酿酒酵母基因网络的最大连通集团中的因果涌现,文章揭示了富有信息的宏观尺度在生物学中是普遍存在的,以及生命机制本身也经常运行在宏观尺度上。该文章也为生物学家提供了一种可计算的工具来识别最具有信息的宏观尺度,并且可以在此基础上建模、预测、控制和理解复杂的生物系统。
Swain 等在文章[9]中探索了蚁群的交互历史对任务分配和任务切换的影响,将蚁群用网络进行建模,使用有效信息研究噪声如何在蚂蚁之间传播。结果发现,蚁群之间历史交互程度影响任务的分配,并且具体交互中蚂蚁群体的类型决定了交互中的噪音。此外,即使当蚂蚁切换功能群时,蚁群涌现出来的凝聚力也能保证群体的稳定,同时不同功能蚁群在维持蚁群凝聚力方面也发挥着不同的作用。
代码:
参考文献:
1. Hoel E P, Albantakis L, Tononi G. Quantifying causal emergence shows that macro can beat micro[J]. Proceedings of the National Academy of Sciences, 2013, 110(49): 19790-19795.
2. Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.
3. Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.
4. Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.
5. Varley, Thomas F. "Causal emergence in discrete and continuous dynamical systems." arXiv preprint arXiv:2003.13075 (2020).
6. Klein B, Swain A, Byrum T, et al. Exploring noise, degeneracy and determinism in biological networks with the einet package[J]. Methods in Ecology and Evolution, 2022, 13(4): 799-804.
7. Klein B, Hoel E, Swain A, et al. Evolution and emergence: higher order information structure in protein interactomes across the tree of life[J]. Integrative Biology, 2021, 13(12): 283-294.
8. Hoel E, Levin M. Emergence of informative higher scales in biological systems: a computational toolkit for optimal prediction and control[J]. Communicative & Integrative Biology, 2020, 13(1): 108-118.
9. Swain A, Williams S D, Di Felice L J, et al. Interactions and information: exploring task allocation in ant colonies using network analysis[J]. Animal Behaviour, 2022, 18969-81.
因果涌现读书会第五季
跨尺度、跨层次的涌现是复杂系统研究的关键问题,生命起源和意识起源这两座仰之弥高的大山是其代表。从2021年夏天至今,集智俱乐部已经陆续举办了四季「因果涌现」读书会,系统梳理了因果涌现理论的发展脉络,深入探讨了信息整合与信息分解的本质,并探索了在生物网络、脑网络、机器学习等跨学科领域的应用。此次因果涌现读书会第五季将追踪因果涌现领域的前沿进展,展示集智社区成员的原创性工作,希望探讨因果涌现理论、复杂系统的低秩表示理论、本征微观态理论之间的相通之处,对复杂系统的涌现现象有更深刻的理解。读书会已完结,现在报名可加入社群并解锁回放视频权限。
详情请见:
荟萃复杂系统前沿进展,集结因果涌现学术社区:因果涌现读书会第五季启动
“复杂 AI 次方”开放实验室招募
作为北师大系统科学学院教授、集智俱乐部与集智学园创始人、集智科学研究中心院长,张江从2003年开始长期从事有关复杂系统建模的工作。近年来,张江带领着北师大的研究组开始聚焦在基于新兴AI技术进行基于数据驱动的自动建模研究,并立志破解复杂系统的涌现之谜。我们希望可以有对复杂系统自动建模领域有热情,且认可这个领域发展前景的朋友一起来合作,促进这一领域的快速发展。我们希望这个叫做“ Complexity AI ”,中文叫做“复杂AI次方”的开放实验室,能够真正实现思想共享、资源共享、跨学科交叉,共同为复杂系统自动建模而奋进。
详情请见:“复杂 AI 次方”开放实验室招募,挑战“涌现”难题
推荐阅读
2. 机器学习框架NIS+:通过最大化有效信息识别“因果涌现”|集智百科
4. 张江:第三代人工智能技术基础——从可微分编程到因果推理 | 集智学园全新课程
5. 龙年大运起,学习正当时!解锁集智全站内容,开启新年学习计划
6. 加入集智,一起复杂!
点击“阅读原文”,报名读书会