Synthesis of Strategies in Influence Diagrams
Synthesis of Strategies in Influence Diagrams
复制标题
影响图中策略的综合
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
F. Díez
中科院分区：
文献类型：
--
作者：
Manuel Luque;M. Arias;F. Díez
在fl中，图是表示和解决不确定情况下决策问题的有力工具。评估ID的目标是计算期望效用和最优策略，最优策略由每个决策的策略组成。每个策略通常表示为一个表，该表包含用于每个决策方案的列，即用于它所依赖的变量的每个配置。不忘假设意味着决策者总是记住过去的所有观察和决定，这使得策略随着ID中变量的数量呈指数级增长。对于人类专家来说，ficult很难理解巨大的策略表中包含的策略，不仅是因为它们的大小，而且因为绝大多数列对应于次优或不可能的情况，因此是无关紧要的。这使得fi很难提取行动规则，调试模型，并说服专家相信ID的建议是合理的。在本文中，我们提出了一种以紧凑树的形式来表示策略的方法。该算法已在概率图形模型开源软件工具OpenMarkov中实现。在评估非小细胞肺癌纵隔分期的Influence图时，这一设施是必不可少的；最优策略，其最大的政策表包含15,000多列，被合成成一棵只有5片叶子的树。
Influence diagrams (IDs) are a powerful tool for representing and solving decision problems under uncertainty. The objective of evaluating an ID is to compute the expected utility and an optimal strategy, which consists of a policy for each decision. Every policy is usually represented as a table containing a column for each decision scenario, i.e., for each configuration of the variables on which it depends. The no-forgetting assumption, which implies that the decision maker always remembers all past observations and decisions, makes the policies grow exponentially with the number of variables in the ID. For human experts it is very difficult to understand the strategy contained in huge policy tables, not only for their size, but also because the vast majority of columns correspond to suboptimal or impossible scenarios and are hence irrelevant. This makes it difficult to extract the rules of action, to debug the model, and to convince the experts that the recommendations of the ID are reasonable. In this paper, we propose a method that presents the strategy in the form of a compact tree. It has been implemented in OpenMarkov, an open-source software tool for probabilistic graphical models. This facility was essential when evaluating an influence diagram for the mediastinal staging of non-small cell lung cancer; the optimal strategy, whose biggest policy table contained more than 15,000 columns, was synthesized into a tree of only 5 leaves.