语义噪声

【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论文（根据其个人主页），若按美国标准申请教职，怕连面试机会都不会有。

然而Ian的博士论文却是一个震撼性的结果。以前，逻辑学家觉得一个逻辑语言，如果有超过多项式的复杂性，就是一个不应该被考虑的，不实际的语言。而Ian 实践证明，有若干优化算法，可以极大的降低一些有丰富表达力的语言的复杂性（甚至达到三个数量级），这就使后来一系列语言如S, SH, SHIQ, SHOQ, SHION（也就是OWL-DL）成为可能。这是一个很了不起的突破。当时还没有语义网，连XML也没有，可是Ian的工作为10年之后今天的应用打下了坚实的基础。

从此以后，Ian的创造力犹如滔滔江水，连绵不绝。除了在推理优化之外，他在DL表达力的丰富， RDF, OIL 和OWL语言的指定，ABox推理，datatype扩展，语义网规则语言等方面都有不凡的贡献。和许多研究者不同，Ian的大量工作是自己（而不是学生）的原创。大多数年份，他能有10篇甚至更多的第一作者论文，而且绝对是高质量的论文。对于大多数研究人员，这就是奇迹了。

我04年见过Ian Horrocks一面，有幸他坐到我的桌子对面也拿出笔记本改slides，聊了几句. 他给我的印象是个很内敛的人。[2011-12-26补充：后来接触多了，进一步发现，他说话非常的“英国”，一种慢条斯理，带着绅士风度，而其内在立场十分坚定的风格。]

【下面是我的发挥，和Ian的履历其实没有多大关系。这些是2006年的认识，现在看又不成熟。有时间以后再改了。】

Ian 四十岁前并无为世人知的成就，而五十岁时则可以一代宗师的地位傲视群雄。我辈后生，除景仰外，又能得到什么启示呢？

我个人觉得，当代科学，早已不是天才的时代。Ian是不是天才？我不敢说。不过我辈昭昭俗人，恐怕没有几个是天才。博士毕业，大多也30左右了，比之牛顿，爱因斯坦，狄拉克，海森堡之类青年得志者，已经足够老了。不过既然现在科学研究是大科学，个人在其中无非是一个螺丝钉，或者一个在科学进化的育种场中提供随机变异用的种子，真正的个人聪明，比重是越来越小了。科学家成名的年龄越来越晚，实在是一个时代的趋势。这不是一个浮躁者的舞台。（当然，当不了科学家还可以当学术官僚，一样功成名就。）

许多时候，感觉读博士一种程序性的折磨。无穷无尽的寻找，失败，再寻找，再失败。在对一个领域没有了解的时候，寻找的方法不是意义不大，就是别人已经做过了，或者有意义别人也没做过但是自己或者老板的水平又不足以解决。所以许多人都希望开始就找到一个好的题目，不要”浪费时间”。不过快毕业的回过头来一看，恰恰不是最后写在博士论文里的那些东西，而往往是被否定掉的那些想法和方向，使自己对整个领域有了广泛的了解。选择做什么难，选择不作什么就更难了。这恐怕也是博士教育和硕士教育的一个区别吧。

2011-12-26补：我现在回去看自己的博士论文，又有了不同的看法。我现在回去写博士论文，绝不会那样选题，也绝不会是那样做法。

之所以说到这个是从Ian的履历想到，其实人何尝能一开始就找到自己的人生定位呢？如果Ian接着做字处理软件，是不是也会一样出色哪？一个具体的研究课题是一种选择，一个学位是一种选择，在什么国家生活和居住，在什么行业从事工作，和什么样的人终身生活，等等，一个选择就意味着更多的不选择。怎样才能知其可，知其不可呢？如何看待生活中的无穷无尽的寻找，失败，再寻找，再失败呢？

其实一个好的学者，往往有一个好的心态。不急躁，不冒进，调查而后结论；名利视之当然，失败视之当然。我想博士的程序性折磨，对形成这种健康的心态是有益的。教育当然不仅是塑造一个学者，也是塑造一个人，一个健康的，全面的，成熟的人。

再回到选择的问题。博士选题，什么样的最好？我以为计算机科学有大体有两种：树叶型的树枝型的。树叶型的研究，基于既有的理论，或者加以修订，或者加以应用，春天长出，秋天落下，来年便不再有人记得。有的博士论文，就是三四个树叶的集合，何以能指望产生持久影响呢？树枝型的研究，并不着眼于立即生叶开花，而是找到领域的一个切入点，寻求一个不光是对特定对象有效的研究方法，扎扎实实的做几年比较和积累，或许几个春秋之后，才能长出叶芽。而一旦奠定这样的基础，每年都会有新的叶子产生，过几年之后，小枝变大枝，又衍生出新的小枝。Ian的选题，无疑就是一个恰当的树枝，而现在的树叶，也无非是厚积薄发，从当年的小枝演化而来的具体成果。

知道什么不去做是最难的。如果着眼于眼前的publication，做了几个树叶，也及时发了几篇论文，是否就是最优的选择呢？有没有一个规划让自己的工作在更广泛的范围内产生影响呢？Ian如果当年的切入点就是医学知识库的建模和具体实现（其博士论文的资金来源），是否还会产生今天这样大的影响力呢？

子曰，从心所欲不逾矩，大概就是指这种”不选择“的艺术吧。

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

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

逻辑在科学界渗透，也不过是很近的事——比如西方医学，直到20世纪早期，还是经验主义主导的天下。至于真正进入普遍的社会大众的思考，大概现在也没有做到。比如普通美国人，连基本数学都搞不好，你说他会用逻辑思考？有多少人能分清相关性和因果性？要是普通美国人学会了逻辑思考，还会有80%的美国人信教？估计逻辑学家看CNN和Fox News，会气死。

文字的普及用了5000多年。逻辑要普及，我估计至少也是1000年以后的事了。

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

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

我就在想，象他这种人，在中国一定会当个国宝供起来。如果中国有这么一个泰斗级人物，大概走哪都众星捧月地围着吧！麦老您走好。麦老，我扶您上楼梯吧。麦老…麦老… 在美国，无非是一个寂寞的没人理的老头子。

Poster Session那天，我看到John又出现了，就鼓起勇气问他有没有兴趣看看我的Poster（就是上面那张照片喽）。我差不多用了一分钟讲了的大意（是描述逻辑方面的），John似乎听力不很好了，说话也不清楚，好像是说，这个东西他不懂，不是他的领域。

我后来几年做Context Logic（域态逻辑）——这是John的领域了。他的图灵奖获奖演说，就说这个，后来做了不少年。他有个学生Guha，后来去了CYC，在CYC里做context（称为micro theory）；现在Guha在Google，大概是schema.org后面的主要推手之一。我曾经想突破John的框架发展一个表达力更强的逻辑。最近几个月仔细读他和他的学生的论文，觉得其实我想的并没有超越他们十几年前的框架——只是在语法上而不是语义上做了扩展。

Context在很多地方现在都叫得很响，我现在在三星的工作也涉及到Context。只是很少有公司会用到域态逻辑这样深刻的工具——虽然我认为也许在遥远的将来会被用到。也许更早，谁知道呢？很多应用（比如IPhone上的SIRI），如果加上context，会成为难以想象的伟大的东西，现在的Web或者移动界不过是刚刚开始真正实践这个思路而已。到那时，再回去看John在1971年的图灵奖演说，想必又有新的感受。

John还发明了LISP和时分复用(time sharing)。时分复用的意义，不需要说了。LISP呢？现在也早就不仅是学校中的语言了，比如AutoCAD和AllegroGraph（一个主流语义数据库）的开发语言都是LiSP.

我搬到加州的第一天，看到路边挂着大牌子，纪念Steve Jobs的逝世。那几天，铺天盖地的对Steve Jobs的纪念，近乎是刷屏了。而John的逝世，就是在学术界，大概也只有搞人工智能中和逻辑有关的一个小人群纪念一下罢了。类似的，还有最近逝世的Dennis Ritchie（C和UNIX之父）。长远看，到底是Steve对人类的贡献大，还是John/Dennis对人类的贡献大？这个取决于价值观了，想必每个人都有自己的看法。【想到这里，我又想到索马里现在赤地千里，一千多万人受灾，死了上十万人了，谁关心了？不管是Steve还是John，都比十万个索马里人得到的眼球多些。我的价值观又混乱了——这是不相关的胡话】

为什么要把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。

2）contex可以被组合形成新的context. C(x, t1, t2) 不如 ist(C(x), t), t= t1^t2。也可以是其他的逻辑连接符，C(x, t1, t2)这种方式就表现不了了。

3）参前文《RDF and Context （域）》所说：域可以被重用（也就是把冗余部分压缩掉）。域可以被推理。域之间可以有关系。

参前文

• 从概率时态逻辑到概率域态逻辑（Probabilistic Context Logic）
• 笔记：加注(Annotated) RDF (3) Dekhtyar 2001
• 笔记：加注(Annotated) RDF (4) Dekhtyar 2001续
• 笔记：加注(Annotated) RDF (5) APT Logic

【会议版】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）的一种特例。

【待补充】

关于Probabilistic Logic's consistency，在First-order probabilistic logic里就有不少讨论。大意是，不同的逻辑公式可以被指定不同的概率值，比如p(A)=0.2, P(B)=0.1，那0<P(A^B)<0.2, 0.1<P(A v B)<0.3。如果P(a^b) =0.5，那这个theory就不consistent。

【待续】

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（全局树）。

本文提到所谓的ParTree (parallel tree)方法，就是每个线程构造一个本地树，最后将这些本地树组合成一个全局树。P-DL推理算法，就是一种proof-level, ParTree的方法。

由于本文不涉及树图算法本身的并行化，参考意义不大。

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.

2007文目标逻辑是SHN，2010文目标是SHIQ（也就是增加inverse property and qualified number restriction）

主要利用树图算法中的不确定选择，例如disjunction rule或者at-most number restriction rule。这些选择会导致不同的ABox被产生。这些ABox被放在一个优先级队列（priority queue）里。初始ABox的优先级为0，n级ABox产生的ABox级别为n+1。

所谓ABox，其实就是Tableau。

本文没有具体讨论backtracking。如果一个ABox被发现inconsistent，是不是可以简单回到它的“父”ABox?

【构架】偷2010文图

【深入讨论】

所谓并行，就是要在尽可能减少通信代价的前提下，把操作分布到不同的处理器上去。在树图算法中，有几类很明显的可并行处理

• 不确定选择（nondeterministic choices），例：A v B(x) -> A(x)或B(x)
• 不同分支（branch）例：∃R.C ^ ∃R.D (x)  -> R(x,y), C(y)和R(x,z), D(z)，则y和z两个分支可以分别处理。这一点在没有inverse property的时候成立。

有几类很明显的不适合并行处理

• 远程计数（remote counting），例如A(x)在节点1，R(x,y)在节点2，R(x,z)在节点3，要问 =2R (x)是否成立，需要做两次远程查询。
• 如果TBox本身是分布在不同节点上，而且需要远程连接时(remote join)

【分类】

一般做并行推理，大体是要么做数据的分布（distributed data），在树图算法里就是TBox的分布（ABox一定是分布的）；要么做计算的分布（distributed computation），在triple-store里就是推理规则的分布，在树图算法里就是树图扩展的分布。如果TBox较小，可以由各节点共享TBox以减少通信代价。

模块化本体算法，将TBox分布，并改造语义以保证局域化（可以减少通信代价）。如果着眼于直接减少通信代价，可能有其他的DL子集，并不需要局域语义。

Liebig说，分布式推理有reasoner level的和proof level的。他的工作是proof level的。我的P-DL推理也是proof level的。DDL的推理是reasoner level的。

Reasoner level的实现比较容易，但是不能最充分的利用并行特性。

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

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

比如列计划。我往往会列七八件事，说今天要做。但一般的情况，一天下来，一件也没有做完。所以我现在，每天只列一件事。

又比如管理邮件。我曾经给我的Gmail加了几百个tag。这些tag，我自己也记不住，现在还是要靠搜索。

又比如带孩子。妞生下来前，有人送了我们很多本书。我曾经下决心啃啃What to Expect the First Year这本人人说好的砖头，但是一直没有超过第一章。其实哪里需要看完了这书再来带孩子呢？基本的，小宝宝90%以上的情况无非是吃，睡，拉，玩，累虽然累，但并不需要自己来学儿科。

又比如语义网。我刚到BBN的时候，给他们的工程师讲语义网基本原理。听完了，大家都很茫然。有一个说：“这个东西很复杂，不是吗？”我倒是觉得，我已经简化得不能再简化了呢：RDF，OWL，SPARQL，我最多讲了这些技术规范的1%——但是这已经足够让工程师们觉得太复杂了。OWL2组里写OWL2的速查指南，曾经和那些搞逻辑的抱怨，说，如果按OWL本身语法结构来写，东西太多了，原计划的一页无论如何做不到（最后是两页；丁力最初的版本只有不到一页）。逻辑学家们还很奇怪：有什么地方复杂了？他们写的一些文章，说OWL2对OWL做了”a small set of extensions”——也许从逻辑表法力的角度是如此。可是，对工程师来讲，OWL1里有40个保留字，OWL2里有77个（RDF-Based Semantics, Table 3.2）,这是92.5%的增长。这里面的复杂性，不光是逻辑的复杂性，而且是认知的复杂性。OWL2的profiles，降低了逻辑的复杂性，但有没有降低认知的复杂性？语言要人来学，来用。太复杂的东西，不会有人去用。语义网的很多问题，或许来自于此。

我现在审文章，特别痛恨复杂的文章——OK，我自己也有原罪，也写过这种文章。复杂，往往意味着作者自己没搞懂，不是对方法没搞懂，就是对问题域没搞懂。（这也就象看病。古人不知道肺结核的病因，搞出很多复杂的“治疗”方法（比如欧洲的放血和中国的草药）；现在就简单了：上抗生素。现在我们“治”艾滋病，也有很多复杂的昂贵的手段，无非是因为我们不知道什么治。）遇到从头到尾都是公式的文章，我直觉以为，作者自己知道不能convince审稿人，所谓打算confuse审稿人；我决不能让这个伎俩得逞。好的科学，最后都是简单的。

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)，可做分布式推理。但是局域语义的复杂性，使它们不适合现在的工程应用。

所以这个系列，主要是在普通全局语义下，探讨完备的推理算法。其中包括对Tableau Algorithm (树图算法)的并行化的一些讨论。

下面附对Rule-based并行推理的一个简短比较（摘自我自己的一个报告）。这些工作，主要是parallel triple-store，而不是parallel reasoner。

———————————

Distributed RDF Reasoning

Most existing work on distributed RDF reasoning relies on parallelization of rule-based reasoning or partition of data on a cluster.

WebPIE (Web-scale Parallel Inference Engine) by Urbani et al [7, 6] performs rule-based forward reasoning based on the MapReduce programming model. It is implemented using the Hadoop framework.  They have shown inference on a triple set of 100 billion triples and in 1.35 hours on 64 nodes against 10 billion triples. This system does not support querying.

SAOR (by Hogan et al.) [1] computes the closure of an RDF graph using two passes over the data on a single machine. A fragment of the OWL Horst semantics is implemented to allow more efficient materialization and to prevent “ontology hijacking”.

In MaRVIN [10, 4], Kotoulas, Oren and others have presented a technique based on data-partitioning in a peer-to-peer network. A load-balanced auto-partitioning approach was used without upfront partitioning costs.

In Williams, Weaver et al [5], straightforward parallel RDFS reasoning on a cluster is presented. This approach replicates all schema triples to all processing nodes and distributes instance triples randomly. Each node calculates the closure of its partition using a conventional reasoner and the results are merged. To ensure that there are no dependencies between partitions, triples extending the RDFS schema are ignored. This approach does not support complete RDFS reasoning.

Newman et al. [2] decompose and merge RDF molecules using MapReduce and Hadoop. They perform SPARQL queries on the data but performance is reported over a dataset of limited size (70,000 triples).

Husain et al. [8] report results for SPARQL querying using MapReduce for datasets up to 1.1 billion triples.

References

1. A. Hogan, A. Harth, and A. Polleres. Scalable authoritative OWL reasoning for the web. International Journal on Semantic Web and Information Systems, 5(2), 2009.
2. A. Newman, Y. Li, and J. Hunter. Scalable semantics the silver lining of cloud computing. In Proceedings of the 4th IEEE International Conference on eScience. 2008.
3. Adjiman, P., Chatalic, P., Goasdou, F., Rousset, M.-C., and Simon, L. (2006). Distributed Reasoning in a Peer-to-Peer Setting: Application to the Semantic Web . Journal of Artificial Intelligence Research, 25:269,314.
4. E. Oren, S. Kotoulas, G. Anadiotis, R. Siebes, et al. Marvin: Distributed reasoning over large-scale semantic web data. J. Web Sem., 7(4):305-316, 2009.
5. G. Williams, J. Weaver, M. Atre, J. A. Hendler. Scalable Reduction of Large Datasets to Interesting Subsets, In Web Semantics: Science, Services and Agents on the World Wide Web, , 2010
6. J. Urbani, S. Kotoulas, E. Oren, F. van Harmelen, Scalable Distributed Reasoning Using MapReduce, in: Proceedings of the 8th International Semantic Web Conference, 2009.
7. J. Urbani, S. Kotoulas, J. Maassen, F. van Harmelen, H. Bal, OWL reasoning with WebPIE: calculating the closure of 100 billion triples, in: Proceedings of the 7th Extended Semantic Web Conference, 2010.
8. M. F. Husain, P. Doshi, L. Khan, and B. Thuraisingham. Storage and retrieval of large rdf graph using hadoop and mapreduce. In M. G. Jaatun, G. Zhao, and C. Rong, (eds.) Cloud Computing, vol. 5931, chap. 72, pp. 680-686. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
9. R. Soma and V. Prasanna. Parallel inferencing for OWL knowledge bases. In International Conference on Parallel Processing, pp. 75{82. 2008.
10. S. Kotoulas, E. Oren, and F. van Harmelen. Mind the data skew: Distributed inferencing by speeddating in elastic regions. In Proceedings of the WWW. 2010.

一般参 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）来做证明。这和“表”没多大关系。

不如意译为“树图算法”。虽然严格来说，不是所有的Tableau算法都产生树图，有些会产生特殊的森林图，但是一般算法的主要内容，是关于树形结构的构造。

相应的，“Hypertableau Reasoning”是“超树图推理”。

结论: Tableau Algorithm=树图算法

下面这个语音blog总结最近关于手工创建知识库的一些谈话：

参：手工创建知识库的一些问题 （2011-05-04）

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一样。

语法：一阶语言分为两个sort（类）: context sort and discourse sort。公式包括普通一阶公式加上ist(k,w) 其中k是context sort上的term（可能是变量），w是公式。

语义：解释interpretation定义在两个集合上：C(ontext)和D(iscourse)。QLC的模型将每个C上的元素映射到一阶结构的集合，并要求：

• 所有的context的一阶结构有同样的domain（分别对C和D）
• C和D互斥
• C上所有的元素都有对应结构的集合（可能为空）
• 常数在所有的解释里都对应到 同样的对象。

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

McCarthy的初始文章：

• A LOGICAL AI APPROACH TO CONTEXT [最简单介绍]
• Notes on Formalizing Context [IJCAI93简介]
• Formalizing Context (Expanded Notes)  [97比较详细的发展]

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

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）. 例

<c1,c2> -> {A},{B}
<c3> ->{B},{A,B}
<c1,c2,c3> -> {A, B}

换句话说，每个context序列是所有普通model的集合的子集。比如，如果有n个model，那有2^n种可能的context序列（等价类）。

一个公式在一个context序列中真，仅当它在这个序列中每个模型中都为真。

由于vocabulary只在某些context序列中被解释，所以这个语义其实是三值的：true, false, meaningless。

再换句话说，这个语义是把所有可能的模型分成若干子集（可能有交叉）。在讨论公式的validity时，不讨论所有的模型，而只是某些子集（context sequences）。

该语义中有一系列公理，如ist(c1, f1) ^ ist (c1, f2) -> ist (c1, f1 ^ f2) 等。文中提出了一组Inference Rules，并证明了其完备性completeness

【评价：该语义中真正的域，是所谓的context sequence。真值相对于context sequence存在。这样有利于做进入域和退出域的推理（enter/leave context）。如果把context sequence都给以名字，那就可以退化成只有原子域（atomic context, or named context）的逻辑。所以意大利学派，说，这个法子的表法力没有他们的Local Model Semantics高。换句话说，本文里，唯一的从原子域构造复杂域的方法是串联。这个语义里，context本身没有其他的组合方法。】

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. 最关键的语义条件是这一条：

If E is a ground triple (s p o) in the context c then I(E,c) = true if c, s, p and o are in V, IS(p,c) is in IP and < IS(s, c), IS(o, c) > is in IEXT(IS(p,c)). Otherwise I(E,c)= false.

注意，IEXT（外延函数）并不是contextual的，上面的条件中，和普通RDF语义唯一的区别是IS（释名函数）。

在不同的context中，一个URI可以映射到不同的资源上，所以可以对应到不同的外延上。

这里Guha没有具体说context本身之间是不是可以有关系，比如context的层次关系，如果< IS(c1, u), IS(c2, u) > is in IEXT(IS(narrower,u)) then IS(x,c1)(如果存在)= IS(x,c2)。或可定义contex上的一阶关系

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

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

这个“未检出DNA”的结果到了UFO专家嘴里，就变成了“未检出与地球上任何生物相符的DNA”！

这句话，逻辑上一点错都没有，虽然按常识，非常之误导。媒体宣传，往往精于此道，比如说“达赖在50年代中国入侵前是国家领导人”，但是它不说，达赖是*中国的*领导人（人大副委员长）。所谓“事实，只有事实”，就是这样用来洗脑的。

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)]

语义：是对RDF语义的一个扩展。大意是如果两个triple有某种共同的源谱，那它们其他的源谱可能也是也是共同的。具体来说，if pc (s1, p1, o1) = pc (s2, p2, o2), then (s1 p v) = (s2 p v) 其中pc是triple的源谱域，p是一个源谱property（比如createdBy）,v是一个值（比如“张三”）。

【评价】我认为这语义只适用于一些特定的场合，或者可用于启发式推理。但是，很难扩展到一般的情况，而且不适合做基于模型论的逻辑推理。当然，工程上可能需要这种简单的框架。

Paulo Shakarian, Austin Parker, Gerardo I. Simari, V. S. Subrahmanian: Annotated probabilistic temporal logic. ACM Trans. Comput. Log. 12(2): 14 (2011)

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

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

频率函数用来建模说：F为真正好t时间单位后，G为真的频率。在一个线程T里，F会出现很多次，G也出现很多次。这个频率，记为fr(T,F,G,t)。所谓点(pointed)频率函数定义为

Existential Frequency Function说，F为真后t时间单位内，G为真的频率。公式略。

APT Rule: 其中I(Th)是线程Th的概率，fr(Th, F,G,Δt)是线程内频率。两者相乘，是G在F后Δt时间为真的频率的数学期望。

【评价】我认为频率函数没有定义的必要。如果系统的“状态”（model）是遍历的，那在任一个时刻x做采样，看F为真的概率，然后过t时刻做第二次采样，看G为真的概率，就可以得到P(G_x+t|F_x)。这个文章引入频率函数，我并不认为增加了表达力，反而搞得很复杂。

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）分布，p_i = p (1-p)ⁱ
• 二项（bionominal）分布 p_i = C(n,i) pⁱ (1-p)^n-i
• 几何（geometric）分布 p_i =  e^-λ λⁱ / i!

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

时态概率关系（TP-Relations）

TP-tuple

语义：从 TP-tuple（数据域x时间域）->概率[0,1]的映射。

满足关系：（概率值的分配满足区间要求和分布函数）【注意，这个语义不涉及概率本身的语义，和probabilistic logic of Nilsson不同】

解释的例子：

改写概率时态元组（TP-tuple）为普通关系元组

下略

【总结】本文并未涉及概率本身的语义: 没有把概率和模型的分布结合起来。我不是很喜欢这类作品，给人以不必要的复杂之感。一个好的逻辑，语义应该是很清楚的。因为没有概率本身的语义，所以要设计比较复杂的概率组合算法。后面设计的algebra，参考意义不大。

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. 例：

• Package p will arrive in Albany at some time between 9am and 5pm on Nov. 8 with probability 50–60%
• Rain is expected to begin sometime between 2pm and 12 midnight on Nov. 8 with probability 5–20%
• IBM stockwill reach $300 per share some time during the time
  interval Nov 1-10 with probability 90-100%

时间的模型：文中Fig 1 普通数据库，时态数据库和概率时态数据库的区别

• Time Unit: 比如天 day={1,2,…,31}
• Linear hierarchy of time units: 比如 day < month < year
• Time point: 是一个tuple，每个分量来自hierarchy中的一层，例如(2011 May 7 Sat 18 28)
• Calendar: 规定了time point的合法性，比如(2011 Feb 31)是不合法的

Octavian Udrea, Diego Reforgiato Recupero, V. S. Subrahmanian: Annotated RDF. ACM Trans. Comput. Log. 11(2): (2010) 【本文的会议版在ESWC2006】

这个文章里，annotation也是一种偏序结构。也提到有不确定性uncertainty（模糊fuzzy？）, 时态temporal and 源谱provenance等几种应用。

aRDF = annotated RDF

历史：Annotated logic [Kifer ans Subramanian 1992] （要求标注是一个半格semilattice）[Leach and Lu 1996] [Fitting 1991]

语法：每个property属于某个偏序关系。一个aRDF triple是(s, p:a, o)。例如(Jie memberOf:[2001,2008], IowaStateUniversity)。画成图，就是每条边上多出来个annotation：例如（文中Fig 1(a)）

语义：一个aRDF解释（interpretation）是一个从资源到标注的映射。I满足(s p:a o) 如果 a≤ I(s p o).

一个aRDF系统(theory)是可能inconsistent的(Straccia 2010就不会）– 大概是偏序关系弱于格关系的缘故。不过我不认为这在工程上有什么影响。

后面和查询及实验相关的细节略过。（他们的实验说能处理10million triples）

【评价】本文和Straccia 2010方法完全类似。区别在于S文标注在triple上，U文标注在property上。S文要求标注为格，U问要求为偏序。两者的语义，都是从triple映射到标注，再做标注的“大小”比较。这一点应做扩展，从大小比较变成entailment的关系。这就变成了有完整表法力的域态逻辑（contextual logic）。