更改

因果涌现理论的历史发展可以追溯到古希腊哲学，是在涌现和复杂系统理论的背景下逐渐形成，在古希腊哲学家亚里士多德的《形而上学》中，涌现的概念初现端倪，他认为整体是超越于部分的东西。这种思想在完形心理学中也有所体现，强调“整体大于部分之和”。20世纪40年代，控制论的创始人维纳和冯·诺伊曼通过研究系统及其因果反馈回路，为复杂系统提供了早期的理论基础。1972年，诺贝尔奖得主菲利普·安德森指出在不同层级的复杂系统中，基本物理定律无法完全解释由大量单元组成的系统的新性质和新行为。2013年，Erick Hoel和他的团队首次提出了因果涌现理论，使用有效信息（Effective Information, EI）来量化离散马尔科夫动力学系统的因果性强弱。

因果涌现理论的历史发展可以追溯到古希腊哲学，是在涌现和复杂系统理论的背景下逐渐形成，在古希腊哲学家亚里士多德的《形而上学》中，涌现的概念初现端倪，他认为整体是超越于部分的东西。这种思想在完形心理学中也有所体现，强调“整体大于部分之和”。20世纪40年代，控制论的创始人维纳和冯·诺伊曼通过研究系统及其因果反馈回路，为复杂系统提供了早期的理论基础。1972年，诺贝尔奖得主菲利普·安德森指出在不同层级的复杂系统中，基本物理定律无法完全解释由大量单元组成的系统的新性质和新行为。2013年，Erick Hoel和他的团队首次提出了因果涌现理论，使用有效信息（Effective Information, EI）来量化离散马尔科夫动力学系统的因果性强弱。

==复杂网络节点动力学的定义==

==定义复杂网络节点动力学==

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是[[状态转移矩阵]]TPM，然而对于复杂网络来说，给定一个网络已知不具有动力学，需要人为定义复杂网络节点的动力学，可以借助随机游走子定义网络中的马尔可夫链，从而假定网络中的每个节点具有[[随机游走动力学]]。

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是[[状态转移矩阵]]TPM，然而对于复杂网络来说，给定一个网络已知不具有动力学，需要人为定义复杂网络节点的动力学，可以借助随机游走子定义网络中的马尔可夫链，从而假定网络中的每个节点具有[[随机游走动力学]]。

==有效信息的定义==  

==定义有效信息==  

将随机游走子放在节点上，等价于对节点做干预<math>do(·) </math>，基于随机游走概率可以定义节点的转移概率矩阵，建立了有效信息与网络连通性的联系，将网络节点类比系统状态构建网络动力学的有效信息。

将随机游走子放在节点上，等价于对节点做干预<math>do(·) </math>，基于随机游走概率可以定义节点的转移概率矩阵，建立了有效信息与网络连通性的联系，将网络节点类比系统状态构建网络动力学的有效信息。

2）基于网络的出边权重分布计算，<math>H(<W_i^{out}>)</math>反映了确定性如何在网络中分布。通过这2项就可得到复杂网络中的有效信息定义，<math>{J}=\frac{1}{N}\sum_{i=1}^ND_{KL}[W_i^{out}||<W_i^{out}>]=\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(W_j)=H(<W_i^{out}>)-<H(W_i^{out})></math>。 同样进一步，有效信息可以分解为确定性和简并性。

2）基于网络的出边权重分布计算，<math>H(<W_i^{out}>)</math>反映了确定性如何在网络中分布。通过这2项就可得到复杂网络中的有效信息定义，<math>{J}=\frac{1}{N}\sum_{i=1}^ND_{KL}[W_i^{out}||<W_i^{out}>]=\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(W_j)=H(<W_i^{out}>)-<H(W_i^{out})></math>。 同样进一步，有效信息可以分解为确定性和简并性。

==网络中的粗粒化==  

==粗粒化复杂网络==  

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。

===贪婪算法===

===贪婪算法===

# 依赖神经网络的超参，如学习率、迭代次数等

# 依赖神经网络的超参，如学习率、迭代次数等

通过上面的网络粗粒化方法可以对节点进行分组，从而可以构建宏观网络。将微观节点合并成宏观节点时，对应宏观网络的转移概率矩阵也要进行相应的处理。通过使用高阶节点显式地对高阶依赖项建模（[[HOMs]]），保证分组后的宏观网络和原始网络具有相同的随机游走动力学。具体来说，不同的类型的微观节点合并成宏观节点时边权有不同的处理方式，包括四种处理方法：1）待合并的节点之间没有连边，且输入节点都指向待合并节点，待合并节点都指向相同输出节点时，如图b所示，需要将输入权重相加，输出权重取平均<math>(W_{\mu}^{out}=\sum_{i \in S}W_i^{out}\frac{1}{N_S})</math>；2）待合并的节点之间没有连边且待合并节点指向多个节点时，如图c所示，需要将输入边权加和，出边的边权按比例加权求和<math>(W_{\mu|j}^{out}=\sum_{i \in S}W_i^{out}\frac{\sum_{j->i}w_{ji}}{\sum_{j->k\in S}w_{jk}})</math>；3）当待合并节点间存在连边时，如图d所示，需要计算待合并节点的平稳分布，然后采用方法2的方式计算<math>(W_{\mu|\pi}^{out}=\sum_{i \in S}W_i^{out}\frac{\pi_i}{\sum_{k\in S}\pi_k})</math>；4）更为复杂的情况，如图e所示，综合考虑方法2和方法3。

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

 

 

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

 

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

 

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

 

[[文件:Coarse.png|居中|800x500像素|边权合并方式|缩略图]]

[[文件:Coarse.png|居中|800x500像素|边权合并方式|缩略图]]

==动力学一致性检验==  

==检验网络的动力学一致性==  

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

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

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

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

==实验分析==

==实验分析==

该工作<ref name=":0" />在随机（ER）、偏好依赖（PA）等人工网络，以及 4 类真实网络中做了试验。 对于ER网络，有效信息的大小只依赖连接概率 <math>p </math>，并且随着网络规模的增大会收敛到<math>-log_2p </math>。在某点之后，随机网络结构不会随着其规模的增加而包含更多的信息，这个相变点近似在网络的平均度 <math><k> </math>=<math>log_2N </math> 的位置。随着ER网络连接概率的增大，巨连通集团相变点位置对应出现，如图a所示。对于PA 网络：<math>\alpha<1.0 </math>时，有效信息的大小随着网络规模的增加而增大；<math>\alpha>1.0 </math>时，结论相反； <math>\alpha=1.0 </math>对应的无标度网络则是增长的临界边界，如图b所示。对于真实网络，生物网络因为具有很大的噪声，所以有效信息最低，通过有效的粗粒化能去除这些噪声。相较于其他类型，因果涌现最显著；技术类型网络是更稀疏、非退化的网络，因此，平均效率更高，节点关系更加具体，所有有效信息也最多，如图c、d所示。此外，还利用贪婪算法构建了宏观尺度的网络，对于大规模网络其效率很低。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>提出了一种基于谱聚类的方法识别偏好依附网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱聚类算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著。

该工作<ref name=":0" />在随机（ER）、偏好依赖（PA）等人工网络，以及 4 类真实网络中做了试验。  

 

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

 

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

 

 

此外，还利用贪婪算法构建了宏观尺度的网络，对于大规模网络其效率很低。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>提出了一种基于谱聚类的方法识别偏好依附网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱聚类算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著。

[[文件:结果.png|居中|700x600像素|实验结果|缩略图]]

[[文件:结果.png|居中|700x600像素|实验结果|缩略图]]