1、人工智能復(fù)習(xí),北京師范大學(xué) 信息科學(xué)與技術(shù)學(xué)院 王醒策,第一章 緒論,課程研究的主要內(nèi)容 知識表示 推理方式 確定性推理（主要歸結(jié)原理） 不確定性推理 搜索技術(shù)研究 普通圖搜索 超圖搜索（與或圖搜索）,第一章 緒論,需要解決的問題： 萬能的人工智能的知識體系結(jié)構(gòu)從根本上就不可能有，最根本的原因是缺乏知識。人是根據(jù)知識行事的，而不是根據(jù)抽象原則上進行推理。 即使是推理系統(tǒng)中，它的主要技術(shù)是狀態(tài)空間搜索。而在執(zhí)行的過程中最主要的問題就是組合爆炸問題，只有是用理性的知識才能夠擺脫困境。,第一章 緒論,人工智能的瓶頸問題 知識獲取 規(guī)模擴展 應(yīng)用前景,第二章 知識的表示,知識的獲取 如何從現(xiàn)實世界中得

2、到知識。 知識的表示 如何將已經(jīng)獲取的知識以計算機內(nèi)部代碼的形式加以合理的表示，以便于存儲。 知識的運用 如何運用這些知識進行推理以解決實際的問題。,第二章 知識的表示,知識的定義 數(shù)據(jù) 信息 知識,第二章 知識的表示,知識表示方式 直覺表示方法 邏輯表示方法 產(chǎn)生式表示方法 語義網(wǎng)絡(luò)表示方法 框架表示方法,第二章 知識的表示,知識表示方式 面向?qū)ο蟊硎痉椒?腳本表示方法 狀態(tài)空間表示方法 與/或樹表示方法,第二章 知識的表示,邏輯表示法（經(jīng)典邏輯推理） 一階謂詞邏輯 謂詞邏輯的規(guī)范表達(dá)式P(x1,x2,xn) 邏輯表示法 語法和語義 1 基本符號 2 原子公式 3 連詞和量詞,第二章 知識的

3、表示,產(chǎn)生式表示法（產(chǎn)生式系統(tǒng)、專家系統(tǒng)） 產(chǎn)生式表示的形式 產(chǎn)生式與謂詞邏輯中的蘊涵式的區(qū)別 蘊涵式只能表示精確知識，產(chǎn)生式不僅可以表示精確知識，而且可以表示不精確知識 蘊涵式要求前提精確匹配，產(chǎn)生式可以不精確匹配 蘊含式有真值，產(chǎn)生式?jīng)]有真值,第二章 知識的表示,產(chǎn)生式知識表示方法 確定性規(guī)則知識的產(chǎn)生式表示 不確定性規(guī)則知識的產(chǎn)生式表示 確定性事實知識的產(chǎn)生式表示 不確定性事實知識的產(chǎn)生式表示 產(chǎn)生式系統(tǒng)的組成 規(guī)則庫、綜合數(shù)據(jù)庫、推理機（匹配、沖突解決、操作）,第二章 知識的表示,語義網(wǎng)絡(luò)表示法（自然語言理解） 從理論上來說，語義網(wǎng)絡(luò)與一階謂詞具有同樣的知識表示能力。 語義網(wǎng)絡(luò)中常用的

4、語義聯(lián)系 類屬關(guān)系（AKO、AMO、ISA） 包含關(guān)系（Part-of） 占有關(guān)系（Have） 時間關(guān)系（Before、After、During）,第二章 知識的表示,語義網(wǎng)絡(luò)表示法 語義網(wǎng)絡(luò)中常用的語義聯(lián)系 位置關(guān)系（Located-on、 Located-at 、 Located-under、 Located-inside、 Located-outside） 相近關(guān)系（Similar-to、Near-to） 屬性關(guān)系（IS）,第二章 知識的表示,語義網(wǎng)絡(luò)表示知識的方法 事實性知識 情況和動作的表示 情況的表示（情況節(jié)點） 動作和事件的表示（動作節(jié)點） 邏輯關(guān)系的表示 合取和析取的表示 存在

5、量詞和全稱量詞的表示,第二章 知識的表示,框架表示法 組成： 框架是由框架名、槽、側(cè)面和值四個部分組成的 舉例子：計算機主機 框架表示法表示知識的步驟 分析表達(dá)只是對象及其屬性，對框架中的槽進行合理設(shè)置 對各對象之間的聯(lián)系進行考察。使用一些常用的或根據(jù)需要定義的槽名，來表示上下框架聯(lián)系,第二章 知識表示,狀態(tài)空間表示法 問題的狀態(tài)空間構(gòu)成 狀態(tài) 算符 狀態(tài)空間（S,F,G）狀態(tài)空間的圖示形式成為狀態(tài)空間圖。節(jié)點表示狀態(tài)，有向邊表示算符,第二章 知識表示,用狀態(tài)空間表示問題的步驟 定義狀態(tài)的描述形式 用所定義的狀態(tài)描述形式把問題的所有可能狀態(tài)都表示出來，并確定出問題的初始狀態(tài)描述和目標(biāo)狀態(tài)集合描

6、述 定義一組算符，使得利用這組算符可把問題有一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。,第二章 知識表示,與/或樹表示法 問題的分解與等價變換 問題的歸約的與/或樹表示 與樹、或樹、與/或樹 端節(jié)點與終止節(jié)點 可解節(jié)點與不可解節(jié)點 解樹,第三章 確定性推理方法,要求： 熟練掌握構(gòu)造邏輯公式的合取范式，skolem標(biāo)準(zhǔn)型的轉(zhuǎn)化方法，歸結(jié)法進行歸結(jié)的過程。掌握歸結(jié)過程中的控制策略,第三章 確定性推理方法,推理方式 正向推理 反向推理 雙向推理 混合推理,第三章 確定性推理方法,自然演繹推理方法 假言三段論P Q，Q R=P R 拒取式P Q，Q=P 假言推理：P，P Q=Q,第三章 確定性推理方法,歸結(jié)推理方法（

7、消解法） 將謂詞公式化為Skolem標(biāo)準(zhǔn)形步驟 消去號和(雙蘊含符號)； 深入到量詞內(nèi)部； 全稱量詞左移，使所有的變元名稱均不相同； 消去存在量詞 把全稱量詞全部移到公式的左邊 母式化為和取范式,第三章 確定性推理方法,歸結(jié)過程的步驟 將命題寫成合取范式 根據(jù)給出的合取范式求出子句集 根據(jù)求得子句集，使用歸結(jié)原理進行歸結(jié) 歸結(jié)之后的新子句還要再次放入子句集，參加歸結(jié)。 直到歸結(jié)為空的時候，即使得問題得證,第三章 確定性推理方法,用歸結(jié)原理進行定理證明 首先否定結(jié)論，并將否定后的結(jié)論B與前提公式集相與A1 B，組成如下的謂詞公式G= A1 B 求謂詞公式G的字句集S 應(yīng)用歸結(jié)原理，證明子句集S的

8、不可滿足性，從而證明謂詞公式G的不可滿足性。這樣就說明對結(jié)論B的否定是錯誤的，推斷出定理的成立。,第三章 確定性推理方法,用歸結(jié)原理進行問題求解 把已知前提條件用謂詞公式表示出來，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。 把待求解問題用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個轉(zhuǎn)為求解問題而設(shè)置的謂詞，其變量必須與問題公式的變量完全一致。 把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。,第三章 確定性推理方法,歸結(jié)過程中的控制策略 刪除策略 純文字刪除法 重言式刪除法 包孕刪除法 支持集歸結(jié)策略 線性歸

9、結(jié)策略 單文字（單元）歸結(jié)策略 輸入歸結(jié)策略,第四章 不確定性推理,學(xué)習(xí)目標(biāo) 了解不確定性推理的含義、思路和討論的主要問題。 掌握可信度方法、主觀Bayes方法和證據(jù)理論不確定性推理方法,第四章 不確定性推理,計算問題 不確定性的傳遞問題 證據(jù)不確定性的合成問題 結(jié)論不確定性的合成問題,第四章 不確定性推理,可信度方法 知識不確定性的表示 在基于可信度的不確定性推理模型中，知識是以產(chǎn)生式規(guī)則來表示的，而只是的不確定性則是以可信度CF(H,E)來表示的，其一般的形式為：,第四章 不確定性推理,可信度方法 組合證據(jù)不確定性表示 當(dāng)多個證據(jù)以合取得方式構(gòu)成一個組合證據(jù)的時候，組合證據(jù)的可信度為這些單

10、一證據(jù)的可信度最小值； 當(dāng)多個證據(jù)以析取得方式構(gòu)成一個組合證據(jù)的時候，組合證據(jù)的可信度為這些單一證據(jù)的可信度最大值；,第四章 不確定性推理,MB(H,E)：信任增長度 MD(H,E)：不信任增長度 MB(H,E)與MD(H,E)是互斥的 解釋 當(dāng)MD(H,E)0時，應(yīng)該有P(H/E)0時，則為P(H/E) P(H),那么有MD(H,E)=0 如果P(H/E)= P(H),則MD(H,E)= MD(H,E)=0表示，E與H無關(guān),第四章 不確定性推理,不確定性的傳遞問題 單條知識 多條知識,第四章 不確定性推理,主觀Bayes方法 知識的不確定性 LS：充分性度量 LN：必要性度量 是為度量產(chǎn)生式

11、規(guī)則的不確定性而引入的一組數(shù)值。,第四章 不確定性推理,LS和LN的討論 LN和LS之間的關(guān)系 LS1且LN1,第四章 不確定性推理,主觀Bayes方法 證據(jù)的不確定性 給定了可信度C(E/S)，就等價于告知了P(E/S)， 組合證據(jù)的不確定性 當(dāng)證據(jù)E是由多個單一證據(jù)合取組合而成 當(dāng)證據(jù)E是由多個單一證據(jù)析取組合而成 對于非運算,第四章 不確定性推理,不確定性的傳遞問題 當(dāng)證據(jù)肯定出現(xiàn)的時候P(E)=P(E/S)=1 肯定出現(xiàn)的時候，用下面的式子既可以把先驗幾率O(H)更換為后驗幾率O(H/E) 如果我們把幾率用概率替換即可得,第四章 不確定性推理,在證據(jù)肯定不出現(xiàn)時P(E)=P(E/S)=

12、0, P(E)=1. 那么用下式計算當(dāng)E肯定不出現(xiàn)的情況下，把先驗幾率O(H)更新為O(H/E) 根據(jù)概率和幾率的換算關(guān)系可得,第四章 不確定性推理,用概率表示證據(jù)的不確定性 上述針對確定性證據(jù)的后驗概率將不再適用而要使用下面的公式。,第四章 不確定性推理,P(E/S)=1; P(H/S)=P(H/E) P(E/S)=0; P(H/S)=P(H/E) P(E/S)=P(E); P(H/S)=P(H),第四章 不確定性推理,利用這三個特殊點，使用分段插值公式可得P(E/S)與P(H/S)的解析表達(dá)式,第四章 不確定性推理,若有n條知識都支持相同的結(jié)論，并且每條知識的前提條件所對應(yīng)的證據(jù)Ei都有相

13、應(yīng)的觀察Si，這時需要按照下面的式子求得P(H/S1,Sn),D-S理論的數(shù)學(xué)基礎(chǔ),信任函數(shù) Bel：2D 0,1。 似然函數(shù) Pl: 2D 0,1,D-S理論的數(shù)學(xué)基礎(chǔ),概率分配函數(shù)正交和 設(shè)M1和M2是兩個概率分配函數(shù)，則他們的正交和M=M1M2為 M() = 0; M(A) = K-1m1(X)m2(Y), 當(dāng)XY = A 其中K = 1 - m1(X)m2(Y), 當(dāng)XY = m1(X)m2(Y), 當(dāng)XY ,特定概率分配函數(shù),設(shè)樣本空間D=S1,S2,Sn,領(lǐng)域內(nèi)的命題都用D的子集來表示，則定義2D上的概率分配函數(shù)M(x)滿足如下條件,特定概率分配函數(shù),其中，|A|表示命題A對應(yīng)的集

14、合中所包含的元素個數(shù)。 在這種特定的概率分配函數(shù)中，定義了只有單個元素構(gòu)成的子集和樣本空間D本身的基本概率數(shù)才有可能大于0，其它子集的基本概率數(shù)均為0,基于特定概率分配函數(shù)的不確定性推理,信任度函數(shù) 性質(zhì),不確定性推理,信任度函數(shù) 推論,不確定性推理,證據(jù)的不確定性表示 證據(jù)E為初始簡單證據(jù)，f(E)由用戶給出 證據(jù)E為前面推理所得到的結(jié)論，f(E)有推理計算給出 證據(jù)E為組合證據(jù)的時候 由多個證據(jù)的合取組成 由多個證據(jù)的析取組成,不確定性推理,知識的不確定性表示 不確定性知識用如下形式的產(chǎn)生式規(guī)則表示 E為前提條件 H是結(jié)論，用樣本空間中的子集來表示，h1,h2,hn是該子集中的元素 CF是

15、該集合中的可信度因子，用集合的形式來表示。,不確定性推理,不確定性的傳遞計算方法 求出H的概率分配函數(shù) 求出H的信任函數(shù)Bel(H)和似然函數(shù)Pl(H) 求出結(jié)論H的信任度f(H),第五章 狀態(tài)空間的搜索策略,狀態(tài)空間搜索可以分為盲目搜索和啟發(fā)式搜索兩種 盲目搜索 又稱為無信息搜索。也就是在搜索的過程中只按預(yù)先的搜索控制策略進行搜索，而沒有任何中間信息來改變這些控制策略 啟發(fā)式搜索 稱為有信息搜索。它是指在問題搜索過程中，根據(jù)問題本身的特征或者搜索過程中產(chǎn)生出來的一些信息來不斷地改變或者調(diào)整搜索方向，使搜索朝著最有希望的方向前進，加速問題的求解，并找到最優(yōu)解。,第五章 狀態(tài)空間的搜索策略,回溯

16、搜索： 不是圖搜索-不能記憶路徑 BackTrack（DATA）遞歸過程 縱向遞歸 橫向循環(huán),第五章 狀態(tài)空間的搜索策略,狀態(tài)空間的搜索算法： 1 建立一個只含有初始節(jié)點S0的搜索圖G，把S0放入到open表中 2 建立closed表，并且將其置為空表 3 判斷open表是否為空表，若為空，則問題無解，退出。 4 若open表非空，則選擇open表中的第一個節(jié)點，把它從open表中移出，并放入closed表中，將此節(jié)點標(biāo)記為節(jié)點n。,第五章 狀態(tài)空間的搜索策略,5 考察節(jié)點n是 否為目標(biāo)節(jié)點，如果是，則問題有解，并且成功退出。問題的解既可從圖G中沿著指針從n到S0的這條路徑得到。 6 擴展節(jié)點

17、n生成一組不是n的祖先的后繼節(jié)點，并將它們記為集合M，將M中的這些節(jié)點作為n的后繼節(jié)點加入圖G中。,第五章 狀態(tài)空間的搜索策略,7 對于那些未曾在G中出現(xiàn)過的（即未曾在open表上或closed表上出現(xiàn)過的）M中的節(jié)點，設(shè)置一個指向父節(jié)點（即節(jié)點n）的指針，并把這些節(jié)點加入到open表中；對于已在G中出現(xiàn)過的M中的那些節(jié)點，確定是否需要修改指向父節(jié)點（n節(jié)點）的指針；對于那些先前已經(jīng)在G中出現(xiàn)并且已在closed表中的那些M中的節(jié)點，確定是否需要修改通向它們后繼點的指針。 8 按照某一種方式或者某種策略重排open表中的節(jié)點的順序 9 轉(zhuǎn)到第（3）步。,第五章 狀態(tài)空間的搜索策略,節(jié)點類型說明,第五章 狀態(tài)空間的搜索策略,盲目搜索 寬度優(yōu)先搜索 第六步，將節(jié)點放入open表的末端 應(yīng)用隊列來實現(xiàn) 深度優(yōu)先搜索 第六步，將節(jié)點放入open表的前端 應(yīng)用棧來實現(xiàn) 擴展：有界深度優(yōu)先搜索,第五章 狀態(tài)空間的搜索策略,考慮搜索代價問題 代價樹寬度優(yōu)先算法 第六步，計算擴展節(jié)點的代價，根據(jù)節(jié)點的代價大小