第二章人工智能邏輯第二部分課件

1、第二章 人工智能邏輯第二部分史忠植中國科學(xué)院計算技術(shù)研究所高級人工智能10/2/20221第二章 人工智能邏輯第二部分史忠植高級人工智能9/24/描 述 邏 輯 Description Logics10/2/20222描 述 邏 輯 Description Logics9/2主要內(nèi)容 什么是描述邏輯？ 為什么用描述邏輯？ 描述邏輯的研究進(jìn)展 描述邏輯的體系結(jié)構(gòu) 描述邏輯的構(gòu)造算子 描述邏輯的推理問題 我們的工作10/2/20223主要內(nèi)容 什么是描述邏輯？9/24/202231 什么是描述邏輯(DL)？一種基于對象的知識表示的形式化，也叫概念表示語言或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上

2、 概念解釋為對象的集合關(guān)系解釋為對象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個可判定的子集具有合適定義的語義(基于邏輯)10/2/202241 什么是描述邏輯(DL)？一種基于對象的知識表示的形式化特點(diǎn)是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化 框架系統(tǒng) (Frame-based systems) 語義網(wǎng)絡(luò) (Semantic Networks) 面向?qū)ο蟊硎?(OO representation) 語義數(shù)據(jù)模型 (Semantic data models) 類型系統(tǒng) (Type systems) 特征邏輯 (Feature Logics) 具有很強(qiáng)的表達(dá)能力 是可判定的，總能保

3、證推理算法終止10/2/20225特點(diǎn)是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化9/24/2022描述邏輯的應(yīng)用 概念建模 查詢優(yōu)化和視圖維護(hù) 自然語言語義 智能信息集成 信息存取和智能接口 工程的形式化規(guī)范 術(shù)語學(xué)和本體論 規(guī)劃 10/2/20226描述邏輯的應(yīng)用 概念建模 9/24/202262 為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，則： 知識的結(jié)構(gòu)將被破壞，這樣就不能用來驅(qū)動推理 對獲得可判定性和有效的推理問題來說，其表達(dá)能力太高，（也許是太抽象了） 對興趣表達(dá)，但仍然可判定的理論，其推理能力太低。DL的重要特征是： 很強(qiáng)的表達(dá)能力； 可判定性，它能保證推理算法總能停止，并返

4、回正確的結(jié)果。 10/2/202272 為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，在眾多知識表示的形式化方法中，描述邏輯在十多年來受到人們的特別關(guān)注，主要原因在于以下三點(diǎn) : 它們有清晰的模型-理論機(jī)制; 它們很適合于通過概念分類學(xué)來表示應(yīng)用領(lǐng)域； 它們提供了很用的推理服務(wù)。 它們可以被認(rèn)為是從基于框架的表示形式化向著精確的語義特征方向發(fā)展。此外，描述邏輯將分類學(xué)中表示和推理（專業(yè)推理）與在分類學(xué)中項的事實(shí)或?qū)嵗谋硎竞屯评恚〝嘌酝评恚﹨^(qū)別開來。 10/2/20228在眾多知識表示的形式化方法中，描述邏輯在十多9/24/2023 描述邏輯的研究進(jìn)展 描述邏輯的基礎(chǔ)研究研究描述邏輯

5、的構(gòu)造算子、表示和推理的基本問題，如可滿足性、包含檢測、一致性、可判定性等。一般都在最基本的ALC的基礎(chǔ)上在擴(kuò)展一些構(gòu)造算子，如數(shù)量約束、逆關(guān)系、特征函數(shù)、關(guān)系的復(fù)合等。TBox和Abox上的推理問題、包含檢測算法等。Schmidt-Schaub 和 Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項式時間內(nèi)判斷描述邏輯ALC概念的可滿足性問題。10/2/202293 描述邏輯的研究進(jìn)展9/24/20229 描述邏輯的擴(kuò)展研究A.Artale和E.Franconi (1998)提出了一個知識表示系統(tǒng)，用時間約束的方法將狀態(tài)、動作和規(guī)劃的表示統(tǒng)一起來。為了能讓描述邏輯處

6、理模態(tài)詞，F(xiàn).Baader將模態(tài)操作引入描述邏輯，證明了該描述邏輯公式的可滿足性問題是可判定的。 Wolter等對具有模態(tài)算子的描述邏輯進(jìn)行了深入系統(tǒng)的調(diào)查分析，并證明在恒定的領(lǐng)域假設(shè)下多種認(rèn)知和時序描述邏輯是可判定的。 另外如時序擴(kuò)展(Artale, Wolter)、模糊擴(kuò)展(Straccia)等。10/2/202210 描述邏輯的擴(kuò)展研究9/24/202210 描述邏輯的應(yīng)用研究描述邏輯在許多領(lǐng)域中被作為知識表示的工具，如信息系統(tǒng)（Catarci,1993）數(shù)據(jù)庫（Borgida,1995; Bergamaschi 1992; Sheth, 1993）軟件工程(Devambu, 1991)

7、網(wǎng)絡(luò)智能訪問（Levy， 1996； Blanco，1994）規(guī)劃（Seida, 1992）等 Horrocks對表達(dá)能力較強(qiáng)的描述邏輯進(jìn)行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和Dieter Fensel等人將描述邏輯、語義網(wǎng)和DAML結(jié)合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎(chǔ)。并在XML及其RDF上面進(jìn)行了擴(kuò)展，用描述邏輯來研究語義網(wǎng)絡(luò)和本體論。10/2/202211 描述邏輯的應(yīng)用研究9/24/2022114 描述邏輯的體系結(jié)構(gòu)一個描述邏輯系統(tǒng)包含四個基本組成部分：1）表示概念和關(guān)系（Role）的構(gòu)造集2）Tbox關(guān)于概念術(shù)語的斷言3

8、）Abox關(guān)于個體的斷言4）Tbox和Abox上的推理機(jī)制。 10/2/2022124 描述邏輯的體系結(jié)構(gòu)一個描述邏輯系統(tǒng)包含四個基本組成部分： 概念 解釋為一個領(lǐng)域的子集 例子：所有在校學(xué)習(xí)的人員的集合構(gòu)成“學(xué)生”概念又如：孩子，已婚的，哺乳動物等概念x | Student(x) ，x | Married(x) 關(guān)系(Roles) 屬性(二元謂詞，關(guān)系)例子：朋友，愛人， | Friend(x,y) ， | Loves(x,y) 1）DL的基本元素概念和關(guān)系10/2/202213 概念 解釋為一個領(lǐng)域的子集 關(guān)系(Roles) 知識庫TBox(模式)Man Human MaleHappy-f

9、ather Human Has-child.Female Abox(數(shù)據(jù))John: Happy-father : Has-child推理系統(tǒng)接口10/2/202214TBox(模式)Abox(數(shù)據(jù))推理系統(tǒng)接口9/24/2022）TBox語言是描述領(lǐng)域結(jié)構(gòu)的公理的集合定義: 引入概念的名稱 A C, A CFather Man has-child.HumanHuman Animal Biped包含：聲明包含關(guān)系的公理C D ( C D C D ，D C) has-degree.Masters has-degree.Bachelors一個解釋I滿足： C D iff CI = DIC D if

10、f CI DI一個解釋I滿足TBox T iff 它滿足T中的每個公理(IT)10/2/2022152）TBox語言定義: 引入概念的名稱 9/24/20221 概念 表示實(shí)體(一元謂詞，類)例子：學(xué)生，已婚的x | Student(x) ，x | Married(x) Bird Animal, Man Human 關(guān)系(Roles) 屬性(二元謂詞，關(guān)系)例子：朋友，愛人 | Friend(x,y) ， | Loves(x,y) TBox實(shí)例10/2/202216 概念 表示實(shí)體(一元謂詞，類) 關(guān)系(Roles) 概念斷言 表示一個對象是否屬于某個概念a:C例如：Tom是個學(xué)生，表示為To

11、m : Student或者Student(Tom)John : Man has-child.Female 關(guān)系斷言 表示兩個對象是否滿足一定的關(guān)系:R例如：John有個孩子叫Mary : has-child3）ABox語言（斷言部分）是描述具體情形的公理的集合10/2/202217 概念斷言 表示一個對象是否屬于某個概念 關(guān)系斷言 一個解釋I滿足： a : C iff aI CI :R iff RI一個解釋I滿足ABox A iff 它滿足A中的每個公理記為： I A一個解釋I滿足知識庫 = iff 它滿足T和A 記為： I 10/2/202218一個解釋I滿足： a : C iff aI C

12、I94）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI IHuman原子關(guān)系RRI I Ihas-child對概念C,D和關(guān)系(role)R合取C DCI DIHuman Male析取C DCI DIDoctor Lawyer非 CI C Male存在量詞 R.Cx| y. RIy CI has-child.Male全稱量詞 R.Cx| y. RI y CI has-child.Doctor10/2/2022194）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI I一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： 合取( )，吸取( )，非

13、( ) 量詞約束：存在量詞( )，全稱量詞()最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為：Man has-child.Male has-child.Female has-child.(Doctor Lawyer)5 DL中的構(gòu)造算子10/2/202220一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的5 DL中的構(gòu)造構(gòu)造算子語法語義例子數(shù)量約束n R . Cx| | y| RI ,y CI | n3 has-child .Male n R . Cx| | y| RI ,y CI | n 3 has-child .Male逆R -| RI has-child-傳遞閉包R

14、*(RI )*has-child*DL中的其它算子topTIMale MaleBottomMan Man另外，有兩個類似于FOL中的全集(true)和空集(false)的算子10/2/202221構(gòu)造算子語法語義例子數(shù)量約束n R . Cx| | y在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達(dá)能力的描述邏輯，其復(fù)雜性問題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆( - )算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(n , n )，則構(gòu)成ALCIQ。若在描述邏輯中添加時序算子，則構(gòu)成為時序描述邏輯(Temporal Description Logic)，例如，可以添加：Unti

15、l算子 U： C U DSince算子 S： C S D還可以加入其它算子，如模態(tài)算子 ， ， 等。10/2/202222在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不6 描述邏輯中的推理1) 一致性（協(xié)調(diào)性consistency）2) 可滿足性(satisfiability)3) 包含檢測（subsumption）4) 實(shí)例檢測 (instance checking)5) Tableaux算法6）可判定性7）計算復(fù)雜性10/2/2022236 描述邏輯中的推理1) 一致性（協(xié)調(diào)性consistenc1)一致性檢測(Consistency)知識庫是協(xié)調(diào)的嗎？即檢測是否有的模型 (

16、解釋) I ？ C關(guān)于Tbox T是協(xié)調(diào)的嗎？即檢測是否有T的模型 I 使得 C ？10/2/2022241)一致性檢測(Consistency)知識庫2) 概念可滿足性(Satisfiablity) 對一個概念C，如果存在一個解釋I使得CI是非空的，則稱概念C是可滿足的，否則是不可滿足的。 檢驗(yàn)一個概念的可滿足性，實(shí)際上就是看是否有解釋使得這個概念成立。例如：概念Male Female，即需要檢測是否有性別既是男的又是女的這樣的人。若確實(shí)是沒有這種兩性人，則我們斷言，這個概念是不可滿足的。 又如概念： student worker，它是可滿足的。即代表那些在職學(xué)生的集合。定理：概念C是可滿足

17、的，當(dāng)且僅當(dāng)C不包含于。 10/2/2022252) 概念可滿足性(Satisfiablity) 對一在知識庫中檢測：C D？即檢測 CI DI 是否在所有的解釋中成立？3) 概念包含(Subsumption)例如：bird animalcomputer equipment在Tbox中檢測：C D？即檢測 CI DI 是否在Tbox T的所有解釋中成立？10/2/202226在知識庫中檢測：3) 概念包含(Subsumption)例C D iff C D是不可滿足的。C T D iff C D關(guān)于T是不可滿足的。C 關(guān)于T是一致的 iff C T A A包含與可滿足性的關(guān)系 DDCC D 10

18、/2/202227C D iff C D是不可滿足的。包含與可滿足4）實(shí)例檢測(Instance checking)概念的實(shí)例：Student (John)，或者表示為 John:Student關(guān)系的實(shí)例：Father(John, Mary)實(shí)例檢索：檢索屬于某個概念的所有實(shí)例的集合10/2/2022284）實(shí)例檢測(Instance checking)概念的實(shí)例5）可滿足性檢測算法Tableaux算法1) 規(guī)則:S x:C1, x:C2S，若x:C1 C2在S中，且x:C1和x:C2不在S中同時出現(xiàn)。2) 規(guī)則:S x:DS，若x:C1C2在S中，x:C1和x:C2都不在S中，且D= C1或

19、者D= C2。3) 規(guī)則:S xP1y,xPky, y:CS，若x:R.C在S中，R= P1Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個新變量。4) 規(guī)則:S y:CS，若x:R.C在S中，xRy在S中成立，且y:C不在S中。 10/2/2022295）可滿足性檢測算法Tableaux算法1) 規(guī)則:9例子：檢測概念的可滿足性：(has-child.Male) (has-child.Male)，其檢測過程為：(has-child.Male) (has-child.Male)(x)(has-child.Male)(x)規(guī)則(has-child.Male)(x)規(guī)則has-child

20、 (x, y)規(guī)則Male (y)規(guī)則Male (y)規(guī)則矛盾所以這個概念是不可滿足的。10/2/202230例子：檢測概念的可滿足性：9/24/2022306）可判定性描述邏輯中的可滿足性問題是可判定的。其它推理問題基本上可以歸結(jié)為可滿足性問題。7）計算復(fù)雜性描述邏輯中的推理問題其計算復(fù)雜性一般是多項式時間的。但通常由于構(gòu)造的不同，其復(fù)雜性也有一定的差異。10/2/2022316）可判定性描述邏輯中的可滿足性問題是可判定的。7）計算復(fù)雜Semantic Web Architecture 10/2/202232Semantic Web Architecture 9/24我們的工作帶缺省的描述邏

21、輯定義 一個缺省規(guī)則是形如 這樣的表達(dá)式， 其中C、D、E為概念名，x是一個變元。C(x)稱為前提條件，D(x)稱為檢驗(yàn)條件(缺省)，E(x)稱為缺省的結(jié)論。定義1.2 一個知識庫是一個三元組，其中T為Tbox，A為Abox，D為缺省規(guī)則集。10/2/202233我們的工作帶缺省的描述邏輯9/24/202233動態(tài)描述邏輯 描述邏輯最開始只是用來表示靜態(tài)知識的。為了考慮在時間上的變化，或者在一定動作下的變化，以及保持其語言的相對簡單性，很自然地我們需要通過相應(yīng)的模態(tài)算子來擴(kuò)展它，以保留其命題模態(tài)狀態(tài)。 提出動態(tài)描述邏輯，用來描述主體中的動態(tài)知識以及推理。描述邏輯動態(tài)邏輯主體面向主體的動態(tài)描述邏

22、輯10/2/202234動態(tài)描述邏輯 描述邏輯最開始只是用來表示靜態(tài)知識的。 以客觀世界的形式化建模為研究內(nèi)容，提出一種統(tǒng)一的形式化框架，同時從靜態(tài)和動態(tài)兩個方面來刻畫世界的模型。為動態(tài)領(lǐng)域的建模提供一種有效的形式化理論工具；將世界中的概念、關(guān)系和個體，公理、事實(shí)和動作有機(jī)地整合在一起，形成統(tǒng)一的關(guān)聯(lián)和運(yùn)作機(jī)制，使動作與公理和事實(shí)相互作用，統(tǒng)一表示并進(jìn)行推理；對概念、公式和動作都給出了統(tǒng)一的、合適的語法和語義；主體與本體的結(jié)合 動態(tài)描述邏輯DDL10/2/202235 動態(tài)描述邏輯DDL9/24/202235動態(tài)描述邏輯DDLDDL：語義環(huán)境中對服務(wù)過程方面的建模和推理服務(wù)改變環(huán)境的狀態(tài)：前提

23、條件和執(zhí)行結(jié)果，Action服務(wù)描述：基于World Model，e.g., 描述服務(wù)的前提和結(jié)果的詞匯來自World ModelTBox描述World Model的結(jié)構(gòu)所有狀態(tài)的描述以數(shù)據(jù)庫或文本的形式分散在Web中用戶或Agent通過查詢的方式獲得狀態(tài)的信息，存放于各自的ABox中DL與Action的交互體現(xiàn)在：Action采用TBox中的詞匯描述前提和結(jié)果Action的執(zhí)行導(dǎo)致ABox的變化DDLDLAction10/2/202236動態(tài)描述邏輯DDLDDL：語義環(huán)境中對服務(wù)過程方面的建模和推An action description is the form of where (1) A

24、 is the action name.(2) x1, , xn are individual variables, which denote the objects the action operate on.(3) PA is the set of preconditions, which must be satisfied before the action is executed.(4) EA is the set of results, which denote the effects of the action. Dynamic Description Logic10/2/202237An action description is the f描述邏輯與語義Web有何區(qū)別與聯(lián)系？思 考描述邏輯與Prolog有何區(qū)別與聯(lián)系？描述邏輯可以在哪些方面進(jìn)行擴(kuò)展與完善？10/2/202238描述邏輯與語義Web有何區(qū)別與聯(lián)系？