机器学习&数据挖掘笔记_PGM练习六：制定决策


前言：

　　本次实验是将一些简单的决策理论和PGM推理结合,实验内容相对前面的图模型推理要简单些。决策理论采用的是influence diagrams，和常见图模型本质一样，其中的决策节点也可以用CPD来描述，做决策时一般是采用最大期望效用准则(MEU)。实验内容参考参考的内容是coursera课程：Probabilistic Graphical Models中的assignment 5. 实验code可参考网友的:code.

 

　　实验中一些函数简单说明：

　　Fnew = VariableElimination(F, Z):

　　给定factorlist F和需要消除的变量集Z，采用sum-product的方法消除这些变量后得到factor集Fnew.内部需调用函数EliminateVar()。

　　EU = SimpleCalcExpectedUtility(I):

　　实验1的内容。I为influence diagrams中的所有factor,包含I.RandomFactors、 I.DecisionFactors、 I.UtilityFactors三种。计算时可以把RandomFactors和DecisionFactors结合在一起，看出是一个BN,然后对该BN进行变量消除，将那些不是效用节点父节点的变量消除掉，得到的factor中就只包含效用节点父节点了。

最后将其与UtilityFactors相乘就可以得到期望效用了，计算公式如下：

  

　　EUF = CalculateExpectedUtilityFactor( I ):

　　实验2的内容。EUF是指期望效用factor. 将前面的EU计算公式变形后如下：

    

　　而所求的EUF就是公式中的：

　　注意与实验1中的SimpleCalcExpectedUtility()区分开来，这里是消除掉与决策节点无关的那些变量(实验1消除的是与效用节点无关的变量)。所以EUF中的var只剩下决策节点及其父节点。

　　[MEU OptimalDecisionRule] = OptimizeMEU( I ):

　　实验3的内容。求的MEU为最大期望效用。除决策factor中的变量外，其它变量组合的每一个assignment下，决策D下的不同决策将得到不同的效用，此

assignment下当然是取效用最大的那个决策。因此这样就好构成一个新的factor,为OptimalDecisionRule.factor中所有的val之和就为MEU. 该函数内部需要调用CalculateExpectedUtilityFactor().

　　[MEU OptimalDecisionRule] = OptimizeWithJointUtility( I ):

　　实验4的内容。该实验处理参数和实验3一样，不同的是这里需要处理有多个效用节点的情形。因为效用值具有可加性，所以只需将这些效用节点所在的factor相加起来构成一个新的效用factor,然后直接调用OptimizeMEU()输出就ok了。

　　[MEU OptimalDecisionRule] = OptimizeLinearExpectations( I ):

　　实验5的内容。所完成的功能和实验4是一样的，函数接口也相同，只是采用的方法不同。实验4中是先将所有的效用factor相加，然后采用实验3的函数来计算。而实验5是直接将效用计算公式变形，如下：

 　　

　　先将EUF整合，然后采用类似OptimizeMEU()的方法来求解。

 

　　相关知识点:

　　Arrhythmogenic Right Ventricular Dysplasia (ARVD): 心律失常性右室心肌病

　　implantable cardioverter defibrillator(ICD):植入型心律转复除颤器,与手术治疗ARVD有关。

　　ARVD的influence diagrams如下：

    　　

　　其中的ARVD变量节点为X，其表示是否得有ARVD;它受先验X3影响;对ARVD的一些观察结果用T表示;决策变量为D(有时候也用A表示),决定是否进行ICD手术，

它与T相关;节点O为是否出现bad outcome,由X和D决定;最后的效用节点D由O和D决定。

　　简单决策包括下面几个部分：一个动作序列A,一般用矩形表示;一个状态序列X，一般用椭圆表示;一个分布P(X|A);一个效用函数U(X,A);效用节点U一般用菱形表示。

　　Expected utility(期望效用)表示做出某个决策后的期望效用，效用值不一定是概率，它是一个实数，可以为负。其计算公式如下：

   

　　MEU(最大期望效用):也就是说做出某个决策后得到的效用最大。此时的决策a计算公式为：

    　　

　　Information edge：指那些与动作节点相连的状态节点之间的edge.这些information edge构成了一个决策规则,用CPD来描述。有information edge的期望效用计算

公式为：

 　

　　对应的最大期望效用计算公式为：

 　

　　决策理论可以将PGM中的一些inference方法引进来。

　　多属性效用函数(Multi-Attribute Utilities):通常情况下效用值受多个变量影响，可以将这些变量整合到一个效用函数中。关于多属性效用函数更详细的理解可参考网友demonstrate 的 blog：PGM 读书笔记节选（十七).

　　效用不能单纯从概率上来看，效用函数应该能体现用户对结果的偏好，它一般需考虑做决策时的风险。

　　VPI(value of perfect information ):增加一条information edge到决策变量前后的MEU变化量。VPI>=0成立。

 

　　参考资料：

       实验code可参考网友的:code

　　coursera课程：Probabilistic Graphical Models 

       Daphne Koller，Probabilistic Graphical Models Principles and Techniques书籍第22章

       网友demonstrate 的 blog：PGM 读书笔记节选（十七)

 

作者：tornadomeet
出处：http://www.cnblogs.com/tornadomeet 欢迎转载或分享，但请务必声明文章出处。
新浪微博：tornadomeet,欢迎交流！


0