语义网不需要描述逻辑

写这个是因为被问到,为什么给描述逻辑,比如SHOIQ,加这个那个操作符,对于语义网的会议,在我看来是没有意义的事。

从接触描述逻辑(Description Logic, DL)到现在有差不多10年了,博士论文就是做描述逻辑。又在OWL Working Group工作一段时间,对描述逻辑还算是比较熟悉的。作为知识表现的工具,DL在某些领域是有价值的,特别是医疗等。但越深入了解这个工具,越觉得它对于语义网这个应用领域没有实际意义,是屠龙之技。

read more

智学八卦之Horrocks[2006]

【Net.Weblog.20060324.txt】

【原文写于2006-03-24。那时候我还不认识Horrocks。2008到2009年,我在OWL工作组,Horrocks是工作组主席,有了更多接触。】

Ian Horrocks (http://www.cs.man.ac.uk/~horrocks/)在描述逻辑界可谓泰山北斗,常人不可望之项背。看他的履历,确也并非一条直线。1981年,Ian在曼彻斯特大学计算机本科毕业,去一家微处理器实验室,后来去一个数据流并行结构工作组工作。1983年他去了一家公司,负责字处理程序和桌面出版软件的开发。 (引自其博士论文)。直到1994年,Ian才回到曼大读硕士,95年毕业。又过了2年,作出了Fact推理机,拿到了博士学位。此时Ian已经40岁上下,无论如何不能算少年得志了。况且,他3年只有2个workshop论文(根据其个人主页),若按美国标准申请教职,怕连面试机会都不会有。

read more

逻辑要普及大概再要一千年

又看到一篇文章,把中国近代的落后归结于没有逻辑思考,把“西方”的领先归结为逻辑。我觉得,这是一种贴标签的方法,无助于我们理解中国的暂时落后,也无助于理解逻辑的真实价值。

其实逻辑在西方吃香,也不过是近代“科学”方法被发展后的事。希腊几个城邦的逻辑成就,在“西方”一片蒙昧的汪洋大海中,象几朵火花,很快就灭了。远的不说,就是雅典的近邻斯巴达,有什么逻辑成就可言?还不是把雅典灭了。希腊化时代之后差不多一千年,“西方”先是几乎没有发展逻辑,继而根本就把它集体遗忘了,要从阿拉伯人那里再引进回来。中世纪后期,用经院哲学的马甲,逻辑才慢慢回到“西方”,被少数精英用来论证基督教的合理性,然后又用在科学这个新的思想工具里。单单逻辑本身,还不能产生科学,科学的实验和检错的方法,恐怕比逻辑要再重要些。

read more

纪念John McCarthy

人工智能的创始人John McCarthy刚刚去世。看了Bertrand Meyer在CACM上的Blog,有些感想。

我见过John一次,2007年在温哥华,AAAI年会上。他很老了(那年80整),走路很慢,手不停在抖,大概是帕金森氏症吧。大多数时候,他一个人在走,上下楼都自己一个人。我认得这张脸,问我老板,这是John McCarthy吧,怎么好像大家都不认识他似的。老板说,大概他太老了吧。老到他自己创立的学科的徒子徒孙们,已经不记得开山鼻祖了。

read more

为什么要区分Context和一般知识

为什么要把context(域)和非context知识分开。比如temporal context, 我们可以写成ist(C(x), t),也可以写成C(x,t)。为什么不使用后一种方式?

用context建模有如下好处

1)用context建模可扩展性好。比如原来我们的知识库里有C1(x)… C100(x),现在要加一个时间维度,那要对所有的谓词都修改arity为2。如果以后又有新的context维度,又要修改。比如我们在Wikipedia上做编辑,编辑的revision log并不会加入页面本身作为正文——这些log就是各个版本的context。

read more

笔记:概率时空逻辑

参前文

【会议版】Austin Parker, Guillaume Infantes, V. S. Subrahmanian, John Grant: An AGM-Based Belief Revision Mechanism for Probabilistic Spatio-Temporal Logics. AAAI 2008: 511-516 [bibtex]

【期刊版】John Grant, Francesco Parisi, Austin Parker, V. S. Subrahmanian: An AGM-style belief revision mechanism for probabilistic spatio-temporal logics. Artif. Intell. 174(1): 72-104 (2010)[bibtex]<

本文可以看成概率域态逻辑(probabilistic context logic, PCL)的一种特例。

read more

笔记:描述逻辑的云计算(4)Aslani方法

Mina Aslani, Volker Haarslev: Towards Parallel Classifcation of TBoxes. Description Logics 2008 [bibtex] 【sound but not complete略过】

Mina Aslani, Volker Haarslev: TBox Classification in Parallel: Design and First Evaluation. Description Logics 2010 [bibtex] 【ECAI文章的workshop版,也可略过】

Mina Aslani, Volker Haarslev: Parallel TBox Classification in Description Logics – First Experimental Results.  ECAI 2010: 485-490 [bibtex]

这篇文章是reasoner level并行,而不是proof level并行。在对一个TBox做分类(classification)时,如果有n个概念,就有n(n+1)/2个子类关系测试。本文分析如何将这些测试分给多个独立的线程(thread)。在内存使用上,基于global tree(全局树)。

read more

笔记:描述逻辑的云计算(3)Liebig 2007

Thorsten Liebig, Felix Müller: Parallelizing Tableaux-Based Description Logic Reasoning. OTM Workshops (2) 2007: 1135-1144 [bibtex]

This paper describes our approach for concurrent computation of the nondeterministic choices inherent to the standard tableau procedure.

Thorsten Liebig, Andreas Steigmiller and Olaf Noppens. Scalability via Parallelization of OWL Reasoning In Workshop on NeFoRS: New Forms of Reasoning for the Semantic Web: Scalable & Dynamic 2010

So far the design is tailored to a SMP (symmetric multi processor) architecture, where all processing cores have access to one main memory.

read more

简单

最近想几件事,发现“简单”这个原则在很多场合都很重要。

比如管钱。妞妞妈和我各有一个401k退休账户。我的帐户里可选择的基金很多,我就会多琢磨,这个行业可能比较好,进一点;过了几个月,觉得另一个市场段比较有潜力,进一点,最后搞到有差不多20个基金在组合里。另一个帐户,也就4、5个基金。结果最近两年,那个简单的组合表现都比那个复杂的好,尽管我在复杂的那个上花了更多的时间。

read more

笔记:描述逻辑的云计算(1)背景

Description Logic in the Cloud 这是很扯蛋的说法

或者说描述逻辑的并行计算(Parallel Computing with Description Logic),主要是指查询和推理两种任务。

对于RDFS或者OWL-RL的某个子集,利用MapReduce或者其他基于集群的(cluster-based)的计算,工作不少。不过一般都是基于规则(rule-based)的推理,不保证推理的完备性(completeness)。很多只支持非常有限的推理,比如BBN的SHARD工作。

模块化本体(modular ontology)语言,如Distributed Description Logics, E-Connections and Package-based Description Logics,基于非经典局域语义(Local Model Semantics),可做分布式推理。但是局域语义的复杂性,使它们不适合现在的工程应用。

read more

Tableau Algorithm该怎么翻译

一般参 http://en.wikipedia.org/wiki/Method_of_analytic_tableaux

描述逻辑中的Tableau Algorithm参

An Overview of Tableau Algorithms for Description Logics
by: Franz Baader, and Ulrike Sattler
In: Studia Logica, Vol. 69, Nr. 1 (2001), p. 5–40.

一般中文文献中,都直接称为“Tableau算法”。有少量文献称之为“表算法”,我以为不妥。

Tableau在Merriam-Webster上相关意思有:

  • a graphic description or representation (图形表现)
  • a depiction of a scene usually presented on a stage by silent and motionless costumed participant (舞台造型)

Tableau算法通常是通过构造一个树形的结构(tree-shaped structure)来做证明。这和“表”没多大关系。

read more

笔记:域态逻辑的语义(3)QLC 1996

Buvac, S. (1996). Quantificational logic of context. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI).

概述:本文扩展PLC(Propositional Logic of Context)到一阶逻辑。Context本身也可以作为一阶逻辑的对象。

Context语义上是一组真值赋值。每个QLC的model,把每个context上对应一组一阶结构(first-order structures)。也就是普通一阶模型会属于一个或多个context。

ist(c, f) is true, iff f is true in all first-order structures of c. 这都和PLC一样。

read more

笔记:域态逻辑的语义(1)PLC 1993

参前:域态逻辑的模型论为什么要用模型论语义

McCarthy的初始文章

以上文章都没有正式的语义。

Buvac和Mason的形式化:

Propositional Logic of Context [AAAI 1993]

语法: 命题逻辑加上ist(c, f) – c是context,f是公式

ist ([c1,c2],f) := ist(c1, ist(c2, f))

另外,有些命题proposition可能只在某些context中有意义。所以,对每个context,有一个相关的词汇vocabulary。只有这些词汇才会被做语义解释。

语义:一个模型model是一个从context序列到真值赋值集合(partial truth assignment)的映射。对命题逻辑,真值赋值就是一个命题的集合(set of propositions). 例

read more

笔记:加注(Annotated) RDF (7) Guha 2004

Ramanathan V. Guha, Rob McCool, Richard Fikes: Contexts for the Semantic Web. International Semantic Web Conference 2004: 32-46

Guha是Context建模的先驱。这个文章,无非是McCarthy和Guha的博士论文工作在语义网上的自然应用。我感兴趣的,是第六节Model Theory。

在一般的RDF语义中, IS是一个从URI到IR v IP 的映射(我把它称为“释名函数”)。Guha的语义里,IS是一个从URIxURI到IR v IP 的映射,第一个URI是资源(class, property等),第二个URI是context. 最关键的语义条件是这一条:

read more

重大新闻:奥巴马的儿子全都是基地组织成员!

因为他没有儿子。上面这句话,从逻辑的角度,是真的。在学习OWL的过程中,最让人困惑的是allValuesFrom(∀)。上面这句话写为{Obama} ⊑ ∀hasSon.AlQaedaMember。我们知道{Obama} ⊑  ∀hasSon.⊥ (没有儿子),可以推理出任意的{Obama} ⊑ ∀hasSon.C,C可以是变形金刚或者外星人。

之所以想到这个 ,是看到《墨西哥“外星婴儿”现形记》(科学松鼠会),里面提到一个似是而非的说法

read more

笔记:加注(Annotated) RDF (6) Sahoo 2010

S.S. Sahoo, O. Bodenreider, P. Hitzler, A. Sheth, K., Thirunarayan, “Provenance Context Entity (PaCE): Scalable provenance tracking for scientific RDF data.”,in the 22nd International Conference on Scientific and Statistical Database Management (SSDBM) 2010

讲RDF的Context(或者annotation)建模的文章虽多(几十篇总是有的),涉及语义的很少。这一篇,定了“源谱域实体”Provenance Context Entity (PaCE) [注:provenance=源谱, context=域]。

语法:Provenance当然是很重要的一种context。本文中,provenance用provenir来建模,本身就是一个RDF/OWL文档。[Provenir是Sahoo自己提出来的。关于不同的源谱模型的比较,参Li Ding和我的这篇文章 (IPAW2010)]

read more

笔记:加注(Annotated) RDF (5) APT Logic

Paulo ShakarianAustin ParkerGerardo I. Simari, V. S. Subrahmanian: Annotated probabilistic temporal logicACM Trans. Comput. Log. 12(2): 14 (2011)

从概率时态逻辑到概率域态逻辑(Probabilistic Context Logic)。今天重读此文。另参前篇笔记:加注(Annotated) RDF (3) Dekhtyar 2001

和前述各篇不同的是,APT Logic中的概率不简单视为标注(annotation),而是有possible world semantics。一个线程是一个状态变化的流(时间到模型model的映射),所有可能的线程构成概率空间,概率分布定义在线程上。 文章的核心贡献是频率函数frequency function,在线程内部可以做概率推理。

read more

笔记:加注(Annotated) RDF (4) Dekhtyar 2001续

Alex Dekhtyar, Robert B. Ross, V. S. Subrahmanian: Probabilistic temporal databases, I: algebra. ACM Trans. Database Syst. 26(1): 41-95 (2001)

【续笔记:加注(Annotated) RDF (3) Dekhtyar 2001

概率分布函数:在时间域(在本文中是calendar)上,每个时间点的概率值。注意,本文只讨论离散的分布函数。

常见的分布函数:

  • 均匀(uniform)分布,例如“下雨”这件事,按星期一到星期日算,差不多是均匀分布。
  • 几何(geometric)分布,pi = p (1-p)i
  • 二项(bionominal)分布 pi = C(n,i) pi (1-p)n-i
  • 几何(geometric)分布 pi =  e λi / i!

如果已知e1和e2的概率,那e1∧e2的概率是多少?有conjunctive和disjunctive两种策略。具体看section 2.4 and 2.5

read more

笔记:加注(Annotated) RDF (3) Dekhtyar 2001

Alex Dekhtyar, Robert B. Ross, V. S. Subrahmanian: Probabilistic temporal databases, I: algebra. ACM Trans. Database Syst. 26(1): 41-95 (2001)

正文44页,共67页。

背景:这个似乎和Annotated RDF无关。不过,temporal information是一种最常见的annotation,而在tuple上的工作,自然也可以用在triple上。Alexander Dekhtyar是Subrahmanian 2000年毕业的PhD。后面的APT (Annotated Probabilistic Temporal) Logic [Shakarian 2011]看似是这个工作的扩展

基本建模对象:Data tuple d is in relation R at some point of time in the interval [ti, tj ] with probability between p1 and p2. 例:

read more