Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

决策网络

决策网络(也称为影响图)是有限顺序决策问题的图形表示。决策网络在信念网络的基础上加入了决策变量和效用。决策网络扩展了单阶段决策网络以允许顺序决策。

来源:artint.info
简介

决策网络(decision networ):是最著名的贝叶斯网络/推理的概括,它代表一组变量及其通过映射的概率关系(也称为定向无环图);

决策网络(也称为相关图,决策图,影响图)是有限顺序决策问题的图形表示。决策网络在信念网络的基础上加入了决策变量和效用。决策网络扩展了单阶段决策网络以允许顺序决策。

【Decision Networks, https://artint.info/html/ArtInt_219.html  】

决策网络是定向无环图,具有三种类型(加上一个子类型)的节点和三种类型的节点之间的弧(或箭头)。

节点:

  • 决策节点(对应于要做出的每个决定)被绘制为矩形。
  • 不确定性节点(对应于要建模的每个不确定性)绘制为椭圆形。
  • 确定性节点(对应于特殊类型的不确定性,其结果在某些其他不确定性的结果也是已知时,确定性地已知)被绘制为双椭圆形。
  • 值节点(对应于可加性分离的Von Neumann-Morgenstern效用函数的每个分量)绘制为八边形(或菱形)。

弧:

  • 功能弧(以值节点结尾)表示可加性可分的效用函数的一个组件是其尾部的所有节点的函数。
  • 条件弧(以不确定性节点结束)表明其头部的不确定性在概率上以其尾部的所有节点为条件。条件弧(以确定性节点结束)表明其头部的不确定性在其尾部的所有节点上确定性地受到条件限制。
  • 信息弧(在决策节点中结束)表明在他们的头部做出的决定是用他们预先知道的尾部的所有节点的结果做出的。

给定一个结构合理的决策网络:

  • 决策节点和传入信息共同指出备选方案(当事先知道某些决策和/或不确定性的结果时可以做什么)
  • 不确定性/确定性节点和传入的条件弧共同模拟信息(已知的和他们的概率/确定性关系)
  • 值节点和传入的功能弧共同量化了偏好(事物如何相互优先)。

替代,信息和偏好在决策分析中被称为决策基础,它们代表任何有效决策情况的三个必要组成部分。

形式上,影响图的语义基于节点和弧的顺序构造,这意味着图中所有条件独立性的规范。该规范由贝叶斯网络的 d-分离标准定义。根据这种语义,给定其前一个节点的结果,每个节点在概率上独立于其非后继节点。同样,非值节点 X和非值节点 Y之间的缺失弧意味着存在一组非值节点Z,例如父节点 Y,给出 Z中节点的结果,使Y独立于 X.

关于度假活动决策的简单影响图。考虑一个简单的影响图,表示决策者正在计划他们的假期。

Image.jpg

  • 这里有1个决策节点(度假活动),2个不确定性节点(天气状况,天气预报)和1个值节点(满意度)。
  • 这里有2个功能弧(以满意度结束),1个条件弧(以天气预报结束)和1个信息弧(以度假活动结束)。
  • 以满意度结束的功能弧表示:满意度是天气条件和度假活动的效用函数。换句话说,如果他们知道天气是什么样的以及他们选择的活动是什么,这里的满意度就可以量化。 
  • 在天气预报中结束的条件弧表明他们相信天气预报和天气状况是可以相互依赖。
  • 在度假活动中结束的信息弧表示他们在做出选择时只会知道天气预报,而不是天气状况。换句话说,实际天气在他们做出选择后就会知道,只有预测是他们在这个阶段可以依赖的。
  • 在语义上也可以这么理解。例如,假设天气预报已知,度假活动独立于(与天气条件无关)。

信息价值的应用

上面的例子强调了影响图表在决策分析中表示极其重要的概念的能力,称为信息的价值。考虑以下三种情况;

  • 场景1:决策者可以在知道天气状况的情况下做出假期活动决定。这对应于在上面的影响图中从Weather Condition到Vacation Activity添加额外的信息弧。
  • 场景2:原始影响图如上所示。
  • 情景3:决策者在不知道天气预报的情况下做出决定。这对应于在上述影响图中从天气预报到度假活动中删除信息弧。

情景1是这种决策情况的最佳可能情景,因为他们在做出决定时不再对他们关心的事物(天气状况)有任何不确定性。然而,情景3是这种决策情况最糟糕的情况,因为他们需要做出他们的决定而没有任何暗示(天气预报),他们关心的事情(天气状况)也是未来才会变成现实。

通过获取新信息,决策者通常会从情景3转变为情景2,从而变得更好(绝对不会更糟)。他们应该愿意为这种行动支付的最多费用称为天气预报信息的价值,这基本上是关于天气状况的不完全信息的价值。

同样,决策者最好从方案3转移到方案1.他们应该愿意为此类移动支付的最多费用称为天气状况的完美信息的价值。

这个简单决策网络的适用性和信息概念的价值是巨大的,特别是在医疗决策时,大多数决策必须用关于他们的患者,疾病等的不完整信息进行做出决策。

发展历史

描述

决策网络最初是由决策分析师在20世纪70年代中期开发的,具有易于理解的直观语义。 它现在被广泛采用并成为决策树的替代方案,决策树通常受到每个变量建模的分支数量的指数增长的影响。 ID(influence diagram)直接适用于团队决策分析,因为它允许团队成员之间的信息不完全共享,以便明确地建模和解决。 决策网络的扩展也发现在游戏理论中当做游戏树的代替表示。

Judea Pearl(因通过概率和因果推理的算法研发在人工智能取得的杰出贡献,在2011年图灵获得者)在2005年《Influence diagrams—Historical and personal perspectives》中阐释:Influence diagrams 也就是决策网络源于图像模型,也可以认为是Wright 1921的路径图(path diagrams)工作的延伸。换句话说,Influence diagrams也可以认为是信任网络中的信息决策过程。(也就是后来的贝叶斯网络),它也是自动推理计算的重要的工具。

从路径图来说,它允许了决策网络割舍了功能线性模型和任意变量之间的关系。经济学家和分析师自从(Howard; Matheson; 1984/2005)的工作中就使用了这样的理念,也是比较早的决策网络的提出。非线性的决策网络(Judea Pearl,2000)如贝叶斯网络在1990年代中期也就出现了。在决策网络理念出现的10年之后。

Judea Pearl认为:在早起的1980年代,其实AI和决策分析有一些重合。在Judea Pearl在还没有提出树中的信任传播的概念的时候,斯坦福的Ron Howard研究组之前,听众不能理解为什么Judea Pearl强调计算特征:如自主特征,异步传播,这些也是大多数决策问题中的比较困难的任务 。

2000年,Judea Pearl在视觉感知中考虑了同步计算的问题,在很多前期工作的支持下,causal Bayesian network 在《Causality: models, reasoning, and inference》提出。

2005年, Howard, R. A., & Matheson, J. E. 对决策网络的基础理念进一步阐释。

之后也有很多对决策网络的改进,如Fuzzy influence diagrams《Fuzzy Influence Diagrams: An Approach to Customer Satisfaction Measurement》《Fuzzy evidential influence diagram and its evaluation algorithm》,它使用了一个无预测变量来展示各个节点之间的关系的一个网络。

【来源:wiki;
学界 | 谷歌新研究,自监督视频上色约等于目标追踪和姿态估计

主要事件

年份事件相关论文/Reference
1981Howard, R.A. and J.E. Matheson提出Influence diagrams" 的基础理念
1985Pearl提出贝叶斯网络的概念Pearl J. (1985). Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning. Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA. pp. 329–334.
2005  Howard, R. A., & Matheson, J. E. 对决策网络的基础理念进一步阐释Howard, R. A., & Matheson, J. E. (2005). Influence diagrams. Decision Analysis, 2(3), 127-143.
2008Kjaerulff, U. B., & Madsen, A. L.分析贝叶斯网络和决策网络Kjaerulff, U. B., & Madsen, A. L. (2008). Bayesian networks and influence diagrams. Springer Science+ Business Media, 200, 114.
2014Pearl, J.出版一本关于智能系统的概率推理的Pearl, J. (2014). Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier.

发展分析

瓶颈

在使用决策树的决策网络中,有如下一些问题:

考虑后果

决策树最有用的方面之一是它们会迫使用户考虑尽可能多的可能的决策结果。在不考虑后果范围的情况下制定时刻决策可能是危险的。决策树可以帮助您权衡一个决策对另一个决策的可能后果。在某些情况下,它甚至可以帮助您估算决策的预期收益。例如,如果用户创建与每个结果相关的所有结果和概率的美元价值估计,您可以使用这些数字来计算哪个初始决策将导致最大的平均财务回报。决策树提供了一个框架来考虑决策的概率和收益,这可以帮助用户分析决策,以便做出最明智的决策。

期望

使用决策树的一个缺点是决策,后续决策和支付的结果可能主要基于期望。在做出实际决策时,支付和由此产生的决策可能与用户计划的决策不同。可能无法计划因决策而可能产生的所有意外事件。这可能导致一个不切实际的决策树,可以指导您做出错误的决定。此外,意外事件可能会改变决策并更改决策树中的支付。例如,如果用户希望父母在决定上学时支付一半的学费,但后来发现用户将需要支付所有学费,那么您的预期收益将与现实大不相同。

复杂

当树中包含的决策和结果很少时,决策树相对容易理解。包含数十个决策节点(进行新决策的点)的大树可能价值有限。树中的决策越多,可能的预期结果就越不准确。例如,如果用户制作一张树来确定上大学的决定,那么你可能无法准确预测十年后你将获得超过10万美元的机会,但你可能能够准确估计离开大学后的收入。

未来发展方向

使用决策树的一个缺点是后续决策和支付的结果可能主要基于期望。然而,有很多后续决策的不可确定因素也是很大的,如何动态地加入网络也是可以考虑的一个部分。

对于复杂的决策网络,如何帮助研究人员或者用户更快速的理解也是一个可以研究的问题。

Contributor: Ruiying Cai

简介