知識表示方法

1、Artificial Intelligence (AI,Email：lyl_,第二章：知識表示方法,預(yù)備知識,人類的智能活動過程主要是一個獲得并運用知識的過程 按照符號主義的觀點，知識是一切智能行為的基礎(chǔ)，要使計算機具有智能，首先必須使它擁有知識 首先需要明確一下幾個問題 什么是知識 知識的劃分 人工智能系統(tǒng)中的知識 什么是知識表示,知識表示方法,知識的概念,知識的一般概念：知識是人們在改造客觀世界的實踐中積累起來的認(rèn)識和經(jīng)驗 認(rèn)識：包括對事物現(xiàn)象、本質(zhì)、屬性、狀態(tài)、聯(lián)系等的認(rèn)識 經(jīng)驗：包括解決問題的微觀方法和宏觀方法 微觀方法：如步驟、操作、規(guī)則、過程、技巧等 宏觀方法：如戰(zhàn)略、戰(zhàn)術(shù)、計謀、

2、策略等 eg：“if 大雁向南飛，then 冬天就要來臨了。”這樣一條知識就是人們經(jīng)過長期的觀察，將“大雁向南飛”與“冬天來臨”這兩條信息關(guān)聯(lián)在一起?！把┦前咨摹狈从逞┡c顏色的一種關(guān)系,知識的概念,知識、信息、數(shù)據(jù)及其關(guān)系 數(shù)據(jù)：是信息的載體，本身無確切含義。如：水的溫度是100，木頭的長度是2米，大樓的高度是100層 信息：是數(shù)據(jù)的關(guān)聯(lián)，賦予數(shù)據(jù)特定的含義，僅可理解為描述性知識。數(shù)據(jù)是沒有聯(lián)系的，孤立的，只有當(dāng)數(shù)據(jù)用來描述一個客觀事物和客觀事物的關(guān)系，形成有邏輯的數(shù)據(jù)流，他們才能被稱為信息。 知識：可以是對信息的關(guān)聯(lián)，也可以是對已有知識的再認(rèn)識。如：西安7月1日氣溫為30度，12月1日氣溫

3、為3度。當(dāng)對這類信息進行歸納和對比就會發(fā)現(xiàn)西安每年7月氣溫比較高，12月氣溫比較低。于是有價值的信息沉淀并結(jié)構(gòu)化后就形成了知識,知識的劃分,知識的劃分 按知識的性質(zhì)：概念、命題、公理、定理、規(guī)則和方法 按知識的作用域：常識性知識，領(lǐng)域性知識 按知識的等級： 零級知識：事實性知識。用于描述事物的概念、定義、屬性等； 或用于描述問題的狀態(tài)、環(huán)境、條件等。 一級知識：過程性知識。用于問題求解過程的操作、演算和行為的知識。表示方式：產(chǎn)生式、謂詞、語義網(wǎng)絡(luò)等。 二級知識：控制性知識，元知識或超知識。是關(guān)于如何使用過程性知識的知識。例如：推理策略、搜索策略、不確定性的傳播策略,知識的劃分,按知識的層次：

4、表層知識：描述客觀事物的現(xiàn)象的知識。例如：感性、事實性知識 深層知識：描述客觀事物本質(zhì)、內(nèi)涵等的知識。例如：理論知識 按知識的確定性： 確定性知識：可以說明其真值為真或為假的知識 不確定性知識：包括不精確、模糊、不完備知識 不精確：知識本身有真假，但由于認(rèn)識水平限制卻不能肯定知識的真假。表示：用可信度、概率等描述 模糊：知識本身的邊界就是不清楚的。例如：大，小等。表示：用可能性、隸屬度來描述 不完備：解決問題時不具備解決該問題的全部知識。例如：醫(yī)生看病,知識的劃分,按人類的思維及認(rèn)識方法： 邏輯性知識：是反映人類邏輯思維過程的知識，一般具有因果關(guān)系或難以精確描述的特點，是人類的經(jīng)驗性知識和直觀

5、感覺；如：人的為人處事的經(jīng)驗與風(fēng)格 形象性知識：通過事物的形象建立起來的知識。如:什么是人？ 按知識的獲取方式： 顯性知識：指可通過文字、語言、圖形、聲音等形式編碼記錄和傳播的知識；如：教材、音視頻光盤。 隱性知識：指人們長期實踐中積累獲得的知識，不易用顯性知識表達的知識。如：每個人都有不同的審美觀,人工智能系統(tǒng)中的知識,一個智能程序高水平的運行需要有關(guān)的事實知識、規(guī)則知識、控制知識和元知識。 事實知識：是有關(guān)問題環(huán)境的一些事物的知識，常以“是”的形式出現(xiàn)。 如事物的分類、屬性、事物間關(guān)系、科學(xué)事實、客觀事實等 事實是靜態(tài)的為人們共享的可公開獲得的公認(rèn)的知識，在知識庫中屬低層的知識。 如：雪是

6、白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的 規(guī)則知識：是有關(guān)問題中與事物的行動、動作相聯(lián)系的因果關(guān)系知識，是動態(tài)的，常以“如果那么” 形式出現(xiàn),人工智能系統(tǒng)中的知識,控制知識：是有關(guān)問題的求解步驟、技巧的知識，告訴人們怎么做一件事，也包括當(dāng)有多個動作同時被激活時應(yīng)選哪一個動作來執(zhí)行的知識。控制知識常與程序結(jié)合在一起出現(xiàn)，如一個問題求解的算法可以看做是一種知識表示。 元知識：是有關(guān)知識的知識，是知識庫中的高層知識。 包括怎樣使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序結(jié)構(gòu)等知識。 元知識與控制知識是有重迭的，對一個大的程序來說，以元知識或說元規(guī)則形式體現(xiàn)控制知識更為方便，因為元知識存于知識庫中

7、，而控制知識常與程序結(jié)合在一起出現(xiàn)，從而不容易修改,知識表示,知識表示：是研究用機器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。 知識表示的要求： 表示能力：能否正確、有效地表示問題。包括：表示范圍的廣泛性、領(lǐng)域知識表示的高效性、對非確定性知識表示的支持程度。 可利用性：可利用這些知識進行有效推理。包括：對推理的適應(yīng)性，對高效算法的支持程度。 可實現(xiàn)性：要便于計算機直接對其進行處理 可組織性：可以按某種方式把知識組織成某種知識結(jié)構(gòu) 可維護性：便于對知識的增、刪、改等操作 自然性：符合人們的日常習(xí)慣 可理解性：知識應(yīng)易讀、易懂、易獲取等

8、,內(nèi)容提要,第二章：知識表示方法,1.狀態(tài)空間法,2.問題歸約法,3.謂詞邏輯法,4.語義網(wǎng)絡(luò)法,5.其他方法,內(nèi)容提要,第二章：知識表示方法,1.狀態(tài)空間法,2.問題歸約法,3.謂詞邏輯法,4.語義網(wǎng)絡(luò)法,5.其他方法,狀態(tài)空間法,人工智能雖然有多個研究領(lǐng)域，而且每個研究領(lǐng)域又各有自己的規(guī)律和特點，都可抽象為一個“問題求解”的過程。問題求解過程實際上是一個搜索過程。 問題求解技術(shù)主要是兩個方面： 問題的表示 求解的方法 狀態(tài)空間法（State Space Representation）： 狀態(tài)空間法就是用來表示問題及其搜索過程的一種方法。它是人工智能中最基本的形式化方法，用“狀態(tài)（state

9、）”和“算符（operator）”來表示問題,狀態(tài)空間法,狀態(tài)空間法的三要素 (1) 狀態(tài)（state）：描述某類不同事物間的差別而引入的一組最少變量 q0，q1，qn的有序集合，是表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)。有序集合中每個元素qi（i= 0,1,.,n）為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài)。 (2) 算符（operator）：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。 (3) 狀態(tài)空間方法：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。S：所有可能的問題初始狀態(tài)集合；F：操作符集合；G：目標(biāo)

10、狀態(tài)集合,狀態(tài)空間法,狀態(tài)空間法舉例：下棋、迷宮及各種游戲。 十五數(shù)碼難題(15 puzzle)：由15個編有1至15并放在44方格棋盤上的可走動的棋子組成,初始棋局,目標(biāo)棋局,十五數(shù)碼難題,初始狀態(tài),目標(biāo)狀態(tài),如何把初試棋局 變成目標(biāo)棋局,首先把適用的算符 用于初始狀態(tài)，以產(chǎn)生新的狀態(tài),再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止,狀態(tài)空間法,狀態(tài)圖示法：狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。狀態(tài)圖中有幾個術(shù)語。 節(jié)點(Node)：圖形上的匯合點，用來表示狀態(tài)、事件和時間關(guān)系的匯合。 弧線(Arc)：節(jié)點間的連接線，表示算符； 有向圖(Directed Graph)：一

11、對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。 后繼節(jié)點(Descendant node)與父輩節(jié)點(Parent node)：如果某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni的后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj的父輩節(jié)點或祖先,狀態(tài)空間法,狀態(tài)圖示法：狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。狀態(tài)圖中有幾個術(shù)語。 路徑(Path)：某個節(jié)點序列(ni1,ni2,nik)當(dāng)j=2,3,k時，如果對于每一個ni,j-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。 代價(Cost)：用c(ni,nj)來表示從節(jié)點ni指向節(jié)點nj的 那段

12、弧線的代價。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。 圖的顯示說明/隱示說明：指各節(jié)點及其具有代價的弧線可以/不可以由一張表明確給出。顯然，顯示說明對于大型的圖是不切實際的，而對于具有無限節(jié)點集合的圖則是不可能的,狀態(tài)空間法,問題的表示對求解工作有很大影響。人們希望有較小的狀態(tài)空間表示。 例如，對于十五數(shù)碼問題： 可以規(guī)定15460條規(guī)則， 即“上移棋子1，下移棋子1，左移棋子1，右移棋子1 ”， 如果用“上下左右移動空格”，則只需4條規(guī)則。所以，移動空格是一種較好的表示,狀態(tài)空間法,狀態(tài)空間法舉例： 猴子和香蕉問題：在一個房間內(nèi)有一只猴子、一個箱子和一束香蕉。香蕉掛在天花

13、板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢,猴子和香蕉問題,解題過程 用一個四元表列（W，x，Y，z）來表示這個問題狀態(tài) W：猴子的水平位置； x： 當(dāng)猴子在箱子頂上時取1；否則取0； Y： 箱子的水平位置； z： 當(dāng)猴子摘到香蕉時取1；否則取0。 初始狀態(tài)為(a,0,b,0) ，目標(biāo)狀態(tài)為(c,1,c,1) 這個問題的操作（算符）如下： goto（U）表示猴子走到水平位置U pushbox（V）猴子把箱子推到水平位置V climbbox猴子爬上箱頂 grasp猴子摘到香蕉,猴子和香蕉問題,解題過程 該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為： Step1: goto(b) S

14、tep2: pushbox(c) Step3: climbbox Step4: grasp,猴子和香蕉問題,狀態(tài)空間圖,內(nèi)容提要,第二章：知識表示方法,1.狀態(tài)空間法,2.問題歸約法,3.謂詞邏輯法,4.語義網(wǎng)絡(luò)法,5.其他方法,問題歸約法,問題歸約（Problem Reduction） 是另外一種基于狀態(tài)空間的問題描述與求解方法 已知問題的描述，通過一系列變換把此問題變?yōu)橐粋€子問題集合 這些子問題的解可以直接得到（本原問題），從而解決了初始問題,問題歸約法,問題歸約法的組成部分 一個初始問題描述； 一套把問題變換為子問題的操作符； 一套本原問題描述。(本原問題:不能再分解或變換且直接可解的子

15、問題) 問題歸約的實質(zhì)： 從目標(biāo)（要解決的問題）出發(fā)逆向推理，建立子問題以及子問題的子問題，直到最后把初始問題歸約為一個本原問題集合,問題歸約法,問題歸約法舉例： 漢諾塔問題（ Hanoi ） 從1移到3 每次移動一個盤子 大盤在下小盤在上,初始狀態(tài)（111,目標(biāo)狀態(tài)（333,漢諾塔問題,原始問題可以歸約為下列3個子問題,子問題1：移動圓盤A和 B至柱子2（借助柱子3,子問題2：移動圓盤C至柱子3,子問題3：把圓盤A和B移至柱子3（借助柱子1,漢諾塔問題,歸約過程（3個圓盤,漢諾塔問題,漢諾塔問題歸約圖,本原問題,本原問題,與或圖,問題歸約法,與或圖表示：用一個類似于圖的結(jié)構(gòu)來表示把問題歸約為

16、后繼問題的替換集合,與圖：把一個復(fù)雜問題分解為若干個較為簡單的子問題，形成“與”樹。 或圖： 利用同構(gòu)或同態(tài)的等價變換，把原問題變換為若干個較為容易求解的新問題，形成“或”樹,問題歸約法,與或圖表示,子問題替代集合結(jié)構(gòu)圖,與或圖,問題歸約法,一些關(guān)于與或圖的術(shù)語,起始節(jié)點對應(yīng)于原始問題描述,終葉節(jié)點對應(yīng)于本原問題,問題歸約法,與或圖的構(gòu)成規(guī)則 1）與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含起始節(jié)點對應(yīng)于原始問題A。 2）對應(yīng)于本原問題的節(jié)點稱為終葉節(jié)點，它沒有后繼節(jié)點。 3）對于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向弧線自A指向后繼節(jié)點表示所求

17、得的子問題集合,問題歸約法,與或圖的構(gòu)成規(guī)則 4）一般對于代表兩個或兩個以上子問題集合的每個節(jié)點，有向弧線從此節(jié)點指向次子問題集合中的各個節(jié)點。由于只有當(dāng)集合中所有項都有解時，這個子問題的集合才能獲得解答，所以這些子問題節(jié)點叫做與節(jié)點。 5）特殊情況下，當(dāng)只有一個算符可應(yīng)用于問題A，而且這個算符產(chǎn)生具有一個以上子問題的某個集合時，由上述規(guī)則3）和規(guī)則4）所產(chǎn)生的圖可以得到簡化,簡化,問題歸約法,與或圖的搜索：目的在于表明起始節(jié)點是有解的。 可解節(jié)點 終葉節(jié)點是可解節(jié)點（對應(yīng)于本原問題）。 如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只要當(dāng)其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。 如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只有當(dāng)其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的,問題歸約法,不可解節(jié)點 沒有后裔的非終葉節(jié)點為不可解節(jié)點。 如果某個非終葉節(jié)點