#gStore-weekly | gAnswer源码解析 关系提取

简介

gAnswer是由北京大学王选计算机研究所邹磊老师牵头开发的基于知识库问答的系统，通过将自然语言转化成查询图，再和RDF图做子图匹配得到用于查询的SPARQL语句。

今天分享的关系提取部分的主要目的是为查询图中的每条边确定合适的谓词候选集合，其主要思想是通过离线建立的关系提及词典（Relation Mention Dictionary）获取可能的谓词，并在依存树上匹配，根据匹配的结果筛选候选谓词。

关系提取（Relation Extraction，下文简称RE）在BuildQueryGraph.java中的调用的位置如下所示，主要实现了extractRelation和matchRelation两个方法。

//step2: Find relations (Notice, we regard that the coreference have been resolved now)
t = System.currentTimeMillis();
qlog.semanticUnitList = new ArrayList<SemanticUnit>();
extractRelation(semanticUnitList, qlog); // RE for each two connected nodes
matchRelation(semanticUnitList, qlog); // Drop the nodes who cannot find relations (except implicit relation)
qlog.timeTable.put("BQG_relation", (int)(System.currentTimeMillis()-t));

传入的参数semanticUnitList对象是类型为SemanticUnit的ArrayList，每一个元素表示一个语义模块，即查询图中的每个节点及其邻居节点的集合，而RE的主要任务就是赋予它们之间的边的信息，换句话说，就是要确定连接该节点和邻居节点的谓词。

ExtractRelation方法是通过在依存树上进行子树匹配获得候选谓词的集合，是RE模块的主要部分，matchRelation方法通过在哈希表中进行查找过滤掉没有找到谓词的边，防止后续生成SPARQL时遇到没有谓词的情况，以下对这两个方法进行更为详细的说明。

extractRelation方法

ExtractRelation方法的主要思想是对于依存树中的每一个节点，将其指代的单词利用离线构造的关系词典获得对应的mention集合，并将这些mention和依存树进行子树匹配，按匹配程度返回候选的谓词。

具体而言，首先通过双重循环枚举查询图中相邻的两个端点，然后调用findRelationsBetweenTwoUnit方法来为这两个端点之间的边分配候选谓词。在findRelationsBetweenTwoUnit方法中，首先将这两个节点之间最短路径上的单词全部放入subBoW_T
中，并在关系词典中查找每一个单词对应的relation mention，放入candidatePatterns
作为候选的谓词。

// Find candidate patterns by SubBoW_T & inveretdIndex
HashSet<String> candidatePatterns = new HashSet<String>();
for (String curWord : SubBoW_T) 
{
    ArrayList<String> postingList = Globals.pd.invertedIndex.get(curWord);
    if (postingList != null) 
    {
        candidatePatterns.addAll(postingList);
    }
}

接下来枚举candidatePatterns
中的每一个谓词，通过子树匹配的方法来检验该谓词是否为最合适的谓词。子树匹配的过程是，首先将该谓词全部拆开（比如词组"directed by"拆成"directed"和"by"两个单词），然后从最短路中的每个节点开始都尝试在其子树中进行匹配：建立一个队列，开始只有当前节点，每次取出队首的节点，如果当前谓词和队首节点相等，就将该节点的孩子加入队列中，并累加匹配个数，直到该谓词全部匹配完或队列为空。

while (unMappedLeft > 0 && (curNode=queue2.poll())!=null) 
{
    if (curNode.word.isIgnored) continue;
    int idx = 0;
    for (String ss : BoW_P) 
    {
        // words in pattern only can be matched once
        if (!matchedFlag[idx]) 
        {
            // check word 
            if (ss.equals(curNode.word.baseForm)) 
            { 
                unMappedLeft --;
                subTreeNodes.add(curNode);
                queue2.addAll(curNode.childrenList);
                matchedFlag[idx] = true;
                mappedCharacterCount += ss.length();
                if(shortestPath.contains(curNode))
                {
                    hitPathCnt++;
                    if(curNode!=n1 && curNode!=n2)
                        hitPathBetweenTwoArgCnt++;
                }
                break;
            }
            // check POS tag
            else if (ss.startsWith("[") && posSame(curNode.word.posTag, ss)) 
            { 
                unMappedLeft --;
                subTreeNodes.add(curNode);
                queue2.addAll(curNode.childrenList);
                matchedFlag[idx] = true;
                mappedCharacterCount += curNode.word.baseForm.length();
                mappedCharacterCountPunishment += 0.01;
                break;
            }
        }
        idx ++;
    }
}

执行匹配之后，首先排除失配数高于阈值的以及可以被其他匹配完全覆盖的匹配。之后会对剩余的匹配进行打分：每一个匹配的得分为该谓词中成功匹配的单词比例 * (1+匹配的单词在最短路径上的比例)，在这个基础上，如果匹配的字符越长，得分也会越高。

double matched_score = ((double)(BoW_P.length-unMappedLeft))/((double)(BoW_P.length));
if (matched_score > 0.95) 
    matched_score *= 10; // Award for WHOLE match

// The match ratio between pattern and path larger, the score higher; especially when uncovered with the two target nodes
if(hitPathCnt != 0)
{
    double hitScore = 1 + (double)hitPathCnt/(double)BoW_P.length;
    if(hitPathBetweenTwoArgCnt == hitPathCnt)
        hitScore += 1;
    else if(shortestPath.size() >= 4) // If path long enough, pattern still cover with the target nodes, punishment 
    {
        //hitScore = 0.5;
        if(hitPathBetweenTwoArgCnt == 0) // If path long enough, pattern cover with target nodes totally, punishment a lot
            hitScore = 0.25;
    }
    matched_score *= hitScore;
}

matched_score = matched_score * Math.sqrt(mappedCharacterCount) - mappedCharacterCountPunishment;

到此为止，对于查询图中的每一条边，findRelationsBetweenTwoUnit方法就能返回带有分数的候选谓词集合，用于后续在生成SPARQL的同时为其打分。

得到了所有边后，extractRelation方法会根据点和边的数量判断是否有环，如果有，会将每条边中isSteadyEdge
变量设置为False
，表示在后续和RDF图匹配时需要进行模糊匹配。

matchRelation方法

MatchRelation方法相比于extractRelation就简单了许多，就是将没有找到谓词的边删去，认为其是误连接的边。因为所有边存储在qlog.semanticRelations
对象中，而边对应的两个端点存储在临时的semanticUnitList
对象中，因此matchRelation将qlog.semanticRelations
中每条边的两个端点存放在哈希表中，并用semanticUnitList
去查找，只有查找结果不为空时，才将对应的两对节点存储在qlog.semanticUnitList
中。

以上就是gAnswer中关系提取的部分，接下来会用完善的查询图和RDF图匹配，生成最终的SPARQL语句。