《西電人工智能8確定性推理part1課件》由會員分享,可在線閱讀,更多相關(guān)《西電人工智能8確定性推理part1課件(45頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
1、Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,西安電子科技大學(xué),Artificial Intelligence(AI),人工智能,主講:戚玉濤,Email,:,第三章:確定性推理,內(nèi)容提要,第三章:確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結(jié)演繹推理,5.,基于規(guī)則的演繹推理,內(nèi)容提要,第三章:確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結(jié)演
2、繹推理,5.,基于規(guī)則的演繹推理,推理的基本概念,推理的基本概念,1.,什么是推理,2.,推理方法及其分類,3.,推理的控制策略及其分類,推理的基本概念,什么是推理,所謂推理就是按某種策略由已知判斷推出另一個(gè)判斷的思維過程。,在人工智能中,推理是由程序?qū)崿F(xiàn)的,稱為推理機(jī)。,智能系統(tǒng)的推理過程實(shí)際上就是一種思維過程。按照推理過程所用知識的確定性,推理可分為:,確定性推理(第三章),不確定性推理(第四章),推理的基本概念,推理的兩個(gè)基本問題,推理的方法:,演繹?歸納?類比?確定?不確定?單調(diào)?非單調(diào)?啟發(fā)式?非啟發(fā)式?,推理的控制策略:,推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達(dá)到目標(biāo)的策
3、略。,推理的控制策略又可分為,搜索策略,和,推理策略,。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,演繹推理,:,從已知的一般性知識出發(fā),推出蘊(yùn)含在已知知識中的適合于某種個(gè)別情況的結(jié)論。是一種由一般到個(gè)別的推理方法,其,核心是三段論,。,歸納推理,:,是一種由個(gè)別到一般的推理方法。,類比歸納推理,:,是指在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上,推出它們在其他屬性上也相同或相似的一種歸納推理,。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,演繹推理:,假言三段論:,AB,,,BC AC,常用的三段論是由一個(gè),大前提,、,一個(gè)小前提,和,一個(gè)結(jié)論,這三
4、部分組成的。,大前提是已知的一般性知識或推理過程得到的判斷;,小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷;,結(jié)論是由大前提推出的,并且適合于小前提的判斷。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,演繹推理:,例如,有如下三個(gè)判斷:,計(jì)算機(jī)系的學(xué)生都會編程序;(一般性知識),程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生;(具體情況),程強(qiáng)會編程序。(結(jié)論),這是一個(gè)三段論推理。其中,是大前提,是小前提;是經(jīng)演繹推出來的結(jié)論。,可見,,其結(jié)論是蘊(yùn)含在大前提中的,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,歸納推理:,按照所選事例的,廣泛性,可分為,完全歸納推理,和,不完全歸納
5、推理,。,完全歸納推理:,是指在進(jìn)行歸納時(shí)需要考察相應(yīng)事物的,全部對象,,并根據(jù)這些對象是否都具有某種屬性,推出該類事物是否具有此屬性。,不完全歸納推理:,是指在進(jìn)行歸納時(shí)只考察了相應(yīng)事物的,部分對象,,就得出了關(guān)于該事物的結(jié)論。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,歸納推理:,按照推理所使用的,方法,可分為,枚舉,、,類比,、,統(tǒng)計(jì),和,差異歸納推理,等。,枚舉歸納推理:,是指在進(jìn)行歸納時(shí),如果已知某類事物的,有限可數(shù)個(gè)具體事物,都具有某種屬性,則可推出該類事物都具有此種屬性。,例如,設(shè)有如下事例:,王強(qiáng)是計(jì)算機(jī)系學(xué)生,他會編程序;高華是計(jì)算機(jī)系學(xué)生,她會編程序;,
6、當(dāng)這些具體事例足夠多時(shí),就可歸納出一個(gè)一般性的知識:凡是計(jì)算機(jī)系的學(xué)生,就一定會編程序。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,類比歸納推理:,若在兩個(gè)或兩類事物有許多屬性相同或相似,則推出它們在其他屬性上也相同或相似。,例如:,設(shè),A,、,B,分別是兩類事物的集合:,A=a,1,a,2,,,B=b,1,b,2,并設(shè),a,i,與,b,i,總是成對出現(xiàn),且當(dāng),a,i,有屬性,P,時(shí),,b,i,就有屬性,Q,與此對應(yīng),即,P(a,i,)Q(b,i,),(,i=1,2,.,)。,當(dāng),A,與,B,中有一新的元素對出現(xiàn)時(shí),若已知,a,有屬性,P,,,b,有屬性,Q,則類比歸納出結(jié)
7、論:,P(a)Q(b,),推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,類比歸納推理:,類比歸納推理的基礎(chǔ)是,相似原理,,其可靠程度取決于兩個(gè)或兩類事物的相似程度以及這兩個(gè)或兩類事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)程度。,推理的基本概念,推理方法及其分類,1.,按推理的邏輯基礎(chǔ)分類,演繹推理與歸納推理的區(qū)別:,演繹推理是在已知領(lǐng)域內(nèi)的一般性知識的前提下,通過演繹求解一個(gè)具體問題或者證明一個(gè)結(jié)論的正確性。,它所得出的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識的前提中,,演繹推理只不過是將已有事實(shí)揭露出來,因此,它不能增殖新知識,。,歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的,。這種由個(gè)
8、別事物或現(xiàn)象推出一般性知識的過程,,是增殖新知識的過程,。,推理的基本概念,推理方法及其分類,2.,按推理過程所用知識的確定性分類,確定性推理,不確定性推理,3.,按推理過程推出的結(jié)論是否單調(diào)增加分類,單調(diào)推理,非單調(diào)推理,4.,按推理過程是否利用問題的啟發(fā)性知識分類,啟發(fā)式推理,非啟發(fā)式推理,推理的基本概念,推理的控制策略及其分類,推理過程不僅依賴于所用的推理方法,同時(shí)也依賴于推理的控制策略。,推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達(dá)到目標(biāo)的策略,。,推理的控制策略可分為:,搜索策略,推理策略,推理的基本概念,推理的控制策略及其分類,搜索策略:,在知識庫中尋找可利用的知識,從而構(gòu)造
9、一條代價(jià)較小的推理路線。主要解決推理線路、推理效果、推理效率等問題。,按是否使用啟發(fā)式信息可分為:,盲目搜索,啟發(fā)式搜索,按問題的表示方式可分為:,狀態(tài)空間搜索,與或樹搜索,推理的基本概念,推理的控制策略及其分類,推理策略:,包括推理方向控制策略、求解策略、限制策略、沖突消解策略等,推理方向控制策略:,用于確定推理的控制方向,可分為正向推理、逆向推理、混合推理及雙向推理。,求解策略:,是指僅求一個(gè)解,還是求所有解或最優(yōu)解等。,限制策略:,是指對推理的深度、寬度、時(shí)間、空間等進(jìn)行的限制。,沖突消解策略:,是指當(dāng)推理過程有多條知識可用時(shí),如何從這多條可用知識中選出一條最佳知識用于推理的策略。,推理
10、的基本概念,推理的控制策略及其分類,推理方向控制策略:,正向推理:,從已知事實(shí)出發(fā)、正向使用推理規(guī)則,亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理。,正向推理從用戶提供的初始已知事實(shí)出發(fā),在知識庫,KB,中找出當(dāng)前可適用的知識,構(gòu)成可適用的知識集,KS,;然后按某種沖突消解策略從,KS,中選出一條知識進(jìn)行推理,并將推出的新事實(shí)加入到數(shù)據(jù)庫,DB,中,作為下一步推理的已知事實(shí)。在此之后,再在知識庫中選取可適用的知識進(jìn)行推理。如此重復(fù)進(jìn)行這一過程,直到求得所要求的解。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略:,正向推理中,如何根據(jù)已知事實(shí)到知識庫中選取可用知識?當(dāng)知識庫中有多條知識可用時(shí)應(yīng)該先
11、使用那一條知識?這些問題涉及到了,知識的匹配方法,和,沖突消解策略。,正向推理的優(yōu)點(diǎn):,比較直觀,允許用戶主動(dòng)提供有用的事實(shí)信息,適合于診斷、設(shè)計(jì)、預(yù)測、監(jiān)控等領(lǐng)域的問題求解。,正向推理的缺點(diǎn):,推理無明確目標(biāo),求解問題是可能會執(zhí)行許多與解無關(guān)的操作,導(dǎo)致推理效率較低。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略:,逆向推理:,從某個(gè)假設(shè)目標(biāo)出發(fā),逆向使用規(guī)則,亦稱為目標(biāo)驅(qū)動(dòng)推理或逆向鏈推理。,逆向推理首先選定一個(gè)假設(shè)目標(biāo),然后尋找支持該假設(shè)的證據(jù),若所需的證據(jù)都能找到,則說明原假設(shè)是成立的;若找不到所需要的證據(jù),則說明原假設(shè)不成立,此時(shí)需要另作新的假設(shè)。,推理的基本概念,推理的
12、控制策略及其分類,推理方向控制策略:,逆向推理的主要優(yōu)點(diǎn):,不必尋找和使用那些與假設(shè)目標(biāo)無關(guān)的信息和知識,推理過程的目標(biāo)明確,有利于向用戶提供解釋,在診斷性專家系統(tǒng)中較為有效。,逆向推理的主要缺點(diǎn):,當(dāng)用戶對解的情況認(rèn)識不請時(shí),由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大,若選擇不好,可能需要多次提出假設(shè),會影響系統(tǒng)效率。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略:,混合推理:,把正向推理和逆向推理結(jié)合起來所進(jìn)行的推理稱為混合推理。是一種解決較復(fù)雜問題的方法。,混合推理方法的三種類型:,1.,先正向后逆向:,這種方法先進(jìn)行正向推理,從已知事實(shí)出發(fā)推出部分結(jié)果,然后再用逆向推理對這些結(jié)果
13、進(jìn)行證實(shí)或提高它們的可信度。,推理的基本概念,推理的控制策略及其分類,推理方向控制策略:,混合推理方法的三種類型:,2.,先逆向后正向:,這種方法先進(jìn)行逆向推理,從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè),然后再用正向推理對這些中間假設(shè)進(jìn)行證實(shí)。,3.,雙向混合:,是指正向推理和逆向推理同時(shí)進(jìn)行,使推理過程在中間的某一步結(jié)合起來。,內(nèi)容提要,第三章:確定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演繹推理,4.,歸結(jié)演繹推理,5.,基于規(guī)則的演繹推理,搜索策略,搜索策略,搜索的基本概念,狀態(tài)空間的搜索策略,與,/,或樹的搜索策略,搜索的完備性與效率,搜索的基本概念,搜索的基本概念,搜索是人工智
14、能中的一個(gè)基本問題,并與推理密切相關(guān),搜索策略的優(yōu)劣,將直接影響到智能系統(tǒng)的性能與推理效率。,搜索的定義:,依靠經(jīng)驗(yàn),利用已有知識,根據(jù)問題的實(shí)際情況,不斷尋找可利用知識,從而構(gòu)造一條代價(jià)最小的推理路線,使問題得以解決的過程稱為搜索。,搜索的適用情況:,不良結(jié)構(gòu)或非結(jié)構(gòu)化問題;難以獲得求解所需的全部信息;更沒有現(xiàn)成的算法可供求解使用。,搜索的基本概念,搜索的類型,按是否使用啟發(fā)式信息:,盲目搜索:,按預(yù)定的控制策略進(jìn)行搜索,在搜索過程中獲得的中間信息并不改變控制策略。,啟發(fā)式搜索:,在搜索中加入了與問題有關(guān)的啟發(fā)性信息,用于指導(dǎo)搜索朝著最有希望的方向前進(jìn),加速問題的求解過程并找到最優(yōu)解。,按問
15、題的表示方式:,狀態(tài)空間搜索:,用狀態(tài)空間法求解問題進(jìn)行的搜索,與或樹搜索:,用問題歸約法求解問題進(jìn)行的搜索,狀態(tài)空間的搜索策略,狀態(tài)空間的搜索策略,狀態(tài)空間搜索的基本思想,圖搜索的一般過程,狀態(tài)空間的盲目搜索,廣度優(yōu)先搜索,深度優(yōu)先搜索,代價(jià)樹搜索,狀態(tài)空間的啟發(fā)式搜索,啟發(fā)性信息和估價(jià)函數(shù),A,算法和,A*,算法,狀態(tài)空間的搜索策略,狀態(tài)空間搜索的基本思想,先把問題的初始狀態(tài)作為當(dāng)前,擴(kuò)展節(jié)點(diǎn),對其進(jìn)行,擴(kuò)展,,生成一組子節(jié)點(diǎn)。,然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn),則搜索成功,找到了問題的解;若沒出現(xiàn),則再,按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn),
16、。,重復(fù)上述過程,直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。,所謂對一個(gè)節(jié)點(diǎn)進(jìn)行,“擴(kuò)展”是指對該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用,生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。,狀態(tài)空間的搜索策略,狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定,OPEN,表:,未擴(kuò)展節(jié)點(diǎn)表,用于存放剛生成節(jié)點(diǎn),CLOSED,表:,已擴(kuò)展節(jié)點(diǎn)表,用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展節(jié)點(diǎn)的,S,:,用表示問題的初始狀態(tài),G,:,表示搜索過程所得到的搜索圖,M,:,表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集,狀態(tài)空間的搜索策略,圖搜索的一般過程,(1),把初始節(jié)點(diǎn),S,放入未擴(kuò)展節(jié)點(diǎn)表,OPEN,表,并建立目前僅包含,S,的圖,G,;,(2),檢查,OPEN,表是否為空,若為空,則問題無解,失敗退出;,(3),把,OPEN,表的,第一個(gè)節(jié)點(diǎn),取出放入已擴(kuò)展節(jié)點(diǎn)表,CLOSED,表,并記該節(jié)點(diǎn)為節(jié)點(diǎn),n,;,(4),考察節(jié)點(diǎn),n,是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解,成功退出。此時(shí)的解為追蹤圖,G,中沿著指針,(步驟,6,中設(shè)置的指針),從,n,到初始節(jié)點(diǎn),S,的路徑。,狀態(tài)空間的搜索策略,圖搜索的一般過程,(5),擴(kuò)展節(jié)點(diǎn),n,,生成