Modeling Time In Belief Networks

该项目解决了给定动态域的不完整和不确定信息的建模时间问题。第一个目标是在信念网络范式中构建一个动态模型，并演示如何在该模型中实现众所周知的时间序列概念，例如后向平滑、前向滤波和预测。给定一个对域的定常关系进行建模的信念网络，将半自动地生成动态模型。这将提供一种半自动的方法，将现有的信念网络模型扩展到动态信念网络模型，该模型可用于考虑系统变量的时间演化的应用中，这对于做出关于域的有效推断至关重要。第二个目标是设计一种有效的随机逼近方案（RAS），用于动态模型的信念网络的概率推理。与其他用于概率推理的随机模拟算法相比，RAS特有的某些特征使其成为动态模型的推理算法的理想选择。例如，在动态领域中，当做出决策所需的时间与系统发生充分变化以使决策过时的预期时间相当时，就会进入决策的效用。RAS提供了在输出中实现预定义精度级别所需的运行时间的先验界限。此信息可用于减少由于延迟决策而造成的效用损失。已知现有的用于信念网络中概率推理的RASs具有较差的最坏情况行为，尽管人们推测它们具有有效的平均情况复杂度。本研究将描述现有ras有效运行的信念网络类别，然后将扩展这些算法以处理该类之外的情况。开发的新ras随后将针对开发的动态模型中的计算推断进行优化。

This project addresses the problem of modeling time in dynamic domains given incomplete and uncertain information about the domain. The first objective is to construct a dynamic model within a belief-network paradigm and to demonstrate how well known time series concepts-such as backward smoothing forward filtering and forecasting - are implemented in this model. The dynamic model will be generated semiautomatically given a belief network that models the time-invariant relations of the domain. This will provide a semiautomatic method for extending existing belief network models to dynamic belief-network models that can be used in applications where consideration of the time evolution of system variables is crucial to making valid inferences about the domain. The second objective is to design an efficient randomized approximation scheme (RAS) for probabilistic inference in belief networks to be employed by the dynamic model. Certain features unique to a RAS, compared to other stochastic simulation algorithms for probabilistic inference, make the RAS desirable as an inference algorithm for a dynamic model. For example, in dynamic domains, the time required to make a decision enters the utility of the decision when this time becomes comparable to the expected time in which the system changes sufficiently to outdated a decision. A RAS provides an a priori bound on the running time required to achieve a predefined level of accuracy in the output. This information can be used to reduce the loss of utility due to delayed decisions. Existing RASs for probabilistic inference in belief networks are known to have a poor worst-case behavior, although it is conjectured that they have efficient average-case complexity. This research will characterize the class of belief networks or which existing RASs run efficiently, then will extend these algorithms to handle cases that fall outside of this class. The new RASs developed will be subsequently optimized specifically for computing inferences in the dynamic models developed.