這部分討論決策理論與 PGM 的關系，一個主要的思路就是將決策與 PGM 的 inference 完美的融合在一起。

MEU

為了引入決策理論中的 maximum expected utility 原則，我們先引入一些概念：

• lottery（彩票）是一個結果與概率的映射關系，用戶對不同的 lottery 的偏好能顯示其對風險的不同評估方式
• 決策問題一般有一組結果 ，一組行為 ，結果的概率模型，即給定某個行為后，得到結果上的一個分布（lottery），一個 utility function，它給出用戶對不同結果的偏好

所謂的 MEU 原則是

事實上也有做其他的選擇的原則的，比如 min max risk，最大風險最小化

我們這里只考慮前者。那么一般說來合理的 utility function 要求滿足，

• orderability，即對任意兩個 lottery，或者選其一或者兩個傾向一樣
• transitivity，即如果兩兩比較 ，則有
• continuity，即若 ，則存在 使得 與 compound lottery
• monoticity，若 ，則
• substitutability，若 ，則這兩個 lottery 可替換：
• decomposability，

可證明對滿足以上六點的 lottery 存在 utility function 使得 當且僅當 。這里 。

一般說來一個 utility function 對 money 的曲線一般是單調增，在正象限是 concave 的，表示 diminishing utility，這一般表示的是 risk averse：即選擇帶隨機的收益和無隨機的收益（兩者平均 utility 相等）兩種 lottery 的時候會傾向后者。與此相反有 risk seeking 和 risk neutral，前者是 convex 的而后者是線性函數。但是很多時候人并不是一成不變或者一味有理智的，他們的 utility function 可能會變化。但是實際情況下的 outcome 可能并不是 money 這么簡單，我們往往面對的是多個 attribute 造成的影響建立對應的 utility model。簡單的說這是一個多元函數如何能寫出表達式的問題。事實上，如果這些 attribute 滿足某些性質，我們可以將這個函數 decompose 成為若干 attribute 上各自的 utility。為此我們引入一些概念，

• 如 是 attributes 的一個 partition，稱 是 preferentially independent of ，當且僅當對任意 ，給定 時有 ，當且僅當給定 時也有
• 以上是說這個 attribute 的 partition 之間有這樣一個無關性，其中一個取定不會影響另外一個的 preference，我們可以將其延拓到分布上，為此引入 conditional preference structure，當 對任意 成立時，記為
• 這樣我們就可以定義 utility independence，即對任意 如果兩個 lottery 的 preference 是恒定的

可以證明：如果 attributes 是 utility independent of ，當且僅當 。這個定理的推論是，如果每個子集 滿足它和它的補集是 utility independent 的，當且僅當存在以下分解

或者

這也就是說 utility function 的最終形式大約是一個關于 attributes 子集上 utility function 的 multilinear function。如果我們只考慮相加這種形式（后者）往往會降低我們的 utility function modeling power，但是它也有一些自己的特點，比如所謂 additive independence，就是說對任意的 attribute margin 來說發現兩個 lottery 的 preference 都是一樣的，這種情況下的 utility function 必然能寫成每個 attribute 上 utility function 的和。類似我們可以定義 conditional additive independence，這是在給定某個 attribute 值（如 ）的情況下任兩個 lottery 的 preference 在任意兩個 margin 上（如 ）是一致的，這時的 utility function 會 decompose 成為幾個 utility function，即 。事實上我們甚至可以用 MRF 表示 CAI-map，這樣 utility function 的 decomposition 也會變成對應幾個 clique 上 utility function 的和。事實上上述要求 disjoint attribute 可以被松弛，這稱為 generalized additive independence，對應情況下的 utility function 分解仍然成立。

一個基本的求解 MEU 的策略是使用 decision tree，根據每個隨機變量的取值進行分叉，最后得到每個 leaf 上的 utility function value，這樣一來最優的 decision 就是能導致走到 utility 最高的 leaf 上的策略。而另一種也就是前面提到對 BN 的擴展是在 BN 中加入 decision variable（對應 action）和 utility variable（對應最終的 utility），而原先的 r.v.s 稱為 chance variable。這個新的圖模型稱為 influence diagram。很快我們就可以發現 MEU 實際上就是要求 或者對應有一定的 observation 時要求 。這里 utility function 是對應節點 的父節點的（確定性）函數。影響 action variable 的 edge 也叫 information edge，而我們需要的 decision rule 。通常我們求解 MEU 策略和前面的 inference 過程也呈現了某種相似之處。我們分幾種情況討論

• 如果沒有 decision variable，我們只需要 marginalize 所有的東西就得到了 expected utility
• 如果只有一個 decision variable，記為 ，那么我們可以 marginalize 掉除了 以外的東西，即得到的函數為 ，這樣取
• 如果有多個，可以采用 iterated optimization algorithm，即每次固定別的 decision rule，更新當前的，這種算法在某些特定條件下能收斂到全局最優，一個充分的條件是滿足 perfect recall，即存在某個 r.v.s 的順序使得按照這個順序走的時候后面的 decision variable 的 parent 必須在之前的 decision variable 及其 parent 里面。

為了更好地刻畫什么時候 local optimal 的 decision 能夠導致 global 的 optimal decision，我們需要研究改變某個 decision rule 時如何會不影響到其他的 decision rule（這樣各自保持最優），這樣以上 iterated optimization algorithm 就能減少迭代次數。為此引入了 strategically relevant 和 s-reachability 的概念，并證明兩者的等價，可以證明滿足 perfect recall 性質對應的 relevance graph 一定是 acyclic 的。那么實際上如果 relevance graph 本身是 acyclic 的直接用 iterated optimization algorithm 也定能獲得最優解。

在 marginalize 其他的 r.v.s 的時候注意到 information edge 的作用（傳遞有用的 message），而某些信息其實是對 MEU 無用的，這一般是不存在一條 active trail 會產生的現象（此時稱為 irrelevant information edge），去掉 irrelevant edge 不會改變 optimal decision。

一個很重要的問題是我們是否能通過某種方式確定某個觀測對決定的影響。對單個 decision observation 而言，我們可以使用所謂 value of perfect information 來衡量，即增加一條 information edge 從該 r.v. 到 decision variable 后 MEU 的變化，記為 ，可以證明這個值不小于零。也就是說知道更多決策不會變差。多個的情況會變復雜很多，一般只能用近似。

——————
And it came to pass at that time, that Abimelech and Phichol the chief captain of his host spoke to Abraham, saying, God is with you in all that you do:

轉載于:https://www.cnblogs.com/focus-ml/p/3775472.html

總結

以上是生活随笔為你收集整理的pgm17的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。