“复杂网络中的因果涌现”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第83行： 第83行：
  
 
===粗粒化复杂网络===  
 
===粗粒化复杂网络===  
−
为了识别复杂网络中的因果涌现，需要对网络进行[[粗粒化]]，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。Klein等人<ref name=":0" />利用贪婪算法构建了宏观尺度的网络，发现对于大规模网络其效率很低。Griebenow 等人<ref>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.</ref>提出了一种基于谱分解的方法识别偏好依赖网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著。
+
为了识别复杂网络中的因果涌现，需要对网络进行[[粗粒化]]，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。Klein等人<ref name=":0" />利用贪婪算法构建了宏观尺度的网络，发现对于大规模网络其效率很低。Griebenow 等人<ref>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.</ref>提出了一种基于谱分解的方法，并应用于[[偏好依附网络]]。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。
 
====贪婪算法====
 
====贪婪算法====
  

2024年11月2日 (六) 14:07的版本

复杂网络中的因果涌现是指对于一个复杂网络来说，在合适的粗粒化处理之后能得到一个宏观的网络，该网络能够比原始网络展现出更强的因果特性，即有效信息（Effective Information，简称EI）更高，则称原始网络发生了因果涌现。复杂网络是一种用图的方式建模复杂系统的模型，广泛应用于多种领域。这些网络通常由大量节点和具有一定随机性的连边组成，节点可以代表个体或元素，而边则代表它们之间的相互作用或联系。因果涌现理论最初是由Erik Hoel[1]等人提出，并使用有效信息来量化离散马尔科夫动力学系统的因果性强弱。2020 年，Klein 等人[2]尝试将因果涌现的概念扩展到复杂网络上，核心思路是将复杂网络上的随机游走模型视作一个马尔科夫链，从而应用有效信息比较粗粒化后的更宏观尺度的网络和原始网络上的有效信息（EI）有何变化，当粗粒化网络（宏观尺度）比原始网络 （微观尺度）具有更高的EI 时，则说明该网络发生了因果涌现。

历史渊源

2013年，Erik Hoel等人首次提出了因果涌现理论[1]，并使用有效信息（Effective Information, EI）来量化离散马尔科夫动力学系统的因果性强弱。2020年Klein等人尝试将因果涌现理论拓展到复杂网络[2]上。这一扩展的主要思路为将复杂网络转变为一个马尔科夫链，从而可以直接应用Erik Hoel等人的原始方法来判断因果涌现。具体地，Klein等人的方法包括如下几个步骤：

  1. 定义复杂网络上的动力学：引入随机游走子，该随机游走子可以沿着网络的连边随机跳转，从而构建该随机游走子的马尔科夫链（其中随机游走子的所有可能状态对应为复杂网络上的不同节点，而状态间的转移概率数值可以定义为每个节点的度的倒数）；
  2. 定义复杂网络上的有效信息：基于随机游走子的概率转移矩阵计算有效信息，如此便可以将原本刻画马尔科夫链的有效信息指标扩展到复杂网络上；
  3. 粗粒化复杂网络（即将所有网络上的节点进行分组，转化为一系列宏观节点，并将连边也进行归并）得到宏观的复杂网络，并保证该转化后的网络满足动力学的一致性，即保证粗粒化完以后的网络具有与原始网络相似的随机游走动力学；
  4. 对比微观网络和粗粒化后的宏观网络的有效信息，判断因果涌现是否发生，并计算因果涌现强度数值。

基本理论

基本思想

如何将Erik Hoel的因果涌现理论应用到复杂网络上？首先，Erik Hoel的理论是针对离散状态马尔科夫链进行展开的。因此，Klein等人需要将复杂网络转变为马尔科夫链。基本思想是，给网络赋予一套随机游走动力学，从而得到马尔科夫链和转移矩阵。其次，Hoel理论中的核心是有效信息指标，那么对该理论做延展的时候，也需要讨论一个网络的有效信息应该如何计算。再次，因果涌现现象是必须借助粗粒化策略来展现的，因此，Klein等人还要考虑如何粗粒化一个复杂网络。下面，本词条分别进行介绍。

随机游走动力学

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是转移概率矩阵（Transitional Probability Matrix，简称TPM）。然而对于复杂网络来说，给定一个已知网络，并不具有动力学，所以需要人为定义一套网络上的动力学。Klein等人借助随机游走子的概念，在网络上定义了一个随机游走动力学，该动力学可以被自然地用马尔科夫链来进行表示，并且该马尔科夫链的状态就对应了网络上的节点，而状态转移概率矩阵也可以自然地用网络的邻接矩阵进行表示。

具体的，假设我们考虑一个联通的无向图G，邻接矩阵为[math]A[/math]。假设图上有N个节点，分别表示为1,2,...,N。我们首先可以定义节点[math]\displaystyle{ i\in \{1,2,\cdots,N\} }[/math]到节点[math]\displaystyle{ j\in \{1,2,\cdots,N\} }[/math]的转移概率为[math]\displaystyle{ w_{ij} }[/math]，它满足：

[math]\displaystyle{ w_{ij}=\frac{a_{ij}}{\sum_{j=1}^N a_{ij}} }[/math]

这里，[math]a_{ij}\geq 0[/math]为G的邻接矩阵A的第i行，第j列元素。由于G是连通图，因此[math]\sum_{j=1}^N a_{ij}\neq 0[/math]。根据该定义，[math]w_{ij}[/math]自然满足归一化条件：

[math]\displaystyle{ \sum_{j=1}^Nw_{ij}=1 }[/math]

因此，我们可以直接定义一个马尔科夫链，其状态空间为[math]\{1,2,\cdots,N\}[/math]，从i状态到j状态的转移概率就是[math]w_{ij}[/math]，且对应的转移概率矩阵为：

[math]\displaystyle{ W=\{w_{ij}\}_{N\times N} }[/math]

定义有效信息

对于一般的N个状态的马尔科夫链，其概率转移矩阵为：[math]P[/math]，则其有效信息可以由下式计算(参见有效信息)：

[math]\displaystyle{ \begin{aligned} EI &\equiv I(S_{t+1};S_t|do(S_t\sim U))=D_{KL}[P_i||\bar{P}]\\ &=\underbrace{-\langle H(P_i)\rangle}_{确定性项}+\underbrace{H(\bar{P})}_{非简并性项} \end{aligned} }[/math]

这里，[math]P_i[/math]为P的第i个行向量，[math]\bar{P}=\sum_{i=1}^N P_i/N[/math]为P的所有行向量求平均得到的平均向量。根据上式，EI可以分为两项，刚好对应两种计算下的Shannon信息熵，即[math]-\langle H(P_i)\rangle[/math]，它描述了P的确定性；还有[math]H(\bar{P})[/math]，它刻画了P的非简并性。

下面，我们把这个公式套用到复杂网络上的随机游走子定义的马尔科夫链上：

[math]\displaystyle{ \begin{aligned} {EI} &=\frac{1}{N}\sum_{i=1}^ND_{KL}[W_i||\bar{W}] \\ &= \frac{1}{N}\sum_{i=1}^N\sum_{j=1}^Nw_{ij}\log_2(w_{ij})-\frac{1}{N}\sum_{i=1}^N\sum_{j=1}^Nw_{ij}\log_2(\bar{w_j}) \\ &=\underbrace{-\langle H(W_i)\rangle}_{确定性项}+\underbrace{H(\bar{W})}_{非简并性项} \end{aligned} }[/math]

 

 

 

 

(1)

其中[math]\displaystyle{ W_i }[/math]为W的第i行构成的行向量，也对应了i节点跳出到其它节点的概率，[math]\bar{W}=\sum_{i=1}^N W_i/N[/math]为W的所有行向量求平均得到的平均向量, [math]\displaystyle{ \bar{w_j}=\frac{1}{N}\sum_{i=1}^N w_{ij} }[/math]，表示节点[math]\displaystyle{ j }[/math]入边权重的平均值。 同样，有效信息可以分解为确定性和简并性（参考有效信息）。

这两项分别是：

  1. 确定性为[math]\displaystyle{ -\langle H(W_i)\rangle }[/math]，其中，随机游走子从节点i跳出的不确定性可通过节点跳出概率向量[math]\displaystyle{ W_i }[/math]的香农熵定义，即[math]\displaystyle{ H(W_i) }[/math]，因此整个网络的确定性可通过所有节点香农熵的平均值取负数[math]\displaystyle{ -\langle H(W_i)\rangle }[/math]得到；
  2. 网络的非简并性为：[math]\displaystyle{ H(\bar{W}) }[/math]，它是所有节点跳出概率的平均值的熵。


除此之外，1式还可以用有效信息的原始定义来理解。在初始时刻，我们假设随机子的初始状态分布为：

[math]\displaystyle{ S_0=(1/N,1/N,\cdots,1/N), }[/math]

这相当于游走子会等概率地分布在所有网络节点上，这种初始分布相当于我们对随机游走子的初始分布进行了do干预，把该分布干预为了均匀分布。计算在这个do干预下的t=1时刻和初始时刻两状态分布的互信息，我们同样可以得到1式。

1式表示任意复杂网络G的有效信息的定义式。

粗粒化复杂网络

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。Klein等人[2]利用贪婪算法构建了宏观尺度的网络，发现对于大规模网络其效率很低。Griebenow 等人[3]提出了一种基于谱分解的方法，并应用于偏好依附网络。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。

贪婪算法

  1. 初始化一个队列，随机选择一个节点[math]\displaystyle{ v_i }[/math](没有访问过的), 将[math]\displaystyle{ v_i }[/math]所属的邻域(马尔可夫毯 )[math]\displaystyle{ B_{v_i} }[/math] 中的节点加入队列中
  2. 初始时[math]\displaystyle{ v_{\mu} }[/math]=[math]\displaystyle{ v_i }[/math]
  3. 分别尝试将 [math]\displaystyle{ v_{\mu} }[/math] 与 [math]\displaystyle{ v_j }[/math][math]\displaystyle{ \in }[/math][math]\displaystyle{ B_{v_i} }[/math] 合并：
    1. 如果合并后的网络的EI增加了，就将这两个节点合并组成新的宏观节点[math]\displaystyle{ v_{\mu} }[/math]，将[math]\displaystyle{ v_j }[/math]所属的邻域中的不在队列中的节点加入队列中
    2. EI没增加则继续尝试与队列中的其他节点进行合并，直至队列中的节点都合并过，返回步骤1

时间复杂度：[math]\displaystyle{ O(N^4) }[/math]

谱分解方法

  1. 输入一个网络[math]\displaystyle{ A_m }[/math]，得到其转移矩阵[math]\displaystyle{ T_{A_m} }[/math]，然后进行矩阵的特征值分解，得到特征值[math]\displaystyle{ Λ=\{λ_i\} }[/math]与特征向量[math]\displaystyle{ E=\{e_i\} }[/math]，构建新的[math]\displaystyle{ E’=\{λ_ie_i|λ_i≠0\} }[/math](新的网络节点数量为[math]\displaystyle{ N' }[/math])
  2. 依据[math]\displaystyle{ E' }[/math]计算节点间的距离矩阵[math]\displaystyle{ D_{N'×N'} }[/math]：
    1. 如果节点[math]\displaystyle{ v_i }[/math]和[math]\displaystyle{ v_j }[/math]分别在对方的邻域中(马尔可夫毯)，则使用cosine计算两个节点的相似性作为距离
    2. 否则将两个节点间的距离设为无穷大∞(1000)
  3. 基于距离矩阵[math]\displaystyle{ D_{N'×N'} }[/math]，使用OPTICS算法进行聚类，同一类里的节点进行粗粒化作为一个宏观节点，存在距离超参[math]\displaystyle{ \epsilon }[/math]，需要线性搜索，选择EI最大的参数

时间复杂度：[math]\displaystyle{ O(N^3) }[/math]

梯度下降方法

由于EI是不可微的，所以梯度下降法不能直接适用。

解决方法：针对一个含有[math]\displaystyle{ 𝑛 }[/math]个节点的网络，定义一个分组矩阵[math]\displaystyle{ M\in R^{n×k} }[/math]，其中[math]\displaystyle{ m_{iμ}=Pr⁡(v_i\in v_{\mu}) }[/math]，表示微节点[math]\displaystyle{ v_i }[/math]属于宏观节点[math]\displaystyle{ v_{\mu} }[/math]的概率，然后根据微观网络和分组矩阵构建宏观网络，优化目标是最大化宏观网络的有效信息EI，使用带动量的梯度下降方法优化[math]\displaystyle{ M }[/math]。

时间复杂度：[math]\displaystyle{ O(N^3) }[/math]

困难：

  1. 初始化分组矩阵的选择，多次重复实验会得到不一样的结果
  2. 依赖神经网络的超参，如学习率、迭代次数等

宏节点合并方法

通过上面的网络粗粒化方法可以对节点进行分组，从而可以构建宏观网络。将微观节点合并成宏观节点时，对应宏观网络的转移概率矩阵也要进行相应的处理。通过使用高阶节点显式地对高阶依赖项建模（HOMs）[4]，保证分组后的宏观网络和原始网络具有相同的随机游走动力学。

具体来说，不同的类型的微观节点合并成宏观节点时边权有不同的处理方式，包括四种处理方法：

1）待合并的节点之间没有连边，且输入节点都指向待合并节点，待合并节点都指向相同输出节点时，如图a所示，需要将输入权重相加，输出权重取平均，其中[math]\displaystyle{ S }[/math]表示待合并节点集合， [math]\displaystyle{ \mu }[/math]表示合并完的宏观节点，[math]\displaystyle{ W_i }[/math]表示节点[math]\displaystyle{ i }[/math]的出边权重， [math]\displaystyle{ Ns }[/math]为待合并节点的数量[math]\displaystyle{ (W_{\mu}=\sum_{i \in S}W_i\frac{1}{N_S}) }[/math]；

2）待合并的节点之间没有连边且待合并节点指向多个节点时，如图b所示，需要将输入边权加和，出边的边权按比例加权求和，其中[math]\displaystyle{ w_{ji} }[/math]为节点[math]\displaystyle{ v_i }[/math]的入边权重[math]\displaystyle{ (W_{\mu|j}=\sum_{i \in S}W_i\frac{\sum_{j-\gt i}w_{ji}}{\sum_{j-\gt k\in S}w_{jk}}) }[/math]；

3）当待合并节点间存在连边时，如图c所示，需要计算待合并节点的平稳分布，然后采用方法2的方式计算，其中 [math]\displaystyle{ π_i }[/math]为节点[math]\displaystyle{ v_i }[/math]在网络平稳分布中的概率[math]\displaystyle{ (W_{\mu|\pi}=\sum_{i \in S}W_i\frac{\pi_i}{\sum_{k\in S}\pi_k}) }[/math]；

4）更为复杂的情况，如图d所示，综合考虑方法2和方法3。

网络节点合并方式

检验动力学的一致性

动力学的一致性检验可以进一步验证HOMs方法的有效性，公式如下所示，比较宏微观网络节点在不同时刻的概率分布的KL散度之和。实验发现在不同节点规模以及参数下的偏好依附网络的粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。

在微观网络[math]\displaystyle{ G }[/math]与宏观网络[math]\displaystyle{ G_M }[/math]上随机游走，在未来某个时间[math]\displaystyle{ t }[/math] ， [math]\displaystyle{ G }[/math]上的预期分布为 [math]\displaystyle{ P_m(t) }[/math]， [math]\displaystyle{ G_M }[/math]上的预期分布为 [math]\displaystyle{ P_M(t) }[/math]。将[math]\displaystyle{ P_m(t) }[/math]分布叠加到宏观上[math]\displaystyle{ G_M }[/math]的相同节点上，得到[math]\displaystyle{ P_{M|m}(t) }[/math]分布。用[math]\displaystyle{ P_M(t) }[/math]和[math]\displaystyle{ P_{M|m}(t) }[/math]之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为：

[math]\displaystyle{ inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)] }[/math]

数值结果

2020年Klein等人在一篇论文[2]中分析了随机（ER）、偏好依赖（PA）等人工网络，以及生物、社会、信息和技术4类真实网络的有效信息（EI）。

人工网络

1）对于ER网络，有效信息的大小只依赖连接概率 [math]\displaystyle{ p }[/math]，并且随着网络规模的增大有效信息会收敛到[math]\displaystyle{ -\log_2p }[/math]。在某点之后，ER网络结构不会随着其规模的增加而包含更多的信息，这个相变点近似在网络的平均度 [math]\displaystyle{ \lt k\gt }[/math]=[math]\displaystyle{ \log_2N }[/math] 的位置。随着ER网络连接概率的增大，巨连通集团相变点位置对应出现，如图a所示。

2）对于PA 网络：[math]\displaystyle{ \alpha\lt 1.0 }[/math]时，有效信息的大小随着网络规模的增加而增大；[math]\displaystyle{ \alpha\gt 1.0 }[/math]时，结论相反； [math]\displaystyle{ \alpha=1.0 }[/math]对应的无标度网络则是增长的临界边界，如图b所示。

真实网络

对于真实网络，生物网络因为具有很大的噪声，所以有效信息最低，通过有效的粗粒化能去除这些噪声。相较于其他类型，因果涌现最显著；技术类型网络是更稀疏、非简并的网络，因此，平均效率更高，节点关系更加具体，所有有效信息也最大，如图c、d所示。

实验结果

代码

参考：https://github.com/jkbren/einet

参考文献

  1. ↑ 1.0 1.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. ↑ 2.0 2.1 2.2 2.3 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.

编者推荐

下面是一些链接能够帮助读者更好的了解因果涌现的相关信息：

因果涌现读书会

读书会通过阅读前沿文献，加深我们对因果、涌现等概念的理解；聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。

分享近期发展起来的一些理论与工具，包括因果涌现理论、机器学习驱动的重整化技术，以及自指动力学正在发展一套跨尺度的分析框架等。

涌现现象无非是复杂系统中诸多现象中最神秘莫测的一个，而Erik Hoel提出的“因果涌现”理论为这种跨层次的奇妙涌现现象提供了一种新的可能解释途径。通过跨层次的粗粒化（Coarse-graining, 或称重整化Renormalization）操作，我们便可以在同一个动力学系统上在不同的尺度得到完全不同的动力学，通过本季读书会梳理，我们希望探讨这一新兴领域的前沿进展，衍生更多新的研究课题。

涌现与因果的结合创造了因果涌现的概念。这是一套利用因果性来定量刻画涌现的理论体系，本季读书会通过阅读前沿文献，加深我们对因果、涌现等概念的理解；聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。第二季读书会更加集中在探讨因果科学与因果涌现之间的关系，以及对涌现进行定量刻画，聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。

因果涌现第三季的读书会中，将进一步围绕因果涌现的核心研究问题『因果涌现的定义』以及『因果涌现的辨识』来进行深入的学习和讨论，对 Erik Hoel 提出的 Causal Emergence，Causal Geometry 等因果涌现的核心理论进行深入的探讨和剖析，并且详细梳理其中涉及到的方法论，包括从动力学约简、隐空间动力学学习等其他研究领域中学习和借鉴相关的研究思路，最后探讨因果涌现的应用，包括基于生物网络、脑网络或者涌现探测等问题展开扩展，发掘更多的实际应用场景。

此次读书会将首先对信息论领域进行整体回顾，介绍经典信息指标，希望建立对信息熵的直觉，给后面的内容打基础。第二部分介绍整合信息论的理论框架。第三部分将详细梳理信息分解的理论框架，包括部分信息分解（PID）、延展的PID框架、信息分解计算，以及信息论在脑与复杂系统中的应用。最后介绍整合信息分解（ΦID）与 Rosas 的因果涌现框架。

本季读书会分成两部分，一部分是有关因果涌现理论方面的最新进展，包括信息分解的定量化、动力学可逆性与因果涌现，以及复杂系统的低秩表示理论、本征微观态理论等，第二部分是这些理论在脑科学及其它学科上的应用。

路径推荐

此词条由王志鹏、刘易明编写，张江、王志鹏、刘易明整理和审校。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=复杂网络中的因果涌现&oldid=39398”