統計關系學習模型Ｍａｒｋｏｖ邏輯網綜述

摘 要：統計關系學習是人工智能研究的熱點，在生物信息學、地理信息系統和自然語言理解等領域有著重要應用，Markov邏輯網是將Markov網與一階邏輯相結合的一種全新的統計關系學習模型。介紹了Markov邏輯網的理論模型和學習方法，并探討了目前存在的問題和研究方向。

關鍵詞：統計關系學習； 一階邏輯； Markov網； 機器學習； Markov邏輯網

中圖法分類號：TP30文獻標識碼：A

文章編號：1001—3695(2007)02—0001—03

近年來，統計關系學習（Statistical Relational Learning， SRL）已成為人工智能領域的一個重要研究熱點，它在生物信息學、系統生物學、Web導航、社會網、似然模型獲取與利用、地理信息系統和自然語言理解等領域，都取得了成功應用[1—3]。統計關系學習，又稱概率邏輯學習（Probabilistic Logic Learning，PLL），是將關系/邏輯表示、概率推理機制（不確定性處理）、機器學習和數據挖掘集成在一起[4]，以獲取關系數據中的似然模型[5，6]。統計關系學習中的“統計”是指采用基于概率論的概率表示和推理機制，如圖模型（Bayesian網、Markov網）、（隱）馬爾卡夫模型、隨機文法等；“關系/邏輯”是指一階邏輯表示和關系表示；“學習”則等同于數據挖掘，是指從數據中學得統計關系模型。目前統計關系學習方法主要有基于Bayesian網的SRL方法、基于（隱）Markov模型的SRL方法、基于隨機文法的SRL方法和基于Markov網的SRL方法等[7]。Markov邏輯網（Markov Logic Networks，MLNs）是將Markov網與一階邏輯相結合的SRL方法，其最早于2004年由Richardson等人[8]提出，之后經過Domingos[9]，Kok[10]， Singla等人[11]的研究，使MLNs得到進一步完善。MLNs本質上是公式附加權值的一階邏輯知識庫，是構建Markov網的模板；MLNs將領域知識引入Markov網，為大型Markov網提供一種簡潔的描述語言，為一階邏輯增加了不確定性處理能力；MLNs還可以作為很多統計關系學習任務的統一框架[9]。

1 一階邏輯和Markov網的基本概念

一階邏輯是建立在一階語言基礎上的邏輯體系[12]。一階語言作為一階邏輯的形式語言，主要由個體詞、謂詞符號、函詞符號、量詞符號、聯結詞符號、括號和逗號連接而成。個體詞是指所研究的對象中可以獨立存在的具體或抽象的客體；將表示具體或者特定的客體個體詞稱為個體常項；將表示抽象或者泛指的個體詞稱為個體變項，個體變項的取值范圍稱為個體域（記為D）。謂詞是用來刻畫個體詞性質及個體詞之間相互關系的詞，n元謂詞是從Dⁿ到{T，F}的映射，沒有個體變項出現的謂詞稱為閉謂詞。公式是由個體常項、個體變項、函詞和謂詞通過邏輯聯結詞和量詞（還有括號）連接起來的抽象符號串，沒有個體變項出現的公式稱為閉公式。

一階邏輯知識庫是一階邏輯公式所構成的集合[13]。一個可能世界（A Possible World）就是為每個可能的閉謂詞指定真值。某一階公式是可滿足的，當且僅當該公式至少在一個世界中為真。一階邏輯的基本推理問題就是判斷一個知識庫中是否包含公式F，即F是否在所有滿足知識庫的世界中為真。

2 Markov邏輯網

一階邏輯知識庫是一階邏輯公式所構成的集合，亦可看作施加于可能世界集合上的限制集合。在一階邏輯知識庫中，每個可能世界必須滿足知識庫中的所有公式，否則該世界不可能存在（發生概率為0）。Markov邏輯網的基本思想是將一階邏輯的限制放松，即一個世界違反公式越多，其發生概率越小，但未必為0。用公式權值來表示公式限制強度的大小，權值越大，滿足該公式世界的發生概率與不滿足該公式世界的發生概率之間的差就越大。隨著公式上權值的增加，Markov邏輯網逐漸向純一階邏輯知識庫靠攏。所謂Markov邏輯網L[8]，就是二元組集合{(F_i，w_i)}m_i=1，其中Fi為一階邏輯公式，實數w_i為公式F_i的權值。給定Markov邏輯網L和有限個體常項集合C={C₁，C₂，…，C_|C|}，則可生成一個以閉謂詞為節點、閉謂詞關系為邊的

由上述說明不難看出，對于同一個MLNs，給定不同個體常項集合，產生不同Markov網，這些網可能規模不一，但對應同一公式的所有閉公式均擁有相同權值，可稱其為閉Markov邏輯網。我們以下例說明閉Markov邏輯網的生成。

式（5）即為閉Markov邏輯網M_L，C關于世界x的可計算的概率分布，其中，qi(x)與f_ij(x)理論上均可由數據庫中的數據計算得到。

3 學習MLNs

統計關系學習的另一個重要內容就是對所采用的統計關系模型進行結構學習和參數學習。所謂結構學習，是指從數據中學出模型的結構，對于MLNs，即指學出其網絡結構；所謂參數學習，則是在結構確定的前提下，進一步學出模型的參數，MLNs中的參數就是公式的權值w_i，i=1，…，m。

現有的兩種MLNs結構學習方法均采用ILP（Inductive Logic Programming）技術：①直接利用CLAUDIEN[15]（一個ILP系統）學習模型結構[8]；②將ILP與Markov網中的特征歸納（Feature Induction）相結合，從關系數據庫中學習MLNs結構[10]，兩個方法均通過試驗驗證了其有效性，但相比而言，后者效率略高。

模型的參數學習常采用最大似然估計方法，即求解方程組

其中，i=1，…，m。顯然式（7）中常量是n_i(x)和n_i(x′)，但是計算數據庫中的n_i(x)和n_i(x′)是#P完全問題[8]。目前替代最大似然估計的參數學習方法有兩種，即最大偽似然估計和區別式訓練（Discriminative Training）方法。

取最大。其中MB_x(X_l)是對應世界x的X_l的Markov毯的狀態值。最大偽似然方法雖然可以學習MLNs參數，但是采納偽似然參數會導致非鄰接變量之間的推理結果不甚理想。為了解決該問題，文獻[11]提出了區別式訓練的參數學習方法，該方法假設謂詞分為兩個集合：證據謂詞集合X（謂詞已知真值）和查詢謂詞集合Y（謂詞未知真值），通過對條件概率

4 存在的問題和研究方向

Markov邏輯網作為解決人工智能問題的一個工具，對其研究才剛剛起步，模型不夠完善，學習和推理算法更是非常有限。對Markov邏輯網的進一步研究將主要側重于模型理論、學習算法、推理算法、應用以及與其他SRL方法的比較等五個方面：①從一階邏輯和Markov網兩個方面完善MLNs理論。②設計新的參數學習和結構學習算法。它將區別式訓練方法推廣到結構學習中等；增強算法學習能力，允許從不完備數據中學習MLNs等；提高學習算法的效率，提高真閉公式個數計算的速度等。③針對MLNs開發更有效的Markov Chain Monte Carlo(MCMC)[16]推理形式，使用置信度繁殖等方法提高推理算法效率。④增強模型實用性。將其與生物信息學、自然語言處理、信息提取、社會網絡分析等領域充分結合，更好地解決實際應用問題。⑤比較MLNs與其他SRL模型的優缺點。尤其是與基于Bayesian網的似然邏輯程序模型(Probabilistic Logic Programs，PLPs)[17，18]、貝葉斯邏輯程序模型（Bayesian Logic Programs，BLPs）[19，20]以及似然關系模型（Probabilistic Relational Models，PRMs）[21—23]作比較。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。