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

第二章人工智能邏輯

第二部分史忠植中國科學(xué)院計算技術(shù)研討所高級人工智能描述邏輯

DescriptionLogics主要內(nèi)容◆什么是描畫邏輯？◆為什么用描畫邏輯？◆描畫邏輯的研討進(jìn)展◆描畫邏輯的體系構(gòu)造◆描畫邏輯的構(gòu)造算子◆描畫邏輯的推理問題◆我們的任務(wù)1/8/20243史忠植高級人工智能1什么是描畫邏輯(DL)？ 一種基于對象的知識表示的方式化，也叫概念表示言語或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上 －概念解釋為對象的集合 －關(guān)系解釋為對象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個可斷定的子集具有適宜定義的語義(基于邏輯)1/8/20244史忠植高級人工智能特點◆是以往表示工具的邏輯重構(gòu)和一致方式化 －框架系統(tǒng)(Frame-basedsystems) －語義網(wǎng)絡(luò)(SemanticNetworks) －面向?qū)ο蟊硎?OOrepresentation) －語義數(shù)據(jù)模型(Semanticdatamodels) －類型系統(tǒng)(Typesystems) －特征邏輯(FeatureLogics)◆具有很強的表達(dá)才干◆是可斷定的，總能保證推理算法終止1/8/20245史忠植高級人工智能描畫邏輯的運用◆概念建?！舨樵儍?yōu)化和視圖維護(hù)◆自然言語語義◆智能信息集成◆信息存取和智能接口◆工程的方式化規(guī)范◆術(shù)語學(xué)和本體論◆規(guī)劃◆…1/8/20246史忠植高級人工智能2為什么用描畫邏輯？假設(shè)直接運用一階邏輯，而不附加任何約束，那么：◆知識的構(gòu)造將被破壞，這樣就不能用來驅(qū)動推理◆對獲得可斷定性和有效的推理問題來說，其表達(dá)才干太高，〔也許是太籠統(tǒng)了〕◆對興趣表達(dá)，但依然可斷定的實際，其推理才干太低。DL的重要特征是：◆很強的表達(dá)才干；◆可斷定性，它能保證推理算法總能停頓，并前往正確的結(jié)果。1/8/20247史忠植高級人工智能在眾多知識表示的方式化方法中，描畫邏輯在十多年來遭到人們的特別關(guān)注，主要緣由在于以下三點:◆它們有明晰的模型-實際機制;◆它們很適宜于經(jīng)過概念分類學(xué)來表示運用領(lǐng)域；◆它們提供了很用的推理效力。它們可以被以為是從基于框架的表示方式化向著準(zhǔn)確的語義特征方向開展。此外，描畫邏輯將分類學(xué)中表示和推理〔專業(yè)推理〕與在分類學(xué)中項的事實或?qū)嵗谋硎竞屯评怼矓嘌酝评怼硡^(qū)別開來。1/8/20248史忠植高級人工智能3描畫邏輯的研討進(jìn)展◆描畫邏輯的根底研討 研討描畫邏輯的構(gòu)造算子、表示和推理的根本問題，如可滿足性、包含檢測、一致性、可斷定性等。 普通都在最根本的ALC的根底上在擴展一些構(gòu)造算子，如數(shù)量約束、逆關(guān)系、特征函數(shù)、關(guān)系的復(fù)合等。 TBox和Abox上的推理問題、包含檢測算法等。 Schmidt-Schaub和Smolka首先建立了基于描畫邏輯ALC的Tableau算法，該算法能在多項式時間內(nèi)判別描畫邏輯ALC概念的可滿足性問題。1/8/20249史忠植高級人工智能◆描畫邏輯的擴展研討 A.Artale和E.Franconi(1998)提出了一個知識表示系統(tǒng)，用時間約束的方法將形狀、動作和規(guī)劃的表示一致同來。 為了能讓描畫邏輯處置模態(tài)詞，F(xiàn).Baader將模態(tài)操作引入描畫邏輯，證明了該描畫邏輯公式的可滿足性問題是可斷定的。 Wolter等對具有模態(tài)算子的描畫邏輯進(jìn)展了深化系統(tǒng)的調(diào)查分析，并證明在恒定的領(lǐng)域假設(shè)下多種認(rèn)知和時序描畫邏輯是可斷定的。 另外如時序擴展(Artale,Wolter)、模糊擴展(Straccia)等。1/8/202410史忠植高級人工智能◆描畫邏輯的運用研討描畫邏輯在許多領(lǐng)域中被作為知識表示的工具，如 信息系統(tǒng)〔Catarci,1993〕 數(shù)據(jù)庫〔Borgida,1995;Bergamaschi1992;Sheth,1993〕 軟件工程(Devambu,1991) 網(wǎng)絡(luò)智能訪問〔Levy，1996；Blanco，1994〕 規(guī)劃〔Seida,1992〕等 Horrocks對表達(dá)才干較強的描畫邏輯進(jìn)展了研討，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描畫邏輯、語義網(wǎng)和DAML結(jié)合起來，提出了DAML+OIL，其中以描畫邏輯作為中心的表示和推理根底。并在XML及其RDF上面進(jìn)展了擴展，用描畫邏輯來研討語義網(wǎng)絡(luò)和本體論。1/8/202411史忠植高級人工智能4描畫邏輯的體系構(gòu)造一個描畫邏輯系統(tǒng)包含四個根本組成部分：1〕表示概念和關(guān)系〔Role〕的構(gòu)造集2〕Tbox——關(guān)于概念術(shù)語的斷言3〕Abox——關(guān)于個體的斷言4〕Tbox和Abox上的推理機制。1/8/202412史忠植高級人工智能◆概念——解釋為一個領(lǐng)域的子集例子：一切在校學(xué)習(xí)的人員的集合構(gòu)成“學(xué)生〞概念 又如：孩子，已婚的，哺乳動物等概念{x|Student(x)}，{x|Married(x)}◆關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}1〕DL的根本元素——概念和關(guān)系1/8/202413史忠植高級人工智能知識庫TBox(方式)Man?Human?MaleHappy-father?Human??Has-child.Female?…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口1/8/202414史忠植高級人工智能2〕TBox言語 是描畫領(lǐng)域構(gòu)造的公理的集合定義:引入概念的稱號A?C,A?CFather?Man??has-child.HumanHuman?Animal?Biped包含：聲明包含關(guān)系的公理C?D(C?DC?D，D?C)?has-degree.Masters??has-degree.Bachelors一個解釋I滿足：C?DiffCI=DI C?DiffCI?DI一個解釋I滿足TBoxTiff它滿足T中的每個公理(I?T)1/8/202415史忠植高級人工智能◆概念——表示實體(一元謂詞，類)例子：學(xué)生，已婚的{x|Student(x)}，{x|Married(x)} Bird?Animal,Man?Human◆關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人{(lán)<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox實例1/8/202416史忠植高級人工智能◆概念斷言——表示一個對象能否屬于某個概念 a:C例如：Tom是個學(xué)生，表示為 Tom:Student 或者 Student(Tom) John:Man??has-child.Female◆關(guān)系斷言——表示兩個對象能否滿足一定的關(guān)系 <a,b>:R例如：John有個孩子叫Mary <John,Mary>:has-child3〕ABox言語〔斷言部分〕 是描畫詳細(xì)情形的公理的集合1/8/202417史忠植高級人工智能一個解釋I滿足：a:CiffaI∈CI<a,b>:Riff<aI,bI>∈RI一個解釋I滿足ABoxAiff它滿足A中的每個公理記為：I?A一個解釋I滿足知識庫=<T,A>iff它滿足T和A記為：I?1/8/202418史忠植高級人工智能4〕語法和語義構(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非?C△I\C?Male存在量詞?

R.C{x|?y.<x,y>∈

RI∧y∈CI}?

has-child.Male全稱量詞?R.C{x|?y.<x,y>∈

RI

y∈CI}?

has-child.Doctor1/8/202419史忠植高級人工智能普通地，描畫邏輯根據(jù)提供的構(gòu)造算子，在簡單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： ◆合取(?)，汲取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最根本的DL稱之為ALC例如，ALC中概念Happy-father定義為： Man??has-child.Male ??has-child.Female ??has-child.(Doctor?Lawyer)5DL中的構(gòu)造算子1/8/202420史忠植高級人工智能構(gòu)造算子語法語義例子數(shù)量約束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≤n}≤3

has-child.Male逆R-{<y,x>|<x,y>∈

RI}has-child-傳遞閉包R*(RI)*has-child*DL中的其它算子topT△IMale?

?MaleBottom

Man?

?Man另外，有兩個類似于FOL中的選集(true)和空集(false)的算子1/8/202421史忠植高級人工智能在DL中添加算子普通地，在描畫邏輯中添加不同的算子，那么得到不同表達(dá)才干的描畫邏輯，其復(fù)雜性問題也不盡一樣。例如，在ALC的根底上添加逆(-)算子，那么構(gòu)成ALCI假設(shè)再加上數(shù)量約束算子(≥n,≤n)，那么構(gòu)成ALCIQ。假設(shè)在描畫邏輯中添加時序算子，那么構(gòu)成為時序描畫邏輯(TemporalDescriptionLogic)，例如，可以添加： Until算子U：CUD Since算子S：CSD還可以參與其它算子，如模態(tài)算子□，

，○等。1/8/202422史忠植高級人工智能6描畫邏輯中的推理1)一致性〔協(xié)調(diào)性consistency〕2)可滿足性(satisfiability)3)包含檢測〔subsumption〕4)實例檢測(instancechecking)5)Tableaux算法6〕可斷定性7〕計算復(fù)雜性1/8/202423史忠植高級人工智能1)一致性檢測(Consistency)◆知識庫<T,A>是協(xié)調(diào)的嗎？ 即檢測能否有<T,A>的模型(解釋)I？◆C關(guān)于TboxT是協(xié)調(diào)的嗎？ 即檢測能否有T的模型I使得C≠？1/8/202424史忠植高級人工智能2)概念可滿足性(Satisfiablity)對一個概念C，假設(shè)存在一個解釋I使得CI是非空的，那么稱概念C是可滿足的，否那么是不可滿足的。檢驗一個概念的可滿足性，實踐上就是看能否有解釋使得這個概念成立。例如：概念Male?Female，即需求檢測能否有性別既是男的又是女的這樣的人。假設(shè)確實是沒有這種兩性人，那么我們斷言，這個概念是不可滿足的。又如概念：student?worker，它是可滿足的。即代表那些在職學(xué)生的集合。定理：概念C是可滿足的，當(dāng)且僅當(dāng)C不包含于。1/8/202425史忠植高級人工智能◆在知識庫中檢測： C?D？ 即檢測CI?DI能否在一切的解釋中成立？3)概念包含(Subsumption)例如： bird?animal computer?equipment◆在Tbox中檢測： C?D？ 即檢測CI?DI能否在TboxT的一切解釋中成立？1/8/202426史忠植高級人工智能C?DiffC??D是不可滿足的。C?TDiffC??D關(guān)于T是不可滿足的。C關(guān)于T是一致的iffC?TA??A包含與可滿足性的關(guān)系?DDCC??D＝1/8/202427史忠植高級人工智能4〕實例檢測(Instancechecking)概念的實例： Student(John)，或者表示為John:Student關(guān)系的實例： Father(John,Mary) 實例檢索：檢索屬于某個概念的一切實例的集合1/8/202428史忠植高級人工智能5〕可滿足性檢測算法——Tableaux算法1)?規(guī)那么:S→?{x:C1,x:C2}?S，假設(shè)x:C1?C2在S中，且x:C1和x:C2不在S中同時出現(xiàn)。2)?規(guī)那么:S→?{x:D}?S，假設(shè)x:C1?C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)?規(guī)那么:S→?{xP1y,…,xPky,y:C}?S，假設(shè)x:?R.C在S中，R=P1?…?Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個新變量。4)?規(guī)那么:S→?{y:C}?S，假設(shè)x:?R.C在S中，xRy在S中成立，且y:C不在S中。1/8/202429史忠植高級人工智能例子：檢測概念的可滿足性：(?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ī)那么?Male(y) ?規(guī)那么Male(y) ?規(guī)那么 矛盾所以這個概念是不可滿足的。1/8/202430史忠植高級人工智能6〕可斷定性描畫邏輯中的可滿足性問題是可斷定的。其它推理問題根本上可以歸結(jié)為可滿足性問題。7〕計算復(fù)雜性描畫邏輯中的推理問題其計算復(fù)雜性普通是多項式時間的。但通常由于構(gòu)造的不同，其復(fù)雜性也有一定的差別。1/8/202431史忠植高級人工智能SemanticWebArchitecture1/8/202432史忠植高級人工智能我們的任務(wù)◆帶缺省的描畫邏輯定義一個缺省規(guī)那么是形如這樣的表達(dá)式，其中C、D、E為概念名，x是一個變元。C(x)稱為前提條件，D(x)稱為檢驗條件(缺省)，E(x)稱為缺省的結(jié)論。定義1.2一個知識庫是一個三元組<T,A,D>，其中T為Tbox，A為Abox，D為缺省規(guī)那么集。1/8/202433史忠植高級人工智能◆動態(tài)描畫邏輯描畫邏輯最開場只是用來表示靜態(tài)知識的。為了思索在時間上的變化，或者在一定動作下的變化，以及堅持其言語的相對簡單性，很自然地我們需求經(jīng)過相應(yīng)的模態(tài)算子來擴展它，以保管其命題模態(tài)形狀。提出動態(tài)描畫邏輯，用來描畫主體中的動態(tài)知識以及推理。描畫邏輯動態(tài)邏輯＋主體面向主體的動態(tài)描畫邏輯1/8/202434史忠植高級人工智能以客觀世界的方式化建模為研討內(nèi)容，提出一種一致的方式化框架，同時從靜態(tài)和動態(tài)兩個方面來描寫世界的模型。為動態(tài)領(lǐng)域的建模提供一種有效的方式化實際工具；將世界中的概念、關(guān)系和個體，公理、現(xiàn)實和動作有機地整合在一同，構(gòu)成一致的關(guān)聯(lián)和運作機制，使動作與公理和現(xiàn)實相互作用，一致表示并進(jìn)展推理；對概念、公式和動作都給出了一致的、適宜的語法和語義；主體與本體的結(jié)合動態(tài)描畫邏輯DDL1/8/202435史忠植高級人工智能動態(tài)描畫邏輯DDLDDL：語義環(huán)境中對效力過程方面的建模和推理效力改動環(huán)境的形狀：前提條件和執(zhí)行結(jié)果，Action效力描畫：基于WorldModel，e.g.,描畫效力的前提和結(jié)果的詞匯來自WorldModel