第二章人工智能邏輯描述邏輯ppt

其次章人工智能邏輯2.1邏輯-----重要的形式工具2.2非單調(diào)邏輯2.3默認(rèn)邏輯2.4限定邏輯2.5自認(rèn)知邏輯2.6真值維護(hù)系統(tǒng)2.7情景演算的邏輯基礎(chǔ)2.8動態(tài)描述邏輯3/2/20231史忠植高級人工智能描述邏輯

DescriptionLogics3/2/20232史忠植高級人工智能主要內(nèi)容◆什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的探討進(jìn)展◆描述邏輯的體系結(jié)構(gòu)◆描述邏輯的構(gòu)造算子◆描述邏輯的推理問題◆我們的工作3/2/20233史忠植高級人工智能1什么是描述邏輯(DL)？ 一種基于對象的學(xué)問表示的形式化，也叫概念表示語言或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上 －概念說明為對象的集合 －關(guān)系說明為對象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個可判定的子集具有合適定義的語義(基于邏輯)3/2/20234史忠植高級人工智能特點◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化 －框架系統(tǒng)(Frame-basedsystems) －語義網(wǎng)絡(luò)(SemanticNetworks) －面對對象表示(OOrepresentation) －語義數(shù)據(jù)模型(Semanticdatamodels) －類型系統(tǒng)(Typesystems) －特征邏輯(FeatureLogics)◆具有很強(qiáng)的表達(dá)實力◆是可判定的，總能保證推理算法終止3/2/20235史忠植高級人工智能描述邏輯的應(yīng)用

◆概念建模◆查詢優(yōu)化和視圖維護(hù)◆自然語言語義◆智能信息集成◆信息存取和智能接口◆工程的形式化規(guī)范◆術(shù)語學(xué)和本體論◆規(guī)劃◆…3/2/20236史忠植高級人工智能2為什么用描述邏輯？若干脆運(yùn)用一階邏輯，而不附加任何約束，則：◆學(xué)問的結(jié)構(gòu)將被破壞，這樣就不能用來驅(qū)動推理◆對獲得可判定性和有效的推理問題來說，其表達(dá)實力太高，（或許是太抽象了）◆對愛好表達(dá)，但仍舊可判定的理論，其推理實力太低。DL的重要特征是：◆很強(qiáng)的表達(dá)實力；◆可判定性，它能保證推理算法總能停止，并返回正確的結(jié)果。3/2/20237史忠植高級人工智能在眾多學(xué)問表示的形式化方法中，描述邏輯在十多年來受到人們的特殊關(guān)注，主要緣由在于以下三點:◆它們有清晰的模型-理論機(jī)制;◆它們很適合于通過概念分類學(xué)來表示應(yīng)用領(lǐng)域；◆它們供應(yīng)了很用的推理服務(wù)。它們可以被認(rèn)為是從基于框架的表示形式化向著精確的語義特征方向發(fā)展。此外，描述邏輯將分類學(xué)中表示和推理（專業(yè)推理）與在分類學(xué)中項的事實或?qū)嵗谋硎竞屯评恚〝嘌酝评恚﹨^(qū)分開來。3/2/20238史忠植高級人工智能3描述邏輯的探討進(jìn)展◆描述邏輯的基礎(chǔ)探討 探討描述邏輯的構(gòu)造算子、表示和推理的基本問題，如可滿足性、包含檢測、一樣性、可判定性等。 一般都在最基本的ALC的基礎(chǔ)上在擴(kuò)展一些構(gòu)造算子，如數(shù)量約束、逆關(guān)系、特征函數(shù)、關(guān)系的復(fù)合等。 TBox和Abox上的推理問題、包含檢測算法等。 Schmidt-Schaub和Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項式時間內(nèi)推斷描述邏輯ALC概念的可滿足性問題。3/2/20239史忠植高級人工智能◆描述邏輯的擴(kuò)展探討 A.Artale和E.Franconi(1998)提出了一個學(xué)問表示系統(tǒng)，用時間約束的方法將狀態(tài)、動作和規(guī)劃的表示統(tǒng)一起來。 為了能讓描述邏輯處理模態(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)等。3/2/202310史忠植高級人工智能◆描述邏輯的應(yīng)用探討描述邏輯在很多領(lǐng)域中被作為學(xué)問表示的工具，如 信息系統(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á)實力較強(qiáng)的描述邏輯進(jìn)行了探討，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語義網(wǎng)和DAML結(jié)合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎(chǔ)。并在XML及其RDF上面進(jìn)行了擴(kuò)展，用描述邏輯來探討語義網(wǎng)絡(luò)和本體論。3/2/202311史忠植高級人工智能4描述邏輯的體系結(jié)構(gòu)一個描述邏輯系統(tǒng)包含四個基本組成部分：1）表示概念和關(guān)系（Role）的構(gòu)造集2）Tbox——關(guān)于概念術(shù)語的斷言3）Abox——關(guān)于個體的斷言4）Tbox和Abox上的推理機(jī)制。

3/2/202312史忠植高級人工智能◆概念——說明為一個領(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)系3/2/202313史忠植高級人工智能知識庫TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口3/2/202314史忠植高級人工智能2）TBox語言 是描述領(lǐng)域結(jié)構(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)3/2/202315史忠植高級人工智能◆概念——表示實體(一元謂詞，類)例子：學(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實例3/2/202316史忠植高級人工智能◆概念斷言——表示一個對象是否屬于某個概念 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語言（斷言部分） 是描述具體情形的公理的集合3/2/202317史忠植高級人工智能一個說明I滿足：a:CiffaI∈CI<a,b>:Riff<aI,bI>∈RI一個說明I滿足ABoxAiff它滿足A中的每個公理記為：I?A一個說明I滿足學(xué)問庫=<T,A>iff它滿足T和A記為：I?3/2/202318史忠植高級人工智能4）語法和語義3/2/202319史忠植高級人工智能一般地，描述邏輯依據(jù)供應(yīng)的構(gòu)造算子，在簡潔的概念和關(guān)系上構(gòu)造出困難的概念和關(guān)系。通常DL至少包含以下算子： ◆合取(?)，吸取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為： Man??has-child.Male ??has-child.Female ??has-child.(Doctor?Lawyer)5DL中的構(gòu)造算子3/2/202320史忠植高級人工智能DL中的其它算子另外，有兩個類似于FOL中的全集(true)和空集(false)的算子3/2/202321史忠植高級人工智能在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達(dá)實力的描述邏輯，其困難性問題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆(-)算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(≥n,≤n)，則構(gòu)成ALCIQ。若在描述邏輯中添加時序算子，則構(gòu)成為時序描述邏輯(TemporalDescriptionLogic)，例如，可以添加： Until算子U：CUD Since算子S：CSD還可以加入其它算子，如模態(tài)算子□，

，○等。3/2/202322史忠植高級人工智能6描述邏輯中的推理1)一樣性（協(xié)調(diào)性consistency）2)可滿足性(satisfiability)3)包含檢測（subsumption）4)實例檢測(instancechecking)5)Tableaux算法6）可判定性7）計算困難性3/2/202323史忠植高級人工智能1)一樣性檢測(Consistency)◆學(xué)問庫<T,A>是協(xié)調(diào)的嗎？ 即檢測是否有<T,A>的模型(說明)I？◆C關(guān)于TboxT是協(xié)調(diào)的嗎？

即檢測是否有T的模型I使得C

≠

？3/2/202324史忠植高級人工智能2)概念可滿足性(Satisfiablity)對一個概念C，假如存在一個說明I使得CI是非空的，則稱概念C是可滿足的，否則是不行滿足的。檢驗一個概念的可滿足性，事實上就是看是否有說明使得這個概念成立。例如：概念Male?Female，即須要檢測是否有性別既是男的又是女的這樣的人。若的確是沒有這種兩性人，則我們斷言，這個概念是不行滿足的。又如概念：student?worker，它是可滿足的。即代表那些在職學(xué)生的集合。定理：概念C是可滿足的，當(dāng)且僅當(dāng)C不包含于。3/2/202325史忠植高級人工智能◆在學(xué)問庫中檢測： C?D？ 即檢測CI?DI是否在全部的說明中成立？3)概念包含(Subsumption)例如： bird?animal computer?equipment◆在Tbox中檢測： C?D？ 即檢測CI?DI是否在TboxT的全部說明中成立？3/2/202326史忠植高級人工智能C?DiffC??D是不行滿足的。C?TDiffC??D關(guān)于T是不行滿足的。C關(guān)于T是一樣的iffC?TA??A包含與可滿足性的關(guān)系?DDCC?

?D＝

3/2/202327史忠植高級人工智能4）實例檢測(Instancechecking)概念的實例： Student(John)，或者表示為John:Student關(guān)系的實例： Father(John,Mary) 實例檢索：檢索屬于某個概念的全部實例的集合3/2/202328史忠植高級人工智能5）可滿足性檢測算法——Tableaux算法1)

?規(guī)則:S→?{

x:C1,x:C2}?S，若x:C1?

C2在S中，且x:C1和x:C2不在S中同時出現(xiàn)。2)?規(guī)則:S→?

{x:D}?S，若x:C1?C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)?規(guī)則:S→?

{xP1y,…,xPky,y:C}?S，若x:?R.C在S中，R=P1?…?Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個新變量。4)?規(guī)則:S→?{y:C}?S，若x:?R.C在S中，xRy在S中成立，且y:C不在S中。

3/2/202329史忠植高級人工智能例子：檢測概念的可滿足性：(?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ī)則 沖突所以這個概念是不行滿足的。3/2/202330史忠植高級人工智能6）可判定性描述邏輯中的可滿足性問題是可判定的。其它推理問題基本上可以歸結(jié)為可滿足性問題。7）計算困難性描述邏輯中的推理問題其計算困難性一般是多項式時間的。但通常由于構(gòu)造的不同，其困難性也有確定的差異。3/2/202331史忠植高級人工智能我們的工作◆帶缺省的描述邏輯定義一個缺省規(guī)則是形如這樣的表達(dá)式，其中C、D、E為概念名，x是一