（计算机科学与技术专业论文）语义万维网的不确定知识表示与信任计算.pdf

浙江大学博士学位论文 摘要 摘要 万维网( w o r l d w i d e w 曲) 的出现改变了人们的交流方式和商业模 式，并逐渐成为人们通向知识经济和知识社会的核心支撑技术。语义 万维网( s e m a n t i c w 曲) 扩展了现有的万维网技术，通过制订相应的标 准和规范，将网络资源以计算机更易处理方式加以表示，并利用智能 技术来发挥这种表示方法所带来的潜在优势，实现诸如信息抽取、知 识融合和基于知识搜索等高层功能和应用。 在语义万维网技术的层次结构中，目前较为成熟的部分( 至底向 上) 有x m l ( 可扩展标记语言) 、r d f r d f s ( 资源描述框架及其模式) 和o w l ( 本体论语言) ，而在o w l 之上的逻辑层和证明层( 规则语言 及其推理) 相关标准的制订工作仍处于需求征询阶段，信任层则还处 于研究阶段。 本文的研究是围绕语义万维网技术的逻辑层、证明层和信任层展 开的，本文的主要内容与贡献如下： _ 针对单独采用描述逻辑( r d f o w l 的逻辑学基础) 或霍恩规则进 行知识表示与推理的局限性，以及目前描述逻辑和霍恩规则结合推理 算法并不同时具备可判定性和合理性问题，利用“约束逻辑”的消解 原理，提出了描述逻辑4 c 腕和霍恩规则相结合的可判定推理算法， 并且证明了约束消解算法的合理性和完备性： - 提出了适合于语义万维网的混合知识表示系统a r t i g e n t ，该系统由 三个组成部分：描述逻辑a c c 腕、一组霍恩规则和事实集合。利用概 率逻辑的思想，提出了在a r t i g e n t 系统的霍恩规则和事实部分中引入概 率不确定性后的推理算法，并将这种不确定推理转化为求解相应的线 性优化方程； 针对语义万维网技术的信任层，提出了基于贝叶斯分析的“封闭” 和“开放”信任计算模型。模型充分考虑了信任计算过程中涉及的五 1 i i 语义万维网的不确定知识表示与信任计算 大关键因素：计算成本、机会成本、服务费用、咨询费用和效用，并 且提出了平衡这些成本和得益的方法。模型具有坚实的数学理论依据 和概率论上合理的解释，能够综合各种来源的信息为用户提供反映其 偏好的一组个性化计算结果，从而辅助用户理性决策； a r t i g e n t 系统的描述逻辑断言和事实部分可以来源于关系数据库， 并将语义数据库网格作为数据库集成和访问的基础平台。为了解决语 义数据库网格系统查询效率较低的问题，以及数据库网格结点在设计、 通信和执行方面的异质异构性与自治性对查询优化造成的困难，设计 了适合于语义数据库网格的查询优化器，并且提出了相应的代价模型 和查询优化算法d g - q o a 。该算法具有动态、并行和启发式的特点，启 发式方法用于限制查询执行策略的搜索空间；并行性用来减少查询的 响应时间；而动态性则能保证依据精确的统计和系统信息来确定后继 的查询执行序列； 一对有代表性的知识表示方法进行了综述与概括，指出了它们各自 的特点和相互之间的关系，并讨论了知识表示的基本要求。以近期一 些主要的研究工作和成果为依据，本文认为：面向网络、运用本体论 和面向对象思想、具备可判定性，并且结合两种或两种以上知识表示 方法的混合知识表示系统是目前和将来的研究重点。 关键词：语义万维网，知识表示，描述逻辑，霍恩规则，信任计算 浙江大学博士学位论文 摘要 a b s t r a c t t h ew o r l dw i d ew e bh a sc h a n g e dt h ew a yp e o p l ec o m m u n i c a t ew i t he a c h o t h e ra n dt h ew a yb u s i n e s si sc o n d u c t e d i tl i e sa tt h eh e a r to far e v o l u t i o nt h a ti s c u r r e n t l yt r a n s f o r m i n gt h ew o r l dt o w a r dak n o w l e d g ee c o n o m ya n dk n o w l e d g e s o c i e t y h o w e v e r , t h em a i no b s t a c l et op r o v i d eb e t t e rs u p p o r tt ow e bu s e r si st h a t ， a tp r e s e n t t h em e a n i n go f 舱6c o n t e n ti sn o tm a c h i n e a c c e s s i b l e 刃聍s e m a n t i c w e be x t c n d st h ec u r r e n tw e bt or e p r e s e n tw j bc o n t e n ti naf o r mt h a ti sm o r ee a s i l y m a c h i n e p r o c e s s a b l ea n dt ou s ei n t e l l i g e n tt e c h n i q u e st ot a k ea d v a n t a g eo ft h e s e r e p r e s e n t a t i o n s t h em a i ni n t e n t i o no ft h es e m a n t i cw e bt h a te n a b l e st h ew e b r e s o b r c e st oh eu n d e r s t o o db yt h er e s o u r c eu s a g ea n ds e r v i c em e c h a n i s m si st o s u p p o r th i g h - l e v e li n f b n n a 6 0 ne x t r a c f i n g k n o w l e d g ef u s i o na n dk n o w l e d g e - b a s e d s e a r c h t h es e m a n t i cw e bc o n s i s t so f s e v e r a lh i e r a r c h i c a ll a y e r s w h e r et h eo n t o l o g y l a y e f ，i nf o r mo ft h eo w lw 曲o n t o l o g yl a n g u a g e ( r e c o m m e n d e db yt h ew 3 c ) i sc u r r e n t l yt h eh i g h e s tl a y e ro fs u f f i c i e n tm a t u r i t y o nt o po ft h eo n t o l o g yl a y e r ， t h er u l e s l o g i c a n dp r o o fl a y e r so ft h es e m a n t i cw 曲w i l lb ed e v e l o p e dn e x t w h i c hs h o u l do f f e rs o p h i s t i c a t e dr e p r e s e n t a t i o na n dr e a s o n i n gc a d a b i l i t i e s f o l l o w i n gt h e s eo b s e r v a t i o n ，t h i sd i s s e r t a t i o n sc o n t r i b u t i o n sa r e ： 一n l ca u t h o rp r e s e n t san o v e lf a m i l yo fr e p r e s e n t a t i o nl a n g u a g e st h a tc o m b i n e t h ee x p r e s s i v ep o w e ro fh o r nr u l e sa n dd e s e r i p t i o n1 0 9 i c s f o l l o w i n gb f i r c k e r t ，a c o n s t r a l n e dl o g i cs c h e m eh a sb e e ni n t r o d u c e dw i t har e s o l u t i o np r i n c i p l ef o rh o m c l a u s e sw h o s ev a r i a b l e sa r ec o n s t r a i n e db v4 c c 诧d e s c r i p t i o nl o g i c c o n s t r a i n t s c a nb es e e na sq u a n t i f i e rr e s t r i c t i o n sf i l t e r i n go u tt h ev a l u e st h a ta n yi n t e r p r e t a t i o n o ft h eu n d e r l y i n gd e s c r i p t i o nl o g i cc a na s s i g nt ot h ev a r i a b l e so fah o r nc l a u s e w i t hs u c hr e s t r i c t e dq u a n t i f i e r s i ts h o w st h a tt h i sk i n do fc o n s t r a i n e dr e s o l u t i o ni s s o u n d ，c o m p l e t ea n dd e c i d a b l ei nt h a t as e to fc o n s t r a i n e dh o mc l a u s e si s u n s a t i s f i a b l eo v e rac e r t a i nd e s e r i p t i o nl o g i ci fa n do n l yi ff o re a c hc a n o n i c a l i n t e r p r e t a t i o no ft h ed e s c r i p t i o nl o g i cw ec a nd e d u c eac o n s t r a i n e de m p t yc l a u s e w h o s ec o n s t r a i n ti ss a t i s f i a b l ei nt h a ti n t e r p r e t a t i o n _ ah y b r i ds y s t e mf o rk n o w l e d g er e p r e s e n t a t i o n c a l l e da r t i g e n t , h a sb e e n p r o p o s e dw h i c hb a s e do n4 c 嗽d e s c r i p t i o nl o g i c h o mr u l e sa n dp r o b a b i l i s t i c l o g i c i ts h o w st h a tt h er e a s o n i n gu n d e ru n c e r t a i n t yi nt h ea r t i g e n ts y s t e mi s i n s t a n c e so fac e r t a i nt y p eo fl i n e a r p r o g r a m m i n gm o d e l t y p i c a l l y w i t l l e x p o n e n t i a l l ym a n y v a r i a b l e s t h er e a s o n i n ga l g o r i t h mo f t h ea r t i g e n ts y s t e mh a s t h r e es t e p s ：f o re v e r yc l a s h f r e ec o m p l e t i o no ft h ec o n s t r a i n ts y s t e mt h a ti sb u i l t f r o mac e r t a i na z ：c a ；t ek n o w l e d g eb a s e ，b u i l dac a n o n i c a li n t e r p r e t a t i o n ；f o re a c h c a n o n i c a li n t e r p r e t a t i o n , c h e c kw h e t h e rw ec a nd e d u c eac o n s t r a i n e de m p t yc l a u s e v 语义万维网的不确定知识表示与信任计算 摘要 w h o s ec o n s t r a i n ti ss a t i s f i 曲l ei nt h ec a n o n i c a li n t e r p r e t a t i o n ；s o l v et h ec o l t e s - p o n d i n gl i n e a ro p t i m i z a t i o np r o b l e m sf o re a c hs u c c e s s f u lc o n s t r a i n e dr e s o l u t i o n w ep r o v em a tt h er e a s o n i n gi nt h ea r t i g e n ts y s t e mi se x p t i m e - h a r d 一m o d e l i n gt r u s tp r o p e r l ya n de x p l o r i n gt e c h n i q u e sf o re s t a b l i s h i n gc o m p u - t a t i o n a lt r u s ti saf u n d a m e n t a lb u i l d i n gb l o c kt or e a l i z et h es e m a n t i cw e b v i s i o n a s e a l a b l ep r o b a b i l i s t i ca p p r o a c hh a sb e e np r o p o s e df o rt r u s te v a l u a t i o nw h i c h c o m b i n e sav a r i e t yo fs o u r c e so fi n f o r m a t i o na n dt a k e sf o u rt y p e so fc o s t s ( o p e r a t i o n a l ，o p p o r t u n i t y , s e r v i c ec h a r g ea n d c o n s u l t a n tf e e ) a n dt a i l i t yi n t o c o n s i d e rd u r i n gt h ep r o c e s so ft r u s te v a l u a t i o n n 圮a p p r o a c hg i v e st r u s tas t r i c t p r o b a b i l i s t i ci n t e r p r e t a t i o nw h i c hc a na s s i s tr i s e r s w i t hm a k i n gt h er e a s o n a b l e d e c i s i o n si nc h o o s i n gt h ea p p r o p r i a t es e r v i c ep r o v i d e r sa c c o r d i n gt ot h e i r p r e f e r e n c e s af o r m a lr o b u s ta n a l y s i sh a sb e e nm a d et oe x a m i n et h ep e r f o r m a n c e o f t h ea p p r o a c h - a s s e r t i o n so fd e s c r i p t i o nl o g i ca n df a c t sc a l lb ep r o v i d e db yr e l a t i o n a l d a t a b a s e sa n dw en s es e m a n t i cd a t a b a s eg r i dt oi n t e g r a t ed a t a b a s er e s o u r c e s a l t h o u g hm a n ya l g o r i t h m sh a v e b e e np r o p o s e df o ro p t i m i z i n gq u e r y - p r o c e s s i n gi n o r d e rt or a i n i m i z ec o s t sa n d o rr e s p o n s et i m e , a s s o c i a t e dw i t ho b t a i n i n gt h ea n s w e r t oq u e r yi nd i s t r i b u t e dd a t a b a s es y s t e m s ，s e m a n t i cd a t a b a s eg r i dq u e r yo p t i m i z a - t i o np r o b l e mi sf u n d a m e n t a l l yd i f f e r e n tf r o mt r a d i t i o n a ld i s t r i b u t e dq u e r yo p t i m i - z a e t i o n t h e s ed i f f e r e n c e sa r es h o w nt ob et h ee o n s e q u e n c e so fa u t o n o m ya n d h e t e r o g e n e i t yo fd a t a b a s en o d e si nt h ed a t a b a s eg r i d f o l l o w i n gt h i so b s e r v a t i o n , t h ea u t h o rp r e s e n t st h ed e s i g no faq u e r yo p t i m i z e rf o rs e m a n t i cd a t a b a s eg r i d ， a n dp r o p o s e st h eq u e r yo p t i m i z a t i o na l g o r i t h m sd g - q o aw i t hh e u r i s t i c ，d y n a m i c ， a n dp a r a l l e lc h a r a c t e r i s t i c s ，h e u r i s t i c sf o rr e d u c i n gs o l u t i o ns p a c e ，d y n a m i cf o r g e n e r a t i n gb e t t e re x e c u t i o ns e q u e n c e s ，a n dp a r a l l e l i s mf o rm i n i m i z i n gr e s p o n s e t i m e r e p r e s e n t a t i o n , a c q u i r e m e n ta n da p p l i c a t i o no fk n o w l e d g ea r et h r e em a i n d o m a i no fr e s e a r c hi na r t i f i c i a li n t e l l i g e n ta n dk r ( k n o w l e d g er e p r e s e n t a t i o n ) s e r v i n ga sas t a r t i n gp o i n to rb a s i so ft h et w ol a t e r w cr e v i e wa n dd i s c n s sb a s i c k r ( 1 0 9 i cf o r m a l i s m s , p r o d u c t i o ns y s t e m ，s e m a n t i cn e t w o r k ，t a b l e , a r t i f i c i a ln e u r a l n e t s ，f r a m ea n de t c ) a n dc o m p l e xk r ( n e u r u l e s ，b a y e s i a nn e t w o r k ，k n o w l e d g e p e t r in e ta n dv a r i a n t s ) u s u a l l yi n t e g r a t i n ga n dm o d i f y i n g 谢t i lo n eo rm o r eb a s i c c o n s e q u e n t l y , t h ea u t h o rp r o p o s e ss o m et r e n d si nd e v e l o p m e n to fk r h y b r i d o r c o m b i n a t i o n , m e t h o d o l o g yo fo n t o l o g y , o b j e c t - o r i e n t e da n dw 曲- o r i e n t e d f i v e 1 e v e l sa n dt h r e ed i m e n s i o n so f r e p r e s e n t a t i o na l s oh a v e b e e nd i s c u s s e d k e y w o r d s ：s e m a n t i cw e b ，k n o w l e d g er e p r e s e n t a t i o n , d e s c r i p t i o nl o g i c ， h o r nr u l e s ，t r u s tm o d e l 一v i 浙江大学博士学位论文 第一章绪论 1 1 背景 第一章绪论 万维网( w o r l dw i d ew e b ) 的出现改变了人们的交流方式和商业模 式，并逐渐成为人们通向知识经济和知识社会的核心支撑技术。它同 时也改变了人们对计算机本身作用的认识，早期主要被用于科学数值 运算的计算机，如今已经广泛应用于数据管理、文本编辑和休闲娱乐 等方面，并正逐步发展成为连结“信息高速公路”的“智能”结点。 然而，目前绝大多数网络内容只适合具备智能的人来阅读与处理，即 使从数据库里自动提取的数据也失去了它原有的结构化信息，从而不 适合计算机进行自动处理。另一方面，人脑的处理能力是有限的，特 别是面对大量的信息和资源时，更显得力不从心，这与网络上已经存 在的、并且日益快速增长的海量信息和资源形成了鲜明的对比。不论 在商业、科研、教育、娱乐等领域，如何有效和充分地利用网络上的 信息和资源已经成为胜负成败的关键因素之一。某种意义上说：“谁 能更好地利用网络，谁就能够赢得未来”。 1 1 1 网络信息利用不充分 目前典型的网络应用场景是：搜寻和阅读网页、浏览在线产品目 录并通过提交表单来订购商品、寻找和结识网友等，但现有的软件工 具未能很好地支持这些应用。除了网页间存在的链接之外，能为人们 带来便利的工具就只有搜索引擎了。搜索引擎无疑取得了巨大的成功， 然而，象g o o l g e 、y a h o o 和百度这类基于关键词匹配技术的搜索引擎仍 然还存在以下的问题【l 】： 高查全率，低准确性。尽管内容高度相关的网页己包含在搜索结 果之中，但是它们被掺杂在数以万计的其它低相关度、甚至不相 语义万维网的不确定知识表示与信任计算第一章绪论 关的网页中。许多有价值的信息很容易被淹没在巨大的“信息海 洋”里，无法起到其应有的作用； 低查全率或搜索没有返回结果。在提交查询请求后的返回结果中， 重要或相关的网页未能被搜索出来； 查询结果对关键词高度敏感。通常最先选择的关键词并不能产生 我们所期望的查询结果。这是由于某些网页中使用了与我们所选 关键词不相同的术语，尽管它们之间的意思十分相近或者相似。 然而，我们希望的是：语义相同的查询能够返回相同的搜索结果： 查询的结果之间缺乏语义关联。如果我们需要的信息分散在许多 不同的网页中，我们必须构造若干个查询来获取所需要的文档， 然后人工提取文档里的部分信息，并将它们串并起来。这会让人 感到非常烦琐，并占用了大量的宝贵时间。 正是由于以上问题，人们目前还不能够真正充分和有效地利用网 络这个巨大而又丰富的信息和知识宝库。产生这些问题的根本原因是： 现代计算机在自然语言理解和信息自动提取方面的能力还十分有限， 同时目前网络上绝大多数内容都是为人脑阅读而设计和准备的。一种 解决的方法是：开发高级的基于人工智能和计算语言学的智能软件来 对网页信息进行自动分析和处理。尽管这方面取得了一些令人鼓舞的 成果，但由于自然语言理解的极度复杂性，还远不能满足实际应用的 要求。另一种可供选择的方法是：把网络内容表示成计算机易于处理 的规范形式，并结合一些智能技术来发挥和利用这些规范表示形式所 带来的潜在优势和价值。这就是我们后面将要提到的语义万维网 ( s e m a n t i c w e b ) 技术的核心思想。 1 1 2 知识表示的发展趋势 知识表示、获取和使用是入工智能三大主要的研究领域，而知识 表示是其中的前提和基础。目前已经提出了一阶谓词逻辑、产生式规 则、语义网络、框架等多种知识表示的方法。经过数十年的发展，知 浙江大学博士学位论文第一章绪论 识表示研究出现了某些新的发展趋势。 认识到任何单一知识表示方法的局限性( 表达能力不足) ，出现了 在一个系统中结合两种或两种以上知识表示方法的混合智能系统 ( h y b r i d i n t e l l i g e n ts y s t e m ) 。混合智能系统的研究始于上世纪8 0 年代后 期，早期工作是将人工神经网络与专家系统1 2 1 或模糊逻辑与专家系统 相结合1 3 1 。混合智能系统通过结合、集成、融合和协调数种知识表示 方法来增强和提高系统的整体能力和性能。 把本体论作为正式、明确的规范用于某个领域概念化的思想在 a g e n t 计算、分布式信息系统和专家系统等计算机科学界引起越来越广 泛的兴趣和关注。本体论是通过交互各方( 人或程序) 对特定领域内 共用的词汇、术语以及其上的分类建立一致的认可和理解的基础上， 进行知识共享和重用的思想。本体论在面对变化的环境中，所拥有的 易交互性、灵活性、扩展性和可维护性也逐渐融入到某些典型的知识 表示方法中。 由于分布式计算的重要性日益明显，基于模块化的软件设计成为 了主要的趋势。如今。大部分的应用系统都采用面向对象方法，智能 系统的设计开发也一样。事实上，在人工智能界，面向对象的思想早 在上世纪7 0 年代就隐含于m a r v i nm i n s k y 所提出的框架知识表示方法 中。框架系统对后来发展起来的术语语言或描述逻辑有着重要的影响。 而发展描述逻辑的主要目的是使其继承逻辑系统所拥有的规范表示形 式和精确语义定义等特点，同时保留类似语义网络和框架知识表示方 法易被人们理解的优点。 网络的广泛应用和迅速发展，使得任何一种系统不得不提出面向 网络环境的解决途径。在开放、动态、分布的网络环境下，如何实现 知识的共享、重用、协作、交互和转换等是如今网络技术迅速发展和 影响力日益增加的迫切要求。为了在原万维网基础上能够表达更高层 次的语义知识，提出了语义万维网( s e m a n t i c w e b ) 的设想。语义万维 网的观点是由计算机程序来自动完成网络信息和资源地交互、共享和 语义万维嘲的不确定知识表示与信任计算第一章绪论 协调，从而支持数据集成、知识发现和辅助决策等高层功能和应用。 从上面的分析可知，面向网络、运用本体论和对象化思想，并且 结合两种或两种以上知识表示方法的混合知识表示系统是目前和将来 的研究重点。特别是万维网技术的出现和发展极大地改变了人们的生 活和商业方式，并且已经在社会经济中产生了举足轻重的作用，而语 义万维网是现有万维网技术的扩展，它将有可能成为第二代万维网标 准的核心技术。 1 1 3 语义万维网 语义万维网的基本目标是：通过对网络资源在语义上明确和规范 的描述来实现用户、程序、a g e n t 等网络实体之间资源共享、交互和协 调，并且能够完成诸如信息抽取、知识融合和基于知识搜索等高级功 能和应用。语义万维网技术希望通过缩小和弥合人的认知域与计算机 的处理域之间的距离，以支持人们用直观的语义对信息资源在概念层 次进行操作。语义万维网技术的发展有来自于业界的大力推动和各政 府的大额资金投入，美国政府已经成立了有关的d a m l 项目( d a r p a a g e n t m a r k u p l a n g u a g e p r o j e c t ) ，欧盟则将语义万维网列入第六个构想计 划( s i x t h f r a m e w o r k p r o g r a m m e ) 的主要行动指南。 b e r n e r s l e e l 提出的语义万维网技术层次结构中，主要由可扩展标记 语言x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 、资源定义框架r d f ( r e s o u r c e d e s c r i p t i o n f r a m e w o r k ) 、本体论语言o w l ( w e b o n t o l o g y l a n g u a g e ) 、逻 辑层( l o g i c ) 、证明层( p r o o f ) 、信任层( t r u s t ) 所组成。国际万维网 标准协会w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 已经提出了用于网络资源 描述的r d f 标准。r d f 虽然提供了知识表示的基本功能，但在知识表 达力上不能满足实际应用的需求。所以，w 3 c 在r d f 的基础上发展了 o w l 语言用于表达领域本体的概念和概念之间的关系，使其表达能力 近似于某个描述逻辑系统。 b e m c r s - 1 _ c e 在2 0 世纪年代来期提出了万维瞬( w o r l d w i d e w e b ) 浙江大学博士学位论文 第一章绪论 目前，在语义万维网技术的各层次中，从下至上，已经较为成熟 的部分仅止于本体论语言o w l 。o w l 有三个表达能力递增的子语言： o w l l i t e 、o w l d l 和o w l f u l l ，其中o w l l i t e 和o w l d l 相当于描述 逻辑中的s r f z y ( o ) 和跏酬d ) 1 4 】。在本体论语言层之上的逻辑层和证 明层( 规则语言以其推理) 相关标准的制订仍在进行中。目前w 3 c 成 立的规则交换规范工作组( r u l ei n t e r c h a n g ef o r m a tw o r k i n gg r o u p ) 仅发 布了规则交互格式r i f ( r u l ei n t e r c h a n g ef o r m a t ) 的用例和需求草案。 关于信任层，除了数字证书等技术之外，目前还是基本处于理论研究 阶段，尚没有统一的标准能被人们广泛认同和接受。 1 2 研究的进展与动态 本文是围绕语义万维网技术的逻辑层、证明层和信任层展开的， 首先讨论结合描述逻辑( 0 w l 的理论基础) 和霍恩规则的知识表示和 推理，并且以此为基础提出了混合知识表示系统a r t i g e n t ，它由描述逻 辑舭卧傀、一组霍恩规则和事实集合三部分组成，并具备一定的不确 定性推理能力。然后讨论适合语义万维网的信任计算模型和语义数据 库网格的查询优化( a r t i g e n t 系统的描述逻辑断言和事实部分可来源于 关系数据库，我们通过网格和语义技术来集成分布在各地的数据库系 统) 。因此，以下仅对涉及结合描述逻辑与霍恩规则的不确定推理、信 任计算模型和传统分布式数据库查询优化的主要研究成果和文献进行 综述，至于知识表示理论和方法将在第二章中专门进行分析与讨论。 1 2 1 结合描述逻辑与霍恩规则的不确定推理 与本文相关的结合描述逻辑与霍恩规则的不确定推理研究工作大 致可分以下为三类：描述逻辑与霍恩规则相结合的混合知识表示方法； 概率描述逻辑；非概率的不确定描述逻辑。 l e v y 的c a r i n 系统【5 1 和d o n i n i 的，4 c 1 0 9 系统旧是第一类研究工作 的代表。c a r i n 是结合描述逻辑和霍恩规则的混合知识表示系统，该 语义万维网的不确定知识表示与信任计算 第一章绪论 系统描述逻辑部分选用了4 c c 诧。但是除非满足一些限制条件，当出 现循环规则( r e c u r s i v e h o r n r u l e s 2 ) 的时候，该系统是不可判定的。l e v y 将不可判定性的原因归结为描述逻辑舡锨的某些构造符( 如：v r c 和茎开矗) ，并提出满足以下两个条件的情况下，推理算法才是可判定的： 描述逻辑不包含v r c 和 n r 构造符，并且概念之间不存在循环定 义； 系统中霍恩规则必须都是角色安全( r o l e s a f e ) 的。描述逻辑的角 色可以看成是二元谓词，而角色安全要求霍恩规则中的每一个角 色谓词至少有一个变元同样也出现在基原子谓词3 中。 d o n i n i 也提出了类似c a r i n 的4 c 1 0 9 系统1 6 】，但该系统的描述逻辑 部分仅为一4 c c ，同时系统的霍恩规则中仅能出现描述逻辑所定义的概 念，而不能出现角色( 即二元谓词) ，因而表达能力有限。此外，4 c 1 0 9 系统的推理算法将描述逻辑作为霍恩规则的约束，然后产生霍恩规则 的所有消解结果，最后检验每一个消解结果所要求的约束条件是否能 在描述逻辑一4 c c 中被满足。这样的算法是不合理的，原因是：算法过 程仅表明这些约束在部分描述逻辑模型下被满足，而逻辑蕴涵或逻辑 结果要求在所有描述逻辑的模型下，都能推导出相应的空规则( 即消 解过程成功) 。此外，r o s a t i ： 初步探讨了本体和规则结合推理的计算复 杂性和可判定等基础性问题，而a n t o n i o u 8 i 贝u 提出了语义万维网本体层 之上非单调规则的推理方法。 对于第二类，g i u 舻o 【9 1 和k e m - i s b e r n e r 1 0 1 对描述逻辑8 z o q ) 在概 率方面加以扩展，提出了概率描述逻辑p 跏p q ( d ) 。g i u g n o 采用基于 概率和缺省推理的方法，在d a m l + o i l 中增加了概念之间包含关系的 不确定性( 即在给定个体属于一个概念的情况下，属于另一个概念的 条件概率) ，并将概念之间包含关系的推理归结为求解相应的线性优化 方程。这方面早期工作的代表有h c i n s o h n n 1 和j a e g e r 【嘲，他们都是利用 2 循环规则是指在霍恩规则的规则头( 后件) 和规则体( 前件) 中出现相同的谓词。 3 基原子谓侧是指：该谓诃小出现在任何霉恩规则的后件中，并且不是描述逻辑中的概念和角色。 浙江大学博i 学位论文第一章绪论 概率逻辑的推理方法来扩展描述逻辑4 c 。k o l l e r 则是采用贝叶斯网络 作为概率推理的基础，提出了概率描述逻辑p c l a s s i c ”】。 对于非概率的不确定描述逻辑的研究工作，s t r a c c i a 利用模糊集 ( f u z z ys e t ) 理论对描述逻辑一4 c c 进行了扩展，即个体是否属于某个 概念是模糊的，需要用相应的隶属度函数来描述。s t r a c c i a 明确定义了 模糊描述逻辑的语法和语义，并且提出了类似t a b l e a u 的推理算法1 1 4 i 。 l u k a s i e w i c s 提出了概率描述逻辑程序( p r o b a b i l i s t i cd e s c r i p t i o nl o g i c p r o g r a m s ) 【1 5 】，目的是实现语义万维网逻辑层和证明层的不确定性推理。 l u k a s i e w i c s 把描述逻辑与解集语义( a i l s w e rs e ts e m a n t i c s ) 和独立选择 逻辑( p o o l c si n d e p e n d e n tc h o i c el o g i c ) 【1 矧相结合，并将概率描述逻辑 程序推理归结为计算和求解相应的解集( 即描述逻辑模型) 和线性优 化方程。该方法需要为每一条规则分配一个被选中的概率，然后对各 种规则的可能组合( 称为选择空间) 进行计算，其计算复杂度很高， 且过程不易于被理解，因而难以应用于实际。 1 2 2 信任计算 为了实现语义万维网的设想，适合的信任模型是目前急待解决的 问题。要使用户愿意使用语义万维网中的信息和服务，首先应该让用 户确信这些信息和服务具有一定的可靠性，并且能够为他们带来相应 的方便和利益。信任计算问题实际上是一个不确定性推理的问题，目 前绝大多数信任计算模型都是基于经典概率、模糊集、证据理论、 d c m p s t e r - s h a f e r 等不确定性理论，但这些理论都存在着某些不足。比如 经典概率论中的单侧假设检验，由于确定的拒绝域一般不十分准确， 因此总是会被大量的样本所证实；而对于分布拟合问题，却由于假设 分布不太精确，丙总是被大量的样本所否定。这表明，运用经典的概 率推理，任何合理的模型都会被过于精确的数据所否决。模糊集理论 中的隶属度函数总是假设为已知的，目前尚未形成一致的构造方法， 而且模糊集理论还未被证明具备可计算性，容易产生所谓的“模糊过 语义万维网的不确定知识表示与信任计算第一章绪论 度”的现象。 贝叶斯网络虽然已经有不少成功的应用，但它缺乏模块化组织机 制，对于处理大规模动态的决策问题，其计算上是不可行的。而“置 信度”方法虽然在m y c l n 系统中表现良好，但它存在一些有待解决的 基本理论问题。比如，除非满足必要的独立性条件，一般认为以捌e ) p ( i 研o p ( i e ) ，而“置信度”方法则认为c f ( h , p ) = c f ( h , o c f ( i , p ) 总是成 立的，其中c f 表示c e r t a i n t yf a c t o r 。此外，两个置信度的合并方法是 启发式的，没有相应的数学理论基础。 在安全、金融、电子商务、多a g e n t 系统、认识心理学等领域，已 经对信任问题进行了较为深入的研究，提出了许多观点和模型【1 6 - 2 3 】。 但到目前为止，这些观点和模型仍然没有趋于一致的迹象。现在应用 较广的要属e b a y 和a m a z o n 等在线拍卖系统所使用的信任计算模型了， 这两个系统都实现了一个集中式的打分机制。用户可以对交易对象的 满意度进行打分，并且浏览其他用户的交易评价记录。以e b a y 为例， 商品的拍卖者在每次交易成功之后都会收到一个关于其交易满意度的 回馈，他的信任值是过去六个月这类回馈的简单加和。系统要求用户 在每次交易之后明确表达自己对交易的评价，但由于网络是虚拟的， 无法保证这种回馈能够真实反映交易对象行为的优劣程度。而且这种 方法是完全集中式的，用户无法获取满足其偏好的个性化信任信息。 r a m c h u r n l 2 4 1 运用模糊集合理论瞄1 帮助用户从过去的交互记录中计算 出交易对象的信任值，以此评估可否建立新的交互或进行新的交易。 但是r a m c h u m 的基于模糊集合的信任计算模型过于繁复，每个用户需要 维护一个复杂而庞大的数据结构来储存和计算相关信息，因此难以在 现实中有效应用。此外，该算法无法满足交易社区规模增加时的可扩 展性要求。h u y n h 提出了f i r e 系统脚】，该系统在计算信任度的时候，综 合考虑了历史交互、对象角色、机构认证、过往声誉等信息。但是， 该系统假设a g e n t 在信息交换过程中是完全诚实的，这个假设在现实中 浙江大学博上学位论文第一章绪论 是不成立的。此外，这个系统不具备动态学习能力，