人工智能邏輯描述邏輯

人工智能邏輯描述邏輯第1頁，課件共35頁，創(chuàng)作于2023年2月第二章人工智能邏輯2.1邏輯-----重要的形式工具2.2非單調邏輯2.3默認邏輯2.4限定邏輯2.5自認知邏輯2.6真值維護系統(tǒng)2.7情景演算的邏輯基礎2.8動態(tài)描述邏輯第2頁，課件共35頁，創(chuàng)作于2023年2月主要內容◆

什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的研究進展◆描述邏輯的體系結構◆描述邏輯的構造算子◆描述邏輯的推理問題◆我們的工作第3頁，課件共35頁，創(chuàng)作于2023年2月8.1什么是描述邏輯(DL)？一種基于對象的知識表示的形式化，也叫概念表示語言或術語邏輯。建立在概念和關系(Role)之上－概念解釋為對象的集合－關系解釋為對象之間的二元關系

源于語義網(wǎng)絡和KL-ONE是一階邏輯FOL的一個可判定的子集具有合適定義的語義(基于邏輯)第4頁，課件共35頁，創(chuàng)作于2023年2月特點◆是以往表示工具的邏輯重構和統(tǒng)一形式化

－框架系統(tǒng)(Frame-basedsystems) －語義網(wǎng)絡(SemanticNetworks) －面向對象表示(OOrepresentation) －語義數(shù)據(jù)模型(Semanticdatamodels) －類型系統(tǒng)(Typesystems) －特征邏輯(FeatureLogics)◆

具有很強的表達能力◆是可判定的，總能保證推理算法終止第5頁，課件共35頁，創(chuàng)作于2023年2月描述邏輯的應用

◆概念建?！舨樵儍?yōu)化和視圖維護◆自然語言語義◆智能信息集成◆信息存取和智能接口◆工程的形式化規(guī)范◆術語學和本體論◆規(guī)劃◆…第6頁，課件共35頁，創(chuàng)作于2023年2月8.2為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，則：◆知識的結構將被破壞，這樣就不能用來驅動推理◆對獲得可判定性和有效的推理問題來說，其表達能力太高，（也許是太抽象了）◆對興趣表達，但仍然可判定的理論，其推理能力太低。DL的重要特征是：◆很強的表達能力；◆可判定性，它能保證推理算法總能停止，并返回正確的結果。第7頁，課件共35頁，創(chuàng)作于2023年2月在眾多知識表示的形式化方法中，描述邏輯在十多年來受到人們的特別關注，主要原因在于以下三點:◆它們有清晰的模型-理論機制;◆它們很適合于通過概念分類學來表示應用領域；◆它們提供了很用的推理服務。它們可以被認為是從基于框架的表示形式化向著精確的語義特征方向發(fā)展。此外，描述邏輯將分類學中表示和推理（專業(yè)推理）與在分類學中項的事實或實例的表示和推理（斷言推理）區(qū)別開來。第8頁，課件共35頁，創(chuàng)作于2023年2月3描述邏輯的研究進展◆描述邏輯的基礎研究研究描述邏輯的構造算子、表示和推理的基本問題，如可滿足性、包含檢測、一致性、可判定性等。 一般都在最基本的ALC的基礎上在擴展一些構造算子，如數(shù)量約束、逆關系、特征函數(shù)、關系的復合等。TBox和Abox上的推理問題、包含檢測算法等。Schmidt-Schaub和Smolka首先建立了基于描述邏ALC的Tableau算法，該算法能在多項式時間內判斷描述邏輯ALC概念的可滿足性問題。第9頁，課件共35頁，創(chuàng)作于2023年2月◆描述邏輯的擴展研究

A.Artale和E.Franconi(1998)提出了一個知識表示系統(tǒng)，用時間約束的方法將狀態(tài)、動作和規(guī)劃的表示統(tǒng)一起來。為了能讓描述邏輯處理模態(tài)詞，F(xiàn).Baader將模態(tài)操作引入描述邏輯，證明了該描述邏輯公式的可滿足性問題是可判定的。

Wolter等對具有模態(tài)算子的描述邏輯進行了深入系統(tǒng)的調查分析，并證明在恒定的領域假設下多種認知和時序描述邏輯是可判定的。另外如時序擴展(Artale,Wolter)、模糊擴展(Straccia)等。第10頁，課件共35頁，創(chuàng)作于2023年2月◆描述邏輯的應用研究描述邏輯在許多領域中被作為知識表示的工具，如信息系統(tǒng)（Catarci,1993）數(shù)據(jù)庫（Borgida,1995;Bergamaschi1992;Sheth,1993）軟件工程(Devambu,1991)網(wǎng)絡智能訪問（Levy，1996；Blanco，1994）規(guī)劃（Seida,1992）等

Horrocks對表達能力較強的描述邏輯進行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語義網(wǎng)和DAML結合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎。并在XML及其RDF上面進行了擴展，用描述邏輯來研究語義網(wǎng)絡和本體論。第11頁，課件共35頁，創(chuàng)作于2023年2月4描述邏輯的體系結構一個描述邏輯系統(tǒng)包含四個基本組成部分：1）表示概念和關系（Role）的構造集2）Tbox——關于概念術語的斷言3）Abox——關于個體的斷言4）Tbox和Abox上的推理機制。第12頁，課件共35頁，創(chuàng)作于2023年2月1）DL的基本元素——概念和關系◆概念——解釋為一個領域的子集例子：所有在校學習的人員的集合構成“學生”概念 又如：孩子，已婚的，哺乳動物等概念{x|Student(x)}，{x|Married(x)}◆

關系(Roles)——屬性(二元謂詞，關系)例子：朋友，愛人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}第13頁，課件共35頁，創(chuàng)作于2023年2月知識庫TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口第14頁，課件共35頁，創(chuàng)作于2023年2月2）TBox語言是描述領域結構的公理的集合定義:引入概念的名稱A?

C,A

?

CFather?

Man?

?

has-child.HumanHuman?

Animal?

Biped包含：聲明包含關系的公理C

?

D

(C?

D

C

?

D，D

?

C)?

has-degree.Masters?

?

has-degree.Bachelors一個解釋I滿足：

C?

D

iffCI

=DI C?

D

iffCI

?

DI一個解釋I滿足TBoxT

iff它滿足T中的每個公理(I?T)第15頁，課件共35頁，創(chuàng)作于2023年2月◆概念——表示實體(一元謂詞，類)例子：學生，已婚的{x|Student(x)}，{x|Married(x)}Bird◆

關系(Roles)——屬性(二元謂詞，關系)例子：朋友，愛人{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox實例第16頁，課件共35頁，創(chuàng)作于2023年2月◆概念斷言——表示一個對象是否屬于某個概念

a:C例如：Tom是個學生，表示為

Tom:Student 或者 Student(Tom)

John:Man??has-child.Female◆

關系斷言——表示兩個對象是否滿足一定的關系 <a,b>:R例如：John有個孩子叫Mary

<John,

Mary>

:has-child3）ABox語言--斷言部分-是描述具體情形的公理的集合第17頁，課件共35頁，創(chuàng)作于2023年2月一個解釋I滿足：a:CiffaI∈CI<a,b>:Riff<aI,bI>∈RI一個解釋I滿足ABoxAiff它滿足A中的每個公理記為：I?

A一個解釋I滿足知識庫=<T,A>

iff它滿足T和A記為：I?

第18頁，課件共35頁，創(chuàng)作于2023年2月4）語法和語義構造算子語法語義例子原子概念AAI?△IHuman原子關系RRI?△I△Ihas-child對概念C,D和關系(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.Doctor第19頁，課件共35頁，創(chuàng)作于2023年2月5DL中的構造算子

一般地，描述邏輯依據(jù)提供的構造算子，在簡單的概念和關系上構造出復雜的概念和關系。

通常DL至少包含以下算子： ◆合取(?)，析取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為：

Man??has-child.Male

??has-child.Female

??has-child.(Doctor?Lawyer)第20頁，課件共35頁，創(chuàng)作于2023年2月構造算子語法語義例子數(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?

?MaleBottomMan?

?Man另外，有兩個類似于FOL中的全集(true)和空集(false)的算子第21頁，課件共35頁，創(chuàng)作于2023年2月在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達能力的描述邏輯，其復雜性問題也不盡相同。例如，在ALC的基礎上添加逆(-)算子，則構成ALCI若再加上數(shù)量約束算子(≥n,≤n)，則構成ALCIQ。若在描述邏輯中添加時序算子，則構成為時序描述邏輯(TemporalDescriptionLogic)，例如，可以添加：

Until算子U：CUD Since算子S：CSD還可以加入其它算子，如模態(tài)算子□，

，○等。第22頁，課件共35頁，創(chuàng)作于2023年2月6描述邏輯中的推理1)

一致性（協(xié)調性consistency）2)可滿足性(satisfiability)3)包含檢測（subsumption）4)實例檢測(instancechecking)5)Tableaux算法6)可判定性7)計算復雜性第23頁，課件共35頁，創(chuàng)作于2023年2月1)一致性檢測(Consistency)◆知識庫<T,A>是協(xié)調的嗎？ 即檢測是否有<T,A>的模型(解釋)I？◆C關于TboxT是協(xié)調的嗎？

即檢測是否有T的模型I使得C≠？第24頁，課件共35頁，創(chuàng)作于2023年2月2)概念可滿足性(Satisfiablity)

對一個概念C，如果存在一個解釋I使得CI是非空的，則稱概念C是可滿足的，否則是不可滿足的。檢驗一個概念的可滿足性，實際上就是看是否有解釋使得這個概念成立。例如：概念Male?Female，即需要檢測是否有性別既是男的又是女的這樣的人。若確實是沒有這種兩性人，則我們斷言，這個概念是不可滿足的。又如概念：student?worker，它是可滿足的。即代表那些在職學生的集合。定理：概念C是可滿足的，當且僅當C不包含于。

第25頁，課件共35頁，創(chuàng)作于2023年2月◆在知識庫中檢測：

C?D？

即檢測CI?DI是否在所有的解釋中成立？3)概念包含(Subsumption)例如：

bird?animal computer?equipment◆在Tbox中檢測：

C?D？

即檢測CI?DI是否在TboxT的所有解釋中成立？第26頁，課件共35頁，創(chuàng)作于2023年2月C?

Diff

C?

?D是不可滿足的。C?T

Diff

C?

?D關于T是不可滿足的。C關于T是一致的

iffC?T

A?

?A包含與可滿足性的關系?

DDCC?

?D＝

第27頁，課件共35頁，創(chuàng)作于2023年2月4）實例檢測(Instancechecking)概念的實例：Student(John)，或者表示為John:Student關系的實例：Father(John,Mary) 實例檢索：檢索屬于某個概念的所有實例的集合。第28頁，課件共35頁，創(chuàng)作于2023年2月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中。第29頁，課件共35頁，創(chuàng)作于2023年2月例子：檢測概念的可滿足性：(?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ī)則

矛盾所以這個概念是不可滿足的。第30頁，課件共35頁，創(chuàng)作于2023年2月6）可判定性描述邏輯中的可滿