张香玲(1983-),女,山东滨州人,博士生,CCF学生会员,主要研究领域为实体检索,知识补全
陈跃国(1978-),男,博士,副教授,博士生导师,CCF高级会员,主要研究领域为交互式大数据分析,实体搜索;
马登豪(1989-),男,博士生,主要研究领域为信息检索,实体搜索
陈峻(1991-),男,博士生,CCF学生会员,主要研究领域为探索式搜索,信息检索,大数据管理
杜小勇(1963-),男,博士,教授,博士生导师,CCF会士,主要研究领域为数据库系统,智能信息检索
与传统的以网页页面集合的方式呈现搜索结果不同,实体搜索的结果是实体或实体集合,其优点是无需用户在纷杂的网页里面进行二次查找,更能提升用户的搜索体验.实体搜索的任务可以分为相关实体搜索和相似实体搜索.对近年来这两类任务的实体搜索技术进行综述.首先给出了实体搜索的形式化定义,并介绍了常用的评测指标;然后,对两种不同形式的实体搜索任务在两类数据源(非结构化数据集和结构化数据集)上的主要研究方法进行了详细的阐述和对比;最后,对未来的研究内容和发展方向进行了探讨和展望.
Entity search differs from traditional search engines in that the results of traditional search engines are Web pages, whereas the results of entity search are entities which can enhance the user's search experience. Entity search can be further categorized into the task of related entity search and the task of similar entity search. In this paper, a survey is presented on the techniques of entity search. Firstly, entity search is defined formally, and frequently used evaluation measures are introduced as well. Secondly, the algorithms of the two different types of entity search on two different data sources (unstructured data and structured data) are reviewed in details. Finally, open research issues and possible future research directions are discussed.
关键字搜索是当前搜索引擎所采用的主流搜索技术, 是一种存在性搜索技术, 返回给用户包含关键字的网页列表, 用户往往需要进一步浏览这些网页并且过滤掉大量无用信息才能找到真正想要的结果.这个过程信息消费代价高, 显著降低了用户体验, 用户更希望能够直接得到答案.比如, 查询“贝拉克·奥巴马的妻子是谁”, 用户希望搜索结果是简洁的信息条目“米歇尔·奥巴马”, 而不是大量的网页, 这种搜索就是实体搜索(entity search).实体搜索的显著特点就是直接给出答案, 它关注的是对象, 对象可以是各种不同的类别, 比如人、电影、公司、小说等.例如:查询“贝拉克·奥巴马的妻子”希望得到的就是类别为“人”的具体实体;而查询“汤姆·汉克斯主演的电影”, 希望得到的是类别为“电影”的实体列表.文献[
为了推动实体搜索任务的研究, 一些知名的信息检索竞赛也都出现了实体搜索任务.INEX(initiative for evaluation of XML retrieval)从2007年开始便有了实体搜索的任务(INEX-XER)[
实体搜索示例
An example of entity search
本文第1节总体概述实体搜索的定义、任务分类及常用的评测指标.第2节对相关实体搜索技术在非结构化数据集和结构化数据集上的研究进展进行分类、对比和总结.第3节对相似实体搜索技术在两种不同数据集上的研究进展进行综述.第4节是对全文的总结及未来研究工作的展望.
本节首先给出与实体搜索相关的几个术语, 然后对实体搜索流程做了简单介绍, 同时对实体搜索任务及相关的研究方法做了分类综述.
●
实体(entity):指现实或虚拟世界中具有特定语义的任何对象或者概念都可以看做是实体, 用符号
● 实体类别(entity class):每个实体都有对应的类别信息, 比如实体“北京”是“地方”“城市”.类别体系构成一个层次结构, 比如:“机构”是一种类别, 机构又包括“公司”“学校”“党派”等不同类别;
● 实体关系(entity relation):表示实体之间的关系, 比如“贝拉克·奥巴马”和“米歇尔·奥巴马”两个实体之间的关系为“夫妻”;
●
实体搜索(entity search):指根据实体与给定查询的相关性或相似性对实体做排序, 形式化定义为四元组{
(1)
(2)
(3)
(4)
实体搜索一般由3个步骤组成, 基本流程如
实体搜索流程图
Process of entity search
在检索开始之前, 首先需要对用于支持查询的数据集(非结构化的文档/网页集合, 或者是结构化的数据)进行处理.在用户将查询提交到检索系统后, 检索系统首先对查询做解析, 然后, 系统根据对数据集预先建立的索引实现对与查询相关数据的快速检索.如果数据集为非结构化的文档/网页集合, 则经过检索系统后, 输出相关文档集, 然后在相关文档集中做实体检索, 从中抽取出候选实体.在将结果提交给用户之前, 根据候选实体与查询的相关度或相似度对结果进行排序.
实体搜索大致可以分为两类(见
实体搜索任务分类
Classification of entity search
实体搜索任务 | 查询 | 查询意图 | 查询示例 | 查询示例结果 |
相关实体搜索 | 关键词或自然 语言描述的查询 | 单个/ 多个实体 | “贝拉克·奥巴马的妻子” | “米歇尔·奥巴马” |
“美国历任总统” | “贝拉克·奥巴马, 乔治·沃克·布什, 威廉·杰斐逊·克林顿...” | |||
相似实体搜索 | 实体或实体集合 | 多个实体 | “贝拉克·奥巴马, 乔治·沃克·布什, 威廉·杰斐逊·克林顿” | “约翰·肯尼迪, 罗纳德·威尔逊·里根...” |
● 第1类是相关实体搜索, 输入是各种关键词或者自然语言描述的查询.根据问题答案的实体数目, 相关实体搜索又可以分为:单实体搜索, 即答案是一个实体, 比如“贝拉克·奥巴马的妻子是谁”, 此类查询更加关注第1个结果的准确率;多实体搜索, 答案是多个实体, 比如“美国历任总统”, 此类查询除了关注准确率之外, 还需要关注召回率.单实体搜索和多实体搜索在技术实现上没有太多区分, 可将单实体搜索看做是多实体搜索的一个特例;
●
第2类是相似实体搜索, 输入是几个实体, 以这几个实体为例, 搜索出与其具有相同语义的其他实体, 在INEX[
虽然实体搜索没有限定数据源, 但在实际应用中, 根据采用的技术需要预先选定数据源.实体搜索的数据源包括非结构化网页/文档数据和结构化数据, 不同数据源在做实体搜索时处理方法也有所不同.本文从实体搜索不同的任务和所使用不同数据源的角度对研究方法做了归类, 如
相关实体搜索研究框图
Classification of studies on related entity search
相似实体搜索研究框图
Classification of studies on similar entity search
实体搜索离不开丰富的数据源.近年来, 随着互联网的快速发展, 文本、视频、语音等非结构化数据大量涌现.同时, 随着开放链接数据(linked open data, 简称LOD)[
(1) 非结构化数据集
目前, 已有的工作主要是在网页或者非结构化文本数据集上进行搜索, 基本思想都是使用文档作为一个承载实体的桥梁, 将查询与候选实体连接起来.分别计算查询与文档的关联性、文档与实体的关联性, 或者说是文档刻画实体的程度.文献[
基于实体生成文档的模型
Candidate entity generation model
基于文档的模型
Document generation model
很多非结构化的网页本身就是关于实体的描述信息, 比如:Wikipedia的每个网页都是对一个实体的描述; IMDB的每个页面也都是对一个电影的介绍;Amazon的每个页面都是与某个产品相关的信息.所以, 利用非结构化网页来做实体搜索是可行的.
(2) 结构化数据集
随着LOD等项目的全面展开, 语义网数据源的数量激增, 大量RDF(resource description framework)数据被发布.互联网正从仅包含网页和网页之间超链接的文档万维网(Web of document), 转变成包含大量描述各种实体和实体之间丰富关系的数据万维网(Web of data).
RDF(资源描述框架)是由W3C提出的一种简单、灵活的描述语义网的数据模型, 它用来描述实体的信息(属性及对应的属性值)以及实体和实体之间的关系[
结构化数据集上的实体搜索技术主要是利用了数据集的结构化特征, 知识是通过实体及其复杂的语义关系来表达, 这样的表达方式更便于对知识的深度理解, 可以支持将传统搜索引擎中基于关键字的搜索提升到知识理解的层次.
(3) 小结
本节主要对两类数据集做了介绍, 其中:基于非结构化数据集的方法主要是利用了同查询语句中词语的共现统计信息来查找实体, 而不关注实体之间丰富的语义信息;利用结构化数据集的方法虽然充分利用了结构化数据集上丰富的语义信息, 但是相对于网页来说存在知识欠缺问题, 包括知识库中缺少新产生的实体, 实体之间的关系也没有非结构化数据集上丰富.
代表性数据集
Representative datasets
数据集 | 特点 | 规模 | 数据形式 | 网址 |
Wikipedia | 基于维基技术的 多语言网络百科全书 | 51G的 数据规模 | 非结构化 网页数据 | https://dumps.wikimedia.org/]]> |
ClueWeb12 | 在2012年的2月和5月期间 爬取的网页, 被多次用于TREC竞赛作为数据集 | 7亿3千3百万 英文网页 | 非结构化 网页数据 | http://www.lemurproject.org/clueweb12.php/]]> |
DBpedia | 基于Wikipedia生成的知识库 | 600万实体 95亿条三元组 | 三元组 | http://wiki.dbpedia.org/]]> |
Freebase | 开放的、协作创建的 结构化知识库 | 19亿条三元组 2300万实体 | 三元组 | https://developers.google.com/freebase/]]> |
Wikidata | 与DBpedia不同, Wikidata不仅 提供在线浏览, 而且任何人都 可以对词条进行编辑 | 1500万实体 4300万条三元组 | 三元组 | https://www.wikidata.org/]]> |
YAGO | 基于GeoNames, WordNet以及Wikipedia开发的知识库 | 1亿两千万条三元组 1千万实体 | 三元组 | http://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/]]> |
Probase | 由网页抽取构建的概率知识库 | 5百万个类别 1255万实体 | 三元组 | https://www.microsoft.com/en-us/research/project/probase/]]> |
本节综合了信息检索领域中几个竞赛, 包括INEX[
● Precision@
● MRR:对于某些IR系统, 比如问答系统, 只关心第1个正确结果的位置, 越靠前越好, 第1个正确结果所在位置的倒数称为RR.对所有查询的RR求平均, 得到MRR;
● MAP:其中, AP表示平均正确率, 对不同召回率上的正确率进行平均.AP是对单一查询而言, 对所有查询的AP值进行算术平均, 得到MAP;
● R-Pre:R-Precision表示检索结果中, 在所有相关文档总数位置上的准确率.如某个查询的相关文档总数为80, 则计算检索结果在前80篇文档中的准确率;
● NDCG(normalized discounted cumulative gain):最早在文献[
● xinfAP:在文献[
本节将对上文中提到的实体搜索相关的几个评测集作介绍, 包括评测集的特点、所使用数据集、评测指标并且给出了查询示例, 见
代表性评测集
Representative testsets
评测集 | 介绍 | 数据集 | 评测指标 | 查询示例 |
INEX-XER | 2009年INEX实体搜索 竞赛, 返回实体列表 | Wikipedia | MAP/xinfAP/P@n | US presidents since 1960 |
TREC entity | TREC2009实体搜索任务, 关注相关实体搜索 | ClueWeb09 | NDCG/P@n | Airlines that currently use Boeing 747 planes |
SemSearch LS | 返回实体列表 | BTC-2009 | MAP/R-pre/P@n | Axis powers of World War Ⅱ |
QALD | 基于链接数据的问答评测 | DBpedia | Recall/Precision/F-measure | Who is the major of Berlin? |
INEX-LD | INEX 2012年开始出现 基于链接数据的实体搜索, 查询使用关键词的形式 | Wikipedia | Precision/Recall/AP/MAP/ P@n/MRR/NDCG | England football player highest paid |
相关实体搜索的目的是检索出与查询相关的实体.用户的输入一般是包含关键词的自然语言描述的查询语句[
在非结构化数据集上的相关实体搜索方法主要包括概率语言模型、机器学习方法、基于链接的方法.这些方法都是将文档看做是连接查询与实体的桥梁, 在下文中, 将依次对各类方法做介绍.
概率语言模型可以分为3类:一类是计算由查询生成候选实体的概率模型, 即查询似然模型;另一类是由候选实体生成查询的概率模型, 也称为查询生成概率模型或者称为实体似然模型;第三类就是分别将查询与文档建模, 然后比较两个模型概率分布的相似性.
(1) 查询似然概率语言模型
先从标准语言模型[
其中,
如上介绍了标准语言模型, 在实体搜索中, 文档集可以直接使用Wikipedia, 每个实体本身就对应一个页面, 页面的信息就是描述该实体.也可以在文档中根据每个实体的上下文为实体创建生成文件.文献[
其中,
(2) 查询生成概率语言模型
查询生成概率语言模型是计算由候选实体生成查询的概率, 又称为话题生成式模型, 把查询看作是一个话题, 计算由候选实体生成查询的概率
根据计算概率
●
一类是候选模型, 建立实体
● 另外一类称为文档模型, 不对实体构造语言模型, 而是直接计算:
其中,
上述两类生成式概率语言模型是基于候选实体和查询关键词分布是条件独立的, 而且查询关键词和候选实体在文档中的语义关系也是忽略的.在文献[
(3) 扩展的概率语言模型
如上介绍的都是单方向的通过文档语言模型生成查询的概率, 或者考虑查询语言模型生成文档的概率.另外一种做法不是从单方向来直接生成对象, 而是查询和文档同时生成语言模型, 然后比较这两个模型之间的差别.文献[
概率语言模型建模的
Probabilistic language modelings
(4) 模型比较
生成式模型是从统计的角度来表示数据分布, 充分利用先验知识.Lafferty和Zhai在文献[
近年来, Learning to Rank(L2R)被广泛应用于文档排序, Liu在文献[
文献[
Macdonald和Ounis提出一种有监督集成学习方法[
基于链接的模型最早是应用于网页检索, 其中, PageRank[
实体搜索可以看做是这样一个过程:随机选择一个文档或者候选实体;待浏览文档结束后, 可能会跳转到文档中涉及到的某个实体或者与这个文档相关的其他文档;待浏览实体结束后, 跳转到提及该实体的其他文档或者与这个实体相关的其他实体.这个过程与随机游走很类似.Serdyukov等人在文献[
在结构化数据集上, 相关实体搜索方法包括概率语言模型方法和基于链接的模型..
在结构化数据集上使用概率语言模型, 首先要为每个实体创建生成文档.文献[
以文献[
贝拉克·奥巴马在知识库中的知识片段
Knowledge fragment of Barack Obama
●
一种是只使用与该实体存在联系的实体, 不关心他们之间的关系(谓词)类型, 称为无结构的实体模型, 此种模型的生成文档见
无结构的实体模型示例
An example of unstructured entity model
实体生成文档 |
贝拉克·奥巴马 |
●
另外一类是将谓词分为4类:Name(表示实体的名称)、Attributes(表示实体具有的属性值, 即实体通过该谓词对应的宾语为值, 而不是实体)、OutRelations(表示实体出边指向的实体)、InRelations(表示实体入边指向的实体), 此类称为结构化实体模型, 此种模型的生成文档见
结构和层次实体模型示例
An example of structured entity model
结构的实体模型 | 层次实体模型 | |||
谓词类型 | 值 | 谓词类型 | 值 | |
谓词 | 谓词对应的值 | |||
Name | 贝拉克·奥巴马 | Name | 名字 | 贝拉克·奥巴马 |
属性 | 贝拉克·侯赛因·奥巴马(Barack Hussein Obama), 1961年8月4日出生, 美国 民主党籍政治家, 第44任美国总统... 1961年8月4日 | 属性 | 摘要 | 贝拉克·侯赛因·奥巴马(Barack Hussein Obama), 1961年8月4日出生, 美国 民主党籍政治家, 第44任美国总统... |
出生日期 | 1961年8月4日 | |||
OutRelations | 美国 夏威夷州-檀香山 哈佛大学 | OutRelations | 国籍 | 美国 |
出生地 | 夏威夷州-檀香山 | |||
毕业学校 | 哈佛大学 | |||
InRelations | 我相信变革 我父亲的梦想 | InRelations | 作者 | 我相信变革 |
作者 | 我父亲的梦想 |
在2010年和2011年的SemSearch竞赛测试集, 基于Billion Triple Challenge2009数据集, 非结构实体模型2010年的MAP最高是0.212 5, NDCG为0.384 8;2011年MAP最高为0.207 2, NDCG为0.294 7;而结构实体模型在2010年MAP高达0.281 6, NDCG为0.494 3;2011年MAP可以达到0.261 4, NDCG可以达到0.396 8.论文还分析到:异构信息网络中存在大量的谓词, 谓词的权重是各不相同的;对于一个实体而言, 一般只有几个不同的谓词;结构实体模型中可以明显看出是有效果的, 但还是没有利用到他们之间的语义信息, 在文献[
3种不同模型使用图9的形式来表示((左)无结构实体模型, (中)结构实体模型, (右)层次实体模型).文献[
3种不同的实体模型图示
Diagrams of three different types of entity model
结构化数据集具有丰富的语义关系, 而经典的基于链接的算法比如Pagerank, SimRank等都不关心边上的语义信息, 所以简单地使用Pagerank, SimRank等方法不能体现出结构化数据集的优势.文献[
在非结构化数据集上相关实体搜索的方法主要是概率语言模型, 文献[
在INEX07, INEX08上的方法对比
Comparisons of results on the INEX07, INEX08 topic sets
Models | INEX07 | INEX08 |
MAP | xinfAP | |
BBR[ |
0.180 | 0.135 |
CC_BBR[ |
0.255 | 0.312 |
KK[ |
0.184 | 0.159 |
CC_KK[ |
0.262 | |
CGSDW[ |
0.075 | 0.089 |
CC_ CGSDW[ |
|
0.334 |
目标实体类别匹配技术主要包括:
1)
精确匹配, 要求候选实体类别与查询目标实体类型完全一致.比如查询“克里斯蒂安·贝尔参演的电影”, 查询要求目标实体类型是“电影”, 如果“金陵十三钗”的类型是“中国电影”, 那即使“金陵十三钗”是正确的答案, 也会因为类别精确匹配影响正确的结果.文献[
2)
模糊匹配, 不要求目标实体类别与查询目标实体类别精确匹配, 他们之间的相关性通过文本相似性来计算.例如查询目标实体类别是“美国电影”, 而实体类别是“中国电影”, 由于两种类别之间具有相关性, 所以实体还是会被赋予一定分值.文献[
3)
结构化匹配, 利用实体类别同查询目标实体类别的上下位关系.上例查询中, 查询目标实体类别是“电影”包含“中国电影”这个类别, 所以“金陵十三钗”也是正确的结果.文献[
可以看出:目标实体类别精确匹配要求过于严格, 没有考虑类别之间的上下位关系, 会影响查询结果精度.另外, 基于候选实体生成的两种算法BBR和KK在不考虑类别匹配的情况下, 精度都要高于采用文档模型的CGSDW算法.
相似实体搜索输入的查询
由于用户背景知识所限, 有时对于一个查询不能给出很好的定义, 从而通过传统的搜索引擎得不到期望的结果.设想:在欣赏一个画展时, 用户观察到高更和梵高的画风很相似, 用户想搜索与这两个画家具有相似画风的其他画家, 然而用户并不了解他们属于什么画风.在搜索引擎中输入查询“与梵高、高更画风相似的画家”, 返回结果如
相似实体搜索示例
An example of similar entity search
相似实体搜索虽然绕过了自然语言处理的难题, 但是如何通过给出的种子实体找到与之相似的其他候选实体也是很有挑战的, 包括:
1) 如何找到种子实体之间的共同语义特征, 如何定义语义特征.例子实体之间共同的语义特征可能是间接的语义, 比如给出“巩俐、章子怡、周冬雨”作为例子, 用户的搜索意图是找出“谋女郎”, 给出的种子与“张艺谋”之间的关系是一种间接关系, 因为这几个种子实体参演了某几部由“张艺谋”导演的电影, 他们通过谓词“参演”和“导演”与“张艺谋”建立联系, 是一种间接关系.另外, 在找共同语义特征时, 还需要考虑数据集中存在知识缺失;
2) 找到共同语义特征后, 如何设计排序模型, 并对候选实体做排序.有效的排序模型才能保证得到高的精度;
3) 在大数据的背景下, 做到支持在线查询, 快速地找到与给定的种子集合相似的实体, 也是非常具有挑战的.
本节将分别在非结构化数据集和结构化数据集上介绍几种典型的相似实体搜索方法.
相似实体搜索在非结构化数据集上的方法主要包括3种:概率语言模型、机器学习方法、基于链接的方法、.
基于概率语言模型的相似实体搜索方法利用了生成式语言模型, 计算出与给定的种子实体相似性最高的候选实体[
文献[
然而, 通过机器学习方法做实体搜索存在数据稀疏问题, 对于信息量少的长尾词搜索结果不好;另一个问题是, 由于网页或者知识都是动态变化的, 某段时间用来做训练的数据集不一定能够很好地适应未来的应用.
在非结构化数据集上查找与给定的种子实体集合相似的实体, 具有代表性的工作是CMU开发的SEAL系统[
SEAL系统是与语言无关的(种子支持各种语言, 中文、英文、日文等等;处理文档的类型可以是HTML或XML), 并且不需要预先标注训练数据, 直接使用互联网语料, 模板是自动学习获得的.但由于需要根据种子节点信息实时抓取网页, 所以会有较多的时间开销.另外, 因为网页的动态性, 不同时期的查询结果可能不相同.SEAL系统不能给出种子实体具有的语义特征, 对于查找结果的解释性差.
另外一个工作SEISA[
在结构化数据集上的相似实体搜索可以充分利用数据集结构化和语义丰富的特征, 主要包括两类方法:第1类就是基于实体对相似性度量;第2类是通过找出种子实体之间的共同语义, 然后来检索相似实体.
基于语义度量的方法就是在结构化数据集或者知识库上度量语义, 从而得到与种子实体相似的候选实体.基于链接的模型是基于实体之间的链接关系, 此类方法认为:如果两个实体与同一个实体相连, 那么这两个实体是相似的.本节将对这两种方法做综述介绍.
在结构化数据集上搜索相似实体最具有代表性的工作是由Sun等人提出的PathSim[
DBLP数据模式
Data schema of DBLP
LDSD(linked data semantic distance)[
这些实体对相似度量都采用度量两个实体之间的相似性, 而不是一个实体同一个实体集合的相似性.可能存在某个候选实体与某个种子实体在某些特征上很相似, 但是与种子集合中实体的共同特征并不相似.所以, 这种基于实体对相似的度量并不适用于相似实体搜索.
此类方法是基于分析种子集合中所有种子共同语义特征, 然后根据共同特征再搜索满足这些特征的其他实体.
由Metzger等人提出的QBEES[
实体之间的相似性也可以通过使用关联规则挖掘的方法ARM[
知识库中的关系在实现相似实体搜索中是非常重要的, 关系用来限定语义, 如果不考虑关系, 将会影响到结果的精度.比如“人工智能 林肯 辛德勒名单”, 在知识库中, 3个种子实体与“史蒂文·斯皮尔伯格”都存在关系, 3部电影的导演都是“史蒂文·斯皮尔伯格”;另外, “人工智能”的编剧也是“史蒂文·斯皮尔伯格”, 如果不考虑具体的关系限定, 在返回结果中会将与“史蒂文·斯皮尔伯格”有关的电影都返回, 既包括由“史蒂文·斯皮尔伯格”所导演的, 也包括“史蒂文·斯皮尔伯格”编剧的, 与用户的查询意图不符, 影响结果的精度.
为了进一步比较说明各种方法的不同, 本节使用一个示例来将上文中提到的在非结构化及结构化数据集上的典型算法对于相似实体查找结果做展示和分析.
查询示例给出的种子实体集合为“Apollo_13, Philadelphia, Forrest_Gump”, 用户的查询意图是查找“汤姆汉克斯参演的电影”.
相似实体搜索代表方法结果示例
A case study of similar entity search
SEAL | HeteSim | QBEES | ARM |
Saving_Private_Ryan |
The_Polar_Express_(film) |
Cast_Away |
● SEAL是基于非结构化数据集上的检索结果, 是基于统计与种子实体的共现来对候选实体排序.3个种子实体与实体“Tom_Hanks”共现频繁, 所以“Tom_Hanks”也出现在结果列表中;另外, SEAL方法没有用到种子实体的共同语义信息;
● HeteSim方法是基于实体对相似度量, 结果中, 实体“Contact”与“Forrest_Gump”的相似性很高(他们具有相同的导演、相同的制片等共同语义), 但是Contact与种子实体集合并不相似(因为“Tom_Hanks”并没有出演“Contact”);
● QBEES方法的准确率最低, 其原因是知识库存在知识缺失, “Apollo_13”与“Tom_Hanks”之间不存在参演的关系, 这种基于所有种子实体都需要满足的共同语义的方法就不能利用这个与用户查询意图匹配的语义特征, 只能利用到这些种子实体都满足的一些很宽泛化的特征(比如类型都是电影、都是美国电影)进行候选实体的扩展;
● ARM方法有一定的容错性, 可以在知识库中找到满足用户意图的特征, 但是由于对语义特征的排序模型不够有效, 所以在Top-10的结果中还是有错误实体.
通过对上文的分析, 我们再对各种方法分别从所使用的数据源、对结果的解释性、是否考虑知识库缺失这3个角度做总结比较, 见
相似实体搜索方法比较
Comparison of similar entity search methods
方法名称 | 数据源类型 | 解释性 | 是否考虑知识库缺失 |
SEAL | 非结构化 | N | - |
SEISA | 非结构化 | N | - |
HeteSim | 结构化 | Y | N |
QBEES | 结构化 | Y | N |
ARM | 结构化 | Y | Y |
使用INEX09测试集和QALD(由QALD-2, QALD-3及QALD-4去掉重复查询后构成)测试集, 在每个查询对应的答案中的实体列表中抽取出不同数目的实体作为种子, 测试集的说明见
测试集描述信息
Characteristics of the datasets
INEX | QALD | |
查询数目 | 52 | 60 |
具有间接语义的查询数目 | 4 | 5 |
混合测试集中具有2个种子的查询数目 | 7 | 17 |
混合测试集中具有3个种子的查询数目 | 33 | 18 |
混合测试集中具有4个种子的查询数目 | 8 | 17 |
混合测试集中具有5个种子的查询数目 | 4 | 8 |
查询对应答案包含的的平均实体数目 | 31 | 42 |
基于
在INEX, QALD上的方法对比
Comparisons of results on the INEX and QALD
方法 | 种子数目 | INEX | QALD |
p@10 MRR R-pre | p@10 MRR R-pre | ||
SEAL |
2 |
|
.377 .550 .269 |
SEAL |
3 |
|
.363 .591 .340 |
SEAL |
4 |
|
.350 .539 .354 |
SEAL |
5 |
|
.317 .535 .352 |
SEAL |
MIX |
|
.347 .592 .335 |
在有3个种子的INEX测试集上, SEAL的R-pre最高, 这是因为SEAL使用Google搜索引擎来检索包含种子的页面, 我们发现:在返回的页面中有INEX测试集的答案文件, 对结果的提升有很大帮助.在QALD测试集上, ARM和QBEES性能较好, 它们都使用是基于种子集合共同语义的方法.另外, 几种方法在QALD测试集上的表现一般都优于INEX, 其中一个原因是因为QALD本身就是基于链接数据设计的查询, 查询语句可以直接转成SPARQL查询, 而INEX中很多查询与DBpedia知识库中的实体或者谓词都不能对应, 从而影响了放在INEX测试集上的性能.另外, 在只有2个种子时, 性能都很差, 这是因为种子数太少不利于找到种子之间的共同语义.当种子数从2增加到5时, SEAL方法的性能有提升, 只是提升的显著性随着种子数大于3之后就不再明显.对于QBEES来说, 随着种子数的增长, 性能反而降低, 尤其是在INEX上.这是因为QBEES需要所有的种子都满足某个共同语义才可以, 如果种子数增加, 考虑到知识库中存在知识缺失, 找到所有种子都满足的共同语义难度增加.
本文从实体搜索的任务以及实体搜索所使用的数据源这两个维度, 对目前已有的实体搜索方法进行了分析和对比.目前的研究工作虽然取得了一些成果, 但有些问题仍然值得深入探讨研究.
1) 数据融合
在第1.4.1节中分析了非结构化数据与结构化数据的特点, 其中:结构化数据质量高、处理相对简单, 但是不能及时地包含新出现的实体和新的关系, 而且存在知识欠缺问题;而非结构化数据尤其是网页更新很快, 数据量要远大于结构化数据.将非结构化数据和结构化的知识库相互融合, 两者可以相得益彰.非结构化数据中, 实体、关系更为丰富, 可以用来补充到结构化数据中.比如, 知识库中有三元组<冯小刚, 配偶, 徐帆>, 使用关系“配偶”来表示“冯小刚”和“徐帆”两个实体的关系.如果两个在知识库中具有某种关系的实体在相同的句子或者文章中出现, 那么他们在句子或者文章中描述的关系很可能与知识库中的关系相同.基于此, 观察从网页中抽取出的包含实体“冯小刚”和“徐帆”的句子有:“1999年, 徐帆与导演冯小刚结婚”“冯小刚发表长微博, 深情表白妻子徐帆” “冯小刚和现任老婆徐帆为什么不生子内幕”, 等等, 这样就可以挖掘出知识库中的关系“配偶”同文档中挖掘出来的“结婚”“妻子”“老婆”是相同的, 从而可以扩充知识图谱中的关系.这方面的研究在文献[
2) 搜索结果可解释性
在
3) 数据质量问题
数据质量对于搜索结果具有直接的影响, 使用高质量的数据源是得到有效搜索结果的保证.数据质量问题包括两方面, 下面将分别加以介绍.
一方面是知识缺失, 比如Wikipedia页面中并不能涵盖所有实体, 以及结构化知识库中缺失实体、关系及三元组.知识的缺失会影响到算法的精度, 比如在相似实体搜索中, 算法QBEES, HeteSim均未考虑知识缺失, 算法的鲁棒性不好, 精度没有考虑到知识缺失的ARM算法高.对于知识库中知识补全的方法主要包括利用对知识库进行张量分解的方法[
另一方面就是知识错误问题.导致出现错误知识的原因很多, 比如可能是语义的歧义、实体歧义、过时信息、单位错误等等.针对网页及知识库的错误知识发现目前有一些研究[
10.1145/1772690.1772769]]]>
10.1007/978-3-540-85902-4_22]]]>
Balog K, de Vries AP, Serdyukov P, Thomas P, Westerveld T. Overview of the TREC 2009 entity track. In:Proc. of the 18th Text REtrieval Conf. Gaithersburg:NIST, 2009.
Unger C, Forascu C, Lopez V, Ngomo ACN, Cabrio E, Cimiano P, Walter S. Question answering over linked data (QALD-4). In:Proc. of the Working Notes for CLEF 2014 Conf. CEUR-WS.org, 2014. 1172-1180.
10.1145/1367497.1367760]]]>
10.1145/1148170. 1148181]]]>
http://www.jos.org.cn/1000-9825/4387.htm[doi:10.3724/SP.J.1001.2013.04387]]]>
http://www.jos.org.cn/1000-9825/4387.htm[doi:10.3724/SP.J.1001.2013.04387]]]>
10.1007/978- 3-540-76298-0_52]]]>
10.1145/1376616.1376746]]]>
10.1016/j.artint.2012.06.001]]]>
10.1145/2623330.2623623]]]>
Zhang J, Tang J. Knowledge graph:The focus of next-generation search engine. Communications of the CCF, 2013,4(9):64-68(in Chinese).
张静,唐杰.下一代搜索引擎的焦点:知识图谱.中国计算机学会通讯,2013,4(9):64-68.
Järvelin K, Kekäläinen J. Cumulated gain-based evaluation of IR techniques. ACM Trans. on Information Systems, 2002,20(4):422-446.[doi:10.1145/582415.582418]
10.1145/1390334.1390437]]]>
Jiang LL. Studies on entity search and resolution[Ph.D. Thesis]. Lanzhou:Lanzhou University, 2012(in Chinese with English abstract).
姜丽丽.实体搜索与实体解析方法研究[博士学位论文].兰州:兰州大学,2012.
Wang D, Niu JY. Entity retrieval method based on multi-perspective association model. Computer Engineering, 2013,1(39):71-75(in Chinese with English abstract).
王东,牛军钰.基于多角度关联模型的实体检索方法.计算机工程,2013,1(39):71-75.
Zhai CX. Statistical language models for information retrieval:A critical review. Foundations and Trends in Information Retrieval, 2008,2(3):137-213.[doi:10.1561/1500000008]
Kaptein R, Kamps J. Exploiting the category structure of Wikipedia for entity ranking. Artificial Intelligence, 2013,194:111-129.[doi:10.1016/j.artint.2012.06.003]
Chen YG, Gao LX, Shi SM, Du XY, Wen JR. Improving context and category matching for entity search. In:Proc. of the 28th Conf. on Artificial Intelligence. Palo Alto:AAAI, 2014. 16-22.
10.1145/1835449.1835563]]]>
10.1145/1321440.1321542]]]>
10.1145/383952.383970]]]>
Balog K, Bron M, de Rijke M. Query modeling for entity search based on terms, categories, and examples. ACM Trans. on Information Systems, 2011,29(4):22.[doi:10.1145/2037661.2037667]
10.1007/978-3-642-14267-3]]]>
Sorg P, Cimiano P. Finding the right expert-Discriminative models for expert retrieval. In:Proc. of the Int'l Conf. on Knowledge Discovery and Information Retrieval. Setúbal:SciTe Press, 2011. 190-199.
Yang Z, Tang J, Wang B, Guo JY, Li JZ, Chen SC. Expert2Bólè:From expert finding to Bólè search. In:Proc. of the ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. New York:ACM Press, 2009. 1-4.
Lin B, Rosa KD, Shah R, Agarwa N. LADS:Rapid development of a learning-to-rank based related entity finding system using open advancement. In:Proc. of the EOS, SIGIR 2011 Workshop, 2011.
10.1007/11880592_5]]]>
10.1007/978-3-642-20161-5_52]]]>
Lawrence P, Sergey B, Rajeev M, Terry W. The PageRank citation ranking:Bringing order to the Web. Technical Report, Stanford InfoLab, 1998.
Kleinberg JM. Authoritative sources in a hyperlinked environment. In:Proc. of the 9th Annual Symp. on DIscrete Algorithm. New York:ACM Press, 1998. 668-677.
10.1145/1458082. 1458232]]]>
10.1145/1390334.1390509]]]>
Blanco R, Halpin H, Herzig DM, Mika P, Pound J, Thompson HS, Duc TT. Entity search evaluation over structured Web data. In:Proc. of the EOS. 2011. 65-71.
Halpin H, Herzig DM, Mika P, Blanco R, Pound J, Thompson HS, Duc TT. Evaluating ad-hoc object retrieval. In:Proc. of the Int'l Workshop on Evaluation of Semantic Technologies. CEUR-WS.org, 2010.
10.1007/978-3-642- 28997-2_12]]]>
10.1145/2390148.2390150]]]>
10.1145/2505515. 2507868]]]>
10.1007/11574620_14]]]>
10.1016/B978-012088469-8/50051-6]]]>
10.1145/1060745.1060828]]]>
10.1145/2452376.2452417]]]>
10.1007/978-3-642-36973-5_33]]]>
Takase S, Okazaki N, Inui K. Set expansion using sibling relations between semantic categories. In:Proc. of the 26th Pacific Asia Conf. on Language, Information and Computation. Stroudsburg:ACL, 2012. 525-534.
10.1145/1995966.1996002]]]>
Ghahramani Z, Heller KA. Bayesian sets. In:Proc. of the NIPS. 2005. 435-442.
Letham B, Rudin C, Heller KA. Growing a list. Data Miningand Knowledge Discovery, 2013,27(3):372-395.[doi:10.1007/s10618-013-0329-7]
Gupta R, Sarawagi S. Answering table augmentation queries from unstructured lists on the Web. Proc. of the VLDB Endowment, 2009,2(1):289-300.[doi:10.14778/1687627.1687661]
Van Durme B, Pasca M. Finding cars, goddesses and enzymes:Parametrizable acquisition of labeled instances for open-domain information extraction. In:Proc. of the 23rd Conf. on Artificial Intelligence. Palo Alto:AAAI, 2008. 1243-1248.
Sadamitsu K, Saito K, Imamura K, Kikui GI. Entity set expansion using topic information. In:Proc. of the 49th Annual Meeting of the Association for Computational Linguistics. Stroudsburg:ACL, 2011. 726-731.
Li XL, Zhang L, Liu B, Ng SK. Distributional similarity vs. PU learning for entity set expansion. In:Proc. of the 48th Annual Meeting of the Association for Computational Linguistics. Stroudsburg:ACL, 2010. 359-364.
Etzioni O, Cafarella MJ, Downey D, Kok S, Popescu AM, Shaked T, Soderland S, Weld DS, Yates A. Web-Scale information extraction in knowitall. In:Proc. of the 13th Int'l Conf. on World Wide Web. New York:ACM Press, 2004. 100-110.
Lang J, Henderson J. Graph-Based seed set expansion for relation extraction using random walk hitting times. In:Proc. of the Human Language Technologies:Conf. of the North American Chapter of the Association of COmputational Linguistics. Stroudsburg:ACL, 2013. 772-776.
10.1109/ICDM.2011.86]]]>
10.1145/2433396. 2433468]]]>
10.3115/1687878.1687941]]]>
10.1109/ICDM.2007.104]]]>
10.1109/ICDM.2008.145]]]>
10.3115/1699648.1699697]]]>
10.3115/1613715.1613837]]]>
10.1145/1963405.1963467]]]>
Sun YZ, Han JW, Yan XF, Yu PS, Wu TY. PathSim:Meta path-based top-K similarity search in heterogeneous information networks. PVLDB, 2011,4(11):992-1003.
10.1007/978-3-642-17749-1_14]]]>
10.1109/WI-IAT.2014.17]]]>
Abedjan Z, Naumann F. Improving RDF data through association rule mining. Datenbank-Spektrum, 2013,13(2):111-120.[doi:10.1007/s13222-013-0126-x]
Cai QQ, Yates A. Large-Scale semantic parsing via schema matching and lexicon extension. In:Proc. of the 49th Annual Meeting of the Association for Computational Linguistics. Stroudsburg:ACL, 2013. 423-433.
10.3115/v1/P14-1090]]]>
Lee JY, Min JK, Oh A, Chung CW. Effective ranking and search techniques for Web resources considering semantic relationships. Information Processing and Management, 2014,50(1):132-155.[doi:10.1016/j.ipm.2013.08.007]
10.1145/2939672.2939874]]]>
Huang JZ, Zhao SQ, Ding SQ, Wu HY, Sun MM, Wang HF. Generating recommendation evidence using translation model. In:Proc. of the 26th Int'l Joint Conf. on Artificial Intelligence (IJCAI). Palo ALto:AAAI, 2016. 2810-2816.
10.1109/ICDE. 2016.7498303]]]>
Kolda T, Bader B. The TOPHITS model for higher-order Web link analysis. In:Proc. of the Workshop on Link Analysis Counterterrorism & Security. 2006.
10.1109/ICDM.2005.77]]]>
10.1007/978-3-642-04930-9_14]]]>
10.1145/2245276.2245341]]]>
Nickel M, Tresp V, Kriegel HP. A three-way model for collective learning on multi-relational data. In:Proc. of the 28th Int'l Conf. on Machine Learning. WI:Omnipress, 2011. 809-816.
10.13140/2.1.4511.7441]]]>
Bordes A, Usunier N, García-Durán A, Weston J, Yakhnenko O. Translating embeddings for modeling multi-relational data. In:Proc. of the Advances in Neural Information Processing Systems 26, 27th Annual Conf. on Neural Information Processing Systems 2013. Berlin:Springer-Verlag, 2013. 2787-2795.
Wang Z, Zhang JW, Feng JL, Chen Z. Knowledge graph embedding by translating on hyperplanes. In:Proc. of the 29th Conf. on Artificial Intelligence. Palo Alto:AAAI, 2014. 1112-1119.
Lin YK, Liu ZY, Sun MS, Liu Y, Zhu X. Learning entity and relation embeddings for knowledge graph completion. In:Proc. of the 29th Conf. on Artificial Intelligence. Palo Alto:AAAI, 2015. 2181-2187.
Socher R, Chen DQ, Manning CD, Ng AY. Reasoning with neural tensor networks for knowledge base completion. In:Proc. of the Advances in Neural Information Processing Systems 26, 27th Annual Conf. on Neural Information Processing Systems 2013. Berlin:Springer-Verlag, 2013. 926-934.
10.1145/2882903.2882954]]]>
10.1007/978-3-319-18818-8_10]]]>
Paulheim H, Bizer C. Improving the quality of linked data using statistical distributions. Int'l Journal of Semantic Web Information Systems, 2014,10(2):63-86.[doi:10.4018/ijswis.2014040104]
10.1007/978-3-319-07443-6_34]]]>
Li X, Dong XL, Lyons K, Meng WY, Srivastava D. Truth finding on the deep Web:Is the problem solved? Proc. of the VLDB Endowment, 2012,6(2):87-108.
10.1109/ICDE.2015.7113275]]]>