1、第二章第二章 人工智能邏輯人工智能邏輯第二部分第二部分史忠植史忠植中國科學(xué)院計算技術(shù)研究所中國科學(xué)院計算技術(shù)研究所高級人工智能高級人工智能描 述 邏 輯 Description Logics2022-4-13史忠植 高級人工智能3主要內(nèi)容 什么是描述邏輯？什么是描述邏輯？ 為什么用描述邏輯？為什么用描述邏輯？ 描述邏輯的研究進展描述邏輯的研究進展 描述邏輯的體系結(jié)構(gòu)描述邏輯的體系結(jié)構(gòu) 描述邏輯的構(gòu)造算子描述邏輯的構(gòu)造算子 描述邏輯的推理問題描述邏輯的推理問題 我們的工作我們的工作2022-4-13史忠植 高級人工智能41 什么是描述邏輯(DL)？一種基于對象的知識表示的形式化，一種基于對象的知

2、識表示的形式化，也叫概念表示語言或術(shù)語邏輯。也叫概念表示語言或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上 概念解釋為對象的集合關(guān)系解釋為對象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個可判定的子集具有合適定義的語義(基于邏輯)2022-4-13史忠植 高級人工智能5特點特點是以往表示工具的邏輯重構(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) 特征邏輯 (

3、Feature Logics) 具有很強的表達能力 是可判定的，總能保證推理算法終止2022-4-13史忠植 高級人工智能6描述邏輯的應(yīng)用描述邏輯的應(yīng)用 概念建模 查詢優(yōu)化和視圖維護 自然語言語義 智能信息集成 信息存取和智能接口 工程的形式化規(guī)范 術(shù)語學(xué)和本體論 規(guī)劃 2022-4-13史忠植 高級人工智能72 2 為什么用描述邏輯？為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，則： 知識的結(jié)構(gòu)將被破壞，這樣就不能用來驅(qū)動推理 對獲得可判定性和有效的推理問題來說，其表達能力太高，（也許是太抽象了） 對興趣表達，但仍然可判定的理論，其推理能力太低。DLDL的重要特征是：的重要特征是：

4、 很強的表達能力； 可判定性，它能保證推理算法總能停止，并返回正確的結(jié)果。 2022-4-13史忠植 高級人工智能8在眾多知識表示的形式化方法中，描述邏輯在十多年來受到人們的特別關(guān)注，主要原因在于以下三點 : 它們有清晰的模型-理論機制; 它們很適合于通過概念分類學(xué)來表示應(yīng)用領(lǐng)域； 它們提供了很用的推理服務(wù)。 它們可以被認為是從基于框架的表示形式化向著精確的語義特征方向發(fā)展。此外，描述邏輯將分類學(xué)中表示和推理（專業(yè)推理）與在分類學(xué)中項的事實或?qū)嵗谋硎竞屯评恚〝嘌酝评恚﹨^(qū)別開來。 2022-4-13史忠植 高級人工智能93 描述邏輯的研究進展描述邏輯的研究進展 描述邏輯的基礎(chǔ)研究描述邏輯的基礎(chǔ)

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

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

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

8、斷言3）Abox關(guān)于個體的斷言4）Tbox和Abox上的推理機制。 2022-4-13史忠植 高級人工智能13 概念概念 解釋為一個領(lǐng)域的子集 例子：所有在校學(xué)習(xí)的人員的集合構(gòu)成“學(xué)生”概念又如：孩子，已婚的，哺乳動物等概念x | Student(x) ，x | Married(x) 關(guān)系關(guān)系(Roles) 屬性(二元謂詞，關(guān)系)例子：朋友，愛人， | Friend(x,y) ， | Loves(x,y) 1 1）DLDL的基本元素的基本元素概念和關(guān)系概念和關(guān)系2022-4-13史忠植 高級人工智能14知識庫TBox(模式)Man Human MaleHappy-father Human Ha

9、s-child.Female Abox(數(shù)據(jù))John: Happy-father : Has-child推理系統(tǒng)接口2022-4-13史忠植 高級人工智能152 2）TBoxTBox語言語言是描述領(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 iff CI DI一個解釋I滿足TBox T i

10、ff 它滿足T中的每個公理(IT)2022-4-13史忠植 高級人工智能16 概念概念 表示實體(一元謂詞，類)例子：學(xué)生，已婚的x | Student(x) ，x | Married(x) Bird Animal, Man Human 關(guān)系關(guān)系(Roles) 屬性(二元謂詞，關(guān)系)例子：朋友，愛人 | Friend(x,y) ， | Loves(x,y) TBox實例實例2022-4-13史忠植 高級人工智能17 概念斷言概念斷言 表示一個對象是否屬于某個概念a:C例如：Tom是個學(xué)生，表示為Tom : Student或者 Student(Tom)John : Man has-child.F

11、emale 關(guān)系斷言關(guān)系斷言 表示兩個對象是否滿足一定的關(guān)系:R例如：John有個孩子叫Mary : has-child3 3）ABoxABox語言（斷言部分）語言（斷言部分）是描述具體情形的公理的集合是描述具體情形的公理的集合2022-4-13史忠植 高級人工智能18一個解釋I滿足： a : C iff aI CI :R iff RI一個解釋I滿足ABox A iff 它滿足A中的每個公理記為： I A一個解釋I滿足知識庫 = iff 它滿足T和A 記為： I 2022-4-13史忠植 高級人工智能194 4）語法和語義）語法和語義構(gòu)造算子構(gòu)造算子語法語法語義語義例子例子原子概念A(yù)AI IH

12、uman原子關(guān)系RRI I Ihas-child對概念對概念C,D和關(guān)系和關(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.Doctor2022-4-13史忠植 高級人工智能20一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： 合取( )，吸取( )，非( ) 量詞約束：存在量詞( )，全稱量詞()最基本的DL稱之為ALC例如，A

13、LC中概念Happy-father定義為：Man has-child.Male has-child.Female has-child.(Doctor Lawyer)5 DL DL中的構(gòu)造算子中的構(gòu)造算子2022-4-13史忠植 高級人工智能21構(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*(RI )*has-child*DLDL中的其它算子中的其它算子topTIMa

14、le MaleBottomMan Man另外，有兩個類似于FOL中的全集(true)和空集(false)的算子2022-4-13史忠植 高級人工智能22在在DLDL中添加算子中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達能力的描述邏輯，其復(fù)雜性問題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆( - )算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(n , n )，則構(gòu)成ALCIQ。若在描述邏輯中添加時序算子，則構(gòu)成為時序描述邏輯(Temporal Description Logic)，例如，可以添加：Until算子 U： C U DSince算子 S： C S D還可以加入其它算子，如模態(tài)

15、算子 ， ， 等。2022-4-13史忠植 高級人工智能236 描述邏輯中的推理1) 一致性（協(xié)調(diào)性consistency）2) 可滿足性(satisfiability)3) 包含檢測（subsumption）4) 實例檢測 (instance checking)5) Tableaux算法6）可判定性7）計算復(fù)雜性2022-4-13史忠植 高級人工智能241)1)一致性檢測一致性檢測(Consistency)(Consistency)知識庫知識庫是協(xié)調(diào)的嗎？是協(xié)調(diào)的嗎？即檢測是否有的模型 (解釋) I ？ C關(guān)于關(guān)于Tbox T是協(xié)調(diào)的嗎？是協(xié)調(diào)的嗎？即檢測是否有T的模型 I 使得 C ？20

16、22-4-13史忠植 高級人工智能252) 2) 概念可滿足性概念可滿足性( (Satisfiablity) ) 對一個概念C，如果存在一個解釋I使得CI是非空的，則稱概念C是可滿足的，否則是不可滿足的。 檢驗一個概念的可滿足性，實際上就是看是否有解釋使得這個概念成立。例如：概念Male Female，即需要檢測是否有性別既是男的又是女的這樣的人。若確實是沒有這種兩性人，則我們斷言，這個概念是不可滿足的。 又如概念： student worker，它是可滿足的。即代表那些在職學(xué)生的集合。定理：定理：概念C是可滿足的，當(dāng)且僅當(dāng)C不包含于。 2022-4-13史忠植 高級人工智能26在知識庫中檢測

17、在知識庫中檢測：C D？即檢測 CI DI 是否在所有的解釋中成立？3) 3) 概念包含概念包含( (Subsumption) )例如：例如：bird animalcomputer equipment在在Tbox中檢測中檢測：C D？即檢測 CI DI 是否在Tbox T的所有解釋中成立？2022-4-13史忠植 高級人工智能27C D iff C D是不可滿足的。C T D iff C D關(guān)于T是不可滿足的。C 關(guān)于T是一致的 iff C T A A包含與可滿足性的關(guān)系包含與可滿足性的關(guān)系 DDCC D 2022-4-13史忠植 高級人工智能284 4）實例檢測）實例檢測(Instance

18、checking)(Instance checking)概念的實例：概念的實例：Student (John)，或者表示為 John:Student關(guān)系的實例：關(guān)系的實例：Father(John, Mary)實例檢索：實例檢索：檢索屬于某個概念的所有實例的集合2022-4-13史忠植 高級人工智能295 5）可滿足性檢測算法）可滿足性檢測算法TableauxTableaux算法算法1) 規(guī)則規(guī)則: :S x:C1, x:C2S，若x:C1 C2在S中，且x:C1和x:C2不在S中同時出現(xiàn)。2) 規(guī)則規(guī)則: :S x:D S，若x:C1 C2在S中，x:C1和x:C2都不在S中，且D= C1或者D

19、= C2。3) 規(guī)則規(guī)則: :S xP1y,xPky, y:C S，若x:R.C在S中，R= P1 Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個新變量。4) 規(guī)則規(guī)則: :S y:C S，若x:R.C在S中，xRy在S中成立，且y:C不在S中。 2022-4-13史忠植 高級人工智能30例子：檢測概念的可滿足性：(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 (x, y)規(guī)

20、則Male (y)規(guī)則Male (y)規(guī)則矛盾所以這個概念是不可滿足的。2022-4-13史忠植 高級人工智能316 6）可判定性）可判定性描述邏輯中的可滿足性問題是可判定的。描述邏輯中的可滿足性問題是可判定的。其它推理問題基本上可以歸結(jié)為可滿足性問題。其它推理問題基本上可以歸結(jié)為可滿足性問題。7 7）計算復(fù)雜性）計算復(fù)雜性描述邏輯中的推理問題其計算復(fù)雜性一般是多項描述邏輯中的推理問題其計算復(fù)雜性一般是多項式時間的。但通常由于構(gòu)造的不同，其復(fù)雜性也式時間的。但通常由于構(gòu)造的不同，其復(fù)雜性也有一定的差異。有一定的差異。2022-4-13史忠植 高級人工智能32Semantic Web Archi

21、tecture 2022-4-13史忠植 高級人工智能33我們的工作我們的工作帶缺省的描述邏輯帶缺省的描述邏輯定義定義 一個缺省規(guī)則是形如 這樣的表達式， 其中C、D、E為概念名，x是一個變元。C(x)稱為前提條件，D(x)稱為檢驗條件(缺省)，E(x)稱為缺省的結(jié)論。定義定義1.2 一個知識庫是一個三元組，其中T為Tbox，A為Abox，D為缺省規(guī)則集。)()(: )(xExDxC)()(),(: )(xFlyxOstrichxPenguinxBird2022-4-13史忠植 高級人工智能34動態(tài)描述邏輯動態(tài)描述邏輯 描述邏輯最開始只是用來表示靜態(tài)知識的。為了考慮在時間上的變化，或者在一定動

22、作下的變化，以及保持其語言的相對簡單性，很自然地我們需要通過相應(yīng)的模態(tài)算子來擴展它，以保留其命題模態(tài)狀態(tài)。 提出動態(tài)描述邏輯，用來描述主體中的動態(tài)知識以及推理。描述邏輯動態(tài)邏輯主體主體面向主體的動態(tài)描述邏輯2022-4-13史忠植 高級人工智能35l以客觀世界的形式化建模為研究內(nèi)容，提出一種統(tǒng)以客觀世界的形式化建模為研究內(nèi)容，提出一種統(tǒng)一的形式化框架，同時從靜態(tài)和動態(tài)兩個方面來刻一的形式化框架，同時從靜態(tài)和動態(tài)兩個方面來刻畫世界的模型。為動態(tài)領(lǐng)域的建模提供一種有效的畫世界的模型。為動態(tài)領(lǐng)域的建模提供一種有效的形式化理論工具；形式化理論工具；l將世界中的概念、關(guān)系和個體，公理、事實和動作將世界中

23、的概念、關(guān)系和個體，公理、事實和動作有機地整合在一起，形成統(tǒng)一的關(guān)聯(lián)和運作機制，有機地整合在一起，形成統(tǒng)一的關(guān)聯(lián)和運作機制，使動作與公理和事實相互作用，統(tǒng)一表示并進行推使動作與公理和事實相互作用，統(tǒng)一表示并進行推理；理；l對概念、公式和動作都給出了統(tǒng)一的、合適的語法對概念、公式和動作都給出了統(tǒng)一的、合適的語法和語義；和語義；l主體與本體的結(jié)合主體與本體的結(jié)合 動態(tài)描述邏輯動態(tài)描述邏輯DDL2022-4-13史忠植 高級人工智能36動態(tài)描述邏輯動態(tài)描述邏輯DDLDDL：語義環(huán)境中對服務(wù)過程方面的建模和推理l服務(wù)改變環(huán)境的狀態(tài)：前提條件和執(zhí)行結(jié)果，Actionl服務(wù)描述：基于World Model，e.g., 描述服務(wù)的前提和結(jié)果的詞匯來自World ModellTBox描述World Model的結(jié)構(gòu)l所有狀態(tài)的描述以數(shù)據(jù)庫或文本的形式分散在Web中l(wèi)用戶或Agent通過查詢的方式獲得狀態(tài)的信