人工智能詳解

第九章不確定條件下的推理河南師范大學(xué)

河南師大計算機與信息工程學(xué)院目錄2引言簡介基于邏輯的反繹推理反繹：邏輯之外的辦法處理不確定性的隨機方法結(jié)語和參考文獻習(xí)題3引言

所有傳統(tǒng)邏輯習(xí)慣上總是假定當(dāng)前使用的是精確地符號。正因為如此，傳統(tǒng)邏輯難以應(yīng)用于現(xiàn)實生活，而只是存在于虛幻的想象之中。----伯蘭特.羅素4

滿足于事物自身允許的精確度，在只要近似解就能滿足的情況下而不去尋求精確解，這事很有指導(dǎo)意義的。-----亞里士多德適用于現(xiàn)實世界的數(shù)學(xué)定律都不具有確定性，具有確定性的數(shù)學(xué)定律則不適用于現(xiàn)實世界。-----阿爾伯特.愛因斯坦引言亞里士多德愛因斯坦5簡介

我們前面學(xué)到的的推理過程遵循著謂詞演算所用的推理模型：可靠的推理規(guī)則從正確的前提推出新的正確的結(jié)論。但是許多情況下我們必須用不可靠的推理規(guī)則從形式不規(guī)則和不確定的證據(jù)中得出有用的結(jié)論。

我們現(xiàn)實生活中的幾乎所有方面都做到了用不可靠的推理從不完備和不精確的數(shù)據(jù)中得出有用的結(jié)論這一點。比如：我們從不明確的癥狀得出正確的醫(yī)療診斷并給出相應(yīng)的治療方案，等等。

不確定性推理6不確定條件下推理問題——汽車專家系統(tǒng)規(guī)則2

如果

發(fā)動機不旋轉(zhuǎn)而且燈不亮，

那么

電池或電纜有問題。這條規(guī)則看起來像一個用在可靠推理中的普通的謂詞關(guān)系。但實際上它是啟發(fā)式的。一種可能情況是，電池和電纜是好的，汽車只是發(fā)動機壞了，前燈燒了，雖然這并不太可能。發(fā)動機不能工作和燈不亮不一定意味著電池和電纜是壞的。7有趣的是這條規(guī)則的逆為真：

如果

電池或電纜有問題，

那么

發(fā)動機不旋轉(zhuǎn)而且燈不亮。

除非有超自然的能力，否則如果電池壞了，燈和發(fā)動機都不能工作！

簡介8

我們的專家系統(tǒng)提供了一個反繹推理的例子。形式上，反繹推理認(rèn)為從P->Q和Q可能推出P。反繹推理是不可靠的推理，意思就是說在前提為真的任一解釋下，結(jié)論不一定為真。

雖然反繹是不可靠的，它對于解決問題來說卻是很重要的。前面的“邏輯上正確”的規(guī)則對診斷汽車故障不是很有用是因為它的前提，電池壞了是我們的目標(biāo)，它的結(jié)論是我們看到的癥狀，我們必須用這些結(jié)論進行診斷。但是，這條規(guī)則可以以反繹的形式使用，就像許多診斷型專家系統(tǒng)中的規(guī)則一樣。故障或疾病引起（蘊含）癥狀，而不是相反的方式，但是診斷必須要由癥狀往回找原因。簡介9

在知識庫系統(tǒng)中，我們經(jīng)常為每條規(guī)則添加一個確信因子來度量結(jié)論的確信度。比如，斷言thelightshavefullpower(0.2)說明前燈確實亮了，但燈光微弱，幾乎看不見。信念和不完全的數(shù)據(jù)可以通過規(guī)則傳播來對結(jié)論加以限制。

簡介拓展10基于邏輯的反繹推理

首先，我們介紹基于邏輯的方法進行反繹。為了克服傳統(tǒng)邏輯的局限性，尤其是在信息丟失或不確定的情況下傳統(tǒng)推理過程可能就難以派上用場。在此我們給出傳統(tǒng)邏輯的擴展讓它來支持反繹推理。

擴展邏輯來讓他描述充滿變化信息和信念的世界。傳統(tǒng)的數(shù)理邏輯是單調(diào)的：它從一個公里集合開始，假定它為真，然后推出結(jié)論。如果我們對系統(tǒng)增加新的信息，就會引起真命題集合擴大。增加知識永遠(yuǎn)不會讓真命題集合減小。當(dāng)我們試圖為建立在信念和假設(shè)基礎(chǔ)上的推理建模的時候，這種單調(diào)性就會帶來問題。11

非單調(diào)推理解決變化信念的問題。非單調(diào)推理系統(tǒng)處理不確定性是通過借助于不確定信息做最合理的假設(shè)的方式來實現(xiàn)的。然后它進行推理，好像這些假設(shè)是真的。稍后，信念會改變，這就需要對從那個信念得出的結(jié)論進行重新驗證?；谶壿嫷姆蠢[推理12（1）非單調(diào)推理邏輯

非單調(diào)性是人類求解問題和常識推理的一個重要特征。在大量的規(guī)劃問題中，比如當(dāng)我們開車上班的時候，我們對道路和交通情況作大量的假設(shè)。如果我們發(fā)現(xiàn)其中的一個假設(shè)被推翻了，或許是道路施工或者是路上的交通事故，我們會改變我們的計劃，尋找其他的路線。

基于邏輯的反繹推理13

使用謂詞邏輯的常規(guī)推理基于三個重要的假設(shè)。首先，謂詞描述對于我們的應(yīng)用領(lǐng)域來說必須是充分的。也就是說，解決問題所需的信息都能被表示出來。其次，信息庫必須是一致的，也就是說，各條知識不能相互矛盾。最后，通過運用推理規(guī)則，得到的信息單調(diào)增長。如果上述三條假設(shè)中的任意一條不能滿足，常規(guī)的基于邏輯的方法就不起作用了?；谶壿嫷姆蠢[推理14

非單調(diào)系統(tǒng)解決了上述三個問題。首先，推理系統(tǒng)經(jīng)常會缺少領(lǐng)域知識。一個重要的問題是:假設(shè)我們沒有關(guān)于謂詞P的知識，但缺少知識意味著我們對P是否為真不太確定還是我們確信notP為真呢？這個問題可以用許多種方式來回答。Prolog采用封閉的世界假設(shè)把推理系統(tǒng)不能證明為真的都認(rèn)為是假的。作為人類自身，我們經(jīng)常采用其他的辦法來假定一些事情為真，除非它可以被明確地看出是假的。基于邏輯的反繹推理15

另外一個解決缺少知識的問題的辦法是對為真的情況做明確的假定。在人們推理的時候，我們假定無辜的人是與犯罪無關(guān)的人。我們可能會進一步假定無辜的人是不能從犯罪中獲益的人。進一步假定能有效地補充我們?nèi)鄙俚闹R細(xì)節(jié)，基于這樣的假定我們不能擴展我們的推理得到新的結(jié)論。第三節(jié)中將討論封閉世界和其他的一些辦法。基于邏輯的反繹推理16人的推理是基于現(xiàn)實通常的情況。大多數(shù)鳥會飛。父母通常愛護并撫養(yǎng)它們的孩子。我們的推理是建立在同用現(xiàn)實世界的假設(shè)進行推理相一致的基礎(chǔ)上。在本節(jié)中，我們將討論模態(tài)操作符的擴充，比如，isconsistentwith和unless，用它們來進行基于假設(shè)的推理?；谶壿嫷姆蠢[推理17

傳統(tǒng)的基于邏輯的系統(tǒng)所需要的第二條假設(shè)是對知識的推理必須是一致的。對于我們推理者來說，這個假定給我們很大的限制。在分析一個問題時，我們通常會對一個情景給出多種解釋，并假定一些是真的直到其他假定被證實更為有效。比如，在分析飛機事故的原因的時候，空難專家會給出多種原因，直到發(fā)現(xiàn)新的信息才排除一部分原因。有多種可能情況時，我們?nèi)擞贸ＷR來試圖指導(dǎo)推理。我們也希望邏輯系統(tǒng)能給出多種可能的假設(shè)?；谶壿嫷姆蠢[推理18

最后，要想運用邏輯系統(tǒng)就必須解決知識庫更新的問題。這里有兩個問題：一個是怎么添加只基于假設(shè)的知識，另外一個是在后來發(fā)現(xiàn)假設(shè)不正確的時候怎么辦。對于第一個問題，可以允許添加基于假設(shè)的新知識。這些新知識被假定是正確的，因此它們可以用來推出新的知識。這種做法的代價是跟蹤基于假設(shè)的所有證據(jù)和推理：必須做好準(zhǔn)備對基于假設(shè)的知識進行調(diào)整?；谶壿嫷姆蠢[推理19

由于結(jié)論可能會調(diào)整，非單調(diào)推理被認(rèn)為是可廢除的，也就是說，新的信息可能會使前面的結(jié)果失效。跟蹤邏輯系統(tǒng)中各步推理的表示和搜索程序稱為真值維護系統(tǒng)，或TMS。在可廢除的推理中，TMS保持知識庫的一致性，記錄可能會出現(xiàn)問題的結(jié)論。第二節(jié)中考慮多種真值維護的辦法?，F(xiàn)在考慮能讓傳統(tǒng)基于邏輯的推理系統(tǒng)可廢除的操作符。基于邏輯的反繹推理20

在實現(xiàn)非單調(diào)推理時，我們可以用操作符unless來擴展我們的邏輯.unless支持在證據(jù)不為真的情況下基于信念的推理。假定我們有以下謂詞邏輯語句:p(X)unlessq(X)→r(X)p(Z)r(W)→s(W)

第一條規(guī)則表明p(X)為真并且我們不認(rèn)為q(X)為真的情況下我們可以推出r(X)。當(dāng)這些條件滿足時，我們可以推出r(X)，然后用r(X)，我們可以推出s(X)。這樣，當(dāng)我們改變信念，或者發(fā)現(xiàn)q(X)為真的時候，r(X)還有s(X)就要收回。需要指出的是，unless是來處理信念的問題而不是真假的問題。所以，把證據(jù)的值從“未知或者被認(rèn)為是假”變成“被認(rèn)為或者已知為真”就會導(dǎo)致我們收回基于這些信念的推理。通過把邏輯擴展為用可能會被收回的信念來推理，我們把非單調(diào)性引入到了系統(tǒng)中。基于邏輯的反繹推理21

上面討論的推理機制還可以引入默認(rèn)規(guī)則(Reiter1980)。如果我們用p(X)unlessabp(X)→r(X)來代替p(X)unlessp(X)→r(X)，其中abp(X)代表abnormalp(X),我們說除非我們有p的一個反常的實例，比如一只翅膀斷了的鳥，我們可以有以下推理：如果X是一只鳥，那么X會飛。

擴展邏輯系統(tǒng)的另外一個模態(tài)操作符是由McDermott和Doyle(1980)提出的。它們用模態(tài)操作符M來擴展一階謂詞，它置于謂詞前面讀作isconsistentwith(與…..相一致)。例如：?Xgood_student(X)∧Mstudy_hard(X)→graduates(X)

這個子句可以被讀作：對于任意X，Y是一個好學(xué)生，如果X學(xué)習(xí)刻苦與我們所知的其他事情相一致的話，X就可以畢業(yè)。當(dāng)然，這里困難的事對與我們所知的其他事情相一致的含義進行定義?；谶壿嫷姆蠢[推理22

首先要指出，與我們所知的其他事情相一致這句話可能是不可判定的。原因是模態(tài)操作符會形成一個已知不可判定系統(tǒng)的超級。有兩種辦法來解決不可判定問題。首先，我們可以用失敗即否定的證明來說明相一致。在我們的例子中，試圖尋找not(study_hard(X))證據(jù)，如果不能證明X不學(xué)習(xí)，那就假定X學(xué)習(xí)。在類似于Prolog的近似于謂詞邏輯的系統(tǒng)中，我們經(jīng)常用這種辦法。然而，這種辦法會不恰當(dāng)?shù)乜s小我們解釋的空間。

解決“與……相一致”問題的第二種辦法是對謂詞的真假做基于啟發(fā)式的和時間空間有限的搜索。例中的謂詞study_hard(X)，如果沒有相矛盾的結(jié)論，就假定它為真，這意味著可能會收回畢業(yè)這個結(jié)論以及其他基于此得出的結(jié)論。

用isconsistentwith操作符我們可能會產(chǎn)生相矛盾的結(jié)論。假定某人Peter是一個好學(xué)生而且喜歡社團活動。我們可以用以下謂詞集合來進行描述：基于邏輯的反繹推理23?Xgood_student(X)∧Mstudy_hard(X)→graduates(X)?Yparty_person(Y)∧Mnot(study_hard(Y))→not(graduates(Y))good_student(peter)party_person(peter)

我們沒有Peter的學(xué)習(xí)習(xí)慣、他學(xué)習(xí)是刻苦等進一步的信息，但是我們使用這些句子可以推出Peter畢業(yè)和Peter不畢業(yè)。

防止出現(xiàn)這種矛盾結(jié)論的辦法是記錄下與模態(tài)操作符isconsistentwith綁定在一起的變量。這樣，一旦Peter結(jié)合到謂詞study_hard或者not(study_hard)中，系統(tǒng)就會防止Peter再結(jié)合到其他謂詞中。其他模態(tài)邏輯系統(tǒng)做法更為保守，它防止任何可能矛盾的子句集得出的結(jié)論。我們可以產(chǎn)生另外一個不規(guī)則集：基于邏輯的反繹推理24?Yvery_smart(Y)∧Mnot(study_hard(Y))→not(study_hard(Y))?Xnot(very_smart(X))∧Mnot(study_hard(X))→not(study_hard(X))從這些子句可以推出一個新的子句：?ZMnot(study_hard(Z))→not(study_hard(Z))模態(tài)操作符isconsistentwith的語義的進一步擴展解決了這樣的不規(guī)則推理的問題。一個擴展就是自認(rèn)知邏輯。

另外的一個非單調(diào)邏輯系統(tǒng)是由Reiter提出的默認(rèn)邏輯。默認(rèn)邏輯采用以下新的推理規(guī)則形式：A(Z)∧:B(Z)→C(Z)

讀作：如果A(Z)可被證實并且它與我們所知道的對B（Z）的假定相一致，我們就可以推出結(jié)論C(Z)基于邏輯的反繹推理25現(xiàn)在看起來默認(rèn)邏輯與剛討論過的McDermott和Dolye的非單調(diào)邏輯很相似。這兩者之間的一種重要不同是推理的方式。在默認(rèn)邏輯中，這些特殊的推理規(guī)則從原始的功力/定理集合中推出似真的推論。每個推論都是用默認(rèn)邏輯推理規(guī)則從原始公里/定理集合表示的知識推出來的。這樣，一個原始知識庫產(chǎn)生很多似真的推論就是很自然的了。我們可以從graduate子句中看出來：?Xgood_student(X)∧：study_hard(X)→graduates(X)?Yparty(Y)∧not:(study_hard(Y))→not(graduates(Y))基于原始知識集每個子句都能推出一個特有的似真的推論。

模態(tài)邏輯允許用似真的推論推出的任一定理作為進一步推理的公理。這就必須要有一些其他的策略來決定哪一個推論用來進行問題求解。默認(rèn)邏輯沒有涉及怎樣從一個知識庫的所有似真推論中進行選擇的問題。Peiter(1987)、Reiter和Criscuolo(1981)和Touretzky(1986)進一步解決了這些問題?；谶壿嫷姆蠢[推理26最后，非單調(diào)邏輯推理情況，它是通過繼承搜索那些繼承了多個父節(jié)點的對象表示時產(chǎn)生的。前面提到的喜歡社團的好學(xué)生Peter，可以繼承好學(xué)生的屬性集，也就是他很可能畢業(yè)。Peter還可以從其他的作為社團成員那里繼承屬性，這種情況下會有點矛盾，這樣，他就不能畢業(yè)。

非單調(diào)推理系統(tǒng)的主要問題是怎樣有效的來修改根據(jù)變化的信念得出的結(jié)論。比如，如果我們用前提r推出s，那么除掉r也就除掉了對s和其他用s得出的結(jié)論的支持。除非由一個獨立的推理集來支持s，否則s都會被收回。在壞的情況下，實現(xiàn)收回這一過程需要我們在信念每次變化的時候重新計算所有的結(jié)論。接下來將要討論的真值維護系統(tǒng)將提供保持知識庫一致性的機制。

基于邏輯的反繹推理27（2）真值維護系統(tǒng)

真值維護系統(tǒng)(TMS)可以被用來保持一個推理系統(tǒng)的邏輯完整性。像在前面指出的那樣，每當(dāng)用知識的子句來表示的信念被修改時，對知識庫中的條目的支持情況重新計算是很有必要的。推理維護系統(tǒng)是通過存儲每條推理的理由，再重新考慮根據(jù)新的信念得出的結(jié)論的支持情況。

解決這個問題的一個辦法是對回溯算法進行修改?；厮菟惴ㄊ窃诨谒阉鞯膯栴}求解中在決策點遍歷所有可能路徑的一種系統(tǒng)方法。但是，回溯算法的主要缺點是它系統(tǒng)地(和盲目地)從空間的死端狀態(tài)退回，在最近的選擇中尋找可能路徑。這種方法有時被稱為時序回溯。我們承認(rèn)時序回溯會系統(tǒng)地檢查空間的所有可能情況，但是，它遍歷的方式是費時的、低效率的、大空間的、和無效的?；谶壿嫷姆蠢[推理28

在基于邏輯的搜索中，我們真正想要的是直接回溯到空間中出現(xiàn)的問題的點，并在那個狀態(tài)對解進行修改的能力。這種方法被稱為相關(guān)性指導(dǎo)回溯。我們來看一個非單調(diào)推理的例子。我們需要找到P，它不能由直接推理得到。但有一個似真的假設(shè)q，如果它為真，可以推出p。所以我們假定q然后得到p。我們的推理繼續(xù)，由p我們得到r和s。我們繼續(xù)推理，沒有p、r或者s的支持，我們可以得到結(jié)論t和u。最后，我們得出先前的對q的假設(shè)是錯誤的。然后我們要做什么呢？

時序回溯會重新遍歷我們推理的步驟，順序同生成的時候正好相反。相關(guān)性指導(dǎo)回溯會立即回到矛盾信息的源頭，比如上面例子中的對q的假設(shè)。然后它向前回收p、r和s。這時，我們檢查r和s是否與p和q無關(guān)。這是因為它們是從不正確的假設(shè)推出來的，這并不意味著它們不被其他支持。最后，因為t和u是在沒有p、r和s的情況下得到的，我們就不用對t和u進行整理。基于邏輯的反繹推理29

要想在推理系統(tǒng)中運用相關(guān)性指導(dǎo)回溯算法，我們必須：1）把每條結(jié)論與它的理由聯(lián)系在一起。這個理由說明了結(jié)論得到的過程。它必須包括所有事實、規(guī)則和用來推出結(jié)論的假設(shè)。2）提供一種機制，在給定矛盾和它的理由時，能找到導(dǎo)致矛盾的理由中的錯誤假設(shè)。3）收回錯誤假設(shè)4）產(chǎn)生一種機制能追溯到收回的假設(shè)，并收回基于理由中收回的錯誤的假設(shè)的結(jié)論。

當(dāng)然，所有收回的結(jié)論并不一定是假的，所以要重新檢查它們看它們在沒有收回的子句的情況下能否被證實。我們接下來給出兩種建造相關(guān)性指導(dǎo)回溯系統(tǒng)的辦法?；谶壿嫷姆蠢[推理30

JonDoyle(1979)研制了基于理由的真值維護系統(tǒng)(JTMS)，它是最早的真值維護系統(tǒng)之一。Doyle是最早明確地把真值維護系統(tǒng)、命題和理由組成的網(wǎng)絡(luò)從一些領(lǐng)域中推理系統(tǒng)分離出來的學(xué)者。分離的結(jié)果是JTMS與問題求解器（或許是自動定理證明程序）進行交互，它接收新的命題和理由，然后提供給問題求解器有關(guān)信息，即通過現(xiàn)有理由來判斷哪個命題被認(rèn)為是真的。JTMS主要有三個操作。首先，JTMS檢查理由網(wǎng)絡(luò)。這個檢查操作可以由問題求解器的查詢來觸發(fā)，比如：我是否要相信命題p？我們?yōu)槭裁匆嘈琶}p？為什么假設(shè)支持命題p?JTMS的第二個操作是修改相關(guān)性網(wǎng)絡(luò)，由問題求解器提供的信息引起修改。修改包括添加新的命題，添加或刪除前提，增加矛盾，對命題中的信念進行證實。JTMS的最后一個操作是更新網(wǎng)絡(luò)。只要相關(guān)性網(wǎng)絡(luò)發(fā)生變化，這個操作就會被執(zhí)行。更新操作重新計算所有的與現(xiàn)存理由相一致的命題的標(biāo)簽?；谶壿嫷姆蠢[推理31

我們建造一個簡單的相關(guān)性網(wǎng)絡(luò)來演示JTMS。下面的模態(tài)操作符M在第一節(jié)中提到過，它放在謂詞前面讀作isconsistentwith(與…..相一致)。例如：?Xgood_student(X)∧Mstudy_hard(X)→study_hard(X)?Ypart_person(Y)→not(study_hard(Y))good_student(david)我們現(xiàn)在就把上面的命題集合放到理由網(wǎng)絡(luò)中去。

在JTMS中，每個代表一個信念的謂詞由其他兩個信念集合來進行關(guān)聯(lián)。第一個集合是對于一個信念來說支持它成立的信念集合。在圖9-1中被標(biāo)記為IN。第二個集合是對于一個信念來說不支持它成立的信念集合，被標(biāo)記為OUT。圖9-1表示了支持study_hard(david)的理由，它由圖中列出的謂詞推導(dǎo)出來。圖9-1中的符號根據(jù)Goodwin(1982)改編的，圖9-2給出了解釋。圖9-2a表示理由的前提假設(shè)，圖9-2b表示支持結(jié)論的命題的合取?；谶壿嫷姆蠢[推理32

good_student(David)not(study_hard(Y))party_person(Y)study_hard(David)INOUT圖9-1相信David學(xué)習(xí)刻苦的理由網(wǎng)絡(luò)基于邏輯的反繹推理33a)前提理由anot(b)b)兩個信念a和notb的并來支持c圖9-2圖9-1的符號解釋（Goodwin1982）基于邏輯的反繹推理34not(study_hard(David))part_person(David)OUTININ圖9-3圖9-1的新標(biāo)記，即與新的前提party_person(David)相聯(lián)系基于邏輯的反繹推理35

像圖9-1和圖9-3顯示的那樣，JTMS并不直接反映原始命題集中所表示的謂詞關(guān)系。JTMS是一個簡單的網(wǎng)絡(luò)，它只考慮原子命題與原子命題的非之間的關(guān)系，并把它們組織起來支持信念之間的關(guān)系。整個謂詞鏈接和推理機制(?X、∧、∨、→，等等)用于問題求解器內(nèi)部使用。McAllester(1987)和Martins及Shapiro(1988)把TMS和問題求解器合并起來，使它們采用單一的表示。JTMS只關(guān)心信念之間的相關(guān)情況，而不關(guān)心信念的內(nèi)容。所以，我們可以用形如n1，n2，……的標(biāo)識符來代替信念，用它們來表示網(wǎng)絡(luò)中鏈接的結(jié)點。像我們在study_hard例子中所看到的的那樣，IN和OUT代數(shù)可以讓JTMS對信念的支持情況進行推理。

總結(jié)一下，JTMS就是在結(jié)點和理由的集合上來工作的。結(jié)點代表信念，理由支持結(jié)點上的信念。結(jié)點之間的聯(lián)系是用IN和OUT來標(biāo)記，它表示了連接點的信念狀態(tài)。通過與結(jié)點有IN和OUT關(guān)系的結(jié)點的情況，我們可以推出該節(jié)點是否成立。JTMS的主要操作有完成檢查、修改，基于邏輯的反繹推理36以及更新上面提到的操作符。因為理由的檢查是它自身回溯理由網(wǎng)絡(luò)的鏈接來實現(xiàn)的，我們就舉了一個相關(guān)性指導(dǎo)回溯的例子。

第二種真值維護系統(tǒng)是基于假設(shè)的真值維護系統(tǒng)(ATMS)。雖然Martins和Shapiro(1983)提出了相近的詞語，但基于假設(shè)這個名詞是由deKleer(1984)首先提出來的。在這種系統(tǒng)中，網(wǎng)絡(luò)中結(jié)點的標(biāo)簽不再是IN和OUT，而是決定推導(dǎo)的前提(假設(shè))集。deKleer還區(qū)分了兩種結(jié)點，前提結(jié)點可以通用，而由問題求解器通過前提推出的結(jié)點可能會被收回。ATMS比JTMS優(yōu)越的地方就體現(xiàn)在ATMS提供了處理信念的多種可能狀態(tài)的靈活性。通過對信念標(biāo)記支持它的前提集，信念就不會只是單一狀態(tài)了(在JTMS中所有的結(jié)點被標(biāo)記為IN)，而是一組可能的狀態(tài)，所有的支持前提集的所有子集的集合。創(chuàng)建不同的信念集就會允許對選擇不同前提得出的結(jié)論的比較，問題的不同的答案的尋在，還允許矛盾的發(fā)現(xiàn)和回復(fù)。ATMS是的不足包括不能表示自身非單調(diào)的前提集，不能控制問題求解器。基于邏輯的反繹推理37

ATMS和問題求解器的交互同JTMS和問題求解器之間的交互很相似，都有檢查、修改和更新操作。唯一的不同是在ATMS中不再是單一狀態(tài)的信念，而是所有支持前提集的子集。ATMS當(dāng)中的目標(biāo)就是尋求足以支持每個結(jié)點的最小前提集。這個計算就是從前提的標(biāo)記開始，合并和傳播標(biāo)記。

接下來給出從Martins(1991)改編的一個例子。假定我們有如圖9-4的ATMS網(wǎng)絡(luò)。在這個網(wǎng)絡(luò)中，n1,n2,n4和n5是前提，并假定為真。這個相關(guān)性網(wǎng)絡(luò)還反映了這樣的關(guān)系:從前提n1,n2我們得出n3,從n3我們得出n7，從n4我們得出n7，從n4和n5我們得出n6,最后，我們從n6得出n7.基于邏輯的反繹推理38n1n2n4n5n3n6n7{{n1}}{{n2}}{{n4}}{{n5}}{{n1，n2}}{{n4，n5}}{{n1，n2}，{n4}，{n4，n5}}圖9-4ATMS對相關(guān)性網(wǎng)絡(luò)中結(jié)點的標(biāo)記基于邏輯的反繹推理39

圖9-5表示在圖9-4中前提依賴關(guān)系的超集/子集格。這個子集提供有效的方式讓我們直觀地觀察前提集的組合空間。這樣，如果我們懷疑某個前提假設(shè)是錯的，就能知道與這個前提相關(guān)的其他的支持前提子集。比如，圖9-4中的結(jié)點n3會被圖9-5中的{n1，n2}上面的所有集合支持。基于邏輯的反繹推理40{n1，n2，n4，n5}{n1，n2，n4}{n1，n2，n5}{n1，n2}{n1，n4，n5}{n2，n4，n5}{n1，n4}{n1，n5}{n2，n4}{n2，n5}{n4，n5}{n1}{n2}{n4}{n5}{}圖9-5圖9-4中網(wǎng)絡(luò)前提的格注：方框中的部分表示不一致的層次，改編自Martins(1991)基于邏輯的反繹推理41

ATMS的推理程序通過刪除已發(fā)現(xiàn)不一致的結(jié)點的前提集來消除矛盾。比如，假定我們修改圖9-4中所反映的推理情況，使n3成為矛盾點。因為n3的標(biāo)記是{n1，n2}，這個前提集就是不一致的。當(dāng)這個不一致性被發(fā)現(xiàn)以后，構(gòu)成圖9-5中{n1，n2}的超集的前提集都會被標(biāo)記為不一致，并從相關(guān)性網(wǎng)絡(luò)中刪除。這種情況下，一個支持n7的標(biāo)記就會被刪除。對矛盾刪除算法的詳細(xì)描述請參閱deKleer(1986)。

真值維護系統(tǒng)推理方面還有其他一些重要的成果。基于邏輯的真值維護系統(tǒng)(LTMS)是建立在McAllester(1987)的工作的基礎(chǔ)上的。命題之間的關(guān)系是由子句來表示的，這些字句可以用來演繹任何它們所描述的命題的真假。另外一個方法---多信念推理邏輯(MBR)，同ATMS推理程序很相似，只不過MBR的問題求解程序和真值維護系統(tǒng)合并成了一個單一的系統(tǒng)。MBR是建立在描述知識狀態(tài)的名叫SWM*的邏輯語言基礎(chǔ)上的。每一知識狀態(tài)由一個描述符對組成，第一個描述符知識庫，第二個描述符知識庫已知的不一致的前提集。推理中檢查不一致性的算法可以在Martins(1991)找到。關(guān)于真值維護系統(tǒng)請參見《TheEncyclopediaofArtificialIntelligence》(Shapiro1992).基于邏輯的反繹推理42(3)基于小模型的邏輯

在前面的章節(jié)中，我們用幾個模態(tài)操作符擴展了邏輯，引入這些邏輯符是為了對現(xiàn)實世界通常的情況進行推理，放松對于知識完備性的要求，希望能用一種更加靈活和可更正的觀點來看待現(xiàn)實世界。在本節(jié)中，我們將給出專門為兩種情況設(shè)計的邏輯：第一種情況是，給定一個斷言集合，其中只指定了為真的斷言；第二種情況是，由于問題求解的本質(zhì)，合取范式的集合通常是正確的。第一種情況下我們用封閉世界假設(shè)，對第二情況我們用限定(circumscription)。這兩種辦法我們都可以看成是在最小模型上的推理。

在2.3節(jié)中，我們看到，模型就是對所有變量賦值滿足謂詞表達式集合S的解釋。有很多種方式來定義最小模型的含義。我們定義最小模型為對所有變量賦值滿足謂詞表達式集合S的模型當(dāng)中沒有比它更小的那個模型?；谶壿嫷姆蠢[推理43最小模型思想產(chǎn)生的非常重要的原因是可以有無限多個謂詞來描述現(xiàn)實世界中的某種情景。比如，我們可以考慮有無數(shù)的謂詞來描述”農(nóng)夫-狼-山羊-卷心菜”問題(3.5節(jié)，練習(xí)2)的情景：船沒有緩慢下沉，河的兩岸離的很近，劃船就可以過去，風(fēng)和水流的因素不予考慮。當(dāng)我們描述一個問題時，我們不愿意去做過多無用的描述，我們只愿意去創(chuàng)建與問題相關(guān)并且是求解問題所必需的謂詞。

封閉世界假設(shè)是建立在世界的最小模型的基礎(chǔ)上的。求解所必須的謂詞都會被創(chuàng)建。封閉世界假設(shè)實現(xiàn)否定的語義。比如，我們知道一個學(xué)生是否是一個班級的注冊會員，我們可以去查看注冊數(shù)據(jù)庫，如果在數(shù)據(jù)庫(最小模型)中沒有明確地列出來，那么他或她就不是注冊成員。類似地，如果我們想知道兩個城市之間是否有直達的班機，我們會查看所有航班的列表。如果直達航班不在列表(最小模型)中，我們就會認(rèn)為不存在直達航班。基于邏輯的反繹推理44

封閉世界假設(shè)認(rèn)為如果我們的計算機系統(tǒng)中不含有p(X)為真，那么not(P(X))就為真。在14.4節(jié)中，將會看到封閉世界假設(shè)支持集Prolog推理。在14.4節(jié)中，我們還將看到在使用最小模型時所隱含的三個假設(shè)(公理)。這三個公理：名稱唯一性，即所有的原子都有唯一的名稱；封閉世界，關(guān)系的唯一實例是由現(xiàn)有的子句推出來的；域封閉，即域中的原子正好是模型中的原子。當(dāng)這三個條件滿足時，最小模型就是一個完整的基于邏輯的規(guī)范系統(tǒng)。如果公理不能滿足，就需要真值維護算法。

如果封閉世界需要給定組成模型的所有謂詞，限定(McCarthy1980，Lifschitz1984，McCarthy1986)只需要給定問題求解相關(guān)的那些謂詞。在限定中，公理是加到系統(tǒng)中去的，系統(tǒng)中知識庫的謂詞必須有最小解釋?！霸^詞”（有關(guān)問題定義的陳述謂詞）描述特定的謂詞是怎么被解釋的。就是說，它們劃界或者限定謂詞可能的解釋?；谶壿嫷姆蠢[推理45

McCarthy(1980)提出了限定的概念，并試著用來解決傳教士和食人者問題。這個問題要求問題求解器給出六個物體在一定的約束下用船過河的一系列的動作描述。McCarthy給出了問題相關(guān)的大量的情形，有些看起來有些可笑，卻是合理的。其中的一部分，如正在下沉的船或者風(fēng)的因素，在前面提到過。McCarthy加到問題描述中的限定公理會精確地描述加以限制。

作為限定的另外一個例子，看一下9.4節(jié)面向常識推理中的一個謂詞表達式：?Xbird(X)∧not(abnormal(X))→flies(X)在對鳥會飛這一屬性進行推理時，就可能會用到這一表達式.但是怎么限定謂詞abnormal的含義呢？是鳥不是企鵝，是翅膀沒斷掉，還是鳥沒有死？謂詞abnormal的含義是不定的。

基于邏輯的反繹推理46

在一階謂詞演算中用公理機制或原規(guī)則集來產(chǎn)生問題域的謂詞。原規(guī)則會使一些公式產(chǎn)生最小擴展。例如，如果B是包括全局知識K和有關(guān)謂詞P的領(lǐng)域知識A(P)的信念系統(tǒng)。我們就會認(rèn)為P是最小化的，即滿足謂詞P(aj)并且與K和A(P)相一致的原子aj最少。全局知識K連同A(P)和限定機制是用來用標(biāo)準(zhǔn)的一階謂詞演算來推出結(jié)論。這些結(jié)論接著再添加到信念系統(tǒng)B中。

假設(shè)是在8.4節(jié)的積木世界中，有表達式：isblock(A)∧isblock(B)∧isblock(C)斷言A、B和C是積木。限定謂詞isblock給出：

?X（isblock(X)←((X=A)∨(X=B)∨(X=C)))這個表達式斷定僅有的積木是A、B和C，即謂詞isblock指定的積木只有A、B和C。以類似的方式，謂詞：

isblock(A)∨isblock(B)可以被限定為：

?X（isblock(X)←((X=A)∨(X=B)))要了解更多的細(xì)節(jié)，包括用來推出結(jié)論的表示模式公理(schemaaxiom),請參基于邏輯的反繹推理47閱McCarthy(1980,第4節(jié))。

當(dāng)使用諸如abnormal的操作符時，限定很像封閉世界假設(shè)，因為他正好產(chǎn)生出abnormal能支持的那些變量綁定。但是限定代數(shù)允許我們在謂詞表示上擴展這個推理，因為，像我們剛才指出的，如果我們有謂詞P(X)∨Q(X),我們可以限定謂詞P和Q，或者它們兩個。于是，不同于封閉世界假設(shè)，限定允許我們在謂詞描述集合上描述可能的例示。

對限定邏輯進一步的研究可以在GeneserethandNilsson(1987)中找到。Lifschiz(1986)做出了重要貢獻，他提出了poit-wise限定，最小模型可以為特定的謂詞和它們可能的例示來執(zhí)行，而是對整個域。另外一個重要的貢獻是Perlis(1988)提出的關(guān)于一個缺少知識的主體的推理。更多討論可以參閱Shapiro(1992)?；谶壿嫷姆蠢[推理48（4）集合覆蓋和基于邏輯的反繹

像在本章概述中所提到的那樣，在反繹推理中，我們給定規(guī)則p→q和q的合理信念。然后我們希望在某種解釋下得到謂詞p為真。反繹推理是不可靠的，但因為q的原因，它又被稱為最佳解釋推理。在本節(jié)中，我們將討論反繹推理域中解釋的產(chǎn)生。

除了已經(jīng)提到的反繹推理的方法外，人工智能的研究者還用集合覆蓋和基于邏輯的分析的辦法。集合覆蓋的辦法試圖解釋這樣的作法，即對某些可解釋的假設(shè)采用可廢除的信念，因為它解釋了用別的方法不可解釋的集合。基于邏輯的辦法描述反繹的規(guī)則連同它們合法形式的定義。

集合覆蓋法定義一個反繹的解釋為謂詞的覆蓋，謂詞通過描述假設(shè)來描述現(xiàn)象。Reggiaetal.(1983)描述了一個基于因果關(guān)系R的覆蓋，R是集合{HypothesesXObservation}的子集。于是，現(xiàn)象集合S2的反繹解釋是足以引起S2的另一個假設(shè)集合S1。根據(jù)集合覆蓋法，最佳解釋是S2的最小集合覆蓋。這種方法的缺點是它把解釋約簡為原因假設(shè)(從S1中)的一個

基于邏輯的反繹推理49簡單列表。在有相關(guān)的或交互作用的原因假設(shè)的情況下，或者需要理解原因交互作用結(jié)構(gòu)或次序時，集合覆蓋模型就是不充分的。

基于邏輯的辦法則是建立在解釋的更高級的概念的基礎(chǔ)上。Levesque(1989)定義某些前面無法解釋的現(xiàn)象集合O為假設(shè)集H中與主體背景知識K一致的最小集合。假設(shè)H連同背景知識K必須能推導(dǎo)解釋出O。更形式化一點：

abduce(K，O)=H,當(dāng)且僅當(dāng)：1)K不能推導(dǎo)解釋出O；2)H∪K能推導(dǎo)解釋出O；3)不存在H的子集有屬性1、2和3。

需要指出的是，總的來說，可能會存在許多假設(shè)集，也就是說，對一個給定的現(xiàn)象O可能會有很多潛在的反繹解釋集?；谶壿嫷姆蠢[推理50

基于邏輯的反繹解釋的定義暗示了發(fā)現(xiàn)知識庫系統(tǒng)中的內(nèi)容的解釋有相應(yīng)的機制。如果可解釋的假設(shè)必須能推導(dǎo)解釋出現(xiàn)象O，則建立一個完整的解釋方式就是從O向后推理。像3.3節(jié)和8.2節(jié)那樣，我們可以從O的合取范式開始，從結(jié)果推回祖先。

這種后向式推理的辦法是很自然的，因為支持后向推理的條件可以被認(rèn)為是因果律，于是我們得出因果知識在產(chǎn)生解釋時起關(guān)鍵作用。這個模型是方便的，因為他很好地符合了人工智能界已有的經(jīng)驗：演繹的后向式推理和計算模型。

還有很多尋找反繹解釋的完整集合的方法?；诩僭O(shè)的真值維護系統(tǒng)ATMS(deKleer1986，9.2.3節(jié))包含了計算最小支持集的算法，支持集是能邏輯上推導(dǎo)出給定命題的命題(非公理)集合。為了找到一個現(xiàn)象集合的所有可能的翻譯解釋，我們在支持集上采用Cartesian產(chǎn)生式。基于邏輯的反繹推理51

基于邏輯的反繹具有簡單、精確、方便的優(yōu)點，他還有兩個相應(yīng)的缺點：高的計算復(fù)雜性和語義缺陷。Selman與Levesque(1990)發(fā)現(xiàn)反繹任務(wù)的復(fù)雜性與計算ATMS的支持集的復(fù)雜性相似。ATMS問題是NP-hard的標(biāo)準(zhǔn)證明依賴于指數(shù)各解的問題實例的存在性。Selman與Levesque通過詢問是否找到也是NP-hard的更小的解集合的方法來避免潛在的解的復(fù)雜性問題。給定Hom子句的知識庫，見14.2節(jié)，Selman與Levesque給出了一個算法，找到一個解釋的階為O(k*n)，其中K表示命題變量的數(shù)量，n表示文字出現(xiàn)的數(shù)目。但是，當(dāng)對要找的解釋的種類加以限制時，問題就又變?yōu)镹P-hard,即使是對Hom子句。

Selman與Levesque(1990)分析得出的令人感興趣的結(jié)論是這樣一個事實：對反繹任務(wù)增加一定的目標(biāo)或限制會使計算變得很難。從人類問題求解的觀點來看，這個增加復(fù)雜性有些讓人不解：人們通常假想對相關(guān)解釋的搜索進行進一步的限制會使任務(wù)便容易。在基于邏輯的模型中反繹任務(wù)變難的原因在于它只是對問題的額外的子句有影響，而對問題求解有用的額外的結(jié)構(gòu)沒有影響?；谶壿嫷姆蠢[推理52

基于邏輯的模型中解釋的發(fā)現(xiàn)是以找到具有一定邏輯屬性的假設(shè)集為特征的。這些屬性，包括與背景知識的一致性和能推導(dǎo)解釋出要解釋的現(xiàn)象，是指抓住解釋的必要條件：可解釋的假設(shè)集成為反繹解釋所必須滿足的最小條件。這種辦法的支持者認(rèn)為通過增加附加限制，這種辦法可以通過擴展來提供好的或合理的解釋的特征。

產(chǎn)生有質(zhì)量的解釋的一個簡單的策略是定義反繹的事實子句集，也就是說，候選假設(shè)必須選上。這個子句集允許搜索事先限定一些因素，這些因素在被選域中是潛在的原因。另外一個策略是增加評價和挑選解釋的選擇標(biāo)準(zhǔn)。人們已經(jīng)提出了很多不同的選擇標(biāo)準(zhǔn)，包括集合最小性，它是指當(dāng)兩個假設(shè)都是一致的且都能推導(dǎo)解釋出要解釋的現(xiàn)象時，如果第一個假設(shè)包含于第二個假設(shè)，則選擇第一個假設(shè)。簡單性標(biāo)準(zhǔn)優(yōu)先選擇簡單的假設(shè)集，即含有更少的通用假設(shè)的假設(shè)集(Levesque1989)?；谶壿嫷姆蠢[推理53

最小性和簡單性都可以看成是奧卡姆剃刀的應(yīng)用。不幸的是，集合最小性作為搜索修剪工具能力有限，它只去掉是已有解釋的超集的最終解釋。只是簡單性自身作為搜索選擇標(biāo)準(zhǔn)有效性也值得懷疑。建立這樣的例子是不難的，需要大的解釋集的解釋優(yōu)先于簡單卻淺顯的解釋集。實際上，復(fù)雜的因果機制通常需要大量的假設(shè)集，但是，這種因果機制的反繹可以被證實，尤其是當(dāng)這個機制的某個關(guān)鍵元素的存在性已經(jīng)被現(xiàn)象證實的情況下。

解釋選擇的另外兩種機制也很令人感興趣，因為它們不僅考慮了假設(shè)集的屬性，還考慮了證明過程的屬性。第一個機制，基于代價的反繹對于潛在的假設(shè)和規(guī)則賦一個代價值。解釋的總代價是用假設(shè)的代價加上用來反繹假設(shè)的代價計算出來的。競爭假設(shè)集然后根據(jù)代價來進行比較。這種方案附帶的自然的啟發(fā)是概率(CharniakandShimony1990)。假設(shè)的代價高代表不太可能的事件，規(guī)則的代價高代表不太可能的因果機制?；诖鷥r的度量可以與最小代價搜索算法結(jié)合起來，如最佳搜索算法，參見第4章，這種算法大大降低了任務(wù)的計算復(fù)雜性。基于邏輯的反繹推理54

第二個機制，基于一致性選擇(coherence-basedselection)，當(dāng)要解釋的不是一個命題而是命題集合時尤其適用。Ng與Mooney(1990)認(rèn)為在分析自然語言文本過程中選擇解釋時一致性度量比簡單性要重要。他們把一致性定義為證據(jù)圖的一個屬性，圖中任意對象之間有更多連接和更少分開的部分的解釋是更一致的。一致性標(biāo)準(zhǔn)是基于這樣一個啟發(fā)式的假設(shè)：我們要解釋的是一個單一的事件或者有多方面的動作。自然語言理解中一致性度量(coherencemetric)的證明是基于Gricean幸運(felicity)條件，即說話者的職責(zé)是要一致和相關(guān)(pertinent)(Grice1975)。我們不難把他們的論點擴展到其他情形中去。例如在診斷中，包含初始要解釋的事情的現(xiàn)象被綜合在一起，因為它們被認(rèn)為與同一個潛在的故障或失敗機制相關(guān)。

在第一節(jié)中，我們討論了傳統(tǒng)邏輯的擴展，以支持不確定或缺少數(shù)據(jù)的推理。我們接下來對討論非邏輯的方法在不確定情況下進行推理，包括Stanford確信度、模糊集推理和Dempster-Shafer證據(jù)理論?；谶壿嫷姆蠢[推理559.1節(jié)中基于邏輯的辦法對許多應(yīng)用尤其是專家系統(tǒng)來說非常麻煩，難于處理。許多早期的專家系統(tǒng)(像PROSPECTOR)試圖采用另外一種辦法，即9.3節(jié)介紹的用貝葉斯方法進行反繹推理。這種辦法的局限性在于對獨立性的要求，對統(tǒng)計數(shù)據(jù)不斷地更新以及進行隨機推理所需的演算。另一種減輕這些限制的推理機制在斯坦福大學(xué)用于開發(fā)早期的專家系統(tǒng)，包括MY-CIN(BuchananandShortliffe1984)。

當(dāng)人類專家在用啟發(fā)式的知識進行推理時，他們能夠給出對結(jié)論的充分有效的估計。人們用類似“很有可能”、“不太可能”或“可能的”這樣的詞語來度量結(jié)論的確信度。這些度量顯然沒有基于對概率的精確分析，而是他們自身從對問題推理的經(jīng)驗中得出啟發(fā)式信息。在9.2節(jié)中將介紹三種反繹推理的方法理論，即Stanford確信度理論、模糊推理和Dempster-Shafer證據(jù)理論。在9.3節(jié)中用隨機的辦法來進行不確定性推理。反繹：邏輯之外的辦法56(1)Stanford確信度代數(shù)

Stanford確信度理論是建立在很多現(xiàn)象的基礎(chǔ)上的。首先在傳統(tǒng)的概率論中，一個關(guān)系的支持它的確信度和不支持它的確信度的和加起來為1。但是，現(xiàn)實中常有這種情況---專家可能對某個關(guān)系為真的確信度為0.7，對于關(guān)系為假的情況則毫無概念，不置可否。另外一個支撐確信度理論的假設(shè)是規(guī)則中含有的知識遠(yuǎn)比計算確信度的代數(shù)重要。確信度的度量要與專家對結(jié)論的非形式化的估計相一致，比如“它可能為真”、“它幾乎為真”、或者“它不太可能”。Stanford確信度理論對建立確信度的度量做了一些簡單的假定，在推理時也有一些簡單的規(guī)則來合并這些確信度。第一個假定是把一個關(guān)系的支持度和不支持度分開：

MB(H|E)稱為給定證據(jù)E時假設(shè)H的可信度量。MD(H|E)稱為給定證據(jù)E時假設(shè)H的不可信度量?，F(xiàn)在或者

當(dāng)MD(H|E)=0時1>MB(H|E)>0，或者

當(dāng)MB(H|E)=0時1>MD(H|E)>0反繹：邏輯之外的辦法57這兩個度量互相限制，給定的證據(jù)對于特定的假設(shè)或者支持，或者不支持，這是確定性理論同概率論的一個重要不同。一旦可信度量和不可信度量的聯(lián)系建立起來，它們就能連接在一起，這是通過下面的公式實現(xiàn)的：CF(H|E)=MB(H|E)-MD(H|E)

當(dāng)確信度因子(CF)接近于1時，證據(jù)傾向于支持假設(shè)，當(dāng)CF接近于-1時，證據(jù)傾向于不支持假設(shè)，當(dāng)CF在大約為0時，表明只有極少的證據(jù)支持或者不支持假設(shè)，或者支持或者不支持假設(shè)的證據(jù)大體相當(dāng)。

當(dāng)專家要建一個規(guī)則庫時，它們必須為每條規(guī)則確定一個CF。CF反映了專家對這條規(guī)則的可信賴程度的信心。確信度的度量可以被用調(diào)整系統(tǒng)的性能，雖然度量的小的改變對整個系統(tǒng)的總體運行情況給予沒有多大影響。確信度的度量的這個作用驗證了“知識產(chǎn)生力量”這句話，也就是說，完整的知識能對正確的診斷提供最好的支持。反繹：邏輯之外的辦法58每條規(guī)則的前提由and、or和一些事實組成。當(dāng)用到產(chǎn)生式時，前提中每個條件的確信度就會按照如下方式被合并成對整個前提的確信度。對規(guī)則的前提P1和P2:

CF(P1andP2)=MIN(CF(P1),CF(P2))CF(P1orP2)=MAX(CF(P1),CF(P2))用上面的規(guī)則合并后的前提的CF接著乘上規(guī)則自身的CF就得到規(guī)則結(jié)論的CF。例如，知識庫中的規(guī)則:

(P1andP2)orP3→R1(0.7)andR2(0.3)其中P1、P2和P3是前提，R1和R2是規(guī)則的結(jié)論，確信度CF分別為0.7和0.3。如果規(guī)則所有的前提是完全正確的，當(dāng)這條規(guī)則被用來代表專家對結(jié)論的確信度時，這些數(shù)字就會附加到規(guī)則上。如果當(dāng)前系統(tǒng)已經(jīng)產(chǎn)生了P1、P2和P3，確信度CF分別是0.6、0.4和0.2，R1和R2這時的確信度CF就是0.28和0.12。下面是計算過程：反繹：邏輯之外的辦法59CF(P1(0.6)andP2(0.4))=MIN(0.6，0.4)CF((0.4)orP3(0.2))=MAX(0.4,0.2)=0.4R1的確信度CF是0.7，所以R1添加到特例知識集中去的時候的確信度CF為(0.7)×(0.4)=0.28R2的確信度是0.3，所以R2添加到特例知識集中去的確信度CF為（0.3）×（0.4）=0.12.

當(dāng)兩個或多個規(guī)則支持同一結(jié)論R時，怎么來合并這么多個CF呢？這個度量生成規(guī)則反映了確信度理論與概率論中合并獨立證據(jù)時度量相乘的相似之處。循環(huán)運用這條規(guī)則，我們可以合并支持結(jié)論R的任意數(shù)目的規(guī)則。假定此時結(jié)論R的當(dāng)前的確定度為CF（R1），以前沒用到的規(guī)則也得出結(jié)論R，確信度為CF（R2）。那么R的新確信度CF用下面的公式計算：反繹：邏輯之外的辦法60當(dāng)CF(R1)和CF(R2)都為正時CF(R1)+CF(R2)-(CF(R1)×CF(R2))當(dāng)CF(R1)和CF(R2)都為負(fù)時CF(R1)+CF(R2)+(CF(R1)×CF(R2))其他情況如下：

其中符號|X|代表X的絕對值。

除了容易計算外，這些合并規(guī)則還有其他一些好的特性。首先，計算出來的CF總是在1和-1之間。第二，在合并符號相反的CF時，它們互相消弱，這是我們想要得到的。第三，合并后的CF是一個單遞增(遞減)的函數(shù)，這也是我們合并證據(jù)時所期望的。

最后，Stanford確信度代數(shù)中對確信度的度量是人們對于癥狀或起因的概率值得主觀估計。像在5.4節(jié)中指出的那樣，在貝葉斯方法中，如果A、B和C都對D有影響，當(dāng)我們要對D進行推理時，我們需要區(qū)分和適當(dāng)?shù)睾喜⑺械南闰灪秃篁灨怕?，包括P(D)、P(D|A)、P(D|B)、P(D|C)、P(D|AB)，等等。Stanford確信度代數(shù)允許把所有的關(guān)系合成一個確信度反繹：邏輯之外的辦法61CF來附加到規(guī)則上，即ifAandBandCthenD(CF)。這種簡化的辦法更好地反映了人類專家是怎么合并和傳播信念的。

確信度理論可能會被認(rèn)為過于特殊。雖然它有形式代數(shù)定義，但是確信度度量的含義與形式概論不完全一致。另一方面，確信度理論并不是用來做“正確”的推理的，而是能讓專家系統(tǒng)在解決問題時合并確信度使得推理繼續(xù)下去的“潤滑劑”。確信度的度量有些特殊，同樣，人類專家對自己結(jié)論的確信度也是近似的、啟發(fā)式的和非形式的。當(dāng)MYCIN運行時，確信度被用來在啟發(fā)式搜索中給出目標(biāo)的優(yōu)先級，在一個目標(biāo)不用再被考慮時給出終止點。但即是確信度被用來維持程序的運行和搜集信息，系統(tǒng)的性能好壞仍然主要取決于規(guī)則的質(zhì)量。反繹：邏輯之外的辦法62(2)模糊集推理

使用形式集合論時，有兩個重要假定。第一個是關(guān)于集合成員關(guān)系：對于任意一個元素和在某個全域中的一個集合來說，這個元素或者在這個集合中，或者在這個集合的補集中。第二個假定稱為排中律，是指一個元素不能既屬于一個集合，有屬于這個集合的補。LotfiZadeh的模糊集理論沖破了這兩個假定。事實上，在模糊集理論的觀點看來，傳統(tǒng)集合論的集合和推理被稱為干脆的。Zadeh的主要思想(Zadeh1983)是：雖然概率論是對信息的隨機性進行度量的，但是用它來對信息的含義進行度量是不恰當(dāng)?shù)摹嶋H上，我們運用英語單詞和詞組時經(jīng)常混淆，這應(yīng)該是不清楚(含糊)而不是隨機性。對于分析語言結(jié)構(gòu)這是很重要的一點，在確定產(chǎn)生式規(guī)則的確定性時也同樣重要。就像概率論度量隨機性一樣，Zadeh提出了可能性理論(possibilitytheory)來度量模糊程度。反繹：邏輯之外的辦法63Zadeh用量化的方式來表達不精確性，為此他引入了取值在0和1之間的集合隸屬函數(shù)。模糊集的概念可以描述如下：另S為集合，s是這個集合的一個元素。S的模糊子集F由隸屬函數(shù)mF(s)來定義，這個函數(shù)度量了s屬于F的“程度”。

圖9-6給出了模糊集的一個例子，S是正整數(shù)集合，稱為小整數(shù)集合的F是S的模糊子集。于是不同的整數(shù)對于小整數(shù)集合的模糊隸屬度有一個“可能性”分布：mF(1)=1.0，mF(2)=1.0，mF(3)=0.9，mF(4)=0.8……，mF(50)=0.001，等等。對于語句正整數(shù)X是一個小整數(shù)，mF創(chuàng)建對于所有正整數(shù)(S)的一個可能性分布。123…1圖9-6“小整數(shù)”的模糊集表示反繹：邏輯之外的辦法64模糊集理論并不關(guān)心這些可能性分布是怎么創(chuàng)建的，而是關(guān)心用什么規(guī)則來計算合并含有模糊變量的表達式的可能性。所以，它包含合并含有模糊變量的表達式的可能性的值的規(guī)則。對于表達式中的or、and和not，合并規(guī)則與Stanford確定度代數(shù)相似：參見9.2.1節(jié)。

圖9-6所示，對于代表小整數(shù)的模糊集，每個屬于這個集合的整數(shù)都有相對應(yīng)的置信度。對傳統(tǒng)邏輯的“干脆”集來說，集合中元素的隸屬值或者是1或者是0.圖9-7給出了男性對于矮、中等、高這三個概念的隸屬函數(shù)。需要指出的是，每個人可以屬于不止一個集合，例如，一個5英尺9英寸的男性既屬于中等集合，又屬于高的男性集合。14’4’6’’5’5’6’’6’6’6’’圖9-7矮、中等和高個男性集合的模糊集表示反繹：邏輯之外的辦法65

接下來求解一個問題來演示一下模糊集的合并和傳播規(guī)則，即對一個倒立擺怎樣控制的問題，它現(xiàn)在成了模糊集著作中很經(jīng)典的問題。圖9-8給出了一個倒立擺，我們希望擺能保持平衡，并指向上方。我們通過移動系統(tǒng)底部來抵消作用于擺的重力的辦法來保持系統(tǒng)的平衡。有一組微分方程可以使擺保持平衡(Ross1995)。用模糊集方法來控制擺系統(tǒng)的優(yōu)點在于生成的算法可以有效和實時地控制系統(tǒng)。我們接下來將討論這種控制機制。

θ圖9-8倒立擺，角度θ

和dθ

/dt的輸入值反繹：邏輯之外的辦法66

我們用兩個維度來刻畫擺問題，以簡化這個問題?？刂瞥绦蛴袃蓚€輸入量度，在圖9-8中我們可以看到：第一個角度是θ，是擺與垂直中線的偏移量，第二個是dθ

/dt，是鐘擺移動的速度。這兩個量度都是垂直線的右邊為正，左邊為負(fù)。系統(tǒng)每次反復(fù)，這兩個量都要提供給模糊控制程序。控制程序的輸出是對系統(tǒng)的地步給出一個移動和一個方向。移動和方向的指示是為了保持鐘擺的平衡。

為說明控制程序的動作，用模糊集描述求解過程。描述鐘擺狀態(tài)的數(shù)據(jù)θ和dθ

/dt被解釋成模糊量度，如圖9-9所示，并送到模糊規(guī)則集。這一步通過稱為模糊聯(lián)想矩陣(FAM)的結(jié)構(gòu)可以有效地實現(xiàn)，如圖9-12所示，矩陣中輸入/輸出的關(guān)系直接用編碼表示了出來。這里的規(guī)則并不像傳統(tǒng)的基于規(guī)則的問題求解那樣鏈在一起。而是所有匹配的規(guī)則結(jié)合在一起，它們的結(jié)果合并起來。如圖9-10所示，這個結(jié)果通常表示模糊輸出參數(shù)空間中的一個區(qū)間，然后這個結(jié)果再經(jīng)過模糊反變換，返回控制響應(yīng)。需要指出的是，開始的輸入和最終的輸出都是純數(shù)字。它們是作為輸入的某些監(jiān)視器的準(zhǔn)確讀數(shù)和作為輸出的對控制的精確指示。反繹：邏輯之外的辦法67-2-10121Z模糊區(qū)間a)θ的模糊區(qū)間

X1NP-5-4-3-2-10123451ZNP模糊區(qū)間b)dθ

/dt的模糊區(qū)間

圖9-9輸入值的模糊區(qū)間X2反繹：邏輯之外的辦法68-24-20-16-12-8-404812162024ZNBNPPBU圖9-10輸出值U的模糊區(qū)間，U指出擺底部的移動1反繹：邏輯之外的辦法69-2-1012NZP10.5Xi(θ

)=1-5-4-3-2-10123450.80.2X2(dθ/dt)=-4a)b)圖9-11輸入值x1=1、X2=-4的模糊化反繹：邏輯之外的辦法70

接下來討論輸入值θ和dθ/dt的模糊區(qū)間。這個例子簡化了一些情形，比如，輸入一個輸入值模糊區(qū)間中的數(shù)，但顯示整個程序的過程和對控制器的響應(yīng)。輸入值θ被劃分成三個區(qū)間：負(fù)、零和正，如圖9-9a所示，θ在-2-+2弧度的區(qū)間取值。圖9-9b給出了第二個輸入值dθ/dt被劃分成的三個區(qū)間，同樣是負(fù)、零和正，取值區(qū)間是-5-+5度/秒。

X2X1PZNPZNPBPZPZNZNNB圖9-12倒擺問題的模糊聯(lián)想矩陣(FAM)。

輸入值在左側(cè)和頂部反繹：邏輯之外的辦法71在圖9-10表示輸出區(qū)間的取值，我們用中間的五個區(qū)間，大負(fù)、負(fù)、零、正和大正。度量值介于-24-+24之間，表示每個響應(yīng)的移動和方向。

現(xiàn)在假定模擬開始，第一次送給控制器的值是θ=1和dθ/dt=-4.圖9-11反映了對這些輸入量的模糊變換。對于每種情況，輸入值作用于兩個模糊輸入空間中的兩個區(qū)間。對于θ，對零的可能性度量為0.5，對正的可能性度量為0.5。對于dθ/dt，對負(fù)的可能性度量為0.8，對零的可能性度量為0.2。

圖9-12給出了針對這個問題的模糊聯(lián)想矩陣的簡化形式。表的左邊表示輸入θ，或者X1，上邊表示輸入dθ/dt，或者X2。FAM表右下角的值表示輸出值。例如，如果θ是正，并且dθ/dt是負(fù)，F(xiàn)AM返回給擺系統(tǒng)的移動值是零。需要指出的是響應(yīng)必須由圖9-10對輸入?yún)^(qū)間零進行模糊變換。

在這個例子中，因為每個輸入值都處在輸入空間的兩個區(qū)間上，所以必須用到四個規(guī)則。像前面指出的那樣，模糊集的合并規(guī)則與Stanford確信度代數(shù)相似。事實上，Zadeh(Bushanan和Shortliff1984)是第一個(歷史上)提出模糊推理代數(shù)的合并規(guī)則的人。如果兩個前提的度量用AND來連接，則度量中最小的那個被作為這條規(guī)則的度量。如果兩個前提用來OR連接，則反繹：邏輯之外的辦法72選度量中最大的。

在我們的例子中，所有的前提用AND來連接，所以將之中的度量作為規(guī)則結(jié)果的度量：IFX1=PANDX2=ZTHENU=Pmin(0.5,0.2)=0.2PIFX1=PANDX2=NTHENU=Zmin(0.5,0.8)=0.5ZIFX1=ZANDX2=ZTHENU=Zmin(0.5,0.2)=0.2ZIFX1=ZANDX2=NTHENU=Nmin(0.5,0.8)=0.5N

接下來進行結(jié)果的合并。在我們的例子中，按照規(guī)則集的結(jié)果所示畫出圖9-10中的聯(lián)合區(qū)域。有許多中模糊反變換的技術(shù)(Ross1995)。我們選擇最常用的一種:質(zhì)心法。這種辦法是把聯(lián)合區(qū)域的質(zhì)心作為控制程序輸出給擺的最終結(jié)果。聯(lián)合區(qū)域的質(zhì)心如圖9-13所示。在輸出作用于系統(tǒng)之后，反繹：邏輯之外的辦法73θ和dθ/dt又被抽樣，控制循環(huán)又重復(fù)下去。

在描述模糊推理系統(tǒng)時，還有很多問題沒有提到，包括屬于收斂過程的擺動的模式和最佳抽樣率的選取。模糊系統(tǒng)尤其是在控制領(lǐng)域給我們提供了一個強大有效的工具來處理度量不準(zhǔn)確的問題。-16-12-8-40481216NZP

1.00.50.2Mua)模糊結(jié)果-16016Mu1.00.50.2U(0)=-2b)模糊區(qū)間圖9-13模糊結(jié)果和他們的區(qū)間注：這個區(qū)間的質(zhì)心(-2)是干脆的輸出反繹：邏輯之外的辦法74Dempster-Shafer證據(jù)理論

到現(xiàn)在我們討論的不確定條件下的推理技術(shù)是給定證據(jù)集，我們賦給單個命題可能起因或者信任程度的估計值。用概率的辦法來求解不確定問題的一個局限是它們用一個單一的數(shù)字來度量一個可能很復(fù)雜的情形。通常，不確定性來源于缺少證據(jù)的合并、啟發(fā)式規(guī)則固有的局限和人們知識的局限性。

另外一種辦法稱為Dempster-Shafer證據(jù)理論，考慮的是命題集，并賦給區(qū)間值[belief、plausibility]，每個命題的可信度(beliefmeasure)必須在這個區(qū)間內(nèi)。這個可信度表示為bel，取值從0到1，取值為0表示沒有證據(jù)支持這組命題，取值為1表示完全確定。命題p的似真性pl(p)是這樣定義的：pl(p)=1-bel(not(p))于是，似真性也是從0到1取值，反映了not(p)的證據(jù)是怎么與信任p的可能性相聯(lián)系的。如果我們對not(p)有確定的證據(jù)，那么bel(not(p))就為1，pl(p)就為0.對bel(p)的唯一可能的值也是0.反繹：邏輯之外的辦法75假定我們有兩個競爭的假設(shè)(competinghypotheses)h1和h2。當(dāng)我們沒有支持每個假設(shè)的信息時，它們的信任度/似真性在[0,1]上取值。當(dāng)我們有了證據(jù)，我們希望區(qū)間縮小，表示對于假設(shè)支持度增加。在貝葉斯定理中，我們開始可能(這是沒有證據(jù))把先驗概率等分到兩個假設(shè)中去。即每個P(h1)=0.5.Dempster-Shafer明確說明開始時沒有證據(jù)，另一方面，貝葉斯方法則不管我們有多少數(shù)據(jù)也能得出相同的概率值。這樣，在基于收集到的證據(jù)數(shù)量來做結(jié)論的時候，Dempster-Shafer證據(jù)理論就非常有用。

總結(jié)一下，Dempster和Shafer通過區(qū)分不確定和不知道來解決度量確定程度的問題。在概率論中，我們必須對假設(shè)h用一個數(shù)字給出它的概率，p(h)。Dempster和Shafer指出概率論辦法的問題在于我們并不一定總是知道概率的值，因此我們給出的p(h)可能沒有經(jīng)過證實。Dempster-Shafer信念函數(shù)能滿足概率論不能滿足的問題，也就是說，當(dāng)所有的概率都給定時，它就成為概率論了。信念函數(shù)允許我們在缺少準(zhǔn)確的概率的情況下，用知識對事件的概率賦值。反繹：邏輯之外的辦法76

Dempster-Shafer理論的基礎(chǔ)思想有兩點：第一，是從相關(guān)問題的主觀概率來得到一個問題可信度的思想；第二，當(dāng)基于相互獨立的證據(jù)時，合并可信度的規(guī)則的使用。合并規(guī)則是由Dempster(1968)最早提出來的。下面我們給出Dempster-Shafer推理的一個不很正式的例子，然后給出規(guī)則。最后，把規(guī)則運用到一個更現(xiàn)實的情況下。

假定我對朋友Melissa的可信賴程度有一個主觀的概率。她是可信賴的可能性為0.9，不可信賴的可能性為0.1。假設(shè)Melissa告訴我，我的計算機被別人侵入了。如果Melissa是可信賴的，則這是真的，但如果她是不可信賴的，這句話則不一定為假。所以Melissa一個人的陳述證實我的計算機被侵入的可信度為0.9，沒有被侵入的可信度為0.0。0.0的可信度與0.0的概率不同，它并不意味著我確信計算機沒有被侵入，而只是表明Melissa的陳述沒有給我理由來相信計算機沒被侵入。在這種情況下，似真性pl為：pl(computer_broken_into)=1-bel(not(computer_broken_into))=1-0.0反繹：邏輯之外的辦法77我對Melissa的可信度為[0.9,1.0]。需要指出的是仍然沒有證據(jù)表明我的計算機沒被侵入。

我們接下來討論Dempster理論中合并證據(jù)的規(guī)則。假設(shè)我的朋友Bill也告訴我，我的計算機被侵入了。假定Bill可信賴的概率為0.8,不可信賴的概率為0.2。我還必須假定Melissa和Bill的有關(guān)計算機的陳述相互獨立，也就是說，他們分別有各自的原因來告訴我這件事。事件Bill是可信賴的必須獨立于事件Melissa也是可信賴的。Melissa和Bill都是可信賴的概率是0.72，都是不可信賴的概率是0.02.至少有一人是可信賴的概率是1-0.02，即0.98。因為他們兩人都說我的計算機被侵入，并且至少有一人是可信賴的概率是0.98，我將給事件計算機被侵入的信任度賦值為[0.98,1.0]。

假設(shè)Melissa和Bill的陳述不一致：Melissa說我的計算機被侵入了，Bill說沒有侵入。在這種情況下，他們不可能都是可信賴的?；蛘咚麄兌际遣豢尚刨嚨模蛘咧挥幸蝗耸强尚刨嚨?。只有Melissa是可信賴的先驗概率是0.9×(1-0.8)=0.18,只有Bill是可信賴的先驗概率0.8×(1-0.9)=0.08,兩個人都不可信賴的先驗概率是0.2×0.1=0.02。給定至少有一人是不可信賴的概反繹：邏輯之外的辦法78率為(0.18+0.08+0.02)=0.28，我們還可以算出只有Melissa是可信賴的后驗概率是0.08/0.28=0.286，這時計算機沒被侵入。

我們剛才運用了Dempster規(guī)則來合并信念。當(dāng)Melissa和Bill都說計算機被侵入時，總結(jié)一下支持侵入的三種情形：Melissa和Bill都是可信賴的；只有Bill是可信賴的；只有Melissa是可信賴的。信念0.98是這幾種支持情形的和。第二次運用Demp