更改

马尔科夫链的粗粒化 (查看源代码)

2024年10月11日 (五) 20:27的版本

添加999字节、 2024年10月11日 (星期五)

无编辑摘要

第105行：第105行：

这个定义可以想象成可压缩的程度，也会是下面的hard partitioning的分组的数量。

+

=Lumpability=

第130行：第132行：

对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{kA_j}</math>都是一样的。

−

~~也就是说~~

+

也就是说，设<math>p_{s_k \rightarrow s_m} = p(f_t = s_m | f_{t-1} = s_k)</math>，<math>p_{A_i \rightarrow s_m} = p(f_t = s_m | f_{t-1} \in A_i)</math>

{{NumBlk|:|

<math>

\begin{aligned}

−

p_{s_k A_j} = \sum_{s_m \in A_j} p_{s_k s_m} = p_{A_i A_j}, k \in A_i

+

p_{s_k \rightarrow A_j} = \sum_{s_m \in A_j} p_{s_k \rightarrow s_m} = p_{A_i \rightarrow A_j}, k \in A_i

\end{aligned}

</math>

第186行：第188行：

<math>

\begin{aligned}

−

P = P_{s_i s_j} = \left [

+

P = P_{s_i \rightarrow s_j} = \left [

\begin{array}{ccc:c}

0.3 & 0.3 & 0.3 & 0.1 \\

第201行：第203行：

我们可以看到，123行都是一样的，所以把他们分在一组，并把状态4分在另外一组，看起来像是一个合理的正例。

−

~~接下来我们来计算一下。~~

+

接下来我们来计算一下。设<math>p_{s_1 \rightarrow s_2} = p(f_t = s_2 | f_{t-1} = s_1)</math>，<math>p_{s_1 \rightarrow A_2} = p(f_t \in A_2 | f_{t-1} = s_1)</math>

−

第1组的状态1到第1组的状态2，<math>p_{s_1 A_1} = p_{A_1 A_1} = \sum_{s_m \in A_1} p_{s_1 s_m} = p_{s_1 s_1} + p_{s_1 s_2} + p_{s_1 s_3} = 0.3 \times 3 = 0.9 </math>

+

第1组的状态1到第1组的状态2，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} + p_{s_1 \rightarrow s_3} = 0.3 \times 3 = 0.9 </math>

−

第1组的状态1到第2组的状态4，<math>p_{s_1 A_2} = p_{A_1 A_2} = \sum_{s_m \in A_2} p_{s_1 s_m} = p_{s_1 s_4} = 0.1 </math>

+

第1组的状态1到第2组的状态4，<math>p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_4} = 0.1 </math>

−

第2组的状态4到第1组的状态1，<math>p_{s_4 A_1} = p_{A_2 A_1} = \sum_{s_m \in A_1} p_{s_4 s_m} = p_{s_4 s_1} + p_{s_4 s_2} + p_{s_4 s_3} = 0.1 \times 3 = 0.3 </math>

+

第2组的状态4到第1组的状态1，<math>p_{s_4 \rightarrow A_1} = p_{A_2 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} + p_{s_4 \rightarrow s_3} = 0.1 \times 3 = 0.3 </math>

−

第2组的状态4到第2组的状态4，<math>p_{s_4 A_2} = p_{A_2 A_2} = \sum_{s_m \in A_2} p_{s_4 s_m} = p_{s_4 s_4} = 0.7 </math>

+

第2组的状态4到第2组的状态4，<math>p_{s_4 \rightarrow A_2} = p_{A_2 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_4} = 0.7 </math>

<math>

\begin{aligned}

−

P = P_{A_k A_l} = \left [

+

P = P_{A_k \rightarrow A_l} = \left [

\begin{array}{c:c}

0.9 & 0.1 \\

第229行：第231行：

同样的，我们来计算一下。这次我们需要对3和4分开计算了。

−

第1组的状态1到第1组的状态2，<math>p_{s_1 A_1} = p_{A_1 A_1} = \sum_{s_m \in A_1} p_{s_1 s_m} = p_{s_1 s_1} + p_{s_1 s_2} = 0.3 \times 2 = 0.6 </math>

+

第1组的状态1到第1组的状态2，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math>

−

第1组的状态1到第2组的状态3，<math>p_{s_1 A_2} = p_{A_1 A_2} = \sum_{s_m \in A_2} p_{s_1 s_m} = p_{s_1 s_3} + p_{s_1 s_4} = 0.4 </math>

+

第1组的状态1到第2组的状态3，<math>p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_3} + p_{s_1 \rightarrow s_4} = 0.4 </math>

−

第2组的状态3到第1组的状态1，<math>p_{s_3 A_1} = \sum_{s_m \in A_1} p_{s_3 s_m} = p_{s_3 s_1} + p_{s_3 s_2} = 0.3 \times 2 = 0.6 </math>

+

第2组的状态3到第1组的状态1，<math>p_{s_3 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_3 \rightarrow s_m} = p_{s_3 \rightarrow s_1} + p_{s_3 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math>

−

第2组的状态4到第1组的状态1，<math>p_{s_4 A_1} = \sum_{s_m \in A_1} p_{s_4 s_m} = p_{s_4 s_1} + p_{s_4 s_2} = 0.1 \times 2 = 0.2 </math>

+

第2组的状态4到第1组的状态1，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math>

−

这里我们就能看到，<math>p_{s_3 A_1} \neq p_{s_4 A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 A_1} = p_{s_3 A_1}</math>还是<math>p_{A_2 A_1} = p_{s_4 A_1}</math>），假设<math>p_{A_2 A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了Lumpability一开始的定义<ref name=":3" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。

+

这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了Lumpability一开始的定义<ref name=":3" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。

第246行：第248行：

<math>

\begin{aligned}

−

P = P_{s_i s_j} = \left [

+

P = P_{s_i \rightarrow s_j} = \left [

\begin{array}{cc:cc}

0.2 & 0.4 & 0.3 & 0.1 \\

第260行：第262行：

<math>

\begin{aligned}

−

P = P_{A_k A_l} = \left [

+

P = P_{A_k \rightarrow A_l} = \left [

\begin{array}{c:c}

0.6 & 0.4 \\

第282行：第284行：

<math>

\begin{aligned}

−

P = P_{s_i s_j} = \left [

+

P = P_{s_i \rightarrow s_j} = \left [

\begin{array}{c:c:cc:c:c}

0 & 0 & 0.3 & 0.1 & 0.6 & 0\\

第322行：第324行：

然后，我们来简单介绍一下的构建宏观HON转移概率矩阵的计算方法。

−

在图2中，我们看到3和4为待合并节点<math>S</math>。

+

在图2中，我们看到3和4为待合并节点<math>A</math>。

−

1. 对于其他节点到待合并节点<math>S</math>的连边，即待合并节点的入流（图2中绿色的连边），我们直接加和即可，即<math>p_{~~1->S~~} = 0.3+0.1=0.4</math>，<math>p_{~~2->S~~} = 0.2+0.3=0.5</math>

+

1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图2中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>

−

2. 对于待合并节点<math>S</math>到其他节点的连边，即待合并节点的出流（图2中棕色的连边），我们需要考虑三种情况：

+

2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图2中棕色的连边），我们需要考虑三种情况：

−

#当待合并节点<math>S</math>间存在连边时；

+

#当待合并节点<math>A</math>间存在连边时；

−

#指向同一个输出节点时；

+

#当待合并节点<math>A</math>指向同一个输出节点时；

−

#当待合并节点<math>S</math>指向不同输出节点时；

+

#当待合并节点<math>A</math>指向不同输出节点时；

−

待合并节点<math>S</math>的出流的计算方式都不一样，如图3所示。

+

待合并节点<math>A</math>的出流的计算方式都不一样，如图3所示。

[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]

−

'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>S</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，lumpability的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于lumpable partition来说都能得出相同的结果。

+

'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，lumpability的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于lumpable partition来说都能得出相同的结果。

由此，我们总结，lumpable partition的聚合方式和HON，无论入流还是出流都完全一致。

第354行：第356行：

实验发现，对不同节点规模以及参数下的微观网络，使用HON粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HON构建的宏观网络和微观网络是保持一致的。回到上面lumpable partition 等于HON的推断，我们就能得出，根据lumpable partition而做的粗粒化，构建的和宏观网络和微观网络也是保持一致的。

+

Liangjh

97

个编辑