近日，意大利都灵理工大学的Stefano Crotti与Alfredo Braunstein合作并取得一项新进展。经过不懈努力，他们提出图上再加权随机动力学的矩阵积信念传播模型
该研究团队在矩阵积腔方法的基础上，进行了两个方向的基本扩展。首先，研究人员展示了如何将该方法应用于由任意再加权因子偏置的马尔可夫过程，这些因子能够有效地将大部分概率质量集中在罕见事件上。其次，他们提出了一种高效的方案，将单个节点更新的计算成本从节点度的指数级降低到了多项式级，从而显著提高了计算效率。在研究过程中，他们考虑了两种应用场景：一种是从SIRS流行病模型中的稀疏观测数据中推断感染概率；另一种是计算几个动力学伊辛模型的典型观测值和大偏差。
据悉，图上的随机过程能够描述众多现象，包括神经活动到流行病的传播。尽管现有众多方法能精确描述这些过程的典型实现，但计算极端罕见事件的属性仍然是一项巨大挑战。尤其在循环模型中，变量可能会返回到先前状态。
附：英文原文
Title: Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
Author: Crotti, Stefano, Braunstein, Alfredo
Issue&Volume: 2023-11-14
Abstract: Stochastic processes on graphs can describe a great variety of phenomena ranging from neural activity to epidemic spreading. While many existing methods can accurately describe typical realizations of such processes, computing properties of extremely rare events is a hard task, particularly so in the case of recurrent models, in which variables may return to a previously visited state. Here, we build on the matrix product cavity method, extending it fundamentally in two directions: First, we show how it can be applied to Markov processes biased by arbitrary reweighting factors that concentrate most of the probability mass on rare events. Second, we introduce an efficient scheme to reduce the computational cost of a single node update from exponential to polynomial in the node degree. Two applications are considered: inference of infection probabilities from sparse observations within the SIRS epidemic model and the computation of both typical observables and large deviations of several kinetic Ising models.
DOI: 10.1073/pnas.2307935120
Source: https://www.pnas.org/doi/abs/10.1073/pnas.2307935120