規(guī)則半自動學習的概率軟邏輯推理模型

張 嘉，張 暉，趙旭劍，楊春明，李 波,3

(1.西南科技大學 計算機科學與技術學院，四川 綿陽 621010； 2.西南科技大學 理學院，四川 綿陽 621010；3.中國科學技術大學 計算機科學與技術學院，合肥 230027)(*通信作者電子郵箱zhanghui@swust.edu.cn)

0 引言

2013年，美國馬里蘭大學的Kimmig等[1]提出了概率軟邏輯模型(Probabilistic Soft Logic, PSL)。與馬爾可夫邏輯網(Markov Logic Network, MLN)及其他統(tǒng)計關系學習方法類似，PSL也使用加權的一階邏輯規(guī)則對問題中的依賴性進行建模。但是和MLN不同的是，PSL表示的邏輯關系是用概率的形式在區(qū)間[0,1]中使用軟真值，而不是用布爾值0或1來代表域中的原子，這使得PSL的推理成為連續(xù)的優(yōu)化問題[2]。此外，作為一種基于聲明式規(guī)則的概率模型，PSL在解決新的領域問題時,可靈活添加有益的先驗領域知識作為規(guī)則輸入，并且其聲明式規(guī)則對于機器和人都是可以理解的，模型構建后更易于人為處理。

然而，PSL面臨的一個巨大挑戰(zhàn)是所需的聲明式規(guī)則完全由人工生成，這種規(guī)則構建方式往往非常昂貴，而且人工獲取的知識由于每個人對事物認知的偏差以及問題本身的多變性，這些知識難免會包含不正確的信息，這些不正確的信息可能會增大推理模型的不確定性。

本文引入規(guī)則自動提取的方法，提出一種規(guī)則半自動學習的概率軟邏輯推理模型(C5.0-Probabilistic Soft Logic, C-PSL)，它將數據驅動和知識驅動的方法相結合，利用C5.0算法從數據中提取規(guī)則，再將這些規(guī)則轉化為適應概率軟邏輯模型的形式，同時輔以決策樹等算法將無法使用的人為常識或知識作為概率軟邏輯模型的輸入進行建模。通過在兩個真實數據上評估本文提出的模型，結果表明，所提模型比沒有規(guī)則學習的PSL和C5.0算法能獲得更高的精度。

本文的主要工作為：1)提出了一種PSL規(guī)則自動挖掘方法，它可以大幅減少人工工作，同時提高了規(guī)則建立的科學性；2)通過手工定義規(guī)則來優(yōu)化模型，讓模型具有處理關系數據的能力，而這種能力是決策樹和大多數其他機器學習算法所不具備的。

1 建立規(guī)則半自動學習的概率軟邏輯模型

1.1 概率軟邏輯相關研究

近幾年，概率軟邏輯(PSL)已經被廣泛應用于情感分類、實體識別、知識圖譜構建、鏈路預測和圖像處理等諸多問題[1]上。

Tomkins等[3]基于時序數據手工定義了多種屬性，將PSL應用于家用電器的能源消耗分解上，獲得了不錯的效果，為降低能耗和資源浪費找到了可行的入手點，該方法能輕易合并各種信息，但其準確性需要大量的手工整合知識作為支撐，這使得該方法很難移植到其他問題上; Huang等[4]將PSL用于建立社會信任模型，通過定義大量規(guī)則對社會影響的傳播建模，驗證了人們在生活問題上比起相信同事更相信家人，在工作問題上更相信同事給出的職業(yè)建議的直覺，該方法使用無監(jiān)督和聚類方法進行建模，然而其模型并非都是PSL規(guī)則輸入; 在圖像修復問題中，LINQS團隊基于Poon等[5]的工作，使用PSL對圖像進行像素級的修復，表現出比和積網絡(Sum-Product Network, SPN)更快的速度，然而在他們建立的模型中，PSL規(guī)則數量多達數萬條，需要耗費難以估量的人工成本; Fakhraei等[6]通過藥物相似性特征使用PSL構建模型，預測藥物之間的相互作用，然而方法中基于經驗所構建的規(guī)則的實用性很難被驗證; Pujara[7]通過知識圖中的關系特征使用PSL構建了實體識別的通用模型，然而對于大規(guī)模數據來說關系特征主導的規(guī)則很難被全面定義。

由以上描述可以看出，PSL具有強大的適應性，其研究和應用已經橫跨多個領域，然而到目前為止，PSL的相關工作幾乎都是基于人工去定義每條規(guī)則，其工作量將隨著問題的復雜性增大而變得不可估計。本文方法試圖解決上述問題，和上述方法一樣，本文依然使用PSL作為建?；A，以保留推理的靈活性和穩(wěn)定性；不同的是，本文的大部分規(guī)則由C5.0算法學習生成，以減少人工工作量。

1.2 概率軟邏輯

1.2.1 PSL語法

PSL中的規(guī)則組成如下：

P1(X,Y)∧P2(Y,Z) >>P2(X,Z):weight

(1)

其中：P1和P2被稱為謂詞，用于定義隨機變量X、Y和Z之間的關系；weight表示權重，代表每條規(guī)則在推理中的重要程度[2]。例如，在本文中，Semester(ID,SE2)表示要判斷的數據為編號為ID的學生在SE2這一學期的成績，GoodScore(ID,SE1) 表示該學生在SE1這一學期成績合格，那么，根據Semester和GoodScore兩個謂詞的組合可以將該學生在SE2這一學期成績合格的概率表示出來。

1.2.2 PSL理論基礎

PSL中閉原子概率取值為[0，1]內連續(xù)的軟真值，表示為I(a)，邏輯規(guī)則r成立的概率記為I(r)，通常使用盧卡西維茲(Lukasiewicz)邏輯來計算I(r)，Lukasiewicz邏輯可以表達為式(2)～(4)：

I(l1∧l2)=max{I(l1)+I(l2)-1，0}

(2)

I(l1∨l2)=min{I(l1)+I(l2),1}

(3)

I(l2)=1-I(l1)

(4)

PSL中一條規(guī)則r可以被描述為rbody→rhead,當I(rbody) ≤I(rhead),即I(r)=1時，這條規(guī)則被滿足；否則，通過計算距離滿意度d(r)的方式來衡量邏輯規(guī)則被滿足的程度，d(r)計算方式如式(5)：

d(r)=max{0,I(rbody)-I(rhead)}

(5)

例如，有一個集合I= {friends(a,b)→1, like_eat(a,c)→ 0.9, like_eat(b,c)→0.3}，可以計算出邏輯規(guī)則friends(a,b)∧like_eat(a,c)→like_eat(b,c)的距離滿意度：

I(friends(a,b)∧like_eat(a,c))=

max{0, 1+0.9-1} = 0.9

d(r)=max{0,0.9-0.3} = 0.6

使用d(r)，PSL定義了概率分布對所有閉原子的解釋概率值：

(6)

式(6)中：Z是歸一化常數，λr是規(guī)則r的權重，R表示所有規(guī)則的集合，p為損失函數，PSL將尋求具有最小滿意距離d(r)的解釋，并盡可能地使其滿足所有規(guī)則。

1.3 規(guī)則半自動學習的PSL模型

在機器學習中，規(guī)則學習(rule learning)是從訓練數據中學習出一組能用于對未知結果數據進行推理判定的規(guī)則。得到的規(guī)則通?？蓪懗伞叭绻?那么”的形式。

在眾多能進行規(guī)則學習的算法中，決策樹算法提取的規(guī)則具有易于理解、能直觀解釋等特性，而其中又以C5.0算法為最優(yōu)[4]，因此本文使用決策樹C5.0建模規(guī)則挖掘模塊。除規(guī)則挖掘模塊之外，規(guī)則半自動學習的概率軟邏輯模型還包含規(guī)則優(yōu)化、手工規(guī)則定義等模塊，模型構建結構如圖1所示，模型通過C5.0算法對輸入的訓練數據進行規(guī)則提取，學習得到的規(guī)則在規(guī)則優(yōu)化模塊進行優(yōu)化和格式轉換，PSL將學習得到的規(guī)則和手工規(guī)則整合組成最終的推理模型。接下來，將詳細介紹如下幾個模塊的構建方式：

規(guī)則提取 運用C5.0算法，通過訓練數據進行規(guī)則學習；

規(guī)則優(yōu)化 討論規(guī)則優(yōu)化策略，改善模型質量；

人工規(guī)則 手動方法生成規(guī)則，輔助優(yōu)化模型；

推理模型 權重學習與推理。

1.3.1 規(guī)則提取

C5.0算法是C4.5算法的改進版本，處理數據時可采用Boosting方式獲得更高的準確率，C5.0算法在面對輸入字段較多和數據遺漏情況時非常穩(wěn)健，運行中占用的內存資源也較少。

圖1 規(guī)則半自動學習的概率軟邏輯推理模型

1.3.2 規(guī)則優(yōu)化

1) Boosting選擇。

使用Boosting在多數情況可使C5.0算法分類效果更加優(yōu)異，然而，Boosting所帶來的一個弊端是模型產生的規(guī)則數量過于龐大，基于本文所使用數據，對使用Boosting和不使用Boosting的情況進行了實驗討論，結果將在第2章展示。

2) 同類規(guī)則合并。

通過規(guī)則挖掘模塊提取出的眾多規(guī)則中，有很大一部分規(guī)則具有由相同屬性組成的結構，如表1所示，三條規(guī)則都包含Librarynum、Classroom、Semester、Booknum四個屬性。

表1 學習得到的規(guī)則中同屬性規(guī)則示例

在PSL模型中，運算量會隨著規(guī)則數的增多而變大，對于這一類同屬性規(guī)則，本文可以將其定義為PSL的ExternalFunction函數，并和謂詞進行組合，從而轉化為一條PSL規(guī)則作為模型輸入：

Librarynum(ID,SE,LI)∧Classroom(ID,SE,CL)∧

Semester(ID,SE) ∧ Booknum(ID,SE,BO) ∧

Lunction(LI,CL,SE,BO) ? GoodScore(ID,SE)

1.3.3 手動規(guī)則

人類認知的知識對于事物的判斷起著至關重要的作用，機器學習算法在很大程度上依然無法完整模擬人類的推理和決策過程。本節(jié)將闡述根據人類知識手動建立規(guī)則的過程，所有的舉例規(guī)則均已用在實驗中。

1) 關聯規(guī)則。

對于大多數機器學習算法，通過數據之間的關聯關系進行推理是很難實施的，而對于PSL來說卻容易得多。

①直接關聯。

問題舉例1 已知A同學在1、2、3三個學期的大量屬性，推斷A同學在2、3學期的成績狀況。

通過1.3.1節(jié)得到的規(guī)則模型可以根據學生屬性推斷A學生的成績狀況，但是推斷結果彼此無關，一般的，我們認為：如果已經推斷出A同學在第1或2學期成績合格，那么有很大可能A同學在第三學期成績也合格。但是可惜的是，此時規(guī)則學習模型得到的規(guī)則無法推斷到這一步，所以需要人為引入這條規(guī)則：

Semester(ID,SE1) ∧Semester(ID,SE2) ∧

資源優(yōu)化 我國高校以院系為單位，一個學院一般設置幾個不同專業(yè)，因此，學院就需要建設幾個相應的專業(yè)實驗室。與基礎實驗室相比，專業(yè)實驗室定位更為精準，課程安排嚴格按照理論課的進度，但是這也局限了專業(yè)實驗室的使用率，資源不能被充分利用，在學院內部較難實現資源共享。專業(yè)實驗室因其特殊性，一方面需要很多儀器滿足實驗教學；另一方面面向學生較少，儀器利用率并不高，甚至導致一些儀器被閑置，造成資源浪費[7]。另外，不同專業(yè)實驗室中不可避免會有設備重復的情況，尤其是一些大型貴重儀器，重復性高也是一種資源浪費。鼓勵專業(yè)實驗室開放，即是避免資源浪費，以進一步提升資源共享。

GoodScore(ID,SE1) ? GoodScore(ID,SE2)

其中：ID表示學生編號，SE1、SE2表示學期，GoodScore(ID,SE1)表示學生在SE1這一學期成績合格，GoodScore(ID,SE2)即為該學生成績合格的概率輸出。

②隱性關聯。

問題舉例2 已知A同學成績優(yōu)異，某學期A同學的圖書館借書類型為(G G G G H H I I O O O TP TP TP TP)，B同學在圖書館的借書類型為(H I I I I O O TM TN TP TP TP)，能否一定程度上推斷本學期B同學的成績合格情況。

通過觀察發(fā)現A、B兩同學看書的類型有很大程度上的相似性，通常人們認為兩個人的看書(接受的知識)類型一致可能會導致成績水平也趨于一致，因此可以把兩個學生看書類型的相似度作為成績關聯的隱性屬性。本文通過計算余弦相似度來評判兩學生看書類型的相似度。

兩同學看書類型的詞頻向量為：

A、B向量夾角的余弦可以表示為：

(7)

得到A、B的余弦值cosθ= 0.707 106 781 186 547 6即為兩同學看書類型的相似度。表示為PSL規(guī)則為：

Booktype(ID1,SE,BOTY1)∧Booktype(ID2,SE,BOTY2)∧

Similarity(BOTY1,BOTY2)∧GoodScore(ID1,SE) ∧

(ID1-ID2)) ? GoodScore(ID2,SE)

其中：Similarity(BOTY1,BOTY2)為余弦相似度計算函數，(ID1-ID2)表示兩個學生不是同一個人。類似的，還可以對學生數據中其他屬性進行相似度計算。

2) 簡單知識規(guī)則。

在已有規(guī)則基礎上，本文還可以再增加一些簡單的常識。如：

課余學習時間越長，學生成績可能越好:

STUDYTIME(S,St) ∧ STUDYTIMEJUDGE(St) ?

GoodScore(S)

談戀愛可能會影響學習:

ROMANTIC(S,Ro) ∧ ROMANTICJUDGE(Ro) ?

家庭關系越好越可能學習好:

FAMREL(S,Fa) ∧ FAMRELJUDGE(Fa) ?

GoodScore(S)

缺課次數越多越可能成績差:

ABSENCES(S,Ab) ∧ ABSENCESJUDGE(Ab) ?

經常上網可能影響學習:

INTERNET(S,In) ∧ INTERNETJUDGE(In) ?

GoodScore(S)

這類規(guī)則對推理結果沒有決定性影響，但卻能讓推理結果的表達形式變得更加符合常理，例如：在不添加這些規(guī)則的情況下，推斷某同學S成績合格的概率可能為GoodScore(S)=0，這很難理解，在添加規(guī)則后GoodScore(S)=0.235,雖然該同學依然被分到成績不合格類，但卻擁有了一個成績合格的概率，這更符合人類正常的思維方式。

1.3.4 規(guī)則優(yōu)化

1) 推理。

PSL模型提供了最大概率推理(Most Probable Explanation，MPE)[2]和邊際概率推理兩種方法，前者是通過數據推斷邏輯規(guī)則包含原子的最可能概率值，后者是計算原子的概率取值區(qū)間。本文采用MPE推理機制。由于概率取值采用[0，1]內的連續(xù)值，使得MPE推理轉化成求最優(yōu)解的凸優(yōu)化過程。

2) 權重學習。

對于學習得到的規(guī)則，根據每條規(guī)則的置信度分配其在PSL內構建時的權重，如有X、Y、Z三條規(guī)則，它們的置信度分別為0.7、0.8、1.0，在將它們轉化成PSL規(guī)則時，可以將其置信度同時擴大多倍作為其權重。然而對于手工定義的規(guī)則，則需要進行權重學習。

在PSL模型權重學習時本文使用最大似然估計法[3]，應用梯度函數進行權重估計：

(8)

2 實驗與分析

2.1 實驗數據

本文使用真實數據集對模型進行評估。

1)UCI機器學習庫所提供的兩所葡萄牙學校的中學生數據集(http://archive.ics.uci.edu/ml/datasets/Student+Performance)。

葡萄牙中學生數據集 該數據集包含葡萄牙兩所中學的1 064條學生數據，數據通過學校提供和問卷收集，屬性包括學生成績、社會家庭情況和學校表現等相關特征，兩個文件分別提供數學(mat)和葡萄牙語(por)成績。其中：屬性G1、G2和G3分別是學生三次考試成績的分數，具有很強的相關性，這是因為學生學習是一個持續(xù)積累的過程，不會在短時間內突然變好或變壞。而該數據集的其他屬性并沒有區(qū)分是學生哪一個學期產生的，因此本文認為是學生長期的表現，所以為了模型推理的科學性，數據預處理過程中，本文對學生的三次成績求平均值作為目標屬性，再將分數大于10分(總分20分)的學生標記為成績合格。

2)中國某高校學生的日常數據集(http://www.dcjingsai.com/common/cmpt/學生成績排名預測_競賽信息.html)。

中國高校學生數據集 該數據集包含中國某高校的某個學院學生的60多萬條活動記錄，其中包含這些學生在三個學期的圖書館進出記錄、一卡通消費記錄、圖書館借閱記錄，以及學生在每個學期成績的相對排名。數據目錄如下：

成績信息包含學期、學號，以及相對排名。

借書信息包含學期、學號、書號、日期。

圖書門禁信息包含學期、學號、日期、時間。

消費信息包含學期、學號、地點、日期、時間、金額。

該數據集標識的學生成績只有學生相對排名，在數據預處理時，我們將成績排名在前200名(共538人)的學生標記為成績合格。

2.2 準備工作

2.2.1 評價指標

本文將對C5.0算法、手工定義規(guī)則的PSL，以及本文提出的C-PSL進行10次隨機實驗，隨機選擇80%的數據作為訓練數據，剩下20%作為測試數據，方法的準確度通過式(9)、(10)、(11)和(12)所示的精確率(Precision)、正確率(Accuracy)、召回率(Recall)和F1值來度量。

(9)

(10)

(11)

(12)

其中:TP表示判斷出成績合格的學生數量，FN表示成績合格的被判斷為不合格的學生數量，FP表示成績不合格被判斷為合格的學生數量；Precision即正確判斷的數量占識別出成績達標學生總數的比例，Accuracy為正確判斷的數量占總數的比例，Recall為正確判斷的數量占應識別出成績達標學生總量的比例，F1為準確率和召回率的調和平均數。

表2 混淆矩陣

2.2.2 Boosting選擇

由表3和表4可以看出，在多次隨機實驗中，使用Boosting所產生規(guī)則的數量遠遠超過未使用Boosting的情況，推理的平均正確率在葡萄牙中學生數據上只相差2.67%，中國高校學生數據上使用Boosting推理正確率反而降低，其原因在于，本文模型構建C5.0模塊的主要目的是通過C5.0算法從訓練數據進行Boosting迭代提取規(guī)則，而算法準確率的測試過程由驗證模塊單獨完成，這對于后續(xù)和PSL模型的比較會更加公平，由于該模型規(guī)則挖掘模塊中C5.0算法不能通過測試數據得到的推理結果進行迭代優(yōu)化而導致其在中國高校學生數據上使用Boosting時推理準確率反而降低。另一方面，對于本文研究，要將大量規(guī)則全部寫入PSL將耗費更多的人工工作量和計算機資源，這違背了我們的研究初衷。因此，為了平衡規(guī)則數量，本文規(guī)則提取模塊只在葡萄牙中學生數據上使用Boosting。

表3 是否使用Boosting的推理效果對比

表4是否使用Boosting時產生的規(guī)則數對比

Tab. 4 Comparison of number of rules generatedwhen using and not using Boosting

2.3 實驗結果

本文在兩個數據集上對三種方法進行實驗，根據模型對學生成績達標情況的推斷能力進行性能評估。實驗配置如下。

C5.0 在葡萄牙中學生數據集上使用Boosting，中國高校學生數據集上不使用Boosting，兩種情況都使用交叉驗證，修建純度70，子分支最少記錄數7。

PSL 完全手工定義規(guī)則，僅有的參數為每條規(guī)則的權重，并且每條規(guī)則的權重由訓練數據訓練得到。

C-PSL C5.0學習的規(guī)則+手工定義規(guī)則。

表5和表6分別是C5.0、C-PSL和PSL在兩組數據集上測試的F1值和Accuracy值對比，葡萄牙中學生數據集不包含學期屬性，因此關于學期成績的前后關聯規(guī)則沒能在該數據集上被手動構建，結果表明，在葡萄牙中學生數據上C-PSL的推理性能優(yōu)于C5.0和PSL；對于中國高校學生數據集，規(guī)則全部被構建，可以看出，C-PSL推理的正確率和F1值依然優(yōu)于C5.0，而表6中之所以C-PSL和PSL的推理正確率相當，是因為此時C-PSL和PSL的規(guī)則有很大一部分是人為定義，而這部分重合的規(guī)則起到了顯著作用，這同時也說明了C-PSL是延續(xù)了PSL的優(yōu)秀推理能力；從兩組數據實驗得到的F1值和Accuracy值的對比表明，C-PSL在學生成績預測問題上可行且推理性能較優(yōu)。

表5 三種方法在兩個數據集中的F1值對比 %

表6 三種方法在在兩個數據集中的正確率對比 %

2.4 補充實驗

為了進一步驗證本文模型的性能，本文將C-PSL和支持向量機 (Support Vector Machines, SVM)[8]、邏輯回歸(Logistic Regression, LR)[9]、貝葉斯網絡(Bayesian Network, BN)[10]、K-最近鄰(K-Nearest Neighbors,KNN)[11]等算法進行10次隨機對比實驗，結果如圖2所示。

由圖2可以看出，在葡萄牙中學生數據，SVM表現優(yōu)秀，然而SVM的分類過程卻很難人為理解，雖然C-PSL推理正確率次于SVM，但是由于C-PSL使用一階邏輯規(guī)則表達推理，其過程的可讀性是SVM無法比擬的；在中國高校學生數據上，C-PSL性能遠超過其他算法，其原因在于，該數據中包含大量具有關聯關系的數據，在使用C-PSL進行推理時加入了眾多手工定義的關聯規(guī)則，而這些關聯關系，卻幾乎不能用SVM等算法進行構建，這正是C-PSL手工定義規(guī)則的優(yōu)勢所在。

2.5 C-PSL穩(wěn)定性

本文所提出C-PSL模型基于PSL、C-PSL應該也應繼承PSL的推理穩(wěn)定性，下面的實驗結果證實了這一點。表7顯示了C5.0、C-PSL和PSL在兩數據集(其中1為葡萄牙中學生數據，2為中國高校學生數據)上各10次實驗的F1值和Accuracy值的標準差。

從10次實驗的F1值和Accuracy值的標準差對比可以看出，本文所提模型(C-PSL)和PSL穩(wěn)定性相當，這正是說明了C-PSL繼承了PSL優(yōu)秀的穩(wěn)定性，并且C-PSL的穩(wěn)定性優(yōu)于C5.0算法。

圖2 六種算法在兩個數據集中分類正確率對比

3 結語

本文提出了一種面向概率軟邏輯的規(guī)則半自動學習方法(C-PSL), 該方法使用C5.0算法作為PSL的規(guī)則挖掘模型，同時輔以手工定義規(guī)則處理數據中的關聯關系，讓PSL成為一種由數據和知識共同驅動的推理模型。通過對兩個屬性差別很大的學生數據集的實驗表明，在成績預測問題上該方法比C5.0算法和PSL具有更高的推理準確度; 并且，和以往純手工定義規(guī)則的方法相比，該方法能大幅降低手工成本; 此外，本文提出的模型，在兩組數據上推理的穩(wěn)定性也優(yōu)于C5.0 算法。對于實際應用，該方法可以通過預測學生成績的方式幫助學生及時發(fā)現生活學習習慣的不足，學校也可將其作為調整教學管理方案的參考因素。

下一步工作主要集中在兩個方面：1)進一步探索規(guī)則優(yōu)化策略，讓模型得到更高質量的規(guī)則; 2)研究基于關聯規(guī)則的自動挖掘方案。