算法的时间复杂度分析的基本方法（复杂系统的逆向工程）

算法的时间复杂度分析的基本方法（复杂系统的逆向工程）图1. 时间序列与社交网络很多复杂系统都可以被抽象为一个相互作用的网络和其上的动力学。传统的研究主要关注如何构建网络动力学模型，从而产生和实验观测数据具有相似统计特征的结果。而我们关注的则是一个逆向工程问题：如何根据系统演化生成的时间序列数据，自动推断出系统的动力学规律及其相互作用网络。这是一个得到了普遍关注的前沿性问题，并在气象、生物、环境、经济等多个领域中都存在着潜在应用价值。Universal framework for reconstructing complex networks and node dynamics from discrete or continuous dynamics data论文链接：https://journals.aps.org/pre/abstract/10.1103/PhysRevE.106.034315

导语

蛋白质相互作用网络、生态群落、全球气候系统……很多复杂系统都可以抽象为一个相互作用的网络和其上的动力学。传统的研究主要关注在如何构建网络动力学模型，从而产生和实验观测数据具有相似统计特征的结果。所谓的复杂系统逆向工程，就是反其道而行之，直接从复杂系统的时间序列数据出发重构出系统的交互结构和节点动力学。这一问题显然要比正向问题困难很多。已有的研究方法虽然已经取得了一定的进展，但是它们要么专注于网络结构推理任务，要么专注于动力学重构问题，很少有方法能同时兼顾两者。

在近日发表于 Physical Review E 的一项最新研究中，北京师范大学系统科学学院张江团队提出了一个通用框架，用观察到的节点时间序列数据来逆向工程复杂系统的网络结构和动力学。研究使用可微分伯努利采样过程来生成候选网络结构，使用神经网络来模拟基于候选网络的节点动力学；然后使用随机梯度下降算法调整所有参数，以最大化在数据上定义的似然函数。实验表明，该模型可以同时高精度地恢复各种网络结构和节点动力学，还可以很好地处理二进制、离散和连续的时间序列数据，并且重建结果对噪声和丢失信息具有鲁棒性。为了验证算法能够学习到正确的因果关系，该研究首次提出利用控制任务对比学习到的替代系统和真实系统。以下是论文第一作者、北京师范大学系统科学学院硕士生张妍对该研究的解读。

研究领域：网络动力学，网络重构，复杂网络自动建模

论文标题：

Universal framework for reconstructing complex networks and node dynamics from discrete or continuous dynamics data

论文链接：

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.106.034315

1. 复杂系统的数据驱动建模

很多复杂系统都可以被抽象为一个相互作用的网络和其上的动力学。传统的研究主要关注如何构建网络动力学模型，从而产生和实验观测数据具有相似统计特征的结果。而我们关注的则是一个逆向工程问题：如何根据系统演化生成的时间序列数据，自动推断出系统的动力学规律及其相互作用网络。这是一个得到了普遍关注的前沿性问题，并在气象、生物、环境、经济等多个领域中都存在着潜在应用价值。

图1. 时间序列与社交网络

例如，如何根据全球范围的气象观测时间序列构建全球大气系统的网络动力学模型，是我们更好地理解气候系统运作规律的基础；如何根据转录因子浓度数据序列推测出基因调控网络，并理解各个节点如何互动，直接关系到我们对生命运行机制的破解；如何根据局部的脑电信号序列重构出大脑结构网络和动力学机制，可以帮助我们理解大脑的认知功能。如何通过各个公司的财务数据推断出公司间的相互作用网络并预测公司未来的走向，这些问题都可以理解为复杂系统的逆向工程学问题。

2. 复杂网络自动建模框架

在此问题上，传统的方法包括贝叶斯估计、概率推断、线性回归等手段虽然也能取得一定进展，但是它们往往需要引入额外的假设信息，例如系统的动力学方程已知等等。而本项最新研究提出了一个基于机器学习的复杂网络动力学自动建模的框架，模型的输入是所有节点在时刻 的状态信息，输出是 1 时刻的状态信息和网络结构。模型由两部分组成：网络生成器和动力学学习器。

图2. 模型框架的构造

网络生成器（Network Generator）使用 Gumbel softmax 技术生成邻接矩阵，动力学学习器（Dynamics Learner）由节点和连边之间的四层映射组成，通过邻接矩阵把所有节点的状态由 时刻映射到 1 时刻。

训练过程如下：首先由网络生成器生成网络的拓扑结构（临接矩阵），动力学学习器用生成的邻接矩阵和所有节点的时间序列信息去预测下一时刻所有节点的状态，计算预测值和真实值的损失，将损失反传，使用梯度下降方法不断迭代优化模型。

由于现实世界中的网络都是较为稀疏的，因此研究中利用稀疏矩阵的先验知识，引入了结构损失学习率来不断稀疏化网络结构。同时在更大尺度的网络节点实验中，采取分批次加入节点的技术以减少内存占用过大的问题。

3. 网络重构和节点动力学预测

除了在ER、WS、BA生成模型网络上，我们还在6种真实的网络结构下进行了实验。在动力学的选择上，采用了连续动力学、离散动力学和布尔动力学。实验结果如下表所示，与其他选定方法（列）在不同动力学和网络结构（行）上的网络重构和动力学预测任务的性能比较，可以看出无论在网络重构还是动力学预测方面，效果都优于其他方法。该算法可以扩展到上千个节点规模的大网络上。

在现实世界中，由于测量误差或者隐私保护等问题，都会面临数据缺失的问题，常常只能记录网络中部分甚至很少节点的数据(M ≪ N)，另一些节点难以测量，我们甚至不知道这些节点存在与否。因此 网络重构必须解决在 M ≪ N（数据缺失）的条件下，利用已有的数据并通过有效的分析方法得到尽可能多的关于网络结构的有用信息。为此该研究在部分节点缺失的情况下进行实验，来探究模型的鲁棒性。

如下图所示，图3(a) 显示了一个真实网络的示意图，其中未观察到的节点（灰色节点）上缺少信息。图3(b) 显示了未观察到的节点的比例对部分网络上交互推断准确性的影响，所有实验均在 100 个节点的 ER 网络上进行。图3(c) 显示了 AUC 和 MSE 对具有 100 个节点的酵母基因网络上的 Michaelis-Menten 动力学（基因动力学）的每个节点上添加的噪声平均值的依赖性。图3(d) 显示了推断整个网络（浅色条）和未观察到的部分网络（深色条）上的拓扑结构的能力，所有网络都包含100个节点，其中10%是随机选择的不可观测节点。

图3. 鲁棒性探究：部分节点缺失的网络上的实验

为了验证该算法是否可以应用于实际场景，研究者尝试根据 GeneNetWeaver 生成的 mRNA 浓度的时间序列数据，从已知的酿酒酵母转录网络中推断出真实的子网络结构。在实验中，研究者使用100个节点的酵母 S. cerevisiae 基因网络作为基准基因网络，并使用 GeneNetWeaver 软件中 DREAM4_In-Silico 的默认参数生成数据。对于动态模拟器，为每个节点使用不同的神经网络，因为节点动态的异质性以及潜在变量、噪声和扰动的存在。

研究者将该方法与偏相关、贝叶斯网络推理和互信息算法进行比较，如图4所示，该方法在网络重构方面优于其他方法，还可以完成较高的精度预测动力学，这表明它可以很好地执行现实的基因调控动力学。

图4. 该研究方法与偏相关、贝叶斯网络推理和互信息算法的比较。

然而，仅仅通过机器学习的方式，我们很难保证学习到的节点关系是真的因果关系，而因果关系只有通过Do操作，即把相同的干预操作同时施加给学习到的系统和真实的系统，并得到相同的响应结果才能真正判断算法学习到了真实的因果机制。因此，我们创新性地提出利用控制实验来验证学习模型的能力，即在相同的控制目标前提下，将学习替代模型上优化出来的最优控制策略应用到真实系统上，看看真实系统是否能够达到和替代模型相同的目标。

我们在两组网络动力学模型系统中展开实验，控制目标定为所有节点的同步，然后在学习替代模型上优化出最优控制策略，并将此策略应用到真实系统（模型）上，观察学习替代模型和真实模型的行为。对比结果如下图所示：

图5. 控制实验结果图。

（a）显示了实验研究的弹簧小球网络。三个黄色节点是驱动节点，其他是目标节点。控制目标是要求所有小球具有相同的运动方向。(b) 显示了控制下所有目标节点的最终运动状态。X 和 Y 表示所有小球的位置的二维坐标。(c) 显示了用于评估误差与时间步长的两条损失曲线。一个代表学习模型的结果，另一个是真实结果。(d) 研究的是耦合晶格网络。两个黄色节点被选为驱动节点。控制目标是要求所有振荡器在相同的位置即0.6，这是所有节点的值范围的平均值。(e) 显示了控制期间所有目标节点的振荡。(f) 显示了用于评估误差与时间步长的两条损失曲线。

从图5(c)的结果看出，最优控制策略不仅在真实和替代系统上都实现了控制目标，而且该策略的控制误差曲线也几乎重合，这说明在替代模型上优化出来的最优控制策略是可以被实施到真实系统上的。从图5(f)的结果来看，虽然没有达到控制目标，但是真实和替代系统具有几乎相同的控制误差曲线，这说明，二者具有类似的因果响应机制。

4. 总结和展望

本研究提出了一个同时进行网络结构重构和节点动力学预测的统一框架，还提出了一个基于控制任务的新标准来评估是否可以学习真正的网络和动力学。与之前的工作相比，该研究以基于马尔可夫动力学和局部网络交互的更严格的数学形式来表述问题。本研究还为该模型提出了一个新的数学框架，提供了一个基于对数似然的统一目标函数，这是该模型可以应用于不同动力学的理论基础。研究还描述了如何将优化目标函数分解为单个节点，这是新的基于深度学习的节点网络重建方法的基础。

从实验方面来看，该模型的主要亮点包括可扩展性、通用性和鲁棒性。高可扩展性体现在该模型可以应用于具有超过数千个节点的大型网络，准确率超过 90%，因为训练过程可以逐个节点进行。它是一个通用框架，因为可以应用于各种类型的动态，包括连续、离散和二进制。该模型不仅对嘈杂的输入信号很稳健，而且对不可观察的节点也很稳健。即使时间序列数据丢失，它也可以恢复整个网络，准确率超过 90%。它还被证明在 GeneNetWeaver 生成的数据集上运行良好，模拟了基因调控网络动态的真实环境。最后，我们提出了一种新的验证机器学习模型的方式，就是通过控制实验来对比机器学习得到的替代模型和真实模型的表现。

这个框架有很多潜在的应用。例如，该方法可用于根据动力学信息推断缺失的连边，也可以用于时间序列预测。与其他预测模型相比，模型可以输出清晰的二元网络，可以更深入地了解元素相互作用和潜在的因果关系，增加模型的可解释性。

但是，当前框架中也存在一些缺点。首先，需要大量的训练数据，尤其是不同初始条件下的时间序列，才能获得一个好的模型。然而，在许多情况下很难获得时间序列数据。因此，我们可以开发适合小数据的新模型。其次，本文考虑的所有动力学都是马尔可夫的，但在实际情况下很难满足这一性质。应该对非马尔可夫动力学进行新的扩展和实验，例如，可以使用循环神经网络而不是前馈网络作为动力学模拟的组件。

张妍 | 作者

邓一雪 | 编辑

商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧!