812
个编辑
更改
跳到导航
跳到搜索
第580行：
第580行： − + 第682行：
第682行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→划分方法
当我们想把 <math>N</math> 个状态的马尔科夫链划分成 <math>M</math> 组时，待选的划分数量可以由 第二类斯特林数（Stirling numbers of the second kind）表示，<math>S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N</math>
当我们想把 <math>N</math> 个状态的马尔科夫链划分成 <math>M</math> 组时，待选的划分数量可以由 第二类斯特林数（Stirling numbers of the second kind）表示，<math>S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N</math>
待选的划分数量极大，比如<math>S(20,10)=1.107e32</math>，几乎不可能通过遍历所有待选划分来寻找最优划分，所以，我们需要使用一些方法。
待选的划分数量极大，比如<math>S(20,10)=1.107e32</math>，几乎不可能通过遍历所有待选划分来寻找最优划分，所以，我们需要使用一些方法来有效的寻找到近似最优解。
<br/>
<br/>
==其他方法==
寻找最优划分本质上是个组合优化问题，所以我们也能使用其他合适的方法来解决该问题。
首先是遗传算法。它是一种受生物进化启发的全局优化算法，通过模拟自然选择（选择适应度高的个体作为父代）、交叉（通过父代基因重组生成子代）和变异（以一定概率随机改变子代基因）等机制，在解空间中搜索最优解。其核心流程包括：
# 种群初始化：随机生成候选解的群体。
# 在每一步迭代过程中：
## 选择：选择最大化目标（划分标准）的个体作为父代。
## 交叉：通过父代基因重组生成子代。
## 变异：以一定概率随机改变子代基因。
所以，我们可以把上述的逐层贪婪算法和谱分解方法的解作为初始解，通过遗传算法，帮助跳出局部最优解，并寻找到新的全局更优解。
另外，我们也能使用梯度下降方法，搭配深度学习方法，比如图神经网络，来寻找最优划分。比如，在Klein等人的论文<ref name=":0"/>，以及Griebenow 等人<ref name=":Griebenow">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>的文献中，把粗粒化方案写成一个分组矩阵，同时将这个分组矩阵参数化，这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算EI。之后，使用自动微分方法执行[[梯度下降算法]]从而优化分组矩阵，以使得EI最大化。
'''输入'''：包含[math]N[/math]个节点的原始网络[math]G[/math]，其对应邻接矩阵为：<math>A</math>，粗粒化后的网络所包含的节点数：<math>K</math>；'''输出'''：宏观网络[math]G'[/math]，对应的邻接矩阵为：<math>B</math>，以及对应的从[math]A[/math]到[math]B[/math]的粗粒化矩阵：<math>M</math>
# 针对一个含有<math>N</math>个节点的网络<math>A</math>，随机初始化一个分组矩阵<math>M\in \mathbb{R}^{N×K}</math>，<math>K</math>表示分组的大小，其中矩阵里面的每个元素<math>m_{iμ}=Pr(v_i\in v_{\mu})</math>，表示微观节点<math>v_i</math>属于宏观节点<math>v_{\mu}</math>的概率
# 根据微观网络和分组矩阵构建宏观网络<math>B</math>，具体计算方法分为两个步骤：1）<math>M^TAM</math>；2）归一化前一步骤得到的矩阵
# 使用带动量的[[梯度下降]]方法优化<math>M</math>，优化目标是最大化宏观网络的有效信息EI。
时间复杂度：<math>O(N^3)</math>
'''缺点'''：
# 初始化分组矩阵的选择，多次重复实验会得到不一样的结果
# 依赖神经网络的超参，如学习率、迭代次数等
=聚合方法=
=聚合方法=