Exploiting the Architecture of Dynamic Systems
Exploiting the Architecture of Dynamic Systems
复制标题
利用动态系统的架构
DOI：
10.3934/fods.2019003
复制
发表时间：
1999
影响因子：
2.3
通讯作者：
D. Koller
中科院分区：
文献类型：
--
作者：
Xavier Boyen;D. Koller
考虑监测一个复杂动态系统的状态并预测其未来演变的问题。此任务的精确算法通常保持一个信念状态，或者在某个时间点上的状态分布。不幸的是，当这些算法应用于复杂的过程时，例如那些表示为动态贝叶斯网络（dbn）的过程，因为信念状态的表示随着过程的大小呈指数级增长。在（Boyen & Koller 1998）中，我们最近提出了一种有效的近似跟踪算法，该算法保持近似信念状态，该状态具有作为一组独立因素的紧凑表示。它的性能取决于通过因子1近似该过程的信念状态所引入的误差。我们非正式地认为，如果过程中变量之间的相互作用是“弱”的，那么这个误差就很低。本文给出了过程间弱相互作用和稀疏相互作用等概念的形式化信息理论定义。我们用这些概念来分析由这种近似引起的误差小的条件。我们展示了几个案例，其中我们的结果正式支持关于相互作用强度的直觉。
Consider the problem of monitoring the state of a complex dynamic system, and predicting its future evolution. Exact algorithms for this task typically maintain a belief state, or distribution over the states at some point in time. Unfortunately, these algorithms fail when applied to complex processes such as those represented as dynamic Bayesian networks (DBNs), as the representation of the belief state grows exponentially with the size of the process. In (Boyen & Koller 1998), we recently proposed an efficient approximate tracking algorithm that maintains an approximate belief state that has a compact representation as a set of independent factors. Its performance depends on the error introduced by approximating a belief state of this process by a factored one. We informally argued that this error is low if the interaction between variables in the processes is "weak". In this paper, we give formal information-theoretic definitions for notions such as weak interaction and sparse interaction of processes. We use these notions to analyze the conditions under which the error induced by this type of approximation is small. We demonstrate several cases where our results formally support intuitions about strength of interaction.