Modeling Time In Belief Networks

这个项目解决了在给定域的不完全和不确定信息的情况下，动态域中的建模时间问题。第一个目标是在信念网络范式下构建一个动态模型，并展示众所周知的时间序列概念--如向后平滑、前向过滤和预测--如何在该模型中实现。在给定对域的时间不变关系建模的信任网络的情况下，将半自动地生成动态模型。这将提供一种半自动方法，将现有的信任网络模型扩展为动态信任网络模型，可用于考虑系统变量的时间演化对于做出关于领域的有效推断至关重要的应用。第二个目标是设计一种有效的随机近似方案(RAS)，用于信任网络中的概率推理，以供动态模型使用。与用于概率推理的其他随机模拟算法相比，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.