人工智能推理技術(shù)-文檔資料

1、Artificial Intelligence第第7 7章、基本的推理技術(shù)章、基本的推理技術(shù) 推理技術(shù)概述 基于規(guī)則的演繹推理正向演繹推理逆向演繹推理雙向演繹推理 不確定性推理概率推理Artificial Intelligence人工智能是用計(jì)算機(jī)來模擬人的智能，就是用能在計(jì)算機(jī)上實(shí)現(xiàn)的技術(shù)和方法來模擬人的思維規(guī)律和過程。 1) 在確定知識(shí)表達(dá)方法后，就可以把知識(shí)表示出來并存儲(chǔ)到計(jì)算機(jī)中。 2) 然后, 利用知識(shí)進(jìn)行推理以求得問題的解. 利用知識(shí)進(jìn)行推理是知識(shí)利用的基礎(chǔ)。各種人工智能應(yīng)用領(lǐng)域如專家系統(tǒng)、智能機(jī)器人、模式識(shí)別、自然語言理解等都是利用知識(shí)進(jìn)行廣義問題求解的智能系統(tǒng).Artifici

2、al Intelligence7.1 推理技術(shù)概述 -1. 推理的概念與類型 推理是人類求解問題的主要思維方法. 所謂推理就是按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程。推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。人類的智能活動(dòng)有多種思維方式，人工智能作為對(duì)人類智能的模擬，相應(yīng)地也有多種推理方式。 Artificial Intelligence1. 演繹推理、歸納推理、默認(rèn)推理(1). 演繹推理：演繹推理是從全稱判斷推出特稱判斷或單稱判斷的過程，即從一般到個(gè)別的推理。最常用的形式是三段論法。 例如： 1）所有的推理系統(tǒng)都是智能系統(tǒng)； 2）專家系統(tǒng)是推理系統(tǒng)； 3）所以，專家系統(tǒng)是智能系統(tǒng)。(2).歸納推理

3、: 是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理過程。(3). 默認(rèn)推理：默認(rèn)推理又稱缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。Artificial Intelligence2、確定性推理、不確定性推理 如果按推理時(shí)所用的知識(shí)的確定性來分，推理可分為確定性推理與不確定性推理。 （1）確定性推理（精確推理）。如果在推理中所用的知識(shí)都是精確的，即可以把知識(shí)表示成必然的因果關(guān)系，然后進(jìn)行邏輯推理，推理的結(jié)論或者為真，或者為假，這種推理就稱為確定性推理。（如歸結(jié)反演、基于規(guī)則的演繹系統(tǒng)等） （2）不確定性推理(不精確推理)。在人類知識(shí)中，有相當(dāng)一部分

4、屬于人們的主觀判斷，是不精確的和含糊的。由這些知識(shí)歸納出來的推理規(guī)則往往是不確定的?；谶@種不確定的推理規(guī)則進(jìn)行推理，形成的結(jié)論也是不確定的，這種推理稱為不確定推理。 (在專家系統(tǒng)中主要使用的方法)。Artificial Intelligence3、單調(diào)推理、非單調(diào)推理 如果按推理過程中推出的結(jié)論是否單調(diào)增加，或者說推出的結(jié)論是否越來越接近最終目標(biāo)來劃分，推理又可分為單調(diào)推理與非單調(diào)推理。 （1）單調(diào)推理。是指在推理過程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論呈單調(diào)增加的趨勢(shì)，并且越來越接近最終目標(biāo)。(演繹推理是單調(diào)推理。) （2）非單調(diào)推理。是指在推理過程中隨著推理的向前推進(jìn)及新知識(shí)的

5、加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。(一般是在知識(shí)不完全的情況下進(jìn)行的)Artificial Intelligence4、啟發(fā)式推理、非啟發(fā)式推理 如果按推理中是否運(yùn)用與問題有關(guān)的啟發(fā)性知識(shí)，推理可分為啟發(fā)式推理和非啟發(fā)式推理。 （1）啟發(fā)式推理：如果在推理過程中，運(yùn)用與問題有關(guān)的啟發(fā)性知識(shí)，如解決問題的策略、技巧及經(jīng)驗(yàn)等，以加快推理過程，提高搜索效率，這種推理過程稱為啟發(fā)式推理。如A、A*等算法。 （2）非啟發(fā)式推理。如果在推理過程中，不運(yùn)用啟發(fā)性知識(shí)，只按照一般的控制邏輯進(jìn)行推理，這種推理過程稱為非啟發(fā)式推理。(推理效率較低，容易出現(xiàn)“組合爆

6、炸”問題。)Artificial Intelligence - 推理的控制策略 主要是指推理方向的選擇、推理時(shí)所用的搜索策略及沖突解決策略等。一般推理的控制策略與知識(shí)表達(dá)方法有關(guān) (產(chǎn)生式系統(tǒng)) . 1、推理方向：用于確定推理的驅(qū)動(dòng)方式。分為正向推理(由已知事實(shí)出發(fā))、反向推理(以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn))和正反向混合推理(正向推理和反向推理相結(jié)合).系統(tǒng)組成: 知識(shí)庫(kù)（KB）+初始事實(shí)和中間結(jié)果的數(shù)據(jù)庫(kù)（DB）+ 推理機(jī) 2、搜索策略:推理時(shí)要反復(fù)用到知識(shí)庫(kù)中的規(guī)則，而知識(shí)庫(kù)中的規(guī)則又很多，這樣就存在著如何在知識(shí)庫(kù)中尋找可用規(guī)則的問題(代價(jià)小,解好). 可以采用各種搜索策略有效地控制規(guī)則的選取

7、.Artificial Intelligence3、沖突解決策略 在推理過程中，系統(tǒng)要不斷地用數(shù)據(jù)庫(kù)中的事實(shí)與知識(shí)庫(kù)中的規(guī)則進(jìn)行匹配，當(dāng)有一個(gè)以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí)，就需要有一種策略來決定首先使用哪一條規(guī)則，這就是沖突解決策略。沖突解決策略實(shí)際上就是確定規(guī)則的啟用順序。 （1）專一性排序(條件部分更具體的規(guī)則) （2）規(guī)則排序(規(guī)則編排順序) （3）數(shù)據(jù)排序(所有條件按優(yōu)先級(jí)次序編排起來) （4）就近排序(最近使用的規(guī)則優(yōu)先) （5）上下文限制(在某種上下文條件下) （6）按匹配度排序(計(jì)算這兩個(gè)模式的相似程度) （7）按條件個(gè)數(shù)排序(條件少的優(yōu)先)Artificial Int

8、elligence72 基于規(guī)則的演繹推理 許多AI系統(tǒng)中所用到的知識(shí)一般是由蘊(yùn)含式直接表示的，但在歸結(jié)反演中，必須首先將它們轉(zhuǎn)化為子句的形式，所以這種推理是比較低效的。 基于規(guī)則的演繹推理則是直接的推理方法。它把有關(guān)問題的知識(shí)和信息劃分為規(guī)則與事實(shí)兩種類型。規(guī)則由包含蘊(yùn)含形式的表達(dá)式表示，事實(shí)由無蘊(yùn)含形式的表達(dá)式表示，并畫出相應(yīng)的與或圖，然后通過規(guī)則進(jìn)行演繹推理。 可分為正向、反向和正反向演繹推理。在正向推理中，作為F規(guī)則用的蘊(yùn)含式對(duì)事實(shí)的總數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算，直至得到該目標(biāo)公式的一個(gè)終止條件為止；在反向推理中，作為B規(guī)則用的蘊(yùn)含式對(duì)目標(biāo)的總數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算，直至得到包含這些事實(shí)的一個(gè)終止

9、條件為止；在雙向推理中，分別從兩個(gè)方向應(yīng)用不同的規(guī)則（F和B）進(jìn)行操作運(yùn)算。 Artificial Intelligence721 正向演繹推理 正向演繹推理屬于正向推理，它是從已知事實(shí)出發(fā)，反復(fù)嘗試所有可利用的規(guī)則（F規(guī)則）進(jìn)行演繹推理，直到得到某個(gè)目標(biāo)公式的一個(gè)終止條件為止。 1、事實(shí)表達(dá)式及其與或圖表示 正向演繹要求事實(shí)用不包含蘊(yùn)含符號(hào)“”的與或形表示。把一個(gè)表達(dá)式轉(zhuǎn)化為標(biāo)準(zhǔn)的與或形的步驟如下： （1）利用等價(jià)式PQ與PQ消去蘊(yùn)含符“”。 （2）把否定符號(hào)“”移到每個(gè)謂詞符號(hào)的前面。 （3）變量標(biāo)準(zhǔn)化，即重新命名變量，使不同量詞約束的變量有不同的名字。 （4）引入Skolem函數(shù)消去存在

10、量詞。 （5）將公式化為前束形。 （6）略去全稱量詞（默認(rèn)變量是全稱量詞量化的）。 （7）重新命名變量，使同一變量不出現(xiàn)在不同的主要合取式中。Artificial Intelligence例如 ：有如下的表達(dá)式 （ x x）（）（ y y）QQ（y y，x x） （R R（y y） P P（y y） S S（x x，y y） 可將其轉(zhuǎn)化為下面標(biāo)準(zhǔn)的與或形：可將其轉(zhuǎn)化為下面標(biāo)準(zhǔn)的與或形：Q Q（z z，A A） R R（y y）P P（y y） S S（A A，y y） 于是于是, ,它的標(biāo)準(zhǔn)與或形可用一棵與或樹表示出來。它的標(biāo)準(zhǔn)與或形可用一棵與或樹表示出來。 Artificial Intell

11、igence 在與或圖中，節(jié)點(diǎn)表示事實(shí)表達(dá)式及其子表達(dá)式。根節(jié)點(diǎn)表示整個(gè)表達(dá)式，葉節(jié)點(diǎn)表示其中的單文字. 規(guī)定: 對(duì)于一個(gè)表示析取表達(dá)式（E1E2En）的節(jié)點(diǎn)，用一個(gè)n連接符（含半圓的?。┡c連接它的n個(gè)子表達(dá)式節(jié)點(diǎn)相連。對(duì)于一個(gè)表示合取表達(dá)式（E1 E2 En）的節(jié)點(diǎn)，用n個(gè)1連接符與連接它的n個(gè)子表達(dá)式節(jié)點(diǎn)相連。 重要性質(zhì):就是由變換表達(dá)式得到的一組子句，可以從與或圖中讀出，每個(gè)子句相當(dāng)于與或圖的一個(gè)解圖，每個(gè)子句是由葉節(jié)點(diǎn)組合成的公式。上例的3個(gè)子句是：Q（z，A）； S（A，y）R（y）； S（A，y）P（y） 這三個(gè)子句正是原表達(dá)式化成的子句集。因此，與或樹可以看成是一組子句的一個(gè)簡(jiǎn)潔

12、的表達(dá)式。Artificial Intelligence2、F規(guī)則的表示形式基于規(guī)則的正向推理中，要求F規(guī)則具有以下形式：LW。具體要求如下：L是單文字，W是任意的與或形表達(dá)式。L和W中的所有變量都是全稱量詞量化的，默認(rèn)的全稱量詞作用于整個(gè)蘊(yùn)含式。各條規(guī)則的變量各不相同，而且規(guī)則中的變量與事實(shí)表達(dá)式中的變量也不相同。1. 將F規(guī)則的左部限制為單文字，是因?yàn)榕c或圖的葉節(jié)點(diǎn)都是單文字，這樣就可用F規(guī)則的左部與葉節(jié)點(diǎn)進(jìn)行匹配，大大簡(jiǎn)化了規(guī)則的應(yīng)用過程。Artificial Intelligence 如果所給知識(shí)的表示形式不是所要求的形式，則可用如下如果所給知識(shí)的表示形式不是所要求的形式，則可用如下步

13、驟將其變換成標(biāo)準(zhǔn)形式：步驟將其變換成標(biāo)準(zhǔn)形式：（1 1）暫時(shí)消去蘊(yùn)含符號(hào)）暫時(shí)消去蘊(yùn)含符號(hào)“”。例如公式。例如公式 （ x）（ y）（）（ z）P（x，y，z） （ u）Q（x，u） 消去蘊(yùn)含符號(hào)消去蘊(yùn)含符號(hào)“”變?yōu)椋鹤優(yōu)椋?（ x） （ y）（）（ z）P（x，y，z） （ u）Q（x，u）（2 2）把否定號(hào)）把否定號(hào)“ ”移到每個(gè)謂詞的前面移到每個(gè)謂詞的前面, ,可變?yōu)榭勺優(yōu)?（ x x） （ y y）（）（ z z） P P（x x，y y，z z） （ u u）Q Q（x x，u u） （3 3）引入）引入skolemskolem函數(shù)消去存在量詞。消去存在量詞后，為函數(shù)消去存在量詞。消

14、去存在量詞后，為 （ x x） （ y y） P P（x x，y y，f f（x x，y y） （ u u）Q Q（x x，u u） （4 4）將公式化為前束式，并略去全稱量詞）將公式化為前束式，并略去全稱量詞, ,可變?yōu)榭勺優(yōu)?P P（x x，y y，f f（x x，y y） Q Q（x x，u u）（5 5）恢復(fù)為蘊(yùn)含式。利用等價(jià)關(guān)系）恢復(fù)為蘊(yùn)含式。利用等價(jià)關(guān)系 P P Q Q 與與 P PQ Q 將上式將上式變?yōu)樽優(yōu)?P P（x x，y y，f f（x x，y y） Q Q（x x，u u） Artificial Intelligence3、目標(biāo)公式的表示形式 要求目標(biāo)公式用文字的析取式

15、(子句)表示，否則就要化為子句形式。4、推理過程 應(yīng)用F規(guī)則作用于表示事實(shí)的與或圖，改變與或圖的結(jié)構(gòu)，從而產(chǎn)生新事實(shí)，直至推出了目標(biāo)公式。過程為：首先用與或圖把已知事實(shí)表示出來。用F規(guī)則的左部和與或圖的葉節(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的F規(guī)則結(jié)論加入到與或圖中，即利用F規(guī)則轉(zhuǎn)換與或圖。重復(fù)第（2）步，直到產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止節(jié)點(diǎn)的解圖為止，當(dāng)一個(gè)目標(biāo)文字和與或圖中的一個(gè)文字匹配時(shí)，可以將表示該目標(biāo)文字的節(jié)點(diǎn)(目標(biāo)節(jié)點(diǎn))通過匹配連接到與或圖中相應(yīng)的文字節(jié)點(diǎn)上。當(dāng)演繹產(chǎn)生的與或圖包括一個(gè)目標(biāo)節(jié)點(diǎn)上結(jié)束的解圖時(shí)，推理便成功結(jié)束。 Artificial Intelligence1)、命題邏輯的情

16、況 應(yīng)用規(guī)則的匹配過程比較簡(jiǎn)單。設(shè)已知事實(shí)的與應(yīng)用規(guī)則的匹配過程比較簡(jiǎn)單。設(shè)已知事實(shí)的與或形表達(dá)式為：（或形表達(dá)式為：（P P Q Q） R R） （S S （T T U U） 規(guī)則為規(guī)則為 S S（X X Y Y） Z Z 把把已知事實(shí)用與或圖表示已知事實(shí)用與或圖表示，圖中有一個(gè)葉節(jié)點(diǎn)是，圖中有一個(gè)葉節(jié)點(diǎn)是文字文字S S，它正好，它正好與規(guī)則的前項(xiàng)與規(guī)則的前項(xiàng)的文字的文字S S完全完全匹配匹配，由此可直接用這條規(guī)則對(duì)與或圖進(jìn)行變換，由此可直接用這條規(guī)則對(duì)與或圖進(jìn)行變換，即把即把規(guī)則后項(xiàng)的與或形公式用與或圖表示后添加到已規(guī)則后項(xiàng)的與或形公式用與或圖表示后添加到已知事實(shí)的與或圖上知事實(shí)的與或圖上

17、，并用一個(gè)匹配弧連接起來并用一個(gè)匹配弧連接起來，規(guī)則匹配后演繹的結(jié)果如下圖所示。圖中匹配弧規(guī)則匹配后演繹的結(jié)果如下圖所示。圖中匹配弧后面是規(guī)則部分。后面是規(guī)則部分。 Artificial IntelligenceArtificial Intelligence 例：事實(shí)表達(dá)式： AB； 規(guī)則集合：ACD，BEG； 目標(biāo)公式：C G 應(yīng)用完這兩條規(guī)則后，得到的與或圖如圖所示，其中有一個(gè)解圖滿足目標(biāo)公式（C G）所建立的結(jié)束條件。Artificial Intelligence2)、謂詞邏輯的情況 需要討論對(duì)含有變量的目標(biāo)公式的處理需要討論對(duì)含有變量的目標(biāo)公式的處理 ( (匹配問題匹配問題) )。 對(duì)

18、具有量詞量化變量的目標(biāo)公式來說對(duì)具有量詞量化變量的目標(biāo)公式來說，化簡(jiǎn)時(shí)要使用，化簡(jiǎn)時(shí)要使用SkolemSkolem化過程的對(duì)偶形式化過程的對(duì)偶形式。即目標(biāo)中。即目標(biāo)中屬于存在量詞轄屬于存在量詞轄域內(nèi)的全稱量化變量要用存在量化變量的域內(nèi)的全稱量化變量要用存在量化變量的SkolemSkolem函數(shù)函數(shù)來替代來替代，經(jīng)過，經(jīng)過SkolemSkolem化的公式化的公式只剩下存在量詞只剩下存在量詞，然后，然后對(duì)析取元作變量改名，最后再把存在量詞省略掉。對(duì)析取元作變量改名，最后再把存在量詞省略掉。 例如，設(shè)目標(biāo)公式為（例如，設(shè)目標(biāo)公式為（ y y）（）（ x x）（）（P P（x x，y y） Q Q（x

19、 x，y y） 用函數(shù)消去全稱量詞后有用函數(shù)消去全稱量詞后有 （ y y）（）（P P（f f（y y），），y y） Q Q（f f（y y），），y y）；然后）；然后進(jìn)行變量改名，進(jìn)行變量改名，使每個(gè)析取元具有不同的變量符號(hào)使每個(gè)析取元具有不同的變量符號(hào)，于是有，于是有 （ y y）（）（P P（f f（y y），），y y） （ y y1 1）Q Q（f f（y y1 1），），y y1 1） 最后省去存在量詞（最后省去存在量詞（P P（f f（y y），），y y） Q Q（f f（y y1 1），），y y1 1） 以后目標(biāo)公式中的變量都假定受存在量詞的約束。以后目標(biāo)公式中的變量都

20、假定受存在量詞的約束。Artificial Intelligence 下面舉例說明應(yīng)用一條規(guī)則LW對(duì)與或圖進(jìn)行變換的過程。設(shè)與或圖中有一個(gè)端節(jié)點(diǎn)的文字L和L可合一，mgu是u，則這條規(guī)則可應(yīng)用，這時(shí)用匹配弧連接的后裔節(jié)點(diǎn)是L，它是規(guī)則后項(xiàng)Wu對(duì)應(yīng)的與或圖表示的根節(jié)點(diǎn)，在匹配弧上標(biāo)記有u，表示用u置換后可與規(guī)則匹配。 例、事實(shí)與或形表示 P（x，y）（Q（x，A）R（B，y） 規(guī)則蘊(yùn)涵式 P（A，B）(S(A) X(B) 下圖是應(yīng)用規(guī)則變換后得到的與或圖，它有兩個(gè)解圖，對(duì)應(yīng)的兩個(gè)子句是 S(A) X(B) Q（A，A）；S(A) X(B) R（B，B）它們正是事實(shí)和規(guī)則公式組成的子句集對(duì)文字P進(jìn)

21、行歸結(jié)時(shí)得到的歸結(jié)式。 Artificial Intelligence圖圖7-77-7、應(yīng)用一條含有變量的規(guī)則后得到的與或圖、應(yīng)用一條含有變量的規(guī)則后得到的與或圖Artificial Intelligence 當(dāng)一個(gè)與或圖含有多個(gè)的匹配弧(應(yīng)用了多條規(guī)則時(shí))，任一解圖可能含多個(gè)匹配?。▽?duì)應(yīng)的置換是u1,u2,un），故在列寫解圖的子句集合時(shí)，只考慮具有一致的匹配弧置換的那些解圖（一致解圖）。一個(gè)一致解圖表示的子句是對(duì)得到的文字析取式應(yīng)用一個(gè)合一復(fù)合的置換之后所得到的子句。 設(shè)有一個(gè)置換集U=u1,u2,un,其中 u i =t i 1/v i 1, t i 2/v i 2,tim(i)/vim

22、(i)是置換對(duì)集合，t是項(xiàng)，v是變量。 根據(jù)這個(gè)置換集，定義變量集和項(xiàng)集： U1=( v11, v1m(1) , v21, v2m(2) , vn1, vnm(n) ,) (由每個(gè)置換ui中的變量vi構(gòu)成) U2=( t11, t1m(1) , t21, t2m(2) , tn1, tnm(n) ,) (由每個(gè)置換ui中的項(xiàng)ti構(gòu)成) 則置換U一致的充要條件是U1 和U2是可合一的。而U的合一復(fù)合u=mgu(U1, U2)。 Artificial Intelligence 可以驗(yàn)證對(duì)一個(gè)置換集合求合一復(fù)合的運(yùn)算是可結(jié)合和可交換的（求置換的合成是不可交換的），因此一個(gè)解圖對(duì)應(yīng)的合一復(fù)合不依賴于構(gòu)

23、造這個(gè)解圖時(shí)所產(chǎn)生的匹配弧的次序。 Artificial Intelligence 例：設(shè)事實(shí)和規(guī)則描述如下： Fido barks and bites, or Fido is not a dog. F: DOG(FIDO) (BARKS(FIDO) BITES(FIDO) All terriers are dogs. R1: （x） DOG(x)TERRIER(x)(原規(guī)則的逆否) Anyone who barks is noisy. R2: （y） BARKS(y) NOISY(y) 要證明的目標(biāo)是There exists someone who is not a terriers or

24、who is noisy. 目標(biāo)公式： （z） TERRIER(z) NOISY(z) Artificial IntelligenceArtificial Intelligence 上圖給出了演繹得到的與或圖，圖中結(jié)束在目標(biāo)節(jié)點(diǎn)的一個(gè)一致解圖，有置換集合 FIDO/x,FIDO/y,FIDO/z，它的合一復(fù)合是u=FIDO/x, FIDO/y, FIDO/z。根據(jù)這個(gè)一致解圖，目標(biāo)公式是事實(shí)和規(guī)則的邏輯推論，因而得到了證明。 如果用這個(gè)合一復(fù)合u應(yīng)用于這個(gè)目標(biāo)公式，可得 TERRIER(FIDO) NOISY(FIDO)，它是已證目標(biāo)公式的例，可作為一個(gè)回答語句。Artificial Inte

25、lligence722 反向演繹推理 它從目標(biāo)表達(dá)式出發(fā)，通過反向運(yùn)用規(guī)則進(jìn)行演繹推理，直到得到包含已知事實(shí)的終止條件為止.1、目標(biāo)表達(dá)式及其與或圖表示 首先,要將目標(biāo)表達(dá)式轉(zhuǎn)化為無蘊(yùn)涵符“”的與或形式，并用與或圖表示。要采用正向演繹中對(duì)事實(shí)表達(dá)式的變換的對(duì)偶形式: 即skolem化全稱量詞量化的變量，略去存在量詞（與正向演繹中對(duì)目標(biāo)表達(dá)式的處理一致）。 例如、有如下的目標(biāo)表達(dá)式： (y)(x) P(x) Q(x,y)(R(x)S(y) 可轉(zhuǎn)化為如下與或形式： P(f(y) Q(f(y),y) R(f(y) S(y) Artificial Intelligence 為使析取式具有不同的變量名，

26、重命名變量，得 P(f(z) Q(f(y),y) R(f(y) S(y)與或形式的目標(biāo)表達(dá)式可以用與或圖表示，但其表示方式與正向演繹中事實(shí)表達(dá)式的與或圖不同。它的n連接符用來把具有合取關(guān)系的子表達(dá)式連接起來，而在正向演繹中是把事實(shí)表達(dá)式具有析取關(guān)系的子表達(dá)式連接起來。上例的目標(biāo)表達(dá)式的與或圖如下圖所示。 圖中根節(jié)點(diǎn)為目標(biāo)表達(dá)式，稱為目標(biāo)節(jié)點(diǎn)，葉節(jié)點(diǎn)表示單個(gè)文字。若把葉節(jié)點(diǎn)用它們之間的合取及析取關(guān)系連接起來，就可得到原目標(biāo)表達(dá)式的三個(gè)子目標(biāo)：P(f(z) ；Q(f(y),y) R(f(y)；Q(f(y),y) S(y) 可以看出，子目標(biāo)是文字的合取式，其中的變量是存在量詞量化的。 Artific

27、ial IntelligenceArtificial Intelligence2、B規(guī)則的表示形式反向演繹推理中的規(guī)則稱為B規(guī)則，其表示形式為WL， 其中W為任一與或形式表達(dá)式，L為單一文字 (為了方便匹配) 。如果規(guī)則不符合這一要求，則要變換成這種形式。如規(guī)則WL1 L2，可以轉(zhuǎn)換為兩個(gè)B規(guī)則，即WL1，WL2。規(guī)則中應(yīng)Skolem化存在量詞量化的變量，并略去全稱量詞。3、已知事實(shí)的表示形式在反向演繹推理中，要求已知事實(shí)表達(dá)式是文字的合取式，可表示為文字的集合。對(duì)任意事實(shí)表達(dá)式，應(yīng)當(dāng)用Skolem函數(shù)代替事實(shí)表達(dá)式中存在量詞量化的變量，并略去全稱量詞量化的變量，將表達(dá)式轉(zhuǎn)化為標(biāo)準(zhǔn)的文字的合取

28、式。 Artificial Intelligence4、推理過程具體過程如下：用與或圖將目標(biāo)表達(dá)式表示出來。在目標(biāo)與或圖中，如果有一個(gè)文字L能夠與L合一，則可應(yīng)用B規(guī)則WL，并將L節(jié)點(diǎn)通過一個(gè)標(biāo)有L和L的最簡(jiǎn)單合一者的匹配弧與L相連，再將匹配成功的B規(guī)則加入與或圖中。一條規(guī)則可用多次，每次應(yīng)使用不同的變量。當(dāng)一個(gè)事實(shí)文字和與或圖中的一個(gè)文字可以合一時(shí)，可將該事實(shí)文字通過匹配弧連接到與或圖中相應(yīng)的文字上，匹配弧應(yīng)標(biāo)明兩個(gè)文字的最簡(jiǎn)單的合一者。1. 重復(fù)進(jìn)行第2步，直到與或圖中包括一個(gè)結(jié)束在事實(shí)節(jié)點(diǎn)上的一致解圖，該解圖的合一復(fù)合作用于目標(biāo)表達(dá)式就是解答語句。 Artificial Intellig

29、ence 例、設(shè)有事實(shí)：例、設(shè)有事實(shí)： F F1 1：DOGDOG（FIDOFIDO） FIDOFIDO是一只狗是一只狗 F F2 2：BARKSBARKS（FIDOFIDO） FIDOFIDO不叫不叫 F F3 3：WAGS-TAILWAGS-TAIL（FIDOFIDO） FIDOFIDO擺尾巴擺尾巴 F F4 4：MEOWSMEOWS（MYRTLEMYRTLE） MYRTLEMYRTLE喵喵叫喵喵叫 規(guī)則如下：規(guī)則如下： R R1 1：WAGS-TAILWAGS-TAIL（x x1 1） DOGDOG（x x1 1） FRIENDLYFRIENDLY（x x1 1） 擺尾巴的狗是友好的擺尾

30、巴的狗是友好的 R R2 2：FRIENDLYFRIENDLY（x x2 2） BARKSBARKS（x x2 2） AFRAIDAFRAID（y y2 2，x x2 2） 友好且不叫的是不令對(duì)方害怕的友好且不叫的是不令對(duì)方害怕的 R R3 3：DOGDOG（x x3 3）ANIMALANIMAL（x x3 3） 狗是動(dòng)物狗是動(dòng)物 R R4 4：CATCAT（x x4 4）ANIMALANIMAL（x x4 4） 貓是動(dòng)物貓是動(dòng)物 R R5 5：MEOWSMEOWS（x x5 5）CATCAT（x x5 5） 喵喵叫的是貓喵喵叫的是貓 問題是：是否存在一只貓和一條狗，這只貓不怕這條狗？問題是：

31、是否存在一只貓和一條狗，這只貓不怕這條狗？ 該問題的目標(biāo)公式是：（該問題的目標(biāo)公式是：（ x x）（）（ y y）CATCAT（x x） DOGDOG（y y） AFRAIDAFRAID（x x，y y） ，求解該問題的過程如下圖，求解該問題的過程如下圖. .Artificial Intelligence CAT（x） DOG（y） AFRAID（x，y） AFRAID（x，y） DOG(y)CAT(x)DOG(FIDO)CAT(x5) AFRAID （y2， x2） MEOWS(x)MEOWS(MYRTLE) BARKS（y） FRIENDLY(y) BARKS（FIDO） FRIENDLY

32、(x1)WAGS-TAIL(y)DOG(y)WAGS-TAIL(FIDO)DOG(FIDO)x/x5R5MYRTLE/xFIDO/yx/y2,y/x2R2FIDO/yy/x1R1FIDO/yFIDO/yArtificial Intelligence從上圖可看出，最后得到的是一個(gè)一致解圖。圖中共有8條匹配弧，每條匹配弧上都標(biāo)有置換，分別為 x/x5、MYRTLE/x、FIDO/y、x/y2,y/x2、 FIDO/y、y/x1、FIDO/y和FIDO/y。 這些置換的合一復(fù)合為 MYRTLE/x 5， MYRTLE/x ，F(xiàn)IDO/y ，MYRTLE/ y2，F(xiàn)IDO/ x2，F(xiàn)IDO/ x1 ，

33、將合一復(fù)合作用于目標(biāo)表達(dá)式就得到解答語句： CAT（MYRTLE） DOG（FIDO） AFRAID（MYRTLE，F(xiàn)IDO） 它表示有一只名叫MYRTLE的貓和一條名叫FIDO的狗，這只貓不怕那條狗。Artificial Intelligence使用條件 正向系統(tǒng) 事實(shí)表達(dá)式是任意形式 規(guī)則形式為L(zhǎng)W或L1L2W（(L為單文字，W為任意形式） 目標(biāo)公式為文字析取形 逆向系統(tǒng) 事實(shí)表達(dá)式是文字合取形 規(guī)則形式為WL或W L1L2（(L為單文字，W為任意形式） 目標(biāo)公式為任意形式Artificial Intelligence化簡(jiǎn)過程 正向系統(tǒng) 用skolem函數(shù)消去事實(shí)表達(dá)式中的存在量詞，化簡(jiǎn)的

34、公式受全稱量詞的約束; 對(duì)規(guī)則的處理同上; 用skolem函數(shù)（對(duì)偶形）消去目標(biāo)公式中的全稱量詞，化簡(jiǎn)的公式受存在量詞約束. 逆向系統(tǒng) skolem函數(shù)（對(duì)偶形）消去目標(biāo)公式中的全稱量詞，化簡(jiǎn)的公式受存在量詞約束。 對(duì)規(guī)則的處理同下; 用skolem函數(shù)消去事實(shí)表達(dá)式中的存在量詞，化簡(jiǎn)的公式受全稱量詞的約束. Artificial Intelligence正向系統(tǒng)逆向系統(tǒng)初始數(shù)據(jù)庫(kù)事實(shí)表達(dá)式的與或樹事實(shí)表達(dá)式的與或樹（ 對(duì)應(yīng)為與關(guān)系，對(duì)應(yīng)為或關(guān)系）.目標(biāo)公式的與或樹（對(duì)應(yīng)為或關(guān)系，對(duì)應(yīng)為與關(guān)系）.推理過程從事實(shí)出發(fā)，正向應(yīng)用規(guī)則（變量改名，前項(xiàng)與事實(shí)文字匹配，后項(xiàng)代替前項(xiàng)），直至得到目標(biāo)節(jié)點(diǎn)為

35、結(jié)束條件的一致解為止.從目標(biāo)出發(fā)，逆向應(yīng)用規(guī)則（變量改名，后項(xiàng)與子目標(biāo)文字匹配，前項(xiàng)代替后項(xiàng)），直至得到事實(shí)節(jié)點(diǎn)為結(jié)束條件的一致解圖為止.子句形式的子集形式文字的析取式; 子句的合取式（合取范式）.文字的合取式;子句的析取式（析取范式）.Artificial Intelligence723 雙向演繹推理 正向演繹推理要求目標(biāo)表達(dá)式是文字的析取式，而反向演繹推理要求事實(shí)公式為文字的合取式。為充分發(fā)揮正向演繹和反向演繹的優(yōu)點(diǎn)，克服各自的局限性，可將兩種演繹推理相結(jié)合，這就是雙向演繹推理。 在雙向演繹推理中，已知事實(shí)用與或圖表示，目標(biāo)表達(dá)式用另一個(gè)與或圖表示。這兩個(gè)與或圖分別由正向演繹的F規(guī)則和反向

36、演繹的B規(guī)則進(jìn)行操作，并且仍限制F規(guī)則的左部為單文字，而B規(guī)則的右部為單文字。 雙向演繹推理分別從正反兩個(gè)方向進(jìn)行推理，兩個(gè)與或圖分別擴(kuò)展，最關(guān)鍵也是最復(fù)雜的是如何判斷推理是否結(jié)束。推理的終止處位于兩個(gè)與或圖分別擴(kuò)展后的某個(gè)交接處，當(dāng)正反兩個(gè)方向的與或圖對(duì)應(yīng)的葉節(jié)點(diǎn)都可合一時(shí)，推理就結(jié)束。 Artificial Intelligence P(f(y) Q(f(y),y) R(f(y) S(y) P(f(y) Q(f(y),y) R(f(y) S(y) Q(f(y),y) R(f(y) S(y) R(f(y) S(y) S(A) R(x) Q(x,A) R(x) S(A) Q(x,A) R(x)

37、 S(A) f(A)/x,A/yf(A)/xA/y匹配目標(biāo)表達(dá)式與或圖（B規(guī)則）事實(shí)表達(dá)式與或圖（F規(guī)則）Artificial Intelligence 上圖說明了雙向演繹推理的過程。圖中對(duì)應(yīng)的已知事實(shí)表達(dá)式和目標(biāo)表達(dá)式分別為： Q(x,A) R(x) S(A); P(f(y) Q(f(y),y) R(f(y)S(y) 圖中，共有3個(gè)匹配弧，并標(biāo)有各自的置換。這些置換是一致的，其合一復(fù)合為f（A）/x，A/y。在推理過程中，沒有使用B規(guī)則和F規(guī)則，這里主要說明雙向推理是如何在交接處終止的。 Artificial Intelligence7.3 不確定性推理 邏輯推理是一種運(yùn)用確定性知識(shí)進(jìn)行的精

38、確推理。但是，現(xiàn)實(shí)世界中的事物以及事物之間的關(guān)系是極其復(fù)雜的，在人類知識(shí)中，有相當(dāng)一部分是不精確的、模糊的，因此不精確的推理模型是人工智能和專家系統(tǒng)的一個(gè)核心研究問題. 實(shí)際上，AI系統(tǒng)的智能主要反映在求解不精確性問題的能力上。 不確定性推理就是從不確定性初始事實(shí)（證據(jù)）出發(fā)，通過運(yùn)用不確定性的知識(shí)，最終推出具有一定程度的不確定性是合理或者近乎合理的結(jié)論的思維過程。Artificial Intelligence一 概率方法)()()|(BPBAPBAP1) 條件概率: 設(shè)A和B是某隨機(jī)試驗(yàn)中的兩個(gè)事件，如果在事件B發(fā)生的條件下考慮事件A發(fā)生的概率，就稱它為事件A的條件概論，記做P（A|B）。若P（B）0，則2) 全概率公式：設(shè)事件A1 ，A2，An滿足: 兩兩互不相容，即當(dāng)ij，AiAj=； P（Ai）0 D為必然事件；則對(duì)任何事件B有下式成立： niiAD1該公式稱為全概率公式，它提供了一種計(jì)算P（B）的方法。Artificial Intelligence 3）Bayes公式：設(shè)事件A1 ，A2，An滿足上述全概率公式的條件，則對(duì)任何事件B有下式成立 niABPA