Archive

Archive for the ‘逻辑’ Category

智学八卦之Horrocks[2006]

2011/12/26 1条评论

【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如果当年的切入点就是医学知识库的建模和具体实现(其博士论文的资金来源),是否还会产生今天这样大的影响力呢?

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

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

2011/12/08 2 条评论

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

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

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

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

分类:逻辑, 随感, 历史

纪念John McCarthy

2011/11/07 1条评论

人工智能的创始人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和一般知识

2011/05/28 1条评论

为什么要把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 (域)》所说:域可以被重用(也就是把冗余部分压缩掉)。域可以被推理。域之间可以有关系。

分类:逻辑, 思路

笔记:概率时空逻辑

2011/05/18 留下评论

参前文

【会议版】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。

【待续】

分类:笔记, 逻辑

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

2011/05/15 1条评论

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的方法。

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

分类:笔记, 逻辑

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

2011/05/15 1条评论

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的实现比较容易,但是不能最充分的利用并行特性。

分类:笔记, 逻辑