湘潭大學-人工智能課件-確定性推理-part1

內(nèi)容提要第二章：知識表示與推理一、知識表示方法二、確定性推理內(nèi)容提要第二章：知識表示與推理一、知識表示方法二、確定性推理內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略3.自然演繹推理4.消解演繹推理5.基于規(guī)則的演繹推理二、確定性推理內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略3.自然演繹推理4.消解演繹推理5.基于規(guī)則的演繹推理二、確定性推理推理的基本概念推理的基本概念1.什么是推理2.推理方法及其分類3.推理的控制策略及其分類推理的基本概念什么是推理所謂推理就是按某種策略由已知判斷推出另一個判斷的思維過程。在人工智能中，推理是由程序實現(xiàn)的，稱為推理機。推理的兩個基本問題推理的方法推理的控制策略推理的基本概念推理方法及其分類1.按推理的邏輯基礎分：演繹，歸納，類比歸納推理演繹推理:從已知的一般性知識出發(fā)，推出蘊含在已知知識中的適合于某種個別情況的結論。是一種由一般到個別的推理方法，其核心是三段論。假言三段論：A→B，B→C?A→C常用的三段論是由一個大前提、一個小前提和一個結論這三部分組成的。大前提是已知的一般性知識或推理過程得到的判斷；小前提是關于某種具體情況或某個具體實例的判斷；結論是由大前提推出的，并且適合于小前提的判斷。其結論是蘊含在前提中的推理的基本概念推理方法及其分類1.按推理的邏輯基礎分：演繹，歸納，類比歸納推理歸納推理：按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理。完全歸納推理：是指在進行歸納時需要考察相應事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。不完全歸納推理：是指在進行歸納時只考察了相應事物的部分對象，就得出了關于該事物的結論。推理的基本概念推理方法及其分類1.按推理的邏輯基礎分：演繹，歸納，類比歸納推理類比歸納推理：若在兩個或兩類事物有許多屬性相同或相似，則推出它們在其他屬性上也相同或相似。類比歸納推理的基礎是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關程度。推理的基本概念推理方法及其分類1.按推理的邏輯基礎分：演繹，歸納，類比歸納推理演繹推理與歸納推理的區(qū)別：演繹推理是在已知領域內(nèi)的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結論的正確性。它所得出的結論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因此它不能增殖新知識。歸納推理所推出的結論是沒有包含在前提內(nèi)容中的。這種由個別事物或現(xiàn)象推出一般性知識的過程，是增殖新知識的過程。推理的基本概念推理方法及其分類2.按推理過程所用知識的確定性分確定性推理不確定性推理3.按推理過程推出的結論是否單調(diào)增加分單調(diào)推理非單調(diào)推理4.按推理過程是否利用問題的啟發(fā)性知識分啟發(fā)式推理非啟發(fā)式推理推理的基本概念推理的控制策略及其分類推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略。推理的控制策略可分為：搜索策略推理策略推理的基本概念推理的控制策略及其分類搜索策略：在知識庫中尋找可利用的知識，從而構造一條代價較小的推理路線。主要解決推理線路、推理效果、推理效率等問題。按是否使用啟發(fā)式信息可分為：盲目搜索啟發(fā)式搜索按問題的表示方式可分為：狀態(tài)空間搜索與或樹搜索推理的基本概念推理的控制策略及其分類推理策略：包括推理方向控制策略、求解策略、限制策略、沖突消解策略等推理方向控制策略：用于確定推理的控制方向，可分為正向推理逆向推理混合推理雙向推理推理的基本概念推理的控制策略及其分類推理方向控制策略：正向推理：從已知事實出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅動推理或前向鏈推理。正向推理從用戶提供的初始已知事實出發(fā)，在知識庫KB中找出當前可適用的知識，構成可適用的知識集KS；然后按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫DB中，作為下一步推理的已知事實；在此之后，再在知識庫中選取可適用的知識進行推理。如此重復進行這一過程，直到求得所要求的解。推理的基本概念推理的控制策略及其分類推理方向控制策略：正向推理中，如何根據(jù)已知事實到知識庫中選取可用知識？當知識庫中有多條知識可用時應該先使用那一條知識？這些問題涉及到了知識的匹配方法和沖突消解策略。正向推理的優(yōu)點：比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設計、預測、監(jiān)控等領域的問題求解。正向推理的缺點：推理無明確目標，求解問題是可能會執(zhí)行許多與解無關的操作，導致推理效率較低。

推理的基本概念推理的控制策略及其分類推理方向控制策略：逆向推理：從某個假設目標出發(fā)，逆向使用規(guī)則，亦稱為目標驅動推理或逆向鏈推理。逆向推理首先選定一個假設目標，然后尋找支持該假設的證據(jù)，若所需的證據(jù)都能找到，則說明原假設是成立的；若找不到所需要的證據(jù)，則說明原假設不成立，此時需要另作新的假設。推理的基本概念推理的控制策略及其分類推理方向控制策略：逆向推理的主要優(yōu)點：不必尋找和使用那些與假設目標無關的信息和知識，推理過程的目標明確，有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。逆向推理的主要缺點：當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設目標的盲目性比較大，若選擇不好，可能需要多次提出假設，會影響系統(tǒng)效率。推理的基本概念推理的控制策略及其分類推理方向控制策略：混合推理：把正向推理和逆向推理結合起來所進行的推理稱為混合推理。是一種解決較復雜問題的方法?；旌贤评矸椒ǖ娜N類型：1.先正向后逆向：這種方法先進行正向推理，從已知事實出發(fā)推出部分結果，然后再用逆向推理對這些結果進行證實或提高它們的可信度。推理的基本概念推理的控制策略及其分類推理方向控制策略：混合推理方法的三種類型：2.先逆向后正向：這種方法先進行逆向推理，從假設目標出發(fā)推出一些中間假設，然后再用正向推理對這些中間假設進行證實。

3.雙向混合：是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結合起來。推理的基本概念推理的控制策略及其分類推理策略：包括推理方向控制策略、求解策略、限制策略、沖突消解策略等求解策略：是指僅求一個解，還是求所有解或最優(yōu)解等。限制策略：是指對推理的深度、寬度、時間、空間等進行的限制。沖突消解策略：是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結演繹推理5.基于規(guī)則的演繹推理二、確定性推理搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索的基本概念搜索的基本概念搜索是人工智能中的一個基本問題，并與推理密切相關，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。搜索的定義：依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索。搜索的適用情況：不良結構或非結構化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。搜索的基本概念搜索的類型按是否使用啟發(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ā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點。然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(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，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n先輩的那部分子節(jié)點記入集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中(6)針對M中子節(jié)點的不同情況，分別作如下處理：①對那些沒有在G中出現(xiàn)過的M成員設置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入OPEN表。（新生成的）②對那些原來已在G中出現(xiàn)過，但還沒有被擴展的M成員，確定是否需要修改它指向父節(jié)點的指針。（原生成但未擴展的）③對于那些先前已在G中出現(xiàn)過，并已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。（原生成也擴展過的）圖搜索的一般過程(7)按某種策略對OPEN表中的節(jié)點進行排序。(8)轉第(2)步。狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略圖搜索的一般過程的幾點說明：上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。各種搜索策略的主要區(qū)別在于對OPEN表中節(jié)點的排列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)點排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點排在前面。狀態(tài)空間的搜索策略圖搜索的一般過程的幾點說明：在第(6)步針對M中子節(jié)點的不同情況進行處理時，如果發(fā)生當?shù)冖诜N情況，那么，這個M中的節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定的，哪一條路經(jīng)付出的代價小，相應的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)點路徑上的代價是指這條路經(jīng)上的所有有向邊的代價之和。狀態(tài)空間的搜索策略圖搜索的一般過程的幾點說明：如果發(fā)生第③種情況，除了需要確定該子節(jié)點指向父節(jié)點的指針外，還需要確定其后繼節(jié)點指向父節(jié)點的指針。其依據(jù)也是由原始節(jié)點到該節(jié)點的路徑上的代價