馬爾科夫邏輯網(wǎng)譯文

1、馬爾科夫邏輯網(wǎng)（譯文）馬修 理查德森() 和佩德羅 多明戈斯 ()美國西雅圖華盛頓大學計算機科學工程系WA 98195-250 摘要：我們提出一個簡單的方法將一階邏輯和概率圖解模型組合成一種表示形式。馬爾科夫邏輯網(wǎng)就是一個每個準則或語句都有權(quán)重的一階邏輯知識庫，其中常數(shù)代表庫中對象，還約定了一個基本馬爾科夫網(wǎng)知識庫中一個一階邏輯準則的每個可能的基元都帶有相應的權(quán)重。馬爾科夫邏輯網(wǎng)推理是通過在回答問題所需的最小基元子集上運用馬爾科夫鏈蒙特卡羅方法實現(xiàn)的。權(quán)重是從關(guān)系數(shù)據(jù)庫通過擬似然度量的優(yōu)化迭代高

2、效學習獲得，可選擇地，額外的子句可運用歸納邏輯程序技術(shù)學得。使用一所大學內(nèi)的一個真實世界數(shù)據(jù)庫和知識庫的實驗表明這種方法大有前途。關(guān)鍵詞：統(tǒng)計關(guān)聯(lián)學習，馬爾科夫網(wǎng)，馬爾科夫隨機場，對數(shù)線性模型，圖模型，一階邏輯，可滿足性， 歸納邏輯程序設(shè)計，基于知識的模式構(gòu)建，馬爾科夫鏈蒙特卡羅方法，擬似然，連接預測介紹    將概率和一階邏輯一起表達一直是人工智能界的目標。概率圖模型使我們能有效地應對不確定性，一階邏輯讓我們能簡潔地表達廣博的知識，而往往許多應用中兩者都需要。近年來，這個問題由于和統(tǒng)計關(guān)系學習 (Getoor & Jensen, 2000; Getoor

3、 & Jensen, 2003; Dietterich等, 2003), 或者多關(guān)系數(shù)據(jù)挖掘(Dzeroski & De Raedt, 2003; Dzeroski等, 2002; Dzeroski等, 2003; Dzeroski & Blockeel, 2004)的相關(guān)性引起了廣泛興趣。當前的提議一般都集中在將概率和一階邏輯的有限子集組合在一起，如霍恩子句(e.g., Wellman等 (1992); Poole (1993); Muggleton (1996); Ngo and Haddawy (1997); Sato and Kameya (1997); Cus

4、sens (1999); Kersting and De Raedt (2001); Santos Costa 等(2003)，基于框架的系統(tǒng)(e.g., Friedman等 (1999); Pasula and Russell (2001); Cumby and Roth (2003)，或者數(shù)據(jù)查詢語言(e.g., Taskar等(2002); Popescul and Ungar (2003)，它們都很復雜。在本論文中，我們介紹了馬爾科夫邏輯網(wǎng)，這是一個除了有窮集要求外沒有其它限制的能將概率和一階邏輯結(jié)合的非常簡單的表示辦法。我們?yōu)轳R爾科夫邏輯網(wǎng)的學習和推理開發(fā)了高效的算法，并在某個現(xiàn)實世

5、界場景中進行了評估。    一個馬爾科夫邏輯網(wǎng)就是一個每個準則都有權(quán)重的一階邏輯知識庫，可看成是構(gòu)建馬爾科夫邏輯網(wǎng)絡(luò)的模板。從概率的視角看，馬爾科夫邏輯網(wǎng)提供一種簡潔的語言來定義大型馬爾科夫網(wǎng)，能靈活地、模塊化地與大量知識合并；從一階邏輯的視角看，馬爾科夫邏輯網(wǎng)能健全地處理不確定性、容許有瑕疵甚至矛盾的知識庫，降低脆弱性。有許多統(tǒng)計關(guān)系學習領(lǐng)域的重要任務，如集合分類、鏈接預測、鏈接聚合、社會網(wǎng)絡(luò)建模和對象識別，都自然而然地成為運用馬爾科夫邏輯網(wǎng)推理和學習的實例。    現(xiàn)實世界數(shù)據(jù)庫和知識庫的試驗顯現(xiàn)了馬爾卡夫邏輯網(wǎng)相對于純邏輯方法或

6、純概率方法的優(yōu)勢。本論文的開頭簡要介紹馬爾科夫網(wǎng)（第二章）和一階邏輯（第三章）的基礎(chǔ)，核心部分介紹了馬爾科夫邏輯網(wǎng)及其推理和學習的算法（第四-六章），接下來是試驗結(jié)果的報告（第七章），最后，我們介紹了怎樣利用馬爾科夫邏輯網(wǎng)來完成各種統(tǒng)計關(guān)聯(lián)學習任務（第八章），還討論了馬爾科夫邏輯網(wǎng)與以前一些方法的關(guān)系（第九章），最后列出了一些下一步工作的方向（第十章）。馬爾科夫網(wǎng)絡(luò)    馬爾科夫網(wǎng)（也叫馬爾科夫隨機場）是隨機變量集x=x1,x2,xn的聯(lián)合分布模型(Pearl, 1988)，它由一個無向圖G和一個勢函數(shù)k集合組成，每個隨機變量是圖上的節(jié)點，圖的每個團在模型中都有

7、一個勢函數(shù)，勢函數(shù)是一個非負實函數(shù)，它代表了相應的團的狀態(tài)。馬爾科夫網(wǎng)的聯(lián)合分布如下（1）其中xk是團中隨機變量的狀態(tài)，Z也叫配分函數(shù)（態(tài)和），定義為 。將馬爾科夫網(wǎng)絡(luò)中每個團的勢用狀態(tài)的所有特征值加權(quán)后求和再取冪，就可方便地表示成對數(shù)線性模式  （2）特征函數(shù)可以是表示狀態(tài)的任何實函數(shù)，本論文將只討論二元特征值。公式一是勢最直接的表示，其中每個團每個可能的狀態(tài)都有一個對應的特征值 fj(x)，它的權(quán)重是wj，這種表示方法與團數(shù)量的冪相關(guān)。可是，我們可以自由地運用一些方法比如狀態(tài)的邏輯函數(shù)等減少特征值數(shù)量，特別在團數(shù)量很大時能相比勢函數(shù)方式提供一種更簡潔的表示形式。馬爾可夫邏輯網(wǎng)絡(luò)就

8、是利用了這一方式。    馬爾可夫網(wǎng)的推理是NP完備問題(Roth, 1996)。最被廣泛使用的近似推理方法是馬爾可夫鏈蒙特卡羅法（MCMC）(Gilks等, 1996)，特別是吉布斯采樣法，它依次對每個隨機變量在它們各自的馬爾可夫毛毯中進行采樣處理（一個節(jié)點的馬爾可夫毛毯是一個節(jié)點能與剩余網(wǎng)絡(luò)互相獨立的最小節(jié)點集合，簡單地說在一個馬爾可夫網(wǎng)中，就是節(jié)點在圖中的鄰居）。邊緣概率可通過對采樣值的計數(shù)得到，而條件概率可將作為條件的隨機變量值設(shè)定后運用吉布斯采樣得到。另外一種流行的馬爾可夫網(wǎng)推理方法是置信傳播法(Yedidia等，2001)。  &#

9、160; 求馬爾可夫網(wǎng)權(quán)重的最大概似法或者最大后驗概率法都不是封閉解，但是由于對數(shù)概似函數(shù)是權(quán)重的凹函數(shù)，可運用標準積分或優(yōu)化的擬牛頓法高效求解 (Nocedal & Wright, 1999)。另一種選擇是迭代法(Della Pietra等, 1997)。特征值可從數(shù)據(jù)中學得，比如通過貪婪地構(gòu)建原子特征合取式(Della Pietra等，1997)。一階邏輯    一個一階知識庫是一個由一階邏輯句子或規(guī)則組成的集合。組成規(guī)則的有四種類型的符號：常數(shù)、變量、函數(shù)和謂語，常數(shù)符號代表所涉及領(lǐng)域的對象（例如,人:安娜,鮑勃,克里斯,等等），變量符號可在涉及領(lǐng)域

10、的對象范圍內(nèi)變化，函數(shù)符號（例如，MotherOf）表示了對象組之間的映射關(guān)系，謂語符號代表了對象間的關(guān)系（如，F(xiàn)riends）或者對象的屬性（如，Smokes），還需要說明哪些符號代表了域中的哪些對象、函數(shù)和關(guān)系。變量和常數(shù)可以有類型，那樣的話常數(shù)只能代表同類型的對象，變量只能在同類型的對象范圍中取值，例如，變量x可以代表人（如，安娜，鮑勃等），常數(shù)C可以表示一個城市（如，西雅圖）。    一個詞是代表域中對象的任意表達式，它可以是常數(shù)，變量或應用到一組詞上的函數(shù)，比如，安娜、X、GreatestCommonDivisor（x，y）都是詞。一個原子規(guī)則或原子是應

11、用到一組詞上的謂語（Friends（x，MotherOf(Anna)）。而規(guī)則是使用數(shù)量詞和邏輯連接符從原子規(guī)則遞歸構(gòu)建的。如果F1和F2是規(guī)則，那么下列的也是規(guī)則： ¬ F1（否定），當且僅當F1為假時取真值； F1 F2（合?。?，當且僅當F1和F2都為真時取真值； F1 F2 （析?。?，當且僅當F1或F2為真時取真值； F1 F2 （蘊涵），當且僅當F1為假或F2為真時取真值；F1 F2（等價） ，當且僅當F1和F2取值一樣時取真值； x F1（全稱量詞），當且僅當F1對域中每個對象X為真時取真值； x F1（存在量詞），當且僅當F1對域中至少一個對象X為真時取真值。圓括號可用來

12、確保優(yōu)先級。知識庫中的規(guī)則之間隱含合取關(guān)系，因此可以說一個知識庫就是一條巨大的規(guī)則。一個基詞是一個不含變量的詞，一個基本原子或基本謂語是一個參數(shù)都是基詞的原子規(guī)則。一個可能世界或者海爾勃朗解釋為每個可能的基詞賦真值。    一個規(guī)則如果是可滿足的，那么當且僅當至少在一個世界中是真的。一階邏輯中基本的推理問題一般是確定一個知識庫KB是否包含某個規(guī)則F，也就是在KB所有真的世界里F也真。這個常常用反證法證明：KB包含F(xiàn)當且僅當KB包含¬F無法滿足。（于是，如果一個知識庫含有矛盾，所有的規(guī)則也就矛盾了，因此，知識庫需要非常盡心維護）。為了方便自動推理，規(guī)則常常

13、被轉(zhuǎn)換成一種正則形式，一種句子形式（也叫做合取范式（CNF）。一個范式的知識庫是由一些合取的句子組成，而每個句子又由析取的文字組成。每個一階邏輯的知識庫都可通過機械的步驟轉(zhuǎn)換成范式。在一階邏輯中范式用于問題求解，這是一個健全的、無法反駁的推理方法。    基于一階邏輯的推理僅是半可解的，因此，知識庫往往使用一階邏輯的有更多特性的限定子集來表示。霍恩子句是一種最被廣泛使用的子集，它的句子只允許最多一個肯定的文字。Prolog程序語言就是基于霍恩子句邏輯（Lloyd, 1987），Prolog程序可以從庫中搜索含有近似數(shù)據(jù)的霍恩子句，這在歸納邏輯程序研究過（Lavra

14、c & Dzeroski, 1994）。    表是一個簡單的知識庫和它的范式轉(zhuǎn)換形式。請注意，這些規(guī)則在現(xiàn)實世界中通常是真的，但不總是真的。在大多數(shù)場景一些重要的規(guī)則往往很難表達為一直為真，這些規(guī)則僅捕捉到了相關(guān)知識的一部分。盡管善于表達，但是純粹的一階邏輯在人工智能實踐中應用能力有限。許多特別的擴展辦法被提出來解決這個問題，這個問題在更有限的命題邏輯范圍內(nèi)已被概率圖模型很好地解決了。下一節(jié)將介紹將這些模型推廣到一階邏輯的辦法。表是一階邏輯知識庫和馬爾可夫邏輯網(wǎng)的例子，F(xiàn)r、Sm、Ca分別是Friends、Smokes和Cancer的縮寫 英文一階邏輯范

15、式權(quán)重Friends of friends are friends. x y zFr(x,y)Fr(y,z)Fr(x,z)¬Fr(x,y)¬Fr(y,z)Fr(x,z)0.7Friendless people smoke. x(¬(yFr(x,y)Sm(x)Sm(x)Fr(x,g(x)2.3Smoking causes cancer. xSm(x)Ca(x)¬Sm(x)Ca(x)1.5If two people are friends,either both smoke or neither does. x yFr(x,y)(Sm(x)Sm(y)

16、2;Fr(x,y)Sm(x)¬Sm(y)¬Fr(x,y)¬Sm(x)Sm(y)1.11.1馬爾科夫邏輯網(wǎng)    一個一階邏輯知識庫可以看作是在一系列可能的世界上加上了一套硬約束：哪怕只與一條規(guī)則沖突也不行。馬爾科夫邏輯網(wǎng)的基本想法就是要軟化這些約束：一個可能世界如果與知識庫規(guī)則沖突，不會不可能存在，而是可能性下降，沖突的規(guī)則數(shù)越少，可能性越大。每個規(guī)則都和一個反映其約束強度的權(quán)重關(guān)聯(lián)：在其它情況一樣的前提下，權(quán)重越高的，滿足和不滿足此規(guī)則的事件的對數(shù)概率差就越大。定義4.1  馬爾科夫邏輯網(wǎng)L是（Fi，wi）對的集合，其中

17、Fi代表一階邏輯規(guī)則， wi是一個實數(shù)；有限的常數(shù)集為C = c1,c2,，馬爾科夫網(wǎng)ML,C如下1、2來定義：1、L中每個謂詞的每個可能基元在ML,C中有一個二元節(jié)點，如果原子公式為真，節(jié)點的值就等于1，否則為0。2、L中每個規(guī)則的每個基本可能在ML,C中有一個特征值，當這個規(guī)則為真時等于1，否則等于0，特征值的權(quán)重為 Fi 對應的wi。馬爾科夫網(wǎng)MLN中規(guī)則的語法是一階邏輯的標準語法(Genesereth & Nilsson, 1987)，自由（未限定）變量被認為是規(guī)則最外層的全稱變量。    這個定義可以看作構(gòu)建馬爾科夫網(wǎng)絡(luò)的模板。如果常數(shù)集不同，它

18、會產(chǎn)生大小不同的網(wǎng)絡(luò)，但是所有關(guān)于結(jié)構(gòu)和參數(shù)的規(guī)則都是確定的（比如一個規(guī)則的所有可能都有相同的權(quán)重）。我們把它稱作基本馬爾科夫網(wǎng)，以示與一階邏輯MLN的區(qū)別。從定義4.1、等式1和2可以得出，基本馬爾科夫邏輯網(wǎng)概率分布如下  （3）ni(x)是Fi在X中所有取真值的基本規(guī)則的數(shù)量，而xi是Fi中為真的原子，又有i(xi)=ewi。請注意，雖然我們將馬爾科夫邏輯網(wǎng)定義成對數(shù)線性模式，它們還可以定義成勢函數(shù)積的樣子，就如上面第二個等式。當硬約束和軟約束并存時，這是最簡便的方法（比如，當一些規(guī)則很確定時，不滿足將導致事件不可能）。    按照定義4.1構(gòu)建的M

19、L,C的圖結(jié)構(gòu)是這樣的：當且僅當兩個節(jié)點相應的基本原子同時出現(xiàn)在L中的一個規(guī)則的至少一個基本形式時，這兩個節(jié)點之間就有一條邊。這樣，ML,C的每個基本公式中的原子構(gòu)成一個（未必最大的）集團。    圖1展示了一個基本的馬爾科夫網(wǎng)，它是由表1的最后兩個規(guī)則和常數(shù)Anna和Bob定義的。圖中的每個節(jié)點都是基本原子（比如，F(xiàn)riends(Anna，Bob)）。當一對原子同時出現(xiàn)在某個基本規(guī)則時，它們之間就有一條弧。這個ML,C可以用來推測當知道Anna和Bob的吸煙習慣時他們朋友的可能性，或者當他們是朋友同時Anna有癌癥時Bob得癌癥的概率，等等。 

20、60;   ML,C的每個狀態(tài)代表了一個可能的世界，一個可能的世界就是一個對象集合、一個函數(shù)集合（映射對象組）和一組對象之間的關(guān)系；它們一起來確定每個基本原子都取真值。下面的幾個假設(shè)保證了代表（L,C）的可能世界集是個有限集，又很好的獨特定義了這些可能世界的概率分布，同時還與所涉領(lǐng)域和表達形式無關(guān)。這些假設(shè)在絕大多數(shù)實踐應用中是合理的，大大簡化了馬爾科夫邏輯網(wǎng)的應用難度。有賴于此，我們可以輕松地討論后面的幾個例子。假設(shè)1：命名唯一性。不同的常數(shù)代表不同的對象（Genesereth & Nilsson，1987）。假設(shè)2：范圍封閉性。只存在能用（L，C）中常數(shù)和函數(shù)符

21、號表示的對象（Genesereth & Nilsson，1987）。假設(shè)3：函數(shù)確定性。L中每個函數(shù)每個可能的值都確定在常數(shù)集C中。    最后這個假設(shè)可以讓我們在基本化規(guī)則時將函數(shù)替換成它們的值，就只需考慮以常數(shù)作為參數(shù)的基本原子，這樣就可以忽略（L,C）中所有的函數(shù)和常數(shù)（海爾勃朗全域）構(gòu)建無限原子集的情況，因為每個詞都是C中確定的常數(shù)，包含它們的原子也就表示為包含對應的常數(shù)。 按定義4.1每個謂詞的可能基形可以這樣簡單得到，將變量用C中常數(shù)替換，將函數(shù)也用相應的常數(shù)替換。表是在假設(shè)1、2、3基礎(chǔ)上求基本原子規(guī)則的步驟。如果一個規(guī)則多于一條子句，那么它

22、的權(quán)重在各個子句上平分；而一個句子的權(quán)重會被賦予它的每個基本形式。表II 基本原子的構(gòu)建 function Ground(F, C)inputs: F, a formula in first-order logic           C, a set of constantsoutput: GF , a set of ground formulascalls: CNF(F,C), which converts F to conjunctive normal form, replacing ex

23、istentially quantified formulas by disjunctions of their groundings over CF CNF(F, C)GF = for each clause Fj F    Gj = Fj    for each variable x in Fj        for each clause Fk(x) Gj         

24、;   Gj (Gj Fk(x) Fk(c1), Fk(c2),. Fk(cj)g ，where Fk(ci) is Fk(x) with x replaced by ci C    GF GF Gjfor each ground clause Fj GF    repeat        for each function f(a1,a2,.) all of whose arguments are constants  &#

25、160;         Fj Fj with f(a1,a2,.) replaced by c, where c = f(a1,a2,.)    until Fj contains no functionsreturn GF    假設(shè)1（命名唯一性）可以去掉，如果引入等于謂詞（Equals(x,y)或x=y）并將等于的自反、對稱和傳遞性，以及對于任意二元謂詞P，其余高階的謂詞和函數(shù)也一樣，這些公理加入馬爾科夫邏輯網(wǎng)的話（Genesereth &

26、 Nilsson，1987）。每對常數(shù)在最終形成的馬爾科夫邏輯網(wǎng)中都有一個節(jié)點，1代表這對常數(shù)是同一對象，否則為0；這些節(jié)點之間以及和網(wǎng)絡(luò)的其它部分的連接弧代表了上述的公理。這讓我們有能力對兩個常數(shù)的等同性進行概率推理，并成功地以此法為基礎(chǔ)進行了對象識別（請參閱8.5節(jié)）。    如果知道未知對象的數(shù)量u，我們可以簡單地引入u個任意新常數(shù)，這樣假設(shè)2（范圍封閉性）就可以去掉了。如果u不確定但是有限的，假設(shè)2也可以不用，辦法是引入u的概率分布，用每個未知對象的數(shù)量對馬爾科夫邏輯網(wǎng)基本化，規(guī)則F的概率可計算為，MuL，C是有u個未知對象的基本馬爾科夫邏輯網(wǎng)。而u如果無

27、限的話，就需要將馬爾科夫邏輯網(wǎng)擴展至無限常數(shù)集條件下。    讓HL,C代表由L中的符號、（L，C海爾勃朗全域）中的常數(shù)構(gòu)建的所有基詞。如果將HL,C的每個對象看作常數(shù)，采取去掉假設(shè)1相同的步驟的話，假設(shè)3也可以去掉。例如，函數(shù)G(x)、常數(shù)A和B，這個馬爾科夫邏輯網(wǎng)將有節(jié)點G(A)=A、G(B)=B等。這有可能引入無限多的新常數(shù)，需要相應擴展馬爾科夫邏輯網(wǎng)。但無論如何，如果我們限定最大嵌套層數(shù)的話，得到的馬爾科夫邏輯網(wǎng)還是有限的。    總之，只要范圍是有限的，那么假設(shè)1-3都可以不要。我們相信馬爾科夫邏輯網(wǎng)能擴展到無限領(lǐng)域（Jae

28、ger（1998），不過那主要是理論研究領(lǐng)域的事，我們以后再考慮。除非另外注明，本論文的接下來部分都基于假設(shè)1-3。    簡單地將一個一階邏輯知識庫的每個規(guī)則賦予權(quán)重，這個庫就變成一個馬爾科夫邏輯網(wǎng)。例如，利用表最后兩行的句子和權(quán)重構(gòu)建的馬爾科夫邏輯網(wǎng)， 當其它條件相同時，根據(jù)這個馬爾科夫邏輯網(wǎng)可以得出，n個沒有朋友的人不吸煙的概率要比所有沒有朋友的人都抽煙的概率小e(2.3)n倍。值得注意的是，表的那些帶全稱量詞的規(guī)則在現(xiàn)實世界都是錯的，但是作為馬爾科夫邏輯網(wǎng)的特征來看的話，卻抓住了朋友友誼和吸煙習慣間的有用信息。比如，青少年朋友傾向于有相同的吸煙習慣（Llo

29、yd-Richardson等，2002）。事實上，像表這樣一個馬爾科夫邏輯網(wǎng)簡潔地表示了一個社會關(guān)系分析中的一個主要模型（Wasserman & Faust，1994）。    顯而易見，馬爾科夫邏輯網(wǎng)包含了命題邏輯概率模型的所有要素，下面詳細說明。命題 4.2：任意離散或有限精度的數(shù)字隨機變量的概率分布都能用馬爾可夫邏輯網(wǎng)表達。證明：首先考慮布爾型的隨機變量（X1，X2，.，Xn）；我們?yōu)槊總€變量Xh定義一個不含參數(shù)的謂詞Rh，再將表示（X1，X2，.，Xn）每個狀態(tài)的規(guī)則加入到L中；這個規(guī)則是n個字的合取，當Xh為真時這個字取Rh()，否則取 

30、2; Rh()，這個規(guī)則的權(quán)重為logP（X1，X2，.，Xn）（如果某些狀態(tài)概率為0，我們就采用乘積形式，見等式3，用i()表示i狀態(tài)的概率）；因為L中所以謂詞都沒有參數(shù)，L所定義的馬爾科夫邏輯網(wǎng)每個變量Xi 就是一個節(jié)點，而且這個ML,C與常數(shù)C無關(guān)；對于任一狀態(tài)，相應規(guī)則為真，其它規(guī)則為假，這樣等式3就代表了初始分布（注意Z=1）。只要為每個變量定義一個沒有參數(shù)的謂詞，將上述方法推廣到任意離散變量就很簡單直接；有限精度數(shù)字隨機變量也一樣，只要用布爾矢量表示這些變量就可以了。（證畢）    當然，只要為相應的要因定義規(guī)則（馬爾科夫網(wǎng)的任意特征、節(jié)點狀態(tài)以及貝葉

31、斯網(wǎng)絡(luò)中的父節(jié)點），象馬爾科夫網(wǎng)、貝葉斯網(wǎng)這樣的緊湊要因模型仍然能用馬爾科夫邏輯網(wǎng)簡潔地表示。    一階邏輯（在假設(shè)1-3下）是馬爾科夫邏輯網(wǎng)的一個特例，下面將接著討論，這個特例的所有權(quán)重都相等且趨向無限大。命題4.3 設(shè)KB是一個可滿足的知識庫，L是一個所有規(guī)則都帶有權(quán)重的代表KB的馬爾科夫邏輯網(wǎng)，C代表KB中出現(xiàn)的常數(shù)集，Pw(x)是由ML,C得出的事件集x的概率，XKB是滿足KB的事件集，F(xiàn)為一階邏輯的任意規(guī)則，那么有：1、 xXKB limw Pw(x) = |XKB|-1 xXKB limw Pw(x) = 02、 F KB蘊含F(xiàn)當且僅當 limw P

32、w(F) = 1證明：設(shè)k為ML,C中基本規(guī)則的數(shù)量，利用等式3，若xXKB則Pw(x)=ekw/Z，若 xXKB則Pw(x)e(k-1)w/Z；所有xXKB等概率，又limw P(xXKB)/P(XKB) limw P(|xXKB|)/P(|XKB|)e-w=0（第一點證畢）。由蘊含的定義，所有滿足KB的事件也滿足F，設(shè)XF為滿足F的事件集，那么有 XKBXF，而Pw(F) = Pw(XF) Pw(XKB)，由第一點limw Pw(XKB) = 1，所以，limw Pw(XF) = 1；反過來，如果 limw Pw(XF) = 1，那么每個非零概率的事件極限上必須滿足F，這就包含了 XKB中

33、 所有的事件。（證畢）    換句話說，在所有相等的無窮大權(quán)重的極限中，馬爾科夫邏輯網(wǎng)表示了滿足知識庫的所有事件的一個均勻分布，所有蘊含問題可以通過計算問題規(guī)則的概率是否為1來判斷。即使在權(quán)重是有限值的情況下，從下面的觀念來看，一階邏輯已被植入到了馬爾科夫邏輯網(wǎng)中。不是一般性，我們假設(shè)權(quán)重都是非負的（若一個規(guī)則的權(quán)重w為負值，我們就用它的否定形式來替換，這時權(quán)重為-w），如果一個由馬爾科夫邏輯網(wǎng)L中規(guī)則構(gòu)成的知識庫是可滿足的，那么，對于任意常數(shù)集C來說，滿足情況的模式分配就是馬爾科夫邏輯網(wǎng)所代表的概率分布，這是因為這些模式都是有最大值iwini(x)（見等式3）的

34、事件，這個表達式在所有規(guī)則的所有可能為真時取最大值（比如，滿足知識庫）。但不管怎樣，馬爾科夫邏輯網(wǎng)和通常的一階邏輯知識庫不一樣，當包含矛盾的規(guī)則時，它也能產(chǎn)生有用的結(jié)果。一個馬爾科夫邏輯網(wǎng)也可以通過一些知識庫的合并來獲得，即使這些知識庫有部分不相容。這個特性在某些領(lǐng)域非常有潛力，如語義網(wǎng)（Berners-Lee et al.，2001）和大規(guī)模協(xié)作（Richardson & Domingos，2003）。    有一個馬爾科夫邏輯網(wǎng)一般化一階邏輯的簡單而有趣的例子，設(shè)一個馬爾科夫邏輯網(wǎng)只有一條規(guī)則：x R(x) S(x)、權(quán)重為w，常數(shù)集C = A；這里只

35、有4個事件：¬R(A)，¬S(A)、¬R(A)，S(A)、R(A)，¬S(A)、¬R(A)，S(A)，從等式3可以得出：P(R(A)，¬S(A)=1/(3ew+1)、其它三個事件的概率是ew/(3ew+1)（除數(shù)是配分函數(shù)Z，見第二章）；這樣，如果w>0，這個馬爾可夫網(wǎng)使得與x R(x) S(x)不一致的事件比其它的三個可能性更低一些；從上我們得到P(S(A)|R(A) = 1/(1+e-1)，limwP(S(A)|R(A) = 1，又回到了一階邏輯的結(jié)果。    實踐中，我們發(fā)現(xiàn)將每個謂詞單獨加到

36、馬爾可夫邏輯網(wǎng)中非常有用。換句話說，對于謂詞R(x1,x2,.)，我們加入規(guī)則x1,x2. R(x1,x2,.)，權(quán)重為wR，這使得單句的權(quán)重能與謂詞邊際分布較好地匹配，讓那些非單句的權(quán)重僅依賴與相關(guān)的謂詞。    如果對權(quán)重有一些直覺上的理解，那么對我們手工構(gòu)建或閱讀學習一個馬爾可夫邏輯網(wǎng)就有幫助。簡單地說，一條規(guī)則F的權(quán)重就在其它條件不變時為真或為假的對數(shù)差異。然而，F(xiàn)往往和其它規(guī)則有著共同的變量，想要反轉(zhuǎn)F同時保持其它規(guī)則不變往往不太可能，規(guī)則F的概率和它的權(quán)重之間也就不再存在一對一關(guān)系。不過，如果我們從最大熵分布的約束或者從學習經(jīng)驗概率的最大似然權(quán)重來看，

37、總的來說所有規(guī)則的概率決定了所有的權(quán)重（Della Pietra et al.，1997）。因此設(shè)定馬爾可夫邏輯網(wǎng)的權(quán)重最好的辦法是：寫下每個規(guī)則應有的概率，把它們當做經(jīng)驗頻率，然后運用第六章的算法來學習這些權(quán)重；相反地，從一個馬爾可夫邏輯網(wǎng)學習到的權(quán)重從統(tǒng)計上可以看作暗含著規(guī)則的經(jīng)驗概率。    如果使用類型化的常數(shù)和變量，由于只需要將變量基本化為相同類型的常數(shù)，那么，基本馬爾可夫邏輯網(wǎng)的大小可以大大減小。不過，即使這樣網(wǎng)絡(luò)還會非常巨大。幸運的是，正如下一章節(jié)介紹的，有許多推理問題并不需要基本化整個馬爾科夫邏輯網(wǎng)來解決。推理   

38、馬爾科夫邏輯網(wǎng)可以回答類似“規(guī)則F2成立的前提下，規(guī)則F1成立的概率是多少？”的任意問題。如果F1和F2是一階邏輯的兩個規(guī)則，C是出現(xiàn)在F1、F2中的常數(shù)的有限集合，而L代表馬爾科夫邏輯網(wǎng)，那么(4)其中XFi是Fi成立的事件集，P（X=x|ML,C）由等式3得出。一般圖形模型中的條件查詢都是等式4的特例，其中F1、F2和L中的謂詞都沒有參數(shù)，而且規(guī)則都是合取式。在一階邏輯中一個知識庫是否蘊含規(guī)則F實際上就是P（F|LKB,CKB,F）是否等于1的問題，LKB是將知識庫中所有規(guī)則權(quán)重都設(shè)成無窮大后等到的馬爾科夫邏輯網(wǎng)，CKB,F是KB或F出現(xiàn)的常數(shù)集合。在F2成立的條件下，利用等式4計算出P（

39、F|LKB,CKB,F）就能回答這個問題。即使在規(guī)模很小的領(lǐng)域直接利用等式4來計算都是棘手的，因為馬爾科夫邏輯網(wǎng)推理包含了#P-complete復雜度的概率推理，而邏輯推理在有限域也是NP-complete復雜度的，所以不能寄予期望?？墒?，提高推理運算效能的許多大數(shù)技術(shù)都可以運用到馬爾科夫邏輯網(wǎng)上，這是因為馬爾科夫邏輯網(wǎng)能使用細粒度的知識庫，包含了上下類的獨立性，推理就要比普通的圖模型更有效；在邏輯方面，具備了概率語義的馬爾科夫邏輯網(wǎng)能夠進行高效的近似推理。    原則上，P（F1|F2，L，C）可以使用馬爾科夫蒙特卡洛算法近似得出，只要拒絕轉(zhuǎn)移到F2不成立的狀態(tài)

40、，計數(shù)F1成立的取樣即可。但即使這樣對于任意規(guī)則，這種算法還是太慢了。當F1和F2都由基詞的合取式組成時，我們準備了一個的算法來替代，雖然沒有等式4的普遍性，但現(xiàn)實中的問題往往是這種形式，而且我們回答問題時將比直接應用等式4更有效率。研究提高的算法（比如要回答的問題含有變量）（參閱Jaeger（2000）和Poole（2003）最初的研究成果）是將來的一個重要研究方向。和知識庫模式構(gòu)建（Wellman等，1992）類似，這個算法分為兩個階段。第一階段求得計算P（F1|F2，L，C）所需基本馬爾科夫邏輯網(wǎng)的最小子集M，如表所示。任何事實上為真的基本規(guī)則可以忽略，相應的弧也可以省略掉，這樣等到的網(wǎng)

41、絡(luò)規(guī)模就大大縮小了，算法也就很快了。在最壞的情況下，得到的網(wǎng)絡(luò)有O（|C|a）個節(jié)點，其中a是所有謂詞的最大參數(shù)數(shù)量，實踐中a往往很小。表 馬爾科夫邏輯網(wǎng)推理中的網(wǎng)絡(luò)構(gòu)建 function ConstructNetwork(F1, F2, L, C)inputs: F1, a set of ground atoms with unknown truth values (the “query”)            F2, a set of ground atoms with know

42、n truth values (the “evidence”)            L, a Markov logic network            C, a set of constantsoutput: M, a ground Markov networkcalls: MB(q), the Markov blanket of q in ML,CG F1while

43、F1 for all q F1    if not q F2        F1 F1 (MB(q)G)       G G MB(q)    F1 F1 qReturn M, the ground Markov network composed of all nodes in G, all arcs between them in ML;C, and the features and weights on

44、 the corresponding cliques第二階段將F2相關(guān)節(jié)點設(shè)為F2成立的值，然后進行推理。我們應用的是吉布斯采樣法，但是其它推理方法也可以使用?；炯妓狗椒ㄊ窃谝粋€基本原子的馬爾科夫毛毯范圍內(nèi)對它進行取樣。一個基本原子的馬爾科夫毛毯是和它一起出現(xiàn)在某些基本規(guī)則中的基本原子集合。一個基本原子Xl在它的馬爾科夫毛毯Bl狀態(tài)為bl時的概率為其中Fl是Xl出現(xiàn)的基本規(guī)則集合，fi（Xl=xl，Bl=bl）是當Xl=xl，Bl=bl時第i個基本規(guī)則的特征值（0或者1）。對于那些在某些事件中確定為真的原子，就可以使用塊操作（比如在一步中將一個原子設(shè)為真，其它為假，在它們的聯(lián)合馬爾科夫毛毯

45、中取樣）。這樣一個基詞合取式的估計概率就是當馬爾科夫鏈收斂時這些基詞為真的取樣所占的比例。因為概率分布往往有多種樣式，我們需要多次運行馬爾科夫鏈。當一個馬爾科夫邏輯網(wǎng)是范式時，我們可以縮短預處理時間，運用MaxWalkSat這樣一個用于求解加權(quán)可滿足性問題的局部搜索算法（比如，找到一個真的賦值使得滿足的規(guī)則的權(quán)重之和最大）（Kautz et al.，1997）來搜尋模式再運行馬爾科夫鏈。當存在硬約束時（規(guī)則的權(quán)重無窮大），MaxWalkSat能發(fā)現(xiàn)滿足它們的區(qū)域，然后我們可再用吉布斯采樣法對這些區(qū)域采樣來估算概率。學習    我們可以從多個關(guān)系數(shù)據(jù)庫中學習馬爾科夫

46、邏輯網(wǎng)的權(quán)重（為了簡便下面只討論一個數(shù)據(jù)庫的情況，一般化到多個數(shù)據(jù)庫太瑣碎就省略了）。先引入閉型世界假定（Genesereth & Nilsson，1987）：如果一個基本原子不在數(shù)據(jù)庫中，那我們就假定它為假。如果有n個基本原子，那么數(shù)據(jù)庫最有效是矢量形式x=（x1,.,xl,.,xn），xl是第l個基本原子的值（如果在數(shù)據(jù)庫中為1，否則等于0）。有了數(shù)據(jù)庫，原則上馬爾科夫邏輯網(wǎng)的權(quán)重可以使用標準的方法學習到，如下：如果第i個規(guī)則在數(shù)據(jù)x中有ni(x)個真的基本形，那么等式3的對數(shù)概似函數(shù)對權(quán)重wi的導數(shù)為其中的求和是對所有事件庫x，而Pw（X=x）是P（X=x）用當前的權(quán)重矢量w =

47、 （w1,wi,）計算的。換句話說，第i部分的斜率就是它為真的基本形式與數(shù)學期望的差。不幸的是，即使一個簡單規(guī)則要數(shù)它的基本形式數(shù)量也是很棘手的事，如下（Dan Suciu）。命題6.1 對一個一階邏輯規(guī)則的真基本形計數(shù)是一個和它長度相關(guān)的#P-complete難題。證明：計數(shù)滿足單調(diào)二元合取范式命題的賦值數(shù)是個#P-complete難題（Roth，1996）。這個問題可簡化為如下的計數(shù)一個知識庫的一條一階邏輯規(guī)則的真基本形問題，設(shè)一個知識庫由R（0，1）、R（1，0）、R（1，1）基本原子組成，有一個單調(diào)二元合取范式規(guī)則由謂詞R（xi，xj）的合取式組成，而謂詞如xixj（比如（x1x2）（

48、x3x4）為R（x1，x2）R（x3，x4）。這樣滿足二元范式的賦值與為真的基本形之間有一一對應關(guān)系。（證畢）    在大領(lǐng)域一條規(guī)則的真基本形數(shù)量可以估算，通過均勻取樣并檢查是否為真來實現(xiàn)。在小的領(lǐng)域，如下面我們的實驗一樣，我們使用一種有效的遞歸算法來得到精確的數(shù)量。    等式6的另一個問題是計算為真的基本形的數(shù)學期望值同樣棘手，需要對整個模型進行推算。另外，高效的優(yōu)化方法還需要計算對數(shù)似然（等式3）和配分函數(shù)Z，這可以使用蒙特卡洛最大似然估計法（MC-MLE）（Geyer & Thompson，1992）?？梢裕谖覀兊?/p>

49、實驗中是使用吉布斯采樣法來計算蒙特卡洛最大似然值，微分在合理時間內(nèi)往往還沒有收斂，而使用沒有收斂的鏈來采樣往往得不到好的結(jié)果。在空間統(tǒng)計、社會網(wǎng)絡(luò)建模、語言處理等領(lǐng)域廣泛使用的一種更有效的選擇是優(yōu)化擬似然方法（Besag，1975）MBx（Xl）是Xl的馬爾科夫毛毯的狀態(tài)。擬對數(shù)似然的微分是其中ni(xxl=0)是當我們強制xl=0同時其余不變的情況下第i條規(guī)則為真的基本形數(shù)量，ni(xxl=1)也同樣。計算這個表達式（或者等式7）不需要對整個模型進行推測。我們還用有限記憶空間的BFGS算法對對數(shù)擬似然法進行優(yōu)化（Liu & Nocedal，1989），使得計算在下面幾個方面更高效：&

50、#183; 忽略第i條規(guī)則中不出現(xiàn)的謂詞，等式8的求和速度大大加快； · ni(x)、ni(xxl=0)、ni(xxl=1)不隨權(quán)重變化，只需要計算一次； · 因為ni(x)=ni(xxl=0)=ni(xxl=1)，只改變一個基詞的值不會改變基本規(guī)則的真假，因此可以忽略。特別的對任何有至少兩個為真的基詞的句子也成立，這往往是絕大多數(shù)基本規(guī)則的特性。     為了避免過度擬合，我們先針對每個權(quán)重利用高斯法對擬似然方法進行了變形。    可以使用歸納邏輯編程技術(shù)來精煉已有或者學習新增的規(guī)則，甚至從頭學習一個馬爾科夫邏輯

51、網(wǎng)。為此，我們使用了CLAUDIEN系統(tǒng)（De Raedt & Dehaspe，1997）。和其它只學習霍恩子句的歸納邏輯系統(tǒng)不同，CLAUDIEN能學習任意的一階邏輯句子，因此非常適用于馬爾科夫邏輯網(wǎng)，還可通過設(shè)定特別語言偏好使用CLAUDIEN來精煉馬爾科夫邏輯網(wǎng)的結(jié)構(gòu)。下一步我們計劃象MACCENT解決分類問題（Dehaspe，1997）一樣，將象Della Pietra et al發(fā)明的技術(shù)或方法等一般化到一階邏輯領(lǐng)域，將結(jié)構(gòu)學習功能完全引入到馬爾科夫邏輯網(wǎng)中。實驗    我們用描述華盛頓大學計算機科學工程系的知識庫來測試馬爾科夫邏輯網(wǎng)。該領(lǐng)域由1

52、2個謂詞、10大類2707個常數(shù)組成，類型有：出版物（342個常數(shù)）、人物（442）、課程（172）、項目（153）、學期（20）等等；謂詞有：Professor(person)、Student(person)、Area(x, area)（x可以取出版物、人物、課程和項目的值)、AuthorOf(publication,person)、 AdvisedBy(person,person)、YearsInProgram(person,years)、CourseLevel(course, level)、TaughtBy(course,person,quarter)、 TeachingAssistan

53、t(course,person,quarter)等等；另外還有10個等于謂詞：SamePerson(person,person)、 SameCourse(course, course)等等，如果兩個參數(shù)值代表相同的常數(shù)，那么就為真。    使用變量類型后，所有可能的基本原子（第六章的n）總數(shù)為4106841，而數(shù)據(jù)庫含有3380個元組（比如3380個為真的基本原子）。我們通過抓取系網(wǎng)站的網(wǎng)頁)獲取數(shù)據(jù)，出版物和作者之間的關(guān)系通過BibServ數(shù)據(jù)庫（）所有記錄中的作者字段至少含兩部分（名、姓）獲得。    四個自愿者每個人都提供了一套

54、一階邏輯規(guī)則來描述這個領(lǐng)域，為我們建立了知識庫（這些自愿者不知道數(shù)據(jù)庫中的元組，但他們都是系里的成員，對整個系有一定的了解）。整合起來后我們獲得了一個有96條規(guī)則的知識庫。整個知識庫、數(shù)據(jù)、算法的參數(shù)、自愿者的指示在可以找到。知識庫中有類似這樣的規(guī)則：學生不是教授；每個學生至少有一個導師；如果一個學生是一篇論文的作者，那么他的導師也是；研究生只上他導師的課程；一篇出版物的作者至少有一位是教授；物理博士第一階段的學生沒有導師等等。請注意上述規(guī)則并不總是正確的，但通常是。    為方便訓練和測試，我們按人工智能、圖像、編程語言、系統(tǒng)和理論5個領(lǐng)域?qū)?shù)據(jù)庫分成5個子數(shù)據(jù)

55、庫。教授和課程這些常數(shù)被手工分配到各個領(lǐng)域，其它常數(shù)被賦予它們最常出現(xiàn)的領(lǐng)域，然后元組被添加到其中常數(shù)所屬的領(lǐng)域，含有不同領(lǐng)域常數(shù)的元組被刪除以避免訓練測試混亂。這些子數(shù)據(jù)庫平均在58457個可能的基本原子中有521個真的基本原子。    我們使用了一個留下一個的測試策略，每次測試一個領(lǐng)域時采用其余四個領(lǐng)域的訓練結(jié)果。兩個測試任務是預測謂詞AdvisedBy（x，y）：任務A，其它信息都知道；任務B，除了Student(x) 和Professor(x)以外，其它信息都知道。在兩個例子中我們都測量了所有領(lǐng)域中謂詞AdvisedBy（x，y）的基本形的平均條件對數(shù)似然

56、率，畫出查準率查全率曲線，然后計算曲線下的面積。這項任務就是連接預測的一個實例，這個問題在統(tǒng)計關(guān)系學習（見第8章）中廣泛關(guān)注。測試中所有知識庫被轉(zhuǎn)化成范式，時間結(jié)果是基于2.8G赫茲奔4處理器的主機。1. 測試的系統(tǒng)    為了評估使用邏輯和概率推理的馬爾科夫邏輯網(wǎng)，我們計劃將它與純邏輯法和純概率方法相比較，同時我們還對使用歸納邏輯程序技術(shù)的規(guī)則自動歸納感興趣。下面各小節(jié)詳細描述了用于比較的各類系統(tǒng)。1.1 邏輯    使用純邏輯實驗的主要目的是為了幫助我們回答一個重要問題，那就是將概率引入邏輯知識庫是否能夠提升我們對某領(lǐng)域建模的能力

57、。為了做到這一點需要我們在回答問題時僅使用邏輯推理，但實際上這非常復雜，因為計算對數(shù)似然率和查準率查全率曲線下的面積需要概率，或者至少對測試中為真的每個基本原子要有“確信度”的衡量值。為此，我們使用了以下方法來近似，設(shè)KB為一知識庫，E為已證實的原子集合，XKBE為滿足KBE的事件集，那么，我們查詢的原子q的概率為P(q)=|XKBEq|/|XKBE|，這是q在XKBE為真的比例。    一個更嚴重的問題是知識庫可能不一致（從自愿者收集的知識庫更是如此），這時P(q)公式的分母為0（設(shè)想一下一個不一致的知識庫可能包含任意規(guī)則）。為了解決這個問題，我們重新將XKBE

58、定義為滿足最大可能基本規(guī)則數(shù)量的事件集合，再用吉布斯采樣法對這個集合進行采樣，每次鏈的初始狀態(tài)由WalkSat方法來獲得。每一步吉布斯采樣都有概率：如果新狀態(tài)滿足的規(guī)則大于當前狀態(tài)，那么，概率為1（也就是當前狀態(tài)的概率應該為0）；如果滿足的規(guī)則數(shù)量與當前狀態(tài)相等，則概率等于0.5；如果新狀態(tài)滿足的規(guī)則數(shù)量要少則概率為0。然后我們再用最大滿足的規(guī)則來計算概率。實際上，等同于從知識庫中構(gòu)建一個權(quán)重無窮大的馬爾科夫邏輯網(wǎng)。1.2 概率    另外一個需要實驗來幫我們回答的問題是是否已經(jīng)存在足夠強大的（命題）概率模型而不再需要馬爾科夫邏輯網(wǎng)的表達能力。 為了應用這種模型，

59、這個領(lǐng)域需要定義一些有表現(xiàn)力的屬性值來命題化，在這種高度關(guān)聯(lián)的領(lǐng)域中創(chuàng)建好的屬性對于命題學習者來說非常困難。無論如何，在平衡了更多潛在關(guān)系信息表達能力和極其冗長的屬性矢量后，我們定義了兩套命題屬性：order-1和order-2。前者包含了查詢謂詞中個體常數(shù)的特性，后者包含了常數(shù)之間關(guān)系的特性。    對于order-1的屬性，我們?yōu)槊繉Γ╝，b）定義一個變量，a是詢問謂詞的一個自變量；b是某個謂詞的自變量，它的值和a一樣。我們定義的變量代表這個謂詞為真的基本形的比例。例如AdvisedBy（Matt，Pedro）有：Pedro是否是學生，Pedro的出版物占比，

60、Matt當助教的課程占比等等。    order-2屬性是這樣定義的：給定詢問謂詞Q（q1,q2,qk），考慮所有k個謂詞和k個常數(shù)q1,q2,qk一一對應集合集，例如Q是AdvisedBy（Matt，Pedro）那么TeachingAssistant（-，Matt，-），TaughtBy（-，Pedro，-）是其中一個集合，這個例子就有2K個屬性，每個對應于k個謂詞的某個為真的基本形。屬性的值等于訓練中當未賦值的變量被賦予相同的值時，謂詞集有特定真賦值的次數(shù)。例如，上述變量為“CSE546”和“Autumn0304”，集合TeachingAssistant（CS

61、E546，Matt，Autumn0304），TaughtBy（CSE546，Pedro，Autumn0304）在訓練時有一些為真的賦值（比如，True，True，True，F(xiàn)alse）,屬性值就是滿足True，True為真賦值的常數(shù)集數(shù)量；True，F(xiàn)alse也一樣；以此類推。查詢謂詞AdvisedBy（Matt，Pedro）的order-2屬性舉例有：Pedro教的課程中Matt任助教的頻度（反過來不任助教的頻度），有多少出版物是Matt和Pedro一起寫的，等等。    最后得到的28個order-1屬性和120個order-2屬性（任務A）通過訓練學習被我們

62、分散到5個等頻度的桶中，我們使用了兩種命題學習方法：簡單貝葉斯（Domingo & Pazzani，1997）和貝葉斯網(wǎng)絡(luò)（Heckerman等，1995）（每個節(jié)點最大4個父節(jié)點，結(jié)構(gòu)和參數(shù)使用VFBN2算法（Hulten & Domingos，2002）求得）。order-2屬性能幫助簡單貝葉斯分類，但是降低了貝葉斯網(wǎng)絡(luò)分類的性能，因此我們報告簡單貝葉斯結(jié)果時使用order-1和order-2屬性，而貝葉斯網(wǎng)絡(luò)僅僅用order-1屬性。1.3 歸納邏輯程序    我們起始的知識庫是自愿者提供的，但是我們對能否用歸納邏輯程序方法自動得到也感興趣。前面提到過，我們使用CLAUDIEN方法從數(shù)據(jù)中歸納知識，CLAUDIEN是這樣運行的：本地范圍、最小精度0.1、使用最小覆蓋、最大復雜度10、廣度優(yōu)先搜索。CLAUDIEN的搜索空間由它的語言偏好決定，我們架構(gòu)這樣的語言偏好以允許：一個句子最多3個變量；一個句子中謂詞數(shù)量不限；一個句子中一個謂詞至多以二次肯定形式出現(xiàn)和二次否定；謂詞的自變量有類型。為了最小化搜索，改善結(jié)果，我們不使用等于謂詞（如SamePerson）。    除了從訓練數(shù)據(jù)中歸納規(guī)則，我們還對自動優(yōu)化由自愿者提供的知識庫感興趣。CLAUDIEN本身沒有這個功能，但可以構(gòu)建一個語言偏