笔记 OPENHPI 语义网技术 Week4

公开课请见:https://openhpi.de/

L4-1 知识表达——作为哲学中中心概念的本体

“如果不讲一门共同的语言,人们将无法分享知识” Thomas Davenport
讲一门共同的语言意味着:
  • 通用的符号和概念(语法Syntax)
  • 对于符号和概念含义的协定(语义Semantics)
  • 概念的分类(分类学Taxonomy)
  • 概念之间的关联和关系(叙词表Thesauri)
  • 有关关系的建立和理解关系的规则和知识(本体Ontologies)
为了表达知识,我们需要一个正式知识表达途径,即本体
据Christiano Wolfio的书philosophia prima
wiki百科本体定义“philosophical study of the nature of being, existence, or reality, as well as the basic categories of being and their relations ”

本体的基本问题:

  • 一个事物存在意味着什么?
  • 事物属于什么类型?

一些相关资料:

  • 巴门尼德(Parmenides)“存在的事物的基本类型有哪些?”
  • 柏拉图和苏格拉底认为idea是不变不灭的,而object是可变可灭的
  • 亚里士多德 建立了一个对事物的陈述进行分类的系统;提出了三段论(Syllogisms)
  • 亚里士多德的分类系统的可视化(树图)
  • 奥卡姆的剃刀 Entia non sunt multiplicanda sine necessitate.若无必要 勿增实体
  • Ramon Lull的树图
  • John Wilkins试图创建一个全球通用的哲学语言
  • 莱布尼茨发展了一个用characteristic numbers作为亚里士多德逻辑的模型,尝试通过计算的方式解决逻辑问题
  • Immanuel Kant的认识论“类型是理解的纯概念???”Categories are pure concepts of understanding

L4-2  知识表达——计算机科学中的本体

Thomas R. Gruber: A Translation Approach to Portable Ontology Specifications.Knowledge Acquisition, 5(2):199-220, 1993.
"An ontology is an explicit, formal specification of a shared conceptualization . The term is borrowed from philosophy, where an Ontology is a systematic account of Existence. For AI systems, what ‘exists’ is that which can be represented.“
本体是对于一个共享概念的明确且正式的的规定。本体这个术语是从哲学中借过来的,在哲学中本体是对于存在的系统化的陈述。对于人工智能系统而言,只有能被表达的东西才可以是“存在”的。
  • 概念化:抽象模型(领域、标识的相关概念、关系)
  • 明确:所有概念的意义必须被定义
  • 正式:机器可读
  • 共享:本体的共识

我们如何表达本体?

本体——组成和模型
类、关系和实例(Classes, Relations and Instances)
  • Class(类) 类代表了概念,类通过属性来描述,属性是名称/值对
  • Relation(关系) 类与其他类相关,关系是特殊的属性,其值为其他类的对象
  • Constraint (限定)  可以限定关系或属性所允许的值
  • 可以通过类、关系、规则来组成语句/推断
  • Axiom(公理)描述了不能够通过其他已经存在了的组成而表示的知识
  • Instance(实例)描述了一个本体中的个体

L4-3 知识表达——如何定义一个本体的正式模型?

  1. 命题逻辑Propositional Logic
    在命题逻辑中,世界由事实(facts)构成,不含其它任何东西
  2. 一阶逻辑First Order Logic
    在一阶逻辑中特别适合本体的描述,但是种种缺点
  3. 描述逻辑Description Logics
    描述逻辑是一系列知识表达语言的集合,大多数描述逻辑都是一阶逻辑的子集,但是与一阶逻辑不同的是,绝大多数描述逻辑都是可决定的,因此可以进行逻辑推断。
  • TBox术语知识(terminological knowledge)有关一个领域内概念的知识(类、属性、关系)
  • ABox断言知识(assertional knowledge)有关实例和实体的知识
描述逻辑中
  • Concepts(概念)代表了实体和类
  • Roles(角色)代表了性质或关系
  • Individuals(个体)实体个体,概念断言、常数
  • Operators(运算符)用于构建有关概念或角色的复杂表达
主要的运算符
  • 联合Conjunction (),
  • 分离、析取Disjunction ( ),
  • 否定 Negation ( )
  • 定量限制 restricted form of Quantification (,)
 ALC Attributive Language with Complement 带补充的定语语言?用来表达基本的描述逻辑
1原子类型(Atomic Type)包括:
  • 概念名称 concept names A, B, ...
  • 特殊概念 special concepts   - Top (通用概念 universal concept)  - Bottom concept 底层概念
  • 规则名称 role names R,S, ...
2构造符(Constructors)
  • Negation: ¬C
  • Conjunction: C  D
  • Disjunction: C  D
  • Existential Quantifier:  R.C
  • Universal Quantifier:  R.C
3类关系:
  • Inclusion C ⊑ D • E.g., Man ⊑ Human
  • Equality C ≣ D • E.g., Frau ≣ Woman
4 类构造符
 
Seminarist ≡ Person 
(participatesAt.Seminar ⊔ manages.Seminar)
 
5 术语知识: 通过公理描述了所表达的领域的结构
6 断言知识: 通过公里描述了特定的情况(数据)
 
描述逻辑
description logics
 
描述逻辑的语义:语义(Semantic)是通过演绎(Interpretation)得出的。
 
演绎功能:

interpretation
我们如何表达本体?
本体可以通过数据库或软件建模技术(如UML)来构建。

L4-4 知识表达——本体类型

ontologies type

(according to Guarino,1998)
  1. 基础本体、高层本体
    表达了非常通用的概念,是跨领域的本体(如:时间、空间、概念、一个特定领域或问题的中的特定事件)
  2. 领域本体
    有关一个特定本体的基础性概念
  3. 任务本体
    有关一个一般的活动或任务的基础性概念
  4. 应用本体
    有关一个特定的活动或任务的基础性概念
不同种类的本体的比较
categories of ontology
according to Lassila/McGuinnes, 2001

L4-5 知识表达——逻辑基础

逻辑的定义:研究如何能够形式化地作出正确的推断。
  • 语法:不带意义的符号——定义了规则,如何构造形式正确的符号序列。
  • 语义:语法的意义——定义了如何通过原子符号的意义得出复杂的符号序列的意义
语义变体(Variants of Semantics)?
模型理论语义(Model theoretic semantics)performs the semantic interpretation of artificial and natural languages byidentifying meaning with an exact and formally defined interpretation with a model
通过“采用一个被明确、正式定义了的演绎模型来识别含义”的方式对人工或自然语言进行语义的解释。
 
逻辑的工作原理:
任何逻辑 L := ( S ,  )都包含
  • 一系列陈述 S
  • 以及一个蕴含关系
Propositional Logic命题逻辑的逻辑连接符
pl
优先顺序:¬ 优先于 ∧,∨ 优先于 →, ↔
如何构建事实?
简单断言:
  • 月亮由绿色奶酪构成    g
  • 下雨了                       r
  • 街上湿了                   n
复合断言:
  • 如果下雨了,则街上湿了 r→n
  • 如果下雨了而且街上没有湿了,则月亮由绿色奶酪构成 (r ∧ ¬n  )→g
命题逻辑中的模式理论语义:
推断I 是 所有的原子命题映射到{t,f}
真值假值表格
truefalsetable
如果I(F)=w 则我们写成I  F
 
基本概念:
  • tautology 重言
  • satisfiable可满足式
  • refutable可驳式
  • unsatisfiable未满足式
一阶逻辑:
逻辑连接符(运算符):同命题逻辑一样
  • 变量:X、Y、Z
  • 常量:a、b、c
  • 函数:f、g、h...
  • 关系/谓词:p、q、r...
示例:(X)( Y) ((p(X) ¬q(f(X),Y)) r(X))
 
一阶逻辑的语法:
 
  • 术语(通过组合变量、常量和函数)
    例如:f(X), g(a,f(Y)), s(a), i(H,T), x_location(Pixel)
  • 原子(通过组合关系和作为论据的术语)
    例如:
    p(f(X)), q (s(a),g(a,f(Y))), add(a,s(a),s(a)),greater_than(x_location(Pixel),128)
  • 公式(通过组合原子、运算符和限定符)
    例如:
    (Pixel) (greater_than(x_location(Pixel),128)  red(Pixel) )
一阶逻辑中如何构建事实?
示例:
  • 所有的孩子都爱冰淇淋:X: Child(X)  lovesIcecreme(X)
  • 一个人的父亲是一个男性的家长:∀X ∀Y: isFather(X,Y) ↔ (Male(X) ∧ isParent(X,Y))
  • 有一个或多个有趣的讲演:∀X ∀Y: isFather(X,Y) ↔ (Male(X) ∧ isParent(X,Y))
结构:
  • 定义一个领域D
  • 常量符号映射至D中的元素
  • 函数符号映射至D中的函数
  • 关系符号映射至D中的关系
然后:
  • 推断将成为D中的元素
  • 带有论据的符号将分为真或假
  • 逻辑连接符和限定符都被处理
逻辑蕴含Logical Entailment
一个理论T是一系列的公式
一个演绎I是T的一个模型:iff I ⊨ G对于所有T中的G均成立。
一个公式F是T的一个逻辑推论:iff 所有T中的模型都是F的模型。
然后我们说T ⊨ F
两个公式F和G被成为逻辑上等价的:iff {F}⊨G and {G}⊨F.
然后我们说:F  G

L4-6 知识表达——标准形式Canonical Form(Normal Form)

逻辑等价:
logical equivalences 

 可换性和量词Commutativity and Quantifiers
  • (X)( Y) F  (Y)( X) F
  • (X)( Y) F  (Y)( X) F
标准形式的目的:将所有的公式转换成子句的形式
(a(b ¬c) (ad))  转换成 {a,{b,¬c},{a,d}}
子句Clause:有限个文字值的分离(finite disjunction of literals) b1∨b2∨b3...bn
将一个简单的子句写成{b1,b2,...bn}的形式
CNF合取范式(Conjunctive Normal Form)是一个个子句的相与
 
所需的步骤:
1.Negation Normal Form 否定范式
     将所有的否定移到内部
2.Prenex Normal Form 前束范式
将所有的量词移至
最前
3.Skolem Normal Form 斯科伦范式
      所有存在量词都去除
4.Conjunctive Normal Form (CNF) = Clausal Form 合取范式
     一个个子句相与的表达
 
否定范式:
  • F  G ≡ (F  G) (G  F) 
  • → G ≡ ¬F ∨ 
  • ¬(F  G) ≡ ¬F  ¬G
  • ¬(F  G) ≡ ¬F  ¬G
  • ¬(X) F ≡ ( X) ¬F 
  • ¬(X) F ≡ ( X) ¬F
  • ¬¬F ≡ F
前束范式:将量词与不同的变量相绑定
 
斯科伦范式:
从左至右移除存在量词
如果在存在量词左边没有全称量词,那么用一个新的常量符号代替这个变量
如果在一个存在量词左边有n个全称量词,那么用一个带有n个参数的新的函数符号代替这个变量,函数的参数是这n个全称参数
 
合取范式:
主要通过逻辑等价式:
F  (G  H) ≡ (F  G)  (F  H)
F  (G  H) ≡ (F  G)  (F  H)
实现转变
 
例子:
 

( (X)( penguin(X)  blackandwhite(X) )
 ( X)( oldTVshow(X)  blackandwhite(X) )
)  ( X)( penguin(X)  oldTVshow(X) )
 
转换为否定范式
¬( (X)( ¬ penguin(X)  blackandwhite(X) )

 ( X)( oldTVshow(X)  blackandwhite(X) )

)  (X)( penguin(X)  oldTVshow(X) )

 
转换为
( (X)( penguin(X)  ¬blackandwhite(X) ) ( X)(¬ oldTVshow(X)  ¬blackandwhite(X) ))  ( X)( penguin(X)  oldTVshow(X) )
转换为
( (X)( penguin(X)  ¬blackandwhite(X) ) ( X)( ¬oldTVshow(X)  ¬blackandwhite(X) ))  ( X)( penguin(X)  oldTVshow(X) )
转换为
( ( X)( penguin(X)  ¬blackandwhite(X) ) ( Y )( ¬oldTVshow(Y)  ¬blackandwhite(Y) ))  ( Z)( penguin( Z)  oldTVshow(Z) )
转换为前束范式
( X)( Y )( Z)( ( penguin(X)  ¬blackandwhite(X) ) ( ¬oldTVshow(Y)  ¬blackandwhite(Y) ) ) ( penguin(Z)  oldTVshow(Z) )
转换为斯科伦范式
( Y)( ( penguin(a)  ¬blackandwhite(a) ) ( ¬oldTVshow(Y)  ¬blackandwhite(Y) ) ) ( penguin( f(Y) )  oldTVshow( f(Y) ) )
转换为
( penguin(a)  ¬blackandwhite(a) ) ( ¬oldTVshow(Y)  ¬blackandwhite(Y) ) ) ( penguin(f(Y))  oldTVshow(f(Y))
转换为 合取范式
( penguin(a)¬oldTVshow(Y) ¬blackandwhite(Y)penguin(f(Y)) ) ( penguin(a)¬oldTVshow(Y) blackandwhite(Y)oldTVshow(f(Y)) ) ( ¬blackandwhite(a) ¬oldTVshow(Y)¬blackandwhite(Y) penguin(f(Y)) ) ( ¬blackandwhite(a) ¬oldTVshow(Y)¬blackandwhite(Y) oldTVshow(f(Y)) )
再转换为 子句范式
{ {penguin(a),¬oldTVshow(Y),¬blackandwhite(Y),penguin(f(Y))},
{penguin(a),¬oldTVshow(Y),¬blackandwhite(Y),oldTVshow(f(Y))},
{ ¬blackandwhite(a),¬oldTVshow(Y),¬blackandwhite(Y),penguin(f(Y))},
{¬blackandwhite(a),¬oldTVshow(Y),¬blackandwhite(Y),oldTVshow(f(Y))} }
 
标准形式的属性:
  • 令F为一个公式
  • G为F的前束范式
  • H为G的斯科伦范式
  • K是H的子句范式
则F=G H=K 但是 F通常不等于K
 
但是如果K是一个矛盾则F也是一个矛盾

L4-7 知识表达——命题逻辑归纳Resolution

不是证明一个公式是重言,而是推断一个从它的反面推导出一个矛盾
 
命题逻辑中
 
如何从一系列的子句中推导出一个矛盾:
  1. 从M中选择两个从句,依照归纳的步骤,创建一个新的从句
  2. 如果K=⊥,则发现了一个矛盾
  3. 如果K ≠⊥,则将K加到M中去,返回第一步
例子:
对于如下一个知识库Φ:
  • 如果下雨,简会带伞
    r→u
  • 如果简带了伞,她就不会淋湿
    u→¬w
  • 如果不下雨,简不会淋湿
    ¬r→¬w
试证明公式ψ:简不会淋湿
  • ¬w
将知识库转化成子句范式:
  • {¬r,u}
  • {¬u,¬w}
  • {r,¬w}
将公式的否定¬¬w = w加入到知识库中,形成新的知识库Φ∧¬ψ
  1. {¬r,u}
  2. {¬u,¬w}
  3. {r,¬w}
  4. {w}
开始归纳:
 
(3,4) {r,¬w}
      {w}
5. {r}
新知识库:
  1. {¬r,u}
  2. {¬u,¬w}
  3. {r,¬w}
  4. {w}
  5. {r}
继续归纳
 
(2,4) {¬u,¬w}
      {w}
6. {¬u}
 
新知识库:
  1. {¬r,u}
  2. {¬u,¬w}
  3. {r,¬w}
  4. {w}
  5. {r}
  6. {¬u}
继续归纳
(1,5) {¬r,u}
      {r}
7. {u}
 
新知识库:
  1. {¬r,u}
  2. {¬u,¬w}
  3. {r,¬w}
  4. {w}
  5. {r}
  6. {¬u}
  7. {u}
继续:
(6,7) {¬u}
      {u}
      {}
发现了矛盾。
 
因而我们证明了 Φ ⊨ ψ
 

L4-8 知识表达——一阶逻辑归纳

一阶逻辑中的归纳需要替换的帮助
(p(X,f(Y))  q( f(X) ,Y)) (¬p(a,Z)  r(Z) ) 在[X/a, Z/f(Y)]的替换下,结果为
(q( f(a),Y)  r(f(Y))).
 
合一子(unifier)对于L1,L2两个Literals
如果用一个变量替换σ使得L1σ=L2σ
则称σ为L1和L2的合一子
合一算法:
  1. 如果L1和L2是常量,则只有在L1=L2时不能合一
  2. 如果L1是变量L2是一个任意术语:当对于L1来说术语L2可以被替换并且变量L1没有出现在L2中时不能合一
  3. 如果L1和L2是谓词或函数PL1(s1,...sm)PL(t1,...tm)时,当PL1=PL2或者n=m且所有的术语si都不能与任何一个ti术语合一时不能合一。
合一示例

 unification example
一个一阶逻辑的归纳示例:
给定TBox:
  • (X) ( human(X)  ( Y) parent_of(Y,X) )(X) ( orphan(X) (human(X)  ¬( Y) (parent_of(Y,X)  alive(Y)))
给定ABox:
  • orphan(harrypotter)
  • parent_of(jamespotter,harrypotter)
是否能推论出¬alive(jamespotter)?
也就是要证明
(( X) ( human(X)  ( Y) parent_of(Y,X) ) ( X) (orphan(X) (human(X)  ¬( Y) (parent_of(Y,X)  alive(Y))) orphan(harrypotter) parent_of(jamespotter,harrypotter)) ¬alive(jamespotter))
是一个重言
 
我们实际要证明
¬((X) ( human(X)  ( Y) parent_of(Y,X) ) ( X) (orphan(X) (human(X)  ¬( Y) (parent_of(Y,X)  alive(Y))) orphan(harrypotter)
 parent_of(jamespotter,harrypotter)) ¬alive(jamespotter))
是一个矛盾
 
证明过程:
转换成前束范式:
(X)( Y)( X1)(Y1)( X2)( Y2)
(( ¬human(X)  parent_of(Y,X) )
 (¬orphan(X1) (human(X1)  (¬parent_of(Y1,X1)  ¬alive(Y1)))
 (orphan(X2)  (¬human(X2)  (parent_of(Y2,X2)  alive(Y2)))
 orphan(harrypotter)
 parent_of(jamespotter,harrypotter))
 alive(jamespotter))
 
转换成子句模式:
{ {¬human(X), parent_of(f(X),X)},
{¬orphan(X1), human(X1)},
{¬orphan(X1),¬parent_of(Y1,X1),¬alive(Y1)},
{orphan(X2),¬human(X2),parent_of(g(X,X1,Y1,X2),X2)},
{orphan(X2) ,¬human(X2),alive(g(X,X1,Y1,X2))},
{orphan(harrypotter)},
{parent_of(jamespotter,harrypotter)},
{alive(jamespotter)}
}
 
知识库:
1. {¬human(X), parent_of(f(X),X)}
2. {(¬orphan(X1), human(X1)}
3. {¬orphan(X1), ¬parent_of(Y1,X1),¬alive(Y1))}
4. {(orphan(X2), ¬human(X2), parent_of(g(X,X1,Y1,X2),X2)}
5. {orphan(X2), ¬human(X2), alive(g(X,X1,Y1,X2))}
6. {orphan(harrypotter)}
7. {parent_of(jamespotter,harrypotter)}
8. {alive(jamespotter)}
 
蕴含子句:
9. {¬orphan(harrypotter), ¬alive(jamespotter)} (3,7) [X1/harrypotter, Y1/jamespotter]
10. {¬orphan(harrypotter)} (8,9)
11.  (6,10)
 
一阶逻辑归纳的属性:
  • 反演的完整性
  • 一阶逻辑归纳具有非决定性

L4-9 知识表达——表格算法Tableaux Algorithm

命题逻辑的表格算法:
  1. 构造一个决定树decision tree,其中每一个节点都标注了一个逻辑公式
  2. 运用表格扩展规则创建树
  3. 表格中的一个路径是封闭的closed:
    如果路径上有x和¬x
    如果出现错误
  4. 如果没有扩展规则可以应用的地方则说表格是完全展开的
  5. 如果一个表格的所有路径都封闭则称表格时封闭的
  6. 对于公式x的表格证明是一个¬x的表格封闭。 

decision tree

表格扩展规则 Tableaux Extension Rules 
对于命题逻辑而言:
 tableaux extension rule pl

 
对于合取公式而言:

 ter conjunctive formula
对于一个disjunctive公式而言:
ter disjunctive formula
命题逻辑示例
证明((q ∧ r)  (¬q ∨ r))
(1) ¬((q ∧ r)  (¬q ∨ r))
(2) α,1: (q ∧ r)
(3) α,1: ¬(¬q ∨ r) = q ∧ ¬r
(4) α,2: q
(5) α,2: r
(6) α,3: q
(7) α,3: ¬r
5和7 路径是封闭的,表格封闭 得证
 
一阶逻辑示例
证明:(x.P(x)∨Q(x)) ( x.P(x))∨(x.Q(x))
(1) ¬((x.P(x)∨Q(x)) ( x.P(x))∨(x.Q(x)))
(2|α from 1) (x.P(x)∨Q(x))
(3|α from 1) ¬((x.P(x))∨( x.Q(x)))
(4|α from 3) ¬(x.P(x))
(5|α from 3) ¬(x.Q(x))
(6|δ from 5) ¬Q(c)
(7|γ from 4) ¬P(c)
(8|γ from 2) P(c)∨Q(c)
(9|β from 8) P(c) | (10|β from 8) Q(c)
 
7和9 6和10 路径封闭,表格封闭 得证

Leave a Reply

Your email address will not be published. Required fields are marked *