西電人工智能8確定性推理part1課件

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