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

ArtificialIntelligence(AI)

人工智能主講：戚玉濤：qi_yutao@163第三章：確定性推理內(nèi)容提要第三章：確定性推理1.推理的根本概念2.搜索戰(zhàn)略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)那么的演繹推理內(nèi)容提要第三章：確定性推理1.推理的根本概念2.搜索戰(zhàn)略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)那么的演繹推理推理的根本概念推理的根本概念1.什么是推理2.推理方法及其分類3.推理的控制戰(zhàn)略及其分類推理的根本概念什么是推理所謂推理就是按某種戰(zhàn)略由知判別推出另一個(gè)判別的思想過(guò)程。在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。智能系統(tǒng)的推理過(guò)程實(shí)踐上就是一種思想過(guò)程。按照推理過(guò)程所用知識(shí)確實(shí)定性，推理可分為：確定性推理〔第三章〕不確定性推理〔第四章〕推理的根本概念推理的兩個(gè)根本問題推理的方法：演繹？歸納？類比？確定？不確定？單調(diào)？非單調(diào)？啟發(fā)式？非啟發(fā)式？推理的控制戰(zhàn)略：推理的控制戰(zhàn)略是指如何運(yùn)用領(lǐng)域知識(shí)使推理過(guò)程盡快到達(dá)目的的戰(zhàn)略。推理的控制戰(zhàn)略又可分為搜索戰(zhàn)略和推理戰(zhàn)略。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類演繹推理:從知的普通性知識(shí)出發(fā)，推出蘊(yùn)含在知知識(shí)中的適宜于某種個(gè)別情況的結(jié)論。是一種由普通到個(gè)別的推理方法，其中心是三段論。歸納推理:是一種由個(gè)別到普通的推理方法。類比歸納推理:是指在兩個(gè)或兩類事物有許多屬性都一樣或類似的根底上，推出它們?cè)谄渌麑傩陨弦惨粯踊蝾愃频囊环N歸納推理。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類演繹推理：假言三段論：A→B，B→C?A→C常用的三段論是由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論這三部分組成的。大前提是知的普通性知識(shí)或推理過(guò)程得到的判別；小前提是關(guān)于某種詳細(xì)情況或某個(gè)詳細(xì)實(shí)例的判別；結(jié)論是由大前提推出的，并且適宜于小前提的判別。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類演繹推理：例如，有如下三個(gè)判別：①計(jì)算機(jī)系的學(xué)生都會(huì)編程序；〔普通性知識(shí)〕②程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；〔詳細(xì)情況〕③程強(qiáng)會(huì)編程序?！步Y(jié)論〕這是一個(gè)三段論推理。其中，①是大前提，②是小前提；③是經(jīng)演繹推出來(lái)的結(jié)論。可見，其結(jié)論是蘊(yùn)含在大前提中的推理的根本概念推理方法及其分類1.按推理的邏輯根底分類歸納推理：按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理。完全歸納推理：是指在進(jìn)展歸納時(shí)需求調(diào)查相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象能否都具有某種屬性，推出該類事物能否具有此屬性。不完全歸納推理：是指在進(jìn)展歸納時(shí)只調(diào)查了相應(yīng)事物的部分對(duì)象，就得出了關(guān)于該事物的結(jié)論。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類歸納推理：按照推理所運(yùn)用的方法可分為枚舉、類比、統(tǒng)計(jì)和差別歸納推理等。枚舉歸納推理：是指在進(jìn)展歸納時(shí)，假設(shè)知某類事物的有限可數(shù)個(gè)詳細(xì)事物都具有某種屬性，那么可推出該類事物都具有此種屬性。例如，設(shè)有如下事例：王強(qiáng)是計(jì)算機(jī)系學(xué)生，他會(huì)編程序；高華是計(jì)算機(jī)系學(xué)生，她會(huì)編程序；……當(dāng)這些詳細(xì)事例足夠多時(shí)，就可歸納出一個(gè)普通性的知識(shí)：凡是計(jì)算機(jī)系的學(xué)生，就一定會(huì)編程序。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類類比歸納推理：假設(shè)在兩個(gè)或兩類事物有許多屬性一樣或類似，那么推出它們?cè)谄渌麑傩陨弦惨粯踊蝾愃?。例如：設(shè)A、B分別是兩類事物的集合：A={a1,a2,…}，B={b1,b2,…}并設(shè)ai與bi總是成對(duì)出現(xiàn)，且當(dāng)ai有屬性P時(shí)，bi就有屬性Q與此對(duì)應(yīng)，即P(ai)→Q(bi)〔i=1,2,…..〕。當(dāng)A與B中有一新的元素對(duì)出現(xiàn)時(shí)，假設(shè)知a'有屬性P，b'有屬性Q那么類比歸納出結(jié)論：P(a')→Q(b')推理的根本概念推理方法及其分類1.按推理的邏輯根底分類類比歸納推理：類比歸納推理的根底是類似原理，其可靠程度取決于兩個(gè)或兩類事物的類似程度以及這兩個(gè)或兩類事物的一樣屬性與推出的那個(gè)屬性之間的相關(guān)程度。推理的根本概念推理方法及其分類1.按推理的邏輯根底分類演繹推理與歸納推理的區(qū)別：演繹推理是在知領(lǐng)域內(nèi)的普通性知識(shí)的前提下，經(jīng)過(guò)演繹求解一個(gè)詳細(xì)問題或者證明一個(gè)結(jié)論的正確性。它所得出的結(jié)論實(shí)踐上早已蘊(yùn)含在普通性知識(shí)的前提中，演繹推理只不過(guò)是將已有現(xiàn)實(shí)揭顯露來(lái)，因此它不能增殖新知識(shí)。歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的。這種由個(gè)別事物或景象推出普通性知識(shí)的過(guò)程，是增殖新知識(shí)的過(guò)程。推理的根本概念推理方法及其分類2.按推理過(guò)程所用知識(shí)確實(shí)定性分類確定性推理不確定性推理3.按推理過(guò)程推出的結(jié)論能否單調(diào)添加分類單調(diào)推理非單調(diào)推理4.按推理過(guò)程能否利用問題的啟發(fā)性知識(shí)分類啟發(fā)式推理非啟發(fā)式推理推理的根本概念推理的控制戰(zhàn)略及其分類推理過(guò)程不僅依賴于所用的推理方法，同時(shí)也依賴于推理的控制戰(zhàn)略。推理的控制戰(zhàn)略是指如何運(yùn)用領(lǐng)域知識(shí)使推理過(guò)程盡快到達(dá)目的的戰(zhàn)略。推理的控制戰(zhàn)略可分為：搜索戰(zhàn)略推理戰(zhàn)略推理的根本概念推理的控制戰(zhàn)略及其分類搜索戰(zhàn)略：在知識(shí)庫(kù)中尋覓可利用的知識(shí)，從而構(gòu)造一條代價(jià)較小的推理道路。主要處理推理線路、推理效果、推理效率等問題。按能否運(yùn)用啟發(fā)式信息可分為：盲目搜索啟發(fā)式搜索按問題的表示方式可分為：形狀空間搜索與或樹搜索推理的根本概念推理的控制戰(zhàn)略及其分類推理戰(zhàn)略：包括推理方向控制戰(zhàn)略、求解戰(zhàn)略、限制戰(zhàn)略、沖突消解戰(zhàn)略等推理方向控制戰(zhàn)略：用于確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙向推理。求解戰(zhàn)略：是指僅求一個(gè)解，還是求一切解或最優(yōu)解等。限制戰(zhàn)略：是指對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)展的限制。沖突消解戰(zhàn)略：是指當(dāng)推理過(guò)程有多條知識(shí)可用時(shí)，如何從這多條可用知識(shí)中選出一條最正確知識(shí)用于推理的戰(zhàn)略。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：正向推理：從知現(xiàn)實(shí)出發(fā)、正向運(yùn)用推理規(guī)那么，亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理。正向推理從用戶提供的初始知現(xiàn)實(shí)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用的知識(shí)集KS；然后按某種沖突消解戰(zhàn)略從KS中選出一條知識(shí)進(jìn)展推理，并將推出的新現(xiàn)實(shí)參與到數(shù)據(jù)庫(kù)DB中，作為下一步推理的知現(xiàn)實(shí)。在此之后，再在知識(shí)庫(kù)中選取可適用的知識(shí)進(jìn)展推理。如此反復(fù)進(jìn)展這一過(guò)程，直到求得所要求的解。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：正向推理中，如何根據(jù)知現(xiàn)實(shí)到知識(shí)庫(kù)中選取可用知識(shí)？當(dāng)知識(shí)庫(kù)中有多條知識(shí)可用時(shí)應(yīng)該先運(yùn)用那一條知識(shí)？這些問題涉及到了知識(shí)的匹配方法和沖突消解戰(zhàn)略。正向推理的優(yōu)點(diǎn)：比較直觀，允許用戶自動(dòng)提供有用的現(xiàn)實(shí)信息，適宜于診斷、設(shè)計(jì)、預(yù)測(cè)、監(jiān)控等領(lǐng)域的問題求解。正向推理的缺陷：推理無(wú)明確目的，求解問題是能夠會(huì)執(zhí)行許多與解無(wú)關(guān)的操作，導(dǎo)致推理效率較低。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：逆向推理：從某個(gè)假設(shè)目的出發(fā)，逆向運(yùn)用規(guī)那么，亦稱為目的驅(qū)動(dòng)推理或逆向鏈推理。逆向推理首先選定一個(gè)假設(shè)目的，然后尋覓支持該假設(shè)的證據(jù)，假設(shè)所需的證據(jù)都能找到，那么闡明原假設(shè)是成立的；假設(shè)找不到所需求的證據(jù)，那么闡明原假設(shè)不成立，此時(shí)需求另作新的假設(shè)。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：逆向推理的主要優(yōu)點(diǎn)：不用尋覓和運(yùn)用那些與假設(shè)目的無(wú)關(guān)的信息和知識(shí)，推理過(guò)程的目的明確，有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。逆向推理的主要缺陷：當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不請(qǐng)時(shí)，由系統(tǒng)自主選擇假設(shè)目的的盲目性比較大，假設(shè)選擇不好，能夠需求多次提出假設(shè)，會(huì)影響系統(tǒng)效率。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：混合推理：把正向推理和逆向推理結(jié)合起來(lái)所進(jìn)展的推理稱為混合推理。是一種處理較復(fù)雜問題的方法。混合推理方法的三種類型：1.先正向后逆向：這種方法先進(jìn)展正向推理，從知現(xiàn)實(shí)出發(fā)推出部分結(jié)果，然后再用逆向推理對(duì)這些結(jié)果進(jìn)展證明或提高它們的可信度。推理的根本概念推理的控制戰(zhàn)略及其分類推理方向控制戰(zhàn)略：混合推理方法的三種類型：2.先逆向后正向：這種方法先進(jìn)展逆向推理，從假設(shè)目的出發(fā)推出一些中間假設(shè)，然后再用正向推理對(duì)這些中間假設(shè)進(jìn)展證明。3.雙向混合：是指正向推理和逆向推理同時(shí)進(jìn)展，使推理過(guò)程在中間的某一步結(jié)合起來(lái)。內(nèi)容提要第三章：確定性推理1.推理的根本概念2.搜索戰(zhàn)略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)那么的演繹推理搜索戰(zhàn)略搜索戰(zhàn)略搜索的根本概念形狀空間的搜索戰(zhàn)略與/或樹的搜索戰(zhàn)略搜索的完備性與效率搜索的根本概念搜索的根本概念搜索是人工智能中的一個(gè)根本問題，并與推理親密相關(guān)，搜索戰(zhàn)略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。搜索的定義：依托閱歷，利用已有知識(shí)，根據(jù)問題的實(shí)踐情況，不斷尋覓可利用知識(shí)，從而構(gòu)造一條代價(jià)最小的推理道路，使問題得以處理的過(guò)程稱為搜索。搜索的適用情況：不良構(gòu)造或非構(gòu)造化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解運(yùn)用。搜索的根本概念搜索的類型按能否運(yùn)用啟發(fā)式信息：盲目搜索：按預(yù)定的控制戰(zhàn)略進(jìn)展搜索，在搜索過(guò)程中獲得的中間信息并不改動(dòng)控制戰(zhàn)略。啟發(fā)式搜索：在搜索中參與了與問題有關(guān)的啟發(fā)性信息，用于指點(diǎn)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過(guò)程并找到最優(yōu)解。按問題的表示方式：形狀空間搜索：用形狀空間法求解問題進(jìn)展的搜索與或樹搜索：用問題歸約法求解問題進(jìn)展的搜索形狀空間的搜索戰(zhàn)略形狀空間的搜索戰(zhàn)略形狀空間搜索的根本思想圖搜索的普經(jīng)過(guò)程形狀空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹搜索形狀空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法形狀空間的搜索戰(zhàn)略形狀空間搜索的根本思想先把問題的初始形狀作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)展擴(kuò)展，生成一組子節(jié)點(diǎn)。然后檢查詢題的目的形狀能否出如今這些子節(jié)點(diǎn)中。假設(shè)出現(xiàn)，那么搜索勝利，找到了問題的解；假設(shè)沒出現(xiàn)，那么再按照某種搜索戰(zhàn)略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。反復(fù)上述過(guò)程，直到目的形狀出如今子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)展“擴(kuò)展〞是指對(duì)該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)展作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。形狀空間的搜索戰(zhàn)略形狀空間搜索算法的數(shù)據(jù)構(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：用表示問題的初始形狀G：表示搜索過(guò)程所得到的搜索圖M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為本人先輩的子節(jié)點(diǎn)集形狀空間的搜索戰(zhàn)略圖搜索的普經(jīng)過(guò)程(1)把初始節(jié)點(diǎn)S放入未擴(kuò)展節(jié)點(diǎn)表OPEN表，并建立目前僅包含S的圖G；(2)檢查OPEN表能否為空，假設(shè)為空，那么問題無(wú)解，失敗退出；(3)把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入已擴(kuò)展節(jié)點(diǎn)表CLOSED表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；(4)調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是那么得到了問題的解，勝利退出。此時(shí)的解為追蹤圖G中沿著指針〔步驟6中設(shè)置的指針〕從n到初始節(jié)點(diǎn)S的途徑。形狀空間的搜索戰(zhàn)略圖搜索的普經(jīng)過(guò)程(5)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)n先輩的那部分子節(jié)點(diǎn)記入集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)參與G中(6)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別作如下處置：①對(duì)那些沒有在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)〔即節(jié)點(diǎn)n〕的指針，并把它放入OPEN表?！残律傻摹尝趯?duì)那些原來(lái)已在G中出現(xiàn)過(guò)，但還沒有被擴(kuò)展的M成員，確定能否需求修正它指向父節(jié)點(diǎn)的指針。〔原生成但未擴(kuò)展的〕③對(duì)于那些先前已在G中出現(xiàn)過(guò)，并曾經(jīng)擴(kuò)展了的M成員，確定能否需求修正其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針?！苍梢矓U(kuò)展過(guò)的〕圖搜索的普經(jīng)過(guò)程(7)按某種戰(zhàn)略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)展排序。(8)轉(zhuǎn)第(2)步。形狀空間的搜索戰(zhàn)略形狀空間的搜索戰(zhàn)略圖搜索的普經(jīng)過(guò)程的幾點(diǎn)闡明：上述過(guò)程是形狀空間的普通圖搜索算法，它具有通用性，后面所要討論的各種形狀空間搜索戰(zhàn)略都是上述過(guò)程的一個(gè)特例。各種搜索戰(zhàn)略的主要區(qū)別在于對(duì)OPEN表中節(jié)點(diǎn)的陳列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索那么把后生成的子節(jié)點(diǎn)排在前面。形狀空間的搜索戰(zhàn)略圖搜索的普經(jīng)過(guò)程的幾點(diǎn)闡明：在第(6)步針對(duì)M中子節(jié)點(diǎn)的不同情況進(jìn)展處置時(shí)，假設(shè)發(fā)生當(dāng)?shù)冖诜N情況，那么，這個(gè)M中的節(jié)點(diǎn)終究應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？普通是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)途徑上所付出的代價(jià)來(lái)決議的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)途徑上的代價(jià)是指這條路經(jīng)上的一切有向邊的代價(jià)之和。假設(shè)發(fā)生第③種情況，除了需求確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需求確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。其根據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的途徑上的代價(jià)。形狀空間的搜索戰(zhàn)略圖搜索的普經(jīng)過(guò)程的幾點(diǎn)闡明：在搜索圖中，除初始節(jié)點(diǎn)外，恣意一個(gè)節(jié)點(diǎn)都含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。因此，由一切節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。在搜索過(guò)程的第(4)步，一旦某個(gè)被調(diào)查的節(jié)點(diǎn)是目的節(jié)點(diǎn)，那么搜索過(guò)程勝利終了。此時(shí)，由初始節(jié)點(diǎn)到目的節(jié)點(diǎn)途徑上的一切操作就構(gòu)成了該問題的解，而途徑由第(6)步所構(gòu)成的指向父節(jié)點(diǎn)的指針來(lái)確定。假設(shè)搜索過(guò)程終止在第(2)步，即沒有到達(dá)目的，且OPEN表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，那么失敗終了。形狀空間的搜索戰(zhàn)略形狀空間的搜索戰(zhàn)略形狀空間搜索的根本思想圖搜索的普經(jīng)過(guò)程形狀空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹搜索形狀空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法廣度優(yōu)先搜索形狀空間的廣度優(yōu)先搜索廣度優(yōu)先搜索的根本思想：從初始節(jié)點(diǎn)S開場(chǎng)逐層向下擴(kuò)展，在第n層節(jié)點(diǎn)還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。未擴(kuò)展節(jié)點(diǎn)表OPEN表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。廣度優(yōu)先搜索形狀空間的廣度優(yōu)先搜索廣度優(yōu)先搜索算法流程：(1)把