人工智能課件-老師2014年春5知識表示方法part

1、Artificial Intelligence (AI)人工智能主講：戚玉濤Email： 第二章：知識表示方法內(nèi)容提要第二章：知識表示方法1.狀態(tài)空間法2.問題歸約法3.謂詞邏輯法4.語義網(wǎng)絡(luò)法5.其他方法謂詞邏輯法命題邏輯與謂詞邏輯命題命題邏輯的局限性謂詞謂詞邏輯法謂詞演算謂詞邏輯語言的語法和語義謂詞邏輯語言的基本符號：謂詞符號變量符號函數(shù)符號常量符號括號和逗號謂詞邏輯法謂詞演算謂詞邏輯語言的語法和語義原子公式：原子公式由若干謂詞符號和項組成謂詞符號規(guī)定定義域內(nèi)的一個相應關(guān)系常量符號是最簡單的項，表示論域內(nèi)的物體或?qū)嶓w變量符號也是項，不明確涉及是哪一個實體函數(shù)符號表示論域內(nèi)的函數(shù)，是從論域內(nèi)

2、的一個實體到另外一個實體的映射例如：原子公式 Married father(LI) , mother(LI) 表示“李（LI）的父親和他的母親結(jié)婚”謂詞邏輯法連詞和量詞連詞合?。悍枴?”， 表示所連結(jié)的兩個命題之間具有“與”的關(guān)系。析?。?符號“ ”，表示所連結(jié)的兩個命題之間具有“或”的關(guān)系蘊涵：符號“ ” ，表示“若則”的語義。PQ讀作“如果P，則Q”其中，P稱為條件的前件，Q稱為條件的后件。非：符號“ ”，表示對其后面的命題的否定雙條件：符號“ ”，表示“當且僅當”的語義。 PQ讀作“P當且僅當Q”。連詞的優(yōu)先級：,謂詞邏輯法連詞和量詞量詞全稱量詞：符號“”，意思是“所有的”、“任一個”

3、x讀作“對一切x”,或“對每一x”，或“對任一x”。命題(x)P(x)為真，當且僅當對論域中的所有x，都有P(x)為真命題(x)P(x)為假，當且僅當至少存在論域中的一個x，使得P(x)為假謂詞邏輯法連詞和量詞量詞存在量詞：符號“”，意思是“至少有”、“存在” x讀作“存在一個x”,或“對某些x”，或“至少有一x”。命題(x)P(x)為真，當且僅當至少存在論域中的一個x，使得P(x)為真命題( x)P(x)為假，當且僅當對論域中的所有x，都有P(x)為假 謂詞邏輯法謂詞公式原子謂詞公式：是由謂詞符號和若干項組成的謂詞演算。若t1,t2,tn是項，P是謂詞，則稱P(t1,t2,tn)為原子謂詞公

4、式。分子謂詞公式：可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。謂詞邏輯法謂詞公式合式公式（WFF，Well-formed Formulas）：通常把合式公式叫做謂詞公式，遞歸定義如下：(1) 原子謂詞公式是合式公式(2) 若A為合式公式，則 A也是一個合式公式(3) 若A,B是合式公式，則AB，AB，AB，AB也都是合式公式(4) 若A是合式公式，x為A中的自由變元，則 (x)A和( x)A都是合式公式(5) 只有按上述規(guī)則(1)至(4)求得的那些公式，才是合式公式。謂詞邏輯法謂詞公式用謂詞公式表示知識時，需要首先定義謂詞，然后再用連接詞把有關(guān)的謂詞連接起來，形成一個謂詞

5、公式表達一個完整的意義。例1：設(shè)有下列知識劉歡比他父親出名。高揚是計算機系的一名學生，但他不喜歡編程 。 任何整數(shù)或者為正或者為負。 為了用謂詞公式表示上述知識，首先需要定義謂詞：FAMOUS (x, y) : x比y出名COMPUTER ( x ) : x 是計算機系的LIKE (x, y ) : x 喜歡 y謂詞邏輯法I(x)表示“x是整數(shù)”P(x)表示“x是正數(shù)”N(x)表示“x是負數(shù)” 此時可用謂詞公式把上述知識表示為:劉歡比他父親出名: FAMOUS ( liuhuan, father ( liuhuan )高揚是計算機系的一名學生，但他不喜歡編程 :COMPUTER(gaoyang

6、)LIKE(gaoyang, programing)任何整數(shù)或者為正或者為負:(x)(I(x) (P(x) N(x)謂詞邏輯法謂詞公式例2：用謂詞邏輯描述右圖中的房子的概念個體 ：A , B謂詞 ：SUPPORT( x,y )：表示 x 被 y支撐著 WEDGE ( x )：表示 x 是楔形塊 BRICK( y )：表示 y 是長方塊 其中 x , y是個體變元，它們的個體域A,B房子的概念可以表示成一組合式謂詞公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )謂詞邏輯法合式公式的性質(zhì)若P、Q是兩個合式公式，則由這兩個合式公式所組成的復合表達式可由下列真值表給

7、出。PQPPQPQPQPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT謂詞邏輯法合式公式的性質(zhì)如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是等價的。應用上述真值表可以確立下列等價關(guān)系：（1）否定之否定： ( P ) = P（2）( P Q ) = ( P Q ) 或者 ( P Q ) = ( P Q ）（3）狄 摩根定律： ( P Q ) = P Q ( P Q ) = P Q謂詞邏輯法（4）分配律：P ( Q R ) = ( P Q ) ( P R )P ( Q R ) = ( P Q ) ( P R )（5）交換律： P Q = Q PP Q =

8、 Q P（6）結(jié)合律：P ( Q R ) = ( P Q ) RP ( Q R ) = ( P Q ) R（7）逆否率：( P Q ) = ( Q P ) 謂詞邏輯法（8）泛界律：P F = P , P T = P P F = F , P T = T （9）互余律：P P = T, P P = F此外還可以確立下列等價關(guān)系： ( x) P(x) = (x) P(x) (x) P(x) = ( x) P(x) (x) P(x) Q(x) = (x) P(x) (x) Q(x) (x) P(x) Q(x) = (x) P(x) (x) Q(x) (x) P(x) = (y) P(y) ( x) P

9、(x) = ( y) P(y) 謂詞邏輯法置換與合一置換 推理規(guī)則：用合式公式的集合產(chǎn)生新的合式公式假元推理全稱化推理綜合推理 W2W1 W1 W2 W(A)(x) W(x) 任意常量A W2(A) W1(A)(x) W1(x) W2(x)尋找A對x的置換，使W1(A)與W1(x)一致謂詞邏輯法置換與合一置換（Substitution）置換的定義：置換是用變元、常量、函數(shù)來替換變元，使該變元不在公式中出現(xiàn)。置換是形如 t1/x1, t2/x2, ， tn/xn的有限集合。t1，t2， ， tn是項x1，x2， ， xn是互不相同的變元ti/xi表示用ti項替換變元xi，不允許ti和xi相同，也

10、不允許變元xi循環(huán)地出現(xiàn)在另一個tj中謂詞邏輯法置換與合一置換（Substitution）例如a/x , f(b)/y ，w/z 是一個置換g(y)/x , f(x)/y 不是一個置換g(a)/x , f(x)/y 不是一個置換謂詞邏輯法置換與合一置換（Substitution）例2.2（P40），表達式 Px, f(y), B的置換為s1= z/x, w/y； s2= A/y；s3= q(z)/x , A/y； s4= c/x , A/y 用Es表示一個表達式E用置換s所得到的表達式的置換。于是，Px, f(y), B的4個置換如下：Px, f(y), B s1 = Pz, f(w), B

11、Px, f(y), B s2 = Px, f(A), B Px, f(y), B s3 = Pq(z), f(A), B Px, f(y), B s4 = Pc, f(A), B 謂詞邏輯法置換與合一置換（Substitution）置換是可結(jié)合的用s1s2表示兩個置換s1和s2的合成，L表示一個表達式，則有（Ls1）s2 = L（s1s2 ）即用s1和s2相繼作用于表達式L是與用s1s2作用于L一樣的進一步推廣：（s1s2）s3 = s1（s2s3 ）一般說來，置換是不可交換的，即 s1s2 s2s1謂詞邏輯法置換與合一合一（Unification）合一的定義：尋找項對變量的置換，以使兩表達式

12、一致。如果一個置換s作用于表達式集合Ei的每個元素，用Eis表示置換的集。稱表達式Ei是可合一的，如果存在一個置換s使得： E1s = E2s = E3s = 那么，稱此s為Ei的合一者（unifier），因為s的作用是使集合Ei成為單一形式。謂詞邏輯法置換與合一合一（Unification）例如，設(shè)有公式集 E= P( x, y, f(y), P( a, g(x), z) 則下式是它的一個合一： s=a/x, g(a)/y, f(g(a)/z謂詞邏輯法謂詞邏輯法舉例：猴子和香蕉問題描述狀態(tài)的謂詞：AT(x, y)：x在y處ONBOX：猴子在箱子上HB：猴子得到香蕉個體域：x ：monkey,

13、 box, bananay：a, b, c問題的初始狀態(tài)AT(monkey, a) AT(box, b) ONBOX HB問題的目標狀態(tài)AT(monkey, c) AT(box, c)ONBOX HB猴子和香蕉問題描述操作的謂詞 Goto(u, v)：猴子從u處走到v處 條件：ONBOX ，AT(monkey, u)動作：刪除表：AT(monkey, u)；添加表：AT(monkey, v)Pushbox(v, w)：猴子推著箱子從v處移到w處條件： ONBOX ，AT(monkey, v)，AT(box, v)動作：刪除表：AT(monkey, v)，AT(box, v) 添加表：AT(mo

14、nkey, w)，AT(box,w)Climbbox：猴子爬上箱子條件： ONBOX ，AT(monkey, w)，AT(box,w)動作：刪除表： ONBOX；添加表：ONBOXGrasp：猴子摘取香蕉條件：ONBOX，AT(box, c)動作：刪除表： HB；添加表：HB猴子和香蕉問題猴子和香蕉問題求解過程：初始狀態(tài)AT(monkey, a) AT(box, b) ONBOX HBGoto(a, b)狀態(tài)1AT(monkey, b) AT(box, b) ONBOX HBPushbox(b, c)狀態(tài)2AT(monkey, c) AT(box, c) ONBOX HBClimbbox狀態(tài)3

15、AT(monkey, c) AT(box, c)ONBOX HB目標狀態(tài)AT(monkey, c) AT(box, c)ONBOX HBGrasp謂詞邏輯法主要優(yōu)點自然：一階謂詞邏輯是一種接近于自然語言的形式語言系統(tǒng)，謂詞邏輯表示法接近于人們對問題的直觀理解明確：有一種標準的知識解釋方法，因此用這種方法表示的知識明確、易于理解精確：謂詞邏輯的真值只有“真”與“假”，其表示、推理都是精確的靈活：知識和處理知識的程序是分開的，無須考慮處理知識的細節(jié)模塊化：知識之間相對獨立，這種模塊性使得添加、刪除、修改知識比較容易進行謂詞邏輯法主要缺點知識表示能力差：只能表示確定性知識，而不能表示非確定性知識、過

16、程性知識和啟發(fā)式知識知識庫管理困難：缺乏知識的組織原則，知識庫管理比較困難存在組合爆炸：由于難以表示啟發(fā)式知識，因此只能盲目地使用推理規(guī)則，這樣當系統(tǒng)知識量較大時，容易發(fā)生組合爆炸系統(tǒng)效率低：它把推理演算與知識含義截然分開，拋棄了表達內(nèi)容中所含有的語義信息，往往使推理過程冗長，降低了系統(tǒng)效率內(nèi)容提要第二章：知識表示方法1.狀態(tài)空間法2.問題歸約法3.謂詞邏輯法4.語義網(wǎng)絡(luò)法5.其他方法語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)法（ Semantic Network Representation ）語義網(wǎng)絡(luò)是奎廉(J. R. Quillian) 1968年在研究人類聯(lián)想記憶時提出的一種心理學模型，認為記憶是由概念間的聯(lián)

17、系實現(xiàn)的。隨后，奎廉又把它用作知識表示。1972年，西蒙在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)表示法。語義網(wǎng)絡(luò)是一種表達能力強而且靈活的知識表示方法，目前已經(jīng)廣泛應用于人工智能領(lǐng)域，尤其是在自然語言處理方面。語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)是通過概念及其語義關(guān)系來表達知識一種網(wǎng)絡(luò)圖。從圖論的觀點看，語義網(wǎng)絡(luò)是一個“帶標識的有向圖”有向圖的節(jié)點代表實體，表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等；節(jié)點還可以是一個語義子網(wǎng)絡(luò)，形成嵌套結(jié)構(gòu)。有向圖的弧代表語義關(guān)系，表示它所連結(jié)的兩個實體之間的語義聯(lián)系，它必須帶有標識。語義網(wǎng)絡(luò)法語義基元語義網(wǎng)絡(luò)中最基本的語義單元稱為語義基元，可用三元組表示為：

18、（結(jié)點1，弧，結(jié)點2）基本網(wǎng)元指一個語義基元對應的有向圖例如：若有語義基元（A, R, B），其中，A、B分別表示兩個結(jié)點，R表示A與B之間的某種語義聯(lián)系，則它所對應的基本網(wǎng)元如下圖所示：ABR語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的簡單例子例如：用于一網(wǎng)絡(luò)表示“鴕鳥是一種鳥”語義網(wǎng)絡(luò)的表示能力事實的表示：例如：“雪的顏色是白的”規(guī)則的表示：例如：“規(guī)則R：如果 A 則B”鴕鳥鳥是一種雪白顏色ABR語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（1）類屬關(guān)系類屬關(guān)系體現(xiàn)的是“具體與抽象”的概念，通常指具有共同屬性的不同事物之間的實例關(guān)系、成員關(guān)系或分類關(guān)系。常有的類屬關(guān)系有：Is-a(是一個)、A-member-of（是一員）

19、、A-kind-of（是一種）。例如：張寧是一個學生。張寧學生Is-a語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（2）聚集關(guān)系如果一個事物是另一事物的組成部分或某個方面，則它們之間的關(guān)系就是聚集關(guān)系。常用的聚集關(guān)系有：A-part-of（是一部分）。例如：手是人體的一部分。手人體A-part-of 語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（3）屬性關(guān)系屬性關(guān)系表示了對象和其屬性之間的聯(lián)系。常用的屬性關(guān)系有：Have(有)、Can（能、會）、Owner（所有者）。 例如：張寧會說英語，年齡18歲，身高160cm。張寧英語18160havehavecan語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（4）推論關(guān)系如果一個概念可由另一個概念推出，兩個概念間存在因果關(guān)系，則稱它們之間是推論關(guān)系，可以用Fetch(推出)表示。 例如：饑餓推出需要進食饑餓需要進食Fetch語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的基本語義關(guān)系（5）相近關(guān)系相近關(guān)系是指不同事