浙江大學(xué)研究生《人工智能引論》

1、人工智能引論課件(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaMarch 10, 2002第一稿April 18, 2007第四次修改稿第四講 不確定性推理概述(Chapter4 Uncertainty Reasoning )1Outline本章的主要參考文獻(xiàn)基本概念基本問題不確定性推理方法的分類不確定性度量的測(cè)度理論不確定性

2、的其它度量方法Shannon信息熵及在決策樹中的應(yīng)用模糊推理21 王永慶. 人工智能原理與方法. 西安交通大學(xué)出版社, 1998. pp156-252. (偏重基本概念)2 張文修, 梁怡. 不確定性推理原理. 西安交通大學(xué)出版社, 1996. （偏重?cái)?shù)學(xué)原理）3 陸汝鈐. 人工智能(下冊(cè)). 科學(xué)出版社, 2000. pp1133-1170. （偏重Bayes概率推理、可信度、模糊推理）4 史忠植. 知識(shí)發(fā)現(xiàn). 清華大學(xué)出版社, 2002. pp24-26, pp141-202. （偏重Rough set和貝葉斯網(wǎng)絡(luò)）本章的主要參考文獻(xiàn)35 Mitchell, T. M.著, 曾華軍等譯.

3、機(jī)器學(xué)習(xí). 機(jī)械工業(yè)出版社, 2003. pp112-143. （偏重貝葉斯學(xué)習(xí)）6 Russell, S., Norvig, P. Artificial Intelligence: A Modern Approach. 人民郵電出版社, 2002. pp413-522. （偏重貝葉斯網(wǎng)絡(luò)及其應(yīng)用）本章的主要參考文獻(xiàn)（續(xù)）“Blessed is the nation whose God is the LORD, the people he chose for his inheritance.” From PSALMS 33:12 NIV 44.1.1 精確推理的局限性 推理依據(jù)已知事實(shí)（證據(jù)）

4、、相關(guān)知識(shí)（規(guī)則）證明某個(gè)假設(shè)成立 or 不成立 精確推理及其不足將原本為不確定性的關(guān)系“硬性”轉(zhuǎn)化為精確關(guān)系將原本不存在明確界限的事物“人為”劃定界限歪曲了現(xiàn)實(shí)情況的本來面目舍棄了事物的某些重要屬性失去了真實(shí)性4.1 基本概念54.1.2 不確定性推理的定義及意義1. 定義也稱“不精確性推理”從不確定性的初始證據(jù)（即已知事實(shí)）出發(fā)運(yùn)用不確定性的知識(shí)（或規(guī)則）推出具有一定程度的不確定性但卻是合理或近乎合理的結(jié)論2. 意義使計(jì)算機(jī)對(duì)人類思維的模擬更接近于人類的真實(shí)思維過程64. 2 不確定性推理中的基本問題不確定性的表示與度量不確定性匹配不確定性的傳遞算法不確定性的合成74.2.1 不確定性的表

5、示與度量1. 不確定性的表示選擇不確定性表示方法時(shí)應(yīng)考慮的因素充分考慮領(lǐng)域問題的特征恰當(dāng)?shù)孛枋鼍唧w問題的不確定性滿足問題求解的實(shí)際需求便于推理過程中對(duì)不確定性的推算8不確定性的表示與度量（續(xù)1）2. 不確定性的度量針對(duì)不同的領(lǐng)域問題采用不同的度量方法用不同的數(shù)值刻畫不同的不確定性程度事先規(guī)定不確定性程度的取值范圍3. 常用的度量方法測(cè)度理論（基于概率統(tǒng)計(jì)的度量方法）Shannon信息熵其它度量方法9不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時(shí)應(yīng)考慮的因素：充分表達(dá)相應(yīng)知識(shí)及證據(jù)不確定性的程度度量范圍便于領(lǐng)域?qū)＜壹坝脩艄烙?jì)不確定性便于計(jì)算過程中的不確定性傳遞，結(jié)論的不確定性度量不超出規(guī)定

6、的范圍度量的確定應(yīng)直觀，且有相應(yīng)的理論依據(jù)104.2.2 不確定性匹配解決不確定性匹配的常用方法設(shè)計(jì)一個(gè)匹配算法用以計(jì)算相似度指定一個(gè)相似度的“限定”（即閾值）“To do what is right and just is more acceptable to the LORD than sacrifice.” From PROVERBS 21:3 NIV 114.2.3 證據(jù)不確定性的組合單一證據(jù) & 組合證據(jù)單一證據(jù)：前提條件僅為一個(gè)簡(jiǎn)單條件組合證據(jù)：一個(gè)復(fù)合條件對(duì)應(yīng)于一組證據(jù)前提條件用AND（與）或OR（或）把多個(gè)簡(jiǎn)單條件連接起來構(gòu)成復(fù)合條件12（1）最大最小法T(E1 AND E2)

7、 = min T(E1), T(E2)T(E1 OR E2) = max T(E1), T(E2)（2）概率方法 （要求事件之間完全獨(dú)立） T(E1 AND E2) = T(E1) T(E2) T(E1 OR E2) = T(E1) + T(E2) - T(E1) T(E2)（3）有界方法T(E1 AND E2) = max 0, T(E1) + T(E2) -1T(E1 OR E2) = min 1, T(E1) + T(E2)【注】：上述T(E)表示證據(jù)E為真的程度，如可信度、概率等。每組公式都有相應(yīng)的適用范圍和使用條件。常用的組合證據(jù)不確定性計(jì)算方法134.2.4 不確定性的傳遞包含兩個(gè)

8、子問題在每一步推理中，如何把證據(jù)及知識(shí)的不確定性傳遞給給結(jié)論在多步推理中，如何把初始證據(jù)的不確定性傳遞給最終結(jié)論144.2.5 結(jié)論不確定性的合成用不同知識(shí)進(jìn)行推理得到相同的結(jié)論同個(gè)結(jié)論的不確定性程度卻不相同需要用合適的算法對(duì)它們進(jìn)行合成154. 3 不確定性推理方法的分類4.3.1 不確定性推理的兩條研究路線模型方法在推理一級(jí)上擴(kuò)展確定性推理不確定證據(jù)和知識(shí)與某種度量標(biāo)準(zhǔn)對(duì)應(yīng)給出更新結(jié)論不確定性的算法構(gòu)成相應(yīng)的不確定性推理模型控制方法在控制策略一級(jí)上處理不確定性無統(tǒng)一的不確定性處理模型，其效果依賴于控制策略164.3.2 不確定性推理方法的分類不確定性推理模型方法控制方法數(shù)值方法非數(shù)值方法概

9、率統(tǒng)計(jì)方法模糊推理方法粗糙集方法絕對(duì)概率方法貝葉斯方法證據(jù)理論方法HMM方法發(fā)生率計(jì)算相關(guān)性制導(dǎo)回溯、機(jī)緣控制、啟發(fā)式搜索等可信度方法174.3.3 關(guān)于不確定性推理方法的說明數(shù)值方法對(duì)不確定性的一種定量表示和處理方法其研究及應(yīng)用較多，已形成多種應(yīng)用模型非數(shù)值方法除數(shù)值方法外的其它處理不確定性的模型方法典型代表：“發(fā)生率計(jì)算方法”，它采用集合來描述和處理不確定性，且滿足概率推理的性質(zhì)18關(guān)于不確定性推理方法的說明（續(xù)1）概率統(tǒng)計(jì)方法有完整、嚴(yán)密的數(shù)學(xué)理論為不確定性的合成與傳遞提供了現(xiàn)成的數(shù)學(xué)公式最早、最廣泛地用于不確定性知識(shí)的表示與處理已成為不確定性推理的重要手段證據(jù)理論方法1967年Demp

10、ster首次提出，1976年Shafer完善可表示并處理“不知道”等不確定性信息19關(guān)于不確定性推理方法的說明（續(xù)2）模糊推理方法可表示并處理由模糊性引起的不確定性已廣泛應(yīng)用于不確定性推理粗糙集理論方法1981年Z. Pawlak首次提出一種新的可表示并處理“含糊”等不確定性的數(shù)學(xué)方法可用于不確定性推理、數(shù)據(jù)挖掘等領(lǐng)域204.4 描述不確定性信息的測(cè)度理論4.4.1 測(cè)度及其分類 設(shè)(X) 是有限集合X上的子集合的全體，測(cè)度的定義如下：定義6.1（測(cè)度） 若g: (X) 0, 1滿足條件： (1) g(X) = 1; (2) 當(dāng)A B = 時(shí)，有g(shù)(A B) = g(A) + g(B) + g

11、(A) g(B)稱為g測(cè)度。【注】：關(guān)于測(cè)度理論的詳細(xì)論述請(qǐng)參見夏道行編著的實(shí)變函數(shù)與泛函分析，復(fù)旦大學(xué)出版社。21定義4.2（模糊測(cè)度） 模糊測(cè)度被定義為一個(gè)映射M: (X) 0, 1具有如下性質(zhì)： (1) 有界性： M() = 0, M(X) = 1; (2) 單調(diào)性： 對(duì)任意A, B(X), AB時(shí)，有M(A) M(B) 由模糊測(cè)度定義可知： （1）有界性表示：一個(gè)非空元素不可能屬于，它必然屬于全集； （2）單調(diào)性表示：一個(gè)元素隸屬于一個(gè)集合的確定度不大于它隸屬于更大的一個(gè)集合的確定度。22定理4.1 當(dāng)-1時(shí)， 測(cè)度g是模糊測(cè)度。定理4.2 當(dāng)-1時(shí)， 測(cè)度g具有如下性質(zhì)：模糊測(cè)度及其

12、性質(zhì)23定義4.3（概率測(cè)度） 稱P： (X） 0，1為概率測(cè)度，若滿足：（1）有界性：P(X) = 1（2）可加性：AB=時(shí)，P(AB) = P(A) + P(B)【注】：可證明概率測(cè)度是0時(shí)模糊測(cè)度。 定義4.4 (條件概率) 如果P是X上的概率測(cè)度，EX，且P(E)0，稱為給定條件E下，事件A發(fā)生的條件概率。24 對(duì)于條件概率有如下聯(lián)合概率公式： 若A1, A2, ., An為X中的n個(gè)事件，可得 若A, B兩個(gè)事件滿足P(A|B) = P(A)，即A發(fā)生的可能性與B無關(guān)，稱A, B是相互獨(dú)立的。這時(shí)有 若n個(gè)事件A1, A2, ., An相互獨(dú)立，則25Markov條件獨(dú)立性定義4.5

13、 (馬氏條件獨(dú)立性) 若A1, A2, ., An是按時(shí)間順序發(fā)生的一系列事件，而且具有如下特性：未來某一事件Ak+1發(fā)生的可能性只依賴于當(dāng)前時(shí)刻的事件Ak ，而與過去發(fā)生的事件無關(guān)，即這時(shí)稱n個(gè)事件具有馬氏（Markov）獨(dú)立性。 對(duì)n個(gè)滿足馬氏獨(dú)立性條件的事件滿足26定義4.6（全概率公式） 設(shè)Hi (i 0 ?！咀ⅰ浚号c不協(xié)調(diào)度相似，當(dāng)m是概率分布時(shí)，混淆度即為不確定度（香農(nóng)信息熵）。37 3、信息量 一個(gè)概念是內(nèi)涵與外延的統(tǒng)一體。內(nèi)涵的多少表示了信息量的大小，但是內(nèi)涵一般是無法度量的。由于內(nèi)涵與外延是某種相反關(guān)系，我們可用外延補(bǔ)集作為信息，用外延補(bǔ)集的測(cè)度作為信息量。于是就得到如下信息

14、量的概念。定義4.19 (信息量) 設(shè)X是有限集，包含n個(gè)元素。P是X上的概率分布，稱是X, P的信息量。其中，38 在不確定性推理過程中，經(jīng)常遇到兩類問題： (1) 匹配（檢索）問題，需要相似度的概念； (2) 推理規(guī)則的條件與結(jié)論之間的蘊(yùn)涵關(guān)系，就需要蘊(yùn)涵度的概念。 經(jīng)專家研究發(fā)現(xiàn)，相似度與蘊(yùn)涵度的共性即為包含度。 【注】：本課件只簡(jiǎn)要介紹上述三個(gè)概念的定義，有關(guān)包含度理論的詳細(xì)論述請(qǐng)參見文獻(xiàn)： 張文修、梁怡不確定性推理原理，西安交通大學(xué)出版社，1996。補(bǔ)充說明：39 4、包含度 設(shè)X是一個(gè)普通集合，(X)表示X中所有子集的全體，(X)表示X中模糊集合的全體。 定義4.19 (包含度)：

15、設(shè)0(X)(X) ，對(duì)A, B 0(X) 有數(shù)D(B/A)對(duì)應(yīng)，且滿足： (1) 0 = D(B/A) H，令R(P; H)為從P推出 H的模糊關(guān)系R(P; H) = APAH = (xP, xH) / uR(xP, xH)uR(xP, xH) = uAp(xP) uAH(xH) 階段二：推理合成規(guī)則（max-min復(fù)合運(yùn)算）當(dāng)實(shí)際的輸入信息為模糊命題P時(shí)，則模糊推理的輸出HAH = AP R(P; H) 可得69基于模糊關(guān)系的推理舉例請(qǐng)參見高濟(jì)教授編著的教材基于知識(shí)的軟件智能化技術(shù)pp206-208有興趣的同學(xué)可進(jìn)一步參考張文修、梁怡編著的不確定性推理原理pp228-235中的“5-4 Ma

16、mdani模糊推理”基本要求：能熟練解答與高濟(jì)教授教材中類似的模糊推理習(xí)題704.7.6 模糊推理的神經(jīng)網(wǎng)絡(luò)算法特別聲明這一節(jié)屬于補(bǔ)充材料，考試時(shí)不做要求 感興趣的同學(xué)可參見張文修、梁怡編著的不確定性推理原理pp244-248中的“5-7 模糊推理的神經(jīng)網(wǎng)絡(luò)算法”模糊推理的神經(jīng)網(wǎng)絡(luò)算法思想將“Ai = Bi”規(guī)則作為第i個(gè)輸入，則形成一個(gè)神經(jīng)網(wǎng)絡(luò)可通過神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法得到權(quán)重wi71模糊推理的神經(jīng)網(wǎng)絡(luò)算法學(xué)習(xí)過程當(dāng)Y是單點(diǎn)集y時(shí)，訓(xùn)練模型為(A, B)，學(xué)習(xí)算法的過程如下：步1：給出初始權(quán)重w1和訓(xùn)練樣本H=(A, B)步2：利用如下公式計(jì)算步3：若B(y) = B(y) ，則終止；否則，修正w1;步4：若上述過程進(jìn)行到第k步，得到Wk=(wk1,wk2,wkn)，使得 則終止，其中，gk為形成的模糊測(cè)度，即 gk(i)= wki；否則，修正權(quán)重wki。【注】：權(quán)重修正方法詳見張文修、梁怡編著的不確定性推理原理pp24672THANKS FOR Y