基于評分緩存的節點序空間下BN結構學習

關鍵詞：貝葉斯網絡；結構學習；節點序；局部搜索；迭代重啟

中圖分類號：ＴＰ１８１ 文獻標志碼：Ａ DOI：１０．１２３０５／ｊ．ｉｓｓｎ．１００１-５０６Ｘ．２０２４．１２．１８

０引言

貝葉斯網絡（Ｂａｙｅｓｉａｎｎｅｔｗｏｒｋ，ＢＮ）是一種結合概率論與圖論的數學模型，是目前不確定知識表達和推理領域最有效的工具［１］，現已被廣泛應用于故障診斷［２３］、可靠性評估［４５］、醫學診斷［６７］、行為決策［８］等方面。目前，ＢＮ 憑借其良好的噪聲數據處理能力和模型可解釋性在基因調控領域［９］備受關注，但是基因調控的動態性導致ＢＮ 應用受限。ＢＮ學習分為結構學習和參數學習，而參數學習［１０］的精度依賴于準確的ＢＮ結構。在實際中，僅依靠專家知識建模具有主觀性和局限性，因此充分利用數據學習ＢＮ 結構是至關重要的［１１］。

根據方法策略的不同，ＢＮ 結構學習（ＢＮ ｓｔｒｕｃｔｕｒｅｌｅａｒｎｉｎｇ，ＢＮＳＬ）方法［１２］主要分為基于依賴分析的方法、基于評分搜索的方法和混合方法。基于依賴分析的方法［１３１４］從ＢＮ 的語義出發，利用統計或信息論的方法定量地分析變量之間的獨立關系來確定網絡結構。基于評分搜索的方法［１５１６］則將ＢＮＳＬ視為組合優化問題，確定合適的評分函數和搜索策略，尋找評分最高的網絡結構。混合方法［１７１８］融合了前兩類算法的優勢，通過條件獨立性測試縮小搜索空間，然后采用評分搜索找到最優的網絡結構。基于依賴分析的方法和混合方法均需要大量的條件獨立性測試，存在誤差傳播問題。

根據搜索空間的不同，基于評分搜索的方法又分為基于有向無環圖（ｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇｒａｐｈ，ＤＡＧ）空間［１８２０］、基于等價類空間［１５］和基于節點序空間［２１２５］的搜索方法。基于節點序空間的搜索方法與前兩類方法相比，搜索空間縮小，計算成本降低，全局搜索步驟增加，避免了大量無環檢測［２１］，進一步簡化了搜索復雜度。基于節點空間的搜索方法通常采取迭代局部搜索（ｉｔｅｒａｔｅｄｌｏｃａｌｓｅａｒｃｈ，ＩＬＳ）的啟發式策略［２６］，在可行時間內找到更優的網絡結構，尤其在大規模網絡中，具有出色的學習效率。因此，基于節點序空間的評分搜索算法是當前ＢＮＳＬ算法的前沿方向［２７３２］。

近年來，基于節點序空間的評分搜索算法得到眾多國內外學者的關注，許多算法也隨之應運而生。Ｔｅｙｓｓｉｅｒ 等［２１］首次提出脫離傳統的ＤＡＧ空間、在節點序空間搜索的定向搜索（ｏｒｄｅｒｉｎｇｂａｓｅｄｓｅａｒｃｈ，ＯＢＳ）算法。該算法在節點序的交換鄰域內使用爬山搜索策略。交換算子盡管簡單高效，卻對搜索鄰域有所限制，存在評分低的弱點。Ｓｃａｎａｇａｔｔａ等［２２］提出的ＡＳＯＢＳ （ａｃｙｃｌｉｃｓｅｌｅｃｔｉｖｅＯＢＳ）算法放松節點序的一致性準則，只要不引入有向環，就允許引入節點間的有向邊。Ｌｅｅ等［２３］提出的插入算子和Ｓｃａｎａｇａｔｔａ等［２４］提出的窗口算子，試圖進一步擴大搜索鄰域，但是漫無目的地搜索遍歷具有隨機性，產生大量的計算浪費問題。王海羽等［２５］提出基于節點塊序列的ＮＣＳＣ （ｎｏｄｅｃｈｕｎｋｓｅｑｕｅｎｃｅｃｏｎｓｔｒａｉｎｔｓ）的ＢＮ 構建算法構建評分定向支撐樹結構，得到節點塊序列，通過Ｋ２ 算法確定網絡結構后完成非法結構修正。Ｗａｎｇ 等［３２］提出的ＰＳＣＯＢＳ （ｐｒｉｏｒｉｔｙｉｎａｓｃｏｒｅｃａｃｈｅＯＢＳ）算法通過基于評分緩存的直接插入算子，逐個遍歷搜索固定深度的候選父集合，耗時長且缺少優化機制。

基于節點序空間的評分搜索算法通常使用ＩＬＳ方法，雖已在評分和時間方面取得卓越成效，但仍存在局部最優和收斂緩慢等問題。產生這些問題的主要原因有：

（１）局部搜索策略采用遍歷插入的方式，搜索半徑小，調整節點少。搜索算子的隨機性和盲目性，將限制局部搜索鄰域，容易使算法陷入局部最優解，且造成大量的計算浪費。

（２）迭代重啟策略通常采用隨機擾動，擾動程度將直接影響跳出局部最優的效果。該策略不能保證搜索進度被不斷推進，且過度擾動有時會產生負面效果，獲得質量更差的解，無法優化當前解。

針對以上問題，本文的主要貢獻如下：

（１）受評分緩存的無損刪減特性啟發，提出一種基于評分緩存（ｇｕｉｄｅｄｂｙｓｃｏｒｅｃａｃｈｅ，ＧＢＳＣ）的ＯＢＳ算法（以下簡稱ＧＢＳＣ算法），采取定向優先搜索策略和次優解的容忍策略，在評分緩存指引下，有效避免搜索的盲目性，使節點序向更高質量的方向更新收斂。基于評分緩存的優先級順序，選擇性地插入候選父集合，通過自適應的局部搜索深度參數，搜索其縱向插入鄰域，獲得評分最高的候選節點序。

（２）受ＤＡＧ空間、等價類空間與節點序空間相通的啟發，提出一種基于等價類深度優先（ｄｅｐｔｈ-ｆｉｒｓｔａｎｄｅｑｕｉｖａｌｅｎｔｃｌａｓｓ，ＤＦＥＣ）的重啟算法，采取轉換搜索空間策略。結合ＤＡＧ空間、等價類空間與節點序空間的三重優勢，確保局部最優節點序都能得以優化提升。將所得局部最優節點序對應的網絡結構轉化為其等價結構，再使用深度優先搜索遍歷該等價結構，得到新的節點序，并以此為始，重新迭代搜索。

（３）以ＧＢＳＣ 算法為局部搜索過程，使用軟啟動下的ＤＦＥＣ算法，得到兩者結合的ＩＬＳ算法ＧＢＳＣ-ＤＦＥＣ （簡稱ＧＢ-ＤＦ），進一步優化評分結果和加快收斂速度。

在運行時間方面，表中算法運行時間小于０．１ｓ，均記為０。ＯＢＳ算法的運行時間均值最小，這是由于ＯＢＳ算法操作簡單，復雜性小。對于小規模的Ａｓｉａ網絡，少量的局部操作就可以尋得最優節點序，因此所有算法的運行時間均為０。而對于中、大、特大規模網絡，ＧＢＳＣ 算法的運行時間均值僅次于ＯＢＳ 算法和ＩＮＯＢＳ 算法，這是由于ＯＢＳ、ＩＮＯＢＳ和ＷＩＮＯＢＳ算法的搜索算子通過規律性地遍歷搜索鄰域，在評估候選節點序時，可以避免部分節點的多次家庭評分計算，節省大量的時間開銷。在樣本大小不同時，與同為插入多個節點的ＷＩＮＯＢＳ 算法相比，ＧＢＳＣ 算法的運行時間均值分別最多縮短８８．１％、７７．１％、７９．８％，分別最少縮短２７．０％、２４．１％、３６．９％。與評分優勢相媲美的ＰＳＣＯＢＳ算法相比，ＧＢＳＣ算法的運行時間均值分別最多縮短４１．３％、３４．９％、２９．５％，分別最少縮短０．９％、４．４％、１．７％。隨著節點數目增加，網絡規模越大，ＧＢＳＣ 算法運行時間改善越顯著。因此，ＧＢＳＣ 算法具有明顯的時間優勢，大大降低了搜索過程的時間復雜度。

本文從綜合評分和時間兩個方面，說明了ＧＢＳＣ 算法在明顯改善搜索速度的同時，小幅提高了評分結果，可以在更短時間內找到評分更高的節點序。這驗證了該算法的可行性和高效性，提供了解決評估候選節點序搜索成本高和搜索算子盲目性強的問題的新方向。

３．５迭代算法的結果分析

圖７～圖９分別給出３ 種樣本大小下現有迭代算法與ＤＦＥＣ算法隨迭代次數變化的ＢＩＣ 評分均值曲線及其標準差。分析４種算法的ＢＩＣ評分變化趨勢可知，在整個迭代過程中，ＤＦＥＣ 算法的評分曲線均位于ＩＯＢＳ、ＩＡＳＯＢＳ 和ＥＳＴＯＢＳ算法曲線的上方，這說明ＤＦＥＣ 算法收斂穩定性強，而且優勢明顯。在樣本大小不同的所有網絡中，ＤＦＥＣ算法在１～１０次迭代過程中，評分增長迅速，而在１０～１００次迭代過程中，評分僅在小范圍內提高，處于穩定狀態。ＩＡＳＯＢＳ算法最少需要２０次迭代才可達到穩定狀態，而多數情況為在１～５０次迭代過程中評分緩慢提高，最終收斂到穩定狀態。對于３ 種樣本大小下的中／小規模網絡，ＩＡＳＯＢＳ和ＥＳＴＯＢＳ 算法的評分變化趨勢相近，而隨著節點數目增加，ＥＳＴＯＢＳ 算法變得難以收斂，明顯差于ＩＡＳＯＢＳ算法。ＩＯＢＳ算法則是在１～１００次迭代過程中評分不斷攀升，難以收斂。隨著網絡規模增大，ＩＯＢＣ算法的收斂速度減小。在不同樣本大小下，ＤＦＥＣ算法前１０次迭代的評分均值增量最多分別為ＩＡＳＯＢＳ算法的１．７、１．５、１．４倍，最少分別為１．４、１．３、１．４ 倍。ＤＦＥＣ 算法進一步跳出局部最優，促使局部搜索過程快速收斂，趨于評分更高的穩定狀態。

分析４種算法的最終ＢＩＣ 評分及標準差可知，ＤＦＥＣ算法評分曲線的終值明顯優于其他３ 種算法。在多數中／小規模網絡中，ＩＡＳＯＢＳ 和ＥＳＴＯＢＳ 算法評分曲線的終值相交，具有相近的評分結果。而在多數大規模網絡中，ＩＡＳＯＢＳ算法評分結果明顯優于ＥＳＴＯＢＳ 算法。除Ｃｈｉｌｄ網絡外，ＩＡＳＯＢＳ算法的評分曲線均高于ＩＯＢＳ 算法，這說明ＩＡＳＯＢＳ算法采用ＡＳＯＢＳ算法優化局部搜索結果，在一定程度跳出局部最優，評分結果優于ＩＯＢＳ算法。在樣本大小不同時，與ＩＡＳＯＢＳ算法相比，ＤＦＥＣ 算法學到最優節點序與初始節點序的評分均值增量分別最多提高２０．１％、２０．１％、１６．２％，分別最少提高９．９％、１１．０％、１２．５％。隨著網絡規模增大，ＤＦＥＣ 算法的評分優勢尤為明顯。尤其對于Ｗｉｎ９５ｐｔｓ、Ｐａｔｈｆｉｎｄｅｒ和Ａｎｄｅｓ網絡，ＤＦＥＣ 算法最終評分優勢格外明顯。ＤＦＥＣ 算法采用等價類轉換策略和ＤＦＳ 法優化局部搜索結果，使得最終評分結果均高于ＩＯＢＳ、ＩＡＳＯＢＳ和ＥＳＴＯＢＳ算法，且魯棒性強，對于初始節點序的依賴性低。對于Ａｓｉａ網絡，４ 種算法評分的標準差最大，這是由于該網絡規模小，節點數目少，隨機生成的初始節點序以極大概率與真實網絡一致。隨著網絡規模增加，整體標準差減小。

本文從綜合收斂速度和最終評分兩個方面，驗證了ＤＦＥＣ算法在較少迭代次數內，可尋得更高評分的節點序，收斂速度更快，明顯優于現有的迭代重啟算法，提供了解決推動局部搜索進度難的問題的新方向。

３．６迭代局部搜索算法的結果分析

表４和表５列出了３種樣本大小和９個基準網絡下７種算法的ＢＩＣ評分均值、標準差。根據加粗數據可以直觀地看出，在２２種類型數據集下，ＧＢ-ＤＦ 算法取得更高的評分均值，具有明顯的評分優勢。在樣本大小不同時，與最著名的近似學習算法ＰＣ-Ｓｔａｂｌｅ、ＧＦＣＩ、ＭＭＨＣ 相比，ＧＢ-ＤＦ 算法均有更高的評分均值和更低的標準差，評分均值分別最多提高４３．２％、５０．１％、５２．７％。在樣本大小不同時，與現有主流的近似學習算法ＳａｉｙａｎＨ、ＦＧＥＳ、ＭＡＨＣ 相比，在大多數類型數據集下，ＧＢ-ＤＦ算法均有更高的評分均值和更低的標準差，評分均值分別最多提高１２．１％、１２．０％、１２．８％。雖然ＧＢ-ＤＦ 算法在３種樣本的Ａｎｄｅｓ網絡中評分均值比ＭＡＨＣ算法分別低１６９．３、５５２９．７、１８２９７．２，但是整體的評分優勢依然明顯。表４ 和表５ 中，“'”表示ＧＢ-ＤＦ 算法的評分結果與該算法相比具有顯著改善；ＮＡ 表示該算法在相同類型數據集下有大于１０組實例無法輸出結果。

對于Ａｎｄｅｓ網絡，ＳａｉｙａｎＨ 算法復雜度高導致內存不足，無法完成尋優。與之不同的是，對于大規模的網絡，ＧＢ-ＤＦ算法總是可以高效地給出最優解，克服內存不足的問題。從統計測試的角度分析，ＧＢ-ＤＦ算法與現有的６ 種結構學習算法相比，分別在２７、２４、２７、１４、２４ 和１７種類型數據集中評分顯著改善，評分明顯提高的比例達到了至少５８．３％ 。這說明ＧＢ-ＤＦ 算法具有超強的學習效率，不易受樣本數據集的影響，具有極強的魯棒性和評分優勢。

表６列出３種樣本大小和９ 個基準網絡下７ 種算法的ＴＰＲ 均值和標準差。根據加粗數據可以直觀地看出，ＧＢ-ＤＦ算法在中／小規模網絡和樣本量較少情況下，ＴＰＲ指標具有一定的優勢，可以較好地找到真實網絡中存在的有向邊。在樣本大小不同時，ＧＢ-ＤＦ算法分別在其中６、７和５個網絡中取得最高的ＴＰＲ 均值，說明ＧＢ-ＤＦ 算法學到的網絡結構的精度極高，學到的有向邊與真實網絡的匹配度最優。與基于評分搜索的方法ＭＡＨＣ 相比，在樣本大小不同時，ＧＢ-ＤＦ 算法除Ｗｉｎ９５ｐｔｓ、Ａｎｄｅｓ網絡外大多具有更優的ＴＰＲ 均值。尤其在Ｃｈｉｌｄ、Ｉｎｓｕｒａｎｃｅ、Ｐａｔｈｆｉｎｄｅｒ網絡中，ＧＢ-ＤＦ算法更是優于基于依賴分析的方法和混合方法。ＴＰＲ 值高，表示真實網絡的有向邊被學到的比例大，與真實網絡的結構匹配程度更優。

表７列出３種樣本大小和９個基準網絡下７種算法的犉１分數均值和標準差。根據加粗數據可以直觀地看出，ＧＢ-ＤＦ算法在中／小規模網絡下，犉１分數具有一定的優勢。在樣本量大小為１０００和５０００時，ＧＢ-ＤＦ算法在其中６個網絡中取得最高的犉１ 分數均值，說明ＧＢ-ＤＦ 算法學到的網絡結構的精度極高，與真實網絡的擬合程度最高。在樣本量大小為10000時，ＧＢ-ＤＦ算法在其中４個網絡中取得最高的犉１分數均值，雖然沒有明顯的絕對優勢，但與６ 種對比算法相比，保持了中等偏上的水平。與現有主流的ＳａｉｙａｎＨ、ＦＧＥＳ、ＭＡＨＣ 算法相比，分別在２０、２２、１９ 種類型數據集中，ＧＢＤＦ算法的犉１分數均值更高，分別最多提高了５７．０％、１３４．８％、３１．８％，最少提高了０．９％、１．０％、１．２％。這是由于基于評分搜索的方法以評分作為唯一評價指標，追求的是與數據的擬合程度。與基于評分搜索的方法不同，基于依賴分析的方法以結構差異性作為主要評價指標，更側重于與真實網絡的差異性。這類算法通過條件獨立性測試確定出節點之間是否存在邊，從而構建出學到的網絡結構。同樣地，大多數混合學習方法也采用條件獨立性測試確定出初始網絡的骨架。但是，在實驗中采樣生成的數據集并不能完全反映真實網絡的情況，實際生活中的數據集大多都沒有公認的基準網絡，更需要從數據中挖掘出變量之間潛在的相關性。因此，與基于依賴分析的方法和混合方法相比，大多數基于評分搜索的方法在圖精度指標上效果較差，評分結果更優。

總體而言，ＧＢ-ＤＦ 算法在大多數數據集中具有更高的ＢＩＣ評分，在樣本量少或中／小規模網絡中具有更優的圖精度結果。同時，在大規模網絡中，ＧＢ-ＤＦ 算法可以有效地給出最優解，解決了從數據中學習大規模ＢＮ 的實際難題。

４結束語

針對盲目搜索造成計算浪費和評分低的問題，本文采取定向優先搜索策略和次優解的容忍策略，提出ＧＢＳＣ算法。通過一種選擇插入算子，在評分優先級指引下，通過自適應的局部搜索深度，搜索縱向插入鄰域，確保局部搜索朝著質量更高的最優節點序前進。針對搜索陷入局部最優和收斂速度慢的問題，本文采取轉換搜索空間策略，提出基于等價類深度優先的迭代算法ＤＦＥＣ。結合ＢＮ 特有的結構等價性，將搜索到的局部最優結構轉化為其等價結構，通過ＤＦＳ法遍歷為新的節點序，重新迭代搜索，累積每次搜索的進度，加快收斂速度，提高學習效率。實驗結果表明，ＧＢＳＣ算法在小幅提高評分的基礎上，搜索速度明顯改善。ＤＦＥＣ迭代算法在顯著提高評分的基礎上，收斂速度加快。與現有主流的結構學習算法相比，結合兩者的ＧＢ-ＤＦ 算法具有明顯的評分優勢。

雖然本文的算法已經具有出色的學習效率，但是仍然存在待改進的問題：本文隨機選取初始節點序，未加以優化設定；本文的圖精度優勢并不明顯，如何進一步改善基于評分搜索方法的圖精度結果，將是未來主要的兩個研究方向。

作者簡介

高曉光（１９５７—），女，教授，博士，主要研究方向為貝葉斯網絡學習、航空火力控制與作戰效能。

閆栩辰（１９９９—），女，碩士研究生，主要研究方向為貝葉斯網絡結構學習。

王紫東（１９９７—），男，博士研究生，主要研究方向為貝葉斯網絡結構學習、因果發現。

劉曉寒（１９９７—），男，博士研究生，主要研究方向為貝葉斯網絡結構學習。

馮奇（１９９９—），男，碩士研究生，主要研究方向為時空數據建模。