【文章內容簡介】 。 IAMB及其派生算法IAMB算法[12]首次發(fā)表于2003年，全名為Incremental Association Markov Blanket。它繼承了GSMB算法的兩步驟策略：先（貪婪）增長，后裁剪（假正元素）。裁剪階段兩者完全一致，增長階段存在一個區(qū)別：IAMB會對通過CI測試的候選元素（參考GSMB算法第5行）進行排序，挑選出“最可能”的候選馬爾科夫毯元素，即和目標變量條件依賴度最高的。雖然這個選擇過程依舊是貪婪決策，相比于GS更充分利用了當下的信息，因此降低了往添加假正元素的可能性。由于GSMB算法發(fā)表時是以學習貝葉斯網(wǎng)絡為目標，而IAMB是專門針對推導馬爾科夫毯提出的，所以后者在該方向的引用頻次和知名度更高。IAMB繼承了GSMB算法低數(shù)據(jù)效率的問題，例如，給定經(jīng)典的Alarm問題，當給定相同的訓練集大?。ɡ?000），IAMB算法輸出的馬爾科夫毯的平均準確率為49%，而IPCMB算法為99%[13]。IAMB的作者也意識到這個問題，提出了三個“改良”版本：InterIAMB、IAMBnPC和InterIAMBnPC。InterIAMB將增長裁剪兩個階段交替執(zhí)行，而原來的IAMB里，完全執(zhí)行完增長階段才開始執(zhí)行裁剪階段。IAMBnPC算法是將經(jīng)典的PC算法應用于裁剪階段，但它忽視了增長階段所獲得的有可能并不包含所有的元素，這將導致輸出仍然不完整。當將這兩個算法的思路合并后即為InterIAMBnPC，它的時間復雜度在這三個算法中最高。相比于IAMB，這三個算法的數(shù)據(jù)效率都有不同程度的提高，因此實際應用的準確率能得到提升，但是時間復雜度也有不同幅度的增加。 FastIAMBFastIAMB算法 [14]發(fā)表于2005年的ICDM年會，它實際上是InterIAMB的升級版本。相比于InterIAMB，該算法有兩個不同：n 條件獨立性檢查選擇了統(tǒng)計；n 增長階段里每個迭代選擇一個或多個變量添加到中。作者認為第二個策略的采用將提高時間效率，但這個更貪婪的策略將導致更多的假正元素被添加到，從而導致IAMB增長步驟已知的問題惡化 – 該步驟更早終止，且終止時包含更多的假正變量（自然包含更少的真元素）。 KIAMBKIAMB和PCMB（在下章節(jié)里介紹）在2007被同時發(fā)表在文獻[15]。其作者認為PCMB等（約束學習II類）算法所要求的忠實性假設過于嚴格，而IAMB算法的數(shù)據(jù)效率太低。KIAMB實質是IAMB的一種隨機版本，它允許算法使用者指定一個參數(shù)，該參數(shù)反映了對搜索貪婪度和隨機性所能接受的一個“度”。當時，KIAMB等價于IAMB，即在增長階段的每個迭代里總是選擇當下和條件相關性最強的元素。當數(shù)據(jù)樣本不充足時，這樣的決策顯然是有風險的。因此時，算法會從隨機選擇一個子集再執(zhí)行類似算法1第5行的CI測試，并基于測試結果決策。 IAMB等算法IAMB發(fā)表于2010年[16]，跟IAMB算法對比存在兩個差異點。其一是作者通過使用信息熵，而非條件互信息，來降低衡量兩個變量的條件獨立性計算量。其二是算法希望一次選取多個候選變量進入，例如和目標變量相關性最高的兩個變量，這和FastIAMB如出一轍。然而，為了降低風險，作者提出了參數(shù)（其實是門限值），當次相關變量和目標變量的相關性和最相關變量的相關性超過一定值時，方可同時被添加到。這個二次檢查的策略和KIAMB類似。盡管較IAMB有一定的改善，F(xiàn)astIAMB、KIAMB和IAMB并沒有在根本上解決此類算法的數(shù)據(jù)效率低的缺陷。4 約束學習II：基于局部條件獨立信息的搜索在IAMB算法的追隨者繼續(xù)沿著那條路徑前進的時候，有些人開始另辟蹊徑來解決IAMB類算法的低數(shù)據(jù)效率的問題。他們的工作基礎是貝葉斯網(wǎng)絡DAG的拓撲信息，特別是“截斷”兩個節(jié)點的割集（的信息）。雖然是和之間的最小割集，但對于單獨的和之間的割集往往遠比小，例如圖1的和的最小割集是空集，而包含六個元素。除了推導策略迥然不同，II類算法的輸出相比I類算法存在一個巨大的優(yōu)勢：能推導出更多的拓撲信息。I類算法僅僅告訴我們一個元素是否屬于，而II類算法能(1)區(qū)分目標變量的父子和配偶集合,(2)從父子集合里分離出部分孩子（節(jié)點）,(3)一部分結構。 MMPC/MB和HITONPC/MB算法MMPC/MB算法[17]發(fā)表于2003年的ACM KDD年會，其第一作者和IAMB的一致，這間接反映了該作者也意思到IAMB算法的局限。MMPC全稱是MaxMin Parents and Children，它的任務是推導特定變量的父子節(jié)點；MMMB的全稱是MaxMin Markov Blanket，即推導一個變量的馬爾科夫毯。MMMB依賴MMPC來完成馬爾科夫毯的推導，這也是第一次將馬爾科夫毯的推導分解成分別推導父子節(jié)點和配偶節(jié)點。這個拆分策略將避免或出現(xiàn)在CI測試里，有助于提高CI測試的可靠性，繼而讓基于CI測試的結果所做的決策（比IAMB等）更準確。HITONPC/MB算法[7]同樣發(fā)表于2003年，它的總體策略和MMPC/MB如出一轍，為了節(jié)省篇幅不再單獨熬述。MMPC/MB和HITONPC/MB都是針對馬爾科夫毯推導的重要嘗試和突破，但更復雜的啟發(fā)式策略也帶來了高的多的計算代價。然而，在2007年這兩個算法都被證明都無法恒保證輸出正確的馬爾科夫毯，有興趣的讀者可以參考文獻[15]里提供的一個反例。鑒于此，我們在此為了節(jié)約篇幅都沒有單獨給出兩個算法的偽代碼，但他們的主要流程被PCMB和IPCMB所繼承，讀者可以參考算法3（IPCMB）。 PCMB算法PCMB算法[15]最初發(fā)表在2007年的《Journal of Approximate Reasoning上》，它的全稱是Parents and Children based Markov Boundary。其作者同樣意識到IAMB及其衍生算法在實際應用中的局限，并充分認可MMPC/MB和HITONPC/MB的作者所提出從拓撲角度出發(fā)進行搜索策略的設計。雖然這個新的方向有貝葉斯網(wǎng)絡研究者所積累的大量理論依據(jù)，但MMPC/MB和HITONPC/MB兩個具體算法都存在設計缺陷，這無法保證它們恒輸出正確的結果。PCMB的作者首次在文獻[15]中給出了反例，因而他們提出的PCMB屬于“約束學習II”類已知發(fā)表的工作中首個能進行正確推導馬爾科夫毯的算法。PCMB算法類似MMPC/MB和HITONPC/MB，采用了分而治之的策略 – 分別學習父子節(jié)點和配偶節(jié)點。由于PCMB算法和隨后將介紹的IPCMB算法的主體架構相似，因此讀者可以參考算法3來了解其總體設計。PCMB算法和IPCMB算法的主要差別是RecognizePC（見算法2），該過程在原文獻中即GetPCD。RecognizePC負責推導一個變量的候選父子集合，有可能輸出后代節(jié)點。PCMB算法的RecognizePC實際是在IAMB的增長裁剪過程前增加一個在候選集合里進行“裁剪”的步驟，故總體上是SGS（ShrinkGrowShrink）。本質上，這是一個混合了后向和前向選擇的搜索策略。然而，過度“謹慎”的檢查導致PCMB算法時間復雜度甚高[10, 11]。算法2：RecognizePC（對應原PCMB文獻中的GetPCD）。輸入： 目標變量 候選鄰居 數(shù)據(jù)集/訓練集 顯著性門限值輸出：的候選父子集合01. 。 02. DO// 刪除中的假正03. FOR() DO04. 。05. FOR() DO06. IF()THEN07. 。 //添加最佳候選到08. 。 09. 。10. 。//從中刪除假正11. FOR() DO12. 。13. FOR() DO14. IF()THEN15. 。16. WHILE 在本輪循環(huán)有改變。17. RETURN 。 IPCMB算法IPCMB算法[18]最初發(fā)表在2007年的澳大利亞AI年會上，而提供了更完善證明的版本發(fā)表在2008年的加拿大人工智能年會上[10]。IPCMB全稱是Iterative ParentChild based search of Markov Blanket。它同PCMB一樣，基于拓撲信息設計，選擇了分而治之的策略，通過迭代的推導父子節(jié)點（這一更局部的信息）來完成馬爾科夫毯的推導。然而，在如何推導直接相連接的節(jié)點（父子節(jié)點）這個核心子策略上，IPCMB選擇了和PCMB完全不同的策略：PCMB采用的是前向選擇，而IPCMB采用的是后向選擇。PCMB的策略在上一節(jié)已經(jīng)有介紹，此處著重介紹IPCMB的后向選擇。，更詳細的討論可以參考Kamp。S的工作[2]。IPCMB（見算法3）是依賴RecognizePC過程（見算法4）來完成對父子節(jié)點的判斷。它的基本思路是當給定一個節(jié)點時，先假設其他的節(jié)點和都相連（即都為真的父子節(jié)點），隨后通過一系列的CI測試來刪除鄰居集合里的假正元素，直到?jīng)]有更多的CI測試可被執(zhí)行。與PCMB算法判斷一個元素是否為真的父子節(jié)點不同，判斷假正元素的條件更為簡單 – 只要存在一個關于節(jié)點和節(jié)點的割集，即可判斷為假正，并從里刪除。在判斷假正元素時，IPCMB的作者從空集合開始判斷其是否是和之間的割集；在第二個迭代里，允許割集合包含一個元素，并尋找可“割斷”的變量；以此類推，直到?jīng)]有更多的CI測試能夠被執(zhí)行。這個策略使得用于判斷假正的CI測試總是能夠基于最小的割集，充分保障了CI測試的可靠性。 算法3：IPCMB。輸入： 目標變量 數(shù)據(jù)集/訓練集 顯著性門限值輸出：的馬爾科夫毯01. ； //候選鄰居02. RecognizePC()。 //候選父子03. 。04. FOR()DO05. 。06. RecognizePC()07. IF () THE