275
个编辑
更改
跳到导航
跳到搜索
第41行：
第41行： − + − − <math> − \frac{K\left(s^{L}\right)}{L}\underset{L\to\infty}{\operatorname*{\operatorname*{\operatorname*{\rightarrow}}}}h_{\mu} , − </math> − − 这里，[[香农熵率]]定义为： − − <math> − h_\mu=\lim_{L\to\infty}\frac{H(\Pr(s^L))}L − </math> − − − 其中<math> \Pr(s^L)</math>是[math]\displaystyle{ s^L }[/math]的边际分布，[math]\displaystyle{ H }[/math]是[[Shannon熵]]，也就是[[自信息]]的平均值，在建模框架中，[math]\displaystyle{ h_μ }[/math]是信息不确定性程度的归一化指标，信息的不确定性越高，香农熵率越大，在这里可以解释为智能体在预测序列[math]\displaystyle{ s^L }[/math]的后续符号时的误差率。我们可以用香农熵率来监测智能体对外部环境的适应能力，智能体的香农熵率越接近外部环境的香农熵率，说明它的适应能力就越强。 − 因为柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑对象中的所有比特，包括随机状态生成的比特。其主要后果是[math]\displaystyle{ K(x) }[/math]中数值大小[math]\displaystyle{ x }[/math]可能会被随机状态生成的比特所主导，这样会导致对象的特征和重要结构被掩盖。为了避免这个问题，计算力学提出了统计复杂度[math]\displaystyle{ C_μ(x) }[/math]的概念，用来量化对象的复杂性，它反映了对象的结构和动态特性，以及有效建模所需的计算资源。它的公式为+ 第81行：
第68行： − + + + + + + + + + + + + + + + + + + + + + + + − − 下图展示了柯式复杂度和统计复杂度随着序列从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对[[信息源]]不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。 − [[文件:复杂度比较.jpg|居中|无框|600x600像素]] − +
→统计复杂度
=== 柯氏复杂度 ===
=== 柯氏复杂度 ===
在已有的众多复杂度量化指标中，柯氏复杂度是最符合我们要求的一个指标，[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时生成字符串[math]\displaystyle{ x }[/math]的最小程序长度。UTM的能力在于可以模拟任何图灵机，因此可以执行任何可计算的过程。柯氏复杂度则依赖于这种通用性，通过UTM，可以理解任何字符串或数据的最短生成程序。但因为图灵停机问题的存在，我们无法构造一个通用算法来决定任意程序是否会在给定输入上停机。这意味着我们不能有效地判断哪些程序是最短的，因为没有方法可以保证找到最短程序的存在与否。由于没有通用的方法来验证或找到生成字符串[math]\displaystyle{ x }[/math]的最短程序，我们就无法计算柯氏复杂度。即使我们能够找到一个生成字符串[math]\displaystyle{ x }[/math]的程序，我们也无法保证它是最短的。为了确定程序是否为最短程序，我们需要检查所有可能的程序，而这一过程在计算上是不可行的。如果待测对象是由信息源（例如[[马尔可夫链]]）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：
在已有的众多复杂度量化指标中，柯氏复杂度是最符合我们要求的一个指标，[[柯式复杂度]][math]\displaystyle{ K(x) }[/math]是指在通用确定性[[图灵机]]（Universal Turing Machine，简称UTM）上运行时生成字符串[math]\displaystyle{ x }[/math]的最小程序长度。UTM的能力在于可以模拟任何图灵机，因此可以执行任何可计算的过程。柯氏复杂度则依赖于这种通用性，通过UTM，可以理解任何字符串或数据的最短生成程序。但它也有比较明显的两个问题，第一个问题是它的不可计算性，由于图灵停机问题的存在，我们无法构造一个通用算法来决定任意程序是否会在给定输入上停机。这意味着我们不能有效地判断哪些程序是最短的，因为没有方法可以保证找到最短程序的存在与否。由于没有通用的方法来验证或找到生成字符串[math]\displaystyle{ x }[/math]的最短程序，我们就无法计算柯氏复杂度。即使我们能够找到一个生成字符串[math]\displaystyle{ x }[/math]的程序，我们也无法保证它是最短的。为了确定程序是否为最短程序，我们需要检查所有可能的程序，而这一过程在计算上是不可行的。第二个问题是它可能无法度量程序的结构和动态特性，因为柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑字符串中的所有比特，包括随机状态生成的比特。若[math]\displaystyle{ K(x) }[/math]中字符串[math]\displaystyle{ x }[/math]大部分是由随机状态生成，这样会导致[math]\displaystyle{ x }[/math]的特征和重要结构被掩盖。
=== '''统计复杂度''' ===
=== '''统计复杂度''' ===
为了解决柯式复杂度两个明显的问题，计算力学提出了统计复杂度[math]\displaystyle{ C_μ(x) }[/math]的概念，用来量化模型的复杂性，它可以反映[math]\displaystyle{ x }[/math]的结构和动态特性，以及能够计算出有效建模所需的计算资源。它的公式为
<math>
<math>
</math>这个符号表示对模型复杂度的量化，它可以是基于模型状态的数量、参数数量或计算资源的度量。
</math>这个符号表示对模型复杂度的量化，它可以是基于模型状态的数量、参数数量或计算资源的度量。
相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：
相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。
下图展示了柯式复杂度和统计复杂度随着序列从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对[[信息源]]不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。
[[文件:复杂度比较.jpg|居中|无框|600x600像素|
]]
=== 香农熵率 ===
香农熵率（Shannon Entropy Rate）是信息论中的一个概念，通常用来衡量一个信源或随机过程在单位时间内传输的信息量，或者说是该信源的不确定性和复杂性的度量。它是香农熵的扩展，主要用于描述时间序列（如随机过程）的平均信息量。在计算力学中用香农熵率来监测智能体对外部环境的适应能力，智能体的香农熵率越接近外部环境的香农熵率，说明它的适应能力就越强。如果待测对象是由信息源（例如[[马尔可夫链]]）生成的离散符号序列[math]\displaystyle{ s^L }[/math] ，[math]\displaystyle{ L }[/math]为序列的长度，柯式复杂度与香农熵率[math]\displaystyle{ h_μ }[/math]的关系为：
<math>
\frac{K\left(s^{L}\right)}{L}\underset{L\to\infty}{\operatorname*{\operatorname*{\operatorname*{\rightarrow}}}}h_{\mu} ,
</math>
在这里，[[香农熵率]]就可以定义为：
<math>
h_\mu=\lim_{L\to\infty}\frac{H(\Pr(s^L))}L
</math>
其中<math> \Pr(s^L)</math>是[math]\displaystyle{ s^L }[/math]的边际分布，[math]\displaystyle{ H }[/math]是[[Shannon熵]]，也就是[[自信息]]的平均值，在建模框架中，[math]\displaystyle{ h_μ }[/math]是信息不确定性程度的归一化指标，信息的不确定性越高，香农熵率越大，在这里可以解释为智能体在预测序列[math]\displaystyle{ s^L }[/math]的后续符号时的误差率。
如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：
[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]
[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]
如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总[[信息量]]。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。
如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总[[信息量]]。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。
==因果态==
==因果态==
要计算模型的统计复杂度[math]\displaystyle{ C_μ(x) }[/math]，我们需要找到一种方法来最大限度地压缩描述测量结果的字符串。这意味着我们要识别出测量结果中的斑图。具体来说，我们利用微分的思想，将测量结果的数据划分为若干部分，并将每个斑图的数据独立划分，会观察到在不同时间点上，某些斑图会反复出现。我们可以用同一个字符串来表示这些重复出现的斑图，这样就能简化我们的描述，得到模型的最小程序长度。可以把这些能够用同一个字符串描述的重复斑图称为“因果态”。这样一来，通过找到这些因果态，我们就能计算出模型的统计复杂度。
要计算模型的统计复杂度[math]\displaystyle{ C_μ(x) }[/math]，我们需要找到一种方法来最大限度地压缩描述测量结果的字符串。这意味着我们要识别出测量结果中的斑图。具体来说，我们利用微分的思想，将测量结果的数据划分为若干部分，并将每个斑图的数据独立划分，会观察到在不同时间点上，某些斑图会反复出现。我们可以用同一个字符串来表示这些重复出现的斑图，这样就能简化我们的描述，得到模型的最小程序长度。我们可以把这些能够用同一个字符串描述的重复斑图称为“因果态”，这样一来，通过找到这些因果态，就能计算出模型的统计复杂度。
===因果态的定义===
===因果态的定义===