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

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理內容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結演繹繹推理5.基于規(guī)則則的演繹繹推理內容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結演繹繹推理5.基于規(guī)則則的演繹繹推理推理的基基本概念念推理的基基本概念念1.什么是推推理2.推理方法法及其分分類3.推理的控控制策略略及其分分類推理的基基本概念念什么是推推理所謂推理理就是按按某種策策略由已已知判斷斷推出另另一個判判斷的思思維過程程。在人工智智能中，，推理是是由程序序實現(xiàn)的的，稱為為推理機機。智能系統(tǒng)統(tǒng)的推理理過程實實際上就就是一種種思維過過程。按按照推理理過程所所用知識識的確定定性，推推理可分分為：確定性推推理（第第三章））不確定性性推理（（第四章章）推理的基基本概念念推理的兩兩個基本本問題推理的方方法：演繹？歸歸納？類類比？確確定？不不確定？？單調？？非單調調？啟發(fā)發(fā)式？非非啟發(fā)式式？推理的控控制策略略：推理的控控制策略略是指如如何使用用領域知知識使推推理過程程盡快達達到目標標的策略略。推理的控控制策略略又可分分為搜索策略略和推理策略略。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類演繹推理理:從已知的的一般性性知識出出發(fā)，推推出蘊含含在已知知知識中中的適合合于某種種個別情情況的結結論。是是一種由由一般到到個別的的推理方方法，其其核心是三三段論。歸納推理理:是一種由由個別到到一般的的推理方方法。類比歸納納推理:是指在兩兩個或兩兩類事物物有許多多屬性都都相同或或相似的的基礎上上，推出出它們在在其他屬屬性上也也相同或或相似的的一種歸歸納推理理。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類演繹推理理：假言三段段論：A→B，B→C??A→C常用的三三段論是是由一個個大前提、一個小前前提和一個結論論這三部分分組成的的。大前提是是已知的的一般性性知識或或推理過過程得到到的判斷斷；小前提是是關于某某種具體體情況或或某個具具體實例例的判斷斷；結論是由由大前提提推出的的，并且且適合于于小前提提的判斷斷。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類演繹推理理：例如，有有如下三三個判斷斷：①計計算機系系的學生生都會編編程序；；（（一般般性知識識）②程程強是計計算機系系的一位位學生；；（（具體體情況））③程程強會編編程序。。（結論論）這是一個個三段論論推理。。其中，，①是大大前提，，②是小小前提；；③是經經演繹推推出來的的結論。?？梢?，其結論是是蘊含在在大前提提中的推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類歸納推理理：按照所選選事例的的廣泛性可分為完全歸納納推理和不完全歸歸納推理理。完全歸納納推理：：是指在進進行歸納納時需要要考察相相應事物物的全部對象象，并根據(jù)據(jù)這些對對象是否否都具有有某種屬屬性，推推出該類類事物是是否具有有此屬性性。不完全歸歸納推理理：是指在進進行歸納納時只考考察了相相應事物物的部分對象象，就得出出了關于于該事物物的結論論。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類歸納推理理：按照推理理所使用用的方法可分為枚舉、類比、統(tǒng)計和差異歸納納推理等。枚舉歸納納推理：：是指在進進行歸納納時，如如果已知知某類事事物的有限可數(shù)數(shù)個具體體事物都具有某某種屬性性，則可可推出該該類事物物都具有有此種屬屬性。例如，設設有如下下事例：：王強是計計算機系系學生，，他會編編程序；；高華是是計算機機系學生生，她會會編程序序；……當這些具具體事例例足夠多多時，就就可歸納納出一個個一般性性的知識識：凡是是計算機機系的學學生，就就一定會會編程序序。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類類比歸納納推理：：若在兩個個或兩類類事物有有許多屬屬性相同同或相似似，則推推出它們們在其他他屬性上上也相同同或相似似。例如：設A、B分別是兩兩類事物物的集合合：A={a1,a2,…}，B={b1,b2,…}并設ai與bi總是成對對出現(xiàn)，，且當ai有屬性P時，bi就有屬性性Q與此對應應，即P(ai)→Q((bi)（i=1,,2,……..）。當A與B中有一新新的元素素對出現(xiàn)現(xiàn)時，若若已知a'有屬性P，b'有屬性Q則類比歸歸納出結結論：P(a'')→Q(b')推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類類比歸納納推理：：類比歸納納推理的的基礎是是相似原理理，其可靠靠程度取取決于兩兩個或兩兩類事物物的相似似程度以以及這兩兩個或兩兩類事物物的相同同屬性與與推出的的那個屬屬性之間間的相關關程度。。推理的基基本概念念推理方法法及其分分類1.按推理的的邏輯基基礎分類類演繹推理理與歸納納推理的的區(qū)別：：演繹推理理是在已已知領域域內的一一般性知知識的前前提下，，通過演演繹求解解一個具具體問題題或者證證明一個個結論的的正確性性。它所得出出的結論論實際上上早已蘊蘊含在一一般性知知識的前前提中，演繹推推理只不不過是將將已有事事實揭露露出來，，因此它不能增增殖新知知識。歸納推理理所推出出的結論論是沒有有包含在在前提內內容中的的。這種由由個別事事物或現(xiàn)現(xiàn)象推出出一般性性知識的的過程，，是增殖新新知識的的過程。推理的基基本概念念推理方法法及其分分類2.按推理過過程所用用知識的的確定性性分類確定性推推理不確定性性推理3.按推理過過程推出出的結論論是否單單調增加加分類單調推理理非單調推推理4.按推理過過程是否否利用問問題的啟啟發(fā)性知知識分類類啟發(fā)式推推理非啟發(fā)式式推理推理的基基本概念念推理的控控制策略略及其分分類推理過程程不僅依依賴于所所用的推推理方法法，同時時也依賴賴于推理理的控制制策略。。推理的控控制策略略是指如如何使用用領域知知識使推推理過程程盡快達達到目標標的策略略。推理的控控制策略略可分為為：搜索策略略推理策略略推理的基基本概念念推理的控控制策略略及其分分類搜索策略略：在知識庫庫中尋找找可利用用的知識識，從而而構造一一條代價價較小的的推理路路線。主主要解決決推理線線路、推推理效果果、推理理效率等等問題。。按是否使使用啟發(fā)發(fā)式信息息可分為為：盲目搜索索啟發(fā)式搜搜索按問題的的表示方方式可分分為：狀態(tài)空間間搜索與或樹搜搜索推理的基基本概念念推理的控控制策略略及其分分類推理策略略：包括推理理方向控控制策略略、求解解策略、、限制策策略、沖沖突消解解策略等等推理方向向控制策策略：用于確定定推理的的控制方方向，可可分為正正向推理理、逆向向推理、、混合推推理及雙雙向推理理。求解策略略：是指僅求求一個解解，還是是求所有有解或最最優(yōu)解等等。限制策略略：是指對推推理的深深度、寬寬度、時時間、空空間等進進行的限限制。沖突消解解策略：：是指當推推理過程程有多條條知識可可用時，，如何從從這多條條可用知知識中選選出一條條最佳知知識用于于推理的的策略。。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：正向推理理：從已知事事實出發(fā)發(fā)、正向向使用推推理規(guī)則則，亦稱稱為數(shù)據(jù)據(jù)驅動推推理或前前向鏈推推理。正向推理理從用戶戶提供的的初始已已知事實實出發(fā)，，在知識識庫KB中找出當當前可適適用的知知識，構構成可適適用的知知識集KS；然后按按某種沖沖突消解解策略從從KS中選出一一條知識識進行推推理，并并將推出出的新事事實加入入到數(shù)據(jù)據(jù)庫DB中，作為為下一步步推理的的已知事事實。在在此之后后，再在在知識庫庫中選取取可適用用的知識識進行推推理。如如此重復復進行這這一過程程，直到到求得所所要求的的解。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：正向推理理中，如如何根據(jù)據(jù)已知事事實到知知識庫中中選取可可用知識識？當知知識庫中中有多條條知識可可用時應應該先使使用那一一條知識識？這些些問題涉涉及到了了知識的匹匹配方法法和沖突消解解策略。。正向推理理的優(yōu)點點：比較直觀觀，允許許用戶主主動提供供有用的的事實信信息，適適合于診診斷、設設計、預預測、監(jiān)監(jiān)控等領領域的問問題求解解。正向推理理的缺點點：推理無明明確目標標，求解解問題是是可能會會執(zhí)行許許多與解解無關的的操作，，導致推推理效率率較低。。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：逆向推理理：從某個假假設目標標出發(fā)，，逆向使使用規(guī)則則，亦稱稱為目標標驅動推推理或逆逆向鏈推推理。逆向推理理首先選選定一個個假設目目標，然然后尋找找支持該該假設的的證據(jù)，，若所需需的證據(jù)據(jù)都能找找到，則則說明原原假設是是成立的的；若找找不到所所需要的的證據(jù)，，則說明明原假設設不成立立，此時時需要另另作新的的假設。。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：逆向推理理的主要要優(yōu)點：：不必尋找找和使用用那些與與假設目目標無關關的信息息和知識識，推理理過程的的目標明明確，有有利于向向用戶提提供解釋釋，在診診斷性專專家系統(tǒng)統(tǒng)中較為為有效。。逆向推理理的主要要缺點：：當用戶對對解的情情況認識識不請時時，由系系統(tǒng)自主主選擇假假設目標標的盲目目性比較較大，若若選擇不不好，可可能需要要多次提提出假設設，會影影響系統(tǒng)統(tǒng)效率。。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：混合推理理：把正向推推理和逆逆向推理理結合起起來所進進行的推推理稱為為混合推推理。是是一種解解決較復復雜問題題的方法法。混合推理理方法的的三種類類型：1.先正向后后逆向：：這種方法法先進行行正向推推理，從從已知事事實出發(fā)發(fā)推出部部分結果果，然后后再用逆逆向推理理對這些些結果進進行證實實或提高高它們的的可信度度。推理的基基本概念念推理的控控制策略略及其分分類推理方向向控制策策略：混合推理理方法的的三種類類型：2.先逆向后后正向：：這種方法法先進行行逆向推推理，從從假設目目標出發(fā)發(fā)推出一一些中間間假設，，然后再再用正向向推理對對這些中中間假設設進行證證實。3.雙向混合合：是指正向向推理和和逆向推推理同時時進行，，使推理理過程在在中間的的某一步步結合起起來。內容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結演繹繹推理5.基于規(guī)則則的演繹繹推理搜索策略略搜索策略略搜索的基基本概念念狀態(tài)空間間的搜索索策略與/或樹的搜搜索策略略搜索的完完備性與與效率搜索的基基本概念念搜索的基基本概念念搜索是人人工智能能中的一一個基本本問題，，并與推推理密切切相關，，搜索策策略的優(yōu)優(yōu)劣，將將直接影影響到智智能系統(tǒng)統(tǒng)的性能能與推理理效率。。搜索的定定義：依靠經驗驗，利用用已有知知識，根根據(jù)問題題的實際際情況，，不斷尋尋找可利利用知識識，從而而構造一一條代價價最小的的推理路路線，使使問題得得以解決決的過程程稱為搜搜索。搜索的適適用情況況：不良結構構或非結結構化問問題；難難以獲得得求解所所需的全全部信息息；更沒沒有現(xiàn)成成的算法法可供求求解使用用。搜索的基基本概念念搜索的類類型按是否使使用啟發(fā)發(fā)式信息息：盲目搜索索：按預定的的控制策策略進行行搜索，，在搜索索過程中中獲得的的中間信信息并不不改變控控制策略略。啟發(fā)式搜搜索：在搜索中中加入了了與問題題有關的的啟發(fā)性性信息，，用于指指導搜索索朝著最最有希望望的方向向前進，，加速問問題的求求解過程程并找到到最優(yōu)解解。按問題的的表示方方式：狀態(tài)空間間搜索：：用狀態(tài)空空間法求求解問題題進行的的搜索與或樹搜搜索：用問題歸歸約法求求解問題題進行的的搜索狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想圖搜索的的一般過過程狀態(tài)空間間的盲目目搜索廣度優(yōu)先先搜索深度優(yōu)先先搜索代價樹搜搜索狀態(tài)空間間的啟發(fā)發(fā)式搜索索啟發(fā)性信信息和估估價函數(shù)數(shù)A算法和A*算法狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想先把問題題的初始始狀態(tài)作作為當前前擴展節(jié)點點對其進行行擴展，生成一一組子節(jié)節(jié)點。然后檢查查問題的的目標狀狀態(tài)是否否出現(xiàn)在在這些子子節(jié)點中中。若出出現(xiàn)，則則搜索成成功，找找到了問問題的解解；若沒沒出現(xiàn)，，則再按照某種種搜索策策略從已已生成的的子節(jié)點點中選擇擇一個節(jié)節(jié)點作為為當前擴擴展節(jié)點點。重復上述述過程，，直到目目標狀態(tài)態(tài)出現(xiàn)在在子節(jié)點點中或者者沒有可可供操作作的節(jié)點點為止。。所謂對一一個節(jié)點點進行“擴展””是指對對該節(jié)點點用某個個可用操操作進行行作用，，生成該該節(jié)點的的一組子子節(jié)點。。狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索算算法的數(shù)數(shù)據(jù)結構構和符號號約定OPEN表：未擴展節(jié)節(jié)點表，，用于存存放剛生生成節(jié)點點CLOSED表：已擴展節(jié)節(jié)點表，，用于存存放已經經擴展或或將要擴擴展節(jié)點點的S：用表示問問題的初初始狀態(tài)態(tài)G：表示搜索索過程所所得到的的搜索圖圖M：表示當前前擴展節(jié)節(jié)點新生生成的且且不為自自己先輩輩的子節(jié)節(jié)點集狀態(tài)空間間的搜索索策略圖搜索的的一般過過程(1)把初始節(jié)節(jié)點S放入未擴擴展節(jié)點點表OPEN表，并建建立目前前僅包含含S的圖G；(2)檢查OPEN表是否為為空，若若為空，，則問題題無解，，失敗退退出；(3)把OPEN表的第一個節(jié)節(jié)點取出放入入已擴展展節(jié)點表表CLOSED表，并記記該節(jié)點點為節(jié)點點n；(4)考察節(jié)點點n是否為目目標節(jié)點點。若是是則得到到了問題題的解，，成功退退出。此此時的解解為追蹤蹤圖G中沿著指指針（步驟6中設置的的指針））從n到初始節(jié)節(jié)點S的路徑。。狀態(tài)空間間的搜索索策略圖搜索的的一般過過程(5)擴展節(jié)點點n，生成一一組子節(jié)節(jié)點。把把這些子子節(jié)點中中不是節(jié)節(jié)點n先輩的那那部分子子節(jié)點記記入集合合M，并把這這些子節(jié)節(jié)點作為為節(jié)點n的子節(jié)點點加入G中(6)針對M中子節(jié)點點的不同同情況，，分別作作如下處處理：①對那那些沒有有在G中出現(xiàn)過過的M成員設置置一個指指向其父父節(jié)點（（即節(jié)點點n）的指針針，并把把它放入入OPEN表。（新新生成的的）②對那那些原來來已在G中出現(xiàn)過過，但還還沒有被被擴展的的M成員，確確定是否否需要修修改它指指向父節(jié)節(jié)點的指指針。（（原生成成但未擴擴展的））③對于于那些先先前已在在G中出現(xiàn)過過，并已已經擴展展了的M成員，確確定是否否需要修修改其后后繼節(jié)點點指向父父節(jié)點的的指針。。（原生生成也擴擴展過的的）圖搜索的的一般過過程(7)按某種策策略對OPEN表中的節(jié)節(jié)點進行行排序。。(8)轉第(2)步。狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略圖搜索的的一般過過程的幾幾點說明明：上述過程程是狀態(tài)態(tài)空間的的一般圖圖搜索算算法，它它具有通通用性，，后面所所要討論論的各種種狀態(tài)空空間搜索索策略都都是上述述過程的的一個特特例。各種搜索索策略的的主要區(qū)區(qū)別在于于對OPEN表中節(jié)點點的排列列順序不不同。例如，廣廣度優(yōu)先先搜索把把先生成成的子節(jié)節(jié)點排在在前面，，而深度度優(yōu)先搜搜索則把把后生成成的子節(jié)節(jié)點排在在前面。。狀態(tài)空間間的搜索索策略圖搜索的的一般過過程的幾幾點說明明：在第(6)步針對M中子節(jié)點點的不同同情況進進行處理理時，如如果發(fā)生生當?shù)冖冖诜N情況況，那么么，這個個M中的節(jié)點點究竟應應該作為為哪一個個節(jié)點的的后繼節(jié)節(jié)點呢？？一般是是由原始始節(jié)點到到該節(jié)點點路徑上上所付出出的代價價來決定定的，哪哪一條路路經付出出的代價價小，相相應的節(jié)節(jié)點就作作為它的的父節(jié)點點。所謂謂由原始始節(jié)點到到該節(jié)點點路徑上上的代價價是指這這條路經經上的所所有有向向邊的代代價之和和。如果發(fā)生生第③種種情況，，除了需需要確定定該子節(jié)節(jié)點指向向父節(jié)點點的指針針外，還還需要確確定其后后繼節(jié)點點指向父父節(jié)點的的指針。。其依據(jù)據(jù)也是由由原始節(jié)節(jié)點到該該節(jié)點的的路徑上上的代價價。狀態(tài)空間間的搜索索策略圖搜索的的一般過過程的幾幾點說明明：在搜索圖圖中，除除初始節(jié)節(jié)點外，，任意一一個節(jié)點點都含有有且只含含有一個個指向其其父節(jié)點點的指針針。因此此，由所所有節(jié)點點及其指指向父節(jié)節(jié)點的指指針所構構成的集集合是一一棵樹，，稱為搜索樹。在搜索過過程的第第(4)步，一旦旦某個被被考察的的節(jié)點是是目標節(jié)節(jié)點，則則搜索過過程成功功結束。。此時，，由初始始節(jié)點到到目標節(jié)節(jié)點路徑徑上的所所有操作作就構成成了該問問題的解解，而路路徑由第第(6)步所形成成的指向向父節(jié)點點的指針針來確定定。如果搜索索過程終終止在第第(2)步，即沒沒有達到到目標，，且OPEN表中已無無可供擴擴展的節(jié)節(jié)點，則則失敗結結束。狀態(tài)空間間的搜索索策略狀態(tài)空間間的搜索索策略狀態(tài)空間間搜索的的基本思思想圖搜索的的一般過過程狀態(tài)空間間的盲目目搜索廣度優(yōu)先先搜索深度優(yōu)先先搜索代價樹搜搜索狀態(tài)空間間的啟發(fā)發(fā)式搜索索啟發(fā)性信信息和估估價函數(shù)數(shù)A算法和A*算法廣度優(yōu)先先搜索狀態(tài)空間間的廣度度優(yōu)先搜搜索廣度優(yōu)先先搜索的的基本思思想：從初始節(jié)節(jié)點S開始逐層層向下擴擴展，在在第n層節(jié)點還還沒有全全部搜索索完之前前，不進進入第n+1層節(jié)點的的搜索。。未擴展節(jié)節(jié)點表OPEN表中的節(jié)節(jié)點總是是按進入入的先后后排序，，先進入入的節(jié)點點排在前前面，后后進入的