ACL2020 KBQA based on query graph generation to answer multi-hop complex questions

Abstract:At present, there are two kinds of complex problems: constraint problem and multi-hop relationship problem. In this paper, the ACL2020 KBQA based on the query graph generation method to answer the multi-hop complex problem is understood and read, and the related experiments are reproduced.

1, the

1.1 Complex problems

1) Constrained problems

2) the problem of multi-jump relationship

1.2 An improved phased query graph generation method is proposed

1.3 SOTA in three data sets: CWQ, WQSP and CQ

2, introduce

2.1 Complex problems

(1) The problem of single-hop relationship with constraints

• Who was the first president of the U.S.?
• Single-hop relationship: “president_of”
• Known entity: “U.S.”
• Constraint word: “first”

(2) the problem of multi-jump relationship

• Who is the wife of the founder of Facebook?
• Two-hop relationship: “wife_of”, “founder_of”

2.2 Solution: Consider longer relational paths, but the search space grows exponentially as the path length increases

2.3 Challenge: How to limit the search space? There have been previous approaches that have been proposed that only consider the best relationship that matches, not all of the relationships. But it didn’t deal with both types of complex problems at the same time.

2.4 Solution: Beam Search

2.5 Improvement: path extension + merge constraint, serial to parallel, effectively reducing the search space

3, methods,

3.1 Preparatory work

(1) the KB

• K={(h,r,t)}
• H, T comes from the entity set E
• R comes from the relational set R

(2) KBQA: Given a question Q, find an answer A from KB

3.2. Stage query graph method

(1) Four types of nodes, as shown in the figure below

• A grounded entity: An existing entity in KB that has at least one (Shaded Rectangle)
• An Existential Variable/Existent Variable/Intermediate Variable: 0 or more (no shaded rectangle)
• A lambda variable represents the answer, with one and only one (round)
• Aggregation function: maximum/minimum/sum operation, 0 or more (diamond)

(2) The edge of the query graph is R in KB

(3) The process of query graph generation is the process of SPARQL query statement generation, as shown in the figure below. Note: Not exactly the same as the example above.

Where, NS: M. 0K2KFPC is the MID (Freebase) of the grounded entity,? Name3 is an unknown variable, right? E1,? E2,? E3,? E4 and so on are the intermediate variables.

3.3 General process of phase query graph generation

1) Starting from a topic entity in the question, identify a core relation path to connect the topic entity to a lambda variable;

2) Add one or more constraints to the core relationship path, which contains a grounded entity or an aggregate function with a relationship;

3) Generate the candidate query graph, measure the similarity between questions and questions, and sort (CNN and other neural networks);

4) Take top1 and execute the query graph on the knowledge graph to get the answer.

Note: the core relational path, in other papers, is called the core inference chain, or the basic query graph

3.4, motivation

(1) Problems:

• Existing methods only consider the core path of a single relationship or two relationships, which cannot solve the problem of multi-relationship constraint.
• If the core relationship path is allowed to be longer, the search space will increase dramatically;
• On the CWQ dataset, there are 10,000 paths per problem for three hops.

(2) Beam Search

• When generating t+1 hop relational paths, only top-k t-hop relational paths are retained, that is, only K are generated for each path.
• The existing methods ignore the constraint condition and only consider reducing the search space through the path.
• Constraints in the problem can also help reduce the search space and steer the core path toward the correct path generation.

(3) Improved phased query graph generation method

• It is not necessary to generate all the core relationship paths before attaching constraints;
• The combination of bundle search and semantic matching results in a smaller search space.
• Given a partial core path (The Jeff Probst Show, convention for, Y1, District, Y2), consider all relationships connecting Y2 on KB if extending a relationship on Y2, However, if a constraint is added first (is A, TV producer), only the TV producers nominated for XX show will be considered.

3.5. Query graph generation

(1) Beam search generates query graph

• Assume that the t-th iteration generates K query graphs, expressed as G_t;
• In the t+1 iteration, for each graph g∈G_t, three operations {extend, connect, aggregate} are used to add an edge and a node, as shown in the figure below.
• All the generated graph sets are expressed as G ‘_(t+1), sorted by score function, and top-K graphs are selected to obtain the candidate query graph G_(t+1).
• Iteration continues until no g∈G_(t+1) scores higher than g∈G_t.

(2) extend operation (extend)

• Add a relationship;
• If the current query graph has only one subject entity E, the extension operation adds a relation R of E, and the other end is lambda variable X.
• If the current query diagram contains a Lambda variable X, the extension operation converts X to an Existential variable Y, finds the relation R of Y, and generates a new Lambda variable X.

(3) Connect operation (Connect)

• In addition to the subject entity, there will often be some other ground entity in the problem.
• The join operation links the grounded entity E to the lambda variable X or an Existential variable connected to X.

(4) Aggregate operation (Aggregate)

• Predefine a keyword set to detect constraint words;
• The aggregation operation connects the constraint word as a node to the lambda variable X or to the Existential variable X.

(5) Innovation of the method: the extension operation can be applied after the join or aggregate operation, but not the previous method.

• Previously: extension → extension →…… → extend → join or aggregate
• Now: extend, connect, aggregate → extend, connect, aggregate →…… → Expansion, Connection, Aggregation

3.6. Query graph sort

(1) Method: In the t-th iteration, sort the candidate query graph G ‘_t, generate a 7-dimensional feature vector, input it to the full connection layer, and calculate the score.

(2) Characteristics

1 d:

• Semantic matching model based on BERT; (Pytorch version: https://github.com/huggingfac…
• The query graph G ∈G ‘_T is transformed into a word sequence according to the generation order of the graph
• Ignore intermediate and unknown variables
• The following query graph generates the sequence of :(The, Jeff, Probst, Show, convention, for, and nominees).

Dimension 2: the sum of the entity link scores of all grounded entities; Entities (Google link: https://developers.google.com.)

The third dimension: the number of grounded entities;

Fourth dimension: the number of entity types;

Fifth dimension: the number of time expressions;

The sixth dimension: the number of superlative expressions;

Seventh dimension: the number of answer entities.

(3) Reinforcement learning method, learning decision function.

4,

(1) Data

• ComplexWebQuestons (CWQ) Data Amount: 34689
• WebQuestionsSP (WQSP) data size: 4737
• Complexquestions (CQ) Data volume: 2100

(2) Results

(3) Ablation test

The improvement in model performance is not only related to Bert.

Paper: Lan Y, Jiang J. Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases[C]//Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020: 969-974.

__ links: _https: / / www.aclweb.org/anthol…

_ code: _https: / / github.com/lanyunshi/…

Click on the attention, the first time to understand Huawei cloud fresh technology ~