有向圖與條件獨立性(精選PPT)

有向圖與條件獨立性 1 2 條件獨立性 定義 直觀地講 知道了Z Y并沒有提供關(guān)于x的額外信息 2 2020 4 21 圖的幾個術(shù)語 圖 點集合和邊集合的二元組頂點 節(jié)點 vertex node 變量邊 edge 依存性無向邊 有向邊有向圖 directedgraph 所有的邊都是有向邊箭頭 原因變量 結(jié)果變量路徑 path 從節(jié)點Xi開始 中間不重復(fù)經(jīng)過節(jié)點到節(jié)點Xj的連續(xù)連接的邊集合 不管邊的方向有向路徑 路徑上所有的邊的方向都是朝向Xj有向環(huán) 從Xi到Xi的有向路徑 3 2020 4 21 有向圖的類型 有向有環(huán)圖 directedcyclicgraph 有有向環(huán)的圖也稱為非遞歸模型 nonrecursivemodel 有向無環(huán)圖 directedacyclicgraph DAG 沒有有向環(huán)的圖也稱為遞歸模型 recursivemodel X1 Y2 Y1 無環(huán)圖 X1 Y2 Y1 有環(huán)圖 4 2020 4 21 有向非循環(huán)圖 DAGs 一個有向圖是由節(jié)點集及連接一對有序節(jié)點的邊集組成的 一條開始和結(jié)束都在同一個變量處的有向路是一個圈 若一個有向圖沒有圈 則是非循環(huán)的 在這種情況下 稱這種圖為一個有向非循環(huán)圖或DAGS 5 2020 4 21 DAG的幾個術(shù)語 父節(jié)點 parents 結(jié)果變量的直接原因子節(jié)點 child daughter 原因變量的直接結(jié)果祖節(jié)點 ancestor 與某變量間有直接路徑的所有變量后裔節(jié)點 descendent 從某變量出發(fā)的直接路徑上的所有變量 所有的父節(jié)點都是祖節(jié)點所有的子節(jié)點都是后裔節(jié)點 6 2020 4 21 有向圖示例 X1 X1 X3 X4 X5 變量的Markov鏈有向圖 X1 Y2 Y5 Y3 Y4 Y1 有分支和擾動的樹形圖 7 2020 4 21 DAG描述的概率分布 對于一個DAG 總可以將所有節(jié)點排序 使得每個節(jié)點Xj的父節(jié)點都排在該節(jié)點之前DAG描述的概率分布為 8 2020 4 21 DAG概率函數(shù)的例子 超重 心臟病 吸煙 咳嗽 9 2020 4 21 Markov條件 令PAj表示節(jié)點Xj的父節(jié)點的集合 一個DAG描述的概率分布具有如下的條件獨立假TheMarkovconditionimpliesthatvariableswillbeunconditionallydependentontheirparentsbutconditionallyindependentofallothernondescendentvariables conditionalonparents 定理 令X Y和Z為互不相交的節(jié)點集 則當(dāng)且僅當(dāng)X和Y被Z有向分離 d separated 馬爾科夫決策方法 10 2020 4 21 有向分離準(zhǔn)則 一 Apathissaidtobed separated orblocked byasetofnodesZifandonlyifpcontainsachaini m joraforki m jsuchthatthemiddlenodemisinsetZ orpcontainsaninvertedfork orcollider i m jsuchthatthemiddlenodemisnotinsetZandsuchthatnodescendentofmisinZ如果一個路徑不是有向分離的 稱為有向連接的 d connected AsetZofvariablescorrespondingtonodesintheDAGissaidtobed separateasetofvariablesXfromYifandonlyifZblockseverypathfromanodeinXtoanodeinY 可用來推斷 起初相關(guān)的變量何時變得獨立起初獨立的變量如何變得相關(guān) 在給定原因條件下 其多個結(jié)果之間 如果沒有因果關(guān)系的話 是相互獨立的作為原因的多個因素 即使它們之間是相互獨立的 但是給定結(jié)果后 這些原因可能變得相關(guān)了很難想象 兩個原因相關(guān) 給定結(jié)果后 這兩個原因因素變得相互獨立了 11 2020 4 21 有向分離準(zhǔn)則 二 X Y Z X X Y Z Y Z W 1 當(dāng)Y不是一個相遇時 X和Z是有向連通的 但是它們在給定Y下是有向分離的 2 若X和Z在Y處相遇 則X和Z是有向分離的 但是它們在給定Y下是有向連通的 3 具有后裔節(jié)點的相遇與一般的相遇具有相同的結(jié)果 因此 在上面最后一個圖中 X和Z是有向分離的 但是它們在給定W下是有向連通的 12 2020 4 21 一個例子 外星人手表 遲到 得知你朋友已經(jīng)遲到一定會增加她被綁架的可能性 但是當(dāng)?shù)弥阃洶涯愕氖直碓O(shè)定好時 就會降低你朋友被綁架的可能性 因此 外星人和手表在給定遲到的條件下是相互依賴的 13 2020 4 21 馬爾科夫決策方法 馬爾科夫決策是一種風(fēng)險型決策 主要研究對象是一個運行系統(tǒng)的狀態(tài)和狀態(tài)的轉(zhuǎn)移 目的是根據(jù)某些變量的現(xiàn)在狀態(tài)及其變化趨向 來預(yù)測它在未來某一特定期間可能出現(xiàn)的狀態(tài) 從而提供某種決策的依據(jù) 基本方法是用轉(zhuǎn)移概率矩陣進行預(yù)測和決策 14 2020 4 21 轉(zhuǎn)移概率矩陣 設(shè)表示概率值 表示步轉(zhuǎn)移概率矩陣 則有 矩陣各行概率表示狀態(tài)經(jīng)過k步轉(zhuǎn)移到狀態(tài)后的概率 矩陣各行元素之和為1 即 15 2020 4 21 例子說明馬爾科夫決策方法的步驟 16 2020 4 21 一 建立轉(zhuǎn)移概率矩陣 根據(jù)上表建立得失的轉(zhuǎn)移概率矩陣 橫行表示各公司失去客戶到其他公司的概率 縱列表示各公司從其他公司得到客戶的概率 17 2020 4 21 二 利用轉(zhuǎn)移概率矩陣進行模擬預(yù)測 上例顯示8月1日各公司的市場占有率為0 22 0 49 0 29 預(yù)計9月1日各個公司的市場占有率的方法是將前一期的市場占有率乘以轉(zhuǎn)移概率矩陣 具體如下 若要預(yù)測k期的市場占有率 可用本期的占有率乘上轉(zhuǎn)移概率矩陣的k次方 18 2020 4 21 三 求轉(zhuǎn)移概率矩陣的穩(wěn)定狀態(tài) 只要轉(zhuǎn)移概率矩陣不變 不管市場占有率如何改變 最后總會達到穩(wěn)定狀態(tài) 這時市場占有率不再改變 稱為最后占有率 設(shè)ABC公司市場占有率分別穩(wěn)定在X1 X2 X3 因此有解得 19 2020 4 21 四 應(yīng)用轉(zhuǎn)移概率矩陣進行決策 假設(shè)A公司為提高市場占有率有2個方案 1 與B公司競爭 從流失到B公司的客戶中爭回5 轉(zhuǎn)移概率矩陣求得最后占有率為 20 2020 4 21 2 與C公司競爭 從流失到C公司的客戶中爭回5 轉(zhuǎn)移概率矩陣如下 求得最后占有率為若兩個方案費用相同 則A公司應(yīng)該選擇第一方案 如費用不同 則要比較凈盈