OpenKN - 网络大数据时代 的知识计算引擎


30 专题 第 10 卷  第 11 期  2014 年 11 月 个组织建立的知识库多达 50 余种, 相关的应用系统更是达到了上百 种。其中,有代表性的知识库或 应用系统有 KnowItAll[3], TextRun- ner[4], NELL[5], Probase[6], Satori [7], PROSPERA[8], SOFIE[9] 以及一些 基于维基百科等在线百科知识构 建的知识库 DBpedia[10], YAGO[11], Omega[12], WikiTaxonomy[13]。除此 之外,一些著名的商业网站、公 司和政府也发布了类似的知识 搜索和计算平台,如 Evi 公司的 TrueKnowledge 知识搜索平台 2、 美国官方政府网站 Data.gov, Wol- fram 的知识计算平台 WolframAl- pha、谷歌的知识图谱 Knowledge Graph、脸书 (Facebook) 推出的实 体搜索服务 Graph Search 等。 就规模而言,拥有概念最多 的知识库是 Probase,目前其核心 概念约有 270 万个,概念总量达到 千万级。它是基于概率化构建的 知识库,支持针对短文本的语义 理解。包含实体最多的是 Wolfra- mAlpha,有10万亿个实体。近年来, 影响力比较大的知识库或知识搜 索服务有谷歌的知识图谱,包含 5 亿个实体对象和 350 亿条实体 间的关系信息,而且规模也在随 着信息的增长不断增大。除此之 外,比较有特色的还有国内搜狗 知立方系统,侧重于基于图的逻 辑推理计算,包括利用语义网的 三元组推理补充实体数据、对用 户查询词进行语义理解以及句法 分析等。 本文将提出一种面向网络大 数据的、开放的、自适应的、可演 化的、可计算的知识计算引擎—— OpenKN。 OpenKN的整体架构 图 1 描述了 OpenKN 作为计 近年来,互联网技术和应用 模式的快速发展在改变人们生活 方式的同时也产生了巨大的数据 资源。预计到 2020 年,全球的数 据总 量 将 达 到 35ZB(1ZB=270B), 其 中 75% 来自个 人(主 要是图 片、视频和音乐),远远超过人类 有史以来所有印刷材料的数据总 量 (200PB1)。随着互联网、物联网、 云计算等技术的迅猛发展,网络 空间 (cyberspace) 中各类应用层出 不穷,引发了数据规模的爆炸式 增长,形成了网络空间的大数据(简 称网络大数据)[1]。 网络大数据中包含大量有价 值的数据,根据其产生方式的不 同可分为 Web 内容数据、Web 结 构数据、自媒体数据、日志数据等。 如何从网络大数据中获得有价值 的知识,并对其进行深入的计算 和分析,已成为国内外工业界和学 术界研究的热点 [2]。目前,世界各 王元卓1 贾岩涛1 赵泽亚2 程学旗1 1中国科学院计算技术研究所 2信息工程大学 OpenKN——网络大数据时代 的知识计算引擎 关键词 :网络大数据 知识计算 知识网络 1 1PB=250B。 2 http://www.evi.com。 31 第 10 卷  第 11 期  2014 年 11 月 算引擎的主要架构。OpenKN 主 要由知识库构建 (knowledge base construction)、知识验证与计算 (knowledge validation and verifi- cation, knowledge computation)、 知 识存储 (knowledge repositories)、知识 服务与应用 (knowl- edge services and application)4 个模块 组成。这些模块实 现了一个全生命周 期的知识处理,从 知识获取、知识融 合、知识验证与计 算、知识存储到知 识服务与应用的知 识处理工作流程。 知识库的构 建 知识库的构建 从逻辑角度讲,包 括知识获取和知识 融合两个方面。其 中知识获取的主要 目的是从开放网页、 在线百科和核心词 表等数据中抽取概念、实例、属 性和关系。知识融合的主要目的 是实现知识的时序融合和多数据 源融合。图 2 进一步描述了知识 库构建的思路。OpenKN 构建的 知识库包含两部分 :(1) 存储众所 周知的常识性知识的通用基础库 (general foundation base),这些知 识可从维基百科等在线百科中直 接抽取获得。(2) 特定领域的知识 库,从左至右依次为领域 1 到领 域 n。基于每一个领域知识的特 点不同,每一个特定领域知识库 又可进一步划分为三部分 :导出 的通用基础库 (induced GFB)、领 域基础库 (domain foundation base) 和领域网络库 (domain Web base)。 具体地讲,导出的通用基础库是 指从常识知识中选取的和领域相 关的知识构成的知识库。领域基 础库是用来描述领域相关的其他 基本知识。领域基础库中的知识 主要来自领域字典、核心词汇表等。 为了获取当前最新最实时的领域 知识,领域网络库用来从开放的 互联网网页中抽取领域相关的最 新知识。在图 2 中,橙色点和黑色 点代表从网页中抽取获得的知识, 点之间的边代表知识间的关联关 系。随着网页数量的不断增加和内 容的不断更新,领域知识库可实 现自适应增长 (self-grew)[14]。上述 这些知识库的构建共同完成知识 获取的全过程。此外,我们利用 已有的公开知识库,如 Freebase, YAGO 等实现了知识融合。在完 成 OpenKN 的知识库构建工作后, 我们得到的知识称为显式的知识。图2 知识库构建 融合 融合 知识融合 知识构建领域1 领域n 网页 领域网络库 领域网络库 领域基础库 领域基础库 来源 来源 领域核心词表等 自适应 增长 自适应 增长 知识 来源 在线百科等 通用基础库 导出的通用 基础库 导出的通用 基础库 图1 OpenKN架构 知识服务与应用 知识推理 语义搜索 个性化推荐 知识问答 知识 存储 显式知识存储:GDB 隐式知识存储: 关系数据库 知识计算 属性计算 关系计算 实例计算 隐式知识 显式知识 知识验证与确认 专家 知识库构建 知识融合 时序融合 多源融合 实体链接 本体扩充 实例匹配 概念对齐 概念 关系 实例 基于实体的爬取和抽取 网页 在线百科 核心词汇 知识获取 32 专题 第 10 卷  第 11 期  2014 年 11 月 图数据模型来存储知识,这里的点 和边都有各自唯一的 ID 并且支持 一系列的多值属性。GDB 描述了 一个与现有的图模型不同的异构网 络,称为可演化知识网络。 OpenKN 的 两 个 主 要 特 征——自适应性和可演化性,加 在一起诠释了 OpenKN 的“Open” 的含义。 OpenKN的自适应性 OpenKN 的自适应性主要体 现在自适应知识演化处理和自适 应知识获取策略两个方面。 如图 3 所示,自适应知识演 化处理用来描述知识演化的规律, 它分为知识库的自我更新和与其 他知识库的句法——语义级融合 两个阶段。在自我更新阶段,知识 演化通过作用在知识库上的两个 基本运算和一系列的规则完成,即 知识计算 除了显式的知 识,通过 OpenKN 的知识计算功 能,包括属性计算、关系计算 [15,16]、 实例计算等,我们还可以进一步 获得隐式的或推断的知识。 知识验证与处理 为了检 验显式知识和隐式知识的完备性、 相关性与一致性,我们需要对知 识进行校验,这称为知识验证过 程。主要是专家或特定的知识计 算方法检查冗余的、冲突的、矛 盾的或者不完整的知识。 知识存储 经过验证的海量 知识,在 OpenKN 里存储在一个 基于图的数据库 (Graph DataBase, GDB) 以及关系数据库中。其中, GDB 中存储的是显式的知识,关 系数据库中存储的是隐式的知识。 GDB 作为大数据存储基础设施, 支持大于 100 亿条知识的存储。与 传统的数据库模型(如 Neo4j, Ti- tan)相比,GDB 通过定义点和边的 逻辑加⊕和逻辑乘⊙运算,以及一 系列基本的规则。这些规则被用 于本源知识库 (primitive KB) 上的 演化。这里的本源知识库定义为 不可以被其他知识库通过逻辑加 和逻辑乘来表示的知识库。如果 我们把所有知识库组成的集合定 义为一个向量空间,那么根据线性 代数的基本知识,这些本源知识库 实际上构成了该线性空间的一组 基。对于向量空间的若干术语,可 参考文献 [17]。另一方面,对于两 个不同知识库的融合可分为两个 操作,语义级的融合 S⊕和句法级 的融合 T⊕。 自适应知识获取策略的主要 目的是获取随时空演化的动态知 识。如图 3 所示,自适应知识获 取策略使用一个称为过滤器的组 件来产生句法——语义级的抽取 模板,例如 Such-As, Is-A,来对网 络数据进行知识抽取。过滤器由 规则和新数据感知器组成,其中 规则保证不同类型的知识库中抽 取得到知识的一致性,新数据感 知器主要用于检测是否有新的数 据产生以动态调整我们的抽取策 略。抽取模板的调整是通过其自 适应的调整和与抽取结果的反馈 来迭代实现的。在自适应调整阶段, 例如当 Such-As 模板遇到例外情 况时,如句子“animals other than dogs such as cats” ,它不仅可以从 概率的角度发现这个特例,还可以 通过模糊本体技术来识别这种情 况,相关术语可参考文献 [18]。在 抽取结果的反馈阶段,抽取模板 通过抽取结果的正确性进行打分, 图3 OpenKN的自适应性 自适应知识演化处理 自我更新 融合 更新后的 本源知识库 更新后的 本源知识库 更新后的 本源知识库 本源 知识库 本源 知识库 本源 知识库 基本规则 基本规则 分解 OpenKN的知识库 自适应知识获取策略 句法级 融合 语义级 融合 知识库 知识库 知识库 1 知识库 2 知识库 n 网络 大数据 规则 模式抽取 抽取结果 输入 产生 输出 自适应过滤器 新数据感知器 外部校正 33 第 10 卷  第 11 期  2014 年 11 月 证了知识的实时更新。 OpenKN的演化计算 为了证明 OpenKN 的可演化 性特征,我们首先引入可演化知 识网络这一知识表示模型。这一 表示模型也是知识存储设施 GDB 搭建的基础。 可演化知识网络 这里的可演化知识网络是每 一个点和边上的带有时空信息和一 系列演化函数或算子的异构网络。 更准确地讲,给定时间信息集合T 和空间信息集合S,点的类型集合 A,边的类型集合R,可演化知识 网络 GT, S 可定义为如下的 8 元组: , ( , , , , , , , )φ ϕ θ τ λ η=T SG V E 其 中,V 是 点的 集 合;E 是 有向边的集合,即一系列关系对 u,v V r R :V A(u, v, r) , u,v V r R :V A(u, v, r) , u,v V r R :V A(u, v, r) , 即 每 对点都被赋予了一个或多个关系; u,v V r R :V A(u, v, r) 是一个定义在点集上的映 射函数,表示在点集合中,每个顶 点通过该计算函数可得到唯一的顶 点类型 ( )v A : E R是一个 关系映射函数,使得每对点之间的 关系类型最多有| |R 个。 : 2TVθ → 是定义在点上的时间映射函数,用 于计算特定点的时间戳进而描述点 的生命周期。这里 2T 是集合T 的幂 集; : 2TEτ → 是定义在边上的时 间映射函数,返回某一指定边的时 间戳用来描述该边存在的时间信 息; : 2SVλ → 是定义在点上的空 间信息映射函数,返回某一指定点 图4 可演化知识网络 图5 可演化知识网络的更新 可演化知识网络 新的网络 更新结果 链接 作用 图6 可演化知识网络融合其他知识库 转换 链接与作用 转换后的知识网络 可演化知识网络 更新结果 知识库 实现所谓的外部校正。 OpenKN的自适应性可以有效 地满足网络大数据的快速变化带 来的挑战。一方面,它可以使知识 库具有捕获新数据的能力,另一 方面,不同的规则如基本规则,保 34 专题 第 10 卷  第 11 期  2014 年 11 月 的空间信息用来描述该点活动的空 间信息; : 2SEη → 是定义在边上 的空间映射函数,返回某一指定边 的空间信息,来描述该边存在的空 间信息。在可演化知识网络中,我 们记录下了点和边的时空信息。需 要指出的是,OpenKN 也可用于构 建特殊领域的知识库,其构建方法 与上述方法相同,此时定义中的点 类型映射函数φ 与边类型映射函数 都是依赖于领域的。 以学术领域为例,我们构建 了一个面向学术圈的可演化知识 网络:在此网络中,点的类型可定 义为作者 (A)、文章 (P)、会议 (C)、 组织 (O) 和关键词 (K) 五类;边的 类型包括作者间的合作关系和论 文间的引用关系等。此外,每一个 点都包含相应的时空信息,例如 出生日期、出生地、归属地、毕业 时间等。边也包含相应的时空信 息,例如两个作者合作的年份、合 作地点等。在图 4 中,我们以可 演化知识网络中的一小部分作为 例子进行阐述。此网络包含点集 { , , , , , , , , , , , , , }V a b c d e f g h i j k l m n= , 时 间 集 合 1 23456{ , , , , , }T t t t t t t= , 空 间 集 合 1 2345{ , , , , }S s s s s s= 。 图 4 的 右 侧 是 一 些 函 数 以 及 相 应 的 函 数 值, 例 如 等 式 { , , }a b coauthor coauthorψ = 表 示 两个点 a, b 之间存在合作关系; 等 式 ( )a Aφ = 表 示 点 a, b的 类 型 是 A ;等 式 1 2( ) { , }a t tθ = 和 1 3( ) { , }a s sλ = 分 别 表 示 在 点 a, b 上的时间和 空间映 射 函 数 值 ; 等 式 1 4{ , , } { , }a b coauthor t tτ = 和 2{ , , } { }a b coauthor sη = 分别表示在 边( , , )a b coauthor 上的时间和空间 映射函数值。 OpenKN 之所以称为可演化知 识网络,主要是因为:一方面网络 可以不断获取最新的知识,并进行 自我更新;另一方面,知识网络可 以将其他知识库中的知识转化为 自己可以利用的标准形式,吸纳到 自身的知识网络中进而形成新的知 识网络。这两个过程如图 5 和图 6 所示。在图 5 中,最左侧的网络是 一个确定的可演化知识网络,当从 网页中获取了新的知识后,可以通 过两个步骤将新知识融合到现有 的网络中。首先,将新知识表示为 一个知识网络,并将其与现有网络 进行“链接”。其次,将新的知识 网络中的点和边与已有网络中的相 应的点和边进行“作用”,最终形 成一个网络。在图 6 中,现有的知 识库先转化为一个知识网络,然后 如图 5 所示,和已有的知识网络进 行融合。 可演化知识网络的演化特性 构成一个完整的演化周期 [19],包 括演化识别与感知、演化定位、 演化评估和管理等阶段。这种演 化的非刚性同时保证了网络的时 新性。 演化计算算子库 OpenKN 的演化计算可规范 化为两类不同的算子或操作,即对 点的操作和对边的操作。具体地讲, 对点的操作单元可分为点的抽取、 点的融合以及点的推理三个子操 作,对边的操作也可分为相应的三 个类似的子操作,即关系抽取、关 系融合、关系推断。这里提到的所 有操作均涉及到对点和边上的时间 与空间信息的操作,并且这些操作 与前文提到的自适应知识演化过程 和自适应知识获取策略是一致的。 即点和边的抽取实现了自适应知识 获取,其他操作构成了自适应知识 演化过程。OpenKN 的演化计算算 子库首次将知识获取的整个流程 中涉及的方法纳入到一个体系当 中,便于深入理解每个方法之间的 关系,为不同的方法及其之间的衔 接与相互作用提供了一个全面的 视角。 目前,OpenKN 这一知识计算 引擎能够处理的点规模达到 3000 万,边的规模达到 10 亿级,同时 处理规模仍在不断扩张中。 总结 网络大数据具有多源异构性、 时效性、高噪声等特点,不但非 结构化数据多,而且数据的实时 性强。网络大数据背后蕴含着丰 富的、复杂关联的知识。要有效 利用网络大数据的价值就须进行 数据的去冗分类、去粗取精,从 数据中挖掘知识, 对大数据网络背 后的知识进行深入分析。本文提 出了一种面向网络大数据的知识 计算引擎——OpenKN。它的主要 特点是自适应性和可演化性。这使 得 OpenKN 可以更好地感知动态 变化的网络知识,同时对潜在的和 变化的时序知识进行推断和预测, 更好地为网络大数据下的知识挖 掘提供服务。■ 35 第 10 卷  第 11 期  2014 年 11 月 贾岩涛 CCF会员。中科院 计算所助理研究 员。主要研究方向 为知识计算、数据 挖掘、组合优化。 jiayantao@ict.ac.cn 参考文献 [1] 王元卓,靳小龙,程学旗. 网络大 数据:现状与挑战.计算机学 报, 2013;36(6): 1~15. [2] 王元卓,贾岩涛,刘大伟等.基于开 放网络知识的信息检索与数据 挖掘.计算机研究与发展. 2014. [3] Etzioni O, Cafarella M, Downey D, et al. Web-scale information e x t r a c t i o n i n k n o w i t a l l: (preliminary results)[C]. Proc of the 13th Int Conf on World Wide Web. New York: ACM, 2004:100~110. [4] B a n k o M, C a f a r e l l a M J, S o d e r l a n d S, e t a l. O p e n information extraction from 王元卓 CCF高级会员。中 科院计算所副研究 员。主要研究方向 为网络大数据知识 计算、社会计算等。 wangyuanzhuo@ict. ac.cn 赵泽亚 信息工程大学研究 生。主要研究方向 为知识工程和数 据挖掘。zhaozeya@ software.ict.ac.cn the web[C]. Proc of the 20th Int Joint Conf on Artifical Intelligence, IJCAI’07. New York: ACM, 2007:2670~2676. [5] Carlson A, Betteridge J, Kisiel B, et al. Toward an architecture for never ending language learning[C]. Proc of the 24th AAAI Conf on Artifical Intelligence. Menlo Park, CA: AAAI Press, 2010:1306~1313. [6] Wu W, Li H, Wang H, et al. Probase: A probabilistic taxonomy for text understanding[C]. Proc of the 2012 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2012:481~492. [7] Gallagher S. How Google and Microsoft taught search to understand the Web. 2012[2013- 07-25]. http://arstechnica.com/ information-technology/2012/06/ inside-the-architecture-of- googles-knowledge-graphand- microsofts-satori/. [8] Nakashole N, Theobald M, Weikum G . Scalable knowledge harvesting with high precision and high recall[C]. Proc of the 4th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2011:227~236. [9] Suchanek F M, Sozio M,Weikum G . SOFIE: A self-organizing framework for information extraction[C] . Proc of the 18th Int Conf on World Wide Web. New York: ACM, 2009:631~640. [10] Auer S, Bizer C, Kobilarov G, et al. DBpedia: A nucleus for a Web of open data[C]. Proc of the 6th Int the Semantic Web and 2nd Asian Conf on Asian Semantic Web Conf, ISWC’07. Piscataway, NJ: IEEE, 2007:722~735. [11] Biega J, Kuzey E, Suchanek F M. Inside YAGO2s: A transparent i n f o r m a t i o n e x t r a c t i o n architecture[C]. Proc of the 22th Int Conf on World Wide Web. New York: ACM, 2013:325~328. [12] Philpot A, Hovy E H, Pantel P. Ontology and the lexicon [M]. The Omega Ontology. C a m b r i d g e: C a m b r i d g e University Press, 2008 35~78. [13] Ponzetto S, Navigli R. Large- scale taxonomy mapping for restructuring and integrating wikipedia[C]. Proc of the 21st Int Joint Conf on Artifical I n t e l l i g e n c e, I J C A I ’09 . S a n F r a n c i s c o: M o r g a n Kaufmann,2009:2083~2088. [14] H a i l u n L i n, Ya n t a o J i a, Yuanzhuo Wang, and et al.. Populating Knowledge Base with Collective Entity Mentions: A Graph-based Approach. IEEE/ ACM International Conference o n A d v a n c e s i n S o c i a l Network Analysis and Mining (ASONAM) 2014. [15] Yantao Jia, Yuanzhuo Wang, X u e q i C h e n g,a n d e t a l.. OpenKN: An Open Knowledge Computational Engine for Network Big Data. IEEE/ ACM International Conference o n A d v a n c e s i n S o c i a l Network Analysis and Mining (ASONAM) 2014. [16] Zeya Zhao, Yantao Jia and Yuanzhuo Wang. Content- Structural Relation Inference in Knowledge Base.AAAI2014. [17] D. C. Lay. Linear algebra and its applications,1997. [18] Y. Cai, C.-m. A. Yeung, and H.- f. Leung.Fuzzy computational ontologies in contexts. 2012. [19] F. Zablith, G. Antoniou, M. d’Aquin, and et al..Ontology evolution: a process-centric s u r v e y. T h e K n o w l e d g e Engineering Review, 2013:1~31. 程学旗 CCF杰出会员、杰出 演讲者。中科院计算 所研究员。主要研究 方向为网络科学、网 络与信息安全以及 互联网搜索与服务。 cxq@ict.ac.cn
还剩5页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

gbxd

贡献于2015-01-23

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf