基于課程學習權重集成的貝葉斯結構學習算法研究

劉凱越，周鋆

國防科技大學 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073

貝葉斯網絡(Bayesian network, BN)，又稱信念網絡，在1985 年由Pearl[1]首先提出，是一種模擬人類推理過程、處理不確定性知識的一種圖模型。BN 通過有向無環(huán)圖和條件概率表可以清晰表示出變量之間的關系，幫助進行決策，為不確定性推理體系提供強有力的工具。目前，BN 已成功地應用于概率推理和因果建模的各種任務，同時在風險評估[2]、故障診斷[3]、決策系統(tǒng)[4]、基因序列分析、生物醫(yī)學圖像處理和疾病預測[5]等領域得到越來越多的應用。目前的BNSL 方法都是通過訓練全部數據樣本來進行學習節(jié)點之間的依賴關系，容易出現數據量過大、訓練時間過長、容易陷入局部最優(yōu)的問題。

由于認知科學的啟發(fā)，Bengio 等[6]提出了課程學習(curriculum learning, CL)的概念，讓模型從簡單樣本學習逐步過渡至復雜樣本。CL 在計算機視覺和自然語言處理等多種場景下，在提高各種模型的泛化能力和收斂率方面表現出了強大的能力[7]。

本文基于課程學習思想，提出了一種基于課程學習權重集成的結構學習 (Bayesian network structure learning based on curriculum learning weight integration, BN-CW)算法，通過模仿人類學習認知過程，分階段構造BN。該算法首先對原始數據集進行采樣，對15 次骨架結構學習執(zhí)行一次集成學習。對于每個訓練樣本，衡量節(jié)點之間的相互影響程度，從具有簡單依賴關系的樣本節(jié)點到復雜且依賴關系不明顯的節(jié)點，根據相應課程階段分配課程權重，將各學習結果所獲得的網絡邊的權重進行集成，并利用邊過濾來去除錯誤的邊，將正確的邊加入白名單，提高搜索效率和學習結果的精確度。

本文的研究重點包括4 個方面：

1）針對網絡中節(jié)點之間的相互影響程度，提出了一種基于課程權重的互信息公式，相較于傳統(tǒng)的互信息公式，可以更好地識別出變量之間的相互影響程度，且可以動態(tài)識別出各個課程階段節(jié)點之間相互影響程度的變化。

2）基于課程階段的劃分，分階段構造學習網絡框架，在集成迭代中不斷強化為修正項的學習，大大減少錯誤邊的出現。

3）通過邊約束策略增加正確邊的可靠性，嚴格限制了錯誤邊的出現，大大縮小了BN 的搜索空間，提高了后續(xù)搜索算法的效率。

4）在不同標準數據集上的實驗結果表明，本文提出的BN-CW 算法可以有效減少BN 中學習的誤差，提高結構學習的效率和準確度。

1 貝葉斯網絡學習相關工作

1.1 貝葉斯結構學習方法

貝葉斯結構學習(Bayesian network structure learning, BNSL)方法是給定問題領域中的變量，以及這些變量的相關觀測數據，學習變量間的相互影響關系的過程。由于結點間的影響是有向的，需要用一個有向無環(huán)的網絡結構來描述，結構學習就是尋找與訓練數據匹配度最好的BN 結構。通過大量的樣本數據來提煉挖掘變量之間潛在的關系是目前BNSL 的一個主要趨勢。然而由于候選結構的數量隨著節(jié)點數量的增加呈現指數級的增長數據學習，因此BNSL 是多項式復雜程度的非確定性問題(non-deterministic polynomial,NP)[8]。目前主流的結構學習算法主要有：基于約束結構學習算法(constraint-based structure learning algorithm, CB)[9]、基于評分結構學習算法(scorebased structure learning algorithm, SB)[10]以及混合結構學習算法(hybrid structure learning algorithm,HS)[11]。

相較于SB 和HS 算法，CB 是目前發(fā)展較為活躍的算法，主要由評分函數和搜索算法2 部分組成。學者們側重于通過對評分函數和搜索算法進行優(yōu)化以提高算法的求解能力和準確度。評分函數主要包括基于信息論和基于貝葉斯2 種，具有代表性的評分函數包括K2 評分(CH 評分)[12]、貝葉斯– 狄利克雷等價一致先驗(Bayesian Dirichlet equivalent uniform prior, BDeu)評分函數[13]、貝葉斯信息準則(Bayesian information criterion,BIC)評分函數[14]等。BN 的搜索空間可以分為有向無環(huán)圖(directed acayclic graph, DAG)[15]、等價類[16]和節(jié)點序搜索空間[17]3 種。大部分的結構學習方法是在DAG 空間中進行搜索的，但DAG 搜索空間會隨著節(jié)點數的增加呈現指數級的增長，常用的搜索策略為爬山搜索[18]、迭代搜索[19]、分布估計算法[20]等。相較于DAG 搜索空間，等價類空間搜索空間較小，且基于馬爾可夫等價類進行劃分，存在空間難以判斷且復雜的問題。節(jié)點序搜索空間是按照節(jié)點的拓撲順序進行劃分的，算法的精確度對于節(jié)點序具有較強的依賴性[21]。雖然基于評分函數的搜索算法有較高的準確度和效率，但當數據結構復雜時，搜索空間過大使得算法很難收斂，難以在巨大的搜索空間內尋找到最優(yōu)的網絡結構。

為了解決BN 結構學習中的一些主要問題，許多研究人員已經提出了一些優(yōu)化策略，包括引入先驗知識[22]、集成學習[23?24]、專家知識整合[25]和矩陣分解[26]。但這些方法都是通過將訓練樣本整體放入算法中進行學習，來發(fā)現變量之間存在的依賴關系。在學習一些依賴關系時，不僅學習到的節(jié)點之間的數據噪聲會影響到節(jié)點之間依賴關系的確立，一些無關的樣本節(jié)點噪聲也會干擾學習過程，導致錯誤依賴關系的建立。雖然一些學者通過A*剪枝操作[27]、添加約束[28]等操作來降低，數據中存在的大量噪聲仍然會影響到算法本身的學習過程。

1.2 課程學習

2009 年的國際機器學習大會(International Conference on Machine Learning, ICML)上Bengio等[6]首次在機器學習的背景下提出了課程學習的概念，旨在通過模仿人類認知學習過程，從簡單樣本出發(fā)逐步過渡到復雜樣本，使得模型具有更高的效率和準確度。課程學習的本質是非凸優(yōu)化中延拓方法的擴展，從更平滑的目標函數逐步過渡至不太光滑的函數。隨后，很多學者在相應的應用領域尋求課程學習的策略，比如弱監(jiān)督物體定位[29]、物體檢測[30]以及神經機器翻譯[31?32]等，這些工作均證明了課程學習在小批量抽樣中常規(guī)培訓的明顯好處。首次將課程學習策略應用與BNSL 的是文獻[33]，通過課程學習的思想來增量構建BN 結構，并將各個階段學習到的DAG 結構作為下一階段的初始網絡結構，最終學習到完整的網絡結構。課程學習雖然在各個領域都取得了較為顯著的成功，但主流著作中對于課程學習的研究仍相對較少，尤其是在貝葉斯結構學習方面。

考慮到前期課程階段學習結果對后續(xù)課程階段的影響，一旦前期課程階段學習到錯誤邊，會誤導后續(xù)課程階段的繼續(xù)學習錯誤邊。因此本文在前文研究的基礎上，不再將前期課程階段學習到的結果直接用于后續(xù)的課程學習，而是通過分配課程權重和權重集成約束的方式，將上一階段的課程學習結果僅作為后續(xù)課程學習的參考，通過權重約束逐步減少錯誤邊的出現，提高可靠邊的數量。

2 BNSL 基本概念

2.1 貝葉斯網絡

BN 由DAG 和對應的條件概率表組成。DAG 中的節(jié)點表示隨機變量{X1,X2,···,Xn}，這些變量涵蓋范圍較為廣泛，可以是可觀測到的變量、隱變量，或者是未知參數等。節(jié)點之間的有向邊表示2 個節(jié)點之間存在依賴關系并非條件獨立的，其關系的依賴程度用條件概率表示。BN 結構的數學表示為

式中：V為BN 中的所有節(jié)點的集合，E為BN 結構中存在的邊的集合。

BNSL 的目標是通過學習得到與樣本數據集擬合度最高的網絡結構。評分函數通常被用于判斷BN 的好壞。本文采用BIC 評分函數，BIC 是在樣本滿足獨立同分布假設的前提下，利用對數似然來衡量結構與數據之間的擬合程度。

式中：qi為變量xi父節(jié)點值組合的數量；misk為xi的父節(jié)點取s的值，xi取k值時的樣本數量； θisk是似然條件概率，0 ≤θisk≤1。

2.2 權重互信息的構建

為了更好地劃分課程階段，衡量樣本節(jié)點之間的相互影響程序，提出了權重互信息(weights of mutual information, WMI）。

定義1已知數據集D中2 個節(jié)點變量Xs和Xt，其Xs和Xt之間的相互影響程度WMI 的計算公式定義如下：

式中：I(Xs,Xt)是節(jié)點Xs和Xt的互信息；W(Xs)為節(jié)點的課程權重值；Ind(Xs)為節(jié)點Xs在課程集合中的位置，即權重由課程節(jié)點在課程中的學習次序決定。

3 基于BN-CW 的貝葉斯結構學習

本文主要是基于課程學習權重集成的思想來分階段構建貝葉斯網結構，利用爬山法(hill climbing, HC)搜索到最終的網絡結構，圖1 給出了算法的整體框架。

圖1 BN-CW算法框架

算法分為4 個階段：

1）集成采樣過程。通過Bagging 集成抽樣，通過可重復的抽樣技術生成多個數據集。

2）課程學習階段。利用WMI（Xi,Xj。）選擇候選節(jié)點Hi與課程節(jié)點集合中各節(jié)點Ci相關性最強的節(jié)點作為下一個課程節(jié)點。根據課程階段，得到課程節(jié)點之間的依賴關系，得到無向初始網絡結構G?，不同的課程權重分配給學習的邊。

3）集成學習階段。根據集成學習的結果，通過評分優(yōu)化函數對每次得到的無向圖骨架進行迭代優(yōu)化，得到每條邊集成后的權重值。

4）邊過濾與搜索。通過集成學習優(yōu)化得到的骨架，得到無向圖骨架權重表示Wk，通過設置閾值刪除權重不滿足閾值 α的邊，將得到的骨架作為初始DAG，通過爬山算法和BIC 評分函數得到最終的BN 結構。

3.1 課程階段的劃分

BN-CW 算法構建基于課程學習的BN，在培訓步上訓練標準序列C={Q1,Q2,···,Qn}。圖2 給出了BN 構建的課程匹配機制、計算節(jié)點間以及節(jié)點與集合之間的相互影響程度，劃分課程階段，對不同課程階段學習到的邊匹配不同的權重。

圖2 BN 構造的課程匹配機制

3.1.1 初始節(jié)點的選取

信息熵表示信息流中的平均信息量。對于由多個離散信源組成的信息，其信息熵可以用信源概率的負對數的均值來表示。

式中：pi為信息源出現的概率，n為信息源個數。

根據信息熵的定義，對于一個事件，整體概率越小，包含的信息量越大。擴展到網絡中的節(jié)點，信息熵越小，節(jié)點包含的信息量越少，越容易學習。按照由淺入深的思路，初始節(jié)點滿足：

3.1.2 后續(xù)課程節(jié)點的選取

根據課程學習的思想，為了考慮不同課程階段下課程節(jié)點與候選節(jié)點之間整體影響程度的變化，通過WMI 來衡量變量之間的關聯方式，WMI 可以更加準確描述變量可能存在的依賴關系，且不受數據節(jié)點序列的影響，更具有魯棒性。

定義2將數據集D中的節(jié)點劃分為課程節(jié)點集合Ci和候選節(jié)點集合Hi，其劃分依據如下：

定義3數據集D中候選節(jié)點Xi與課程集合Ci中各課程節(jié)點的最大權重互信息定義如下：

通過衡量各個候選節(jié)點集合節(jié)點與課程節(jié)點之間的權重互信息，將滿足條件的候選節(jié)點加入下一階段的課程節(jié)點。

3.2 初始網絡構建

3.2.1 無向圖骨架構建

本文采用集成優(yōu)化的思想對原始數據進行采樣，每隔15 次設置一次集成學習。對于每個訓練樣本，課程學習構造的骨架Si被用作先驗知識，對每次集成學習得到的骨架進行優(yōu)化，得到更優(yōu)的骨架Sbi。骨架優(yōu)化函數 cs是將2 個骨架結構進行比較，將相同的邊放入Es中，將不同的邊放入Ed中，將相同的無向邊添加到初始骨架中，遍歷Ed中的邊eij并將其添加到Si?1，比較得分變化。如果得分增加，則將其相加，直到得分不再增加。遍歷結束形成一個骨架結構Sbi并獲得一個權重矩陣Wi。它的定義如下：

其中，骨架中的邊劃分為

式中：eij為節(jié)點i和節(jié)點j之間的邊，Si為經過第i次采樣后學習到的BN 骨架，Es為2 次采樣后網絡學習都存在的邊，Ed為采樣后學習過程中出現的相異邊。

式中：s(Si?1)為學習到的骨架結構Si?1的評分值，則為骨架結構Si?1加入邊eij后所得到的評分值。當Ed為1 時，保留骨架中對應的eij，相反則刪除eij。對于多次學習后學到的相同邊執(zhí)行保留操作。

3.2.2 權重集成和邊過濾

通過每次學習到的骨架的權重矩陣集合W進行集成，權重值表示每條邊學習到的可信度，權重值越高，表示學習到該條邊的可靠性更大，權重值的合理分配為后續(xù)貝葉斯結構學習提供了更加可靠的初始骨架結構。每條邊的權重定義為

式中：n為優(yōu)化次數，s為課程階段數目，為第k次迭代后在第s次課程中節(jié)點Xi和Xk之間邊出現的次數。

為了確保學習到的骨架結構的準確性并減少搜索空間，對學習邊設置約束，計算平均權重avgW，并根據經驗值設置閾值 α為0.6，如果Weij＜avgW，則刪除eij；否則，保留對應的邊eij。

具體的算法如算法1 所示。

算法1BN-CW 算法

輸入：訓練數據集D、樣本大小n、BN 節(jié)點集合X、學習步長t、課程數量nc

輸出：對應的BN 結構DAG

4 實驗結果與分析

4.1 實驗設置與數據集

本文使用Python 語言中的Pgmpy 工具包。選取了4 種不同規(guī)模的標準數據集進行對比實驗，通過抽樣形成了不同數據規(guī)模的樣本。根據實驗對比效果，BN-CW 算法中的學習步長t根據數據集的出入度進行設計；實驗中所涉及到的相關數據集如表1 所示。

表1 標準數據集

4.2 結果分析

為了驗證算法的有效性，本文涉及到的指標有F1 分數(F1-Score)、結構漢明距離(structural Hamming distance, SHD)、正確邊數(true positive,TP），對生成的BN 進行評價。SHD 值越小表示學習到的BN 越接近真實網絡，TP 值越大說明學習到的正確邊越多。

4.2.1 WMI 和MI 的對比

驗證WMI 方法的有效性，選取互信息(mutual information, MI)值作為參照，對WMI 值和MI 值方法構建的初始網絡的進行了對比實驗，來判斷WMI 方法是否具有更好地分析變量間相互影響程度的能力。對4 種標準數據集分別進行采樣，共32 組對比實驗，而每一組對比實驗有10 組數據，實驗結果是10 組實驗結果的平均值和與最優(yōu)值的百分比。實驗結果如圖3 和圖4 所示。

圖3 比較使用WMI 和MI 構建初始網絡的SHD 實驗結果

圖4 比較使用WMI 和MI 構建初始網絡的TP 實驗結果

圖3 和圖4 詳細繪制了標準數據集上MI 和WMI 方法構造出來的BN，在Cancer 數據集的實驗結果中，WMI 方法只有在采樣500 次的錯誤邊數和MI 方法相同，其他指標均大大優(yōu)于MI 方法；在Asia 數據集上可以明顯看出WMI 方法在各項指標上完全由于MI 方法。對于Child 和Alarm 數據集，WMI 方法在一些指標上略差于MI 方法，由于節(jié)點數目較多時，課程階段的劃分影響了WMI 對于數據節(jié)點之間影響關系的判斷。

4.2.2 不同數據集下BN-CW 算法和其他算法性能對比

實驗中對4 種標準數據集分別采樣，樣本大小為500、1 000、1 500 和2 000，與HC、皮特–克萊克算法(Peter-Clark algorithm, PC)、最大最小爬山法(max-min hill-climbing, MMHC)[34]、基于跡指數和增廣拉格朗日的非組合優(yōu)化(non-combinatorial optimization via trace exponential and augmented lagrangian for structure learning, NOTEARS[35]、遺傳算法(genetic algorithm, GA)和基于遺傳算法改進的粒子群算法(particle swarm optimization with genetic algorithm, PSO-GA)[36]等算法進行對比，每組對比實驗有10 組 數據，取10 組數據的平均值，實驗結果如圖5 和圖6 所示。從圖5 中可以看出，在SHD 的表現上，BN-CW 算法相較于其他結構學習算法具有明顯的優(yōu)勢。對于Cancer 數據集，當樣本量較小時，算法略次于NOTEARS 算法，但隨著樣本量的增大，漢明距離逐漸降低，當樣本量大于或者等于1 k 時，BN-CW 算法相較于其他算法具有顯著優(yōu)勢。對于Asia 和Child 網絡，該算法均有明顯優(yōu)勢。相較于其他算法，BNCW 算法性能表現較為穩(wěn)定，說明了BN-CW 設置的邊約束機制和集成優(yōu)化策略可以顯著降低錯誤邊的出現概率。

圖5 標準數據集上不同算法的漢明距離

圖6 標準數據集上不同算法的F1-score

從圖6 可發(fā)現，BN-CW 在4 種標準數據集上的F1-score 值均優(yōu)于其他算法，特別是在Cancer和Alarm 數據集上，BN-CW 的優(yōu)勢遠超過其他算法。而在Child 和Asia 網絡僅在部分樣本略次于NOTEARS 算法和PC 算法。從F1-score 指標上也反映出BN-CW 算法具有更高的精確度，構建出來的網絡結構更加接近真實結構。

通過圖5 和圖6 的分析可以發(fā)現，本文提出的BN-CW 算法在各數據集上均有較好的表現，說明該算法具有普適性。將初始無向骨架作為先驗知識用于結構學習，能夠有效壓縮搜索空間，提高算法的搜索效率。課程階段的不斷學習可以不斷地加強正確邊的學習，弱化錯誤依賴關系的影響，減少錯誤邊的出現，邊約束可以進一步地過濾掉錯誤邊，這也是算法在漢明距離表現出色的原因。特別對于大型網絡，在學習過程中，通過不斷調整優(yōu)化骨架結構使得初始網絡不斷接近真實網絡，因此生成的BN 也會越接近真實網絡。但是BN 的搜索學習最終是通過HC 算法實現的，與標準網絡相比還存在一定的誤差(如多邊、反邊)，容易陷入局部最優(yōu)。由于是對于節(jié)點數目較多的中大型網絡，這也是在這些數據集上的某些指標為次優(yōu)的原因。

5 結束語

本文結合課程學習思想和集成策略進行BNSL 中，提出了BN-CW 算法，提出了WMI 的概念，并推導了WMI 的計算公式，通過實驗驗證了WMI 相較于傳統(tǒng)的互信息，具有更加優(yōu)秀的識別變量關聯程度的能力。課程階段的劃分學習，可以在集成迭代中不斷加強對正確邊的識別，并在課程階段的學習過程中，大量減少了錯誤依賴關系的出現，一定程度上減少了錯誤邊的出現。通過在標準數據集上進行實驗，并與其他的結構學習算法進行對比，驗證了算法在結構學習上的有效性和普適性。但在后期的搜索過程中使用HC 算法進行搜索，很容易陷入局部最優(yōu)，導致算法效果的下降。未來的工作包括2 個方面：1）探索如何實現課程學習過程的反饋和自修正，實現學習過程中自調整；2）進一步研究如何將課程學習的思想應用于搜索的迭代優(yōu)化過程跳出局部最優(yōu)，從而優(yōu)化算法的搜索效果。