Source-linked AI summary
KBQA: Learning Question Answering over QA Corpora and Knowledge Bases
Wanyun Cui, Yanghua Xiao, Haixun Wang, Yangqiu Song, Seung-won Hwang, Wei Wang
TL;DR
KBQA addresses the difficulty of mapping varied natural-language questions, including complex questions, to knowledge-base queries. It uses template-based question understanding and expanded predicates, and reports effective, efficient performance that beats state-of-the-art competitors.
Problem
Natural-language questions can express the same intent in many ways, while rule-, keyword-, and synonym-based representations cannot fully capture question semantics or complex knowledge-base structures.
Method
KBQA maps questions to learned templates through conceptualization, filters entity-value pairs by answer categories, and uses expanded multipredicate paths to improve knowledge-base coverage.
Results
KBQA learns templates for 2782 predicates and beats state-of-the-art competitors in effectiveness and efficiency, especially precision.
Takeaways & Limitations
Template-based understanding supports binary factoid questions and contributes an effective component to hybrid systems for datasets containing many non-binary-factoid questions.
Takeaways & Limitations
KBQA has relatively low recall because it answers only binary factoid questions and uses strict template matching that lacks training coverage for rare predicates.
Abstract
from arXiv · showhide
Question answering (QA) has become a popular way for humans to access billion-scale knowledge bases. Unlike web search, QA over a knowledge base gives out accurate and concise results, provided that natural language questions can be understood and mapped precisely to structured queries over the knowledge base. The challenge, however, is that a human can ask one question in many different ways. Previous approaches have natural limits due to their representations: rule based approaches only understand a small set of "canned" questions, while keyword based or synonym based approaches cannot fully understand the questions. In this paper, we design a new kind of question representation: templates, over a billion scale knowledge base and a million scale QA corpora. For example, for questions about a city's population, we learn templates such as What's the population of $city?, How many people are there in $city?. We learned 27 million templates for 2782 intents. Based on these templates, our QA system KBQA effectively supports binary factoid questions, as well as complex questions which are composed of a series of binary factoid questions. Furthermore, we expand predicates in RDF knowledge base, which boosts the coverage of knowledge base by 57 times. Our QA system beats all other state-of-art works on both effectiveness and efficiency over QALD benchmarks.
1. INTRODUCTION
KBQA addresses the difficulty of mapping diverse natural-language questions, including complex questions, to structured queries over RDF knowledge bases. It uses learned templates to represent question intent and map questions to predicates and expanded predicate paths.
- Challenges: Knowledge-base QA must handle binary factoid questions and complex questions decomposable into series of binary factoid questions.The paper focuses on both question types, with examples including ranking, comparison, listing, and nested factoid questions.
- Challenges: 27M question templates span 2782 question intents, reflecting the scale of representation design required for varied natural-language questions.Templates must identify questions with the same semantics while distinguishing different intents.
- Overview of Our Approach: Expanded predicates model relations expressed as multiple RDF edges, while template decomposition handles complex questions composed of nested predicate-specific subquestions.For example, “spouse of” can be represented by marriage →person →name, and nested questions can combine that path with dob.
- Previous Works: Previous rule-, keyword-, and synonym-based approaches struggle with diverse wording, whole-question intent, and complex knowledge-base structures.Rule-based methods require infeasible manual effort, while keyword and synonym methods cannot reliably interpret context-dependent phrases or multi-predicate relations.
- Overview of Our Approach: Templates replace entities with concepts such as $city, allowing varied questions to share an internal representation while preserving intent.Context-aware conceptualization disambiguates entities and provides sufficiently granular concepts for different question types.
- Overview of Our Approach: KBQA learns template-to-predicate mappings from Yahoo! Answers by identifying entities, answers, and shared knowledge-base predicates.A template is mapped to a predicate when most of its instances share that predicate.
2. SYSTEM OVERVIEW
KBQA operates over RDF triples and learns question templates from a large QA corpus. Its online pipeline decomposes complex questions into binary factoid questions and infers answers using template–predicate distributions learned offline.
- Binary Factoid QA: KBQA focuses on binary factoid questions that ask for a specific property of an entity.The paper distinguishes these from complex factoid questions, which can be decomposed into multiple binary factoid questions.
- RDF Knowledge Base: An RDF knowledge base stores facts as triples (s, p, o), represented as directed edges from subjects to objects labeled by predicates.The system finds answers by querying this edge-labeled graph.
- QA Corpora: The QA corpus contains 41 million Yahoo! Answers question–answer pairs used to learn question templates.Each answer contains the exact factoid answer within several sentences.
- Templates: Templates are derived by replacing entities with their context-aware conceptual categories, potentially yielding multiple templates for one question.For example, an entity may produce both $Person and $Politician versions of a birth-date question.
- System Architecture: Online processing decomposes incoming questions into binary factoid questions and uses probabilistic inference based on P(p|t) to find values.The predicate distribution is learned during the offline procedure.
3. OUR APPROACH: KBQA
KBQA models question answering probabilistically, connecting questions to entities, templates, predicates, and values. It computes answer probabilities online while learning template–predicate mappings offline.
- Probabilistic model: KBQA represents answer generation as a probabilistic process from question q through entity e, template t, predicate p, and value v.The model factors this process into P(e|q), P(t|q,e), P(p|t), and P(v|e,p).
- Offline and online procedures: The system estimates P(p|t) offline, while online inference computes answer probabilities and returns the value with maximum probability.Other probability terms are computed using methods such as entity recognition and conceptualization.
- Probability computation: Entities are identified using named entity recognition and knowledge-base membership, with multiple candidate entities assigned uniform probability.The offline procedure can instead infer entity probabilities from extracted entity–value pairs.
- Question representation: Templates replace entity mentions with entity categories, such as When was $person born?, to represent question patterns.The template distribution is computed from the category distribution of an entity in its question context.
- Probability computation: For an entity and predicate, values are obtained by knowledge-base lookup, with multiple values assumed to have uniform probability.The model can return the value directly or embed it in a natural-language answer.
- Efficiency: The online procedure has complexity O(|P|), dominated by enumerating distinct knowledge-base predicates.The analysis treats entities, concepts, and values per entity–predicate pair as constants.
4. PREDICATE INFERENCE
Predicate inference learns P(p|t) from question–answer corpora by extracting entity–value triples and optimizing a probabilistic model with latent templates and predicates. EM estimation makes this optimization tractable, with overall complexity O(km).
- Likelihood formulation: The method estimates P(p|t) from question–answer corpora by first extracting question–entity–value triples.This indirect likelihood formulation reduces the influence of irrelevant answer tokens.
- Entity–value extraction: Candidate entity–value pairs require entity and value substrings connected by some knowledge-base predicate.The extraction can include noisy values, which are filtered using agreement between question and value categories.
- Likelihood formulation: The likelihood of the QA corpus is reduced to the likelihood of extracted triples under an independence assumption.The corpus likelihood and triple likelihood are related linearly after treating the number of extracted pairs as constant.
- Latent-variable model: Latent variables z_i=(p,t) identify the predicate and template generating each observed triple x_i.Introducing these hidden variables turns complete-data likelihood estimation into a more tractable objective.
- EM estimation: EM alternates an E-step that computes the expected complete-data likelihood with an M-step that updates parameters by maximizing its lower bound.The Q-function lower-bounds the log-likelihood up to a term constant with respect to the current optimization.
- Efficiency: O(km) is the overall EM complexity when the algorithm is repeated k times over m extracted triples.Predicate and template enumeration are reduced to O(m) by considering only candidates with positive model factors.
5. ANSWERING COMPLEX QUESTIONS
KBQA answers complex questions by decomposing them into sequential binary factoid questions and selecting the most likely answerable decomposition. Dynamic programming reduces the search complexity to O(|q|^4).
- Problem formulation: Complex questions are modeled as sequences of binary factoid questions whose later questions depend on preceding answers.For example, answering a spouse question supplies the entity needed by a subsequent birth-date question.
- Question decomposition: The system recursively replaces substrings with entity variables to construct candidate question sequences.Each later question uses the previous question’s answer as its entity variable, while the first retains the original entity.
- Validity scoring: A decomposition is assigned probability P(A) by multiplying the probabilities of its individual questions under an independence assumption.A sequence is valid exactly when every constituent question is valid.
- Validity scoring: Question validity scores reward valid corpus matches and penalize over-generalized patterns through counts f_v and f_o.The example assigns P(ˇq1)=1 to a valid entity pattern and P(ˇq2)=0 to an over-generalized pattern.
- Optimization: O(|q|^4) is the dynamic-programming complexity, replacing a search space of O(|q|^2k) for decompositions into k subquestions.The algorithm relies on a local-optimality property for substring decompositions.
- Efficiency: Over 99% of QA-corpus questions contain fewer than 23 words, making the O(|q|^4) complexity acceptable in that corpus.The algorithm enumerates substrings in nested loops and processes them in ascending length order.
6. PREDICATE EXPANSION
Predicate expansion represents multi-edge knowledge-base relations as predicate paths and adapts KBQA to learn and answer over them. The method limits path length and uses disk-based BFS for billion-scale knowledge bases.
- Expanded predicates: Expanded predicates represent relations as sequences of predicates, allowing KBQA to cover facts expressed by multi-edge paths.For example, spouse of can be represented by marriage → person → name.
- KBQA adaptation: Offline inference learns P(p+|t), while online inference traverses the RDF graph along p+ to compute answer values.The adaptation preserves the original offline template mapping and online value inference structure.
- Scalability: Predicate expansion limits path length to k because the number of expanded predicates grows exponentially with length.The scalable implementation also reduces starting subjects and uses memory-efficient breadth-first search.
- Scalability: The disk-based multi-source BFS scans a 1.1TB knowledge base while retaining generated paths from question entities in memory.Its time cost is mainly the knowledge-base scan repeated k times.
- Selecting path length: Larger path lengths increase coverage but also introduce meaningless relations, creating a trade-off in selecting k.The path marriage → person → dob connects Barack Obama and 1964 without an obvious useful relation.
- Selecting path length: k = 3 is selected because the number of valid expanded predicates drops significantly at length 3, suggesting most meaningful facts fit within that length.The selection uses sampled RDF paths and their correspondence with Wikipedia Infobox facts.
7. EXPERIMENTS
The experiments evaluate KBQA’s setup, effectiveness, efficiency, predicate expansion, and complex-question capabilities across large knowledge bases and QA benchmarks. Results show strong precision, fast online answering, and substantially broader predicate/template coverage, while recall remains limited by scope and rare predicates.
- Experimental setup: KBQA is evaluated on KBA, Freebase, and DBpedia, alongside WebQuestions and QALD-1, QALD-3, and QALD-5 benchmarks.KBA contains 1.5 billion entities and 11.5 billion SPO triples; Freebase and DBpedia provide public reproducibility settings.
- Experimental setup: The probabilistic framework models uncertainty arising from multiple choices during question understanding, including translating questions and entities into templates.For example, identifying an entity does not uniquely determine its category, motivating probabilities such as P(t|e, q).
- Effectiveness: KBQA beats other competitors on QALD-5 and QALD-3 across knowledge bases except squall2sparql in precision, where humans identify entities and predicates.KBQA performs best over DBpedia, which aligns with the QALD benchmarks’ design focus.
- Effectiveness: 0.67 and 0.61 are KBQA’s recalls when considering only BFQs on QALD-5 and QALD-3, respectively, over DBpedia.Overall recall is lower because the benchmarks contain many non-BFQs; 12 of 15 analyzed QALD-3 BFQ failures involved strict matching of rare predicates and templates.
- Effectiveness: KBQA’s precision is significantly higher than DEANNA’s on BFQs in QALD-1, supporting the reported advantage of template-based over synonym-based matching.The comparison uses the number of processed questions, right answers, and partially right answers defined for QALD evaluation.
- Efficiency: 79ms is KBQA’s online answering time, making it 13 times faster than gAnswer and 98 times faster than DEANNA.Offline template learning takes 1438 minutes and runs only once.
- Predicate expansion: 57 times more templates are learned with expanded predicates, while predicate expansion from paths of length 2 to k generates ten times as many predicates as direct predicates.Case studies report that the expanded predicates and learned templates are meaningful and correct in the examined examples.
9. CONCLUSION
KBQA addresses knowledge-base question answering with templates, learned template–predicate mappings, expanded RDF predicates, and decomposition of complex questions. The experiments report that it is effective and efficient, especially in precision, compared with state-of-the-art competitors.
- Conclusion: KBQA represents questions with templates, learns their mappings to predicates, expands RDF predicates, and handles complex questions through binary-factoid decomposition.These four aspects distinguish the system from previous systems.
- Conclusion: The experiments show that KBQA is effective and efficient, and beats state-of-the-art competitors especially in precision.The conclusion summarizes the reported evaluation outcome without specifying a single benchmark metric.