《人工智能及其應(yīng)用》課件第3章 確定性推理

第3章確定性推理如果人類的大腦簡單到我們可以理解，那么我們就將愚蠢到無法理解大腦?！獝勰び?19773.1推理的基本概念3.1.1推理的定義

從初始證據(jù)出發(fā)，按某種策略不斷運(yùn)用知識(shí)庫中的已知知識(shí)，逐步推出結(jié)論的過程稱為推理。3.1推理的基本概念3.1.2推理方式及其分類

若從推出結(jié)論的途徑來劃分，推理可分為演繹推理、歸納推理。演繹推理（DeductiveReasoning）是從全稱判斷推導(dǎo)出單稱判斷的過程，即由一般性知識(shí)推出適合于某一具體情況的結(jié)論。這是一種從一般到個(gè)別的推理。歸納推理（InductiveReasoning）是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理。3.1推理的基本概念3.1.2推理方式及其分類

若按推理時(shí)所用知識(shí)的確定性來劃分，推理可分為確定性推理與不確定性推理。確定性推理是指推理時(shí)所用的知識(shí)與證據(jù)都是確定的，推出的結(jié)論也是確定的，其真值為真或者為假，沒有第三種情況出現(xiàn)。不確定性推理是指推理時(shí)所用的知識(shí)與證據(jù)不都是確定的，推出的結(jié)論也是不確定的?，F(xiàn)實(shí)世界中的事物和現(xiàn)象大都是不確定的，或者模糊的，很難用精確的數(shù)學(xué)模型來表示與處理。3.1推理的基本概念3.1.3推理的方向1.正向推理正向推理是以已知事實(shí)作為出發(fā)點(diǎn)的一種推理。正向推理的基本思想：從用戶提供的初始已知事實(shí)出發(fā)，在知識(shí)庫中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用知識(shí)集（KS），然后按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入數(shù)據(jù)庫中作為下一步推理的已知事實(shí)，此后再在知識(shí)庫中選取可適用知識(shí)進(jìn)行推理，如此重復(fù)這一過程，直到求得了問題的解或者知識(shí)庫中再無可適用的知識(shí)為止。3.1推理的基本概念3.1.3推理的方向2.逆向推理逆向推理是以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理。

逆向推理的基本思想是：首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)是成立的；若無論如何都找不到所需要的證據(jù)，則說明原假設(shè)是不成立的，為此需要另作新的假設(shè)。3.1推理的基本概念3.1.3推理的方向3.混合推理正向推理具有盲目、效率低等缺點(diǎn)，推理過程中可能會(huì)推出許多與問題無關(guān)的子目標(biāo)。逆向推理中，若提出的假設(shè)目標(biāo)不符合實(shí)際，會(huì)降低系統(tǒng)的效率。

為解決這些問題，可把正向推理與逆向推理結(jié)合起來，使其各自發(fā)揮自己的優(yōu)勢，取長補(bǔ)短。這種既有正向又有逆向的推理稱為混合推理。3.1推理的基本概念3.1.4沖突消解策略在推理過程中，系統(tǒng)要不斷地用當(dāng)前已知的事實(shí)與知識(shí)庫中的知識(shí)進(jìn)行匹配。此時(shí)，可能發(fā)生如下三種情況。①已知事實(shí)恰好只與知識(shí)庫中的一個(gè)知識(shí)匹配成功；②已知事實(shí)不能與知識(shí)庫中的任何知識(shí)匹配成功；③已知事實(shí)可與知識(shí)庫中的多個(gè)知識(shí)匹配成功；

3.1推理的基本概念3.1.4沖突消解策略

推理過程中不僅有知識(shí)匹配成功，而且有多個(gè)知識(shí)匹配成功，稱為發(fā)生了沖突。按一定的策略從匹配成功的多個(gè)知識(shí)中挑出一個(gè)知識(shí)用于當(dāng)前的推理的過程稱為沖突消解。

解決沖突時(shí)所用的策略稱為沖突消解策略。

3.1推理的基本概念

3.1推理的基本概念3.1.4沖突消解策略2.按已知事實(shí)的新鮮性排序

在產(chǎn)生式系統(tǒng)的推理過程中，每應(yīng)用一條產(chǎn)生式規(guī)則就會(huì)得到一個(gè)或多個(gè)結(jié)論或者執(zhí)行某個(gè)操作，數(shù)據(jù)庫就會(huì)增加新的事實(shí)。

一般把數(shù)據(jù)庫中后生成的事實(shí)稱為新鮮的事實(shí)，即后生成的事實(shí)比先生成的事實(shí)具有較大的新鮮性。

若一條規(guī)則被應(yīng)用后生成了多個(gè)結(jié)論，則既可以認(rèn)為這些結(jié)論有相同的新鮮性，也可以認(rèn)為排在前面（或后面）結(jié)論有較大的新鮮性，根據(jù)情況決定。

3.1推理的基本概念

3.2自然演繹推理

3.2自然演繹推理

3.2自然演繹推理

3.2自然演繹推理

3.2自然演繹推理

3.2自然演繹推理#程序3.1父子和爺孫關(guān)系推理3.3子句集的求取

3.3子句集的求取

3.3子句集的求取

3.3子句集的求取

3.3子句集的求取

3.3子句集的求取

3.3子句集的求取

3.3子句集的求取定理3.1：謂詞公式不可滿足的充要條件是其子句集不可滿足。由此定理可知，要證明一個(gè)謂詞公式是不可滿足的，只要證明相應(yīng)的子句集是不可滿足的就可以了。3.3子句集的求取

3.3子句集的求取

3.4歸結(jié)原理魯賓遜歸結(jié)原理

子句集中子句之間是合取關(guān)系，其中只要有一個(gè)子句不可滿足，則子句集就不可滿足。

由于空子句是不可滿足的，所以，若一個(gè)子句集中包含空子句，則這個(gè)子句集一定是不可滿足的。

魯賓遜歸結(jié)原理：檢查子句集S中是否包含空子句，若包含，則S不可滿足；若不包含，就在子句集中選擇合適的子句進(jìn)行歸結(jié)，一旦通過歸結(jié)得到空子句，就說明子句集S是不可滿足的。3.4歸結(jié)原理

3.4歸結(jié)原理

3.4歸結(jié)原理

3.4歸結(jié)原理

3.4歸結(jié)原理

3.4歸結(jié)原理

3.5歸結(jié)反演

3.5歸結(jié)反演

3.6歸結(jié)原理求解問題

3.6歸結(jié)原理求解問題

3.6歸結(jié)原理求解問題

3.6歸結(jié)原理求解問題

3.7非單調(diào)推理建立在謂詞邏輯基礎(chǔ)上的傳統(tǒng)系統(tǒng)是單調(diào)的，這意味著，已知為真的命題數(shù)目將隨時(shí)間而嚴(yán)格增加。

這種系統(tǒng)具有以下優(yōu)點(diǎn)：（1）當(dāng)加人一個(gè)新命題時(shí)，不必檢查新命題與原有知識(shí)之間的不相容性。（2）對(duì)每一個(gè)已被證明了的命題，不必保留一個(gè)命題表。

它的證明以該命題表中的命題為根據(jù)，因?yàn)椴淮嬖谀切┟}會(huì)被取消的危險(xiǎn)。3.7非單調(diào)推理非單調(diào)推理系統(tǒng)的必要性：（1）不完全知識(shí)的出現(xiàn)要求缺省推理。（2）一個(gè)不斷變化的世界必須用適應(yīng)不斷變化的數(shù)據(jù)庫來描述。（3）產(chǎn)生一個(gè)問題的完全解可能要求關(guān)于部分解的暫時(shí)的假設(shè)。3.7非單調(diào)推理3.7.1缺省推理

很少有能在處理過程中擁有它所需要的一切信息的系統(tǒng)，當(dāng)缺乏信息時(shí)，只要不出現(xiàn)相反的證據(jù)，就可以作一些有益的猜想。構(gòu)造這種猜想稱為缺省推理。3.7.2真值維持系統(tǒng)

真值維持系統(tǒng)（TruthMaintenanceSystem，TMS）是一個(gè)已經(jīng)實(shí)現(xiàn)了的非單調(diào)推理系統(tǒng)，它用以協(xié)助其他推理程序維持系統(tǒng)的正確性，所以它的作用不是生成新的推理，而是在其他程序所產(chǎn)生的命題之間保持相容性。

一旦發(fā)現(xiàn)某個(gè)不相容，它就調(diào)出自己的推理機(jī)制，面向從屬關(guān)系的回溯，并通過修改最小的信念集來消除不相容。3.7非單調(diào)推理

在TMS中，每一個(gè)命題或規(guī)則均稱為節(jié)點(diǎn)，且對(duì)任一節(jié)點(diǎn)，以下兩種狀態(tài)必居其一：IN相信為真。OUT不相信為真，或無理由相信為真，或當(dāng)前沒有可相信的理由。

每個(gè)節(jié)點(diǎn)附有一張證實(shí)表，表中每一項(xiàng)表示一種確定節(jié)點(diǎn)有效性的方法。節(jié)點(diǎn)是指那些至少有一個(gè)在當(dāng)前說來是有效證實(shí)的節(jié)點(diǎn)。3.8小結(jié)

從初始證據(jù)出發(fā)，按某種策略不斷運(yùn)用知識(shí)庫中的已知知識(shí)，逐步推出結(jié)論的過程稱為推理。

原子謂詞公式及其否定，稱為文字。任何文字的析取式稱為子句。把謂詞公式可以化成子句集。謂詞公式不可滿足的充要條件是其子句集不可滿足。魯賓遜歸結(jié)原理是機(jī)器定理證明的基礎(chǔ)，是一種證明子句集不可滿足性，從而實(shí)現(xiàn)定理證明的一種理論及方