RDF问答系统中一种基于N-gram的消歧方法

RDF问答系统中一种基于N-gram的消歧方法

江伟豪，严丽，屠要峰，周祥生，李忠良，1(南京航空航天大学计算机科学与技术学院/人工智能学院，南京211106)2(中兴通讯股份有限公司，南京210000)1引言RDF(1)https：///TR/rdf-primer/(ResourceDescriptionFramework)资源描述框架，被广泛应用于表达互联网中的资源以及资源之间的语义关系[1].RDF的基本结构为主语、谓语、宾语所构成的三元组，可以记作，描述了以主语和宾语所代表资源之间具有谓语所代表的关系.各应用在存储RDF数据时遵守了同一协议，所以在交换RDF数据的过程中不会发生语义丢失的问题.因此，RDF被广泛应用于数据可视化、查询、交换、融合以及知识网络的构建中.对于RDF数据的查询，具有语义知识背景的专业人员可以通过构建结构化查询语言SPARQL[2]来对RDF数据进行查询.虽然结构化语言具有很强的表达能力，但由于该语言复杂的语法以及RDF数据概要的约束，使用SPARQL对RDF数据进行查询对于普通用户而言需要很高的学习成本.而通过Key搜索[3]的形式对相关RDF资源进行查询的方式虽然操作简单，但Key的表达能力有限，仅通过几个Key难以明确表达用户的查询意图.同样，使用受限的自然语言[4]来表达用户的查询意图，所提供的输入模板无法满足用户查询需求的多样性.对于基于自然语言处理的RDF问答系统，其中需要弥补自然语言与结构化查询语言之间的差异，而在具体转化过程中往往要解决由自然语言的语义多样性所造成的歧义，有研究人员依赖于提供用户交互操作[5]来解决其中的歧义问题，然而交互的次数不稳定会影响用户的查询效率.所以，解决转化过程中所产生的歧义问题成为了设计RDF问答系统的关键.基于自然语言处理的RDF问答系统主要包含以下两个处理阶段：用户意图理解和查询验证.用户意图理解的主要工作是弥补非结构化的自然语言与结构化的查询语言之间的差异，在本文中的体现则是识别用户自然语言输入的查询意图，以及将查询意图转化成相应的SPARQL查询语句的过程.而查询验证阶段则是根据构造好的查询语句匹配出与问句相关的答案并进行验证的过程.其中，本文的工作更注重于用户意图理解的阶段.由于用户表达的歧义性以及自然语言的多样性，在该过程中往往会存在歧义问题，从而导致所构造的查询语言有多种组合.在用户意图理解阶段识别出与用户查询意图最匹配以及最有可能执行成功的top-k组合，相比穷举验证的效率要高.以下，将结合例子介绍本文的研究动机.由于所提方法是针对英文语言的输入，所以本章后续的所有例子当中都以英文自然语言问句作为用户输入进行讨论.以自然语言问句：“WhatisthenameofthefilmthatdirectedbyStevenSpiel-berg?”为例，该问句所对应的SPARQL查询语句组合如图1所示.表1中展示了示例的RDF片段，其中RDF数据由三元组表示，以主语、谓语、宾语的形式组成，主语为实体资源，谓语代表关系资源，而宾语可以表示为资源也可以表示为字面量.从自然语言问句转化为SPARQL查询语句的过程中分为三个处理阶段：意图提取，资源映射，语句转化.图1SPARQL语句方案表1RDF片段示例以例句当中的Key所组成的用户查询意图可表示为：与.如表2资源映射表所示，Key“StevenSpielberg”可映射为两个不同的资源，分别为和，前者为导演，后者则为同名演员.由于用户输入歧义以及资源映射的多样性所引起的问题，称为映射歧义问题.而图1则展示了以上Key所能构成的查询语句有4种可能组合，由于自然语言表达的多样性所引起的歧义问题，称为结构歧义问题.表2资源映射表示例对于映射歧义问题，Key“StevenSpielberg”所映射的资源和，前者的类型为，而后者的类型为.然而，当已知所查询数据集的资源与搭配的可能性要比与搭配的要更高的前提下，我们可以得出与相匹配所能得出正确答案的概率要高.而对于结构歧义问题，比如是映射为<，，>还是<，，>.对于机器是难以分清以上两种组合，但如果知道前者所出现的可能性要比后者出现的要高时，此时应该选择组合<，，>来构造我们的查询语句.以上所说的可能性则是文章后续所述的联合概率的计算与比较问题.文章基于N-gram模型的原理，利用所查询数据当中三元组所映射的Key组合来充当语料库建立语义概率模型.在用户查询意图理解的过程中，通过语义概率模型计算用户查询意图中Key组合的联合概率，再通过比较相应组合的联合概率，消除其中的映射歧义.然后筛选出概率最高的top-k查询语句，执行查询语句查找相应的结果.通过基准数据集与现存的方法进行比较，本文所提出的方法在精确度和召回率方面表现优异，特别是在处理隐式关系问题方面要优于其他方法，而且本方法执行的是最能表达用户查询意图的top-k查询语言，节省了无效查询语句的运行时间.2背景知识2.1RDFRDF是用来描述互联网上资源以及资源之间相关关系的数据模型.这个资源可以是互联网中物理上的物体或者是概念的表述，比如一个人物、一个网站或者一个地址.而且资源一般使用IRI(国际资源标识符，InternationalResourceIdentifier)作为唯一的标识，例如表示物理学家阿尔伯特·爱因斯坦.RDF数据模型是以三元组为基本单位表示资源之间存在的相关关系，多个三元组所组成的数据集构造出表达资源相关关系的RDF图.在三元组当中，subject也称为主语是以上使用IRI作为唯一标识的资源或者空白节点(BlankNode，具有随机序列号作为唯一标识，所表述的是复合的资源)，宾语object则可以为资源、空白节点或字面量(可以是数字、字符串或者日期等不同的数据类型的值，数据类型可以用描述单位的IRI进行标识)，而谓语predicate则是表述主语与宾语之间相关关系的IRI.例如，三元组表示“AlbertEinstein′sdoctoraladvisorisAlfredKleiner.”所表达的意思，其中db为“http：///ontology/”的前缀缩写.对于RDF模型，我们给出以下简单定义：定义1.设G为表示RDF数据所代表的RDF图，则该RDF图是由三元组所构成的，三元组表示为∈G，s，p，o分别表示主语、谓语和宾语.其中s∈(I∪B)，I表示所有以IRI为标识的资源的集合，而B则是所有空白节点的集合，且I∩B=Ø.而p∈I，只有能够描述资源之间关系的IRI才能充当谓语.最后o∈(I∪B∪L)，L则是所有字面量的集合.根据以上描述，可以得出RDF图G=(I∪B)×I×(I∪B∪L).2.2用户查询意图由于非结构化的自然语言与结构化SPARQL查询语言之间存在差异，如何从自然语言问句当中识别出用户的查询意图并将其翻译为SPARQL查询语言是构建RDF问答系统的关键.通过借助斯坦福自然语言分析工具(StanfordParser(2)https：///software/lex-parser.shtml)对自然语言进行解析，解析后可获得包含自然语言问句语法特征的类型依赖关系树(TypedDependenciesTree)[1].如图2所示，为例句“WhatisthenameofthefilmthatdirectedbyStevenSpielberg?”所对应的类型依赖关系树.每一个单词代表一个节点，节点中使用词性标注(PartofSpeechtagging，POS)[7]对该单词的词性就行标识，节点之间存在的关系(边)则为类型依赖关系(TypedDependencies)，标识两个单词在句子中的语法依赖关系.本方法将从以上类型依赖关系树当中根据语法规则抽取描述用户查询意图的Key组合，我们把每个查询意图组合定义为语义关系来表示，以下定义2中为语义关系的描述.通过识别所有可能描述同一实体的词性标注进行实体Key的抽取作为参数保存到语义关系中，通过描述关系的词性标注进行关系Key的抽取作为关系保存到语义关系中.并且利用类型依赖关系对描述实体以及关系之间的Key集合进行连接，解决句法倒装和指代消解(CoreferenceResolution)等问题，最终组成相应的语义关系集合.由于用户意图抽取的研究不是本文所提出的贡献，而且对该项工作的研究和定义的规则也有很多，详情可以参考[8].从例句中抽取的表达用户查询意图的语义关系为，.图2类型依赖关系树示例定义2.语义关系由描述两个实体的Key集合arg1与arg2构成，这两个实体之间由描述关系的Key集合rel进行联系.2.3N-gram模型N-gram模型是一种语言模型(LanguageModel，LM)，该语言模型是一个基于概率的判别模型[9].该模型描述的是，在一个自然语言句子当中，第i个单词出现的概率只与前i-1个单词相关，而与其他的单词无关，其中组成整个句子的概率则等于每个词出现的概率的乘积，即：P(w1，w2，…，wm)=P(w1)*P(w2|w1)…P(wm|w1，w2，…，wm-1)基于马尔科夫链的假设，当前第i个单词仅与其前n个词相关，则以上概率计算可以简化为：其中每一项的条件概率将使用词语组合出现的频数C根据极大似然估计法(MaximumLikelihoodEstimation，MLE)来计算：在现实应用中N的值一般取2和3，其对应的是BiGram和TriGram模型.N-gram一般应用于词性标注、词汇分类、机器翻译以及语音识别等工作当中.3处理流程本文所提出的基于自然语言处理的RDF问答系统的处理流程如图3所示，主要包括以下流程：1)利用斯坦福自然语言分析工具解析自然语言获取相应的类型依赖关系树；2)从类型依赖关系树当中提取与用户查询意图相关的语义关系；3)利用所建立的语义概率模型对语义关系进行消歧与组合，得到联合概率top-k的语义关系组合；4)基于top-k的语义关系组合构建相应的SPARQL查询语句，在SPARQL端口上进行查询.由于本文的贡献在于语义概率模型的建立以及如何利用语义概率模型进行消歧，其他流程均使用较为成熟的方法来实现，因此以下将按照语义概率模型的建立以及查询语言的消歧过程进行讨论.图3处理流程图3.1语义概率模型的建立由于所建立的语义概率模型需要反映所查询数据的特征，而本文所查询的数据集来源于DBpedia(2015)，所以我们使用该数据集所映射的Key集合来建立语义概率模型.对于数据源当中的每一个实体资源，首先需要知道实体与描述该实体的关键字之间的对应关系，形如表3中的Key与实体资源的映射词典DE.DBpedia的实体资源映射表一般建立的方法是以Wikipedia中的链接为锚点链接(AnchorLink)[10]，从该链接中的文章抽取Key建立相应的映射关系，如CrossWikis[11]所实现的实体映射词典.而本方法则是直接从DBpedia-lookup(3)http：///中的Key与实体资源的映射索引中抽取映射关系实现我们的映射词典.表3Key实体资源映射词典除了Key实体映射词典外，仍需要Key与关系之间的映射词典DR，如表4所示，而关系则相当于连接两个实体的关系路径，如之前表达“directedby”的关系.而关系与Key的映射存在关系连接的问题，如关系则需要表示为的连接.而关系映射仍然不是本文研究的重点，我们将使用Patty[12]中依靠依存关系基于规则去构建Key与关系之间的映射词典.表4Key关系映射词典具备上述的Key实体资源映射词典DE和Key关系映射词典DR，对于数据集当中的三元组，从DE中可以获取描述subject与object所代表实体的Key集合DE(subject)→K(s)=(a1，a2，…，ai)和DE(object)→K(o)=(b1，b2，…，bj)，ai、bj分别对应描述实体subject与object的Key.其中，当object为字面量的情况下，以该字面量的类型来充当Key(如int整型，则以val_int充当相应的Key).而从DR中可以获取描述predicate所代表关系的Key集合DR(predicate)→K(p)=(c1，c2，…，ck)，ck为描述关系predicate的Key.据此得到描述整个三元组的Key组合(K(s)，K(p)，K(o))，根据该组合建立语义概率模型有如下定义：定义3.描述三元组的Key组合为(K(s)，K(p)，K(o))=((a1，a2，…，ai)，(c1，c2，…，ck)，(b1，b2，…，bj))，而为了区分该Key所代表的资源是充当主语还是宾语，将以上Key组合扩展为(，(a1，a2，…，ai)，(c1，c2，…，ck)，(b1，b2，…，bj)，).根据N-gram模型中当N=2时的BiGram定义，组合(，ai，ck，bj，)所出现的概率为：P(ai，ck，bj)=P(ai|)P(ck|ai)P(bj|ck)P(|bj)根据贝叶斯公式，需要记录(×K(s))，(K(s)×K(p))，(K(p)×K(o))，(K(o)×)的词语排列(也称为片段)出现次数，假设各Key集合中不存在重复的Key，则每个三元组构建出的模型空间复杂度为O((ijk)2).定义4.对于三元组，当主语subject和宾语object都有其对应的类型T(s)与T(o)，则从DE中获取到描述两个类型的Key集合分别为DE(T(s))→(d1，d2，…，dp)与DE(T(o))→(e1，e2，…，eq)，同样将以上Key组合进行扩展为(，(d1，d2，…，dp)，(c1，c2，…，ck)，(e1，e2，…，eq)，)，根据BiGram的定义，组合(，dp，ck，eq，)所出现的概率为：P(dp，ck，eq)=P(dp|)P(ck|dp)P(eq|ck)P(|eq)根据贝叶斯公式，需要记录(×K(T(s)))，(K(T(s))×K(T(p)))，(K(T(p))×K(T(o)))，(K(T(o))×)的片段出现次数，假设各Key集合中不存在重复的Key，则每个类型三元组构建出的空间复杂度为O((pqk)2).根据以上定义建立语义概率模型，总的空间复杂度为O((ijk)2+(pqk)2).该语义概率模型不仅可以在用户意图理解阶段进行消歧以优化处理过程.基于该语义概率模型还可以实现输入提示机制，在用户输入自然语言问句的时候显示与前一个词最相关的top-kKey以协助用户进行输入描述问题.3.2基于语义概率模型进行消歧问答系统需要将自然语言问句中用户的查询意图翻译成相应的SPARQL查询语句进行查询，其中存在由语义多样性所造成的资源映射歧义以及结构歧义的问题.本小节将介绍利用上述所建立的语义概率模型在用户查询意图翻译为SPARQL语句的阶段解决以上歧义问题.对于表示用户查询意图的语义关系，各元素代表描述相应实体以及关系的Key集合，其目的是匹配数据源当中符合(，，)所映射资源的三元组.但由于用户的语言习惯或者语法倒装的存在，语义关系所描述的三元组在数据源当中可能以(，，)的形式存在，即存在结构歧义.在传统的处理方法当中，可以通过枚举所有的可能组合形式进行查询验证，但是当所查询语义关系的数量增多时，组合的数量也会呈指数增长，此时使用穷举的方式进行验证将消耗大量的查询时间，特别是数据量较大的情况下，用户查询的效率将受到严重影响.而我们的解决方法则是利用语义概率模型计算并比较不同组合的联合概率.设δ(R)为代表语义关系R=的所有组合的集合，计算δ(R)中每个组合的联合概率，δ1=(arg2，rel，arg1)，δ1∈δ(R)的联合概率为P(arg2，rel，arg1)(相关计算请参照上述联合概率的介绍)，描述顺序(，arg2，rel，arg1，)所代表的三元组存在于数据源当中的概率，其中和为三元组首尾标志.多个语义关系相连接则分别计算各语义关系，最后将对应语义关系概率相乘则得到联合概率，然后根据概率排序并选取最优的top-k组合转化为相应的查询语句进行查询验证，通过这种方式可以解决结构歧义问题，从而排除较低可能性的查询组合.对于包含疑问词的语义关系，如(“What”，“isthenameof”，“film”)，只需以变量代替疑问词的位置，则得到的语义关系为.而对于带变量的语义关系的联合概率的计算，其中P(rel|?x)的计算需要在语义概率模型中查找以rel为后缀片段的数量，然后加入到条件概率的计算当中，而对于语义关系，则计算P(?x|rel)时需要在语义概率模型中查找以rel为前缀片段的数量，其他部分的条件概率计算与上述过程中的一致，在此不再赘述.由于用户的语义使用习惯不同以及Key与资源的一对多关系会存在资源映射歧义的问题.当语义关系满足以下假设时，将扩展候选Key的成员：假设：prefix和suffix属于语义关系中的两个相邻成员，当满足：1)当C(prefix)≠0且C(prefix_suffix)=0时，查找满足C(prefix_*)≠0的Key集合σ1(wi)，计算σ1(wi)中Key与suffix的语义相似度θ(wi，suffix)，当相似度大于所设定阈值γ，即θ(wi，suffix)>γ时，加入wi到suffix的候选集合当中参与联合概率的计算.2)当C(suffix)≠0且C(prefix_suffix)=0时，查找满足C(*_suffix)≠0的Key集合σ2(wj)，计算σ2(wj)中Key与suffix的语义相似度θ(wj，suffix)，当相似度大于所设定阈值γ，即θ(wj，suffix)>γ时，加入wj到suffix的候选集合当中参与联合概率的计算.例如在该语义关系所计算的语义关系中，rel在语义概率模型中是可以查找到的，即C(rel)≠0，由于用户的使用习惯或者语义的多样性导致用户所输入的词语arg1和arg2无法在语义概率模型中找到，表现为C(prefix_rel)=0，C(rel_suffix)=0.此时我们从语义概率模型中找出满足C(*_rel)≠0的Key集合σ1(wi)，计算其中Key与rel的语义相似度θ(wi，rel)，当该值大于我们所设定的阈值γ时，表示该Keywi与原Keyarg1是有语义相似性的，所以将wi加入到arg1的候选集合c(arg1)当中，参与联合概率的计算.同样，满足C(rel_*)≠0的Keyσ2(wj)，当其中的Key满足θ(wj，rel)>γ时，也将wj加入到arg2的候选集合中，所以最初的语义关系的联合概率可使用候选集合中的Key来近似计算：P(arg1，rel，arg2)≈P(wi，rel，wj)wi∈c(arg1)&wj∈c(arg2)在应用中，计算语义相关性的工具有很多，比如WordNet(4)https：///.而在实现中我们使用了Word2Vec来计算Key的语义相关性，Word2Vec可以指定训练语料库去训练隐藏层的模型，在应用过程中可以使用反映所查询数据集数据特征的语料库用作训练数据集.而阈值γ的选取反映了所加入候选词与原Key的语义相似程度，在实现中将γ设置为0.5，也可通过训练的形式寻找最佳的γ值.对于语义关系中arg1和arg2可以映射为实体或者标签.当映射为标签的情况下，如arg2映射为标签，则原语义关系需扩展为，.而当arg2代表非资源型属性时，即arg2代表一个字面量，则以该字面量的对应类型val_type来替代arg2的位置去计算该语义关系的联合概率.算法1.筛选top-k联合概率最高的语义关系输入：语义关系组合R输出：top-k语义关系组合1.M←Ø2.δ(R)←find_All_Combinations(R)3.forrinδ(R)：4.p=1.05.forinr：6.c(arg1)←wfromC(arg1_rel)=0&C(w_rel)≠0&θ(w，arg1)>γ7.c(rel)←wfromC(arg1_rel)=0&C(arg1_w)≠0&θ(w，rel)>γ8.c(arg2)←wfromC(rel_arg2)=0&C(rel_w)≠0&θ(w，arg2)>γ9.c(rel)←wfromC(rel_arg2)=0&C(w_arg2)≠0&θ(w，rel)>γ10.forwiinc(arg1)：11.forwjinc(rel)：12.forwkinc(arg2)：13.p=p*P(wi，wj，wk)14.M←((wi，wj，wk)，p)15.sortwithP(M)16.returntop-ksemanticrelationinM由于自然语言表示的多样性，在自然语言表述当中存在显示关系和隐式关系的表达，例如，“WhichelectronicscompanieswerefoundedinBeijing?”为隐式关系表达，而其对应的显示关系表达为“Whichcompany′sindustryiselectronicswerefoundedinBeijing?”.显式关系所抽取的用户查询意图为，<companies，foundedin，Beijing>，而隐式关系所抽取的用户查询意图则为.对于实体中带有修饰词的语义关系，需要考虑其中是否包含隐式的语义关系，所以将其扩展为，，并计算其联合概率，加入到top-k可能组合的排序中.需要说明的是，如果语义关系当中包含描述类型的Key，如当中”companies”属于类型，则需要在计算联合概率时将其扩展为，.4实验本文在DBpedia上的基准数据集中验证所提出的方法.所使用的自然语言问题来自QALD-6.QALD(5)http：///是针对关联数据问题回答的一系列评估活动.与QALD-6当中的CANaLI[13]，UTQA[14]，KWGAnswer[15]，NbFramework[16]，SEMGraphQA.进行对比.文章所提方法是使用Java语言实现的，所进行的实验运行于搭载IntelCoreCPU3.80GBHz，32GBRAM的Windows10平台当中.4.1实验数据集DBpedia是一个从维基百科(WikiPedia)中提取结构化信息，并且将数据存储为RDF形式发布到互联网上的组织.本次实验中所使用的数据集为2015年发布的DBpedia数据集(6)http：///2015-10/core-i18n/en/，其中包含了约5百万个实体，约11亿个三元组，所包含RDF数据集的容量约为8.9GB.文章中所使用的计算词语之间的语义相关性的工具为Word2Vec_Java(7)https：///NLPchina/Word2VEC_java，是基于文献[18]中所介绍的Word2Vec模型建立的Java应用工具.Word2Vec是一个用于生产词向量的相关模型，该模型为浅而双层的神经网络.我们所用的训练语料集为Wikipedia+Gigaword5(6B)(8)https：///3Top/word2vec-api，维度为300，词典大小为400000.4.2实验验证本次实验将验证QALD-6中的多语言回答问题(MultilingualquestionansweringoverDBpedia)的100个测试问题.由于我们的方法是处理英语语言方面的自然语言问题，所以在对比的时候也是使用英语语言的自然语言问句.对于中文的自然语言处理方法，可根据目标领域(如文献[19]中面向电商领域的问答)选取语料训练集建立语义概率模型，使用中文自然语言解析器(如StanfordParser的中文解析模块)对语句进行解析，再根据中文语法对解析结果进行查询意图的提取，利用所建立的语义概率模型或者自定义消歧方法(如文献[20]中的滑动语义消歧方法)进行消歧后转化为相应的查询语句即可查询相关内容.在实验当中，我们将与上述所提方法在以下指标中作对比，分别为准确率(Accuracy，A)，所解决的问题占问题总量的比例；精确度(Precision，P)，所查出的正确资源占结果总量的比例；召回率(Recall，R)，所查出的正确资源占正确问题总量的比例；F-1(F1-Measure)=2×P×R/(P+R)，为精确度与召回率的调和平均值.表5中展示了我们所提方法(简称为NGQA)与各方法在执行测试数据后测量的以上指标的数值.表5验证QALD-6的测试问题从实验结果中得知，本文所提出的方法在F-1评价中排名与NbFramewrk并列第二.我们的方法在一百个问题当中能够解决其中的58个问题，精确度为0.85，召回率为0.88，其中召回率只比CaNaLI要低，但是比其他的方法要高.其中需要注意的是，CaNaLI需要用户输入受限的自然语言问句，即用户需要以准确的资源名称(IRI表示)去表达问句当中的资源以及关系.换言之，CaNaLI解决受限自然语言V在用户层面，以用户自身的认知去进行消歧的，而我们的问答，方法却没有这种限制.在实验过程当中，本文的方法在解决单三元组问题(如问题：“WhowasthedoctoralsupervisorofAlbertEinstein?”查询时只包含单个三元组：)的时候正确率、精准度和召回率都很高.我们将无法解决的问题进行了分类分析，总结出了以下原因，如表6中所示.在无法解决的问题中，其中占比最高的是错误的资源映射问题，用户所输入的自然语言问句当中所包含的Key映射无法映射到正确的资源当中，从而导致问题的查询失败，如问题“Whatisthefullname