无穷随机矩阵乘积的基础理论及其在多智能体系统中的应用

Multi-agent system is a typical type of complex systems, emergent behavior is one the most important characteristics of multi-agent system, which describes the process from simple and local interactions to complex and global behavior. The deep understanding on emergent behavior will guide us to uncover the origin of complexity. Stochastic matrix is a tool which describes the interactions among agents in multi-agent systems, and the products of stochastic matrices describes the evolution dynamics of multi-agent systems. The study on products of stochastic matrices will help us find the essential rule behind the emergent behavior of multi-agent systems. However, the analysis on products of stochastic matrices is very hard due to the fact: the widely-used Lyapunov-based approach often fails in analyzing the convergence of products of stochastic matrices. This project extracts the basic theory of products of stochastic matrices from multi-agent systems, and tries to explore several basic problems of complexity science. In particular, this project studies the intrinsic mechanism on convergence of products of stochastic matrices from three perspectives: computational complexity, graph theory, and numerical approximation. We further use the theory of products of stochastic matrices to study the convergence of distributed optimization algorithm, and related results can be applied in machine learning, rail traffic optimization, etc.

多智能体系统是一类典型的复杂系统，涌现行为是多智能体系统的重要特征，它描述了个体之间通过简单局部相互作用从而产生整体行为的过程，对涌现行为的深刻理解将引导我们最终揭开复杂性起源的奥秘。随机矩阵是一种用于刻画多智能体系统中个体之间相互作用的重要工具，而随机矩阵乘积则可以被用来描述多智能体系统的演化动力学过程，对随机矩阵乘积的深入研究有助于我们找到多智能体系统涌现行为的本质规律。然而，分析随机矩阵乘积的收敛性具有极大的挑战性，其重要原因在于无法通过构造常规的Lyapunov函数来刻画其收敛特性。本项目从多智能体系统中抽象出随机矩阵乘积的一般性理论，试图从随机矩阵乘积的角度去探索复杂性科学的若干根本问题。具体而言，项目将分别从计算复杂性、图论、数值逼近这三个角度研究随机矩阵乘积收敛的内在机理，并利用随机矩阵的乘积理论去刻画分布式优化算法的收敛性，相关成果可进一步应用于机器学习、轨道交通等领域。

无穷随机矩阵乘积是多智能体系统分析中的关键理论工具之一，对随机矩阵乘积的深入研究有助于我们找到多智能体系统涌现行为的本质规律。本项目从多智能体系统中抽象出随机矩阵乘积的一般性理论，试图从随机矩阵乘积的角度去探索复杂性科学的若干根本问题。作为理论研究成果的进一步延伸，我们将多智能体系统和随机矩阵的基本思想应用到知识图谱的训练和推理中。以下从理论和工程两个方面来阐述本项目的主要工作。..在理论研究方面，本项目的成果包括：..1..给出了确定性框架下的异步随机矩阵乘积的收敛性分析。.项目从两个角度深入探讨了异步更新对随机矩阵乘积的影响，即什么样的网络结构能够保证异步更新一定收敛和什么样的网络结构一定不能保证异步更新收敛。我们发现了两类特殊的拓扑结构：部分邻居共享图和本质周期图，并采用严格的理论证明了这两类图能够恰好回答关于异步更新收敛的本质问题。相关论文发表于控制领域的顶级期刊IEEE Trans. Automatic Control上。.2..给出了随机更新框架下的异步随机矩阵乘积的收敛性分析。.在随机异步更新的情况下，项目研究发现网络的图结构对于异步更新的收敛性并没有非常显著的影响，即只需要网络图结构是联通的（甚至不需要是非周期的）条件下，随机对网络中的节点更新均会以概率1导致网络状态的收敛。该理论发现对于实际中涉及分布式学习算法具有一定的启示意义。相关论文发表于控制领域的顶级期刊Automatica上。..在工程应用领域，本项目的成果包括：..1..基于随机矩阵乘积理论给出了高精度的知识图谱连接预测算法。.知识图谱是目前在人工智能应用中采用的一种通用知识表示结构，知识的表示就蕴含于这些概念构成的网络之中。本项目基于随机矩阵的基本理论，首次将知识的表示引入到了复杂的几何结构Möbius环中，实验表明：采用基于Möbius环的知识表示嵌入向量能实现目前最好的链接预测效果。相关论文发表于AI领域的著名期刊Knowledge Based Systems。.2..就随机矩阵乘积理论的知识图谱训练框架设计。.项目基于随机矩阵乘积理论设计了目前世界上最快的知识图谱嵌入训练框架GraphKE。目前GraphKE的详细代码目前在github上进行了开源，该训练框架比目前已知的最快的知识图谱嵌入训练框架DGL-KE快2-3倍，对显存的消耗仅仅只有DGL-KE的1/10左右。