戴望州 周志華

(計算機(jī)軟件新技術(shù)國家重點(diǎn)實驗室(南京大學(xué)) 南京 210023)

規(guī)則學(xué)習(xí)是機(jī)器學(xué)習(xí)中以符號規(guī)則為模型表達(dá)方式的一個分支，主要屬于符號主義學(xué)習(xí)的內(nèi)容.在文獻(xiàn)[1]中有對規(guī)則學(xué)習(xí)的基本介紹，本文主要關(guān)注以一階邏輯(first-order logic， FOL)為表達(dá)語言的歸納邏輯程序設(shè)計(inductive logic programming，ILP)[2].一階邏輯是一種形式系統(tǒng)[3].與只能陳述簡單命題的命題邏輯相比，F(xiàn)OL引入了謂詞、函數(shù)和量詞等更多詞匯，它可以通過謂詞來量化地陳述命題，因此也被稱為一階謂詞演算.

基于文獻(xiàn)[1]的界定，ILP指以FOL歸納理論為基礎(chǔ)，以FOL規(guī)則為模型的機(jī)器學(xué)習(xí)方法.與其他種類機(jī)器學(xué)習(xí)方法相比，ILP能夠在學(xué)習(xí)過程中以FOL規(guī)則的形式引入復(fù)雜領(lǐng)域知識，并能自然地處理學(xué)習(xí)問題中的復(fù)雜推理.此外，它學(xué)得的模型具有較好的可理解性，這使得用戶和領(lǐng)域?qū)＜夷軌蚍奖愕貙W(xué)習(xí)成果進(jìn)行解讀和研究.

1 發(fā)展歷程

“歸納邏輯程序設(shè)計”的命名來自于Muggleton[2]于1991年發(fā)表的奠基性論文以及同年召開的第一屆國際歸納邏輯程序設(shè)計研討會，它是如今國際歸納邏輯程序設(shè)計會議(International Conference on Inductive Logic Programming)的前身.

20世紀(jì)七、八十年代出現(xiàn)并流行的專家系統(tǒng)[4]極大地推廣了人工智能實際應(yīng)用.專家系統(tǒng)的知識庫一般由一組符號邏輯規(guī)則構(gòu)成.早期專家系統(tǒng)中的規(guī)則必須由領(lǐng)域?qū)＜姨峁?，這不僅成本高，在許多任務(wù)中還由于專家知識難以總結(jié)或?qū)＜也辉阜窒碇R而難以完成，形成了所謂“知識工程瓶頸”.為了突破這個瓶頸，出現(xiàn)了許多以符號邏輯表達(dá)語言的機(jī)器學(xué)習(xí)方法[1].

一般來說，此類方法存在3種局限[2]：1)它們學(xué)得的模型一般為命題邏輯規(guī)則.受限于模型的表達(dá)能力，難以描述對象之間的“關(guān)系”(relation)，而在許多任務(wù)中關(guān)系信息非常重要.2)命題學(xué)習(xí)的輸入一般為屬性-值(attribute-value).許多領(lǐng)域知識難以被表示為這種形式，導(dǎo)致學(xué)習(xí)過程不易利用領(lǐng)域知識.3)命題規(guī)則只能由一組固定的屬性特征所對應(yīng)的原子構(gòu)成，學(xué)習(xí)過程不能自主地對原始特征空間進(jìn)行變換以彌補(bǔ)其不足.

為了解決這些問題，Muggleton[2]指出應(yīng)當(dāng)使用表達(dá)能力更強(qiáng)的FOL作為機(jī)器學(xué)習(xí)的形式化語言.邏輯程序(logic programming)[5]作為計算機(jī)技術(shù)中應(yīng)用最廣泛的FOL系統(tǒng)之一，理所當(dāng)然地成為了首選.由于機(jī)器學(xué)習(xí)是一種從數(shù)據(jù)中自動“歸納”(induction)的方法，因此它與邏輯程序設(shè)計結(jié)合而誕生的學(xué)科便被命名為“歸納邏輯程序設(shè)計”.

事實上，早在20世紀(jì)70年代就已出現(xiàn)一些關(guān)于FOL歸納理論的先驅(qū)性工作[6-9]，例如對FOL歸納學(xué)習(xí)可行性的證明，為ILP的出現(xiàn)奠定了基礎(chǔ).其中Plotkin[6]提出的“最小一般泛化”和“相對最小一般泛化”后來成為ILP的基礎(chǔ)運(yùn)算.20世紀(jì)80年代中期，開始出現(xiàn)Marvin[10]等初步運(yùn)用FOL歸納的機(jī)器學(xué)習(xí)算法.20世紀(jì)80年代后期出現(xiàn)了許多關(guān)于FOL歸納理論的研究，例如Muggleton的逆歸結(jié)[11-13]以及Rouveirol和Puget[14]的工作等.Muggleton[12]首次提出使用FOL歸納來實現(xiàn)一階謂詞發(fā)明[12]，使得機(jī)器學(xué)習(xí)過程能自動對不夠完善的背景知識進(jìn)行彌補(bǔ)，這期間也出現(xiàn)了最早的ILP系統(tǒng)Cigol[12].

由于邏輯程序無法直接描述不確定性，ILP難以對帶噪聲的數(shù)據(jù)進(jìn)行學(xué)習(xí).為了解決此問題，Dantsin[32]首次在邏輯程序中引入概率分布，提出了概率邏輯程序(probabilistic logic programming， PLP)，Poole[33]研究了PLP中的概率推斷，Sato[34]則在Dantsin[32]的基礎(chǔ)上為PLP定義了嚴(yán)格的FOL語義.2004年De Raedt[35]等人提出了以PLP為模型的機(jī)器學(xué)習(xí)框架，它是ILP的一種概率擴(kuò)展，被稱為概率歸納邏輯程序設(shè)計(probabilistic inductive logic programming， PILP).在這些工作的基礎(chǔ)上，研究者們提出了眾多PLP模型[36-43]與PILP算法[44-48].

2010年至今，ILP領(lǐng)域的研究又取得進(jìn)一步發(fā)展.例如在傳統(tǒng)的ILP理論方面，研究者們提出采用二階邏輯誘導(dǎo)來進(jìn)行FOL歸納[49-50]，此類ILP方法在謂詞發(fā)明和學(xué)習(xí)遞歸規(guī)則的能力上取得了突破；PILP領(lǐng)域依舊十分活躍[51-58]，被成功應(yīng)用在自然語言處理和生物信息學(xué)等許多兼具不確定性與復(fù)雜領(lǐng)域知識的實際任務(wù)中[59-64]；此外，隨著近年來深度學(xué)習(xí)的崛起，為了進(jìn)一步提高ILP的學(xué)習(xí)效率，研究者們開始嘗試在ILP中嵌入可微構(gòu)件[65-66]，并取得了一定成效.

2 基本內(nèi)容

在不做特別說明的情況下，本文將以漢字、阿拉伯?dāng)?shù)字和小寫英文字母開頭的詞代表謂詞、函數(shù)與常量，以大寫英文字母開頭的詞代表變量和FOL公式，并省略FOL公式中的全稱量詞“?”.

不含連接詞的FOL公式被稱為原子公式(atom)，例如“奇數(shù)(X)”；原子公式及其否定式被稱為邏輯文字(literal)，例如“奇數(shù)(X)”；當(dāng)公式中不含變量時被稱為“具體的”(grounded)，具體的原子公式被稱為具體事實(ground facts)，例如“奇數(shù)(3)”.

ILP模型是由邏輯公式組成的集合：

A←B1∧B2∧…∧Bn.

(1)

其中，A和Bi分別為FOL原子和文字.一般稱這種公式為FOL規(guī)則，其中“←”右邊的部分是有限個文字的合取，被稱為規(guī)則體(body)，表示此規(guī)則的前提；“←”左邊的A是一個FOL原子，被稱為規(guī)則頭(head)，表示規(guī)則的結(jié)果；“←”是數(shù)理邏輯中的蘊(yùn)涵符，表示“推出”關(guān)系；n≥0為規(guī)則長度.該規(guī)則表示：“若B1,B2,…,Bn均成立，則A也成立”.

FOL系統(tǒng)的語義被體現(xiàn)在FOL公式的賦值(assignment)中.最基本地，可以對每一個具體事實進(jìn)行賦值，令其為true或為false.然后FOL系統(tǒng)會按照一定規(guī)則進(jìn)行演算，從而得到其他公式的真值.若存在一種賦值方使得某公式為true，則稱此公式為可滿足的(satisfiable).公式(集)Γ與T之間的可滿足性被稱為“語義蘊(yùn)涵”(entailment)，記為“ΓT”.它表示一切令Γ為真的賦值也使得T為真.公式(集)之間還存在一種“語構(gòu)蘊(yùn)涵”(implica-tion)關(guān)系，記為“ΓT”，一般讀作“Γ可推出T”.它表示?？梢詰{借FOL公理證明出T.

對于一般的形式系統(tǒng)，這2種蘊(yùn)涵關(guān)系并不等價.若一個形式系統(tǒng)有(ΓT)→(ΓT)，則稱該系統(tǒng)為“完備的”(complete)[3].對機(jī)器學(xué)習(xí)而言，若令Γ和T分別表示假設(shè)(hypothesis)和訓(xùn)練樣例(example)，那么對完備的學(xué)習(xí)算法來說，其假設(shè)空間必然包含所有滿足訓(xùn)練樣例的假設(shè).

2.1 學(xué)習(xí)任務(wù)

ILP主要關(guān)注“概念學(xué)習(xí)”[1]，即學(xué)習(xí)一個關(guān)于目標(biāo)概念(target concept)的描述(該描述也可視為一個單類別分類器).學(xué)習(xí)過程的輸入是一組關(guān)于目標(biāo)概念的樣例和背景知識(background knowledge)，輸出為一個滿足所有樣例的假設(shè)，即學(xué)得模型.本文將背景知識記為B，假設(shè)模型記為H，訓(xùn)練樣例記為E=E+∪E-，其中E+和E-分別代表正負(fù)樣例.那么，概念學(xué)習(xí)任務(wù)可以用FOL語言形式化為

B∪HE.

(2)

對于傳統(tǒng)的概念學(xué)習(xí)問題來說，B和E的形式一般為屬性-值數(shù)據(jù)集，E中的每個示例(instance)均被表示為一個特征向量，H可以是任何形式.而對ILP來說，這里的B,E和H均為邏輯程序[5].通常情況下，E是一組關(guān)于目標(biāo)概念的具體事實；B則是一系列關(guān)于原始概念(primitives)的具體事實；H是一個FOL規(guī)則集，每條規(guī)則均由原始概念組成.

表1[1]展示了一個ILP任務(wù)所使用的數(shù)據(jù)集.其中的原始概念為瓜與瓜之間在某些屬性上的比較關(guān)系；每行是一個關(guān)于原始概念的具體事實；目標(biāo)概念是“更好”.此類數(shù)據(jù)集中的條目不再是關(guān)于某一個對象的特征或標(biāo)記，而是多個對象之間的“關(guān)系”.故而ILP的任務(wù)屬于關(guān)系學(xué)習(xí)(relational learning)[1]，此類數(shù)據(jù)集也被稱為關(guān)系型數(shù)據(jù)集(relational data).

Table 1 An Example of Relational Dataset表1 關(guān)系型數(shù)據(jù)集

對象間的關(guān)系可能十分復(fù)雜，例如表1中的目標(biāo)概念“更好”便是一個遞歸關(guān)系：

更好(X,Y)←更好(X,Z)∧更好(Z,Y).

“歸納邏輯程序設(shè)計中”的“歸納”是邏輯系統(tǒng)中演繹(deduction)推理的逆過程.“演繹”指從一般規(guī)律出發(fā)推演出具體結(jié)論的特化(specialization)過程.譬如式(2)自左向右所描述的便是以B∪H作為前提，最終推導(dǎo)出結(jié)論E的演繹推理.而“歸納”則與演繹相反，它需要從具體的樣例出發(fā)，總結(jié)出一般規(guī)律以概括這些樣例，故而它是一個泛化(generalization)過程.換言之，ILP可視為FOL中演繹推理的逆運(yùn)算.

表2總結(jié)了FOL中常見的演繹和歸納運(yùn)算.大部分ILP方法[11-12,14-16,67]均源自這些歸納運(yùn)算.此外，還有一些ILP系統(tǒng)試圖先將關(guān)系型數(shù)據(jù)轉(zhuǎn)化為屬性-值數(shù)據(jù)，再使用命題學(xué)習(xí)技術(shù)來獲取FOL規(guī)則[25,68-70].本節(jié)將簡要介紹這些基本的ILP方法.

Table 2 Deduction and Induction Operations in FOL表2 FOL中的演繹與歸納運(yùn)算

2.2 最小一般泛化

Robinson[71]提出的“合一”(unification)是最簡單的FOL演繹運(yùn)算，其目標(biāo)是將邏輯變量替換(substitute)為常量以使2個邏輯文字相等，這可以直觀地理解為對背景知識B進(jìn)行“查詢”[1].例如當(dāng)B中存在事實“A1=a(1,2)”時，若欲推出“A2=a(X,2)”的賦值，只需將A2與A1合一即可得到一個替換“θ={X=2}”使得A2θ=A1，即當(dāng)X=2時A2為true.合一過程中同時存在多種可行的替換時，往往希望通過替換最少的變量來使合一成立，這被稱為“最一般合一”(most general unification, MGU).

合一的逆運(yùn)算是由Popplestone[72]所提出的“泛化”運(yùn)算，它反過來將原子公式中的常量替換為變量以使邏輯文字變得更一般.MGU的逆運(yùn)算是Plotkin[6]提出的最小一般泛化(least general gener-alization, LGG)，它能夠通過替換最少的常量使得FOL公式的泛化性最強(qiáng).例如，若B中同時存在2條具體規(guī)則：

1) 更好(瓜1,瓜2)←色澤更黑(瓜1,瓜2).

2) 更好(瓜3,瓜2)←色澤更黑(瓜3,瓜2).

LGG可將它們中的常量代換為變量，以得到一條能夠概括這2條規(guī)則的一般規(guī)則：

更好(X,瓜2)←色澤更黑(X,瓜2).

在ILP問題中，B∪E一般為關(guān)于原始概念和目標(biāo)概念的具體事實，不存在可供LGG直接泛化的具體FOL規(guī)則.因此Plotkin[7]提出先用B∪E來生成關(guān)于目標(biāo)概念的具體規(guī)則，再使用LGG對它們進(jìn)行泛化.例如根據(jù)表1中的所有事實即可構(gòu)造出具體規(guī)則：

更好(瓜2,瓜3)← 色澤更黑(瓜2,瓜3)∧

根蒂更蜷(瓜3,瓜4)∧

…

這種根據(jù)全體B∪E生成的具體FOL規(guī)則后來被稱為飽和規(guī)則(saturation)[14]；由于針對飽和規(guī)則進(jìn)行的LGG與B∪E相關(guān)，所以這種LGG被稱為相對最小一般泛化(relative LGG, RLGG)[7].

Plotkin[7]證明對于任意FOL文字集合S，只要它不包含矛盾文字——即不存在A使得A∈S且(A)∈S，則可通過LGG得到至少一條可滿足S的非空FOL規(guī)則R.當(dāng)B與E分別為由n和m個具體事實構(gòu)成的集合時，RLGG可以求出所有滿足式(2)的H，但最壞情況下學(xué)得的規(guī)則將包含O((n+1)m)個文字[8].

但是，若B中包含形式不受限制的FOL公式，則(R)LGG運(yùn)算無法保證完備性[8].此外，若目標(biāo)概念必須由多條FOL規(guī)則才能表示，則(R)LGG將無法學(xué)得正確的模型[8].因此，一般情形下基于(R)LGG的ILP不滿足完備性.

基于RLGG歸納的代表性ILP算法是Muggleton和Feng[24]提出的Golem，它有較高的學(xué)習(xí)效率，是早期應(yīng)用最廣泛的ILP系統(tǒng)之一.

2.3 逆歸結(jié)

在合一的基礎(chǔ)上，Robinson[71]提出了歸結(jié)原理(resolution principle)以處理更復(fù)雜的多步演繹.它試圖借助MGU運(yùn)算來找到背景知識與演繹目標(biāo)中相反的項，然后對它們進(jìn)行消解.將歸結(jié)原理的過程逆轉(zhuǎn)過來便構(gòu)成一種FOL歸納運(yùn)算.Muggleton[11-12]首次將該方法應(yīng)用于機(jī)器學(xué)習(xí)，并將它命名為逆歸結(jié)(inverse resolution).文獻(xiàn)[1]中對FOL中的歸結(jié)原理與逆歸結(jié)有詳細(xì)介紹.

圖1展示了4種逆歸結(jié)運(yùn)算.其中，p，q和r代表規(guī)則頭中的原子公式；A，B和C代表規(guī)則體中的FOL文字集合；每種運(yùn)算的上下2行分別為逆歸結(jié)的輸入與輸出；二者間的箭頭代表逆轉(zhuǎn)后的歸結(jié)原理[1].

Fig. 1 Four kinds of inverse resolution operators圖1 4種逆歸結(jié)運(yùn)算

逆歸結(jié)首次實現(xiàn)了FOL歸納中的謂詞發(fā)明[12]，它在學(xué)習(xí)過程中能夠自動構(gòu)建背景知識B中未出現(xiàn)的概念，例如圖1內(nèi)構(gòu)(intra-construction)與互構(gòu)(inter-construction)運(yùn)算輸出的新原子q和r.新發(fā)明的謂詞可作為新的“原始概念”被用于構(gòu)成H.直觀來看，謂詞發(fā)明是當(dāng)B中的原始概念不足以簡潔地描述目標(biāo)概念時，ILP將某些邏輯文字的組合歸納為一個事先未定義的新概念，并將之用于構(gòu)建H，以減少H的規(guī)則條數(shù)或者規(guī)則長度.換言之，謂詞發(fā)明能夠?qū)所定義的領(lǐng)域結(jié)構(gòu)進(jìn)行補(bǔ)充，它可以幫助用戶對領(lǐng)域建立新的認(rèn)識[2].

對命題規(guī)則學(xué)習(xí)而言，只需吸收與內(nèi)構(gòu)2種運(yùn)算即可保證逆歸結(jié)的完備性[11]，但對ILP該結(jié)論并不成立[13].

基于逆歸結(jié)的Duce[11]和Cigol[12]是最早實現(xiàn)的ILP系統(tǒng)，它們分別被用于命題規(guī)則學(xué)習(xí)和ILP任務(wù)中，后者第一次實現(xiàn)了FOL中的謂詞發(fā)明.逆歸結(jié)的缺點(diǎn)在于內(nèi)、互構(gòu)運(yùn)算會不斷地對規(guī)則集進(jìn)行擴(kuò)充，而得到的新規(guī)則又會作為下一階段逆歸結(jié)的輸入，從而導(dǎo)致生成更多規(guī)則.此外，這些新謂詞、新規(guī)則的可滿足性在學(xué)習(xí)過程中很難驗證.因此在缺乏有效的剪枝策略時，逆歸結(jié)運(yùn)算會造成組合爆炸.所以Cigol的效率遠(yuǎn)不如基于RLGG的Golem[24].

2.4 逆語構(gòu)蘊(yùn)涵

2.2節(jié)和2.3節(jié)講述的2種FOL歸納運(yùn)算均無法滿足完備性，根本原因在于它們所采用的基礎(chǔ)泛化運(yùn)算LGG與FOL中的語構(gòu)蘊(yùn)涵關(guān)系“→”并不等價[15].

“P是Q的LGG”僅代表公式P可以通過變量替換與Q合一，不妨將這種關(guān)系記為“Pθ?Q”，其中θ代表合一時使用的變量替換.而語構(gòu)蘊(yùn)涵關(guān)系“P→Q”的本義是“P可推出Q”.事實上，若Pθ?Q則必有P→Q；反之則并不成立.例如，考慮2個FOL公式：

P≡p(f(X))←p(X)，
Q≡p(f(f(X)))←p(X)，

使用f(x)替換掉P中的X得到:

R≡p(f(f(x)))←p(f(X)).

再對P，R使用三段論(modus ponens)[3]即可證P→Q，即P蘊(yùn)涵Q；但是，P卻無法通過任何變量替換來使之等價于Q.也就是說，Q無法通過LGG得到P.因此LGG不能保證FOL歸納的完備性.

可以看到，上例中從P到Q的推導(dǎo)過程只利用了規(guī)則P自身，因此Q被稱為由P“自歸結(jié)”(self-resolution)得到.為了補(bǔ)全LGG運(yùn)算，Muggleton[15]給出了完備語構(gòu)蘊(yùn)涵的3種情況.在FOL中，若P→Q，則要么Q恒真；要么Pθ?Q；要么?R(θR?Q)，其中R可通過對P不斷進(jìn)行自歸結(jié)得到.

依據(jù)該結(jié)論，Muggleton[15]給出了對FOL歸納完備的逆語構(gòu)蘊(yùn)涵(inverse implication)運(yùn)算，它在使用LGG對具體規(guī)則進(jìn)行泛化的同時，還需對所有LGG輸出的中間結(jié)果R進(jìn)行逆歸結(jié)，以找到所有可通過自歸結(jié)得到R的規(guī)則R′.根據(jù)上面的結(jié)論，只需令H=R∪R′即可保證FOL歸納的完備性.

事實上，在FOL中能夠進(jìn)行自歸結(jié)的公式均為遞歸公式，即類似于“p(f(X))←p(X)”這樣規(guī)則體與規(guī)則頭中出現(xiàn)相同謂詞的FOL規(guī)則.在逆語構(gòu)蘊(yùn)涵出現(xiàn)之前，基于(R)LGG與逆歸結(jié)的ILP無法處理此類遞歸概念.

遺憾的是，找尋遞歸語句的逆自歸結(jié)公式是一個不可判定(undecidable)[3]問題，所以完備的逆語構(gòu)蘊(yùn)涵只停留在理論階段，并未形成真正的算法.目前為止，基于逆語構(gòu)蘊(yùn)涵思想的ILP方法僅有Idestam-Almquist[67]在對其進(jìn)行放松后提出的逆T-語構(gòu)蘊(yùn)涵.

2.5 逆語義蘊(yùn)涵

2.4節(jié)介紹的(R)LGG、逆歸結(jié)和逆語構(gòu)蘊(yùn)涵的目標(biāo)均是對可證關(guān)系(即“→”)進(jìn)行逆轉(zhuǎn)，它們很難保證FOL歸納的完備性.為了解決“→”帶來的問題，Muggleton[16-17]提出應(yīng)當(dāng)從FOL語義——即B∪H對E可滿足性的角度來進(jìn)行歸納.

基于該想法，Muggleton[16]提出了語義蘊(yùn)涵“”的逆運(yùn)算——逆語義蘊(yùn)涵(inverse entailment).通俗地理解，它基于“逆否命題與原命題等價”這一原則，將式(2)等價地轉(zhuǎn)化為

B∪EH.

(3)

這種做法巧妙地將原歸納問題化歸為一個演繹問題：即通過B∪E來推導(dǎo)出可能的H，最后只需將推導(dǎo)出的結(jié)果取反，即可得到原問題所求解的H.

具體來說，在應(yīng)用逆語義蘊(yùn)含時，先要將所有樣例E取反得到E，再對B∪E進(jìn)行演繹得到⊥.由于演繹推理得到的結(jié)果只能是一組具體事實，因此不能將⊥直接取反作為H.不過，若H存在，則由式(3)可知(⊥H)∧(H⊥).根據(jù)“∧”的右半部分，只需先將⊥中所有具體事實取反，再進(jìn)行泛化即可得到H.也就是說，逆語義蘊(yùn)涵的步驟是“先特化、后泛化”.

理論上，對形如式(1)的FOL規(guī)則集合，逆語義蘊(yùn)涵能保證歸納的完備性[17]，但這在實際操作中卻并不簡單.一個主要原因是在進(jìn)行式(3)中的演繹推理時難以保證得到的⊥形式和數(shù)量足夠豐富.例如對2.4節(jié)提到的遞歸公式，它們通過自歸結(jié)演繹得到的事實可能有無窮多個.因此一旦B中存在遞歸規(guī)則，就無法保證獲得足夠大的⊥并泛化出一切滿足式(3)的H.所以，在實現(xiàn)過程中往往要引入一些先驗來對⊥的形式和演繹過程進(jìn)行約束，在保證逆語義蘊(yùn)涵的效率的同時使之盡可能完備.

最早基于逆語義蘊(yùn)涵的ILP方法是Muggleton[16]于1995年提出的Progol，它通過設(shè)置超參數(shù)來約束⊥的大小；并使用模式聲明(mode declaration)來保證⊥中事實的形式足夠豐富.而在對⊥進(jìn)行泛化時，Progol還提出使用精化算子(refinement operator)[18]來對搜索過程進(jìn)行剪枝來提高學(xué)習(xí)效率，避免在進(jìn)行泛化時出現(xiàn)冗余規(guī)則.

2.6 命題化

基于命題化方法[68]的ILP試圖先將關(guān)系型數(shù)據(jù)轉(zhuǎn)化為屬性-值數(shù)據(jù)，然后再使用命題規(guī)則學(xué)習(xí)技術(shù)來建立模型.命題化數(shù)據(jù)中的特征為FOL文字或FOL文字構(gòu)成的合取式，因此命題化方法學(xué)得的“命題規(guī)則”事實上仍舊是FOL規(guī)則.

Table 3 An Example of Propositionalized Dataset表3 命題化數(shù)據(jù)集

與其他ILP方法相比，基于命題規(guī)則學(xué)習(xí)的命題化方法既能更自然地處理領(lǐng)域中的噪聲，又擁有更高的學(xué)習(xí)效率.但它在生成數(shù)據(jù)集時需要耗費(fèi)一定時間.此外，它的假設(shè)空間十分依賴于關(guān)系型特征的構(gòu)造，若領(lǐng)域中的關(guān)系過于復(fù)雜，則需要生成大量的關(guān)系型特征才能保證學(xué)得足夠好的H.此外，基于命題化方法的ILP不能學(xué)習(xí)遞歸規(guī)則，因此無法保證FOL歸納的完備性.所以，命題化方法一般被應(yīng)用于以個體為中心的領(lǐng)域[68]，即目標(biāo)概念只描述個體屬性而不涉及個體間關(guān)系的領(lǐng)域.

2.7 ILP的PAC可學(xué)習(xí)性

基于命題規(guī)則學(xué)習(xí)的PAC可學(xué)習(xí)性結(jié)論[19,73]，Page和Frisch[74]證明了單條不含函數(shù)符且非遞歸的一類特殊FOL公式通過LGG是PAC可學(xué)習(xí)的.此類FOL公式形如式(1)，但所有出現(xiàn)在{B1,B2,…,Bn}中的FOL變量必須也在A中出現(xiàn).

上述結(jié)論只適用于單條FOL規(guī)則學(xué)習(xí)，為了研究規(guī)則集可學(xué)習(xí)性，D?eroski等人[20]定義了一類“確定子句”來對FOL規(guī)則的形式進(jìn)行約束.這里的“確定”代表對于式(1)規(guī)則體中的每個文字Bi：若Bi中存在一個變量X從未在其之前的文字A,B1,…,Bi-1中出現(xiàn)，那么對X來說，一旦A,B1,…,Bi-1中除X以外的變量取值確定，則X的取值也能唯一確定.他們證明了對于符合某些簡單概率分布、不含函數(shù)符且無遞歸的FOL確定子句集，可在多項式時間內(nèi)將其擴(kuò)張為PAC可學(xué)習(xí)的命題規(guī)則集.

若不對目標(biāo)概念所服從的概率分布進(jìn)行假設(shè)，D?eroski等人[21]證明不含函數(shù)符、無遞歸且每條規(guī)則長度有限的一類FOL規(guī)則集是PAC可學(xué)習(xí)的.但此時學(xué)習(xí)算法的時間復(fù)雜度關(guān)于目標(biāo)概念中最大規(guī)則的長度呈指數(shù)級增長.Cohen[22]進(jìn)一步去掉了該結(jié)論中對“非遞歸”的要求，但增加了一些額外假設(shè)，例如每個FOL變量在規(guī)則中的出現(xiàn)次數(shù)有限.

雖然陸續(xù)有理論證明某些形式受約束的FOL規(guī)則集PAC可學(xué)習(xí)，但Kietz[23]證明，一般形式的FOL公式集不是PAC可學(xué)習(xí)的.這是因為ILP在搜索H的過程中必須不停地檢測它是否與B∪E沖突，而對于形式不加約束的B和E，這是NP-hard問題.

這些結(jié)果均說明FOL規(guī)則學(xué)習(xí)在本質(zhì)上比命題規(guī)則學(xué)習(xí)更加困難.Cohen與Page[75]總結(jié)了ILP關(guān)于PAC可學(xué)習(xí)性研究的大部分結(jié)論.他們指出，F(xiàn)OL模型遠(yuǎn)比命題規(guī)則復(fù)雜，所以不能僅以命題規(guī)則學(xué)習(xí)的樣例數(shù)與規(guī)則復(fù)雜度來衡量FOL模型的可學(xué)習(xí)性，而應(yīng)當(dāng)試圖從FOL模型本身的角度對可學(xué)習(xí)性進(jìn)行探索.

3 研究進(jìn)展

第2節(jié)所介紹的基本ILP方法有3個主要局限：1)除了逆歸結(jié)以外，其他實用性更強(qiáng)的ILP方法均無法直接實現(xiàn)謂詞發(fā)明，并且對遞歸規(guī)則的學(xué)習(xí)效率較低；2)受FOL語言表達(dá)能力的限制，大部分ILP方法不能在數(shù)據(jù)帶噪聲的情況下進(jìn)行學(xué)習(xí)；3)由于ILP的假設(shè)空間結(jié)構(gòu)十分復(fù)雜，進(jìn)行高效的學(xué)習(xí)有相當(dāng)?shù)睦щy.

近年來，ILP研究者們在這3個問題上均取得了進(jìn)展.其中以元解釋學(xué)習(xí)(meta-interpretive learning, MIL)[50]為代表的二階誘導(dǎo)方法較好地解決了謂詞發(fā)明和遞歸規(guī)則學(xué)習(xí)的問題；概率歸納邏輯程序(PILP)[35]則對ILP進(jìn)行了概率擴(kuò)展，使之能夠應(yīng)對學(xué)習(xí)問題中的噪聲；還有一些工作嘗試在ILP中嵌入神經(jīng)網(wǎng)絡(luò)等可微構(gòu)件[65-66]，利用梯度下降和誤差反向傳播算法來加速ILP學(xué)習(xí).本節(jié)將對這些方向中的代表性工作進(jìn)行簡要介紹.

3.1 二階誘導(dǎo)推理

誘導(dǎo)推理(abductive reasoning)[76]是在演繹和歸納之外的另一種邏輯推理形式.它能根據(jù)背景知識為已觀測事實找到一種合理的原因作為解釋，因此也被稱為“溯因”推理.例如，若背景知識中存在如下3條FOL規(guī)則：

1) 出汗(X) ←覺得熱(X),

2) 覺得熱(X)←天氣熱,

3) 覺得熱(X)←運(yùn)動后(X).

那么，在觀測到“出汗(張三)”為true時，根據(jù)第1條規(guī)則便能誘導(dǎo)出唯一的原因：“覺得熱(張三)”.接下來，根據(jù)后2條規(guī)則我們可以進(jìn)一步推測出：要么現(xiàn)在天氣熱、要么張三剛剛運(yùn)動完、要么此二者均成立.可以看到，誘導(dǎo)推理是一種已知一般規(guī)則(因果關(guān)系)，從具體事實(關(guān)于某個對象的觀測事實)中推演出其他具體事實(發(fā)生在該對象身上的特殊原因)的過程.

遺憾的是，ILP的目標(biāo)并不是獲得關(guān)于某個概念的具體事實，而是學(xué)習(xí)由一般規(guī)則組成的FOL規(guī)則集H.因此，上述FOL誘導(dǎo)推理不能被直接用于ILP.為此，Inoue等人[49]提出了元誘導(dǎo)(meta-level abduction)方法，試圖使用二階邏輯誘導(dǎo)來進(jìn)行FOL歸納.

早在2003年，Lloyd[77]就曾指出高階邏輯(higher-order logic)語言[3]或許能更有效地形式化并解決FOL歸納問題.二階邏輯(second-order logic, SOL)即是一種高階邏輯，它可以對FOL中的謂詞和函數(shù)進(jìn)行量化，因此對于SOL公式來說，F(xiàn)OL公式只是它的具體個例.比如對于SOL規(guī)則：

P(X,Y)←Q(X,Z)∧R(Z,Y).

其中,P,Q和R均為SOL變量，可被替換為任意二元FOL謂詞.若將它們?nèi)刻鎿Q為“更好”，便可得到關(guān)于“更好”關(guān)系的遞歸FOL規(guī)則.元誘導(dǎo)學(xué)習(xí)試圖將SOL規(guī)則作為背景知識B、將訓(xùn)練樣例E作為觀測到的具體事實來進(jìn)行誘導(dǎo)推理，最終得到的便是具體的SOL規(guī)則集合，即FOL規(guī)則集H.

不過，元誘導(dǎo)學(xué)習(xí)并未實現(xiàn)真正意義上的SOL誘導(dǎo).它需要將描述原始概念的FOL謂詞轉(zhuǎn)化為邏輯常量，并將背景知識中的SOL規(guī)則轉(zhuǎn)化為FOL規(guī)則，以將SOL誘導(dǎo)表示為FOL中的誘導(dǎo)問題進(jìn)行求解.最終還需將誘導(dǎo)得出的具體事實進(jìn)行還原，才能獲得待求解的FOL規(guī)則集H.

Muggleton等人[50]提出的元解釋學(xué)習(xí)(meta-interpretive learning, MIL)在邏輯程序中實現(xiàn)了一個可以解釋SOL規(guī)則的元解釋器(meta-interpreter)，真正實現(xiàn)了SOL誘導(dǎo)推理.MIL允許用戶在B中定義一組被稱為“元規(guī)則”(metarule)的SOL公式BMR，并通過元解釋器來對這些元規(guī)則進(jìn)行SOL中的誘導(dǎo)推理.

MIL的目標(biāo)可以這樣描述：給定背景知識B、訓(xùn)練樣例E和SOL元規(guī)則BMR，MIL需要找到一種SOL變量替換θ將元規(guī)則的SOL變量替換為關(guān)于原始概念的FOL謂詞，以得到FOL規(guī)則(集)BMRθ，使得BMRθ∪BE.換言之，MIL通過令H=BMRθ將式(1)中對H的搜索轉(zhuǎn)化為對θ的搜索.

這種搜索是通過SOL中的誘導(dǎo)推理完成的，而誘導(dǎo)推理中的已觀測事實是“E可證”.因此MIL需要在對E的證明過程中誘導(dǎo)出θ的取值.以表2的任務(wù)為例，待證明的樣例為“E=更好(瓜2,瓜3)”，設(shè)此時BMR只包含一條元規(guī)則R≡P(X,Y)←Q(X,Y).證明過程開始時，MIL會將R的規(guī)則頭與E進(jìn)行合一，以表示E是可證明的結(jié)論，為此需采用變量替換：

θ1={P=更好,X=瓜2,Y=瓜3},

將其應(yīng)用于BMR中的元規(guī)則R，得到:

Rθ1=(更好(瓜2,瓜3)←Q(瓜2,瓜3)).

為了令證明成立，必須保證該規(guī)則體中的“Q(瓜2,瓜3)”賦值為true.通過對表2中的事實進(jìn)行查詢，可看出只需使用變量替換:

θ2={Q=色澤更黑}

即可令B∪Rθ1θ2E成立.保留θ1中的SOL變量替換可得{P=更好}，最終令即可得到一個候選假設(shè)模型

Rθ=(更好(X,Y)←色澤更黑(X,Y)).

顯然，MIL可看作一種以SOL元規(guī)則為模板進(jìn)行的FOL規(guī)則搜索.

由于SOL變量能被替換為任意FOL謂詞，MIL的規(guī)則搜索比基于FOL歸納運(yùn)算的ILP更加靈活：當(dāng)元規(guī)則頭和規(guī)則體中的SOL變量被替換為相同謂詞時，便形成了遞歸規(guī)則；當(dāng)元規(guī)則頭被替換為B中不存在的謂詞時，便實現(xiàn)了謂詞發(fā)明.

例如文獻(xiàn)[50]以樓梯的3D點(diǎn)云作為訓(xùn)練樣例，學(xué)會了關(guān)于樓梯概念的模型假設(shè)：

staircase(X)←s1(X).

staircase([X,Y,Z|Planes])←

s1([X,Y,Z])∧staircase([Z|Planes]).

s1([X,Y,Z])←vertical(X,Z)∧horizontal(Z,Y).

其中，(X,Z)，(Z,Y)和Planes均為點(diǎn)云中的平面；{X,Y,Z}為平面的邊界；謂詞vertical和horizontal分別表示平面的方向為垂直和水平，謂詞staircase(X)表示平面序列X是一段樓梯.該模型中第2條規(guī)則即為遞歸規(guī)則，而s1則是被發(fā)明的謂詞.經(jīng)過解讀可知s1代表“一級臺階”，而第2條規(guī)則表示“樓梯加上一級臺階依然是樓梯”.

顯然，MIL的假設(shè)空間結(jié)構(gòu)依賴于元規(guī)則的選取.若僅使用“P(X,Y)←Q(X,Y)”作為元規(guī)則，那么MIL將永遠(yuǎn)無法學(xué)會形式為P(X,Y)←Q(X,Z)∧R(Z,Y)的FOL規(guī)則.此外，由于MIL的誘導(dǎo)過程中可以使用BMR中的任意一條元規(guī)則作為模板，元規(guī)則的總數(shù)會影響MIL的搜索效率.Cropper與Muggleton[78-79]研究了元規(guī)則選擇對MIL假設(shè)空間完備性的影響，證明BMR只需包含2條元規(guī)則，其假設(shè)空間即可包含所有通用圖靈機(jī)可計算函數(shù).但對于一般的目標(biāo)概念H*，MIL通過這2條元規(guī)則學(xué)得的模型H′只能保證在語義上與H*等價.而在形式上，H′所包含的規(guī)則條數(shù)可能比H*多很多，這往往要求MIL在對樣例的證明過程中增加搜索深度.因此僅僅減少元規(guī)則條數(shù)不一定能夠提高M(jìn)IL的學(xué)習(xí)效率.

3.2 概率擴(kuò)展

3.2.1 概率邏輯程序

經(jīng)典FOL只能用于形式化“非真即假”的推理過程.為了在FOL中引入概率分布，需要對原始的FOL語義進(jìn)行擴(kuò)展——即允許邏輯事實依概率為真.那么式(2)的學(xué)習(xí)問題可以重寫為

(4)

式(4)不再要求H與訓(xùn)練樣例E絕對一致，僅要求H盡可能在對E賦值的判斷上少犯錯誤.

為了適應(yīng)模型語義的變化，還需對式(1)中FOL規(guī)則的語法進(jìn)行擴(kuò)展.一般可以采用如下形式的概率邏輯規(guī)則(probabilistic logic rules)：

p∷A←B1∧B2∧…∧Bn.

(5)

其中，p∈[0,1]為概率值.當(dāng)n=0時，式(5)退化為一個概率原子公式(probabilistic atom)p∷A，當(dāng)A不含變量時它被稱為概率事實(probabilistic facts)，它表示A是一個隨機(jī)變量，且A服從參數(shù)為p的二項分布.

由概率FOL規(guī)則構(gòu)成的邏輯程序被稱為概率邏輯程序[32]，為了使用概率邏輯程序進(jìn)行推理，必須嚴(yán)格定義其上的概率分布形式.

FOL系統(tǒng)的語義由領(lǐng)域內(nèi)所有具體事實的賦值決定，因此最直接的方法便是將概率分布定義在這些具體事實上，這種定義方式被稱為“分布語義”(distribution semantics)[34].它將領(lǐng)域中所有具體事實作為隨機(jī)變量，并在其上定義聯(lián)合概率分布.考慮圖2中的PLP模型：

0.8∷根蒂更蜷(瓜1,瓜2).
0.3∷敲聲更悶(瓜1,瓜2).
0.6∷色澤更黑(瓜1,瓜2).
false←根蒂更蜷(X,Y)∧根蒂更蜷(Y,X).
false←敲聲更悶(X,Y)∧敲聲更悶(Y,X).
false←色澤更黑(X,Y)∧色澤更黑(Y,X).
更好(X,Y)←根蒂更蜷(X,Y)∧敲聲更悶(X,Y).
更好(X,Y)←敲聲更悶(X,Y)∧色澤更黑(X,Y).

Fig. 2 An example of probabilistic logic program
圖2 概率邏輯程序示例

其中行1～3定義了3個帶權(quán)的具體事實，它們是該領(lǐng)域中分布的來源；其他幾行為一般的FOL規(guī)則.

若將PLP中所有FOL規(guī)則構(gòu)成集合記為R，所有概率事實的集合記為F.假設(shè)F中的概率事實相互獨(dú)立，W∈F是所有賦值為true的概率事實，那么W出現(xiàn)的概率為

(6)

例如，若W僅包含圖2中的前2個概率事實，那么它出現(xiàn)的概率為PF(W)=0.8×0.3×(1-0.6)=0.096.W加上原有的FOL規(guī)則集R即可得到一個普通的一階邏輯程序：

根蒂更蜷(瓜1,瓜2).
敲聲更悶(瓜1,瓜2).
false←根蒂更蜷(X,Y)∧根蒂更蜷(Y,X).
false←敲聲更悶(X,Y)∧敲聲更悶(Y,X).
false←色澤更黑(X,Y)∧色澤更黑(Y,X).
更好(X,Y)←根蒂更蜷(X,Y)∧敲聲更悶(X,Y).
更好(X,Y)←敲聲更悶(X,Y)∧色澤更黑(X,Y).

根據(jù)W不同取值而產(chǎn)生的所有一階邏輯程序被稱為“可能世界”(possible worlds)[80].在每個可能世界的內(nèi)部都可進(jìn)行正常的FOL推理.如此便可以計算PLP中任意原子公式A為真的概率：

(7)

式(7)表示原子公式A為真的概率等于所有蘊(yùn)涵A的可能世界的概率之和.以圖2為例，除去互斥事實后該領(lǐng)域的可能世界共有8個，其概率分布如表4所示.通過計算可知，“更好(瓜1,瓜2)”為真的概率是0.144+0.096+0.036+0.024=0.3.

Table 4 Possible Worlds of the PLP in Fig.2表4 PLP(圖2)的可能世界與概率分布

早期的PLP語法不允許FOL規(guī)則像式(5)那樣擁有自己的權(quán)重，實際上，使用概率事實(布爾隨機(jī)變量)加FOL規(guī)則的PLP的表達(dá)能力已經(jīng)足夠強(qiáng)大，能夠直觀地定義基于布爾隨機(jī)變量的貝葉斯網(wǎng)、馬爾可夫鏈和隱馬爾可夫模型等常見概率模型.

Dantsin[32]在提出PLP時便確定了“概率事實加FOL公式”的基礎(chǔ)語法規(guī)則，但由于其語法過于靈活，在PLP上進(jìn)行精確概率推斷比較困難.為此，Poole[33]對PLP語法進(jìn)行了簡化，并證明貝葉斯網(wǎng)是這種PLP的一個特例.Muggleton[37]提出的隨機(jī)邏輯程序(stochastic logic programs)在PLP中引入了遞歸規(guī)則，能夠通過采樣來進(jìn)行概率推斷.由于不斷遞歸產(chǎn)生的具體事實概率值呈指數(shù)級減小，因此SLP的概率推斷可以保證有界.隨后Poole[38]和Vennekens[40]在PLP中引入了帶權(quán)規(guī)則，進(jìn)一步擴(kuò)展了PLP的語法，使其有能力表達(dá)多值概率分布.

De Raedt等人提出的ProbLog[41]是現(xiàn)在應(yīng)用最廣泛的PLP系統(tǒng).它集成了許多成熟的PLP語法，并進(jìn)一步優(yōu)化了PLP概率推斷的效率.它通過將PLP編譯為二元決策圖(binary decision diagrams, BDD)[81]來將PLP的概率推斷轉(zhuǎn)化為一種可滿足性(SAT)問題，然后使用帶權(quán)模型計數(shù)(weighted model counting, WMC)來實現(xiàn)高效的PLP推理.最新的版本ProbLog2[82]將基于BDD的WMC改進(jìn)為基于d-DNNF(deterministic decomposable nega-tion normal form)[83]的WMC，進(jìn)一步提高了推理效率.

近年來，針對不同的應(yīng)用領(lǐng)域，研究者們依舊不斷地提出新的PLP系統(tǒng).例如與貝葉斯網(wǎng)相結(jié)合的CLP(BN)[39]、與ASP(answer set programming)相結(jié)合的P-Log[42]、與因果推斷相結(jié)合的CP-logic[43]、為信息檢索設(shè)計的PROPPR[55]等.它們大多仍使用分布語義對PLP進(jìn)行建模，僅在做概率推斷時有一定區(qū)別.有興趣的讀者可參閱相關(guān)文獻(xiàn)[46,84].

3.2.2 概率歸納邏輯程序

概率歸納邏輯程序(PILP)[46]是以PLP為模型的機(jī)器學(xué)習(xí)方法，其任務(wù)為找到滿足式(4)的假設(shè)模型H.為便于討論，令其中的H=(Γ;Θ)，這里的Γ表示假設(shè)模型中的FOL規(guī)則結(jié)構(gòu)，Θ代表所有概率規(guī)則和事實的參數(shù).在無歧義的情況下，可以省略式中的背景知識B，將式(4)重寫為

(8)

雖然PILP使用的數(shù)據(jù)形式上還是邏輯事實構(gòu)成的集合，但由于引入了概率分布，其本質(zhì)是關(guān)于隨機(jī)變量的采樣.因此PILP中的樣例一般被寫為D={E1=e1,E2=e2,…,EM=eM}，其中的Em表示第m次采樣的隨機(jī)變量(具體事實)集合，em表示本次采樣的結(jié)果，即Em中所有具體事實的賦值.為了能夠用D來對模型進(jìn)行估計，一般假設(shè)這些采樣結(jié)果服從獨(dú)立同分布.于是，式(8)中的后驗概率可以寫成：

(9)

PILP學(xué)習(xí)的目標(biāo)即為最大化似然函數(shù)L(Γ,Θ|D)=P(D|Γ,Θ).通常采用對數(shù)似然函數(shù)，那么PILP最終被形式化為

(10)

若Γ已知，則PILP退化為參數(shù)估計問題：

(11)

其中，PΓ是結(jié)構(gòu)為Γ的概率邏輯模型的分布函數(shù)，對基于分布語義的PLP，PΓ就是式(7)中的P.

當(dāng)Em為模型中所有隨機(jī)變量——即領(lǐng)域中全部具體事實時，PILP的參數(shù)學(xué)習(xí)問題可以直接使用極大似然估計[1]解決.例如Cussens[45]提出的FAM(failure-adjusted maximization)和ProbLog[41]使用的LFI-ProbLog[51]等.

然而在大部分應(yīng)用中，訓(xùn)練數(shù)據(jù)僅包含模型中一部分具體事實的賦值.這種情況相當(dāng)于參數(shù)估計時存在隱變量.記模型第i組樣例中的隱變量為Xi，則式(11)的目標(biāo)可以重寫為

(12)

當(dāng)Γ未知時，PILP需要同時學(xué)習(xí)規(guī)則結(jié)構(gòu)和模型參數(shù)，大部分算法選擇交替地對它們進(jìn)行學(xué)習(xí).

De Raedt等人[46]提出的PLP模型壓縮方法試圖通過貪心算法來逐條刪除PLP中的規(guī)則，并確保每次刪除規(guī)則后得到的PLP關(guān)于訓(xùn)練數(shù)據(jù)集的似然值最大.該方法雖能對PLP模型結(jié)構(gòu)進(jìn)行修改，但難以從數(shù)據(jù)中學(xué)習(xí)新規(guī)則.

Bellodi和Riguzzi[54]提出的SLIPCASE通過ILP的規(guī)則精化[18]來生成候選Γ，并采用EMBLEM[53]算法來學(xué)習(xí)模型參數(shù).Bellodi和Riguzzi[58]提出的SLIPCOVER算法則通過演化計算來改進(jìn)SLIPCASE中基于規(guī)則精化的結(jié)構(gòu)搜索，可有效地縮小搜索空間.

戴望州和周志華[56]提出的SUL(statistical unfolded learning)試圖將ILP中的命題化[68]方法擴(kuò)展至PILP.它首先將訓(xùn)練數(shù)據(jù)表示為一個超圖，然后通過關(guān)系型路徑查找[85]來構(gòu)建關(guān)系型特征并對數(shù)據(jù)集進(jìn)行命題化.接下來，SUL采用統(tǒng)計模型在命題化后的數(shù)據(jù)集上進(jìn)行學(xué)習(xí)，最終將模型轉(zhuǎn)化為概率邏輯規(guī)則集.與其他PILP方法相比，SUL能夠以較高的效率同時學(xué)習(xí)規(guī)則結(jié)構(gòu)與參數(shù).此外，SUL還實現(xiàn)了PILP中的謂詞發(fā)明.

3.3 可微構(gòu)件嵌入

在決策樹等模型中嵌入神經(jīng)網(wǎng)絡(luò)這樣的可微構(gòu)件早有研究[86].在ILP中嵌入可微構(gòu)件的策略目前有2種：1)使用線性運(yùn)算和神經(jīng)網(wǎng)絡(luò)來替代邏輯運(yùn)算，并對FOL系統(tǒng)中的真值進(jìn)行連續(xù)放松；2)將規(guī)則結(jié)構(gòu)搜索中的組合優(yōu)化轉(zhuǎn)換為參數(shù)空間中的連續(xù)優(yōu)化.與ILP和PILP相比，可微構(gòu)件的嵌入進(jìn)一步提升了學(xué)習(xí)效率，并允許模型擁有更大的數(shù)據(jù)吞吐量.

Rockt?schel與Riedel[65]提出的neural theorem prover(NTP)方法采用了第1種策略.它保留了邏輯程序中的后向鏈(backward chaining)推理，并使用神經(jīng)網(wǎng)絡(luò)來代替推理中用到合一等運(yùn)算.后向鏈?zhǔn)沁壿嫵绦蛑幸环N對原子公式進(jìn)行證明的方式，MIL[50]的元解釋器便借鑒了其思想.對于一條FOL規(guī)則a(X,Y)←b(X,Y)∧c(X,Y)，當(dāng)用戶查詢目標(biāo)概念具體事實a(1,2)的賦值時，它會首先被用來與規(guī)則頭a(1,2)進(jìn)行合一，得到變量替換θ={X=1,Y=2}；再將規(guī)則體中的原子經(jīng)過θ替換可得b(1,2)∧c(1,2).后向鏈遞歸地證明這2個原子，若它們均為true，那么對該規(guī)則的證明成功，得到a(1,2)的賦值為true.

NTP將證明過程中使用的合一運(yùn)算轉(zhuǎn)變?yōu)樯窠?jīng)網(wǎng)絡(luò)unifyσ(A,B,S)=S′，其中A與B為待合一的2個原子，每個原子p(e1,e2,…,em)被表示為一個k(m+1)維向量(σ(p),σ(e1),…,σ(em))，其中σ(X)表示符號X的嵌入形式，k是其長度；S與S′分別為合一之前與之后的證明狀態(tài)，它包含一個集合Sφ和一個標(biāo)量Sψ∈[0,1].前者用于存儲目前為止所有使用過的變量替換θ，后者代表目前狀態(tài)下合一成功的可能性.σ為NTP網(wǎng)絡(luò)的所有參數(shù)，它包含所有邏輯符號(謂詞及常量)的嵌入以及所有unifyσ(A,B,S)網(wǎng)絡(luò)的參數(shù).A與B的合一可能涉及到多種情況，NTP分別對它們進(jìn)行了定義.例如若A=e1和B=e2均為邏輯常量時，則unifyσ會直接輸出其嵌入的相似度；若A是變量時，則B被直接賦值為σ(A).

Evans和Grefenstette[66]提出的?ILP則主要采用了第2種策略.它首先將所有可能的候選假設(shè)模型提前構(gòu)建出來；然后為每個候選模型設(shè)置一個權(quán)重；最終根據(jù)訓(xùn)練樣例對權(quán)重進(jìn)行優(yōu)化，篩選出權(quán)重最高的模型作為輸出.

為了限制候選模型的數(shù)量，?ILP規(guī)定對每個目標(biāo)概念p只能學(xué)習(xí)一個由2條FOL規(guī)則組成的假設(shè)模型，其中每條FOL規(guī)則都依照一條SOL元規(guī)則[50]為模板而生成.它將式(2)中的ILP學(xué)習(xí)目標(biāo)改寫為優(yōu)化問題：

(13)

為了求解該目標(biāo)，?ILP也采用策略1將FOL中的賦值放松為[0,1]區(qū)間內(nèi)的連續(xù)值，并定義關(guān)于Θp的負(fù)對數(shù)似然函數(shù)：

其中e和y分別為訓(xùn)練樣例及其標(biāo)記；P(e|Θp,Π,B,T)表示當(dāng)(Θp,Π,B)確定時，經(jīng)過T步演繹后e賦值為true的可能性.

為了優(yōu)化該目標(biāo)函數(shù)，?ILP需要將p(e|Θp,Π,B,T)中的FOL演算轉(zhuǎn)化為連續(xù)可微的函數(shù)運(yùn)算.它將候選假設(shè)模型中的每條FOL公式R轉(zhuǎn)化為一個可微函數(shù)FR:[0,1]n|→[0,1]n，這里的n為領(lǐng)域中所有具體事實的個數(shù)，因此FR的定義域和值域均為領(lǐng)域中全體具體事實的賦值.

x[a]=max(Fj(a[i]),Fk(a[i])).

?ILP雖然是一種可微分模型，但它幾乎完全保留了FOL規(guī)則的形式.與PLP的分布語義類似，它的FOL語義直接建立在領(lǐng)域中全體具體邏輯事實的賦值上.在許多不帶噪聲的ILP任務(wù)中，?ILP的學(xué)習(xí)效果甚至可以與MIL[50]相媲美；而當(dāng)數(shù)據(jù)中存在噪聲時，它依然能夠?qū)W到有效的FOL規(guī)則.其局限在于假設(shè)模型的形式不夠靈活.當(dāng)目標(biāo)概念難以僅用2條規(guī)則描述時，用戶必須將其分解為2個甚至更多待學(xué)習(xí)謂詞，并為它們一一設(shè)定元規(guī)則作為模板.此外，?ILP在進(jìn)行參數(shù)學(xué)習(xí)之前必須枚舉所有的候選模型，并將其全部用于FOL推理.事實上，絕大部分候選模型可能是無效、甚至矛盾的，因此?ILP可能將大量計算資源浪費(fèi)在無效模型的推斷中.

一方面，嵌入可微構(gòu)件的ILP能夠有效地利用GPU等并行計算設(shè)備，在一些僅需簡單邏輯推理的關(guān)系型學(xué)習(xí)任務(wù)中實現(xiàn)高效學(xué)習(xí)；但另一方面，它們加入了大量約束來對ILP模型的形式進(jìn)行簡化，無法保證待學(xué)習(xí)的目標(biāo)概念仍然存在于假設(shè)空間中.

4 應(yīng) 用

ILP在早期一般被應(yīng)用于生物、化學(xué)和制藥等領(lǐng)域.Golem曾被應(yīng)用到蛋白質(zhì)結(jié)構(gòu)預(yù)測[27]任務(wù)中，并取得了比神經(jīng)網(wǎng)絡(luò)更好的效果；Progol被應(yīng)用于生物醫(yī)藥研究上，并輔助科學(xué)家們發(fā)現(xiàn)了重要的生物誘變劑[29]；基于誘導(dǎo)推理的ILP則被用于學(xué)習(xí)生物的新陳代謝規(guī)律[88].

除了經(jīng)典ILP系統(tǒng)之外，PILP也在許多任務(wù)中得到應(yīng)用.例如，自然語言是一種結(jié)構(gòu)性強(qiáng)但形式很靈活的數(shù)據(jù).PILP既可以有效地引入語法等背景知識，又能從概率上對其不確定性進(jìn)行建模，因此已被應(yīng)用于自然語言處理[60].

ILP也影響了其他機(jī)器學(xué)習(xí)領(lǐng)域的研究.例如在統(tǒng)計關(guān)系學(xué)習(xí)(statistical relational learning， SRL)[89]中，ILP常被用于對SRL模型結(jié)構(gòu)進(jìn)行初始化[90].而在概率圖模型中，ProbLog可以作為一種效率非常高的概率推斷引擎來對圖模型上的推理和學(xué)習(xí)進(jìn)行加速[41].

得益于FOL語言強(qiáng)大的表達(dá)能力，ILP能用于輔助科學(xué)發(fā)現(xiàn).例如生態(tài)學(xué)中的一個重要問題是從生物數(shù)量的變化判斷物種之間的捕食關(guān)系.因為收集到的數(shù)據(jù)量十分龐大，若由科學(xué)家來對它們一一進(jìn)行檢驗則需要消耗很長時間.并且物種間的捕食關(guān)系可能十分復(fù)雜，一個物種的數(shù)量往往受十幾種其他物種的影響.生態(tài)學(xué)家們擁有大量復(fù)雜的領(lǐng)域知識，能通過FOL語言進(jìn)行表達(dá).Bohan等人[91]將MIL應(yīng)用于該問題，不僅實現(xiàn)了數(shù)據(jù)驅(qū)動的食物網(wǎng)自動構(gòu)建，還通過MIL自動發(fā)明的謂詞，輔助科學(xué)家們發(fā)現(xiàn)了許多新的現(xiàn)象.

由于ILP學(xué)得的模型具有良好的解釋性，用戶可以更好地加以利用.例如Progol曾被應(yīng)用于一個叫“機(jī)器人科學(xué)家”(robot scientist)的項目中.每當(dāng)ILP從實驗數(shù)據(jù)中學(xué)得一個模型，生物學(xué)家們便對它發(fā)現(xiàn)的FOL規(guī)則進(jìn)行深入分析，然后根據(jù)這些分析結(jié)果來設(shè)計新的實驗.這種模式將人類的科學(xué)發(fā)現(xiàn)與機(jī)器學(xué)習(xí)組成一個閉環(huán)：人類知識被用于設(shè)計科學(xué)實驗；實驗結(jié)果最終成為機(jī)器學(xué)習(xí)的數(shù)據(jù)來源；從數(shù)據(jù)中學(xué)得的模型最終被用于更新人類的知識并設(shè)計下一步實驗.該計劃運(yùn)用這種模式成功發(fā)現(xiàn)了帶有重要功能的基因片段[30-31].

上述應(yīng)用中所使用的均為關(guān)系型數(shù)據(jù).而Muggleton等人[92-93]提出的Logical Vision則試圖將ILP直接應(yīng)用于像素表示的圖像數(shù)據(jù)以進(jìn)行視覺概念學(xué)習(xí).該方法用其他學(xué)習(xí)模型來探測圖像中分隔主物件與背景的“邊界點(diǎn)”，同時結(jié)合FOL表達(dá)的幾何概念作為背景知識，通過ILP學(xué)習(xí)更復(fù)雜的視覺概念.Logical Vision采用了認(rèn)知科學(xué)中的“假設(shè)-檢驗”模型，試圖在符號表示的抽象概念學(xué)習(xí)與原始數(shù)據(jù)感知之間架起橋梁.借助領(lǐng)域知識，Logical Vision甚至可以學(xué)會預(yù)測未出現(xiàn)在圖像中的物體[92].例如，基于簡單的光學(xué)常識，該方法僅從一幅圖片中即可學(xué)會判斷圖像外光源的位置.更有趣的是，得益于FOL強(qiáng)大的表達(dá)能力，Logical Vision在光源學(xué)習(xí)任務(wù)中得到的FOL規(guī)則還能夠從圖像中解讀出關(guān)于反射面凹凸形狀的歧義，并通過對不同光源位置進(jìn)行假設(shè)來解釋這種歧義.這在目前其他形式的機(jī)器學(xué)習(xí)中很難實現(xiàn).

5 討論與展望

與其他類型的機(jī)器學(xué)習(xí)技術(shù)相比，ILP有其自身的優(yōu)勢.

1) 使用FOL作為表達(dá)語言的ILP擁有強(qiáng)大的表達(dá)能力和推理能力，便于對復(fù)雜結(jié)構(gòu)的領(lǐng)域知識進(jìn)行處理和利用.

2) FOL規(guī)則有良好的可理解性.每條FOL規(guī)則均遵循“若X成立，則Y成立”這樣的簡單模式，且其中的謂詞、函數(shù)符號大多取自于背景知識中的原始概念，所以學(xué)得的模型有良好的語義.

3) FOL規(guī)則有著良好的可重用性.由于背景知識和假設(shè)模型均為FOL規(guī)則集，ILP學(xué)得的模型可以作為背景知識被直接應(yīng)用在其他ILP任務(wù)中.例如，戴望州等人[93]提出的Logical Vision便將學(xué)習(xí)“三角形”概念所得到的FOL規(guī)則集作為背景知識重用于“直角三角形”的概念學(xué)習(xí)任務(wù)中.依照這種模式，ILP可以實現(xiàn)從簡單到復(fù)雜任務(wù)的分階段學(xué)習(xí)[94]，并不斷將學(xué)得的模型進(jìn)行重用，這為實現(xiàn)“學(xué)件”[95]等構(gòu)想提供了便利.

但另一方面，ILP技術(shù)本身還存在很多局限，很多問題有待解決.

1) 由于FOL規(guī)則的形式和結(jié)構(gòu)是離散的，其假設(shè)空間十分復(fù)雜.為了提高學(xué)習(xí)效率，PILP與可微構(gòu)件的嵌入在一定程度上對FOL模型的語義和語法做出了放松.但是，對FOL語義的放松導(dǎo)致難以區(qū)別錯誤規(guī)則和領(lǐng)域噪聲造成的規(guī)則沖突，甚至無法保證放松后的假設(shè)空間仍包含目標(biāo)概念.此外，機(jī)器學(xué)習(xí)任務(wù)不僅面臨著日益增長的數(shù)據(jù)量，還面臨著越來越龐大的領(lǐng)域知識.例如，WordNet[96]作為自然語言處理中最常用的領(lǐng)域知識庫之一，它擁有的詞匯量與二元具體事實的數(shù)量已分別超過150 000條與200 000個.現(xiàn)有的ILP方法很難對如此龐大的背景知識加以利用.

2) 目前的ILP不能進(jìn)行非單調(diào)學(xué)習(xí).只能不斷地學(xué)習(xí)與背景知識不發(fā)生沖突的新規(guī)則.這使得它們十分依賴于背景知識的正確性，然而現(xiàn)實機(jī)器學(xué)習(xí)任務(wù)中往往很難確保背景知識的正確性.

3) 幾乎所有的ILP方法都只能從邏輯符號表示的數(shù)據(jù)中進(jìn)行學(xué)習(xí)[97].但現(xiàn)實機(jī)器學(xué)習(xí)任務(wù)中往往涉及到很多非符號類型數(shù)據(jù)，例如像素構(gòu)成的圖像、波形組成的音頻等.此外，ILP任務(wù)中的原始概念及具體事實通常需由領(lǐng)域?qū)＜覐脑紨?shù)據(jù)中標(biāo)注而來，這往往需要消耗大量成本.

對上述問題目前已經(jīng)有一些探索.例如，在工程上可以嘗試采用分布式計算來提高ILP的搜索效率[98].而在理論上，限制ILP效率的瓶頸主要在于FOL對模型完備性和一致性的要求.對這2個要求該如何放松，放松至何種程度，放松的過程中如何保證學(xué)習(xí)的效率，均是值得解決的問題.

對非單調(diào)學(xué)習(xí)問題，一種可行的方式是為ILP引入非單調(diào)推理模型，例如信念修正中的AGM模型[99]等.對于PILP來說，該問題則更加復(fù)雜，由于它允許數(shù)據(jù)集中出現(xiàn)噪聲，學(xué)習(xí)系統(tǒng)還必須能夠區(qū)分由數(shù)據(jù)噪聲和錯誤規(guī)則導(dǎo)致的沖突.

對如何從原始數(shù)據(jù)中自動抽取符號表示，在ILP中嵌入可微構(gòu)件是一種探索，例如Evans和Grefenstette[66]提出的?ILP即可接入預(yù)訓(xùn)練的卷積神經(jīng)網(wǎng)絡(luò)，從手寫數(shù)字圖像中學(xué)習(xí)大小與關(guān)系.戴望州等人[100]提出的誘導(dǎo)學(xué)習(xí)(abductive learning)則將FOL誘導(dǎo)推理與深度學(xué)習(xí)相結(jié)合，實現(xiàn)了邏輯模型和深度學(xué)習(xí)模型的同時訓(xùn)練.其他機(jī)制尚有待探索.

此外，ILP良好的可理解性或可對其他形式的機(jī)器學(xué)習(xí)方法產(chǎn)生一定啟發(fā).目前在該方向中的探索可大致分為2類:1)將ILP作為獨(dú)立的部件與其他機(jī)器學(xué)習(xí)方法相結(jié)合；2)將ILP所使用的FOL演算嵌入機(jī)器學(xué)習(xí)過程.例如，戴望州和周志華[101]采用第1種策略，試圖通過誘導(dǎo)推理來約束統(tǒng)計機(jī)器學(xué)習(xí).Socher等人[102]提出的NTN(neural tensor network)以及Cohen[103]提出的TensorLog則采用第2種策略，將FOL演算表示為張量運(yùn)算嵌入深度神經(jīng)網(wǎng)絡(luò).第1種策略有助于保持FOL的表達(dá)能力，但是將FOL演算與機(jī)器學(xué)習(xí)分離為2個相對獨(dú)立的過程；第2種策略便于引入“端到端學(xué)習(xí)”，但是一定程度上損失了FOL的表達(dá)能力.

總的來看，作為一個已經(jīng)發(fā)展了30年的機(jī)器學(xué)習(xí)分支方向，ILP已經(jīng)取得了很多的進(jìn)展和成果.尤其在人們對機(jī)器學(xué)習(xí)的可理解性愈來愈關(guān)注的今天，ILP的研究可能值得更多研究者關(guān)注和參與.