基于可逆性的因果涌现理论

2024-09-24T03:27:18Z

GongMingkang：

2024-09-13T02:34:44Z

GongMingkang：

[[基于可逆性的因果涌现理论]]是一种量化[[因果涌现 Causal Emergence|因果涌现]]的新框架，该方法基于奇异值分解和动力学可逆性的概念，提出了近似动力学可逆性：<math>
\Gamma_{\alpha}
</math>，用于量化因果涌现的强度。经过理论推导和数值实验证明，在对因果涌现的判断和量化上，该理论与Erik Hoel等人提出的基于[[有效信息]](EI)的因果涌现理论具有相同的效果，且<math>
\Gamma_{\alpha}
</math>和EI在多个方面存在联系。此外，该理论还提出了基于[[奇异值分解]]（SVD）的新粗粒化策略，并通过实验证明了该方法的有效性。

=简介=
2024年，[[张江]]等人<ref name=":22">Zhang J, Tao R, Yuan B. Dynamical Reversibility and A New Theory of Causal Emergence. arXiv preprint arXiv:2402.15054. 2024 Feb 23.</ref>基于[[奇异值分解]]，提出了一套新的因果涌现理论。该理论的核心思想是指出所谓的因果涌现其实等价于动力学可逆性的涌现。给定一个系统的马尔科夫转移矩阵，通过对它进行奇异值分解，将奇异值的<math>\alpha</math>次方的和定义为马尔科夫动力学的[[可逆性]]度量（<math>\Gamma_{\alpha}\equiv \sum_{i=1}^N\sigma_i^{\alpha}</math>），这里[math]\sigma_i[/math]为奇异值。该指标与[[有效信息]]具有高度的相关性，也可以用于刻画动力学的因果效应强度。根据奇异值的谱，该方法可以在不显式定义粗粒化方案的条件下，直接定义所谓'''清晰涌现'''（clear emergence）和'''模糊涌现'''（vague emergence）的概念。

=基本概念=
下面详细介绍该理论的基本概念，分别是动力学可逆性、近似动力学可逆性、清晰因果涌现和模糊因果涌现。
==动力学可逆性==
对于给定的马尔可夫链<math>
\chi
</math>和对应的转移概率矩阵(TPM) P ，如果P同时满足：1. P是可逆矩阵，即存在矩阵<math>
P^{-1}
</math>，使得<math>
PP^{-1}=I
</math>； 2. <math>
P^{-1}
</math>也是另一个马尔可夫链<math>
\chi^{-1}
</math>的有效TPM，则<math>
\chi
</math>和P可以称为'''严格动力学可逆的'''。

'''定理1：'''对于一个给定的马尔科夫链<math>
\chi
</math>和对应的TPM P，当且仅当P是置换矩阵的时候，P是严格动力学可逆的。

纯粹的置换矩阵在所有可能的TPM中非常稀少，所以大多数的TPM并不是严格动力学可逆的。因此，需要一个指标来刻画任意一个TPM接近动力学可逆的程度。

考虑P的秩r，当且仅当r<N（N为矩阵的维数）的时候，P是不可逆的；且P越退化对应着越小的r。然而，非退化（满秩）的矩阵P并不总是动力学可逆的，因为：1. 尽管<math>
P^{-1}
</math>存在，<math>
P^{-1}
</math>并不一定是满足归一化条件（P的第i行向量<math>
P_{i}
</math>的第一范数应该为1）的合法TPM。2. 如前所述，若P满足动力学可逆性，则P必为置换矩阵。

所有置换矩阵的行向量都是[[one-hot向量|独热向量（one-hot vector)]]（即只有一个元素是1，其余元素均为零的向量）。这一特性可以被矩阵P的弗罗贝尼乌斯范数（Frobenius norm）刻画。事实上，当且仅当P的行向量是独热向量的时候，矩阵P的弗罗贝尼乌斯范数取最大值。因此，我们可以借由矩阵P的秩r和矩阵的弗罗贝尼乌斯范数共同定义P的近似动力学可逆性。

首先，矩阵的秩可以被写作：
<blockquote>
<math>
\begin{aligned}
r=\sum_{i=1}^{N}\sigma_{i}^{0}
\end{aligned}
</math>
</blockquote>
其中<math>
\sigma_{i}
</math>是矩阵P的第i个奇异值。

紧接着，矩阵的弗罗贝尼乌斯范数可以被写作：
<blockquote>
<math>\begin{aligned}
{||P||}_{F}^{2}=\sum_{i=1}^{N}\sigma_{i}^{2}
\end{aligned}
</math>
</blockquote>
这也是所有奇异值的平方和。可以看出矩阵的秩和弗罗贝尼乌斯范数都与奇异值相联系。

==近似动力学可逆性==
假设马尔科夫链的TPM为P，奇异值为<math>
(\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0)
</math>，那么矩阵P的<math>
\alpha
</math>阶近似动力学可逆性定义为：
<blockquote>
<math>\begin{aligned}
\Gamma_{\alpha}=\sum_{i=1}^{N}\sigma_{i}^{\alpha}\end{aligned}
</math>
</blockquote>
其中<math>
\alpha\in(0,2)
</math>是参数。

实际上，当<math>
\alpha\ge1
</math>时，<math>
\Gamma_{\alpha}
</math>是P的沙滕范数（Schatten norm）；当<math>
0<\alpha<1
</math>时，<math>
\Gamma_{\alpha}
</math>是P的准范数（quasinorm）<ref>Schatten norm from Wikipedia. https://en.wikipedia.org/wiki/Schatten norm</ref><ref>Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review 52(3), 471–501 (2010)</ref><ref>Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing 67(20), 52395269 (2019)</ref><ref name="Cui">Cui, S., Wang, S., Zhuo, J., Li, L., Huang, Q., Tian, Q.: Towards discriminability and diversity: Batch nuclear-norm maximization under label insufficient situations. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3941–3950 (2020)</ref>。

使用这个定义来刻画近似动力学可逆性是合理的，因为完全动力学可逆性可以通过最大化<math>
\Gamma_{\alpha}
</math>来得到。

'''定理2：'''对于任意<math>
\alpha\in(0,2)
</math>，<math>
\Gamma_{\alpha}
</math>的最大值是N，当且仅当P是置换矩阵的时候能取到该最大值。更进一步来说，可以证明，<math>
\Gamma_{\alpha}
</math>的下界可以由<math>
{||P||}_{F}^{\alpha}
</math>确定<ref name="Zhangjiang">Zhang, Jiang, Ruyi Tao, and Bing Yuan. "Dynamical Reversibility and A New Theory of Causal Emergence." arXiv preprint arXiv:2402.15054 (2024).</ref>。

===确定性和简并性===
通过调整参数<math>
\alpha\in(0,2)
</math>，可以使更好地反映P的确定性或者简并性。当<math>
\alpha\to0,\Gamma_{\alpha}
</math>收敛到P的秩，这类似于EI定义中的非简并项，因为随着P越来越退化，r越来越小。然而，定义不允许<math>
\alpha
</math>精确为零，因为rank(P)不是P的连续函数，而且最大化秩不等于置换矩阵。同样，当<math>
\Gamma_{\alpha}\to2
</math>时，<math>
\Gamma_{\alpha}
</math>收敛到<math>
{||P||}_{F}^{2}
</math>，但是定义不允许<math>
\alpha
</math>取2，因为<math>
\Gamma_{\alpha=2}
</math>的最大化并不意味着P是可逆的。<math>
{||P||}_{F}
</math>与EI定义中的确定性项具有可比性，因为当P具有越来越多的独热向量，P中的最大转移概率也会变得更大，意味着动力学变得更加可逆。

在实践中总是取<math>
\alpha=1
</math>来平衡<math>
\Gamma
</math>测量确定性和简并性的倾向，<math>
\Gamma_{\alpha=1}
</math>被称为核范数<ref name="Cui" /><ref>Fazel, M.: Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford University (2002)</ref>。为简便，下文中将<math>
\Gamma_{\alpha=1}
</math>记作<math>
\Gamma
</math>。

===归一化===
<math>
\Gamma_{\alpha}
</math>受矩阵的大小影响，所以我们需要进行归一化，从而刻画与大小无关的近似动力学可逆性，这样可以更方便地在不同大小的马尔科夫链之间进行比较：
<blockquote>
<math>\begin{aligned}
\gamma_{\alpha}=\frac{\Gamma_{\alpha}}{N}\end{aligned}
</math>
</blockquote>
容易证明，<math>
\gamma_{\alpha}
</math>总是小于1。

一方面，EI 表征了马尔可夫链的因果效应强度；另一方面，<math>
\Gamma_{\alpha}
</math>可以定量地捕捉马尔可夫链的近似动态可逆性。基于可逆性的因果涌现理论认为，因果关系和可逆性之间有着深刻的联系。首先，如下定理所述，EI 和<math>\log\Gamma_{\alpha}</math> 有相同的最小值和最大值。

'''定理3：'''对于任意 TPM P 和 <math>
\alpha\in(0,2)
</math>，<math>
\Gamma_{\alpha}
</math>的对数和EI都有相同的最小值0和一个共同的最小值<math>
P=\frac{1}{N}I_{N\times{N}}
</math>。它们还有相同的最大值<math>\log{N}</math>，最大值点对应于P是一个置换矩阵。

因此当P是可逆的（置换矩阵）时，<math>
\log{\Gamma_{\alpha}}
</math>和EI可以达到最大值<math>
\log{N}
</math>。当<math>
P_{i}=\frac{I}{N},\forall{i}\in[1,N]
</math>，它们也可以达到最小值0。然而，我们可以证明<math>
\frac{I}{N}
</math>并不是EI的唯一最小点,对于任何满足<math>P_{i}=P_{j},\forall{i}\in{[1,N]}</math>的TPM都能使EI=0.其次EI的上限和下限都是<math>\log{\Gamma_{\alpha}}</math>的线性项。

'''定理4：'''对于任何TPM P，其有效信息EI的上限为<math>\frac{2}{\alpha}\log{\Gamma_{\alpha}}</math>，下限为<math>
\log{\Gamma_{\alpha}}-\log{N}</math>.

因此，有如下不等式：
<blockquote>
<math>
\begin{aligned}
\log{\Gamma_{\alpha}}-\log{N}\le{EI}\le\frac{2}{\alpha}\log{\Gamma_{\alpha}}
\end{aligned}
</math></blockquote>
实际上，EI有一个更严格的上限，<math>EI\le\log{\Gamma_{\alpha}}</math>,这个上限是由数值实验的结果确定的。我们发现在许多例子中，EI和<math>\log\Gamma_{\alpha}</math>,因此，基于可逆性的因果涌现理论主张：
<blockquote>
<math>\begin{aligned}
EI\sim\log\Gamma_{\alpha}.
\end{aligned}
</math>
</blockquote>
==清晰因果涌现==
对于具有TPM P的给定马尔可夫链<math>
\chi
</math>，如果<math>r≡rank(P)<N</math>，则该系统中会出现明显的因果涌现。且因果涌现的程度为：
<blockquote>
<math>\begin{aligned}
\Delta\Gamma_{\alpha}=\Gamma_{\alpha}\cdot(\frac{1}{r}-\frac{1}{N})
\end{aligned}
</math>
</blockquote>
==模糊因果涌现==
对于具有TPM P的给定马尔可夫链<math>
\chi
</math>，假设其奇异值为<math>
(\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0)
</math>。对于给定实值<math>
\epsilon\in[0,\epsilon_{1}]
</math>，如果存在整数<math>
i\in[1, N)
</math>，使得<math>
\sigma_{i}>\epsilon
</math>，则系统中出现了模糊因果涌现，其模糊程度为<math>
\epsilon
</math>。而因果涌现的程度为：
<blockquote>
<math>\begin{aligned}
\Delta\Gamma_{\alpha}(\epsilon)=\frac{\sum_{i=1}^{r_{\epsilon}}\sigma_{i}^{\alpha}}{r_{\epsilon}}-\frac{\sum_{i=1}^{N}\sigma_{i}^{\alpha}}{N},
\end{aligned}
</math>
</blockquote>
其中<math>
r_{\epsilon}=max\{ i| \sigma_{i} > \epsilon\}
</math>

这些定义与任何粗粒化方法无关。因此，它代表了马尔可夫动力学的内在客观属性。因此，清晰和模糊因果涌现的程度都可以客观地量化。

当<math>
\epsilon=0
</math>时，清晰因果涌现是模糊因果涌现的特例，特别是当奇异值可以分析求解时，它具有理论价值。此外，对因果涌现发生的判断与<math>
\alpha
</math>无关，因为它只与秩有关。因此，清晰因果涌现的概念仅由P决定，是无参数的。

在实际应用中，必须给出阈值<math>
\epsilon
</math>，因为奇异值可能无限趋近于0，但P是全秩的。可以根据奇异值频谱中的明显截止点来选择<math>
\epsilon
</math>。若<math>
\epsilon
</math>非常小（比如<math>
\epsilon<{10}^{-10}
</math>），我们也可以说因果涌现大致发生。

对于任意<math>
\epsilon\ge{0},\Delta\Gamma_{\alpha}(\epsilon)\in[0,N-1].
</math>只有当<math>\Delta\Gamma_{\alpha}(\epsilon)>0
</math>时，才会出现因果涌现。
=与有效信息（EI）的比较=

==相似性==
根据前文，EI的上界和下界分别是<math>\log{\Gamma_{\alpha}}
</math>的线性项。由此还可以推测两者具有近似关系：<math>
EI\sim\log{\Gamma_{\alpha}}
</math>。下面通过数值模拟说明这一点。

如下图所示，在由三种不同方法生成的各种归一化的TPM 上比较了<math>
\log{\Gamma_{\alpha}}
</math>和 EI：1）软化置换矩阵；2）软化退化矩阵；3）完全随机矩阵。图(a)、(b)和(c)表明，在这些例子中都观察到了正相关性，并且在N ≫ 1 时，<math>
EI\sim\log{\Gamma_{\alpha}}.
</math>的近似关系得到了证实。在(a) 和 (b) 中可以明显观察到这种关系，但在(b) 中，由于覆盖了有限的<math>
\Gamma
</math>值区域，这种关系退化为近似线性关系。

图(a)和(b)中用红色虚线表示了 EI 的上下限。不过，在图(c）中，由于所有点都集中在一个小区域内，因此看不到理论边界线。根据经验，图中灰色断线所示的对数<math>\log{\Gamma_{\alpha}}
</math>的EI上限更为严格。因此可以推测 <math>EI\le\log{\Gamma_{\alpha}}
</math>这一新关系是成立的，但其严密性有待证明。

[[文件:20240101.png|替代=|1029x1029像素]]

文献中作者还在大小为N=2 的最简单参数化TPM中得到了EI和<math>
\Gamma
</math>的解析解，并展示了EI和<math>
\Gamma
</math>与参数p和q的关系。下图(a)和(b)之间的差异显而易见：1）当<math>
p\approx 1-q
</math>时，<math>\Gamma
</math>有一个峰值，但EI没有；2）观察到EI ≈ 0时的区域更宽，而<math>\Gamma\approx 1
</math>时的区域要小得多；3）观察到<math>\Gamma
</math>有一个从0到最大N=2的渐进过渡，但EI没有。
因此，我们得出结论，EI和<math>\Gamma
</math>在各种TPM上高度相关。

[[文件:202401012.png|替代=|603x603像素]]

==不同==
首先，EI 通过KL散度来量化每个行向量与P的平均行向量之间的差异，衡量的是行向量之间的相似性。相反，<math>
\Gamma_{\alpha}
</math>评估的是动力学可逆性，特别是当<math>
\alpha
<nowiki></math>接近 0 时，这与行向量之间的线性相互依赖性相关。虽然行向量的线性相互依赖性表明它们的相似性——这意味着两个相同的行向量是线性相关的，但反之则不一定成立。因此，<math>
\Gamma_{\alpha}
</math>不仅捕获了行向量之间的相似性，而且还捕获了P与动态可逆矩阵的接近度。相比之下，EI无法完成这个任务。

可以通过以下数值实验来验证这一点：可以通过将线性相关行向量与线性独立行向量混合来创建TPM，其中独立向量的数量或等级是受控参数。首先，生成r个独立的独热向量，然后软化这些行向量，软化程度由<math>
\sigma</math>确定。随后，通过将这些软化的独热向量与随机选择的线性系数线性组合来创建额外的行向量。然后量化<math>
\Gamma</math>和 EI 之间的差异，结果如下图所示。

[[文件:20202021.png|替代=|480x480像素]]

很明显，对于较小的r值，随着<math>
\sigma</math>的增加，<math>
\log{\Gamma}
</math>和 EI 之间的差异会减小，因为 P 的线性依赖性随着向量变得更加明显而增强。这强调了线性相关性并不等于行向量之间的相似性。然而，随着独立行向量数量的增加，如果<math>
\sigma
</math>保持很小，P会收敛到置换矩阵。因此，EI 和<math>
\log{\Gamma}
</math>都达到相同的最大值。这解释了为什么当r很大时会出现轻微的颠簸。

其次，即使在所有行向量相同的情况下，EI 和<math>
\Gamma_{\alpha}
</math>之间也存在显着区别，导致 EI= 0 而<math>\Gamma_{\alpha}= ||\overline{P}||^{\alpha}\cdot N^{\alpha /2}
</math>，而这是一个可以随<math>
||\overline{P}||
</math>变化的量（参见引理 4，附录 A.2）。这种差异意味着，与 EI 不同，<math>
\Gamma_{\alpha}
</math>可以提供有关行向量的更全面的见解，超越其与平均行向量的相似性。
=基于SVD分解的新粗粒化策略=
虽然无需粗粒化也能定义和量化清晰或模糊因果涌现，但需要对原始系统进行更简单的粗粒化描述，以便与 EI 得出的结果进行比较。因此，该理论提供了一种基于奇异值分解的粗粒度方法，以获得宏观层面的简化TPM。其基本思想是将 P 中的行向量 <math>
P_{i},\forall i \in [1,N]
</math>投影到<math>
P\cdot P^{T}
</math>的特征向量张成的子空间上，从而保留P的主要信息，并保持<math>
\Gamma
</math>不变。
==方法==
该粗粒化方法包括五个步骤：

1) 对TPM进行SVD分解；

2)选择一个<math>
\epsilon
</math>作为阈值来切断奇异值谱，并得到<math>r_{\epsilon}
</math>作为保留状态的个数；

3)通过计算<math>
P\cdot V_{N\times r_{\epsilon}}
</math>对P中的所有Pi进行降维，其中<math>
V_{N\times r_{\epsilon}}
</math>由<math>
P\cdot P^{T}
</math>的前<math>r_{\epsilon}
</math>特征向量构成；

4) 将<math>
P\cdot V_{N\times r_{\epsilon}}
</math>中的所有行向量聚类为<math>r_{\epsilon}
</math>组，得到投影矩阵<math>
\Phi</math>；

5) 利用<math>
\Phi</math>和P得到新的TPM，使总静态通量保持不变。

=测试量化因果涌现的效果=
==布尔网络==
下面基于Hoel等人的论文<ref name="Hoel2013">Hoel, E.P., Albantakis, L., Tononi, G.: Quantifying causal emergence shows that macro can beat micro. Proceedings of the National Academy of Sciences of the United States of America 110(49), 19790–19795 (2013) https://doi.org/10.1073/ pnas.1314922110</ref><ref name="Hoel2017">Hoel, E.P.: When the map is better than the territory. Entropy 19(5) (2017) https://doi.org/10.3390/e19050188</ref>中提出的几种布尔网络马尔可夫动力学来测试清晰和模糊因果涌现的定义。

下图(a)-(i)分别显示了从具有相同节点机制的相同布尔网络模型生成的用于因果涌现和模糊因果涌现的TPM的两个示例。图(d)中的TPM直接源自图(a)和(b)中的布尔网络及其节点机制。它们的奇异值谱分别如图(e)和(h)所示。(d)中的第一个例子只有4个非零奇异值(图(e))，因此，出现明显的因果涌现，且因果涌现的程度为<math>
\Delta\Gamma=0.75
</math>。因果涌现的判断与参考文献<ref name="Hoel2013" />相同。

图(g)中的TPM可以显示出模糊的因果涌现，这是在(d)中的TPM上添加强度为（std = 0.03）的随机高斯噪声后得到的。因此，奇异频谱如图(h) 所示。我们选择<math>
\epsilon=0.2
</math>作为阈值，这样就只剩下4个大的奇异值。因果涌现程度为<math>
\Delta\Gamma(0.2)=0.69
</math>。<math>
\epsilon
</math>值是根据图(h)中的奇异值频谱选择的，在图(h)中可以观察到指数为3和<math>
\epsilon=0.2
</math>时有一个明显的分界点。

[[文件:截屏2024-08-27_14.58.17.png|替代=|740x740像素]]

下图显示了另一个更复杂的布尔网络模型的明显因果涌现例子，该模型来自参考文献<ref name="Hoel2013" />，其中具有相同节点机制的6个节点可归类为3个超级节点，以显示因果涌现。原始布尔网络模型的相应TPM如图(c)所示。奇异值频谱如图(d）所示，其中有8个非零值。这个清晰因果涌现的程度为<math>
\Delta\Gamma=2.23
</math>。对因果涌现的判断与<ref name="Hoel2013" />相同。

[[文件:截屏2024-08-31_20.54.36.png|替代=|702x702像素]]

==复杂网络==
对因果涌现的量化可应用于复杂网络，如下图所示。图（a)-(c）显示了由随机块模型（SBM）生成的具有三组参数（内部或内部连接概率）的复杂网络的模糊因果涌现例子。TPM是通过对网络的邻接矩阵按每个节点的度进行归一化得到的。图(a)显示了一个有 100 个节点和 5 个区块（社区）的示例网络，图(b)显示了其奇异值频谱，在与区块数相同的横坐标上可以观察到一个明显的分界点<math>
(\epsilon=0.3,r_{\epsilon}=5)
</math>。可以确定，在这个网络模型中出现了模糊的因果涌现，程度为<math>
\Delta\Gamma(0.3)=0.56
</math>。同图中还显示了两个由SBM生成的网络光谱，它们的大小和块数相同，但参数不同。

[[文件:截屏2024-08-31_21.01.3211.png|替代=|931x931像素]]

==元胞自动机==
如下图所示，关于清晰因果涌现的定义可应用于元胞自动机，以发现其局部涌现结构。在这个例子里刻画了元胞自动机（编号40的基本一维元胞自动机）局部TPM的清晰因果涌现。局部TPM 由包括每个单元及其两个相邻单元的局部窗口获得。图(b) 显示了这些局部 TPM 的奇异值的可能频谱，在这些频谱中可能出现也可能不出现清晰因果涌现。图(c)用红点标记显示了所有单元和时间步长的清晰因果涌现分布（<math>
\Delta\Gamma
</math>）。

[[文件:截屏2024-08-30_10.05.1111.png|替代=|935x935像素]]

=参考文献=
<references />