第二章人工智能邏輯

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

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

△Ihas-child對(duì)概念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í)人工智能普通地，描畫(huà)邏輯根據(jù)提供的構(gòu)造算子，在簡(jiǎn)單的概念和關(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史忠植高級(jí)人工智能構(gòu)造算子語(yǔ)法語(yǔ)義例子數(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另外，有兩個(gè)類(lèi)似于FOL中的選集(true)和空集(false)的算子1/8/202421史忠植高級(jí)人工智能在DL中添加算子普通地，在描畫(huà)邏輯中添加不同的算子，那么得到不同表達(dá)才干的描畫(huà)邏輯，其復(fù)雜性問(wèn)題也不盡一樣。例如，在ALC的根底上添加逆(-)算子，那么構(gòu)成ALCI假設(shè)再加上數(shù)量約束算子(≥n,≤n)，那么構(gòu)成ALCIQ。假設(shè)在描畫(huà)邏輯中添加時(shí)序算子，那么構(gòu)成為時(shí)序描畫(huà)邏輯(TemporalDescriptionLogic)，例如，可以添加： Until算子U：CUD Since算子S：CSD還可以參與其它算子，如模態(tài)算子□，

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