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

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
GongMingkang讨论 | 贡献2024年8月11日 (日) 18:28的版本
跳到导航 跳到搜索

基于可逆性的因果涌现理论是一种量化因果涌现强度的新框架,该方法基于奇异值分解和近似动力学可逆性的概念,与基于有效信息(EI)的因果涌现理论不同。

理论

下面将定义马尔科夫链上的动力学可逆性,并提出了一个量化指标:近似动力学可逆性。来衡量任意马尔可夫链对动力学可逆性的接近程度。

定义动力学可逆性

对于给定的马尔可夫链[math]\displaystyle{ \chi }[/math]和对应的转移概率矩阵(TPM) P ,如果P同时满足:1. P是可逆矩阵,即存在矩阵[math]\displaystyle{ P^{-1} }[/math],使得[math]\displaystyle{ PP^{-1}=I }[/math]; 2. [math]\displaystyle{ P^{-1} }[/math]也是另一个马尔可夫链[math]\displaystyle{ \chi^{-1} }[/math]的有效TPM,则[math]\displaystyle{ \chi }[/math]和P 可以称为动力学可逆的。

定理1:对于一个给定的马尔科夫链[math]\displaystyle{ \chi }[/math]和对应的TPM P,当且仅当P是置换矩阵的时候,P是严格动力学可逆的。


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

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

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

首先,矩阵的秩可以被写作:

[math]\displaystyle{ r=\sum_{i=1}^{N}\sigma_{i}^{0} }[/math]

其中[math]\displaystyle{ \sigma_{i} }[/math]是矩阵P的第i个奇异值。

紧接着,矩阵的弗罗贝尼乌斯范数可以被写作:

[math]\displaystyle{ {||P||}_{F}^{2}=\sum_{i=1}^{N}\sigma_{i}^{2} }[/math]

这也是所有奇异值的平方和。可以看出矩阵的秩和弗罗贝尼乌斯范数都与奇异值相联系。

定义近似动力学可逆性

下面定义矩阵P的近似动力学可逆性:

假设马尔科夫链的概率转移矩阵为P,奇异值为[math]\displaystyle{ (\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0) }[/math],那么矩阵P的[math]\displaystyle{ \alpha }[/math]阶近似动力学可逆性定义为:

[math]\displaystyle{ \Gamma_{\alpha}=\sum_{i=1}^{N}\sigma_{i}^{\alpha} }[/math]

其中[math]\displaystyle{ \alpha\in(0,2) }[/math]是参数。

实际上,当[math]\displaystyle{ \alpha\ge1 }[/math]时,[math]\displaystyle{ \Gamma_{\alpha} }[/math]是P的沙滕范数(Schatten norm);当[math]\displaystyle{ 0\lt \alpha\lt 1 }[/math]时,[math]\displaystyle{ \Gamma_{\alpha} }[/math]是P的准范数(quasinorm)。

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

定理2:对于任意[math]\displaystyle{ \alpha\in(0,2) }[/math][math]\displaystyle{ \Gamma_{\alpha} }[/math]的最大值是N,当且仅当P是置换矩阵的时候能取到该最大值.

证明见附录A.2.2 更进一步来说,可以证明,[math]\displaystyle{ \Gamma_{\alpha} }[/math]的下界可以由[math]\displaystyle{ {||P||}_{F}^{\alpha} }[/math]确定。

决定性和简并性

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

在实践中,我们总是取alpha=1 来平衡gama测量确定性和简并性的倾向,gama被称为核规范。 考虑到alpha=1的重要性,我们将主要展示alpha=1 的结果,在下文中,我们将gama1基座gama。

归一化及例子

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

[math]\displaystyle{ \Gamma_{\alpha} }[/math]和EI的联系

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

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

证明见附录A.3

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

定理4:对于任何TPM P,其有效信息EI的上限为[math]\displaystyle{ \frac{2}{\alpha}\log{\Gamma_{\alpha}} }[/math],下限为[math]\displaystyle{ \log{\Gamma_{\alpha}}-\log{N} }[/math].

证明见附录A.3.

因此,我们有如下不等式:

[math]\displaystyle{ \log{\Gamma_{\alpha}}-\log{N}\le{EI}\le\frac{2}{\alpha}\log{\Gamma_{\alpha}} }[/math]

实际上,EI有一个更严格的上限,[math]\displaystyle{ EI\le\log{\Gamma_{\alpha}} }[/math],这个上限是由数值实验的结果确定的。我们发现在许多例子中,EI和[math]\displaystyle{ \log\Gamma_{\alpha} }[/math],因此,基于可逆性的因果涌现理论主张:

[math]\displaystyle{ EI\sim\log\Gamma_{\alpha}. }[/math]

因果涌现的新定义

定义因果涌现强度

对于具有TPM P的给定马尔可夫链[math]\displaystyle{ \chi }[/math],如果[math]\displaystyle{ r≡rank(P)\lt N }[/math],则该系统中会出现明显的因果涌现。且因果涌现的程度为:

[math]\displaystyle{ \Delta\Gamma_{\alpha}=\Gamma_{\alpha}\dot(\frac{1}{r}-\frac{1}{N}) }[/math]

定义模糊因果涌现

对于具有TPM P的给定马尔可夫链[math]\displaystyle{ \chi }[/math],假设其奇异值为[math]\displaystyle{ (\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0) }[/math]。对于给定实值[math]\displaystyle{ \epsilon\in[0,\epsilon_{1}] }[/math],如果存在整数[math]\displaystyle{ i\in[1, N) }[/math],使得[math]\displaystyle{ \sigma_{i}\gt \epsilon }[/math],则系统中出现了模糊因果涌现,其模糊程度为[math]\displaystyle{ \epsilon }[/math]。而因果涌现的程度为:

[math]\displaystyle{ \Delta\Gamma_{\alpha}(\epsilon)=\frac{\sum_{i=1}^{r_{\epsilon}}\sigma_{i}^{\alpha}}{r_{\epsilon}}-\frac{\sum_{i=1}^{N}\sigma_{i}^{\alpha}}{N}, }[/math] 其中[math]\displaystyle{ r_{\epsilon}=max{i|\sigma_{i}\gt \epsilon} }[/math]

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


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

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

对于任意[math]\displaystyle{ \epsilon\ge{0},\Delta\Gamma_{\alpha}(\epsilon)\in[0,N-1]. }[/math]只有当[math]\displaystyle{ \Delta\Gamma_{\alpha}(\epsilon)\gt 0 }[/math]时,才会出现因果涌现。命题和证明见附录A.3.1。


EI和[math]\displaystyle{ \Gamma }[/math]的比较

在2.3节中,我们推导出Ei的上界和下界分别是[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]的线性项,并推测了两者的近似关系:[math]\displaystyle{ EI\sim\log{\Gamma_{\alpha}} }[/math]。接下来我们将通过数值模拟证明这一点。

我们在由三种不同方法生成的各种归一化TPM 上比较了[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]和 EI:1)软化置换矩阵;2)软化退化矩阵;3)完全随机矩阵。这些生成模型的详情见附录 B。结果如图2 所示。如图2(a)、(b)和(c)所示,在所有这些例子中都观察到了正相关性,并且在N ≫ 1 时,[math]\displaystyle{ EI\sim\log{\Gamma_{\alpha}}. }[/math]的近似关系得到了证实。在图 2(a) 和 (b) 中可以明显观察到这种关系,但在图 2(b) 中,由于覆盖了有限的[math]\displaystyle{ \Gamma }[/math]值区域,这种关系退化为近似线性关系。关于不同α的更多结果,请参阅附录B.1节。

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

我们还在大小为N=2 的最简单参数化TPM中得到了EI和gama的解析解,并展示了EI和gama与参数p和q的关系。图 2(c)和(d)之间的差异显而易见:1)当[math]\displaystyle{ p\approx 1-q }[/math]时,[math]\displaystyle{ \Gamma }[/math]有一个峰值,但EI没有;2)观察到EI ≈ 0时的区域更宽,而[math]\displaystyle{ \Gamma\approx 1 }[/math]时的区域要小得多;3)观察到[math]\displaystyle{ \Gamma }[/math]有一个从0到最大N=2的渐进过渡,但EI没有。

相似性

不同

量化因果涌现

基于SVD分解的粗粒化策略