积分商城

最新搜索： 充放电 神经网络 路径规划 变频调速 开关电源EMC LUKOU
您现在的位置是：首页 > 技术资料 > 一种基于近似因子的在线概率知识库推理方法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

一种基于近似因子的在线概率知识库推理方法

更新时间：2019-12-26 14:41:44 大小：878K 上传用户：IC老兵查看TA发布的资源 标签：近似因子 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

概率知识库中的推理技术是近年来的研究热点.目前,大多数系统的推理主要基于批处理的方式实现,并不适用于在线查询场景.对此,提出了一种基于近似因子的在线概率知识库推理方法.它可以重复利用已推断结果计算查询变量的边缘概率.该算法首先提取查询变量的子图(含已推断变量);然后,在此子图上添加近似因子,以模拟子图外其余变量的影响;最后,采用团树算法推断查询变量的边缘概率.实验结果表明:相对于已有算法,该算法可在时间和精度上取得较好的权衡.


部分文件列表

文件名 大小
一种基于近似因子的在线概率知识库推理方法.pdf 878K

部分页面预览

（完整内容请下载后查看）
软件学报ISSN 1000-9825, CODEN RUXUEW  
Journal of Software,2018,29(2):383−395 [doi: 10.13328/j.cnki.jos.005388]  
©中国科学院软件研究所版权所有.  
E-mail:  
Tel: +86-10-62562563  
一种基于近似因子的在线概率知识库推理方法∗  
1,2  
1,2  
1,2  
1,2  
王艳艳  
,
陈
群
,
钟
评
,
李战怀  
1(西北工业大学 计算机学院,陕西 西安 710129)  
2(大数据存储与管理工业和信息化部重点实验室(西北工业大学),陕西 西安 710129)  
通讯作者: 王艳艳, E-mail:  
摘
要: 概率知识库中的推理技术是近年来的研究热点.目前,大多数系统的推理主要基于批处理的方式实现,并  
不适用于在线查询场景.对此,提出了一种基于近似因子的在线概率知识库推理方法.它可以重复利用已推断结果计  
算查询变量的边缘概率.该算法首先提取查询变量的子图(含已推断变量);然后,在此子图上添加近似因子,以模拟子  
图外其余变量的影响;最后,采用团树算法推断查询变量的边缘概率.实验结果表明:相对于已有算法,该算法可在时  
间和精度上取得较好的权衡.  
关键词: 概率知识库;在线推理;近似因子;马尔可夫逻辑网  
中图法分类号: TP181  
中文引用格式: 王艳艳,陈群,钟评,李战怀.一种基于近似因子的在线概率知识库推理方法.软件学报,2018,29(2):383−395.  
英文引用格式: Wang YY, Chen Q, Zhong P, Li ZH. Online inference based on approximate factors for probabilistic knowledge  
bases. Ruan Jian Xue Bao/Journal of Software, 2018,29(2):383−
Online Inference Based on Approximate Factors for Probabilistic Knowledge Bases  
WANG Yan-Yan1,2  
,
CHEN Qun1,2  
,
ZHONG Ping1,2  
,
LI Zhan-Huai1,2  
1(School of Computer Science, Northwestern Polytechnical University, Xi’an 710129, China)  
2(Key Laboratory of Big Data Storage and Management (Northwestern Polytechnical University), Ministry of Industry and Information  
Technology, Xi’an 710129, China)  
Abstract: The inference techniques for probabilistic knowledge bases have recently attracted significant attentions. In most off-the-shelf  
existing systems, the inference is mainly implemented based on batch processing and thus not suited for online querying. This paper  
proposes an online inference approach based on approximate factors for probabilistic knowledge bases, so as to provide a way to reuse  
those inferred results to calculate the marginal probability for the query variable. In this approach, a subgraph is extracted first, taking the  
query variable as center; then some approximate factors are attached to simulate the influences from the variables outside the subgraph;  
and finally, the marginal probability of the query variable is calculated by the clique tree algorithm. Experiments show that compared with  
existing algorithms, the presented approach can achieve a better tradeoff between accuracy and time.  
Key words: probabilistic knowledge base; online inference; approximate factor; Markov logic network  
随着信息提取和数据库管理系统的不断发展,构建大规模知识库已成为工业界和学术界的研究热点,典型  
系统有 Yago[1]、Freebase[2]、Google knowledge graph[3]、DBPedia[4]、NELL[5]等.知识库构建(knowledge base  
construction,简称KBC)的主要过程为:从结构和非结构数据源(比如文本、表格、图片)中获取关系型事实.比如,  
∗ 基金项目: 国家重点研发计划(2016YFB1000703); 国家自然科学基金(61332006, 61732014, 61672432, 61472321, 61502390)  
Foundation item: National Key Research and Development Program of China (2016YFB1000703); National Natural Science  
Foundation of China (61332006, 61732014, 61672432, 61472321, 61502390)  
收稿时间: 2017-04-10; 修改时间: 2017-05-18, 2017-07-28; 采用时间: 2017-09-05; jos 在线出版时间: 2017-12-01  
CNKI 网络优先出版: 2017-12-04 06:46:36, http://kns.cnki.net/kcms/detail/11.2560.TP.20171204.0646.002.html  
384  
Journal of Software 软件学报 Vol.29, No.2, February 2018  
谷歌知识图谱主要从 Freebase、维基百科以及大规模网页内容中抽取知识,到 2016 年底,它已包含 700 亿条实  
体关系.这种以结构化形式存储信息的方式能够促进信息的有效处理和查询.  
然而,由于信息提取算法固有的概率特性和人类知识的局限性,知识库系统通常存在不确定性和不完全性.  
因此,通常需要以概率的方式去推断知识库中的缺失事实.而马尔可夫逻辑网(Markov logic network,简称  
MLN)[6]是将一阶逻辑(first-order logic)和概率图模型(probabilistic graph model)相结合的一种统计关系型模型,  
它可用于处理不确定的规则和事实.于是,基于 MLNs 的概率知识库系统运用而生,典型用例有 Deepdive[7]、  
Elementary[8]、ProbKB[9]等.它们主要采用命题推断的思想,其过程包括两个阶段:1) 实例化(grounding)阶段——  
基于 MLNs 构建因子图;2) 推断(inference)阶段——在因子图上执行边缘推断.在 Inference 阶段,已有的大多数  
概率知识库系统主要采用基于马尔可夫链蒙特卡罗(Markov chain Monte Carlo,简称MCMC)的算法[10](比如吉  
布斯采样)在整个因子图上执行边缘推断(批量式),即计算因子图中每个变量的边缘概率.  
目前,我们正采用MLN 模型构建商品决策支持系统Poolside[11].其主要目标是:为用户提供针对性的推荐服  
务,并可支持含有模糊概念的查询,比如推荐一款性价比高的华为手机.在响应用户的查询时,若采用以上批处  
理的方式执行边缘推断则耗时较多(商品数目通常较多),而且也没有必要(用户并不可能对所有商品都感兴趣).  
尽管基于查询驱动的k-hop 算法[12,13]可加快推理过程,但它很难同时在时间和精度上取得权衡:若跳跃步数k 取  
值较大则精度较高,但推理较慢;若跳跃步数 k 取值较小则推理较快,但精度较差.但事实上,随着用户的不断访  
问,概率知识库中的已推断事实会逐渐增加,若能重复利用它们的推断结果计算其他查询事实的概率,则可在保  
证精度的情况下降低计算量.  
基于以上分析,本文提出了一种基于近似因子的在线推理方法(online inference based on approximate  
factors),记为 OIAF 算法.OIAF 算法主要包括 3 个步骤:子图提取、添加并估算近似因子和边缘推断.其具体过  
程为:首先,从因子图中提取查询变量的子图(含已推断变量);然后,为子图中的已推断变量添加近似因子以模拟  
子图外变量的影响,并基于已推断变量的概率估算近似因子的取值;最后,采用团树算法在含有近似因子的子图  
上执行边缘推断.本文的主要贡献总结如下.  
1) 针对概率知识库的在线查询场景,提出了一种基于近似因子的在线推理算法.它主要利用已推断结果  
计算查询变量的边缘概率.  
2) 在真实和模拟数据集上进行大量实验,进而说明相对于k-hop 算法,OIAF 算法可在时间和精度上取得  
较好的权衡.  
本文第 1 节综述概率知识库推理技术的相关工作.第 2 节介绍概率知识库的背景知识,包括马尔可夫逻辑  
网及其推理过程的两个阶段:Grounding 阶段和 Inference 阶段.第 3 节给出本文的研究问题和相关的符号定义,  
并对 OIAF 算法的工作流程进行介绍.第4 节通过实验说明 OIAF 算法可在时间和精度上取得较好的权衡.第 5  
节对本文内容进行总结.  
1
相关工作  
目前,概率知识库的推理主要基于马尔可夫逻辑网模型,它已广泛应用在社交网络分析(social network  
analysis)[14]、实体解析(entity resolution)[15]、信息提取(information extraction)[16]等领域.MLNs 是将一阶逻辑与  
概率图模型相结合的一种统计关系型模型.它主要包括两种类型的推断方法:命题推断(propositional inference)  
和合一推断(lifted inference).命题推断主要采用概率图模型的推理算法[17],比如置信传播、变分推断以及马尔可  
夫链蒙特卡罗等,其主要思想为:基于 MLNs 构建概率图模型(比如因子图、马尔可夫网),然后采用以上方法执  
行边缘推断.合一推断则基于一阶逻辑推理的思想,主要算法有合一一阶置信传播(lifted first-order belief  
propagation)[18]、加权一阶模型计算(weighted first-order model counting,简称WFOMC)[19]等.相对于合一推断,  
目前,命题推断的应用较为广泛.  
本文主要采用命题推断的思想,其过程主要包括两部分:Grounding 阶段和 Inference 阶段.基于它的概率知  
识库系统主要有 Alchemy[20],Tuffy[21],ProbKB[9],Deepdive[22]等.最初的 Alchemy 系统提出了一系列算法,主要用  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号