2019, Vol. 51
知识库(knowledge base, KB)以大量复杂且结构化的知识，存储与描述着互联网中的数据，为机器提供了一种更加可读的知识网络，助力其从语义角度理解用户的搜索意图，从海量数据中快速、准确地获得有价值的结果，并呈现与搜索结果关联的整个知识体系，满足信息时代人们更具深度与广度的数据需求.知识库中的知识条目(即事实, fact)被表示为一个形如(subject, relation, object)的三元组，其中subject和object表示实体，relation描述subject和object间的语义关系.基于知识库的问答(QA-KB)旨在对自然语言形式的查询需求或问题进行分析处理，并将来自于知识库的三元组(或三元组集合)作为输出返回给用户.例如问题“红楼梦的作者是谁？”对应的答案三元组为“(红楼梦, 作者，曹雪芹)”，而为了回答问题“红楼梦的作者是哪个朝代的？”，需要对知识库中的两个三元组“(红楼梦, 作者, 曹雪芹)”，“(曹雪芹, 所处时代, 清朝)”进行整合.针对上述的两个示例，前者被我们称为“单跳问题”，后者被我们称为“多跳问题”.
目前针对QA-KB的研究方法大致可以被分为两种思路.第一种围绕语义解析，旨在将自然语言问题通过语义解析方法转化为逻辑表达式，再将其转化为如SPARQL的查询语言检索知识库得到答案[1-3].而另一种QA-KB思路不依赖逻辑表达式，围绕深度学习模型直接致力于问题与三元组的匹配，是近几年比较常见的做法[4-9].而这类QA-KB方法大多基于一个分步式的处理流程，即APA (alignment-prediction-answering)框架.它将整个问答过程拆分为实体识别、实体链接、关系预测等多个分离的任务，各任务都有独立的目标与处理逻辑.最后，各任务都会选择在当前步骤下的局部最优解，通过串联得出最终答案，在决策本质上属于贪心思想的范畴，缺乏统一化的建模架构与全局化的优化策略.即使研究者们在上述每个任务上都取得了优异的效果，但整个QA-KB系统的表现却很少有明显提升.另一方面，愈发复杂的监督学习模型对训练数据的数量与质量提出了较高要求，尤其在中文领域，开放的问答数据集较少，覆盖面有限，模型泛化性能难以提升.
因此基于上述两点考虑，我们提出了一种端到端的无监督QA-KB模型，并使用动态规划算法支撑模型的综合决策与全局优化，我们称其为“DPQA”.通过实验，我们证明了DPQA在中文问答数据集上具有良好的建模效果与泛化能力，尤其在解决多跳问题上有突出表现，为现有的问答方法框架提供了新的思路.
1 DPQA知识库问答模型如果将知识库中所有三元组组织起来，将(s, r, o)中s, o作为节点，r作为连接节点的有向边，就得到了一张大规模的有向图.由于知识库中的实体并不都存在关联，所以此时的图是非联通的.我们人为构造一个新节点N0，此节点不表征知识库中任何一个实体，但在图上与其他所有节点都能通过一条有向边相连，那么此时就将知识库中的所有知识信息表示成一张有向联通图.
设自然语言形式的问题为q=(w1, w2，…，wn)，其中wi为问题所包含的词语，n为词语个数，问题答案在图上对应的节点集合为N(q)，那么整个QA-KB问题就被转化为在给定序列q的条件下，从节点N0到N(q)的最佳路径问题.我们选择动态规划方法解决最佳路径问题.下面就对DPQA模型中涉及的状态单元定义、状态转移以及整个算法流程进行详细描述.
1.1 状态单元定义我们将每个状态单元定义为四元组st=(j, p, N, W)，各元素的详细说明如表 1所示.系统中所有的状态单元组成状态集ST，在算法运行前，ST中仅包含n个初始状态st0=(-1, 0, N′, Wq)，n由问题q的单词个数决定，N0为上文中人为构造的初始节点，各初始状态仅在Wq上取值不同，第i个初始状态st0i的Wq取值为Wiq=(wiq, …, wnq)，即q的长度为n-i+1的后缀子序列.
|
表 1 状态四元组说明 Tab. 1 Description of state quad |
随着算法的运行，如果某状态st满足状态转移条件，则衍生新状态st′=(j′, p′, N′, W′)加入到ST中，st′的各元素的取值也在表 1中加以说明.状态转移条件与迭代打分函数f将在后文中详述.
1.2 状态转移我们按当前状态是否是初始状态，分两种情况分析：如果当前状态为初始状态，即还未从初始节点出发识别到任何实体，此时需要利用问题中的可用词语构建候选mention，并在M2E(mention-to-entities)反向映射表中查找可以匹配到的实体.M2E表的构造方法比较简单：遍历知识库中的所有实体，将每个实体N的名称(以及“简称”、“英文名”等“别名”信息)记录在一个表中，并添加一条从该名称到实体N的映射，如果该名称已在表中(存在同名实体)，则将此映射追加到原有记录之后；若当前状态不是初始状态，表示已经在问题中识别到了实体，设其为s，此时需要在包含s的所有三元组(s, r, o)中抽取候选关系r，结合状态目前可用词语列表判断是否满足状态转移条件.
综合上述两种情况的分析，在给定当前状态st=(j, p, N, W)及W的前缀子序列Wi=(w1, w2, …, wi)时，我们对状态转移的规定如下：
1) 如果st为初始状态，则将Wi内的词语进行拼接得到候选mentionMi，如果在反向映射表中存在Mi到实体N(Mi)的映射，则认为满足转移条件，产生一个(如存在同名实体则产生多个)新状态st′=(j+1, 1, N(Mi), Wic)，其中Wic为W删除Wi得到的后缀子序列.
2) 如果st为非初始状态，则对于所有包含N的三元组(N, r, N′)，如果similarity(r, Wi)>θ，则认为满足转移条件，产生新状态st′=(j+1, f(p, r, Wi), No, Wic).
上述条件中，similarity(r, Wi)表征了r与Wi的相似性，θ为人为设定的阈值.θ一方面让我们通过实验对其进行调整，以优化算法结果；另一方面也可在算法运行过程中起到剪枝效果，提高效率.我们将r与Wi的相似性定义为其包含的文本信息在语义向量空间上的距离，并使用word2vec[10]训练词语的语义向量.设r，Wi的语义向量分别为vr，viW，则可以将Wi的语义向量viW定义为
| $ \mathit{\boldsymbol{v}}_i^W = \frac{{\mathit{\boldsymbol{v}}_1^w + \mathit{\boldsymbol{v}}_2^w + \cdots + \mathit{\boldsymbol{v}}_i^w}}{i}, $ |
以及将r与Wi间的相似度定义为向量间的余弦相似度
| $ similarity\left( {r,{W_i}} \right){\rm{ = }}\frac{{{\mathit{\boldsymbol{v}}_r} \cdot \mathit{\boldsymbol{v}}_i^W}}{{\left\| {{\mathit{\boldsymbol{v}}_r}} \right\|\;\;\left\| {\mathit{\boldsymbol{v}}_i^W} \right\|}}. $ |
进一步，我们设计了迭代打分函数
| $ f\left( p, r, {{W}_{i}} \right)\text{=}p\cdot \left( similarity\left( r, {{W}_{i}} \right)\cdot 0.5-\theta +1 \right) $ |
为了更直观地对DPQA的状态转移过程进行说明，图 1对问题“请问摩尔定律的提出者是哪个国家的?”在DPQA算法中产生的完整状态转移图进行了展示.针对st02-st2-st5-st7这条路径，首先从初始状态st02出发，W2可以满足状态转移条件1)，从而产生新状态st2.然后对于存在的三元组(摩尔定律, 提出者, 戈登·摩尔)，similarity(r, W2)>θ满足状态转移条件2)，于是产生新状态st5.之后st5由于三元组(戈登·摩尔, 国籍, 美国)再次满足条件2)产生了st7.此时st7无法再满足条件1)或2)，路径结束，并将st7所到达的实体“美国”作为此路径上的最终答案.
|
图 1 状态转移过程示意 Fig. 1 Instance of state transition process |
结合上文的分析结果与定义，DPQA完整的算法流程如下所示.
输入:问题q=(w1q, w2q, …, wnq)，知识库所有三元组集合T反向映射表M2E
输出:问题的答案在知识库中对应的实体Nq
初始化状态集ST={st01, st02, …, st0n}，其中st0i=(-1, 0, N0, (wiq, …, wnq))
for st=(j, p, N, W=(w1, …, wm))in ST do
for i=1 to m do
Wi=(w1, …, wi) if j=-1 then
顺序拼接Wi中所有词语得到Mi
if Mi in M2E then
将st′=(0, 1, N(Mi), (wi+1, …, wm))加入状态集ST
end if
else
for (N, r, N′)in T do
if similarity(r, Wi)>θ then
将st′=(j+1, f(p, r, Wi), N′, (wi+1, …, wm))加入状态集ST
end if
end for
end if
end for
end for
在算法最后，如果拥有最高得分的状态存在多个，我们将根据状态所在路径上第一次跳转时所使用的词语长度排序，即在问题中识别到最长mention的状态将作为最佳状态.如果此时最佳状态仍有多个，则再根据“知名度”指标对第一次跳转到的实体进行排序，即将mention链接到最高知名度的实体的状态作为最终的输出状态.在具体实现过程中，我们通过统计在知识库中包含某个实体的三元组个数，获取该实体的“知名度”.
2 DPQA实验分析本节中，我们通过实验证明DPQA模型的有效性.我们首先对实验所使用的数据集、知识库、对比方法、评测指标以及实现细节加以描述，并对实验结果进行详细分析.
2.1 数据集与评测指标我们使用了3个数据集进行实验，包括2个中文数据集及1个英文数据集.在中文数据集上，我们首先使用了NLPCC 2016在open domain Chinese question answering挑战任务中发布的中文KBQA数据集(后文中用“NLPCC”标识)，包含14 609条训练数据及9 870条测试数据.数据仅包含单跳问题.另外，由于目前领域内尚缺乏开放的面向多跳问题的中文QA数据集，为了验证模型在多跳问题上的有效性，我们基于NLPCC所包含的单跳问题，通过扩充问句内容的方式，构建了一个专注多跳问题的中文KBQA数据集(后文中用“NLPCC-MH”标识)(https://github.com/wavewangyue/NLPCC-MH).NLPCC-MH数据集共包含4 000条训练数据与1 000条测试数据，数据涵盖2~3跳的问题.最后，在英文数据集上我们选择了领域较为常用的WebQuestions[11]，包含3 000条训练数据与2 032条测试数据.在中文数据集上的实验中我们使用北京航空航天大学ACT实验室所构建的开放领域中文知识库(http://www.actkg.com/)，共包含10 921 453个实体，13 522 532条关系以及51 339 398项事实.在英文数据集上的实验使用Freebase[12]作为知识库.
在对比方法上，我们寻找了以下3种方法进行实验：其一是Yih等人提出的QA方法[3]，也是NLPCC 2016在当次KBQA测评任务上的基准方法(后文以“NLPCC-BASE”标识)；其二是Bao等人参考翻译模型所实现的问答方法[13](后文中以“CYK”标识)；其三是我们在APA框架下所实现的监督学习方法，基于BiLSTM-CRF训练实体识别模型[14]，使用Seq2Seq作为关系预测模型[15](后文中以“Seq2Seq”标识)，在3个数据集上均参与比较.
本文采用F1均值作为各方法的评测指标，即模型在每条测试数据上所取得的F1的平均值.
2.2 实验结果经过实验对比，针对中文数据集NLPCC，NLPCC-BASE方法取得的F1均值为52.5%，Seq2Seq方法为54.9%，而DPQA达到64.8%，超过其他两种监督学习方法，证明了DPQA模型良好的建模效果，以及在不依赖训练数据的情况下所取得的较强的泛化能力.在中文多跳数据集NLPCC-MH上，Seq2Seq方法与DPQA分别达到33.4%与64.8%，差距明显.而在英文数据集WebQuestions上，CYK、Seq2Seq与DPQA方法的F1均值分别达到37.5%、47.4%与38.4%，DPQA没有取得与监督学习方法Seq2Seq比肩的效果.
通过对实验结果的进一步分析，我们将DPQA在中文数据集上的优势归结为以下两点：其一，DPQA对复杂实体名的识别效果更好，包括长实体如“清填漆戗金凤纹莲瓣式捧盒”，中英文混合实体如“华擎G41 M-VS2”等；其二，DPQA克服了训练数据不平衡问题的影响.当某些关系在训练集中出现次数极少或极多时，有监督的机器学习方法会更倾向于语义相近但在训练中出现次数更多的关系，甚至出现过拟合问题.而DPQA不依赖训练数据，其在关系匹配上更为公平准确.在多跳问题上，Seq2Seq方法预测出的关系序列仍不能保证准确且完整，一半以上都存在对跳数的分割不准确或对序列中某部分预测错误的情况.而DPQA在大多数情况都能规划出一个完整准确的路径，即使问题中存在着多次语义关系的转折.
另外，由于中英文在语序及语义表达等方面都有很大差异，建立在中文顺序表达规则上的DPQA在WebQuestions就无法取得与监督学习方法Seq2Seq比肩的效果，但也超过了监督学习方法CYK.
为了具体分析DPQA的不足，我们在3个数据集上分别抽取了部分DPQA预测错误的数据，人工观察并分析出错原因，分析结果如下：第一，部分实体出现在问句的末尾而不是开始，例如“who did the voice for Lola Bunny？”，而依赖中文顺序表达习惯的DPQA未能对出现在实体之前的词语合理利用，此类情况在中文数据集不明显，但在英文数据集上较为突出；第二，由于问句中包含的语义关系表达不明显甚至较隐晦，导致未经训练的DPQA很难将这种语义关系与知识库中的关系名联系起来.例如问题“韦德是哪的人？”中，“是哪的人”与关系“出生地”的相似度不高；第三，部分问题中的mention会链接到多个同名实体上，例如问题“清凉寺是在什么地理位置？”中，预测实体为“清凉寺(南京市清凉寺)”而正确实体为“清凉寺(河北省清凉寺)”.此类错误大多由于同名实体在知识库中的表现相似时不易区分，且问题本身也缺乏更明确的指代信息.
3 结论近年来的QA-KB方法大多在APA框架下进行，本质上是用贪心思想作决策，且严重依赖训练数据质量.本文为探索问答方法的新思路，提出了基于动态规划、无监督且端到端的DPQA模型.经过实验，DPQA在问答数据集上均取得良好效果，特别是在中文多跳问题上表现突出，给开放领域问答系统的实现提供了简单可行的方案.
| [1] |
KRISHNAMURTHY J, MITCHELL T M. Weakly supervised training of semantic parsers[C]//Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Jeju Island, 2012: 754-765.
(  0) |
| [2] |
BERANT J, LIANG P. Semantic parsing via paraphrasing[C]//Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. Baltimore, 2014: 1415-1425.
( 0) |
| [3] |
YIH W T, CHANG M W, HE X, et al. Semantic parsing via staged query graph generation: question answering with knowledge base[C]//Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing. Beijing, 2015: 1321-1331.
( 0) |
| [4] |
BORDES A, CHOPRA S, WESTON J. Question answering with subgraph embeddings[C]//Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Doha, 2014: 615-620.
( 0) |
| [5] |
DONG L, WEI F R, ZHOU M, et al. Question answering over freebase with multi-column convolutional neural networks[C]//Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing. Beijing, 2015: 260-269.
( 0) |
| [6] |
YANG Y, CHANG M W. S-MART: novel tree-based structured learning algorithms applied to tweet entity linking[C]//Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing. Beijing, 2015: 504-513.
( 0) |
| [7] |
YU M, YIN W D, HASAN K S, et al. Improved neural relation detection for knowledge base question answering[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Vancouver, 2017: 571-581.
( 0) |
| [8] |
HAO Y C, ZHANG Y Z, LIU K, et al. An end-to-end model for question answering over knowledge base with cross-attention combining global knowledge[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Vancouver, 2017: 221-231.
( 0) |
| [9] |
TURE F, JOJIC O. No need to pay attention: simple recurrent neural networks work[C]//Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Copenhagen, 2017: 2866-2872.
( 0) |
| [10] |
MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]// International Conference on Neural Information Processing Systems. Lake Tahoe, 2013: 3111-3119.
( 0) |
| [11] |
BERANT J, CHOU A, FROSTIG R, et al. Semantic parsing on freebase from question-answer pairs[C]//Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. Seattle, 2013: 1533-1544.
( 0) |
| [12] |
BOLLACKER K, EVANS C, PARITOSH P, et al. Freebase: a collaboratively created graph database for structuring human knowledge[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. Vancouver, 2008: 1247-1250.
( 0) |
| [13] |
BAO J W, DUAN N, ZHOU M, et al. Knowledge-based question answering as machine translation[C]//Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. Baltimore, 2014: 967-976.
( 0) |
| [14] |
LAMPLE G, BALLESTEROS M, SUBRAMANIAN S, et al. Neural architectures for named entity recognition[C]//The 15th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. San Diego, 2016: 260-270.
( 0) |
| [15] |
SUTSKEVER I, VINYALS O, LE Q V. Sequence to sequence learning with neural networks[C]//Proceedings of Advances in Neural Information Processing Systems. Montreal, 2014: 3104-3112.
( 0) |