人工智能推理技術【業(yè)界相關】

1、第7章、基本的推理技術,推理技術概述 基于規(guī)則的演繹推理 正向演繹推理 逆向演繹推理 雙向演繹推理 不確定性推理 概率推理,人工智能是用計算機來模擬人的智能，就是用能在計算機上實現(xiàn)的技術和方法來模擬人的思維規(guī)律和過程。 1) 在確定知識表達方法后，就可以把知識表示出來并存儲到計算機中。 2) 然后, 利用知識進行推理以求得問題的解. 利用知識進行推理是知識利用的基礎。各種人工智能應用領域如專家系統(tǒng)、智能機器人、模式識別、自然語言理解等都是利用知識進行廣義問題求解的智能系統(tǒng),7.1 推理技術概述 -1. 推理的概念與類型,推理是人類求解問題的主要思維方法. 所謂推理就是按照某種策略從已有事實和知

2、識推出結論的過程。推理是由程序實現(xiàn)的，稱為推理機。 人類的智能活動有多種思維方式，人工智能作為對人類智能的模擬，相應地也有多種推理方式,1. 演繹推理、歸納推理、默認推理,1). 演繹推理：演繹推理是從全稱判斷推出特稱判斷或單稱判斷的過程，即從一般到個別的推理。最常用的形式是三段論法。 例如： 1）所有的推理系統(tǒng)都是智能系統(tǒng)； 2）專家系統(tǒng)是推理系統(tǒng)； 3）所以，專家系統(tǒng)是智能系統(tǒng)。 (2).歸納推理: 是從足夠多的事例中歸納出一般性結論的推理過程，是一種從個別到一般的推理過程。 (3). 默認推理：默認推理又稱缺省推理，它是在知識不完全的情況下假設某些條件已經(jīng)具備所進行的推理,2、確定性推理

3、、不確定性推理,如果按推理時所用的知識的確定性來分，推理可分為確定性推理與不確定性推理。 （1）確定性推理（精確推理）。如果在推理中所用的知識都是精確的，即可以把知識表示成必然的因果關系，然后進行邏輯推理，推理的結論或者為真，或者為假，這種推理就稱為確定性推理。（如歸結反演、基于規(guī)則的演繹系統(tǒng)等） （2）不確定性推理(不精確推理)。在人類知識中，有相當一部分屬于人們的主觀判斷，是不精確的和含糊的。由這些知識歸納出來的推理規(guī)則往往是不確定的?；谶@種不確定的推理規(guī)則進行推理，形成的結論也是不確定的，這種推理稱為不確定推理。 (在專家系統(tǒng)中主要使用的方法,3、單調推理、非單調推理,如果按推理過程中

4、推出的結論是否單調增加，或者說推出的結論是否越來越接近最終目標來劃分，推理又可分為單調推理與非單調推理。 （1）單調推理。是指在推理過程中隨著推理的向前推進及新知識的加入，推出的結論呈單調增加的趨勢，并且越來越接近最終目標。(演繹推理是單調推理。) （2）非單調推理。是指在推理過程中隨著推理的向前推進及新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使得推理退回到前面的某一步，重新開始。(一般是在知識不完全的情況下進行的,4、啟發(fā)式推理、非啟發(fā)式推理,如果按推理中是否運用與問題有關的啟發(fā)性知識，推理可分為啟發(fā)式推理和非啟發(fā)式推理。 （1）啟發(fā)式推理：如果在推理過程中，運用與問題有關的啟發(fā)

5、性知識，如解決問題的策略、技巧及經(jīng)驗等，以加快推理過程，提高搜索效率，這種推理過程稱為啟發(fā)式推理。如A、A*等算法。 （2）非啟發(fā)式推理。如果在推理過程中，不運用啟發(fā)性知識，只按照一般的控制邏輯進行推理，這種推理過程稱為非啟發(fā)式推理。(推理效率較低，容易出現(xiàn)“組合爆炸”問題。,推理的控制策略,主要是指推理方向的選擇、推理時所用的搜索策略及沖突解決策略等。一般推理的控制策略與知識表達方法有關 (產(chǎn)生式系統(tǒng)) . 1、推理方向：用于確定推理的驅動方式。分為正向推理(由已知事實出發(fā))、反向推理(以某個假設目標作為出發(fā)點)和正反向混合推理(正向推理和反向推理相結合).系統(tǒng)組成: 知識庫（KB）+初始事

6、實和中間結果的數(shù)據(jù)庫（DB）+ 推理機 2、搜索策略:推理時要反復用到知識庫中的規(guī)則，而知識庫中的規(guī)則又很多，這樣就存在著如何在知識庫中尋找可用規(guī)則的問題(代價小,解好). 可以采用各種搜索策略有效地控制規(guī)則的選取,3、沖突解決策略,在推理過程中，系統(tǒng)要不斷地用數(shù)據(jù)庫中的事實與知識庫中的規(guī)則進行匹配，當有一個以上規(guī)則的條件部分和當前數(shù)據(jù)庫相匹配時，就需要有一種策略來決定首先使用哪一條規(guī)則，這就是沖突解決策略。沖突解決策略實際上就是確定規(guī)則的啟用順序。 （1）專一性排序(條件部分更具體的規(guī)則) （2）規(guī)則排序(規(guī)則編排順序) （3）數(shù)據(jù)排序(所有條件按優(yōu)先級次序編排起來) （4）就近排序(最近使

7、用的規(guī)則優(yōu)先) （5）上下文限制(在某種上下文條件下) （6）按匹配度排序(計算這兩個模式的相似程度) （7）按條件個數(shù)排序(條件少的優(yōu)先,72 基于規(guī)則的演繹推理,許多AI系統(tǒng)中所用到的知識一般是由蘊含式直接表示的，但在歸結反演中，必須首先將它們轉化為子句的形式，所以這種推理是比較低效的。 基于規(guī)則的演繹推理則是直接的推理方法。它把有關問題的知識和信息劃分為規(guī)則與事實兩種類型。規(guī)則由包含蘊含形式的表達式表示，事實由無蘊含形式的表達式表示，并畫出相應的與或圖，然后通過規(guī)則進行演繹推理。 可分為正向、反向和正反向演繹推理。在正向推理中，作為F規(guī)則用的蘊含式對事實的總數(shù)據(jù)庫進行操作運算，直至得到該

8、目標公式的一個終止條件為止；在反向推理中，作為B規(guī)則用的蘊含式對目標的總數(shù)據(jù)庫進行操作運算，直至得到包含這些事實的一個終止條件為止；在雙向推理中，分別從兩個方向應用不同的規(guī)則（F和B）進行操作運算,721 正向演繹推理,正向演繹推理屬于正向推理，它是從已知事實出發(fā)，反復嘗試所有可利用的規(guī)則（F規(guī)則）進行演繹推理，直到得到某個目標公式的一個終止條件為止。 1、事實表達式及其與或圖表示 正向演繹要求事實用不包含蘊含符號“”的與或形表示。把一個表達式轉化為標準的與或形的步驟如下： （1）利用等價式PQ與PQ消去蘊含符“”。 （2）把否定符號“”移到每個謂詞符號的前面。 （3）變量標準化，即重新命名變

9、量，使不同量詞約束的變量有不同的名字。 （4）引入Skolem函數(shù)消去存在量詞。 （5）將公式化為前束形。 （6）略去全稱量詞（默認變量是全稱量詞量化的）。 （7）重新命名變量，使同一變量不出現(xiàn)在不同的主要合取式中,例如 ：有如下的表達式,x）（y）Q（y，x）（R（y）P（y）S（x，y） 可將其轉化為下面標準的與或形：Q（z，A）R（y）P（y） S（A，y） 于是,它的標準與或形可用一棵與或樹表示出來,在與或圖中，節(jié)點表示事實表達式及其子表達式。根節(jié)點表示整個表達式，葉節(jié)點表示其中的單文字. 規(guī)定: 對于一個表示析取表達式（E1E2En）的節(jié)點，用一個n連接符（含半圓的?。┡c連接它的n個

10、子表達式節(jié)點相連。對于一個表示合取表達式（E1E2En）的節(jié)點，用n個1連接符與連接它的n個子表達式節(jié)點相連。 重要性質:就是由變換表達式得到的一組子句，可以從與或圖中讀出，每個子句相當于與或圖的一個解圖，每個子句是由葉節(jié)點組合成的公式。上例的3個子句是：Q（z，A）； S（A，y）R（y）； S（A，y）P（y） 這三個子句正是原表達式化成的子句集。因此，與或樹可以看成是一組子句的一個簡潔的表達式,2、F規(guī)則的表示形式,基于規(guī)則的正向推理中，要求F規(guī)則具有以下形式：LW。 具體要求如下： L是單文字，W是任意的與或形表達式。 L和W中的所有變量都是全稱量詞量化的，默認的全稱量詞作用于整個蘊含

11、式。 各條規(guī)則的變量各不相同，而且規(guī)則中的變量與事實表達式中的變量也不相同。 將F規(guī)則的左部限制為單文字，是因為與或圖的葉節(jié)點都是單文字，這樣就可用F規(guī)則的左部與葉節(jié)點進行匹配，大大簡化了規(guī)則的應用過程,如果所給知識的表示形式不是所要求的形式，則可用如下步驟將其變換成標準形式： （1）暫時消去蘊含符號“”。例如公式 （x）（y）（z）P（x，y，z） （u）Q（x，u） 消去蘊含符號“”變?yōu)椋?（x）（y）（z）P（x，y，z） （u）Q（x，u） （2）把否定號“”移到每個謂詞的前面,可變?yōu)?（x）（y）（z）P（x，y，z） （u）Q（x，u） （3）引入skolem函數(shù)消去存在量詞。消去

12、存在量詞后，為 （x）（y） P（x，y，f（x，y） （u）Q（x，u） （4）將公式化為前束式，并略去全稱量詞,可變?yōu)?P（x，y，f（x，y） Q（x，u） （5）恢復為蘊含式。利用等價關系 PQ 與 PQ 將上式變?yōu)?P（x，y，f（x，y） Q（x，u,3、目標公式的表示形式 要求目標公式用文字的析取式(子句)表示，否則就要化為子句形式。 4、推理過程 應用F規(guī)則作用于表示事實的與或圖，改變與或圖的結構，從而產(chǎn)生新事實，直至推出了目標公式。過程為： 首先用與或圖把已知事實表示出來。 用F規(guī)則的左部和與或圖的葉節(jié)點進行匹配，并將匹配成功的F規(guī)則結論加入到與或圖中，即利用F規(guī)則轉換與或圖

13、。 重復第（2）步，直到產(chǎn)生一個含有以目標節(jié)點作為終止節(jié)點的解圖為止，當一個目標文字和與或圖中的一個文字匹配時，可以將表示該目標文字的節(jié)點(目標節(jié)點)通過匹配連接到與或圖中相應的文字節(jié)點上。當演繹產(chǎn)生的與或圖包括一個目標節(jié)點上結束的解圖時，推理便成功結束,1)、命題邏輯的情況,應用規(guī)則的匹配過程比較簡單。設已知事實的與或形表達式為：（PQ）R）（S （TU） 規(guī)則為 S（XY）Z 把已知事實用與或圖表示，圖中有一個葉節(jié)點是文字S，它正好與規(guī)則的前項的文字S完全匹配，由此可直接用這條規(guī)則對與或圖進行變換，即把規(guī)則后項的與或形公式用與或圖表示后添加到已知事實的與或圖上，并用一個匹配弧連接起來，規(guī)則

14、匹配后演繹的結果如下圖所示。圖中匹配弧后面是規(guī)則部分,例：事實表達式： AB； 規(guī)則集合：ACD，BEG； 目標公式：C G 應用完這兩條規(guī)則后，得到的與或圖如圖所示，其中有一個解圖滿足目標公式（C G）所建立的結束條件,2)、謂詞邏輯的情況,需要討論對含有變量的目標公式的處理 (匹配問題)。 對具有量詞量化變量的目標公式來說，化簡時要使用Skolem化過程的對偶形式。即目標中屬于存在量詞轄域內(nèi)的全稱量化變量要用存在量化變量的Skolem函數(shù)來替代，經(jīng)過Skolem化的公式只剩下存在量詞，然后對析取元作變量改名，最后再把存在量詞省略掉。 例如，設目標公式為（y）（x）（P（x，y） Q（x，y

15、） 用函數(shù)消去全稱量詞后有 （y）（P（f（y），y）Q（f（y），y）；然后進行變量改名，使每個析取元具有不同的變量符號，于是有 （y）（P（f（y），y）（y1）Q（f（y1），y1） 最后省去存在量詞（P（f（y），y）Q（f（y1），y1） 以后目標公式中的變量都假定受存在量詞的約束,下面舉例說明應用一條規(guī)則LW對與或圖進行變換的過程。設與或圖中有一個端節(jié)點的文字L和L可合一，mgu是u，則這條規(guī)則可應用，這時用匹配弧連接的后裔節(jié)點是L，它是規(guī)則后項Wu對應的與或圖表示的根節(jié)點，在匹配弧上標記有u，表示用u置換后可與規(guī)則匹配。 例、事實與或形表示 P（x，y）（Q（x，A）R（B，y）

16、 規(guī)則蘊涵式 P（A，B）(S(A) X(B) 下圖是應用規(guī)則變換后得到的與或圖，它有兩個解圖，對應的兩個子句是 S(A) X(B) Q（A，A）；S(A) X(B) R（B，B）它們正是事實和規(guī)則公式組成的子句集對文字P進行歸結時得到的歸結式,圖7-7、應用一條含有變量的規(guī)則后得到的與或圖,當一個與或圖含有多個的匹配弧(應用了多條規(guī)則時)，任一解圖可能含多個匹配?。▽闹脫Q是u1,u2,un），故在列寫解圖的子句集合時，只考慮具有一致的匹配弧置換的那些解圖（一致解圖）。一個一致解圖表示的子句是對得到的文字析取式應用一個合一復合的置換之后所得到的子句。 設有一個置換集U=u1,u2,un,其

17、中 u i =t i 1/v i 1, t i 2/v i 2,tim(i)/vim(i)是置換對集合，t是項，v是變量。 根據(jù)這個置換集，定義變量集和項集： U1=( v11, v1m(1) , v21, v2m(2) , vn1, vnm(n) ,) (由每個置換ui中的變量vi構成) U2=( t11, t1m(1) , t21, t2m(2) , tn1, tnm(n) ,) (由每個置換ui中的項ti構成) 則置換U一致的充要條件是U1 和U2是可合一的。而U的合一復合u=mgu(U1, U2,可以驗證對一個置換集合求合一復合的運算是可結合和可交換的（求置換的合成是不可交換的），因此

18、一個解圖對應的合一復合不依賴于構造這個解圖時所產(chǎn)生的匹配弧的次序,例：設事實和規(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) 要證明的目標是There exists someone who is not a terriers or who is no

19、isy. 目標公式： （z） TERRIER(z) NOISY(z,上圖給出了演繹得到的與或圖，圖中結束在目標節(jié)點的一個一致解圖，有置換集合 FIDO/x,FIDO/y,FIDO/z，它的合一復合是u=FIDO/x, FIDO/y, FIDO/z。根據(jù)這個一致解圖，目標公式是事實和規(guī)則的邏輯推論，因而得到了證明。 如果用這個合一復合u應用于這個目標公式，可得 TERRIER(FIDO) NOISY(FIDO)，它是已證目標公式的例，可作為一個回答語句,722 反向演繹推理,它從目標表達式出發(fā)，通過反向運用規(guī)則進行演繹推理，直到得到包含已知事實的終止條件為止. 1、目標表達式及其與或圖表示 首先

20、,要將目標表達式轉化為無蘊涵符“”的與或形式，并用與或圖表示。要采用正向演繹中對事實表達式的變換的對偶形式: 即skolem化全稱量詞量化的變量，略去存在量詞（與正向演繹中對目標表達式的處理一致）。 例如、有如下的目標表達式： (y)(x) P(x) Q(x,y)(R(x)S(y) 可轉化為如下與或形式： P(f(y) Q(f(y),y) R(f(y) S(y,為使析取式具有不同的變量名，重命名變量，得 P(f(z) Q(f(y),y) R(f(y) S(y) 與或形式的目標表達式可以用與或圖表示，但其表示方式與正向演繹中事實表達式的與或圖不同。它的n連接符用來把具有合取關系的子表達式連接起來

21、，而在正向演繹中是把事實表達式具有析取關系的子表達式連接起來。上例的目標表達式的與或圖如下圖所示。 圖中根節(jié)點為目標表達式，稱為目標節(jié)點，葉節(jié)點表示單個文字。若把葉節(jié)點用它們之間的合取及析取關系連接起來，就可得到原目標表達式的三個子目標：P(f(z) ；Q(f(y),y) R(f(y)；Q(f(y),y) S(y) 可以看出，子目標是文字的合取式，其中的變量是存在量詞量化的,2、B規(guī)則的表示形式 反向演繹推理中的規(guī)則稱為B規(guī)則，其表示形式為WL， 其中W為任一與或形式表達式，L為單一文字 (為了方便匹配) 。如果規(guī)則不符合這一要求，則要變換成這種形式。如規(guī)則WL1 L2，可以轉換為兩個B規(guī)則，

22、即WL1，WL2。 規(guī)則中應Skolem化存在量詞量化的變量，并略去全稱量詞。 3、已知事實的表示形式 在反向演繹推理中，要求已知事實表達式是文字的合取式，可表示為文字的集合。對任意事實表達式，應當用Skolem函數(shù)代替事實表達式中存在量詞量化的變量，并略去全稱量詞量化的變量，將表達式轉化為標準的文字的合取式,4、推理過程,具體過程如下： 用與或圖將目標表達式表示出來。 在目標與或圖中，如果有一個文字L能夠與L合一，則可應用B規(guī)則WL，并將L節(jié)點通過一個標有L和L的最簡單合一者的匹配弧與L相連，再將匹配成功的B規(guī)則加入與或圖中。一條規(guī)則可用多次，每次應使用不同的變量。當一個事實文字和與或圖中的

23、一個文字可以合一時，可將該事實文字通過匹配弧連接到與或圖中相應的文字上，匹配弧應標明兩個文字的最簡單的合一者。 重復進行第2步，直到與或圖中包括一個結束在事實節(jié)點上的一致解圖，該解圖的合一復合作用于目標表達式就是解答語句,例、設有事實： F1：DOG（FIDO） FIDO是一只狗 F2：BARKS（FIDO） FIDO不叫 F3：WAGS-TAIL（FIDO） FIDO擺尾巴 F4：MEOWS（MYRTLE） MYRTLE喵喵叫 規(guī)則如下： R1：WAGS-TAIL（x1） DOG（x1） FRIENDLY（x1） 擺尾巴的狗是友好的 R2：FRIENDLY（x2）BARKS（x2） AFRA

24、ID（y2，x2） 友好且不叫的是不令對方害怕的 R3：DOG（x3）ANIMAL（x3） 狗是動物 R4：CAT（x4）ANIMAL（x4） 貓是動物 R5：MEOWS（x5）CAT（x5） 喵喵叫的是貓 問題是：是否存在一只貓和一條狗，這只貓不怕這條狗？ 該問題的目標公式是：（x）（y）CAT（x） DOG（y） AFRAID（x，y），求解該問題的過程如下圖,從上圖可看出，最后得到的是一個一致解圖。圖中共有8條匹配弧，每條匹配弧上都標有置換，分別為 x/x5、MYRTLE/x、FIDO/y、x/y2,y/x2、 FIDO/y、y/x1、FIDO/y和FIDO/y。 這些置換的合一復合為

25、MYRTLE/x 5， MYRTLE/x ，F(xiàn)IDO/y ，MYRTLE/ y2，F(xiàn)IDO/ x2，F(xiàn)IDO/ x1 ，將合一復合作用于目標表達式就得到解答語句： CAT（MYRTLE） DOG（FIDO） AFRAID（MYRTLE，F(xiàn)IDO） 它表示有一只名叫MYRTLE的貓和一條名叫FIDO的狗，這只貓不怕那條狗,使用條件,正向系統(tǒng) 事實表達式是任意形式 規(guī)則形式為LW或L1L2W（(L為單文字，W為任意形式） 目標公式為文字析取形,逆向系統(tǒng) 事實表達式是文字合取形 規(guī)則形式為WL或W L1L2（(L為單文字，W為任意形式） 目標公式為任意形式,化簡過程,正向系統(tǒng) 用skolem函數(shù)消去

26、事實表達式中的存在量詞，化簡的公式受全稱量詞的約束; 對規(guī)則的處理同上; 用skolem函數(shù)（對偶形）消去目標公式中的全稱量詞，化簡的公式受存在量詞約束,逆向系統(tǒng) skolem函數(shù)（對偶形）消去目標公式中的全稱量詞，化簡的公式受存在量詞約束。 對規(guī)則的處理同下; 用skolem函數(shù)消去事實表達式中的存在量詞，化簡的公式受全稱量詞的約束,723 雙向演繹推理,正向演繹推理要求目標表達式是文字的析取式，而反向演繹推理要求事實公式為文字的合取式。為充分發(fā)揮正向演繹和反向演繹的優(yōu)點，克服各自的局限性，可將兩種演繹推理相結合，這就是雙向演繹推理。 在雙向演繹推理中，已知事實用與或圖表示，目標表達式用另一

27、個與或圖表示。這兩個與或圖分別由正向演繹的F規(guī)則和反向演繹的B規(guī)則進行操作，并且仍限制F規(guī)則的左部為單文字，而B規(guī)則的右部為單文字。 雙向演繹推理分別從正反兩個方向進行推理，兩個與或圖分別擴展，最關鍵也是最復雜的是如何判斷推理是否結束。推理的終止處位于兩個與或圖分別擴展后的某個交接處，當正反兩個方向的與或圖對應的葉節(jié)點都可合一時，推理就結束,上圖說明了雙向演繹推理的過程。圖中對應的已知事實表達式和目標表達式分別為： Q(x,A) R(x) S(A); P(f(y) Q(f(y),y) R(f(y)S(y) 圖中，共有3個匹配弧，并標有各自的置換。這些置換是一致的，其合一復合為f（A）/x，A/

28、y。在推理過程中，沒有使用B規(guī)則和F規(guī)則，這里主要說明雙向推理是如何在交接處終止的,7.3 不確定性推理,邏輯推理是一種運用確定性知識進行的精確推理。但是，現(xiàn)實世界中的事物以及事物之間的關系是極其復雜的，在人類知識中，有相當一部分是不精確的、模糊的，因此不精確的推理模型是人工智能和專家系統(tǒng)的一個核心研究問題. 實際上，AI系統(tǒng)的智能主要反映在求解不精確性問題的能力上。 不確定性推理就是從不確定性初始事實（證據(jù)）出發(fā)，通過運用不確定性的知識，最終推出具有一定程度的不確定性是合理或者近乎合理的結論的思維過程,一 概率方法,1) 條件概率: 設A和B是某隨機試驗中的兩個事件，如果在事件B發(fā)生的條件下考慮事件A發(fā)生的概率，就稱它為事件A的條件概論，記做P（A|B）。若P（B）0，則,2) 全概率公式：設事件A1 ，A2，An滿足: 兩兩互不相容，即當ij，AiAj=； P