Dynamic Bayesian Networks as Formal Abstractions of Structured Stochastic Processes
Dynamic Bayesian Networks as Formal Abstractions of Structured Stochastic Processes
复制标题
动态贝叶斯网络作为结构化随机过程的形式抽象
DOI：
10.4230/lipics.concur.2015.169
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Majumdar
中科院分区：
文献类型：
--
作者：
S. Soudjani;A. Abate;R. Majumdar
研究广义（不可数）状态空间上离散马尔可夫过程的有限视界概率不变性问题。我们计算离散时间有限状态马尔可夫链作为一般马尔可夫过程的形式抽象。我们的抽象在两个方面不同于现有的方法。首先，我们利用底层马尔可夫过程的结构分别计算每个维度的抽象。其次，我们采用动态贝叶斯网络（DBN）作为抽象的紧凑表示。相比之下，根据我们的实验，现有的方法显式地表示和存储（指数级大的）马尔可夫链，这导致了大量的内存需求，将应用限制在维度小于一半的模型上。
We study the problem of finite-horizon probabilistic invariance for discrete-time Markov processes over general (uncountable) state spaces. We compute discrete-time, finite-state Markov chains as formal abstractions of general Markov processes. Our abstraction differs from existing approaches in two ways. First, we exploit the structure of the underlying Markov process to compute the abstraction separately for each dimension. Second, we employ dynamic Bayesian networks (DBN) as compact representations of the abstraction. In contrast, existing approaches represent and store the (exponentially large) Markov chain explicitly, which leads to heavy memory requirements limiting the application to models of dimension less than half, according to our experiments.
We show how to construct a DBN abstraction of a Markov process satisfying an independence assumption on the driving process noise. We compute a guaranteed bound on the error in the abstraction w.r.t. the probabilistic invariance property; the dimension-dependent abstraction makes the error bounds more precise than existing approaches. Additionally, we show how factor graphs and the sum-product algorithm for DBNs can be used to solve the finite-horizon probabilistic invariance problem. Together, DBN-based representations and algorithms can be significantly more efficient than explicit representations of Markov chains for abstracting and model checking structured Markov processes.