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

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