We present a question answering system over linked data. We use natural language processing tools to extract slots and SPARQL templates from the question. Then, we use semantic similarity to map a natural language question to a SPARQL query. We combine important words to avoid loss of meaning, and compare combined words with uniform resource identifiers (URIs) from a knowledgebase (KB). This process is more powerful than comparing each word individually. Using our method, the problem of mapping a phrase of a user question to URIs from a KB can be more easily solved than without our method; this method improves the F-measure of the system.
Question answering (QA) systems (QASs) find the answers to natural language (NL) questions by analyzing huge corpora. In the big data era, this property of QA is increasingly necessary. Two popular types of QAS are those based on information retrieval (IR) and those based on knowledgebases (KBs).
Most IR-based QASs use the following general strategy [
Recently, very large, structured, and semantically-rich KBs have become available;
examples include Yago [
In FALCON [
Translating NL questions into SPARQL query requires performing both a
disambiguation task and a mapping task. DEep Answers for maNy Naturally Asked questions
(DEANNA) [
In this paper, we aim to solve the problem of translating the NL question into a SPARQL query to search for the answer in the KB. To improve the F-measure of the system, we use linguistic information about the user question, and semantic similarity for translating the NL words into the words in the KB.
We used semantic similarity based on Explicit Semantic Analysis (ESA) [
However, previous work did not use our approach in this problem of using semantic
vectors from Wikipedia. FREyA uses a method that generates suggestions with string
similarity and hierarchy defined in an ontology, scores them again using string
similarity algorithms, then maps them to high-scoring concepts in the ontology. PowerAqua
[
We built our system by extending TBSL [
In which country does the Nile start?
Slot : <?x, resource, Nile> <?c, class, country> <?p, property, start > SPARQL Template: SELECT ?x WHERE {?x ?p ?y . ?x rdf:type ?c} Slot with URI : < res:Nile, resource, Nile> <dbo:country, class, country> <dbo:sourceCountry, property, start> SPARQL query: PREFIX dbo: <http://dbpedia.org/ontology/> PREFIX res: <http://dbpedia.org/resource/> SELECT DISTINCT ?x WHERE{ res:Nile dbo:sourceCountry ?x .
?x rdf:type dbo:Country .} 2.2
We use NL analysis to extract slots. Given NL question inputs, we classify questions to detect question-type keywords (e.g., “who”, “what”, “when”, “where”, and “how”). The heuristics to extract slots and templates differ slightly among question types. After the question is classified, the question is analyzed at the word, syntactic, and semantic levels. For these analyses, we used ClearNLP1, which is available in github. Additionally, we used open NLP2 for chunking. For named entity (i.e., resource) disambiguation, we used AIDA3. Additionally, we used keywords of questions provided by Question Answering over Linked Data (QALD-44) organizers. Using the result of NL analysis, we developed several rules to extract slots.
First, we check all words in the NL question and find a word to maximize the appropriateness score (eq. 1), which will become a class (i.e., answer type). The class is a type of proxy variable x that the question seeks.
( )
= ( ) + ( ) + ( ),
(1)
where is word i in the question, ( ) is the pre-defined weight when the
POS of is NN or NNS; otherwise ( ) is 0. ( ) is the pre-defined
weight when is a dependency of the main verb; otherwise ( ) is 0.
( ) is the pre-defined weight when is a head of question type; otherwise
( ) is 0. We determine appropriateness scores by analyzing the answer type in
QALD-4 training data and UIUC data [
Heuristics Class Extraction Input S – Natural language question
Initialize class c as null; the appropriateness score of null is 0; the number of words in the NL question is n 1: For all words in the NL question 1: Calculate the appropriateness score of wi and the appropriateness score of current c 2: Compare the appropriateness score of wi and the appropriateness score of current c 3: Update current c as the lemma of wi if the appropriateness score of wi > current c
When the named entities or noun phrases consist of more than one word, we use a dependency parser and a chunker to concatenate words in the noun phrase into one word before applying the heuristic rules. For example, first we use AIDA or given keywords to detect the named entity (i.e., resource). Named entities are usually subjects or objects in the NL questions. We used the dependency parser to concatenate “Walt” and “Disney” to “Walt Disney”, which we regard as one word.
We use AIDA and given keywords to extract the named entity. We use the chunker to extract the noun phrases and our heuristics to extract the class and then apply the chunker to obtain the predicate between the subject and object (Fig. 2). First, we extract entities as a subject and object, for example, “television show” and “Walt Disney”. To extract the predicate between them, we use the dependency parser to detect the head of each word. We finally extract the predicate, which is a chunk that includes the two heads. If the heads are the same word, we regard the head as the predicate. If the two heads are not in the same chunk, we concatenate two chunks into the predicate. After the QALD-4 deadline passed, we added graph-based reduction rules (Fig. 3) to extract slots. 1. Initialize dependency graph: We obtain a dependency graph from the result of the dependency parser. Each node has information such as word surface form and lemma form, and each edge represents a dependency relation. 2. Determine reduction policy tag by reduction rules: We give four policy tags, remove (OMT), merge (MRG), reverse (REV), and remain (REM) to each node followed by rules that check information such as the POS of the head, the dependent of the POS, the dependency-label (e.g., SUB or OBJ) and the word of the dependent and the head. 3. Apply Reduction policy: We apply four reduction policies to the initial dependency graph to reduce it.
These graph-based reduction rules improve our total system F-measure in the QALD4 test dataset, but they still have limitations. First, devising rules to determine tags is a difficult task. Moreover, we determine each node as subject, predicate or object by the distance from “question-type keywords” (e.g., “who”, “what”, “when”, “where”, and “how”). For a question such as “Give me all movies with Tom Cruise.”, the slots are difficult to extract. 2.3
We used lexical information from each question to extract the appropriate SPARQL template. · Template for a Boolean question: ASK WHERE { ?x ?p ?y. }
Using lexical information, we detect whether the question is a “wh-question”. If the question is a “yes/no question”, it does not include “question-type keywords”. We regard each question as a “yes/no question” if it contains neither question type words nor “list-question keywords” (e.g., “Give”, “List”). · Template for a simple question: SELECT DISTINCT ?x WHERE { ?x ?p ?y . (Option:?x rdf:type ?c.)} We define the basic query template as above. Optionally, we used ?c (replaced with class) if the class is exactly correct. Our class detections module works well for a “which” question or a “who” question. We usually include only one triple. We use lexical information (conjunction such as “and” and relative pronoun such as “who”) and a dependency parser to extract n triples, but this remains a difficult task. We must extract more than one triple to successfully translate the NL question into a SPARQL query in some cases. However, we cannot extract n triples in many cases such as “Give me all films produced by Steven Spielberg with a budget of at least $80 million.”, because it does not include a conjunction or relative pronoun explicitly; to extract n triples is a difficult task to complete by only using heuristics. · Template for including an aggregation function question: We used the “aggregation” attribute, which indicates whether any operations beyond triple pattern matching are required to answer the question. We define “aggregation” functions as “count”, filter” and “order”, and define the modifier target as a proxy that is the target of the aggregation function. We used three types of functions, for example: ─ COUNT: SELECT COUNT (DISTINCT ?x) WHERE { ?x ?p ?y. } ─ ORDER: SELECT DISTINCT ?x WHERE {?x ?p ?y. } ORDER BY DESC(?x)
OFFSET 0 LIMIT n ─ FILTER: SELECT DISTINCT ?x WHERE {?x ?p ?y . FILTER (?y <1950)} Some words indicate the types of functions to use. We define these words as “aggregation indicators”. For example, if the sentence contains “How many” we extract COUNT template and extract the target, i.e., the head of the “many”. If the question contains a superlative, we infer that the question requires an ORDER operation. If the question contains a comparative, we infer that the question requires a FILTER operation. We use the head-dependency relation of an “aggregation indicator” to detect the targets of these types of operations and the constant (e.g., 1950) that the filter uses. 2.4
The process (Fig. 4) for mapping proxy variables to URIs entails the following seven steps: 1. Identify resource/class URIs from noun Phrases: We use noun phrases delivered from the slot extraction module to identify URIs from the KB; normal noun phrases are regarded as class type URIs, and proper noun phrases are regarded as resource-type URIs. We built an inverted index of all resource/class type URIs from DBpedia; consequently, the actual mapping is performed by searching the inverted index with variant forms of NPs, which were generated by heuristics in capitalization and white spacing; this process works well. To map quickly, we used lucene5. 5 http://lucene.apache.org/
Search the NL pattern: We used PATTY6 to map NL predicates to the words in the KB. However, in most cases, the PATTY pattern repository failed to map the predicates from the questions into the appropriate words in KB.
Retrieve predicate URI candidates: We determine that the predicate URI is a word from the user’s phrase; this word is translated to words extracted from the KB. We collect predicate URI candidates occurring in triples that have a resource or class that was previously identified as a subject or object. Queries to retrieve predicates are structured as follows:
<SPARQL Query for collecting predicate URI candidates from resource> SELECT DISTINCT ?p WHERE { {<IDENTIFIED_RESOURCE_URI> ?p [] .} UNION{[]?p<IDENTIFIED_RESOURCE_URI>.} }
<SPARQL Query for collecting predicate URI candidates from class> SELECT DISTINCT ?p WHERE { {?x ?p []. ?x rdf:type <IDENTIFIED_CLASS_URI>.} UNION {[] ?p ?x. ?x rdf:type <IDENTIFIED_CLASS_URI>.} } Choose a string from the NL against which to measure the semantic relatedness: Pattern matching alone is insufficient to translate predicates in the NL question to predicate URIs. The slot extraction phase delivers several strings for measuring the semantic relatedness. Each string includes a different set of classes that restrict the meaning of the predicate. Restricting the meaning of the predicate helps ESA to choose the most relevant predicates. For example, the NL question "In which country does the Nile start?" requires the predicate URI "sourceCountry" for class type: Country. Measuring the semantic relatedness using the string "start" did not assign a high score to the desired predicate URI, but using the string "start country" did. Adding class information such as “start country” to the predicate is better than using only a predicate such as “start” to represent the user intention and semantic meaning of the question.
Rank predicate URI candidates by semantic similarity: Calculate the semantic relatedness between each predicate URI in the KB and the string from the question.
Choose n-best predicate URI candidates: Choose n-best similar predicate URIs from the KB. We experimentally determined n many times. In our cases, n > 2 was not helpful; it decreased the precision much more than it increased the recall.
Query generation with n-best predicates: Replace the slots with identified URIs and complete the query. This process identifies the proxy variables that the question requires. 6 http://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yagonaga/patty/
We used the QALD-4 test dataset for task 1 to evaluate the proposed method and used DBpedia 3.97 as the KB. We mainly compare two approaches. One (P) uses only pattern matching to identify resource/class/predicate URI, and the other (P+ESA) combines pattern matching to identify the resource/class URI and ESA to identify the predicate URI. The latter yielded a higher F-measure than did the former. Additionally, we added graph-based reduction rules to the latter, and this P+ESA+graph approach yielded the highest F-measure. We used the ESA open library8. The test dataset includes 31 simple questions, four yes/no questions and 15 questions with aggregation. 4
To evaluate the QA system, we used global precision, recall and F-measure (Table 1). Graph-based reduction reduces the parse tree by applying predefined reduction rules. P+ESA+graph yielded a higher F-measure than did P+ESA. Graph-based reduction is in initial development; we will continue to improve it. We do not have results for graphbased reduction in Tables 2-4. In this section, we mainly compare our semantic similarity approach and pattern matching approach. We usually used pattern matching (e.g., capitalization and white spacing) to map a class and resource. However, most predicates cannot be mapped using pattern matching, so we used ESA when mapping the NL predicate to the predicate URI in the KB. We show the number of questions that were answered successfully by predicate mapping using ESA (Table 2) and pattern matching (Table 3). The proposed method of computing semantic similarity achieved higher precision and recall than did the previous pattern matching approach (Tables 2, 3).
Method
P 50
P + ESA 50 P+ESA+graph 50
We successfully extracted slots and templates for 38 of the 50 questions. We finally generated 28 SPARQL queries using P+ESA and 31 SPARQL queries using P+ESA+graph. Among them, we used P+ESA to extract 10 correct answers and three partially correct answers (Table 1). We used P+ESA to map 13 NL predicates to appropriate predicate URIs in the KB without graph-based reduction (Table 2). The number of appropriate mapping results was the same as the result of the whole system. We used pattern matching to map three NL predicates to the appropriate predicate URIs in the KB (e.g., we can match “are spoken in” to “spokenIn”). We used both PATTY and the pattern matching (e.g., white spacing and capitalization). PATTY failed to map predicates in all cases. The pattern matching mapped only three appropriate predicate URIs but could not map classes and resources in the three questions, so we did not generate SPARQL queries from them and obtained no answer (Tables 1, 3).
Consequently, we focused on using P+ESA. We successfully extracted slots and templates for 38 questions and then generated 28 SPARQL queries. Many of the queries failed to map the proxy variables to the appropriate URIs for some of them; this is a difficult task. We analyzed error cases to learn ways to improve the global F-measure (Table 4).
Error Case Failed to detect entity in sentences and map to a correct resource/class URI in the KB.
Failed to map to a correct predicate URI in the KB. Failed to extract correct triple patterns.
What was Brazil’s lowest rank in the FIFA World Ranking? - “FIFA Word Ranking” should be treated as a predicate, but the cue gave a wrong hint that this should be treated as a resource.
Give me the grandchildren of Bruce Lee.
- Complex predicate “grandchildren” in the user question should be handled as a composite of the predicate “children”. is based on TF/IDF and is not sophisticated enough.
More sophisticated measuring similarity method may be useful.
A dictionary for implicit predicates or complex predicates may be useful. 5
Using a dependency parser and other NLP, we extracted appropriate slots for SPARQL queries. We used prepositions to find URIs as well as nouns and adjectives, which are known as the most useful terms to find keywords. Additionally, we combined pattern matching with semantic similarity based on ESA to identify URIs. To improve the ESA result, we compared not only the predicate with predicate URIs in DBpedia but also concatenated the predicate with additional information to increase the concreteness of the meaning representation. This approach is more accurate than the pattern matching approach. By concatenating additional information to the predicate, we increased the effectiveness of mapping proxies to URIs. Our approach is domain-independent; consequently, it can be adapted easily to other KBs such as Yago2 and Freebase.
The proposed system in this paper is our initial system, and we will continue to develop it. In future work, we will develop our graph-based reduction rules, extract slots by reducing the number of nodes in the dependency parse tree and will use machinelearning algorithms. Furthermore, we will develop methods to select valid answers among the answer candidates.
Acknowledgments. This work was partly supported by the ICT R&D program of MSIP/IITP [10044508, Development of Non-Symbolic Approach-based Human-Like Self-Taught Learning Intelligence Technology] and the National Research Foundation of Korea (NRF) [NRF-2014R1A2A1A01003041, Development of multi-party anticipatory knowledge-intensive natural language dialog system].