人工智能原理3-2課件

Review1、SearchEnginePageRank2、DataMiningAssociationRule3、Resolutionbasedonclauseoverview1.Rulebaseddeductionsystem2.Productionsystem3.Uncertaintyknowledgeandreasoning歸結反演的策略以上討論的幾種基本的歸結策略，在具體應用時可把幾種策略組合在一起使用。歸結演繹推理是在自動定理證明領域影響較大的一種推理方法，它比較簡單且又便于在計算機上實現。但由于它要求把邏輯公式轉化成子句集，就可能丟失蘊含式含有的邏輯控制信息。例如下列邏輯公式：

(┐A∧┐B)→C(┐A∧┐C)→B(┐B∧┐C)→A┐A→(B∨C)┐B→(A∨C)┐C→(A∨B)A∨B∨C1規(guī)則演繹系統對于許多公式來說，子句形是一種低效率的表達式，因為一些重要信息可能在求取子句形過程中丟失?？梢圆捎靡子跀⑹龅膇fthen規(guī)則來求解問題，這種基于規(guī)則的系統叫做規(guī)則演繹系統。規(guī)則正向演繹系統基于規(guī)則的演繹系統和產生式系統，均有兩種推理方式：正向推理(forwardchanining)和逆向推理(backwardchaining)。

正向推理：從if部分向then部分推理的過程，它是從事實或狀況向目標或動作進行操作的。

逆向推理：從then部分向if部分推理的過程，它是從目標或動作向事實或狀況進行操作的。

規(guī)則正向演繹系統

1.事實表達式的與或形變換

在基于規(guī)則的正向演繹系統中，我們把事實表示為非蘊涵形式的與或形，要把一個公式化為與或形，可采用下列步驟(1)利用(W1→W2)和(┐W1∨W2)的等價關系，消去符號→(2)用狄·摩根(DeMorgan)定律把否定符號移進括號內，直到每個否定符號的轄域最多只含有一個謂詞為止。(3)對所得到的表達式進行Skolem化和前束化。(4)對全稱量詞轄域內的變量進行改名和變量標準化，而存在量詞量化變量用Skolem函數代替。(5)刪去全稱量詞，且使各主要合取式中的變元不同名。

例如，我們有事實表達式

按上述步驟進行轉化后得到與/或形表達式：規(guī)則正向演繹系統規(guī)則正向演繹系統2、F規(guī)則的表示形式在與/或形正向演繹推理中，要求F規(guī)則具有如下形式：L→W

其中，L為單文字，W為與/或形。如果領域知識的表示形式不是所要求的形式，則需通過變換將它變成規(guī)定的形式。3、目標公式的表示形式在與/或形正向演繹推理中，要求目標公式用子句表示，否則就需要化成子句形式。規(guī)則正向演繹系統4、推理過程

應用F規(guī)則進行推理的目的在于證明某個目標公式。其推理過程為：

1)首先用與/或樹把已知事實表示出來。

2)用F規(guī)則的左部和與/或樹的葉節(jié)點進行匹配，將匹配成功的F規(guī)則加入與/或樹中。

3)重復進行步驟2)，直到產生一個含有以目標節(jié)點作為終止節(jié)點的解圖為止。規(guī)則正向演繹系統規(guī)則正向演繹系統規(guī)則正向演繹系統規(guī)則正向演繹系統規(guī)則逆向演繹系統與/或形逆向演繹推理是從待證明的問題出發(fā)，逆向使用蘊式(B規(guī)則)進行演繹推理，直至得到包含已知事實的終止條件為止。1、目標公式的與/或形及其與/或樹表示在與/或形逆向演繹推理中，要求目標公式用與/或形表示，其變換過程與正向演繹推理中對已知事實的變換相似，只是要用存在量詞約束的變元的Skolem函數替換由全稱量詞約束的相應變元，并且消去全稱量詞，然后再消去存在量詞，且使各主要析取式中的變元不同名。規(guī)則逆向演繹系統規(guī)則逆向演繹系統2、B規(guī)則的表示形式

B規(guī)則的表示形式為：W→L其中，W為任一與/或形公式，L為文字。如果已知的B規(guī)則不是所要求的形式，可以把它化成規(guī)定的形式。比如：W→(L1∧L2)W→(L1∨L2)？W→L1,W→L23、已知事實的表示形式在逆向演繹推理中，要求已知事實是文字的合取形式，即形如F1∧F2∧…∧Fn規(guī)則逆向演繹系統4、推理過程應用B規(guī)則進行逆向演繹推理的目的是求解問題，從目標公式的與/或樹出發(fā)，通過運用B規(guī)則來進行求解。其推理過程為：1)先用與/或樹把目標公式表示出來。2)用B規(guī)則的右部和與/或樹的葉節(jié)點進行匹配，將匹配成功的B規(guī)則加入到與/或樹中。3)重復進行步驟2)，直到產生某個終止在事實節(jié)點上的一致解圖為止。規(guī)則逆向演繹系統規(guī)則逆向演繹系統規(guī)則雙向演繹系統規(guī)則雙向演繹系統的主要復雜之處在于其終止條件，終止涉及兩個圖結構之間的適當交接處。這些結構可由標有合一文字的節(jié)點上的匹配棱線來連接。用對應的mgu來標記匹配。代換的一致性

無論對于正向演繹、逆向演繹還是雙向演繹，都要求推理過程中所用的代換集合具有一致性。剪枝策略剪枝策略的基本思想：每當選用一條規(guī)則時，就進行一次一致性檢查，如果當前的部分解圖是一致的，則繼續(xù)向下擴展，否則就放棄該規(guī)則而選用其他侯選規(guī)則。剪枝策略2產生式系統美國數學家Post，1943年提出了一種計算形式體系里所使用的術語。主要是使用類似文法的規(guī)則，對符號串做替換運算。這就是最早的一個產生式系統。到了60年代，產生式系統成為認知心理學研究人類心理活動中信息加工過程的基礎，由此心理學家認為，人腦對知識的存儲就是產生式形式。因此，用它來建立人類認知模型。到目前為止，產生式系統已發(fā)展成為人工智能系統中最典型最普遍的一種結構。產生式表示方法是專家系統中知識表式的第一選擇。產生式系統組成產生式系統由3個部分組成，即總數據庫(或全局數據庫)、產生式規(guī)則和控制策略。各部分間的關系如圖所示。

產生式系統組成①產生式規(guī)則是一個以“如果滿足這個條件，就應當采取某些操作”形式表示的語句。P→Q或ifPthenQ例如，

規(guī)則:

if某種動物是哺乳動物，并且吃肉

then

這種動物被稱為食肉動物②總數據庫有時也被稱作上下文，全局數據庫，GlobalData-base。總數據庫是產生式規(guī)則的注意中心。產生式規(guī)則的左邊表示在啟用這一規(guī)則之前總數據庫內必須準備好的條件。執(zhí)行產生式規(guī)則的操作會引起總數據庫的變化，這就使其他產生式規(guī)則的條件可能被滿足。

產生式系統組成控制策略其作用是說明下一步應該選用什么規(guī)則，也就是如何應用規(guī)則。通常從選擇規(guī)則到執(zhí)行操作分3步：匹配、沖突解決和操作。

(1)匹配在這一步，把全局數據庫與規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。當按規(guī)則的操作部分去執(zhí)行時，稱這條規(guī)則為啟用規(guī)則。被觸發(fā)的規(guī)則不一定總是啟用規(guī)則，因為可能同時有幾條規(guī)則的條件部分被滿足，這就要在解決沖突步驟中來解決這個問題。在復雜的情況下，在數據庫和規(guī)則的條件部分之間可能要進行近似匹配。匹配結果分為：完全匹配,近似匹配,不匹配

產生式系統組成(2)沖突解決當有一條以上規(guī)則的條件部分和當前數據庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。舉例如下:設有以下兩條規(guī)則,

規(guī)則R1IFfourthdawnshortyardageTHENpunt

規(guī)則R2IFfourthdawnshortyardagewithin30yards(fromthegoalline)THENfieldgoal全局數據庫包括：”fourthdawn””shortyardage””within30yards”

產生式系統組成有很多種沖突解決策略，其中一種策略是先使用規(guī)則R2，因為R2的條件部分包括了更多的限制，因此規(guī)定了一個更為特殊的情況。這是一種按專一性來編排順序的策略，稱為專一性排序。還有不少其他的沖突解決策略產生式系統組成(a)專一性排序如果某一規(guī)則條件部分規(guī)定的情況，比另一規(guī)則條件部分規(guī)定的情況更有針對性，則這條規(guī)則有較高的優(yōu)先級。(b)

規(guī)則排序

如果規(guī)則編排的順序就表示了啟用的優(yōu)先級，則稱之為規(guī)則排序。(c)數據排序

把規(guī)則條件部分的所有條件按優(yōu)先級次序編排起來，運行時首先使用在條件部分包含較高優(yōu)先級數據的規(guī)則。(d)規(guī)模排序

按規(guī)則的條件部分的規(guī)模排列優(yōu)先級，優(yōu)先使用被滿足的條件較多的規(guī)則。(e)就近排序

把最近使用的規(guī)則放在最優(yōu)先的位置。這和人類的行為有相似之處。如果某一規(guī)則經常被使用，則人們傾向于更多地使用這條規(guī)則。(f)上下文限制

把產生式規(guī)則按它們所描述的上下文分組，也就是說按上下文對規(guī)則分組。在某種上下文條件下，只能從與其相對應的那組規(guī)則中選擇可應用的規(guī)則。產生式系統組成控制策略(1)匹配(2)沖突解決(3)操作操作就是執(zhí)行規(guī)則的操作部分，經過操作以后，當前數據庫將被修改。然后，其他的規(guī)則有可能被使用產生式系統表示1、事實的表示：一般用三元組（對象，屬性，值）或 （關系，對象1，對象2）例：（Lee,Age,35）,(Friend,Lee,Chang)產生式系統表示2、規(guī)則表示例子：MYCIN系統中典型規(guī)則的定義：

<rule>=(IF<antecedent>THEN<action>(ELSE<action>))

<antecedent>=(AND<condition>)

<condition>=(OR｛<condition>｜(<predicate><associative_triple>)

<associative_triple>=(<attribute><object><value>)

<action>=｛<consequent>｝｜｛<procedure>｝

<consequent>=(<associative_triple><certainty_factor>)

產生式系統表示規(guī)則的內容：

前提條件

◆

細菌革氏染色陰性

◆

形態(tài)桿狀

◆

生長需氧

結論

該細菌是腸桿菌屬，CF=0.8。

產生式系統推理1.正向推理

正向推理又稱為正向鏈接推理，其推理基礎是邏輯演繹的推理鏈，它從一組表示事實的謂詞或命題出發(fā)，使用一組推理規(guī)則，來證明目標謂詞公式或命題是否成立。

實現正向推理的一般策略是：先提供一批數據(事實)到總數據庫中，系統利用這些事實與規(guī)則的前提匹配，觸發(fā)匹配成功的規(guī)則(即啟用規(guī)則)，把其結論作為新的事實添加到總數據庫中。繼續(xù)上述過程，用更新過的總數據庫中的所有事實再與規(guī)則庫中另一條規(guī)則匹配，用其結論再修改總數據庫的內容，直到沒有可匹配的新規(guī)則，不再有新的事實加到總數據庫為止。產生式系統推理產生式系統推理動態(tài)演示產生式系統推理產生式系統推理2.反向推理

反向推理又稱為后向鏈接推理，其基本原理是從表示目標的謂詞或命題出發(fā)，使用一組規(guī)則證明事實謂詞或命題成立，即提出一批假設(目標)，然后逐一驗證這些假設。產生式系統推理產生式系統推理3.雙向推理

雙向推理又稱為正反向混合推理，它綜合了正向推理和逆向推理的長處，克服了兩者的短處。雙響推理的策略是同時從目標向事實推理和從事實想目標推理，并在推理過程中的某個步驟，實現事實與目標的匹配。產生式系統舉例建立一個動物識別系統，用以識別虎、金錢豹、斑馬、長頸鹿、企鵝、駝鳥、信天翁等七種動物。規(guī)則庫：r1:IF該動物有毛發(fā)

THEN該動物是哺乳動物r2:IF該動物有奶

THEN該動物是哺乳動物r3:IF該動物有羽毛THEN該動物是鳥r4:IF該動物會飛AND會下蛋

THEN該動物是鳥r5:IF該動物吃肉

THEN該動物是食肉動物r6:IF該動物有犬齒

AND有爪

AND眼盯前方

THEN該動物是食肉動物r7:IF該動物是哺乳動物AND有蹄THEN該動物是有蹄類動物r8:IF該動物是哺乳動物AND是嚼反芻動物THEN該動物是有蹄類動物R9: IF該動物是哺乳動物

AND是食肉動物AND是黃褐色AND身上有暗斑點THEN該動物是金錢豹r10:IF該動物是哺乳動物

AND是食肉動物AND是黃褐色AND身上有黑色條紋THEN該動物是虎r11:IF該動物是有蹄類動物AND有長脖子AND有長腿AND身上有暗斑點

THEN該動物是長頸鹿r12:IF該動物是有蹄類動物AND身上有黑色條紋THEN該動物是斑馬r13:IF該動物是鳥AND有長脖子AND有長腿AND不會飛AND有黑白二色

THEN該動物是鴕鳥r14:IF該動物是鳥AND會游泳AND不會飛AND有黑白二色

THEN該動物是企鵝r15:IF該動物是鳥AND善飛THEN該動物是信天翁產生式系統舉例(1)分類的思想(2)知識的合理組織與管理{r1、r2、r5、r6、r7、r8、r9、r10、r11、r12}{r3、r4、r13、r14、r15}產生式系統的特點①用產生式系統結構求解問題的過程和人類求解問題時的思維很相像。因而可以用它來模擬人類求解問題的思維過程。②可以把產生式系統作為人工智能系統的基本結構單元或基本模型看待。因而研究產生式系統的基本問題就具有一般意義。③表示的格式固定、形式單一、規(guī)則間相互獨立。所以建立容易；推理方式單純、知識庫與推理機分離，修改方便、容易理解。3知識的不確定性

在各種實際應用領域中，嚴格精確的和確定的知識并不多見，大量的知識是不精確的和不確定的，需要采用不確定推理或稱為不精確推理對不確定知識進行處理?？梢哉f，不確定性(Uncertainty)是智能問題的本質特征，因此，智能系統的能力更主要反映在求解不確定性問題的能力上。知識的不確定性現實生活中的事物有時很難用精確的概念來描述，比如高、矮、胖、瘦等。對于不確定性知識要用不確定推理來處理，否則有可能得出一些荒謬的結論。專家系統中的不確定性表現在三個方面，第一是證據或事實的不確定性，第二是規(guī)則的不確定性，第三是推理的不確定性。知識的不確定性1、證據的不確定性(1)證據的歧義性：如“同意總理開會”

“Isawamanwithatelescope.”(2)證據的不完全性

①證據尚未收集完全

②證據的特征值不完全(3)證據的不精確性：如“大約是1.7米”(4)證據的模糊性：如“年輕”(5)證據的可信性(6)證據的隨機性知識的不確定性2、規(guī)則的不確定性產生式規(guī)則的不確定性主要有以下幾個方面。(1)構成規(guī)則前件的模式的不確定性如：有一條產生式規(guī)則“如果患者發(fā)高燒且常流清鼻涕，則患者感冒”知識的不確定性(2)觀察證據的不確定性例如，患者發(fā)高燒的體溫觀察值并不是恒定的。晚上可能是39℃，早上可能是38.5℃。(3)規(guī)則前件的證據組合的不確定性例如，有一位患者的體溫一直都是40℃，流清鼻涕，但并不是常流清鼻涕。知識的不確定性(4)規(guī)則本身的不確定性每一條規(guī)則并不都具有100%的信任度，這就是規(guī)則的不確定性，或稱為規(guī)則強度(5)規(guī)則結論的不確定性由于規(guī)則的前件包含有各種不確定性因素，運用不確定的規(guī)則，導出的結論也就不可避免地是不確定的。知識的不確定性此外，在規(guī)則使用過程中，還有兩種典型的使用規(guī)則的不確定性。(1)沖突消解策略包含有使用規(guī)則的不確定性(2)選擇假設進行反向推理驗證的不確定性知識的不確定性3、推理的不確定性由于證據的不確定性和規(guī)則的不確定性在推理過程中的動態(tài)積累和傳播從而導致推理結論的不確定性。因此，需要采用某種不確定性的測度，并能在推理過程中來傳遞和計算這種不確定性的測度，最總得到結論的不確定性測度。

在不確定推理中，不確定性測度的計算有以下三種基本的計算模式。知識的不確定性知識的不確定性知識的不確定性知識的不確定性一、不確定性推理及實現1.基本概念

(1)什么是不確定性推理不確定性推理就是從不確定性的初始證據出發(fā)，通過運用不確定性的知識，最終推出具有一定程度的不確定性但卻合理或者近乎合理的結論的思維過程。

4不確定性推理

(2)不確定性推理中的基本問題在不確定性推理中，知識和證據都具有某種程度的不確定性，這就為推理機的設計與實現增加了復雜性和難度。它除了必須解決推理方向、推理方法、控制策略等基本問題外，一般還需要解決不確定性的表示和量度、不確定性匹配、不確定性的傳遞算法以及不確定性的合成等重要問題。

不確定性推理

(3).

不確定性匹配算法及閾值的選擇

對于不確定性推理，由于知識和證據都具有不確定性，而且知識所要求的不確定性與證據實際具有的不確定性程度不一定相同，因而就出現了“怎樣才算匹配成功”的問題。

不確定性推理不確定性推理

對于這個問題，目前常用的解決方法是：設計一個算法用來計算匹配雙方相似的程度，另外再指定一個相似的“限度”，用來衡量匹配雙方相似的程度是否落在指定的限度內。如果落在指定的限度內，就稱它們是可匹配的，相應知識可被應用。

?

用來計算匹配雙方相似程度的算法稱為不確定性匹配算法

?

用來指出相似的“限度”稱為閾值(4)不確定性的傳遞算法

推理過程中不確定性的傳遞過程，包括如下兩個密切相關的子問題：

?在每一步推理中，如何把證據及知識的不確定性傳遞給結論；

?在多步推理中，如何把初始證據的不確定性傳遞給最終結論。

不確定性推理不確定性推理

對前一個問題，在不同的不確定推理方法中所采用的處理方法各不相同。對第二個問題，各種推理方法所采用的處理方法基本相同，即：把當前推出的結論及其不確定性程度作為證據放入數據庫中，供以后推理使用。

(5).

結論不確定性的合成

推理時有時會出現這樣的情況：用不同的知識進行推理得到了相同的結論，但不確定性的程度卻不同。此時，需要用合適的算法對它們進行合成。在不同的不確定推理方法中所采用的處理方法各不相同。不確定性推理不確定性推理二、常用的不確定性推理方法介紹(1)基于概率的不確定推理

利用新的信息將先驗概率P(H)更新為后驗概率P(H|E)的一種計算方法.基于概率的不確定推理于1976年提出，其首先在Prospector專家系統中使用，它以概率論中的全概率公式和Bayes公式為基礎?；诟怕实牟淮_定推理基于概率的不確定推理基于概率的不確定推理

(2)可信度方法(CertaintyFactor)

可信度方法是由E.H.Shortliffe等人在確定性理論的基礎上，結合概率提出的一種不確定性推理方法，首先在Mycin系統中得到了成功的應用。

其核心思想是：利用確定性因子CF（值）

Ⅰ.

聯系于具體的斷言

Ⅱ.

聯系于每條規(guī)則

Ⅲ.

通過CF的計算傳播不確定性

不確定性推理

(1)可信度根據經驗對一個事物或現象為真的相信程度。

(2)C-F模型

C-F模型是基于可信度表示的不確定性推理的基本方法。

可信度方法

Ⅰ.

知識不確定性的表示

在C-F模型中，知識是用產生式規(guī)則表示的，其一般形式是：

ifEthenH(CF(H,E))

其中，

E：是知