基于規則過濾和謂詞覆蓋的MLN遷移算法研究

吁 松， 何 慧， 王 星

(哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001)

0 引 言

隨著機器學習領域研究的不斷深入，遷移學習作為機器學習領域的一個重要方向而引起研究者的高度關注與重視。 相對于傳統的機器學習針對一個領域進行訓練、測試和運用，遷移學習針對的是2個不同但有關聯的領域，在一個領域上訓練，在另一個領域上測試和運用，前者被稱為源領域，后者被稱為目標域。 這種訓練數據與測試數據處于不同領域的要求，正是因為人們在運用傳統的機器學習解決問題時，一些獲取有標簽數據代價昂貴或者難以收集的領域受到有標簽數據不足的困擾[1]。 而這類領域正是遷移學習可以發揮作用的地方。

遷移學習從其遷移的內容來看，可以分為遷移參數、遷移實例、遷移特征和遷移關系[1]。 遷移關系的算法核心是尋找源領域和目標領域之間共享的關系，Li等人[2]就利用bootstrapping的方法迭代構建領域之間的關系。 針對馬爾科夫邏輯網絡[3]的遷移算法，大部分就是一種基于關系的遷移。 研究者往往是利用馬爾科夫邏輯網絡模型的邏輯公式作為源領域和目標領域關系的橋梁。 其中，一類算法是將MLN模型中的一階邏輯公式轉換成高階形式，然后進行模型的遷移。 Davis等人[4]通過引入謂詞變量將一階邏輯公式轉換成二階公式，并將這些二階公式合并成團，再對每個二階團進行評估，將分數最高的k個二階團遷移到目標域。 Haaren等人[5]同樣是將一階公式轉換成二階公式，但在二階轉換成一階的過程引入了偏置，實現了效果更好的遷移。 另一類算法則是通過謂詞映射的方式直接生成目標域的一階邏輯公式，然后采用不同的策略來調整、變換公式，最終篩選公式進入MLN模型[6]，或者更簡單一點，運用篩選策略不加調整地遷移公式到MLN模型中[7]。

本文設計的遷移算法是一類對目標域數據量要求不高的算法，在謂詞映射算法[6]的基礎上，提出了基于規則的公式遷移策略和依據權重進行謂詞覆蓋的遷移策略，實現了馬爾科夫邏輯網絡模型[8-10]的遷移。

1 MLN遷移算法

本文提出的馬爾可夫邏輯網絡遷移算法是一種遷移馬爾可夫邏輯網絡模型中一階邏輯公式的方法。 目標領域只需要提供一個單實體為中心的實例就可以實現遷移。 遷移算法總體設計思想是將源領域的一階邏輯公式通過謂詞映射轉換成目標域的一階邏輯公式，然后利用數據驗證、規則遷移和基于權重的謂詞覆蓋等手段遷移公式，最后生成目標域的MLN模型。 本文的最大貢獻就是提出了基于規則的公式遷移策略以及基于權重的謂詞覆蓋策略。

1.1 數據驗證

首先，MLN遷移學習算法需要通過謂詞映射生成目標域公式。 本文采用局部謂詞映射方法，即類型的一致性約束只針對單個公式，不同的公式的類型約束可以是不同的。 在映射過程中，研究的算法還額外要求謂詞一致性，即在針對單個公式進行遷移時，源領域的謂詞與目標域的謂詞是一一對應的。 謂詞一致性約束同樣是局部的，即不同公式中的源領域謂詞可以對應目標域中的不同謂詞。 增加這樣2種局部的一致性約束一方面可以節省算法的運行時間；另一方面相對于全局性的一致性約束而言，有利于生成多樣化的遷移公式，進而提高遷移效果。

在得到目標領域的公式之后，研究利用僅有的目標域數據對這些映射公式進行驗證。 在本文中，可以用數據來驗證的公式即稱為被數據驗證的公式，簡稱為已驗證的公式。 同時，進一步對被數據驗證過的公式進行細分，將上一步得到的已驗證的公式分為2種。 一種是經過數據驗證成立的公式，即可行公式，另一種是數據驗證后不成立的公式，即不可行公式。 研究借鑒Lilyana等人[7]的思想，提取所有可行公式中包含的映射得到可行謂詞映射集合，提取所有不可行公式包含的謂詞映射組成不可行謂詞映射集合，利用其來篩選公式。 而且，考慮到不可行公式中的謂詞映射并不都是不可行的映射，有的只是由于公式中的某個謂詞的映射不好而導致公式驗證失敗。 因此，研究擬使用不可行謂詞映射集合與可行謂詞映射集合做差，得到的真正的不可行謂詞映射集合。 此后用這種真正的不可行映射來篩選未被數據驗證的公式，也稱之為未驗證公式，得到候選公式。

在前面提到過，本文算法對目標域數據量的設定是少量數據，所以不會得到太多已驗證的公式，而未驗證的公式數量則較多。 這些未被數據驗證過的目標公式中既含有對目標域推理有價值的公式，也含有對目標域推理無價值的公式，因此就需要通過其它手段—基于規則的篩選和根據權重進行謂詞覆蓋—獲得更多對目標域推理有用的公式。

1.2 基于規則的遷移策略

通過對已有的非遷移馬爾可夫邏輯網絡模型中邏輯公式的觀察，研究發現大部分公式都具有如下特征：公式的前置條件參數之間的相互關聯，最后推導出與之有關的結論參數的關系。 對比遷移得到的未驗證的公式，有很多公式違背這個特征，存在一些相互關聯的變量推導出與之無關的變量之間的關系，因此推導出一些不合理的結果。

表1是非遷移的方式得到uwcse領域的MLN模型中的2條公式。 從第一條中可以看到，前置條件是a1在a4學期教a3，a2在a4學期教a3，由此就可以得到一個可能成立的結論—a1和a2是同一人。 同理，第二條的前置條件中給出了a1出版a2，a3出版a2，a1不是學生，a3是學生，于是可以推出a1是教授的結論。 當然上述結論并不都是一定正確，只是有較大概率成立而已，但由于MLN的公式有權重來進行描述，因此可以允許這種推導出非確定性結論的公式。 表2是從imdb域向uwcse域遷移得到的MLN模型的公式中選取了2條。 第一條，前置條件描述了a2和a3的關系，但結論給出的卻是a1和a2的關系，相對而言并不合理。 同樣，表2中的第2條，前置條件分別描述的a1與a2的關系和a1與a3的關系，結論卻給出了a4和a2的關系，也不是合理的推導。 基于上述的觀察和特征的歸納，本次研究提出一個遷移候選公式的規則，篩選出的公式則稱為符合規則的公式，簡稱為規則公式。

表2 IMDB遷移到UWCSE域得到的遷移公式

為了進一步解釋基于規則的公式遷移原理，研究使用圖1和圖2分別解釋了一個符合規則的公式驗證過程和一個不符合規則的公式驗證過程。 圖1～2中的每個圓代表一個集合，2個圓相交的部分是2個集合共同的元素。 紅色虛線圓圈表示的是作為結論的謂詞的實參元素集合，箭頭右邊的實線圓圈代表可能被推導出關系的元素集合。 圖1、圖2中的2個公式的前提條件都是2個原子公式構成，這2個原子公式的實參都含有a1，因此，a1成為2個集合之間關系的橋梁，2個本沒有關系的集合如今可能存在某種關系，于是并成一個集合，即箭頭右邊的集合。 該集合中任何元素之間都有可能存在某種可推理的關系，或者可以認定某人的身份，因此如果紅色圓圈代表的集合是該集合的子集，即圖1所示的情況，則相應的關系可能存在，該公式被認為是符合規則的公式，反之，如果公式中作為結論的謂詞的實參不完全在前置條件實參構成的集合中，即圖2所示的狀態，則這個結論由條件關系推導出的可能性就低，該公式被認為是不符合規則的公式。

taughtBy(a2,a3,a4)∧taughtBy(a1,a3,a4)?same Course(a1,a2)

圖1 符合規則的公式示意圖

┐publication(a1,a2)∧publication(a1,a3)?adviseBy(a4,a2)

圖2 不符合規則的公式示意圖

需要強調的是，符合規則的公式推導出的結論也有可能是錯誤的，反過來，不符合規則的公式推導出的結論也是有存在可能的。 但這不會造成太多不良影響，因為馬爾可夫邏輯網絡是一種軟化邏輯公式硬約束的模型，故而不需要模型中的公式是絕對正確的。

1.3 基于謂詞覆蓋的遷移策略

這里，首先要明確謂詞被覆蓋和謂詞沒被覆蓋的定義。 所謂謂詞覆蓋是指目標域中的謂詞存在于MLN模型的某個公式中，而所謂謂詞沒被覆蓋是指目標域中存在謂詞不在研究的MLN模型的公式中。 謂詞覆蓋就是指去覆蓋那些沒有被覆蓋的謂詞，而依據權重意味著需要優先使用權重高的公式去覆蓋謂詞。 研究中要盡量去覆蓋所有目標域的謂詞，是因為通過初步試驗發現，如果某個謂詞沒有公式去覆蓋的話，那么針對該謂詞的推理就不能取得良好的效果。 因為該謂詞沒有公式覆蓋，那么推理程序就沒有推理的依據，故而得不到正確的結果。 因此，本文研發的算法考慮在經過前2步公式遷移后，在未能覆蓋所有謂詞的情況下，挑選剩余的公式中可以覆蓋這些謂詞的公式作為MLN模型公式的補充。 研究將使用alpha參數來指示每個謂詞需要被多少個公式覆蓋，對于不同的源領域和目標領域可以設置不同的值以達到最好的效果。 設計流程步驟是:先根據權重大小排序，然后統計目前MLN模型公式還未能覆蓋的謂詞或者說覆蓋的公式數量還沒能達到alpha參數要求的謂詞，最后將公式依據權重大小補充進遷移的MLN模型中,使其盡量滿足alpha參數規定的數目。

2 實驗評估

在這一部分，研究將對算法進行實驗評估。 這里對比了2個MLN遷移學習算法，分別是TAMAR算法[6]和SR2LR算法[7]。 這2個算法都有謂詞映射的步驟，除謂詞映射之外的遷移手段是不同算法之間的主要區別，因此非常適合用于與本文提出算法的對比。

為了分析算法的表現，采用了2種典型的用于分析馬爾可夫邏輯網絡的度量方法——AUC-PR和CLL。 研究可知，PR曲線是精確度-召回率曲線，AUC-PR是指PR曲線下的面積。 如果用一般的正確率這種方式來衡量則容易被大量不存在的關系的正確率所影響，導致評估結果與真實使用情況有差距。 條件對數似然(conditional log-likehood，CLL)則主要用于評估馬爾科夫邏輯網絡推理的質量，是對AUC-PR的一種補充。CLL值越大，則推理質量越高；反之，值越低，推理質量越差。 仍需看到，文中的評估方法比較簡單，由此反映得出的推理質量并非精確可靠，如果模型能夠生成足夠有區別的閾值的話，CLL高低并不重要。

實驗中使用了3個公開的關系型數據集，分別是IMDB、UWCSE和WebKB。 這3個數據集都是從現實世界中收集而來的，在時下研究的實驗中得到了廣泛的使用。 其中，UWCSE數據收集自華盛頓大學的計算機科學與工程系，記錄了課程、教授、學生等身份信息，并記錄了個體之間的關系，例如，advisedBy、taughtBy等等。 IMDB數據集是Lily Mihalkova采集自IMDB數據庫的電影領域的相關信息，具體包含了導演、演員、電影等信息以及不同個體之間的關系。 WebKB數據集則記錄了4所大學計算機系的Web網頁和超鏈接信息。

實驗中，測試了3個數據集構成的共6個遷移場景：IMDB→UWCSE、IMDB→WebKB、UWCSE→IMDB、UWCSE→WebKB、WebKB→IMDB、WebKB→UWCSE。 其中，箭頭前方是源領域，箭頭后方是目標域。 在本文的后面章節，會著重展示這4個算法在6種遷移場景中的表現，而后在這6種遷移場景中測試本文提出的遷移策略的效果，最后將基于實驗討論分析規則遷移、謂詞覆蓋和alpha參數在本文提出算法中的作用。

3 實驗驗證

3.1 實驗結果對比

實驗中，首先測試了4種算法在6種遷移場景下的表現，4個算法的AUC-PR值和CLL值分別見表3、表4。 表格的第一列是目標域，第二列是源領域。 RFPC是本文提出的遷移學習算法，其alpha的參數取值為4。

從表3和表4可以看出，在本文的實驗中TAMAR算法和SR2LR算法表現較為相近，且TAMAR算法還略好于SR2LR算法。 2個算法在遷移的目標域為WebKB時，表現幾乎一致，AUC-PR都是0.49，但是在CLL這個指標上，SR2LR又略好于TAMAR。 測試的遷移場景是UWCSE向IMDB遷移時，SR2LR表現較好，AUC-PR值比TAMAR高0.05左右。 而當遷移場景是WebKB向UWCSE遷移時，TAMAR表現較好，AUC-PR比SR2LR高0.1左右。 在其它遷移場景下，2個算法的AUC-PR的相差不大。

接下來，將2個已有的遷移學習算法與本文提出的RFPC進行比較。 從表3可以看出，在IMDB向WebKb遷移時，本文的算法比SR2LR效果要略有遜色，但在剩余的全部數據上，本文的算法在AUC-PR這個指標上是超過SR2LR算法的，因此在整體上來看，本文的遷移算法得到的馬爾可夫邏輯網絡模型能夠做出更好的推理。 從表4可以看到，本文的遷移算法在CLL指標上普遍比SR2LR算法差，除了UWCSE向IMDB遷移時，本文的算法的CLL指標比SR2LR高之外，這意味著本文算法的推理結果概率普遍低于SR2LR算法。 這可能是因為本文的算法未能進行權值的調整。 但是如前述分析可知，如果推理概率的閾值選擇恰當，就不會影響本文算法的預測效果，因此這也不會意味著本文的算法比SR2LR算法更差。 在與TAMAR算法比較時，本文的算法在遷移目標域為UWCSE時，AUC-PR的值比其略有不及，但在其它遷移場景中，本文的算法均是優于TAMAR的，并且在UWCSE向WebKB和WebKB向IMDB遷移時，本文的算法在AUC-PR指標上將遠遠高于TAMAR。 因此，從整體上來看，本文的算法比SR2LR和TAMAR都是要好的。

表3 不同算法在不同數據集上的平均AUC-PR的值

表4 不同算法在不同數據集上的平均CLL的值

3.2 實驗結果分析

基于前述仿真測試研究過程，這里擬將探討剖析RFPC算法中不同部分發揮的作用。 同樣，研究在6種遷移場景下對比這些算法的效果，運行后詳情見表5、表6。 其中，Only-Data代表只使用被目標域數據驗證過的公式生成MLN模型，Data+Rule代表了用數據驗證過的公式和規則遷移公式構成的MLN模型。 最后一列代表了完整的RFPC算法(alpha參數的取值為4)，該算法遷移得到的MLN模型中包含了數據驗證的公式，規則遷移的公式和依據權重進行謂詞補充的公式。

從表5中可以看到，除了向UWCSE領域的遷移之外，Data+Rule的方案都比只有Data的方案要好，而且大部分情況下均是如此。 例如，Data+Rule在WebKB領域向IMDB領域遷移時，AUC-PR值比Only-Data高出了0.157 4。 更為明顯的是當源領域為UWCSE、目標域為WebKB的情況，Data+Rule的AUC-PR值接近Only-Data的AUC-PR值的2倍。 即便是在向UWCSE遷移時，Data+Rule只比Only-Data在AUC-PR值上低了一點點。 從IMDB向WebKB遷移的時候，Only-Data和Data+Rule則顯出劣勢，AUC-PR為0是因為數據驗證和規則遷移兩種策略都不能得到合適的公式，此時MLN不會在這種情況下進行推理，故而對應的AUC-PR值為0。 此種情況下，根據權重進行謂詞覆蓋的作用就得以體現，在補充了一些權重較高的公式之后，RFPC算法依舊能夠取得較好的效果。 在前2種公式遷移策略能夠有效發揮作用時，根據權重進行謂詞覆蓋的效果將不再直觀明顯，但如果alpha設置合理，那么對推理效果也能有一些提升，關于該點將在下文予以闡釋分析。

表5 不同算法在不同場景下的平均AUC-PR的值

表6 不同算法在不同場景下的平均CLL的值

由于研究的算法中有一個alpha參數，指示了研究在覆蓋謂詞時需要選擇多少公式，所以研究有必要對其進行深入分析，探尋考察不同的alpha參數會對算法效果產生的影響。 同樣測試了在6種遷移場景下，alpha參數對RB算法的影響，alpha參數設置的范圍為[0,18]。

從圖3中可以看到，除了之前分析過的情況，alpha參數對算法效果的影響較為有限。 在alpha參數增加時，在一定程度上將會提升算法的效果，但有時也會導致算法效果下降。 研究中可以在IMDB向UWCSE和WebKB向UWCSE遷移時發現較大的波動，說明在Data+Rule的AUC-PR值不高時，alpha參數影響相對較大。 當Data+Rule的AUC-PR值較大時，alpha參數的影響相對較小，正如研究中看到當UWCSE向WebKB遷移時未見任何波動。 由此也可以推斷得出，作為本算法的關鍵部分—基于規則的公式遷移策略—起著關鍵的作用，用于覆蓋謂詞的公式起到一個補充的作用，而alpha參數卻只是用于最后的微調。

圖3 alpha參數對算法的影響

研究至此，又統計了RFPC算法(alpha參數設置為4)在所有遷移場景下生成的MLN模型中不同來源的公式數量。 并且推導計算了每類公式為推理效果做出的貢獻，用于詳盡評估每種遷移策略的效果。 計算公式貢獻的方法為每類公式帶來的AUC-PR的提升除以該類公式的數量。

圖4展示的是alpha參數設置為4時，RFPC遷移算法生成的模型中不同來源的公式的分布情況。 從圖4中可以看出，不同的遷移場景，不同來源的公式分布情況是不同的。 除了2種極端情況，也就是IMDB向UWCSE遷移時數據驗證的公式占主導和IMDB向WebKB遷移時只有謂詞覆蓋的公式以外，研究發現基于規則的遷移公式構成了MLN遷移模型公式的主要部分。

圖4 不同遷移策略得到的公式的平均數量

圖5展示的是不同類別的公式為最終的推理效果做出的貢獻。 由圖5可以看到，除了IMDB向WebKB遷移的時候(因為該遷移場景下MLN模型中只有謂詞覆蓋的公式)，數據驗證遷移的公式做出了最大的貢獻。 正如研究所希望的，基于規則的公式貢獻總體而言僅居次席，并且相對來說是明顯大于基于謂詞覆蓋的公式，這說明本文提出的規則發揮了應有效果，規則遷移的公式要遠遠勝過根據權重進行謂詞覆蓋得到的遷移公式。 某些情況下，基于規則的公式貢獻比基于數據驗證的公式貢獻明顯要小，這是因為真實的數據是檢驗映射公式的最佳規則。 需要特別注意的是，基于數據驗證的公式中也會存在部分公式符合規則，這也說明滿足規則的公式所做出的實際貢獻會高于圖5中所顯示的貢獻。

圖5 不同遷移策略得到的公式的平均貢獻

4 結束語

本文研究提出了一種針對極為有限的目標域數據的MLN遷移算法，通過提出一種符合邏輯的公式遷移規則，在沒有目標域數據支撐的情況下遷移映射出來的目標域公式，并根據遷移公式的權重，盡量覆蓋所有目標域謂詞。 通過在6種遷移場景下的實驗驗證，可以看到本文的算法超過現有的MLN遷移算法，同時也驗證了本文提出的規則的有效性，以及基于權重覆蓋目標域謂詞的價值。

在后續的工作中，研究將嘗試把MLN遷移學習算法運用到更多領域中去，考慮在多個源領域向一個目標域遷移的場景中運用本文的算法以及提出更多遷移公式的規則或算法使得在沒有更多目標域數據支撐的情況下遷移更好的公式到目標域。