RI: Small: A New Approach to Influence Diagram Evaluation

人工智能、运筹学和相关领域研究的一个中心目标是发展在不确定性条件下进行决策的算法方法。 这个项目考虑影响图，一个广泛使用的图形模型表示和解决不完美信息下的顺序决策问题。 影响图最初是为了提供比决策树更紧凑的决策问题表示而开发的，决策树的分支数量随着模型中变量数量的变化而呈指数爆炸。虽然影响图提供了一个紧凑的问题表示，解决影响图的标准算法并不表示在一个类似的紧凑形式的决策问题的解决方案。该项目通过引入更紧凑的决策策略图形表示来解决这一限制，该图形表示提高了求解影响图的算法的可扩展性，使人类用户更容易理解推荐的决策策略，并允许采用原则性方法进行近似。此外，该项目开发了一种新的方法来解决基于分支定界搜索的影响图，包括一种增量的概率推理方法。从这个项目开发的算法和软件工具将提高影响图的可扩展性和实用性，作为一种方法，在不确定的自动决策。 这些贡献将在影响图应用的许多学科中产生广泛的影响，包括医疗决策分析和支持、治疗计划选择、用户建模、信息检索、气候变化分析等。

A central goal of research in artificial intelligence, operations research, and related fields is the development of algorithmic approaches to decision making under uncertainty. This project considers influence diagrams, a widely-used graphical model for representing and solving problems of sequential decision-making under imperfect information. Influence diagrams were originally developed to provide a more compact representation of a decision problem than is provided by a decision tree, which suffers from an exponential explosion in the number of its branches as a function of the number of variables in the model. Although influence diagrams provide a compact problem representation, standard algorithms for solving influence diagrams do not represent the solution to a decision problem in a similarly compact form. This project addresses this limitation by introducing a more compact graphical representation of decision strategies that improves the scalability of algorithms for solving influence diagrams, makes it easier for a human user to understand the recommended decision strategy, and allows a principled approach to approximation. In addition, the project develops a new approach to solving influence diagrams based on branch-and-bound search, including an incremental approach to probabilistic inference.The algorithms and software tools developed from this project will improve the scalability and utility of influence diagrams as an approach to automated decision making under uncertainty. These contributions will have a broad impact in the many disciplines in which influence diagrams are applied, including medical decision analysis and support, therapy plan selection, user modeling, information retrieval, climate change analysis, and many others.