3 GAnswer 系统
KB-QA中的难点之一是“歧义”问题，不同于传统的语义解析的方法，我们设计实现了一个新颖的面向知识图谱的问答系统gAnswer[8]。一方面，我们提出一种新的逻辑形式语义查询图，使用数据驱动的方式解决实体和关系的歧义，将消歧操作后推到查询执行阶段，从而提高识别精度。此方法的核心是将自然语言问题转化一个语义查询图QS，回答自然语言问题就是找到语义查询图Q在知识图谱RDF图G中的匹配。所谓“歧义后推”的方法是指，在产生语义查询图Q时我们并不做消歧的工作。如图5中短语Paul Anderson可能对应Paul S. Anderson、Paul W. S. Anderson等实体，在语义解析产生查询图QS阶段保留这些歧义,即允许问题中的“Paul Anderson”对应多个候选的实体；当进行查询图匹配时，我们发现不能找到包含Paul S. Anderson在内的匹配子图，则可以自然地抛弃这一候选实体，从而消除歧义。需要强调的一点是，我们提出了不依赖模板的语义组合方法，能够处理包括隐式关系在内的复杂问题，同时具备很好的鲁棒性和可扩展性。
3.1 GAnswer中的语义解析
GAnswer首先对问题进行语义解析，构建语义查询图。第一步是节点识别。对于自然语言问题N={w1,w2,...,wn}，其中wi是N中第i个单词、wij是N中的一个短语。节点识别的目标是在N中抽取若干wij并产生wij的候选实体/概念列表。根据各节点对应的元素类别，还需要对其进行标注，图6是节点识别的样例。不同于传统方法只识别实体等常量，我们还识别变量并进行共指消解，提高了问题理解能力。
在得到节点集合后，我们需要知晓哪些节点之间有关系，需要进行连边。给出两个节点u和v，可以调用关系抽取模型判定它们之间有没有关系，并找到候选谓词列表。关系抽取模型有两部分，第一部分利用u和v在语法依存树(dependency parse tree) Y上的最短路径同关系短语复述词典进行匹配；第二部分是隐式关系推测，是直接将u和v映射到知识库中，并进行路径挖掘，得到最可能的候选谓词集合。有了关系抽取模型，最朴素的想法是对任意两个节点u和v，判断它们之间是否有关系，但这样做的时间复杂度较高。
为了提高效率，我们提出了一个基本假设：对于两个节点u和v，它们之间存在关系当且仅当u和v在Y上的最短路径P(u, v)中不存在第三个节点w。这是由于如果u和v之间存在节点w，那么u和w之间应该比u和v更亲密，那么u应该和w连边而不是v。经过实验证明，该假设在绝大多数情况下是正确的，少数错误的情况是由于关系依存树Y本身的错误。
在通过上述假设确定哪些节点之间有关系之后，就得到了语义查询图的基本结构。再对每一对u和v调用关系抽取模块和实体识别模块，即得到完整的语义查询图。传统方法在生成逻辑形式时已经进行语义消歧，为此花费额外的算法开销并可能丢失正确解。而我们在构建语义查询图时保留歧义，并在查询阶段根据数据匹配的情况进行消歧。另一方面，由于语法依存树Y本身可能存在错误，所以语义查询图也可能存在某些错误边，例如图7中v3和v4之间的边即是不应该存在的。这些错误边在对语义查询图进行查询时也会被消除掉。
3.2 GAnswer 中的查询执行
若我们在语义查询图QS各边/点的候选关系/实体列表中选择一个确定的关系/实体替代原来各边/点的标签，则QS转化为标准的查询图Q，即可使用现有的子图匹配算法进行查询。与信息检索式方法类似，我们定义了匹配的得分并返回得分最高的k个匹配作为最终结果。
为了提高效率，一方面将子图匹配算法进行扩展，使之支持对多标签的查询图进行子图匹配。基于图遍历算法，我们将实体节点对应的各实体作为它的候选，类似于原算法中的变量；将各边作为原算法中的节点看待，为它们建立候选列表。同时，建立代价模型(cost model)来评估各遍历顺序的花销，找到预估代价最小的方案来执行算法。
另一方面，由于QS可能存在错误边，正确的语义查询图QC是QS的一个生成子图。鉴于枚举所有生成子图再进行匹配的开销十分巨大，我们设计了自底向上的贪心算法。初始从一个节点出发，每一步优先选择置信度更高的边加入查询图，并不断进行匹配来确保当前的查询图可以找到解。当匹配失败的时候标记错误边并通过回溯选择其他边，最终将找到的匹配排序并返回得分最高的k个匹配。
3.3 GAnswer 在 QALD 比赛中的表现
QALD(Question Answering over Linked Data)[20]是一系列开放领域问答比赛，从2011年开始至今已举办七届。我们的系统参加了QALD-6的评测(QALD-6是ESWC 2016会议举办的评测任务之一)，如 表1所示，以0.86的F-1值排名第二[20]。排名第一的系统CANaLI[21]并不是全自动的自然语言问答系统，它需要人工指定各短语所对应的实体和谓词，相当于要求用户自行解决消歧问题，并不适合直接与其他自动问答系统进行比较。KWGAnswer是我们开发的关键词问答系统，其表现也强于大部分自然语言问答系统。
