《西電人工智能8確定性推理part1課件》由會員分享，可在線閱讀，更多相關《西電人工智能8確定性推理part1課件（45頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,西安電子科技大學,Artificial Intelligence(AI),人工智能,主講：戚玉濤,Email,：,第三章：確定性推理,內容提要,第三章：確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結演繹推理,5.,基于規(guī)則的演繹推理,內容提要,第三章：確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結演

2、繹推理,5.,基于規(guī)則的演繹推理,推理的基本概念,推理的基本概念,1.,什么是推理,2.,推理方法及其分類,3.,推理的控制策略及其分類,推理的基本概念,什么是推理,所謂推理就是按某種策略由已知判斷推出另一個判斷的思維過程。,在人工智能中，推理是由程序實現(xiàn)的，稱為推理機。,智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為：,確定性推理（第三章）,不確定性推理（第四章）,推理的基本概念,推理的兩個基本問題,推理的方法：,演繹？歸納？類比？確定？不確定？單調？非單調？啟發(fā)式？非啟發(fā)式？,推理的控制策略：,推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策

3、略。,推理的控制策略又可分為,搜索策略,和,推理策略,。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,演繹推理,:,從已知的一般性知識出發(fā)，推出蘊含在已知知識中的適合于某種個別情況的結論。是一種由一般到個別的推理方法，其,核心是三段論,。,歸納推理,:,是一種由個別到一般的推理方法。,類比歸納推理,:,是指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其他屬性上也相同或相似的一種歸納推理,。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,演繹推理：,假言三段論：,AB,，,BC AC,常用的三段論是由一個,大前提,、,一個小前提,和,一個結論,這三

4、部分組成的。,大前提是已知的一般性知識或推理過程得到的判斷；,小前提是關于某種具體情況或某個具體實例的判斷；,結論是由大前提推出的，并且適合于小前提的判斷。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,演繹推理：,例如，有如下三個判斷：,計算機系的學生都會編程序；（一般性知識）,程強是計算機系的一位學生；（具體情況）,程強會編程序。（結論）,這是一個三段論推理。其中，是大前提，是小前提；是經(jīng)演繹推出來的結論。,可見，,其結論是蘊含在大前提中的,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,歸納推理：,按照所選事例的,廣泛性,可分為,完全歸納推理,和,不完全歸納

5、推理,。,完全歸納推理：,是指在進行歸納時需要考察相應事物的,全部對象,，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。,不完全歸納推理：,是指在進行歸納時只考察了相應事物的,部分對象,，就得出了關于該事物的結論。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,歸納推理：,按照推理所使用的,方法,可分為,枚舉,、,類比,、,統(tǒng)計,和,差異歸納推理,等。,枚舉歸納推理：,是指在進行歸納時，如果已知某類事物的,有限可數(shù)個具體事物,都具有某種屬性，則可推出該類事物都具有此種屬性。,例如，設有如下事例：,王強是計算機系學生，他會編程序；高華是計算機系學生，她會編程序；,

6、當這些具體事例足夠多時，就可歸納出一個一般性的知識：凡是計算機系的學生，就一定會編程序。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,類比歸納推理：,若在兩個或兩類事物有許多屬性相同或相似，則推出它們在其他屬性上也相同或相似。,例如：,設,A,、,B,分別是兩類事物的集合：,A=a,1,a,2,，,B=b,1,b,2,并設,a,i,與,b,i,總是成對出現(xiàn)，且當,a,i,有屬性,P,時，,b,i,就有屬性,Q,與此對應，即,P(a,i,)Q(b,i,),（,i=1,2,.,）。,當,A,與,B,中有一新的元素對出現(xiàn)時，若已知,a,有屬性,P,，,b,有屬性,Q,則類比歸納出結

7、論：,P(a)Q(b,),推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,類比歸納推理：,類比歸納推理的基礎是,相似原理,，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎分類,演繹推理與歸納推理的區(qū)別：,演繹推理是在已知領域內的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結論的正確性。,它所得出的結論實際上早已蘊含在一般性知識的前提中,，演繹推理只不過是將已有事實揭露出來，因此,它不能增殖新知識,。,歸納推理所推出的結論是沒有包含在前提內容中的,。這種由個

8、別事物或現(xiàn)象推出一般性知識的過程，,是增殖新知識的過程,。,推理的基本概念,推理方法及其分類,2.,按推理過程所用知識的確定性分類,確定性推理,不確定性推理,3.,按推理過程推出的結論是否單調增加分類,單調推理,非單調推理,4.,按推理過程是否利用問題的啟發(fā)性知識分類,啟發(fā)式推理,非啟發(fā)式推理,推理的基本概念,推理的控制策略及其分類,推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。,推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略,。,推理的控制策略可分為：,搜索策略,推理策略,推理的基本概念,推理的控制策略及其分類,搜索策略：,在知識庫中尋找可利用的知識，從而構造

9、一條代價較小的推理路線。主要解決推理線路、推理效果、推理效率等問題。,按是否使用啟發(fā)式信息可分為：,盲目搜索,啟發(fā)式搜索,按問題的表示方式可分為：,狀態(tài)空間搜索,與或樹搜索,推理的基本概念,推理的控制策略及其分類,推理策略：,包括推理方向控制策略、求解策略、限制策略、沖突消解策略等,推理方向控制策略：,用于確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙向推理。,求解策略：,是指僅求一個解，還是求所有解或最優(yōu)解等。,限制策略：,是指對推理的深度、寬度、時間、空間等進行的限制。,沖突消解策略：,是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。,推理

10、的基本概念,推理的控制策略及其分類,推理方向控制策略：,正向推理：,從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅動推理或前向鏈推理。,正向推理從用戶提供的初始已知事實出發(fā)，在知識庫,KB,中找出當前可適用的知識，構成可適用的知識集,KS,；然后按某種沖突消解策略從,KS,中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫,DB,中，作為下一步推理的已知事實。在此之后，再在知識庫中選取可適用的知識進行推理。如此重復進行這一過程，直到求得所要求的解。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略：,正向推理中，如何根據(jù)已知事實到知識庫中選取可用知識？當知識庫中有多條知識可用時應該先

11、使用那一條知識？這些問題涉及到了,知識的匹配方法,和,沖突消解策略。,正向推理的優(yōu)點：,比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設計、預測、監(jiān)控等領域的問題求解。,正向推理的缺點：,推理無明確目標，求解問題是可能會執(zhí)行許多與解無關的操作，導致推理效率較低。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略：,逆向推理：,從某個假設目標出發(fā)，逆向使用規(guī)則，亦稱為目標驅動推理或逆向鏈推理。,逆向推理首先選定一個假設目標，然后尋找支持該假設的證據(jù)，若所需的證據(jù)都能找到，則說明原假設是成立的；若找不到所需要的證據(jù)，則說明原假設不成立，此時需要另作新的假設。,推理的基本概念,推理的

12、控制策略及其分類,推理方向控制策略：,逆向推理的主要優(yōu)點：,不必尋找和使用那些與假設目標無關的信息和知識，推理過程的目標明確，有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。,逆向推理的主要缺點：,當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設目標的盲目性比較大，若選擇不好，可能需要多次提出假設，會影響系統(tǒng)效率。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略：,混合推理：,把正向推理和逆向推理結合起來所進行的推理稱為混合推理。是一種解決較復雜問題的方法。,混合推理方法的三種類型：,1.,先正向后逆向：,這種方法先進行正向推理，從已知事實出發(fā)推出部分結果，然后再用逆向推理對這些結果

13、進行證實或提高它們的可信度。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略：,混合推理方法的三種類型：,2.,先逆向后正向：,這種方法先進行逆向推理，從假設目標出發(fā)推出一些中間假設，然后再用正向推理對這些中間假設進行證實。,3.,雙向混合：,是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結合起來。,內容提要,第三章：確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結演繹推理,5.,基于規(guī)則的演繹推理,搜索策略,搜索策略,搜索的基本概念,狀態(tài)空間的搜索策略,與,/,或樹的搜索策略,搜索的完備性與效率,搜索的基本概念,搜索的基本概念,搜索是人工智

14、能中的一個基本問題，并與推理密切相關，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。,搜索的定義：,依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索。,搜索的適用情況：,不良結構或非結構化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。,搜索的基本概念,搜索的類型,按是否使用啟發(fā)式信息：,盲目搜索：,按預定的控制策略進行搜索，在搜索過程中獲得的中間信息并不改變控制策略。,啟發(fā)式搜索：,在搜索中加入了與問題有關的啟發(fā)性信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。,按問

15、題的表示方式：,狀態(tài)空間搜索：,用狀態(tài)空間法求解問題進行的搜索,與或樹搜索：,用問題歸約法求解問題進行的搜索,狀態(tài)空間的搜索策略,狀態(tài)空間的搜索策略,狀態(tài)空間搜索的基本思想,圖搜索的一般過程,狀態(tài)空間的盲目搜索,廣度優(yōu)先搜索,深度優(yōu)先搜索,代價樹搜索,狀態(tài)空間的啟發(fā)式搜索,啟發(fā)性信息和估價函數(shù),A,算法和,A*,算法,狀態(tài)空間的搜索策略,狀態(tài)空間搜索的基本思想,先把問題的初始狀態(tài)作為當前,擴展節(jié)點,對其進行,擴展,，生成一組子節(jié)點。,然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再,按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點,

16、。,重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。,所謂對一個節(jié)點進行,“擴展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。,狀態(tài)空間的搜索策略,狀態(tài)空間搜索算法的數(shù)據(jù)結構和符號約定,OPEN,表：,未擴展節(jié)點表，用于存放剛生成節(jié)點,CLOSED,表：,已擴展節(jié)點表，用于存放已經(jīng)擴展或將要擴展節(jié)點的,S,：,用表示問題的初始狀態(tài),G,：,表示搜索過程所得到的搜索圖,M,：,表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集,狀態(tài)空間的搜索策略,圖搜索的一般過程,(1),把初始節(jié)點,S,放入未擴展節(jié)點表,OPEN,表，并建立目前僅包含,S,的圖,G,；,(2),檢查,OPEN,表是否為空，若為空，則問題無解，失敗退出；,(3),把,OPEN,表的,第一個節(jié)點,取出放入已擴展節(jié)點表,CLOSED,表，并記該節(jié)點為節(jié)點,n,；,(4),考察節(jié)點,n,是否為目標節(jié)點。若是則得到了問題的解，成功退出。此時的解為追蹤圖,G,中沿著指針,（步驟,6,中設置的指針）,從,n,到初始節(jié)點,S,的路徑。,狀態(tài)空間的搜索策略,圖搜索的一般過程,(5),擴展節(jié)點,n,，生成